Complete Boolean algebra

A complete boolean algebra is a collection of boolean operaters which 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 NOR (a not-gate can be simulated in this set by tying both inputs of a NAND or NOR to one signal, and AND and OR by appending one of these to undo the negation).