# Correct progression from DNF to CNF?

Trying to figure out how to transform this predicate from disjunctive normal form to conjunctive normal form (repost of an earlier question):

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

Re-write rule: distribution of conjunction over disjunction: $$( S \land ( P \lor R ) ) \lor ( P \land Q )$$

"Add" $S \lor$ to each: $$( S \lor S \land ( P \lor R ) ) \land ( S \lor ( P \land Q ) )$$

$S \lor S \land$ "cancel out": $$( P \lor R ) \land ( S \lor ( P \land Q ) )$$

Re-write rule: Distribution of disjunction over conjunction: $$( P \lor R ) \land ( P \lor S ) \land ( Q \lor S )$$

The rewrite rules I'm unsure of I have put in quotes.

Is the above a valid progression?

Please note: $S\lor S \neq \text{True}$.

But we cannot "Add" $S$ to both sides of the disjunction: $$( S \land ( P \lor R ) ) \lor ( P \land Q )$$

without changing the proposition to a nonequivalent proposition (note, doing so will give you the following, so your "adding" S was not the only error, you also "added" S incorrectly):

$$[S \lor ( S \land ( P \lor R ) )] \lor [S\lor ( P \land Q )]\equiv S \lor [S \lor (P \land Q)] \equiv S$$

It other words, by "adding $S$", we are essentially making the original proposition into a proposition that depends only on the truth value of $S$.

Take care! You were simply lucky that you incorrectly evaluated what "adding S" to both sides of the disjunction would do, and lucky that that error happened to give you a final correct answer.

It's not too challenging to transition from DNF to CNF: \begin{align} ( P \land Q ) \lor ( R \land S ) \lor ( P \land S ) &\equiv [( P \land ( Q \lor S ) ] \lor (R \land S)\\ \\ &\equiv [R \lor (P \land (Q \lor S))] \land [S \lor (P \land (Q \lor S))]\\ \\ & \equiv (P\lor R) \land (Q\lor R \lor S) \land (P \lor S) \land (Q \lor S)\\ \\ &\equiv (P \lor R) \land (P \lor S) \land (Q \lor S)\end{align}

Challenge: see if you can justify the last step above.

• Thanks, @Amzoti. I hope you're having a fantastic day! Commented Oct 30, 2013 at 1:23
• @amWhy: Right back at you! ;-) Commented Oct 30, 2013 at 1:23
• Challenge reply: I would say that $\land ( Q \lor S )$ "cancels out" $\land ( Q \lor R \lor S )$" -- how would you say it? Commented Nov 4, 2013 at 18:52

No, your doubtful "rules" make no sense. By accident the errors cancel out.

• I suspected I was noticing a coincidence rather than discovering a new rule! Commented Oct 29, 2013 at 8:33

After about a dozen of distributions I get the following CNF:

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

Then we cancel those clauses that are equivalent to simpler ones already present, obtaining:

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

Given the long formula, it is provable (by $\lor$-intro), for example, that: $(P \lor R) \equiv (P \lor R \lor Q)$, so we can simply get rid of the redundancies by deleting conjuncts 2, 3, 4, and 6, because they're already contained in conjuncts 1, 5, and 7. To convince yourself of this, work backwards:

1 $(P \lor R) \land (S \lor P) \land (S \lor Q)$ [assumption]

2 $(P \lor R)$ [from 1 by $\land$-elimination]

3 $(P \lor S)$ [from 1 by $\land$-elimination]

4 $(S \lor Q)$ [from 1 by $\land$-elimination]

5 $(P \lor R \lor Q)$ [from 2 by $\lor$-introduction]

6 $(S \lor R \lor P)$ [from 2 by $\lor$-introduction]

7 $(S \lor R \lor Q)$ [from 4 by $\lor$-introduction]

8 $(P \lor S \lor Q)$ [from 4 by $\lor$-introduction]

9 $(P \lor R) \land (P \lor R \lor Q) \land (S \lor R \lor P) \land$

$~~~~~~ (S \lor R \lor Q) \land (P \lor S) \land (P \lor S \lor Q) \land (S \lor Q)$ [from 2-8 by $\land$-introduction]

Since you asked, here are the steps that took me to the long formula & its eventual simplification:

• I'd be interested in seeing your dozen or so distributions. Commented Oct 29, 2013 at 8:32
• Thanks for the extra info. I think the rule missing from my arsenal was $( P \lor Q ) \land ( P \lor Q \lor R ) \equiv ( P \lor Q )$ Commented Oct 29, 2013 at 16:10
• ...but what really helped was when you grouped $( ( R \lor P ) \land ( R \lor Q ) )$ sepately from $( ( S \lor P ) \land ( S \lor Q ) )$ then "add" $\lor ( P \land S )$ to each group -- it prompted me to group $( ( P \lor S ) \land ( P \lor S ) )$ sepately from $( ( Q \lor R ) \land ( Q \lor S ) )$ and made my own way to a solution. Commented Oct 29, 2013 at 16:30
• @onedaywhen I'm glad you found it helpful. Commented Oct 29, 2013 at 19:09