Originally Posted by

**steve_bank**
Any logic function can be implemented by AND-OR or NAND-NOR. logic.

Crisp logic, at least.

However, one needs a NOT function to do so. I will prove that by finding out what happens when one only has AND and OR.

Each of those two operators is both commutative and associative, so that one can easily define multiple-argument versions of them. Also, both operators are idempotent, meaning that one can collapse repetitions of an argument to a single copy of it.

They are also monotone, meaning that (x <= y) <-> (AND(x,z) <= AND(y,z)) and (OR(x,z) <= OR(y,z)). This has the consequence that every combination is monotone, and also that every combination is bounded from below by AND(all its args) and from above by OR(all its args).

Thus, every combination of AND's and OR's returns 0 for all-0 args and 1 for all-1 args. So to get 0 for all-1's and 1 for all-0's, one needs a NOT operator. That is also true for violations of monotonicity, like X(0,others) = 1 while X(1,others) = 0.

But if one has a NAND or a NOR operator, one can get a NOT out of it with NOT(x) = NAND(x,x) = NOR(x,x), using the idempotence of AND and OR. NOT with NAND gives AND, and with DeMorgan's rules, OR, and with further negation, NOR. Likewise, one can get OR, AND, and NAND from NOR.

In fact, one can get any truth table with combinations of NOT, AND, and OR.