Converting to conjunctive normal form?

Question

How to convert to conjunctive normal form? If i have a formula:

$(\neg Q\land P) \lor (\neg Q\land R) \lor (Q \land \neg P \land \neg R) \lor (\neg P \land \neg R)$

The formula is in disjunctive normal form. I don't know which rule to use. I tried to use distribution rule as stated here but i would end up at 24 members which i don't think is the correct way to do this.

Answer 1

Well, you can do what you sad: just 'multiply' them all out; it'll give you 24 terms, but many can be removed through various simplification principles.

In fact, one of those simplification principles is:

Absorption

$P \land (P \lor Q) \Leftrightarrow P$

$P \lor (P \land Q) \Leftrightarrow P$

You can apply this to your original expression, since $\neg P \land \neg R$ will 'absorb' $Q \land \neg P \land \neg R$, and therefore your original expression can immediately be simplified to just:

$(\neg Q\land P) \lor (\neg Q\land R) \lor (\neg P \land \neg R)$

OK, and now applying Distribution will 'only' give you $8$ terms ... that's not so bad, is it?

Answer 2

Try a Karnaugh map: $$\begin{array}{c|cccc} P\setminus QR&00&01&11&10\\ \hline 0&1&1&0&1\\ 1&1&1&0&0\end{array}$$

The disjunctive normal form can be found by covering the $1$ entries with rectangles that correspond to conjunctions. The conjunctive normal form can likewise be found from the $0$ entries, but the corresponding literals must all be negated.

In this case, we see that $\neg Q\lor\neg R$ and $\neg P\lor\neg Q$ will cover all possible ways of getting $0$, so the conjunctive normal form is $(\neg P\lor\neg Q)\land(\neg Q\lor\neg R)$. (We also see that the minimal disjunctive normal form is $\neg Q\lor(\neg P\land\neg R)$.)