Consequência e Equivalência Semântica

RESUMO
Nesta aula, estudaremos a Consequência e Equivalência Semântica na lógica proposicional, o que é uma continuação natural do que já vimos anteriormente. Aprenderemos como obter a noção de consequência semântica a partir das atribuições de valores de verdade e como essa ideia se relaciona com o teorema da dedução. Além disso, veremos exemplos práticos do uso das tabelas de verdade para obter propriedades úteis como a Eliminação da Conjunção e a Introdução da Disjunção. Também exploraremos a noção de Equivalência Semântica e veremos como ela se relaciona com as propriedades que já conhecemos. Finalmente, mostraremos como o uso de modelos e técnicas de dedução nos permite simplificar o estudo de problemas de consequência e equivalência semântica.

OBJETIVOS DE APRENDIZAGEM:
Ao final desta aula, o aluno será capaz de

Compreender a noção de consequência semântica.
Compreender as diferentes interpretações do símbolo ⊨.
Compreender a demonstração do teorema da dedução em sua versão semântica e seu uso no estudo da consequência e equivalência semântica.
Compreender a definição de equivalência semântica e sua relação com os valores de verdade.
Aplicar o teorema da dedução em sua versão semântica para transformar problemas de consequência em problemas de validade.
Aplicar as propriedades úteis no uso das tabelas de verdade para demonstrar equivalências semânticas.
Aplicar as leis de absorção, distribuição e DeMorgan na simplificação de expressões complexas.
Analisar a relação entre modelos e deduções no estudo da lógica proposicional.

ÍNDICE
ATRIBUIÇÕES E MODELOS
O TEOREMA DA DEDUÇÃO (VERSÃO SEMÂNTICA)
USO DO TEOREMA DA DEDUÇÃO NO ESTUDO DA CONSEQUÊNCIA E EQUIVALÊNCIA SEMÂNTICA
EQUIVALÊNCIA SEMÂNTICA E PROPRIEDADES
SÍNTESE

O estudo da Consequência e Equivalência Semântica é uma continuação natural do que fizemos ao revisar a semântica da lógica proposicional. Agora revisaremos como, a partir das atribuições de valores de verdade, se obtém a noção de consequência semântica e como, a partir disso, surge naturalmente uma versão semântica do teorema da dedução. Serão apresentados exemplos práticos do uso das tabelas de verdade para obter algumas propriedades úteis. Você também pode ver tudo isso no canal do YouTube.

Atribuições e Modelos

Primeiro, vamos começar com uma definição que é crucial para os desenvolvimentos que veremos neste post, a de consequência semântica.

DEFINIÇÃO: Uma expressão

G

é uma (semântica) consequência de outra expressão

F

se, para cada atribuição

\mathcal{A}

, vale que

$\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$

Isso é representado escrevendo $F\models G$ e se lê como “a expressão $F$ modela a expressão $G$ ” ou “ $G$ é uma (semântica) consequência de $F$ .”

Com essa definição em mãos, devemos notar que o símbolo $\models$ realmente tem várias leituras diferentes dependendo do contexto:

$\mathcal{A} \models F$ significa que $\mathcal{A}(F) = 1$ ; ou seja, que “ $\mathcal{A}$ modela $F$ .”
$G \models F$ significa que, se qualquer atribuição modela $G$ , então modela $F$ , e lemos isso como “ $F$ é consequência de $G$ .”
$\models F$ significa que $F$ vale sob qualquer atribuição; ou seja, que $F$ é uma tautologia.

Assim, embora o símbolo $\models$ possa ter muitas interpretações, o contexto não é ambíguo.

A noção de consequência (semântica) é próxima à noção de “implicação” que revisamos anteriormente, no sentido de que, se $F\models G$ é verdadeiro, então $\models (F\rightarrow G)$ . Na verdade, isso é muito semelhante ao teorema da dedução que vimos várias aulas atrás.

O Teorema da Dedução (Versão Semântica)

[ver]

TEOREMA: Se

F

G

são quaisquer expressões, então vale que

$F\models G \Leftrightarrow \models (F\rightarrow G)$

Prova:

A prova deste teorema é facilmente obtida observando as tabelas de verdade

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

Se nos concentrarmos no significado de $F\models G$ , veremos que isso é equivalente a dizer que $\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$ , que por sua vez é o mesmo que dizer que $\mathcal{A}\not\models F \vee \mathcal{A}\models G$ . Agora, se notarmos que também $\mathcal{A}\not\models F$ é exatamente o mesmo que $\mathcal{A}\models \neg F$ , então $F\models G$ é equivalente a dizer que $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ . Agora, se fizermos uma tabela de verdade para $F \rightarrow G$ e marcarmos em verde a região onde se cumpre que $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ , então veremos o seguinte:

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

Daqui temos que, quando $F\models G$ , sempre ocorre que $\models (F \rightarrow G)$ e vice-versa, o que nada mais é do que o teorema da dedução e seu recíproco na versão semântica.

Suponhamos que queiramos saber se uma expressão $G$ é consequência de outra expressão $F$ . Vamos nos referir a isso como o problema da consequência. Usando o teorema anterior, esse problema pode ser transformado em um problema de validade, porque “ $G$ é consequência de $F$ se e somente se $(F\rightarrow G)$ é um teorema”.

Uso do Teorema da Dedução no Estudo da Consequência e Equivalência Semântica

A partir das tabelas de verdade, algumas propriedades podem ser inferidas que lembram algumas vistas no passado.

EXEMPLO: Mostrar usando tabelas de verdade que as seguintes propriedades são verdadeiras

Eliminação da Conjunção:

(F\wedge G)\models F

Introdução da Disjunção:

F\models (F\vee G)

Contradição:

(F\wedge\neg F)\models G

Solução: Usando o teorema da dedução que acabamos de revisar, podemos transformar o problema da consequência em um problema de validade.

Para resolver a Eliminação da Conjunção, podemos fazer a seguinte tabela de verdade

$F$	$G$	$(F\wedge G)$	$((F\wedge G) \rightarrow F)$
$0$	$0$	$0$	$1$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$

Com isso, demonstramos que $((F\wedge G)\rightarrow F)$ é uma tautologia e, portanto, seguindo o recíproco do teorema da dedução, obtemos que $(F\wedge G) \models F$ .

Introdução da Disjunção é resolvido de forma semelhante, construindo uma tabela de verdade adequada

$F$	$G$	$(F\vee G)$	$(F\rightarrow(F\vee G))$
$0$	$0$	$0$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$
$1$	$1$	$1$	$1$

Aqui observamos que $(F\rightarrow (F\vee G))$ é uma tautologia e, portanto, pelo recíproco do teorema da dedução, temos que $F\models (F\vee G)$

E finalmente, a propriedade da Contradição é demonstrada usando o mesmo método

$F$	$\neg F$	$(F\wedge \neg F)$	$G$	$((F\wedge \neg F)\rightarrow G)$
$0$	$1$	$0$	$0$	$1$
$0$	$1$	$0$	$1$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$0$	$0$	$1$	$1$

Com esta tabela de verdade, demonstramos que $((F\wedge \neg F)\rightarrow G)$ é uma tautologia e, portanto, pelo recíproco do teorema da dedução, temos que $(F\wedge \neg F)\models G$ .

Equivalência Semântica e Propriedades

[ver]

DEFINIÇÃO: Se ocorrerem ao mesmo tempo,

F\models G

G\models F

, então diz-se que

F

G

são semanticamente equivalentes entre si. Isso é representado escrevendo

F\equiv G

Como consequência desta definição, duas expressões são semanticamente equivalentes se e somente se tiverem os mesmos valores de verdade.

EXEMPLO: Pode-se mostrar, usando tabelas de verdade, que valem as equivalências semânticas de simetria.

(F\downarrow G) \equiv (G\downarrow F)

(F\vee G) \equiv (G\vee F)

(F\wedge G) \equiv (G\wedge F)

(F\leftrightarrow G) \equiv (G\leftrightarrow F)

(F\underline{\vee} G) \equiv (G\underline{\vee} F)

EXEMPLO: Se

F

é qualquer expressão,

\top

uma tautologia, e

\bot

uma contradição, então, por meio de tabelas de verdade, pode-se provar as seguintes equivalências semânticas

(F\wedge \top) \equiv F

(F\vee \top) \equiv \top

(F\wedge \bot) \equiv \bot

(F\vee \bot) \equiv F

Essas equivalências são conhecidas como leis de absorção.

EXEMPLO: Na semântica da lógica proposicional, as equivalências de distribuição da conjunção e da disjunção também valem.

(F\wedge (G\vee H)) \equiv ((F\wedge G) \vee (F\wedge H))

(F\vee (G\wedge H)) \equiv ((F\vee G) \wedge (F\vee H))

EXEMPLO: Na semântica da lógica proposicional, as Leis de DeMorgan também valem.

\neg(F\wedge G) \equiv (\neg F \vee \neg G)

\neg(F\vee G) \equiv (\neg F \wedge \neg G)

EXERCÍCIO: Um bom exercício é provar, usando tabelas de verdade, que as equivalências semânticas das Leis de Absorção, Distributividade e Leis de DeMorgan realmente se sustentam.

EXEMPLO: Demonstrar, usando equivalências semânticas, que ocorre a seguinte equivalência:

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E))\equiv ((A\wedge B)\vee(C\wedge D))$ .

Solução: Podemos provar essa equivalência usando tabelas de verdade, mas, se fizermos isso, teremos que lidar com uma expressão com 5 variáveis proposicionais, e isso implica fazer uma tabela de verdade com

2^5 = 32

linhas, o que seria ideal evitar. Para conseguir isso, usaremos as equivalências que já mostramos.

Primeiro, observe que $(E\vee \neg E)$ é uma tautologia. Vamos denotar essa tautologia por $\top$ . Em seguida, usando as leis de absorção, temos

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B))$

Usando as leis de distribuição, obtemos

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) \equiv ((C\wedge D) \vee (A\wedge B))$

Finalmente, por simetria

$((C\wedge D) \vee (A\wedge B)) \equiv ((A\wedge B) \vee (C\wedge D))$

Portanto, seguindo essas equivalências, temos a equivalência

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((A\wedge B) \vee (C\wedge D))$

que é o que queríamos provar.

Síntese

Se observarmos o desenvolvimento deste último exemplo, veremos que, à medida que o número de variáveis aumenta, a complexidade do estudo dos problemas de consequência e equivalência semântica cresce exponencialmente se dependermos das tabelas de verdade. No entanto, vimos que, a partir do desenvolvimento da ideia de modelo, emerge algo análogo às técnicas de dedução que já estudamos com bastante detalhe. Essa relação entre modelos e deduções é o que veremos em breve, e a combinação de ambos nos poupará, finalmente, incontáveis dores de cabeça no estudo da lógica.