108
CHAPTER 2 Formal Logic
Table 2.5 lists many commonly used tautologies. The reader should study them carefully 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 logical 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 contradiction.
Theorem 1. A formula * is a tautology if and only if -*4 is unsatisfiable.
CHAPTER 2 Formal Logic
Table 2.5 lists many commonly used tautologies. The reader should study them carefully 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 logical 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 contradiction.
Theorem 1. A formula * is a tautology if and only if -*4 is unsatisfiable.