Consequência Semântica Proposicional

$$H\models p$$

Certas hipóteses, $H$, são verdadeiras, apenas com algumas valorações, $v$. Nesse caso, que outras proposições, $p$, também resultam verdadeiras?

Objetivo: Determinar se a proposição $p$ é verdadeira quando são verdadeiras as hipóteses $H$.

Mais concretamente, pretende-se relacionar os valores booleanos das hipóteses com os da conclusão.

Definição (Consequência Semântica, $\models$)

Sejam $H$ um conjunto de proposições e $p$ uma proposição.

Diz-se que $p$ é consequência semântica de $H$ e escreve-se $H\models p$ se qualquer modelo de $H$ também é modelo de $p$: $$\text{Se}v\models H\text{enta˜o}v\models p.$$

Observações:

• $H/\models p$ significa que existe um modelo de $H$ que é uma refutação de $p$.
• Para que $H\models p$ é necessário que, para cada valoração $v$, $$\text{Se}\forall h\in H,v\models h\text{enta˜o}v\models p.$$

Exemplos

• $\left\{p,q\right\}\models p$
  • Qualquer modelo de $\left\{p,q\right\}$ também é modelo de $p$:
    • Se $v\models \left\{p,q\right\}$ então $v\models p$.
• $\left\{p,q\right\}\models p\wedge q$
  • Qualquer modelo de $\left\{p,q\right\}$ também é modelo de $p$ e de $q$, de acordo com a tabela dos conectivos.
• $\left\{p\right\}\models p\vee q$
  • Um modelo de $p$, de acordo com a tabela dos conectivos, também é modelo de $p\vee q$.
• $\left\{p\wedge q\right\}\models p\vee q$
  • Um modelo de $p\wedge q$, de acordo com a tablea dos conectivos, tem de ser modelo de $p$ e modelo de $q$.
  • Portanto também é modelo de $p\vee q$.
• $\left\{p\vee q\right\}/\models p\wedge q$
  • Com a valoração $v\left(p\right)=\mathtt{v};v\left(q\right)=\mathtt{f}$ temos $v\models p\vee q$ mas $v/\models p\wedge q$.
• $\left\{p,\neg p\right\}\models q$ porque as hipóteses não têm qualquer modelo.
  • Este caso pode parecer um pouco confuso. A pergunta que a colocar é: "Existe algum modelo de $H$ que não seja de $q$?" — e a resposta é "Não"!
• $\neg p\models p\to q$:
  • Se $v\left(\neg p\right)=\mathtt{v}$ então $v\left(p\right)=\mathtt{f}$.
  • Mas então, de acordo com as regras das valorações, também $v\left(p\to q\right)=\mathtt{v}$ independentemente de $v\left(q\right)$.
• $\models p\vee \neg p$
  • Para qualquer valoração $v$, ou $v\left(p\right)=\mathtt{v}$ ou $v\left(\neg p\right)=\mathtt{v}$ (exercício: porquê?).
  • Portanto $v\left(p\vee \neg p\right)=\mathtt{v}$.

Equivalência Semântica

Definição (Proposições Equivalentes, $\equiv$)

Duas proposições $p,q$ são equivalentes se $p\models q$ e $q\models p$. Nesse caso escreve-se $p\equiv q$.

Exemplo. $a\to b\equiv \neg b\to \neg a$

Para provar que $a\to b\equiv \neg b\to \neg a$ por uma tabela:

$$\begin{array}{lcccccc}& C_1& C_2& C_3& C_4& C_5& C_6\\ & a& b& \neg a& \neg b& a\to b& \neg b\to \neg a\\ L_1& \mathtt{v}& \mathtt{v}& \mathtt{f}& \mathtt{f}& \mathtt{v}& \mathtt{v}\\ L_2& \mathtt{v}& \mathtt{f}& \mathtt{f}& \mathtt{v}& \mathtt{f}& \mathtt{f}\\ L_3& \mathtt{f}& \mathtt{v}& \mathtt{v}& \mathtt{f}& \mathtt{v}& \mathtt{v}\\ L_4& \mathtt{f}& \mathtt{f}& \mathtt{v}& \mathtt{v}& \mathtt{v}& \mathtt{v}\end{array}$$

Nesta tabela:

• Cada linha corresponde a uma das quatro valorações de $a,b$.
  • As colunas $C_1$ e $C_2$ (isto é, $a$ e $b$) mostram como essas valorações variam.
• As colunas $C_5$ e $C_6$ (isto é, $a\to b$ e $\neg b\to \neg a$) são iguais.
  • Isto prova que qualquer modelo (isto é, em qualquer linha) se uma coluna é verdadeira, também a outra coluna o é.
• Também se conclui que $\neg a\models a\to b$:
  • Porque $\neg a$ é verdadeira nas linhas 4 e 5 e, nessas linhas, também $a\to b$ é verdadeira.
• Porém $a\to b/\models \neg a$:
  • Na linha 1 $a\to b$ é verdadeira mas $\neg a$ é falsa.

Sobre a Equivalência Semântica

• O símbolo $\equiv$ não é um conectivo lógico, ao contrário de $\wedge ,\vee ,\to$.
• Isto é, se $p,q$ forem proposições $p\equiv q$ não é uma proposição enquanto que $p\wedge q,p\vee q,p\to q$ são.
  • Analogamente $2<3$ não é um número mas $2+3$, $2-3$, $2\times 3$ e $2÷3$ são.

Leis de De Morgan e outras equivalências

$$\begin{array}{rlrl}\neg \left(p\vee q\right)& \equiv \neg p\wedge \neg q& \neg \left(p\wedge q\right)& \equiv \neg p\vee \neg q\\ \left(p\vee q\right)\wedge r& \equiv \left(p\wedge r\right)\vee \left(q\wedge r\right)& \left(p\wedge q\right)\vee r& \equiv \left(p\vee r\right)\wedge \left(q\vee r\right)\\ p\to q& \equiv \neg p\vee q& p\to q& \equiv \neg q\to \neg p\\ p\vee p& \equiv p& p\wedge p& \equiv p\\ p\to p& \equiv \top & p\leftrightarrow p& \equiv \top \\ p\to \perp & \equiv \neg p& \neg \left(p\leftrightarrow q\right)& \equiv p\dot{\vee }q\\ p\vee \neg p& \equiv \top & p\wedge \neg p& \equiv \perp \end{array}$$

Consequência Semântica, Sintática e Implicação

$$\begin{array}{lll}H\models p& h\models p& \models h\to p\\ H⊢p& h⊢p& ⊢h\to p\end{array}$$

É possível re-escrever $H\models p$ de formas que podem ser mais úteis em certas circunstâncias. Exatamente as mesmas formas são também aplicáveis a $H⊢p$.

Teorema (Consequência Semântica, Sintática e Implicação)

Sejam $H=\left\{h_1,\dots ,h_N\right\}$ um conjunto de proposições, $h=h_1\wedge \cdots \wedge h_N$ e $p$ uma proposição.

Então:

• $H\models p$ se e só se $h\models p$ se e só se $\models h\to p$.
• $H⊢p$ se e só se $h⊢p$ se e só se $⊢h\to p$.

Este teorema mostra:

• Como na consequência semântica $H\models p$, as hipóteses $H$ podem ser "reduzidas" a uma única proposição $h$ e como "retirar" todas as hipóteses, escrevendo a implicação $h\to p$.
• Exatamente as mesmas transformações são aplicáveis à consequência sintática.

Completude e Validade

$$H\models pH⊢p$$

Qual a relação entre "dedução" e "verdade"? Entre $H⊢p$ e $H\models p$?

Teorema (Completude e Validade da Lógica Proposicional)

Seja $H$ um conjunto de proposições e $p$ uma proposição.

Então $H\models p$ se e só se $H⊢p$.

Este teorema afirma que a Lógica Proposicional é:

• Completa: Se $\models p$ então $⊢p$
  • Todas as proposições válidas são teoremas.
• Segura: Se $⊢p$ então $\models p$
  • Todos os teoremas são válidos.

Na Lógica Proposicional todas as verdades podem ser deduzidas e todos os teoremas são verdadeiros.

Gödel e Turing

Além da Lógica Proposicional, os "Teoremas da completude e validade" têm uma importância enorme na Matemática e na Computação.

Na Matemática

Kurt Gödel mostrou, em 1931, que qualquer teoria que inclua a aritmética não pode ser simultâneamente completa e segura.

Isto significa que em muitas disciplinas da Matemática, por exemplo na Álgebra Linear ou na Análise Matemática, das duas uma:

• Ou essa disciplina não é segura, isto é alguns teoremas são falsos.
• Ou é incompleta, isto é algumas proposições verdadeiras não têm demonstração.

Esta conclusão destruiu o Programa de Hilbert, que tinha por objetivo formalizar toda a matemática num conjunto completo de axiomas e provar que esse conjunto é seguro.

No entanto não se predeu muito do trabalho feito no sentido da formalização. Nem sempre é necessário incluir toda a aritmética e muitas vezes é, de facto, possível provar que certas teorias formais são seguras e completas, como a Lógica Proposicional.

Na Computação

Além da Matemática, também na Computação (isto é, "A Teoria da Informática") as questões sobre completude e validade são importantes. A mais importante é conhecida por "Halting Problem" ou "Problema da Paragem":

Existe um programa capaz de determinar se um dado programa termina?

Isto é, será possível escrever um programa que tem como entrada outro programa e, após um número finito de passos, determina se o programa dado termina ou não termina?

Esta questão foi posta, e respondida, por Alan Turing, um dos fundadores da Computação: Não. Nenhum programa pode resolver este problema.

A relação entre o Problema da Paragem e o Teorema de Gödel não é evidente mas é profunda: A abordagem de Turing ao Problema da Paragem segue a abordagem de Gödel à questão da completude e validade.