108 CHAPTER 2 Formal Logic
Table 2.5 lists many commonly used tautologies. The reader should study them care-
fully and determine what they "assert." The names should suggest analogies to other
operations. For example, V, A, and <-* all obey associative laws, just as + and do in
arithmetic.Table 2.5 Commonly Used Tautologies(a) (p A p) ÷ p Idempotence
(b) (p v p) ÷- p Idempotence(c) p V -'p Law of the Excluded Middle
(d) -(p A -p)
(e) (p A (p --+ q)) -+ q Modus Ponens
(f) ((p --* q) A (q -- r)) -+ (p -+ r) The Law of Syllogism
(g) ((p V q) A -p) -- q Modus Tollendo Ponens
(h) ((p A q) A r) *÷ (p A (q A r)) Associative Law
(i) ((p V q) v r) *-+ (p V (q V r)) Associative Law(j) ((p ++ q) + r) + (p - (q +- r)) Associative Law
(k) (p A r) +- (r A p) Commutative Law
(1) (p V r) -•* (r V p) Commutative Law
(m) (p -• r) <* (r *+ p) Commutative Law
(n) (p A (r V q)) +* ((p A r) V (p A q)) Distributive Law
(o) (p V (r A q)) +- ((p V r) A (p V q)) Distributive Law
(p) ----p -* p Double negative
(q) -(p A r) *-+ (-p V -r) DeMorgan's Law
(r) -(p v r) +* (--p A -r) DeMorgan's Law
(s) (p -- r) ÷ (-r - --p) Contrapositive(t) (p -+(r - q)) -((p A r) - q)
(u) ((--p -+ r) A (-p --+ -r)) * p Contradiction
(v) ((p A r) V r) +- r Absorption
(w) ((p V r) A r) +-* r Absorption
(x) (p *+ q) +-* ((p A q) V (-,p A -,q))
(y) -(p +-•q) * ((-p A q) V (p A -q))
(z) (p -+ F) <-* (-,p)The two tautologies (q) and (r) in Table 2.5, called DeMorgan's Laws, are the logi-
cal analogues of the DeMorgan's Laws of set theory (Theorem 8 in Section 1.3.2). That
theorem states how the set operations of union, intersection, and complementation interact.
Here, we see how conjunction, disjunction, and negation interact with propositions.Example 8. Let p denote "X is a bird" and r denote "X can fly." Tautology(s) from Table
2.5 states that "If X is a bird implies that X can fly" is equivalent to "If X cannot fly, then
X is not a bird."The following theorem is the basis of many proofs, notably many proofs by contradic-
tion.Theorem 1. A formula * is a tautology if and only if -*4 is unsatisfiable.