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

Passo 1

O enunciado pede para verificar a validade da fórmula
\varphi \;=\;(p\rightarrow q)\;\vee\;\neg(\neg p\vee q)
usando o método de CNF. O conteúdo aqui é lógica proposicional e vamos testar se \varphi é tautologia mostrando que a negação \neg\varphi é insatisfatível quando convertida para CNF.

Passo 2

Para verificar a validade de \varphi, consideramos a negação \neg\varphi e mostramos que \neg\varphi não tem nenhuma interpretação que a torne verdadeira (ou seja, suas cláusulas em CNF entram em contradição).

Passo 3

Escrevendo explicitamente
\neg\varphi =\neg\bigl((p\rightarrow q)\vee\neg(\neg p\vee q)\bigr)
aplicamos De Morgan a uma disjunção:
\neg\varphi =\neg(p\rightarrow q)\;\wedge\;\neg\neg(\neg p\vee q) =(\neg(p\rightarrow q))\wedge(\neg p\vee q).

Passo 4

Agora eliminamos a implicação p\rightarrow q\equiv\neg p\vee q:
\neg(p\rightarrow q) =\neg(\neg p\vee q) = p\wedge\neg q.
Logo
\neg\varphi =(p\wedge\neg q)\wedge(\neg p\vee q).

Passo 5

Observamos que
(p\wedge\neg q)\wedge(\neg p\vee q)
já está em forma normal conjuntiva (CNF): é a conjunção das cláusulas \{p\}, \{\neg q\} e \{\neg p\vee q\}.

Passo 6

Verificamos insatisfatibilidade:
da cláusula \{p\} e da cláusula \{\neg p\vee q\} deduzimos q,
que contradiz a cláusula \{\neg q\}. Logo não há interpretação que satisfaça todas as cláusulas.

Resposta

A fórmula (p\rightarrow q)\vee\neg(\neg p\vee q) é válida, pois a CNF da sua negação é insatisfatível.

Exercícios relacionados