Verifique a propriedade indicada das seguintes fórmulas através de Tableaux:
( p \rightarrow q ) \rightarrow ( \neg q \rightarrow \neg p ), validade, mostrando, caso não seja, um contraexemplo.

Passo 1

O enunciado pede para verificar se a fórmula
(p \rightarrow q)\rightarrow(\neg q \rightarrow \neg p)
é válida, usando o método de tableaux semântico. Para mostrar validade, constrói-se o tableau para a negação da fórmula e prova-se que todas as ramificações fecham (logo, a negação é insatisfatível).

Passo 2

Começamos com a negação da fórmula alvo:
\neg\bigl((p \rightarrow q)\rightarrow(\neg q \rightarrow \neg p)\bigr)
Aplicando a regra de negação de implicação \neg(A\rightarrow B)\equiv A\land\neg B, obtemos os ramos simultâneos
  1. p\rightarrow q
  2. \neg(\neg q \rightarrow \neg p)

Passo 3

Agora expandimos 2) de novo como negação de implicação, com A=\neg q e B=\neg p:
\neg(\neg q \rightarrow \neg p)\equiv \neg q\;\land\;\neg(\neg p).
Isto gera as fórmulas literais
3.1) \neg q
3.2) \neg(\neg p), que por dupla negação dá p.
No ramo temos então o conjunto
\{\,p \rightarrow q,\;\neg q,\;p\}.

Passo 4

Expandimos p\rightarrow q usando a regra de implicação A\rightarrow B\equiv\neg A\;\lor\;B, o que gera duas sub-ramificações:
• Ramo 1 com \neg p. Atribuindo ao conjunto: \{\neg p,\;\neg q,\;p\}, há p e \neg p juntos → contradição → ramo fecha.
• Ramo 2 com q. Atribuindo ao conjunto: \{q,\;\neg q,\;p\}, há q e \neg q juntos → contradição → ramo fecha.

Passo 5

Como ambas as ramificações fecharam, o tableau para \neg\bigl((p \rightarrow q)\rightarrow(\neg q \rightarrow \neg p)\bigr) está completamente fechado. Isso mostra que a negação da fórmula é insatisfatível, logo a fórmula original é válida (tautologia).

Resposta

A fórmula (p \rightarrow q)\rightarrow(\neg q \rightarrow \neg p) é válida.

Exercícios relacionados