Complete set of Boolean operators

In computer science, a complete Boolean algebra is a collection of Boolean operators that permits the realisation of any possible truth table.

Example truth table (Xor):

a	b	Result
0	0	0
0	1	1
1	0	1
1	1	0

Using a complete Boolean algebra which does not include XOR (such as the well-known AND OR NOT set), this function can be realised as follows:

(a or b) and not (a and b).

However, other complete Boolean algebras are possible, such as NAND or NOR (either gate can form a complete Boolean algebra by itself - the proof is detailed on their pages).

Note that just because a set of gates forms a complete Boolean algebra does not mean that the resulting expressions will be simple. To gain an XOR function using only NAND gates, for example, is a fairly complex expression - the important thing is that it exists.