118 CHAPTER 2 Formal Logic
(d) (p- (r V q)) ((p r) v (p q))
(e) (p- (rAq)) ((p r) v(p q))
(f) ((p- q) --> q) -+ p- Construct the truth table for
(p A (p -+ q) A (q -- r)) -- rSimplify this expression to one using only A, v, and -.- Show that the following formulas from Table 2.5 are tautologies:
(a) (pAp) ÷*p
(b) (p A (p q)) -+ q
(c) (p - r) + (-r - -p)- Let 0 = (p V q) -> (r A -s). For each of the following interpretations of
p, q, r, and s, compute 1(0) using the truth tables for -, V, A, --, and *÷:
(a) I(p) = T, I(q) = T, I(r) = T, and I(s) = F
(b) l(p) = T, I(q) = T, I(r) = F, and I(s) = F
(c) I(p) = F, 1(q) = T, 1(r) = T, and I(s) = T
(d) I(p) = F, I(q) = F, 1(r) = T, and I(s) = T
- Let 4 = (p -+ q) -+ ((r A -s) -> q). For each of the following interpretations of
p, q, r, and s, compute 1(4) using the truth tables for -, V, A, ->, and •-*:
(a) I(p) = T, I(q) = T, I(r) = F, and I(s) = T
(b) I(p) = T, I(q) = F, I(r) = T, and I(s) = F
(c) I(p) = F, 1(q) = T, I(r) = T, and I(s) = F
(d) I(p) = F, I(q) = F, I(r) = T, and I(s) = F
- Let 4 = (-(p A q)) + (-r V -s). For each of the following interpretations of
p, q, r, and s, compute I(0) using the truth tables for -, V, A, -+, and •÷:
(a) I(p) = T, I(q) = T, I(r) = F, and I(s) = T
(b) I(p) = T, I(q) = F, I(r) = F, and I(s) = F
(c) l(p) = F, l(q) = T, I(r) = F, and I(s) = T
(d) I(p) = F, l(q) = F, 1(r) = F, and I(s) = T
- Simplify the following boolean expressions:
(a) (x A y) V (x A -y) V (-x A y) V (-XA-y)
(b) (XAyAZ)V(XA-yAz)V(-xAyA-Z)V(-xXA-yAZ)
(c) (xAyA-Z)V(XA-yAZ)V(XA-yA-Z)
- Find formulas equivalent to the following formulas with all the negations "pushed
inward to the proposition letters":
(a) --(p AT)
(b) ((p q) r)- F
(c) ((p - q) - r) -+ T
(d) (p <-> q) <- r
(e) (p * q) ++ F
(Hint: Look for a way to simplify this last one.) (Note: The method given to "push
negations inward" does not always give the shortest formula that is equivalent to the
given formula and has - applied only to proposition letters.)