Correct progression from DNF to CNF?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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: