19 de Março de 2002   Lógica

Perplexidades lógicas

Desidério Murcho

Este estudo tem por objectivo fornecer ao leitor já familiarizado com a lógica elementar alguns resultados menos evidentes cujo desconhecimento pode gerar alguma perplexidade. Os resultados aqui apresentados são os seguintes: o conjunto de todas as conectivas lógicas binárias, a distinção entre a relação de derivabilidade e a de condicional, a relação lógica entre o modus ponens, o princípio do terceiro excluído e o princípio da não-contradição, a definição de fórmula satisfazível do cálculo de predicados, e a intransitividade da derivabilidade num sistema de lógica livre. A minha esperança é estimular os leitores a ter uma visão ampla e crítica da lógica.

Viver Para Quê?

Também em Kindle

1. Conectivas lógicas

O cálculo proposicional clássico conhece quatro conectivas binárias e uma unária:

∨, ∧, →, ↔, ¬.

Sabemos que podemos prescindir de quaisquer três das primeiras quatro e ficar apenas com a restante e a negação. Mas sabemos também que a economia tem um preço: quanto mais económico for um sistema dedutivo (quer quanto ao número de conectivas, quer quanto ao número de axiomas e de regras de inferência), mais prolixas serão as suas demonstrações. Conversamente, quanto mais prolixo for um sistema dedutivo (quer quanto ao número de conectivas, quer quanto ao número de axiomas e de regras de inferência), mais económicas serão as suas demonstrações.

Apesar de tradicionalmente o cálculo proposicional conhecer no máximo quatro conectivas binárias, as conectivas binárias possíveis são no entanto dezasseis, número que resulta da combinação exaustiva dois a dois (porque são dois os valores de verdade) das quatro filas existentes numa tabela de verdade com duas variáveis proposicionais. A tabela que se obtém é a seguinte:

1
 
2
¬∧, |
3
4
¬⇐
5
6
¬⇒
7
8
¬∨, ↓
V V V F V F V F V F
V F V V F F V V F F
F V V V V V F F F F
F F V V V V V V V V
9
10
¬↔
11
12
¬←
13
14
¬→
15
16
 
V V V F V F V F V F
V F V V F F V V F F
F V V V V V F F F F
F F F F F F F F F F

A análise da tabela acima revela imediatamente que as conectivas 9-16 são a negação das conectivas 1-8, e reciprocamente. Para cada conectiva tradicional existe por isso outra conectiva que é a sua negação. As conectivas 2, 8, 10 e 14 são, respectivamente, a negação das conectivas 15 (∧), 9 (∨), 7 (↔) e 3 (→). É também instrutivo notar que o traço de Sheffer (|) — capaz, só por si, de representar todas as funções de verdade — é de facto a negação da conjunção (conectiva 2) e que a adaga de Quine (↓) — também ela capaz de, só por si, de representar todas as funções de verdade — é de facto a negação da disjunção (conectiva 8).

Excluídas as tradicionais e as suas negações, ficamos com oito conectivas. Destes oito, podemos concentrar a nossa atenção apenas nas quatro primeiras, pois as restantes são apenas a negação destas.

Destas quatro, a 5 é obtida por comutação das variáveis proposicionais a partir da 3 (→), podendo por isso ser representada por «←».

Restam assim três conectivas, dos quais a 1 é pouco interessante, uma vez que transforma em verdade lógica todas as proposições nas quais esta conectiva seja a principal, independentemente do valor de verdade das variáveis proposicionais.

As duas conectivas que restam são a 4 e a 6. Mas imediatamente se percebe que a 4 se obtém na verdade por comutação a partir da 6, de forma que podemos concentrar a nossa atenção na 6. No entanto, é a negação da 6 que é realmente interessante, de forma que vamos tomar 11 («⇒») como primitiva e a 6 como a sua negação. A conectiva «⇒» garante que se obtém o valor de verdade V se e só se a segunda variável proposicional tem o valor de verdade V.

Com a nossa nova conectiva «⇒» podemos simplificar algumas proposições da lógica clássica. A verdade lógica seguinte

(1) [(Q → ¬P) → ¬(P → Q)] → P

pode agora exprimir-se do seguinte modo:

(2) (Q ⇒ P) → P.

(2) pode acrescentar-se como axioma a um sistema axiomático do tipo do de Hilbert, pois representa o comportamento da própria conectiva «⇒». Será interessante verificar se as demonstrações num sistema que contenha esta nova conectiva resultam mais económicas, como é legítimo esperar.

2. Derivabilidade e condicional

A relação lógica entre a derivabilidade e a condicional é a seguinte: sejam A e B duas fórmulas moleculares do cálculo de predicados ou do cálculo proposicional; então

(3) para quaisquer A e B, se A ⊢ B então A → B
(4) existem fórmulas A e B tal que A → B e A ⊬ B.

A proposição (3) é na verdade o Teorema da Dedução, cuja demonstração não cabe apresentar aqui. A proposição (4) demonstra-se da seguinte forma:

  1. Seja T uma teoria axiomática independente para o cálculo proposicional.
  2. Nenhum axioma de T é derivável a partir de outro qualquer axioma.
  3. Mas todos os axiomas são verdades lógicas.
  4. Se duas fórmulas A e B são verdades lógicas, então têm o mesmo valor de verdade. Logo, A e B são equivalentes.
  5. Mas se duas fórmulas A e B são equivalentes, então A → B.
  6. Logo, para quaisquer axiomas R e R* de T, R → R*.
  7. Existem assim fórmulas A e B tal que A → B e A ⊬ B.

3. Modus ponens e terceiro excluído

Uma aplicação do resultado anterior é o seguinte: é óbvio que dadas quaisquer duas verdades lógicas S e S*, S → S* e S* → S, e assim não é de estranhar que o princípio do terceiro excluído

(TE) A ∨ ¬A

e a formulação proposicional da regra de inferência modus ponens

(MP) [A ∧ (A → B)] → B,

formem condicionais verdadeiras, tanto numa direcção como na outra. Mas é agora pertinente perguntar se TE se deriva de MP e reciprocamente. A resposta positiva demonstra-se assim:

Caso 1: TE ⊢ MP

1.   A ∨ ¬A TE
2.   (A → B) ∨ ¬(A → B) 1, RI
3.   ¬(A → B) ∨ (A → B) 2, Comutatividade de «∨»
4.   ¬(A → B) ∨ (¬A ∨ B) 3, Eliminação da «→»
5.   [¬(A → B) ∨ ¬A] ∨ B 4, Associatividade de «∨»
6.   ¬[(A → B) ∧ A] ∨ B 5, De Morgan
7.   [(A → B) ∧ A] → B 6, Introdução da «→»
8.   [(A → B) ∧ A] → B 7, RI
9.   [A ∧ (A → B)] → B 8, comutatividade de «∧»

Caso 2: MP ⊢ TE

1.   [A ∧ (A → B)] → B MP
2.   [(A → B) ∧ A] → B 1, Comutatividade de «∧»
3.   [(A → B) ∧ A] → B 2, RI
4.   ¬[(A → B) ∧ A] ∨ B 3, Eliminação da «→»
5.   [¬(A → B) ∨ ¬A] ∨ B 4, De Morgan
6.   ¬(A → B) ∨ (¬A ∨ B) 5, Associatividade de «∨»
7.   ¬(A → B) ∨ (A → B) 6, Introdução de «→»
8.   (A → B) ∨ ¬(A → B) 7, Comutatividade de «∨»
9.   A ∨ ¬A 8, RI

Uma vez que o princípio do terceiro excluído

(TE) A ∨ ¬A

deriva do princípio da não-contradição

(NC) ¬(A ∧ ¬A)

e reciprocamente (por De Morgan), segue-se que NC, TE e MP são princípios interderiváveis.

3. Satisfazibilidade

Há três tipos de fórmulas moleculares bem formadas no cálculo proposicional: fórmulas contingentes, verdades lógicas e contradições. No cálculo de predicados existe um paralelo óbvio com as verdades lógicas e as contradições: são as fórmulas universalmente válidas (FUV) e as fórmulas universalmente inválidas (FUI).

Uma fórmula proposicional molecular bem formada A é uma verdade lógica se e só se resulta verdadeira em todas as atribuições de valores de verdade às suas variáveis proposicionais; uma fórmula predicativa molecular bem formada A é uma FUV se e só se resulta verdadeira em todas as interpretações. Uma fórmula proposicional molecular bem formada A é uma contradição se e só se resulta falsa em todas as atribuições de valores de verdade às suas variáveis proposicionais; uma fórmula predicativa molecular bem formada A é uma FUI se e só se resulta falsa em todas as interpretações.

Este paralelo perde-se no que respeita às fórmulas contingentes. Com efeito, na lógica proposicional, A é uma fórmula contingente se e só se existem atribuições de valores de verdade às variáveis proposicionais de A que a tornam falsa e outras atribuições que a tornam verdadeira. Mas, na lógica predicativa, para que A seja uma fórmula satisfazível (FS) basta que existam interpretações que tornem A verdadeira; não é necessário que existam também interpretações que a tornem falsa (mas podem existir interpretações que a tornem falsa).

Formalmente, os axiomas que regulam o conceito de FS são os seguintes:

(A1) FUV(P) ≡ ¬FS(¬P)
(A2) FS(P) ≡ ¬FUV(¬P)

Pelos axiomas é fácil verificar que existem dois tipos diferentes de fórmulas que são FS: fórmulas como

(5) ∀x(Px → Qx)

e fórmulas como

(6) ∀x(Px → Px).

Ora, uma análise básica de (5) e (6) revela imediatamente que se trata de dois tipos diferentes de fórmulas: (5) é verdadeira em alguns domínios e falsa noutros, enquanto (6) é verdadeira em todos os domínios. O conceito de satisfazibilidade expresso nos axiomas (A1)-(A2) cobre estes dois casos.

Torna-se assim claro que (i) existem de facto contrapartes predicativas das fórmulas contingentes da lógica proposicional, e que (ii) o conceito corrente de FS não satisfaz o paralelismo com a lógica proposicional por considerar como FS dois tipos diferentes de fórmulas.

Proponho que se chame a (5) uma fórmula predicativa contingente (FPC). A sua definição

(7) FPC(P) ≡ FPC(¬P)

é perfeitamente paralela em relação ao cálculo proposicional e dá conta do facto mais relevante: a negação de qualquer fórmula como (5) é ainda uma FPC.

Um resultado interessante dos axiomas (A1)-(A2) é a sua incompletude: não podemos a partir de (A1)-(A2), com os meios tradicionais da lógica, derivar como teoremas pelo menos uma verdade básica acerca das relações entre as FUV e as FS.

Demonstração: Seja A uma FUV. É fácil verificar que A é uma FS. Logo, podemos assumir como uma verdade que FUV(P) → FS(P). Mas este resultado não é derivável sintacticamente a partir dos axiomas. Não ofereço a demonstração deste facto, que pode com economia ser realizada através do método das árvores semânticas, mas ofereço a derivação mais próxima a que é possível chegar, porque tem o interesse de mostrar uma contradição semântica que não é no entanto uma contradição sintáctica:

(A1), (A2) FUV(P) → FS(P) (reductio)

1.   ¬[FUV(P) → FS(P)] Hip. Red.
2.   FUV(P) ∧ ¬FS(P) 1, verdade lógica
3.   ¬FUV(¬P) → FS(P) (A2), verdade lógica
4.   FUV(¬P) 2, 3, MT
5.   FUV(P) ∧ FUV(¬P) 2, 4
6.   FUV(P) → FS(P) 1-5, Red.

O passo 5, única contradição a que é possível chegar para demonstrar o teorema desejado, não é de facto uma contradição no sentido sintáctico do termo. É apenas uma contradição semântica: afirma que a fórmula A e a sua negação são FUV, o que é diferente de uma contradição sintáctica, que teria de ser «FUV(P) ∧ ¬FUV(P)».

4. Intransitividade da derivabilidade

As lógicas livres caracterizam-se por admitir domínios de quantificação vazios ou nomes sem denotação. Esta frase é propositadamente ambígua, e pode ser erradamente interpretada como significando que admitir domínios de quantificação vazios e nomes sem denotação é a mesma coisa. Mas a verdade é que são dois conceitos distintos.

A distinção entre os dois é comodamente compreendida considerando que podemos ter uma lógica com domínios possivelmente vazios e em que todos os nomes próprios denotam objectos existentes num domínio.

Admitir domínios de quantificação vazios implica considerar que

(8) ∀x Px ⊢ ∃x Px

não é válida.

Sustentar que todos os nomes têm denotação implica considerar que

(9) Pa ⊢ ∃x Px

É válida.

Mas Hodges quer admitir como válida também

(10) ∀x Px ⊢ Pa,

o que parece permitir a existência de nomes sem denotação, única possibilidade de tornar (10) uma inferência válida, uma vez que a asserção universal pode estar a quantificar sobre um domínio vazio. Na verdade a ideia de Hodges é diferente: sempre que se utiliza no sistema dedutivo um nome próprio, existe um objecto denotado por esse nome.

Da aceitação de (10) segue-se ainda a consequência desagradável da derivabilidade ter de ser considerada intransitiva, caso contrário (8) é derivável a partir de (10) e (9).

No entanto, a condicional é transitiva em Hodges:

(11) (∀x Px → Pa), (Pa → ∃x Px) ⊢ (∀x Px → ∃x Px).

O resultado é um sistema de lógica cuja relação de derivabilidade é intransitiva, apesar de a condicional ser transitiva. Esta é aliás a única maneira de manter um sistema de lógica com domínios possivelmente vazios, mas cujos nomes denotam necessariamente.

Desidério Murcho

Siga gratuitamente a Crítica por email e nunca perca as novidades.