How is this simplification done?

Question

The models of the formula $p \rightarrow \neg(q \rightarrow r)$ are $V_{2}, V_{5}, V_{6}, V_{7}, V_{8}$. In disjunctive normal form this would be:

$(p \wedge q \wedge \neg r) \vee (\neg p \wedge q \wedge r) \vee (\neg p \wedge q \wedge \neg r) \vee (\neg p \wedge \neg q \wedge r) \vee (\neg p \wedge \neg q \wedge \neg r)$

In the book it says that this formula can be simplified to $(p \wedge q \wedge \neg r) \vee \neg p$. It says that the disjunction of the last four conjunctions is equivalent with $\neg p$.

I would like to know how this simplification is done in the most simplest of terms, since the book doesn't mention anything about it.

Answer 1

A literal consists of a lower case letter or its negation. Each conjunction here consists of three literals from the set of literals {p, ¬p, q, ¬q, r, ¬r} where no letter appears twice in a conjunction. Now, suppose that we have a conjunction with ¬p as the first literal. What are the other possibilities for the other two literals? Well, the possibilities correspond to pairs (q, r), (q, ¬r), (¬q, r), (¬q, ¬r). Consequently, every possibility for "¬p" gets covered by the last four conjunctions cover all cases where "¬p" holds true. Thus, if any of the last 4 cases, then ¬p holds true.

Perhaps a better way to think about it, let's write the truth table out here:

p   q   r   F(p, q, r)
0   0   0   1   
0   0   1   1
0   1   0   1
0   1   1   1
1   0   0   0
1   0   1   0
1   1   0   1
1   1   1   0

If p, q, and r are false, then ¬p, ¬q, and ¬r are true. Thus (¬p$\land$¬q$\land$¬r) corresponds to the first row above. (¬p$\land$¬q$\land$r) corresponds to the second row above and so. The last four conjunctions of the formula in the post correspond to the 1st 4 rows above. This consists of the only time that ¬p holds true. Equivalently, if ¬p holds true, then a disjunction of the 4 conjunctions will hold true. Consequently, we can replace such a disjunction of conjunctions by ¬p.

Actually, we could further simplify the formula to [¬p$\lor$(q$\land$$\lnot$r)].

Answer 2

Hint. $(a \wedge b) \vee (a \wedge c) \equiv a \wedge (b \vee c)$

Also, a satisfiable expression $f$ has some satisfying assignment $y_1 \dots y_n$. Given any assignment $x_1 \dots x_n$ we have map $x_i = y_i$ or $\neg x_i = y_i$. Therefore if we fix any assignment $x_i$ and try all possible ways to negate its variables, we will run into one that satisfies $f$.