Perplexidades lógicas
Desidério MurchoEste 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 todos os conectivos lógicos binários, a distinção entre a relação lógica de dedução e a de implicação, 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 dedução 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.
Conectivos lógicos
O cálculo proposicional clássico conhece 4 conectivos binários e um unário:
∨, ∧, →, ↔, ¬.
Sabemos que podemos prescindir de quaisquer três dos primeiros quatro e ficar apenas com o 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 conectivos, 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 conectivos, 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 4 conectivos binários, os conectivos binários possíveis são no entanto 16, 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 ¬∨, ↓ |
9 ∨ |
10 ¬↔ |
11 ⇒ |
12 ¬← |
13 ⇐ |
14 ¬→ |
15 ∧ |
16 |
|
| V V | V | F | V | F | V | F | V | F | V | F | V | F | V | F | V | F |
| V F | V | V | F | F | V | V | F | F | V | V | F | F | V | V | F | F |
| F V | V | V | V | V | F | F | F | F | V | V | V | V | F | F | F | F |
| F F | V | V | V | V | V | V | V | V | F | F | F | F | F | F | F | F |
A análise da tabela acima revela imediatamente que os conectivos 9-16 são a negação dos conectivos 1-8, e reciprocamente. Para cada conectivo tradicional existe por isso um outro conectivo que é a sua negação. Os conectivos 2, 8, 10 e 14 são, respectivamente, a negação dos conectivos 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 (conectivo 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 (conectivo 8).
Excluídas as tradicionais e as suas negações, ficamos com oito conectivos. Destes oito, podemos concentrar a nossa atenção apenas nos quatro primeiros, pois os restantes são apenas a negação destes.
Destes quatro conectivos, o 5 é obtido por comutação das variáveis proposicionais a partir do 3 (→), podendo por isso ser representado por «←».
Restam assim três conectivos, dos quais o 1 é pouco interessante, uma vez que transforma em tautologia todas as proposições nas quais este conectivo seja o principal, independentemente do valor de verdade das variáveis proposicionais.
Os dois conectivos que restam são o 4 e o 6. Mas imediatamente se percebe que o 4 se obtém na verdade por comutação a partir do 6, de forma que podemos concentrar a nossa atenção no 6. No entanto, é a negação do 6 que é realmente interessante, de forma que vamos tomar 11 («⇒») como o conectivo primitivo e 6 como a sua negação. O conectivo «⇒» 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 o nosso novo conectivo «⇒» podemos simplificar algumas proposições da lógica clássica. A tautologia expressa na proposição
(1) [(Q → ¬P) → ¬(P → Q)] → P
pode agora exprimir-se na proposição
(2) (Q ⇒ P) → P.
(2) pode acrescentar-se como axioma a um sistema axiomático do tipo do de Hilbert, pois representa o comportamento do próprio conectivo «⇒». Será interessante verificar se as demonstrações num sistema que contenha este novo conectivo resultam mais económicas, como é legítimo esperar.
Dedução e implicação
A relação lógica entre a dedução e a implicação é 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:
- Seja T uma teoria axiomática independente para o cálculo proposicional
- Nenhum axioma de T é derivável a partir de outro qualquer axioma
- Mas todos os axiomas são tautologias
- Se duas fórmulas A e B são tautologias, então têm o mesmo valor de verdade. Logo, A e B são equivalentes.
- Mas se duas fórmulas A e B são equivalentes, então A → B.
- Logo, qualquer axioma de T implica qualquer outro axioma de T.
- Existem assim fórmulas A e B tal que A → B e A ⊬ B.
Modus ponens e terceiro excluído
Uma aplicação do resultado anterior é o seguinte: é óbvio que quaisquer duas tautologias se implicam mutuamente, e assim não é de estranhar que o princípio do terceiro excluído
(TE) A ∨ ¬A
implique a formulação proposicional da regra de inferência modus ponens
(MP) [A ∧ (A → B)] → B ,
e reciprocamente. Mas é agora pertinente perguntar se TE 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.
Satisfazibilidade
Todos os estudantes de lógica elementar sabem que existem três tipos de fórmulas moleculares bem formadas no cálculo proposicional: fórmulas contingentes, tautologias e contradições. No cálculo de predicados existe um paralelo óbvio com as tautologias 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 tautologia 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, Tautologia |
| 3. ¬FUV(¬P) → FS(P) | (A2), Tautologia |
| 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)».
Intransitividade da dedução
Qualquer estudante sabe que as lógicas livres se caracterizam 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 dedução ter de ser considerada intransitiva, caso contrário (8) é derivável a partir de (10) e (9).
No entanto, a implicação é 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 implicação ser transitiva. Esta é aliás a única hipótese de manter um sistema de lógica com domínios possivelmente vazios, mas cujos nomes denotam necessariamente.