“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 admittedly 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 “multiplication” (*) 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 hypotheses) 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].
Yet Another Mathblog 