How is this simplification done? 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.
 A: 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$.
A: 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)].
