Perplexidades lógicas

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.

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:

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. Por sua vez, esta é apenas a negação da 11 (“⇒”), que é logicamente equivalente à mera afirmação da segunda variável proposicional, pelo que está longe de ser interessante.

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.