Converta para CNF as fórmulas abaixo:
(\neg p \wedge(\neg q \rightarrow r)) \rightarrow s

Passo 1

O enunciado nos dá a fórmula
(\neg p \wedge(\neg q \rightarrow r)) \rightarrow s
e pede para convertê-la em Forma Normal Conjuntiva (CNF). Para isso vamos usar três etapas principais:
  1. Eliminar todas as implicações usando (A\rightarrow B)\equiv \neg A\vee B.
  2. Mover negações para dentro com as Leis de De Morgan.
  3. Distribuir disjunções sobre conjunções para chegar a uma conjunção de cláusulas.

Passo 2

Eliminamos primeiro a implicação interna \neg q\rightarrow r e depois a externa:
\neg q \rightarrow r \equiv \neg(\neg q)\vee r \equiv q\vee r
(\neg p \wedge(q\vee r)) \rightarrow s \equiv \neg(\neg p \wedge(q\vee r)) \vee s

Passo 3

Aplicamos De Morgan em \neg(\neg p \wedge(q\vee r)):
\neg(\neg p \wedge(q\vee r)) \equiv \neg(\neg p)\vee \neg(q\vee r) \equiv p \vee (\neg q \wedge \neg r)
Logo a fórmula fica
(p \vee (\neg q \wedge \neg r)) \vee s \equiv (p \vee s \vee (\neg q \wedge \neg r))

Passo 4

Distribuímos a disjunção sobre a conjunção interna \neg q \wedge \neg r, usando
X\vee(Y\wedge Z)\equiv (X\vee Y)\wedge (X\vee Z).
Aqui X = p\vee s, Y=\neg q, Z=\neg r. Assim
(p\vee s\vee(\neg q\wedge\neg r)) \equiv \bigl((p\vee s)\vee\neg q\bigr)\;\wedge\;\bigl((p\vee s)\vee\neg r\bigr)
e simplificando a notação de disjunção,
(p \vee s \vee \neg q)\;\wedge\;(p \vee s \vee \neg r).

Resposta

(p \vee s \vee \neg q)\;\wedge\;(p \vee s \vee \neg r)

Exercícios relacionados