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 or 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 *).