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”,

“The rules of logic are to mathematics what those of structure are to architecture.”
Bertrand Russell
1917, p61


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


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