How to convert this CNF to a DNF? (((p ∨ q) ∧ (¬q ∨ ¬r)) ∧ (¬p ∨ r))
I know we can use a truth table, but I'm trying to convert by equivalences. It seems like it will blow up, but I may be doing this wrongly. Could someone let me know if you could get the answer without a blow up please?
Thanks!
 A: You know the FOIL principle from high school algebra, right?
$$(a + b)(c + d) = ac+ad+bc+bd$$
Well, this principle can be generalized to more and larger terms. For example:
$$(a + b + c)(d + e + f) = ad+ae+af+bd+be+bf+cd+ce+cf$$
So note what happens here: you pick exactly one variable from each term, and list all the possible ways to do that. So with two terms having $3$ variables each, you get $3 \times 3 = 9$ terms as you can see above.
Now, as it turns out, in boolean algebra the same distributive principles hold. Here is the classic '$2 \times 2$' FOIL which gets you $4$ terms:
$$(A \lor B) \land (C \lor D)=$$
$$((A \lor B) \land C) \lor ((A \lor B) \land D )=$$
$$(A \land C) \lor (B \land C) \lor (A \land D) \lor (B \land D)$$
So, like FOIL, you can go from the first one straight to the final one (you just call it 'Distribution' in the context of logic). And, like FOIL, it generalizes to any number of terms of any size. For example, here is a '$2 \times 3$' that gives you $6$ terms:
$$(A \lor B) \land (C \lor D \lor E) =$$
$$(A \land C) \lor (A \land D) \lor (A \land E) \lor (B \land C) \lor (B \land D) \lor (B \land E)$$
And here is the '$2 \times 2 \times 2$' that you are dealing with, giving you $8$ terms:
$$(A \lor B) \land (C \lor D) \land (E \lor F)=$$
$$ (A \land C \land E) \lor (B \land C\land E) \lor (A \land D\land E) \lor (B \land D\land E) \lor (A \land C \land F) \lor (B \land C\land F) \lor (A \land D\land F) \lor (B \land D\land F)$$
So yeah, it's a little work to write that all out, but at least you don't have to go through all the intermediate steps.
Also, the 'blow up' is unavoidable ... but it is certainly not 'incredibly long', and in the resulting DNF you can remove any term that contains an atomic statement and its negation. E.g. the 'first' term you get is $p \land \neg q \land \neg p$, which is equivalent to a contradiction $\bot$, and a contradiction disjuncted with anything else is equivalent to that anything else.
