12.3.1 Give a truth table for each of the Boolean functions denoted by the following ex- pressions:

(a) p AND (p OR q)

(b)   NOT p OR q

(c)  (p AND q) OR ( NOT p AND  NOT q)

12.4.2 Give a truth table for each of the Boolean functions denoted by the following ex- pressions:

(a)  (p → q) = ( NOT p OR q)

(b) p → q → (r OR NOT p)

(c)  (p OR q) → (p AND q)

(d)  (p AND q) → (p OR q)

12.4.7 The binary exclusive-or function, ⊕ , is defined to have value TRUE if and only if exactly one of its arguments are TRUE. Draw the truth table for ⊕ .

12.x.x  How many binary (two-argument) Boolean functions are there?  Justify your an- swer. Draw the truth tables for the ones not discussed in class or in this homework. Do any of them have intuitive interpretations?

12.7.x Translate each of the following expressions from “shorthand” notation to the full Boolean expression syntax:

(a) pqr → p + q

(b)  ((p → q)(q → r)) → (p → r)

(c)  (p → q) → p

(d)  (p = (q + r)) → (q(¯) → pr)

12.7.1 Which of the expressions from the previous questions are tautologies?

12.8.1  How would you check whether any of the laws from FOCS Section 12.8 are tau- tologies? Do it for some or all of the laws.

12.8.9  Prove law 12.24(b) by substituting expressions into previous laws:

(p1p2 ··· pn → q) = (¯p1 + ¯p2 + ··· + ¯pn + q)               (12.24(b))