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

Passo 1

O enunciado pede para verificar, por meio de Tableaux semântico, se a fórmula
\neg(p \wedge q)\;\rightarrow\;(\neg p \vee \neg q)
é válida (isto é, tautologia) e, caso não fosse, encontrar um contraexemplo. Para mostrar validade via tableaux, testamos a insatisfatibilidade da negação da fórmula.

Passo 2

Escrevemos a negação da fórmula principal como fórmula inicial no tableau:
1.\quad \neg\bigl(\neg(p \wedge q)\rightarrow(\neg p \vee \neg q)\bigr)
e vamos decompor passo a passo.

Passo 3

Aplicamos a regra de negação de implicação:
\neg(A\rightarrow B)\;=\;A\wedge\neg B.
Aqui A é \neg(p \wedge q) e B é \neg p \vee \neg q. Logo obtemos duas fórmulas conjuntas:
2.\quad \neg(p \wedge q)
3.\quad \neg\bigl(\neg p \vee \neg q\bigr)

Passo 4

Decompomos a negação de disjunção em conjunção de negações:
\neg(\neg p \vee \neg q)\;=\;\neg\neg p\;\wedge\;\neg\neg q.
Isto gera:
4.\quad \neg\neg p
5.\quad \neg\neg q
Em seguida simplificamos duplas negações: 6.\quad p 7.\quad q

Passo 5

Agora restou a fórmula \neg(p \wedge q). A negação de conjunção se decompõe em disjunção de negações:
\neg(p \wedge q)\;=\;\neg p\;\vee\;\neg q.
Isto gera duas ramificações no tableau:
Ramo 1:
8.\quad \neg p
Ramo 2:
9.\quad \neg q
Em ambas as ramificações mantemos também as fórmulas p (6) e q (7).

Passo 6

Verificamos cada ramo:
  • Ramo 1 contém p e \neg p (contradição).
  • Ramo 2 contém q e \neg q (contradição).
Ambos os ramos fecham. Como não há ramo aberto, a negação da fórmula é insatisfatível.

Resposta

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

Exercícios relacionados