1

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.

Garth Marenghi
  • 1,115

2 Answers2

1

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$.

Karolis Juodelė
  • 9,702
  • 1
  • 25
  • 39
  • I get what you're trying to say, but I still can't frame it. E.g.: $\neg p \vee (p \wedge q \wedge \neg r)$ would be $(\neg p \vee p) \wedge (\neg p \vee q) \wedge (\neg p \vee \neg r)$. Otherwise, removing $\neg p$ from the last 4 disjunctions, what happens to the $\neg q$'s, $q$'s, $\neg r$'s, $r$'s$ in that formula? – Garth Marenghi May 06 '14 at 19:14
  • I see your edited post, thanks for your effort. But I do not understand what you are talking about. – Garth Marenghi May 07 '14 at 20:06
  • @GarthMarenghi, $f(x, y) = x \wedge y$ is satisfiable at $f(1, 1)$. What you have after moving $\neg p$ is $f(x, y) \vee f(\neg x, y) \vee f(x, \neg y) \vee f(\neg x, \neg y)$. Those are all the possible ways to put $\neg$ before $x$ and $y$. No matter what $x, y$ you start with, one of the terms will evaluate to $f(1, 1)$. Hence what you have is a tautology. – Karolis Juodelė May 08 '14 at 15:32
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)].

Doug Spoonwood
  • 11,211
  • Yes, you're absolutely correct on the further simplification, this was in the same answer. I figured that if I could get an answer for the first simplification, I'd be able to figure out the second. You beat me to it though! And, of course, thanks for your answer! – Garth Marenghi May 08 '14 at 18:17