Completude e Solvência na Lógica Proposicional
RESUMO
Esta aula aborda a relação entre completude e solvência na lógica proposicional. Embora as técnicas de dedução e semântica na lógica proposicional tenham sido amplamente discutidas, pouca atenção foi dada à relação entre essas duas facetas. A solvência refere-se à propriedade de um sistema lógico onde, sempre que uma expressão G pode ser inferida a partir de um conjunto de expressões Γ, G é consequentemente uma consequência (semântica) de Γ. Por outro lado, a completude refere-se à propriedade de um sistema lógico onde, se G é uma consequência semântica de um conjunto de expressões Γ, então existe uma prova formal com premissas Γ a partir da qual G pode ser inferida. Mostra-se que a lógica proposicional é solvente e completa, e uma explicação detalhada de cada propriedade é apresentada. Em particular, mostra-se como a solvência decorre da constituição do sistema dedutivo da lógica proposicional, e como a completude é inferida de forma simples. Esta análise é de grande importância para entender como a lógica proposicional funciona e para aplicá-la efetivamente em vários campos do conhecimento.
OBJETIVOS DE APRENDIZADO:
Ao final desta aula, o aluno será capaz de:
- Distinguir entre solvência e completude em um sistema lógico.
- Aplicar a tabela verdade para os axiomas de Łukasiewicz para demonstrar a solvência da lógica proposicional.
- Explicar como o modus ponens pode ser reescrito usando a versão semântica do teorema da dedução.
- Entender que solvência e completude estão relacionadas e podem ser inferidas uma da outra.
- Analisar o conceito de tautologia e sua relação com os teoremas na lógica proposicional.
ÍNDICE
COMPLETUDE E SOLVÊNCIA NA LÓGICA PROPOSICIONAL
A LÓGICA PROPOSICIONAL É SOLVENTE
A LÓGICA PROPOSICIONAL É COMPLETA
Completude e Solvência na Lógica Proposicional
Neste ponto, é hora de falar sobre a completude e a solvência da lógica proposicional. Acontece que, até agora, muito foi dito sobre as técnicas de dedução e a semântica da lógica proposicional, mas tudo foi feito de uma forma que faz parecer que são duas facetas completamente independentes, sem qualquer relação entre si. A realidade é completamente oposta.
SOLVÊNCIA: Por um lado, diz-se que um sistema lógico é solvente quando, sempre que uma expressão G pode ser inferida a partir de um conjunto de expressões \Gamma, segue-se que G é uma consequência (semântica) de \Gamma |
COMPLETUDE: Por outro lado, diz-se que é completo quando, se G é uma consequência semântica de um conjunto de expressões \Gamma, então existe uma prova formal com premissas \Gamma a partir da qual G pode ser inferida. |
Revisando essas ideias, veremos que a completude e a solvência são satisfeitas para a lógica proposicional.
A Lógica Proposicional é Solvente
É fácil obter a solvência da lógica proposicional observando a constituição do seu sistema dedutivo. Se fizermos a tabela verdade para os axiomas de Łukasiewicz, veremos que eles têm uma estrutura tal que sempre resultam em verdadeiro como valor de verdade, ou seja:
| \models (\alpha \rightarrow (\beta \rightarrow \alpha)) |
| \models ((\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma))) |
| \models ((\neg\beta \rightarrow \neg\alpha)\rightarrow(\alpha \rightarrow \beta)) |
Da mesma forma, o modus ponens pode ser reescrito como \{\alpha,(\alpha\rightarrow \beta)\}\models \beta., o que pode ser obtido usando a versão semântica do teorema da dedução. De fato, por esse meio temos que \{(\alpha\rightarrow \beta)\}\models (\alpha\rightarrow \beta), e então \models ((\alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow \beta)),, que, claro, é uma tautologia mais do que óbvia.
A Lógica Proposicional é Completa
A completude da lógica proposicional nos diz que, se B é uma consequência semântica de A, então B é inferida a partir de A. Em outras palavras: todas as expressões verdadeiras têm uma demonstração. Isso é o que chamamos de completude. Isso pode ser inferido de maneira simples.
Isso pode ser inferido de maneira simples. Suponha que B não possa ser inferido de A, ou melhor, \neg(A\vdash B), pelo teorema da dedução isso é equivalente a dizer que: \neg (\vdash A\rightarrow B); agora, se recorrermos à solvência, isso nos leva a \neg(\models A \rightarrow B), que, pela contrapartida do teorema da dedução (versão semântica), é equivalente a \neg(A\models B). Em resumo, o que temos é que
\neg(A\vdash B) \Rightarrow \neg(A\models B)
Que é equivalente a dizer
(A\models B) \Rightarrow (A\vdash B)
Isso significa que, se A modela B, então B é inferido a partir de A. E se utilizarmos os respectivos teoremas da dedução, podemos obter
(\models A\rightarrow B) \Rightarrow (\vdash A \rightarrow B)
Ou seja: se uma expressão é uma tautologia, então é um teorema; e como vimos, os teoremas são o resultado de uma demonstração.