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 showsby induction on formulasthat for any formula A and two valuations f1 <= f2, f1(A) <= f2(A). Therefore, negation is not expressible by any formula.