# Rubik’s cube notes – logic

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