What is the conjunctive normal form for $(\neg Q\land P) \lor (\neg Q\land R) \lor (\neg P \land \neg R)$

82 Views Asked by At

$(\neg Q\land P) \lor (\neg Q\land R) \lor (\neg P \land \neg R)$
i have calculated this using wolframalpha and the output of CNF was
$(\neg Q \lor\neg P) \land (\neg Q \lor\neg R) $
but all i can reach out -after using the Absorption rule- is $(\neg Q\land P) \lor (\neg Q\land R) \lor (\neg P \land \neg R)$ and using Distribution the final result is $\neg Q\land(R \lor P)\lor \neg P \land \neg R $
so can someone help me getting what is wrong

1

There are 1 best solutions below

0
On BEST ANSWER

The Redundacy Law or Reduction might be useful here $\def\box#1#2{\boxed{\underline{\text{#1}}\\#2\\}}$ $$\box{The Redundancy Law/Reduction} {(P\land \neg Q)\lor Q\equiv P\lor Q\\ \underline{\text{Proof.}}\\ \begin{align} &(P\land \neg Q)\lor Q\\ \equiv&(P\lor Q)\land (\neg Q\lor Q)\hspace{5ex}\text{Distributive law}\\ \equiv&(P\lor Q)\land \top\hspace{13ex}\text{Negation law}\\ \equiv&P\lor Q\hspace{19.3ex}\text{Identity law} \end{align} }$$ Here is a possible approach for your question, which gives the Minimal CNF \begin{align} &(¬Q∧P)∨(¬Q∧R)∨(¬P∧¬R)\\ \equiv&(\neg Q\land(P\lor R))∨(¬P∧¬R)\tag*{Distributive law}\\ \equiv&(\neg Q\land\neg(\neg P\land\neg R))∨(¬P∧¬R)\tag*{De Morgan's law}\\ \equiv&\neg Q\lor (\neg P\land \neg R)\tag*{Redundancy law}\\ \equiv&(\neg Q\lor \neg P)\land(\neg Q\lor\neg R)\tag*{Distributive law} \end{align}