116
CHAPTER 2 Formal Logic
This is an application of the Second Substitution Principle. Then, eliminate all --*'s as
follows: Replace each subformula of the form • -
,1 with the logically equivalent subformula --4 V V.
Step 2. Apply DeMorgan's Laws,
-(p V q) <-+ (-p A -q)
and -- (p A q) <-+ (-p V -q)
to "push negations" in past A and v and replace each double negation -- p formed with
the unnegated p. Ultimately, only proposition letters will be negated. By the Second Substitution Principle, the formula so formed will be equivalent to the original formula.
Example 12. For the formula
-_(-(p A -- q) V (q A -- r))
use DeMorgan's Laws and the law of double negation to "push negations inside."
Solution. Start from the "outside" and work "inside."
1. This formula is of the form --,(0 V fl), where 0 = -(p A -q) and 7f = (q A -- r), so
we apply DeMorgan's Law to get the equivalent
-- '(p A -- q) A -,(q A -r)
2. Apply the same techniques to the "outermost" subformulas, -- '(p A -q) and -- (q A
-- r). By the law of double negation, the first is equivalent to (p A -q) and by DeMorgan's Laws, the second is equivalent to -q v -- r. So, the entire formula is equivalent
to
(p A -'q) A (-q V --- r)
3. Now work "inward." Again, by the law of double negation, -- r is equivalent to r, so
the entire formula is equivalent to
(p A -'q) A (-q V r)
which is in the desired form.
rnExercises
1. A restaurant displays the sign "Good food is not cheap," and a competing restaurant
displays the sign "Cheap food is not good." Are the two restaurants saying the same
thing?
2. The country of Ost is inhabited only by people who either always tell the truth or
always tell lies and who will respond to questions only with a "yes" or a "no." A
tourist comes to a fork in a road, where one branch leads to the capital and the other
does not. There is no sign indicating which fork to take, but Mr. Zed, who is a resident
of Ost, comes along. What single question should the tourist ask Mr. Zed to determine
which fork in the road to take?
CHAPTER 2 Formal Logic
This is an application of the Second Substitution Principle. Then, eliminate all --*'s as
follows: Replace each subformula of the form • -
,1 with the logically equivalent subformula --4 V V.
Step 2. Apply DeMorgan's Laws,
-(p V q) <-+ (-p A -q)
and -- (p A q) <-+ (-p V -q)
to "push negations" in past A and v and replace each double negation -- p formed with
the unnegated p. Ultimately, only proposition letters will be negated. By the Second Substitution Principle, the formula so formed will be equivalent to the original formula.
Example 12. For the formula
-_(-(p A -- q) V (q A -- r))
use DeMorgan's Laws and the law of double negation to "push negations inside."
Solution. Start from the "outside" and work "inside."
1. This formula is of the form --,(0 V fl), where 0 = -(p A -q) and 7f = (q A -- r), so
we apply DeMorgan's Law to get the equivalent
-- '(p A -- q) A -,(q A -r)
2. Apply the same techniques to the "outermost" subformulas, -- '(p A -q) and -- (q A
-- r). By the law of double negation, the first is equivalent to (p A -q) and by DeMorgan's Laws, the second is equivalent to -q v -- r. So, the entire formula is equivalent
to
(p A -'q) A (-q V --- r)
3. Now work "inward." Again, by the law of double negation, -- r is equivalent to r, so
the entire formula is equivalent to
(p A -'q) A (-q V r)
which is in the desired form.
rnExercises
1. A restaurant displays the sign "Good food is not cheap," and a competing restaurant
displays the sign "Cheap food is not good." Are the two restaurants saying the same
thing?
2. The country of Ost is inhabited only by people who either always tell the truth or
always tell lies and who will respond to questions only with a "yes" or a "no." A
tourist comes to a fork in a road, where one branch leads to the capital and the other
does not. There is no sign indicating which fork to take, but Mr. Zed, who is a resident
of Ost, comes along. What single question should the tourist ask Mr. Zed to determine
which fork in the road to take?