1.

A) Prove the following algebraic statements using truth tables. A xor B = AB + AB (where A denotes complement of A) A xnor B = AB + AB

B) Using De Morgans theorems and idempotency, show that

a. Each of the logic gates can be fully expressed using only nand gates.

b. Each of the logic gates can be fully expressed using only nor gates.

c. Do NOT submit any answer for this part: As an added aspect, think about the usefulness and potential issues arising from these relationships. (Note: To be discussed further in the lectures.) C) Prove the following Expansion Theorem in two dual forms (due to Claude Shannon) using only the postulates/axioms of Boolean Set Theory.

A. f(x1, , xk, , xN) = xk .f(x1, , 1, , xN) + xk.f(x1, , 0, , xN)

B. f(x1, , xk, , xN) = [xk + f(x1, , 0, , xN)] . [xk + f(x1, , 1, , xN)] Hint: Dont try to prove the general case, consider base cases and work from there, using substitution and other tricks.