Semântica da Lógica Proposicional
RESUMO
Nesta aula, estudamos a semântica da lógica proposicional, especificamente a atribuição de valores de verdade a uma expressão e como esses valores se propagam de uma expressão para outra através dos conectores lógicos. Introduz-se a noção de tabelas de verdade e são apresentadas as tabelas de verdade dos conectores derivados, tais como negação, disjunção, conjunção, implicação, dupla implicação e disjunção exclusiva. Além disso, apresenta-se a definição de uma atribuição sobre um conjunto de expressões atômicas e explica-se como ela se estende naturalmente a todas as expressões que podem ser construídas a partir desse conjunto. Finalmente, estabelecem-se as definições de expressões válidas, satisfatíveis e insatisfatíveis, e apresentam-se exemplos de tautologias e contradições. No entanto, reconhece-se que o cálculo das tabelas de verdade para expressões complexas pode ser ineficiente, por isso menciona-se a busca por métodos alternativos para resolver problemas de validade ou satisfatibilidade.
OBJETIVOS DE APRENDIZAGEM:
Ao final desta aula, o estudante será capaz de
- Explicar a semântica da lógica proposicional
- Usar tabelas de verdade para representar as atribuições de valores de verdade das expressões na lógica proposicional
- Modelar uma expressão com uma atribuição na lógica proposicional
- Aplicar as regras semânticas da lógica proposicional para determinar se uma expressão é tautologia, contradição ou contingência
ÍNDICE
SOBRE AS ATRIBUIÇÕES DOS VALORES DE VERDADE
SEMÂNTICA DOS CONECTORES DA LÓGICA PROPOSICIONAL
ATRIBUIÇÕES NA LÓGICA PROPOSICIONAL
MODELOS NA LÓGICA PROPOSICIONAL
UM PROBLEMA DE EFICIÊNCIA NA SEMÂNTICA DA LÓGICA PROPOSICIONAL
Sobre as Atribuições dos Valores de Verdade
Anteriormente revisamos a sintaxe e os sistemas dedutivos da lógica proposicional. Embora isso nos tenha servido para revisar a forma como podemos obter uma expressão a partir de outra, até agora não falamos nada sobre a atribuição dos valores de verdade. Como já dissemos tudo o que há para dizer sobre as técnicas de dedução na lógica proposicional, começaremos nosso estudo sobre a semântica da lógica proposicional, onde revisaremos a forma como as atribuições dos valores de verdade se propagam de uma expressão para outra.
Semântica dos Conectores da Lógica Proposicional
A semântica dos conectores é introduzida através das tabelas de verdade, pois elas fornecem uma forma simples e ordenada de representar todas as atribuições possíveis sobre uma expressão.
Tabela de Verdade da Negação Conjunta
Em primeiro lugar, começaremos com o conector mais fundamental de todos, que é a negação conjunta. Sua tabela de verdade é a seguinte:
| \alpha | \beta | (\alpha\downarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Os valores “1” e “0” correspondem a “Verdadeiro” e “Falso”, respectivamente. Cada linha na tabela de verdade é uma possível atribuição sobre as variáveis (ou expressões atômicas) que compõem a expressão (ou expressões) a serem estudadas. Da mesma forma, cada coluna onde se encontra uma expressão formada por essas variáveis tem os possíveis resultados dessas atribuições. Desta forma, a interpretação desta tabela nos diz que \alpha\downarrow\beta é verdadeiro apenas quando \alpha e \beta são ambos falsos ao mesmo tempo, e falso em outro caso. Por essa razão, o conector \downarrow recebe o nome de negação conjunta.
Tabelas de Verdade dos Conectores Derivados
A partir da semântica da negação conjunta, é possível obter a dos demais conectores através de suas definições. Estas são:
| Negação: | \neg \alpha | := | (\alpha\downarrow\alpha) |
| Disjunção Inclusiva: | (\alpha \vee \beta) | := | \neg(\alpha\downarrow\beta) |
| Conjunção: | (\alpha \wedge \beta) | := | \neg(\neg\alpha\vee \neg\beta) |
| Implicação: | (\alpha \rightarrow \beta) | := | (\neg\alpha\vee \beta) |
| Dupla Implicação: | (\alpha \leftrightarrow \beta) | := | ((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha)) |
| Disjunção Exclusiva: | (\alpha \underline{\vee} \beta) | := | \neg(\alpha\leftrightarrow \beta) |
A partir dessas definições, é possível calcular as tabelas de verdade dos demais conectores:
Negação
| \alpha | \neg \alpha |
| 0 | 1 |
| 1 | 0 |
Daqui vem o fato de que o conector de negação tem a propriedade de inverter o valor de verdade da expressão sobre a qual é aplicado.
Disjunção Inclusiva
| \alpha | \beta | (\alpha\vee\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
É por isso que a disjunção inclusiva (ou simplesmente “disjunção”) entre duas expressões é verdadeira se pelo menos uma das expressões for verdadeira, e é falsa quando ambas as expressões forem falsas ao mesmo tempo.
Conjunção
| \alpha | \beta | (\alpha\wedge\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Como resultado, a conjunção entre duas expressões é verdadeira apenas se ambas as expressões forem verdadeiras ao mesmo tempo, e falsa em outro caso. Por isso, um nome adequado para este conector também pode ser “afirmação conjunta”.
Implicação
| \alpha | \beta | (\alpha\rightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Assim, a tabela de verdade da implicação resume a noção de que uma expressão verdadeira só pode implicar uma expressão verdadeira, mas uma falsa pode implicar qualquer coisa.
Dupla Implicação
| \alpha | \beta | (\alpha\leftrightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
A dupla implicação forma uma expressão verdadeira sempre que as duas expressões que a formam têm os mesmos valores de verdade, e é falsa em outro caso.
Disjunção Exclusiva
| \alpha | \beta | (\alpha\underline{\vee}\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
A disjunção exclusiva entre duas expressões é verdadeira quando uma, e apenas uma das expressões é verdadeira, e falsa em outro caso.
Atribuições na lógica proposicional
Com o que foi descrito anteriormente temos uma noção simples do que é uma atribuição; no entanto, para os desenvolvimentos que veremos mais adiante, precisaremos de algo mais preciso. Se S=\{A_1, A_2, \cdots, A_n\} é um conjunto de expressões atômicas e \mathcal{F}(S) o conjunto de todas as expressões que podem ser construídas a partir das expressões de S, então temos a seguinte definição:
DEFINIÇÃO: Uma atribuição sobre S é uma função \mathcal{A}: S \longrightarrow \{0,1\}
Em outras palavras, uma atribuição sobre S fornece um valor de verdade a cada expressão atômica de S. Uma atribuição \mathcal{A} de S se estende naturalmente a todos os elementos de \mathcal{F}(S). Se temos uma expressão F\in \mathcal{F}(S), então uma atribuição \mathcal{A} sobre S corresponde a uma única linha na tabela de verdade de F e diz-se que \mathcal{A}(F) é o valor de verdade de F nessa linha.
Uma atribuição \mathcal{A} de S também pode se estender a certas expressões que não estão em \mathcal{F}(S). Se F_0 é uma expressão que não está em \mathcal{F}(S) e S_0 é o conjunto de subfórmulas atômicas de F_0, então se todas as extensões de \mathcal{A} para S\cup S_0 tiverem o mesmo valor para F_0, então define-se \mathcal{A}(F_0) como esse valor.
EXEMPLO: Se A e B são expressões atômicas e \mathcal{A} é uma atribuição sobre \{A,B\} definida por \mathcal{A}(A)=1 e \mathcal{A}(B)=0, então teremos:
\mathcal{A}(A\wedge B)=0 e \mathcal{A}(A\vee B)=1
E apesar de não haver uma atribuição estabelecida sobre uma variável C, pode-se dizer que:
\mathcal{A}(A\wedge (C\vee \neg C))=1 e \mathcal{A}(B\vee (C\wedge \neg C))=0
Isso acontece com as duas últimas expressões porque, independentemente da atribuição de C, sempre ocorrerá que
\mathcal{A}(C\vee\neg C)=1 e \mathcal{A}(C\wedge\neg C)=0
Coisa que podemos revisar rapidamente calculando suas tabelas de verdade.
| C | \neg C | (C\wedge \neg C) | (C \vee \neg C) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
■ Fim do Exemplo
Modelos na Lógica Proposicional
Consideremos uma atribuição \mathcal{A} sobre um conjunto de expressões S. Se F\in S for tal que \mathcal{A}(F)=1, então diz-se que a atribuição \mathcal{A} modela F, ou que a expressão F é sustentada pela atribuição \mathcal{A} e representamos isso através da escrita
\mathcal{A}\models F.
E, a partir disso, estabelecem-se as seguintes definições:
DEFINIÇÃO: Diz-se que uma expressão é válida quando é sustentada por qualquer atribuição. Se F for válida, então escreve-se \models F . As expressões válidas também são chamadas de tautologia.
EXEMPLO: A expressão (C\vee \neg C), que já vimos, é uma tautologia.
■ Fim do Exemplo
DEFINIÇÃO: Diz-se que uma expressão é satisfatível se for sustentada por alguma atribuição. As expressões satisfatíveis que não são tautologias são chamadas de contingências.
DEFINIÇÃO: Diz-se que uma expressão é insatisfatível se não for sustentada por nenhuma atribuição. As expressões insatisfatíveis são chamadas de contradições. Se F for uma contradição, então escreve-se \not\models F .
EXEMPLO: A expressão (C\wedge \neg C), que já vimos, é uma contradição..
■ Fim do Exemplo
Exemplos de Tautologias e Contradições
Suponhamos que queremos ver se uma expressão é válida ou não. Isso que acabamos de expor é um problema de decisão dentro da Semântica da Lógica Proposicional. Um problema de decisão é qualquer problema que, dada uma determinada entrada, resulta em um “sim” ou “não”. Se nos derem uma expressão F e perguntarmos se é ou não válida, então estamos diante de um problema de decisão que chamamos de problema de validade. Da mesma forma, se perguntarmos se é ou não satisfatível, estamos diante de um problema de satisfatibilidade. Na lógica proposicional, as tabelas de verdade oferecem uma abordagem sistemática para resolver esses problemas de decisão: se todos os valores de verdade possíveis de F forem “1”, então F é válida; se apenas alguns forem “1”, então é satisfatível; e finalmente, se todos forem “0”, então é insatisfatível.
EXEMPLO: Consideremos a expressão ((A\wedge (A \rightarrow B)) \rightarrow B). Para determinar se essa expressão é válida, satisfatível ou contraditória, fazemos sua tabela de verdade.
| A | B | (A\rightarrow B) | (A\wedge(A\rightarrow B)) | ((A\wedge(A\rightarrow B))\rightarrow B) |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Com isso, vemos que ((A\wedge(A\rightarrow B))\rightarrow B) tem valor de verdade “1” para todas as atribuições possíveis, de modo que a expressão resulta ser uma tautologia.
■ Fim do Exemplo
EXEMPLO: Consideremos agora a expressão (((A\rightarrow B)\rightarrow A)\wedge \neg A). O cálculo da tabela de verdade nos dá o que é mostrado abaixo:
| A | B | (A\rightarrow B) | ((A\rightarrow B)\rightarrow A) | \neg A | (((A\rightarrow B)\rightarrow A)\wedge \neg A) |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Desta forma, o resultado é uma contradição.
■ Fim do Exemplo
Um Problema de Eficiência na Semântica da Lógica Proposicional
Em teoria, podemos determinar se uma expressão é válida, contingente ou insatisfatível simplesmente calculando sua tabela de verdade, o que não é especialmente difícil; infelizmente, a facilidade de execução tem um custo em termos de eficiência. Se temos uma expressão F composta por n expressões atômicas, então teremos que calcular uma tabela de verdade com 2^n linhas; assim, se, por exemplo, F for composta por 23 expressões atômicas, sua tabela de verdade terá 8.388.608 linhas que precisam ser calculadas. Procedendo desta maneira, embora mecânica e fácil de realizar, a execução rapidamente se torna impraticável à medida que a complexidade das expressões aumenta. Devido a isso, um de nossos objetivos futuros será encontrar uma maneira de resolver problemas de validade ou satisfatibilidade sem a necessidade de calcular tabelas de verdade. A busca por tais métodos é um dos problemas centrais de qualquer lógica.