$(\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
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Your formula is equivalent, but it is not the conjunctive normal form. $\endgroup$– ascheplerCommented Jul 20, 2020 at 20:22
-
$\begingroup$ what is wrong is you can't have $\color{red}{∨}$ here for CNF. $$¬Q∧(R∨P)\color{red}{∨}(¬P∧¬R)$$ $\endgroup$– EthanCommented Jul 20, 2020 at 22:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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}
