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 sub-
formula -- 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 Sub-
stitution 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."- 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) - 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 DeMor-
gan's Laws, the second is equivalent to -q v -- r. So, the entire formula is equivalent
to
(p A -'q) A (-q V ---r)
- 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
- 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? - 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?