1. Prove the validity of the following laws of Boolean logic:

   	x + 1 = 1
   	x 0 = 0

   using only the five axioms of Boolean algebra.

   Extra credit -- prove this law, also using only the axioms of Boolean algebra:

   x (yz) = (xy) z

    

2. Consider this digital circuit with feedback (sorry for the lousy drawing):
   
        ----------
       | ____     |
       --\   \    |
          |OR >---+--> X
   A ----/___/
   
   Write down the Boolean equations that describe this circuit, and determine how many stable states it has, written out as a truth table. 
   Then do the same for each of these two circuits:
          ___
   A ----|   \
         |AND |---+--> X
       --|___/    |
       |__   _____|
          \ /
           X
        __/ \_____
       |          |
       | ____     |
       --\    \   |
          |OR >---+--> Y
   B ----/___/
   
              /|
        --o<NOT|--
       |      \|  |
       | ____     |
       --\   \    |
          |OR >---+--> Y
   X ----/___/
    
    
3. Download this Haskell code, and rename the file Circuits.lhs.  You should then open the file with a text editor and do Exercises 1.1 through 1.5.  You will also have to load the module into GHCi to test your programs.

1. Closure under + and * operations.
2. Unit axiom (0 for + and 1 for *).
3. Commutation.
4. Distribution.
5. Inverse

(I could have called 2 the "Unit property," but the point of the axiom is
_the existence_ of a unit such that it has that property.)

3.
Lemma 0 (idempotence)
xx = x
(Proved in class.)
Proof
xx = xx + 0 = xx + xx' = x(x + x') = x1 = x

Lemma 1 (absorption, +)
x + xy = x
Proof
  x + xy
= x1 + xy    (unit axiom)
= x(1 + y)   (distribution)
= x1         (unit theorem)
= x

Lemma 2 (absorption, *)
x(x + y) = x
Proof
  x(x + y)
= (x + 0)(x + y)    (unit axiom)
= x + 0y            (distribution)
= x                 (unit theorem)

Lemma 3:
x + (xy)z = x
Proof
  x + (xy)z
= (x + xy)(x + z)    (commutation, distribution)
= x(x + z)           (absorption)
= xx + xz            (distribution)
= x + xz             (idempotence)
= x                  (absorption)

Theorem (association)
x(yz) = (xy)z

Proof:
  x(yz)
= x((y + (xy)z)z)            (lemma 3)
= x((y + (xy)z)(z + (xy)z))  (absorption, commutation)
= x(yz + (xy)z)              (commutation, distribution)
= (x + (xy)z)(yz + (xy)z)    (lemma 3)
= x(yz) + (xy)z              (commutation, distribution)
= (xy + x(yz))(z + x(yz))    (distribution, commutation)
= (xy + x(yz))z              (lemma 3)
= ((x + x(yz))(y + x(yz)))z  (commutation, distribution)
= (x(y + x(yz)))z            (absorption)
= (xy)z                      (lemma 3)