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 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:

  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 tautologias
  4. 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.
  5. Mas se duas fórmulas A e B são equivalentes, então A → B.
  6. Logo, qualquer axioma de T implica qualquer outro axioma de T.
  7. 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.

Desidério Murcho
Termos de utilização ⋅ Não reproduza sem citar a fonte