next up previous
Next: Homework 4 Up: Homework Assignments Previous: Homework 2

Homework 3

I will discuss this assignment further on Friday the 28th; the due date is extended to Tuesday, February 1.

For additional discussion, see material at the beginning of the lecture notes for Friday the 28th.

There is another ``algebraic'' approach to propositional logic which
might be of interest.  This is based on arithmetic mod 2.  Even
integers are said to be congruent to 0 mod 2, and odd integers are
said to be congruent to 1 mod 2.  The following tables for addition
and multiplication result:

+ | 0 1     * | 0 1
-------     -------
0 | 0 1     0 | 0 0
1 | 1 0     1 | 0 1

If we interpret 0 as false and 1 as true, we can think of these
as truth tables for <+> (addition) and & (multiplication).  ~x can be
defined as 1+x.  x|y can be defined as x+y+xy, so the notions
1, *, + = ``true'', conjunction, and exclusive or, are a basis 
for the propositional connectives (we have shown how to define
negation, conjunction and disjunction using these).

The usual algebraic rules for addition and multiplication (both
operations are commutative and associative, multiplication distributes
over addition, 0 is the identity of addition and 1 is the identity of
multiplication) plus cancellation laws x+x = 0 and x*x = x are a
sufficient basis to prove all tautologies.

Exercise 1: Verify that the algebraic rules described above are
     sufficient by carrying out calculations verifying the axioms of
     Boolean algebra listed above (suitably translated).  Some of the
     axioms are the same (e.g. associativity and commutativity of
     multiplication correspond to associativity and commutativity of
     conjunction) and some will require work.

If we interpret 0 as true and 1 as false, we get a dual basis using
the biconditional, disjunction, and ``false'' as basic notions.

The interest of this algebraic approach is that it is actually directly
based on the algebra we are familiar with, though in a disguised form.

Exercise 2: An incidental interest of this approach is that it allows
     us to see fairly easily what the meaning of formulas like

     P <+> Q <+> R <+> S


     P <-> Q <-> R <-> S

     will be.  Explain why this is true (hint: the expression with the
     biconditional is best handled using the dual interpretation of +
     and *).

Randall Holmes