Considere as duas sentenças seguintes, expressas na linguagem da lógica proposicional, (\mathrm{P} \rightarrow \mathrm{Q}) \wedge(\mathrm{Q} \rightarrow \mathrm{R}) e \mathrm{P} \rightarrow \mathrm{R} verificando, analiticamente (isto é, sem o uso de tabela da verdade) se elas são logicamente equivalentes. Faça também uma verificação para os seguintes pares de sentenças: (P \wedge Q) \rightarrow P e R \vee \neg R; A \wedge(B \vee \neg C) e A \wedge(\neg B \wedge C).

Passo 1

Vou deixar bem claro o que o enunciado pede e quais sentenças temos para comparar.
  • O enunciado pede: verificar, analiticamente (sem tabela verdade), se os pares de sentenças abaixo são logicamente equivalentes (ou seja, têm exatamente as mesmas valorizações verdadeiras em todas as interpretações).
Os pares a verificar são:
  1. (\mathrm{P} \rightarrow \mathrm{Q}) \wedge(\mathrm{Q} \rightarrow \mathrm{R}) e \mathrm{P} \rightarrow \mathrm{R}.
  2. (P \wedge Q) \rightarrow P e R \vee \neg R.
  3. A \wedge(B \vee \neg C) e A \wedge(\neg B \wedge C).
Observações sobre o que temos: cada par contém duas fórmulas proposicionais e a tarefa é dizer se, para qualquer atribuição de verdade às letras proposicionais, as duas fórmulas têm sempre o mesmo valor lógico. Não vamos usar tabelas; vamos usar equivalências lógicas, regras de inferência e, quando necessário, contraexemplos (atribuições específicas de verdade) para mostrar falta de equivalência.

Passo 2

Ferramentas básicas que vou usar (explicadas de forma simples):
  • Equivalência da implicação: \;P\rightarrow Q\; é equivalente a \;\neg P \vee Q\;. Isso vem da definição de implicação: a única situação que torna P\rightarrow Q falsa é P verdadeiro e Q falso; a disjunção \neg P \vee Q tem exatamente a mesma tabela.
  • Modus ponens (regra de inferência): de P e P\rightarrow Q segue Q.
  • Prova condicional (conditional proof): para demonstrar que P\rightarrow R é consequência de algumas hipóteses, assume-se P e tenta-se derivar R; se conseguir, conclui-se P\rightarrow R.
  • Leis algébricas úteis: De Morgan, associatividade, comutatividade, e a tautologia \;P\vee\neg P\; (princípio do terceiro excluído).
Vou aplicar essas ferramentas passo a passo nos pares.

Passo 3

Análise do par 1: (P\rightarrow Q)\wedge(Q\rightarrow R) versus P\rightarrow R.
a) Mostrar que (P\rightarrow Q)\wedge(Q\rightarrow R) implica logicamente P\rightarrow R (ou seja, toda interpretação que torna a primeira verdadeira torna a segunda verdadeira).
  • Começo por uma prova por condicional: suponha (P\rightarrow Q)\wedge(Q\rightarrow R) verdadeira. Então tenho as duas hipóteses separadas:
    • \;P\rightarrow Q\;
    • \;Q\rightarrow R\;.
  • Para provar \;P\rightarrow R\; faço uma suposição provisória: suponha P verdadeira.
  • Pela hipótese \;P\rightarrow Q\; e pelo fato P verdadeiro, por modus ponens obtenho Q verdadeiro.
  • Pela hipótese \;Q\rightarrow R\; e pelo fato Q verdadeiro, por modus ponens obtenho R verdadeiro.
  • Assim, partindo de P obtive R; por prova condicional, isso permite concluir \;P\rightarrow R\;.
  • Portanto, toda interpretação que torna (P\rightarrow Q)\wedge(Q\rightarrow R) verdadeira também torna P\rightarrow R verdadeira. Em notação de consequência: (P\rightarrow Q),(Q\rightarrow R)\models P\rightarrow R.
b) Mostrar que a recíproca não vale (isto é, que P\rightarrow R não implica necessariamente (P\rightarrow Q)\wedge(Q\rightarrow R)). Para isso basta um contraexemplo (uma atribuição de valores) que faça P\rightarrow R verdadeira e (P\rightarrow Q)\wedge(Q\rightarrow R) falsa.
  • Considere a atribuição: P é verdadeira, Q é falsa, R é verdadeira.
  • Avaliando:
    • \;P\rightarrow R\; é verdadeiro porque R é verdadeiro (se R é verdadeiro, \neg P\vee R é verdadeira).
    • \;P\rightarrow Q\; é falso porque P é verdadeiro e Q é falso.
    • \;Q\rightarrow R\; é verdadeiro porque R é verdadeiro (mesma razão).
    • Logo (P\rightarrow Q)\wedge(Q\rightarrow R) é falso (conjunção com um membro falso).
  • Assim temos uma interpretação que satisfaz P\rightarrow R mas não satisfaz (P\rightarrow Q)\wedge(Q\rightarrow R). Portanto não há equivalência lógica entre as duas fórmulas: a implicação no sentido inverso falha.
Conclusão do par 1: não são logicamente equivalentes. (Expliquei por que uma implica a outra, mas a recíproca falha com contraexemplo.)

Passo 4

Agora o par 2: (P\wedge Q)\rightarrow P e R\vee\neg R.
Primeiro vou transformar (P\wedge Q)\rightarrow P usando equivalência da implicação:
(P\wedge Q)\rightarrow P \equiv \neg(P\wedge Q) \vee P.
Aplicando De Morgan em \neg(P\wedge Q):
\neg(P\wedge Q) \equiv \neg P \vee \neg Q,
portanto
\neg(P\wedge Q) \vee P \equiv (\neg P \vee \neg Q) \vee P.
Por associatividade e comutatividade da disjunção reagrupamos:
(\neg P \vee P) \vee \neg Q.
Mas \neg P \vee P é uma tautologia (lei do terceiro excluído): sempre verdadeiro. Uma disjunção que tem um membro sempre verdadeiro é sempre verdadeira; logo (\neg P \vee P) \vee \neg Q é sempre verdadeira independentemente do valor de \neg Q. Portanto (P\wedge Q)\rightarrow P é uma tautologia (é verdadeira para toda atribuição de valor das variáveis).
A outra fórmula R\vee\neg R é exatamente a forma canônica da lei do terceiro excluído; por definição é uma tautologia.
Como ambas as fórmulas são tautologias (sempre verdade), elas têm exatamente as mesmas valorizações (sempre verdade) em todas as interpretações. Logo são logicamente equivalentes.
Explicação intuitiva curta: (P\wedge Q)\rightarrow P é trivialmente verdadeira porque sempre que P\wedge Q ocorre, P já ocorre; nos demais casos a implicação é verdadeira por definição. Assim é tautologia, assim como R\vee\neg R.

Passo 5

Agora o par 3: A\wedge(B\vee\neg C) e A\wedge(\neg B\wedge C).
Faço primeiro uma transformação para ver as formas canônicas:
  • A primeira fórmula distribui com A:
A\wedge(B\vee\neg C) \equiv (A\wedge B)\vee(A\wedge\neg C).
  • A segunda fórmula pode ser escrita como
A\wedge(\neg B\wedge C) \equiv A\wedge\neg B\wedge C.
Agora compare as formas: a primeira é a disjunção (A\wedge B)\vee(A\wedge\neg C), a segunda é apenas um caso conjunção A\wedge\neg B\wedge C. Para serem logicamente equivalentes, cada interpretação que torna a primeira verdadeira teria de tornar a segunda verdadeira e vice-versa.
Mostro que não são equivalentes exibindo um contraexemplo (atribuição de verdade) que torna a primeira verdadeira e a segunda falsa.
Considere a atribuição: A verdadeira, B verdadeira, C verdadeira.
  • Avaliando a primeira fórmula:
    • B\vee\neg C é \text{verdadeiro} \vee \text{falso} = \text{verdadeiro}.
    • Então A\wedge(B\vee\neg C) é \text{verdadeiro}\wedge\text{verdadeiro} = \text{verdadeiro}.
  • Avaliando a segunda fórmula:
    • \neg B é falso (pois B é verdadeiro).
    • Logo A\wedge(\neg B\wedge C) é \text{verdadeiro}\wedge(\text{falso}\wedge\text{verdadeiro}) = \text{verdadeiro}\wedge\text{falso} = \text{falso}.
  • Assim há uma interpretação que satisfaz a primeira fórmula e não satisfaz a segunda; portanto não são logicamente equivalentes.
Observação adicional (intuitiva): a primeira permite o caso A e B verdadeiros (independente de C ser verdadeiro), enquanto a segunda exige especificamente que B seja falso e C verdadeiro; são condições incompatíveis em geral.

Resposta

(P\rightarrow Q)\wedge(Q\rightarrow R) e P\rightarrow R: não são logicamente equivalentes.
(P\wedge Q)\rightarrow P e R\vee\neg R: são logicamente equivalentes (ambas tautologias).
A\wedge(B\vee\neg C) e A\wedge(\neg B\wedge C): não são logicamente equivalentes.

Exercícios relacionados