Disjunctive normal form process

63 Views Asked by At

Say I want to transform a term in to disjunctive normal form; $$((\neg p \land \neg r) \lor q) \land ( \neg r \lor p)$$

Then what is the next step? I keep going round in circles. Do I do $$((\neg r \land ((\neg p \land \neg r) \lor q) \lor (p \land ((\neg p \land \neg r) \lor q))?$$

2

There are 2 best solutions below

0
On

Yes, that would be good: just keep distributing any $\land $ over $\lor$ and you'll get there. In fact, you're just two such distributions away from it being in DNF

0
On

Hint: Temporarily substituting $x$ for $(\neg p\land\neg r)$ will make things less cluttered. $$\begin{split}((\neg p \land \neg r) \lor q) &\land ( \neg r \lor p)\\(x\lor q)&\land(\neg r\lor p)&\quad&\text{substitution: }[x\backslash(\neg p\land\neg r)]\\ ((x\lor q)\land \neg r)~&\lor~((x \lor q)\land p) &&\text{distribution }\land\text{ over }\lor \end{split}$$ This is where you are.   Can you now see how to distribute within those two disjuncts to get a disjunctive series of conjunctions?   Well, after that, substitute back and you shall see what you must do then.