A set of operators is called complete if all functions {0, 1}n 7→ {0, 1} can be constructed by

means of the given operators.

a) Show that {∧,¬} containing conjunction and negation is complete.

b) Show that {↓} which only includes the Peirce function (NOR) is complete.

c) Show that {|} which just contains the Sheffer function (NAND) is complete.

d) Show that {→,¬} containing implication and negation is complete.

e) Why are the following sets of operators not complete?

i) {∧}

ii) {∨}

iii) {→}