1. ## Not Functionally Complete

Show that each set of gates in not functionally complete.

{AND}

{AND, OR}

While I can picture and understand why these gates are not functionally complete, I don't know how to show this using Boolean expressions (edit: answer does not use any math; only words) My biggest problem is how to start. If I can get the start, I should be able to take it from there.

2. The short answer is that AND and OR are monotonic with respect to the usual ordering on {0, 1}, while NOT is non-monotonic.

For the long answer, one has to define a Boolean formula (or circuit). It is defined inductively.

1. If x is a variable, then it is a formula.
2. If A and B are formulas, then A AND B, as well as A OR B, are formulas.

Then, given a valuation f : V -> {0, 1}, where V is the set of variables, one extends it to formulas as usual, so that f(A) is in {0, 1}.

For two valuations f1, f2 : V -> {0, 1}, write f1 <= f2 if f1(x) <= f2(x) for all x in V.

Then one shows by induction on formulas that for any formula A and two valuations f1 <= f2, f1(A) <= f2(A). Therefore, negation is not expressible by any formula.