Universal sets of elementary functions. A set of elementary functions is universal if every boolean function can be implemented with a circuit that uses only functions from that set. The...

Universal sets of elementary functions. A set of elementary functions is universal if every boolean function can be implemented with a circuit that uses only functions from that set. The sum-of-products construction in the text shows that {AND, OR, NOT} is universal (as does the product-of-sums construction in Exercise 7.1.9). Acknowledging that NOT has just one argument and assuming that all other functions mentioned have two arguments, show that all but one of the following sets of functions are universal, and prove that the exceptional set is not universal.

a. NOT and AND

b. NOR

c. NAND

d. AND and OR

e. NOT and OR

f. AND and XOR

Exercise 7.1.9

Show that every boolean function can be expressed as a product of sums that involve each input or its negation, as in the example in the previous exercise. Of course, this is known as the product-of-sums representation.