Universal sets of gates. A set of gates is universal if every boolean function can be implemented with a circuit that uses only wires and gates from that set. Our sum-of-products circuit construction...

Universal sets of gates. A set of gates is universal if every boolean function can be implemented with a circuit that uses only wires and gates from that set. Our sum-of-products circuit construction shows that generalized multiway gates are universal (which is perhaps not surprising, since there are so many types of gates). Acknowledging that NOT has just one input and assuming that all other gates are available only in two-input versions, show that all but one of the following sets of gates 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