Verifique a validade das seguintes fórmulas, utilizando o método da CNF:
\neg(\mathrm{p} \wedge \mathrm{q}) \rightarrow(\neg \mathrm{p} \vee \neg \mathrm{q})

Passo 1

O enunciado pede para verificar a validade da fórmula
\neg(p \wedge q)\rightarrow(\neg p \vee \neg q)
usando o método de CNF (forma normal conjuntiva) e resolução. Isso faz parte de lógica proposicional, e vamos mostrar que a negação da fórmula é insatisfatível, provando assim que a fórmula é uma tautologia.

Passo 2

Uma fórmula \Phi é válida (tautologia) se, e somente se, a sua negação \neg\Phi for insatisfatível. Portanto, definimos
\Phi \;=\;\neg(p \wedge q)\rightarrow(\neg p \vee \neg q)
e vamos testar a insatisfatibilidade de
\neg\Phi \;=\;\neg\bigl(\neg(p \wedge q)\rightarrow(\neg p \vee \neg q)\bigr).

Passo 3

Simplificamos \neg\Phi usando equivalências lógicas:
\neg\bigl(A\rightarrow B\bigr)\equiv A\wedge\neg B,
onde A=\neg(p\wedge q) e B=(\neg p\vee\neg q). Logo
\neg\Phi \equiv \neg(p\wedge q)\;\wedge\;\neg\bigl(\neg p\vee\neg q\bigr).
Em seguida,
\neg\bigl(\neg p\vee\neg q\bigr)\equiv p\wedge q,
portanto
\neg\Phi\equiv \bigl(\neg(p\wedge q)\bigr)\wedge(p\wedge q).
E finalmente
\neg(p\wedge q)\equiv(\neg p\vee\neg q),
de modo que
\neg\Phi\equiv(\neg p\vee\neg q)\;\wedge\;p\;\wedge\;q.

Passo 4

Escrevemos \neg\Phi em CNF como um conjunto de cláusulas:
(\neg p\vee\neg q)\wedge p\wedge q
gera as cláusulas
C_1:\{\neg p,\neg q\},\quad C_2:\{p\},\quad C_3:\{q\}.

Passo 5

Aplicamos o método de resolução:
  • Resolva C_1 e C_2:
    C_1=\{\neg p,\neg q\} e C_2=\{p\} resolvem sobre p, produzindo
C_4=\{\neg q\}.
  • Resolva C_4 e C_3:
    C_4=\{\neg q\} e C_3=\{q\} resolvem sobre q, produzindo a cláusula vazia \bot.
A obtenção de \bot mostra que \neg\Phi é insatisfatível.

Resposta

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

Exercícios relacionados