We know there are 16 possible binary logic functions:
A=0 A=0 A=1 A=1
B=0 B=1 B=0 B=1
------------------------------------
0 0 0 0 ZERO
0 0 0 1 AND
0 0 1 0 ANDNOT
0 0 1 1 A
0 1 0 0 NOT-A-AND-B (whatever...)
0 1 0 1 B
0 1 1 0 XOR
0 1 1 1 OR
1 0 0 0 NOR
1 0 0 1 XNOR
1 0 1 0 NOT-B
1 0 1 1 ORNOT
1 1 0 0 NOT-A
1 1 0 1 IMPLIES
1 1 1 0 NAND
1 1 1 1 ONE
As is well known, all sixteen functions can be described using only NAND, and all sixteen functions can be described using only NOR. But these are the only two such functions that are "universal."
This has always struck me as a very interesting asymmetry. Why NAND and NOR but not AND and OR? Why are these two special? When all sixteen functions are numbered from 0..15 in the order above, NOR and NAND are numbers 8 and 14, neither at the beginning nor end of the list, nor right in the middle; they seem to hold arbitrary positions in the list.
Is there any underlying (simpler) concept that would motivate that these two particular functions are special in this way? Or is it just one of those things that has no motivating underlying explanation?
For universality, you needto be able to produce $1$ even when all inputs are $0$, hence $0\circ 0=1$. Similarly, $1\circ1=0$. This leaves us with only four functions. Two of these ($\neg A$ and $\neg B$) are in fact unary, so indeed only NAND and NOR remain.