"If logic is the hygiene of the mathematician, it is not his source of food; the great problems furnish the daily bread on which he thrives." Andre Weil "The future of mathematics", AMER MATH MONTHLY, May, 1950 "The rules of logic are to mathematics what those of structure are to architecture." Bertrand Russell MYSTICISM AND LOGIC AND OTHER ESSAYS, 1917, p61 LOGIC AND SETS This chapter will present some background to make some of the terminology and notation introduced later a little clearer. It is not intended to be a rigorous introduction to mathematical logic. A "statement" is a logical assertion which is either true or false. (Of course we assume that this admitedly circular 'definition' is a statement.) Sometimes the truth or falsity of a statement is called its "Boolean value". One can combine several statements into a single statement using the "connectives" 'and', 'or', and 'implies'. The Boolean value of a statement is changed using the 'negation'. We shall also use 'if and only if' and 'exclusive or' but these can be defined in terms of the other three connectives (exercise: do this). Notation: Let p and q be statements. statement notation terminology ___________________________________________________________ p and q p /\ q "conjunction" p or q p \/ q "disjunction" p implies q p => q "conditional" negate p ~p "negation" p if and only if q p <=> q "if and only if" either p or q (not both) p _\/ q "exclusive or" Given the Boolean values of p, q, we can determine the values of p/\q, p\/q, p=>q, p<=>q, p _\/ q using the truth tables: p | q | p /\ q p | q | p \/ q ------------------------------- ------------------------------- T | T | T T | T | T T | F | F T | F | T F | T | F F | T | T F | F | F F | F | F p | q | p => q p | q | p <=> q ------------------------------- ------------------------------- T | T | T T | T | T T | F | F T | F | F F | T | T F | T | F F | F | T F | F | T p | q | p _\/ q p | ~p ------------------------------- ----------------- T | T | F T | F T | F | T F | T F | T | T F | F | F Let B be the set {0,1} with the two operations "addition" (+) and "multipication" (*) defined by the following tables p | q | p + q p | q | p*q ------------------------------- ------------------------------- 1 | 1 | 0 1 | 1 | 1 1 | 0 | 1 1 | 0 | 0 0 | 1 | 1 0 | 1 | 0 0 | 0 | 0 0 | 0 | 0 Note how these mimic the truth tables of 'exclusive or' (_\/) and 'and' (/\). We call B the "Boolean algebra". Exercise: Use truth tables to verify the DeMorgan laws: (a) p /\ (q \/ r) <=> (p /\ q) V (p /\ r) , (b) p \/ (q /\ r) <=> (p \/ q) /\ (p \/ r) , and the laws of negation: (c) ~(p /\ q) <=> ~p \/ ~q , (d) ~(p \/ q) <=> ~p /\ ~q . A "logical argument" is a sequence of statements (called "hypothesis") p1, p2, ..., pn, which imply a statement q (called the "conclusion"). In other words, a "logical argument" is a true statement of the form (p1 /\ p2 /\ ... /\ pn) => q. Exercise: Use truth tables to verify the logical argument (p=>q /\ q=>r) => p=>r. A "set" is a 'well-defined' collection of objects. The objects in a set are the "elements" of the set. Just as one can use connectives to form new statements from old statements, there are analogous ways to form new sets from old ones using 'intersection' (the analog of 'and'), 'union' (the analog of 'or'), and 'complement' (the analog of 'negation'). The analog of 'implies' is 'subset'. The "empty set" is the set containing no elements, denoted EMPTY. We call two sets S, T "disjoint" if they have no elements in common, i.e., if S intersect T = EMPTY. Notation: Let S and T be sets. Assume that S is contained in a set X. statement notation terminology ___________________________________________________________ set of elmts in S and T S intersect T "intersection" set of elmts in S or T S union T "union" set of elmts in S or T (not both) S Delta T "symmetric difference" elmts in X not in S S^c "complement of S in X" S is a subset of T S subset T "subset" Exercise: Use Venn diagrams to verify the DeMorgan laws: (a) S intersect (T union U) = (S intersect q) union (T intersect U) , (b) S union (T intersect U) = (S union T) intersect (T union U) , and the laws of negation: (c) (S intersect T)^c = S^c union T^c , (d) (S union T)^c = S^c intersect T^c . Logic/set theory analogs: set theory logic ---------------------------------------------------------- sets statements union or intersection and subset implies symmetric difference exclusive or equal if and only if Venn diagrams truth tables For more on logic or set theory, see for example [C] or [St]. 