"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].