Conversion of disjunctive normal form to conjunctive normal form

Question

Explain how $ (p \lor q \lor r \lor s) $ can be re-written into an equivalent CNF formula such that each clause contains exactly $3$ variables or negations of variables.

Answer 1

Hints:

$$ (p \lor q \lor r \lor s) \equiv (((p \lor q) \lor r) \lor s) \; \text {Associative Law} $$

$$ (a \lor b) \equiv (\lnot (\lnot(a \lor b) ))$$

$$ (\lnot (a \lor b)) \equiv ((\lnot a) \land (\lnot b)) \; \text {de Morgan's Law}$$

Answer 2

To convert long disjunctions to length 3, can break the clause up by inserting a new variable, $$(p\vee q\vee r\vee s) \to (p\vee q\vee z) \wedge (\overline{z} \vee r\vee s).$$ The resulting statement require at least one of the $p,q,r,s$ variables to be true in order for both clauses to be true. It is interesting to note that this can only be done for clauses of length at least 3.