Discrete Mathematics for Computer Science

120 CHAPTER 2 Formal Logic

(b) Let 0 be the formula

( ... ((P I <+- P2) ++ P3) +- .)•Pn

for n > 1. For what interpretations I is I (0) = T? (Hint: The answer involves

counting how many of the pi's are true in I. Prove the result by induction on n.)

22. Two other commonly used propositional connectives are exclusive or (either one or
    the other but not both are T), denoted V, and the Sheffer stroke (not both T), denoted
    Their truth tables are as follows:

p q pVq p q p ý q

T T F T T F

T F T T F T

F T T F T T

F F F F F T

(a) Do commutative laws hold for V and I?

(b) Do associative laws hold for v and I?

(c) For what interpretations I is I((... ((Pl Y P2) v P3) v ...) v pn) = T?

(d) Find formulas 01 and 02, (containing only proposition letters; the propositional

constants T and F; the propositional connectives -- , v, and A; and parentheses)

that are logically equivalent to p V q and p Iq. (Compare formula x in Table 2.5 in

Section 2.3.1, where such a formula is given for p +- q.)

(e) Repeat part (d) for p v p and pIp, but find the shortest formulas you can.

(f) Find formulas logically equivalent to p A q, p V q, and -- p built from p and q

using only I and parentheses.

23. Prove both parts of Theorem 2.


24. Prove parts (b) through (e) of Theorem 3.


25. (a) Prove both parts of Theorem 4.
    (b) Show that the converses to both parts of Theorem 4 need not be true.
    (c) Does Theorem 4(a) remain true if the word tautology is replaced with satisfiable?
    Definition A formula is an alphabetic substitution of a formula 0 if is formed from
    0 by replacing every occurrence of some proposition letter p in 4) with some proposition
    letter q where q does not occur in 4). (Note: The relation of being an alphabetic substitution
    is symmetric, but it is not reflexive or transitive.) Define to be an alphabetic variant of
    0 if there is a finite sequence of formulas 00, 0, ... .. on where )00 = 0, each Oi+1 is an
    alphabetic substitution of 4)i, and 0,n = .
    26. (a) Show that (p v q) is an alphabetic variant of (q V p).
    (b) Show that the relation of being an alphabetic variant is an equivalence relation.
    (c) Show that if r is an alphabetic variant of 0, then 0 is a tautology (respectively, is
    satisfiable, is unsatisfiable) if and only if ' is a tautology (respectively, is satisfi-
    able, is unsatisfiable).
    (d) Show that 4 being an alphabetic variant of does not imply that 0 and Vr are
    tautologically equivalent.
    27. The first stage of the method described to "push negations inward" was a method to
    eliminate --'s and ++'s. Prove that in the method to eliminate them, the process of