Boolean Algebras Canonically Defined - Basis

The operations need not be all explicitly stated. A basis is any set from which the remaining operations can be obtained by composition. A "Boolean algebra" may be defined from any of several different bases. Three bases for Boolean algebra are in common use, the lattice basis, the ring basis, and the Sheffer stroke or NAND basis. These bases impart respectively a logical, an arithmetical, and a parsimonious character to the subject.

• The lattice basis originated in the 19th century with the work of Boole, Peirce, and others seeking an algebraic formalization of logical thought processes.
• The ring basis emerged in the 20th century with the work of Zhegalkin and Stone and became the basis of choice for algebraists coming to the subject from a background in abstract algebra. Most treatments of Boolean algebra assume the lattice basis, a notable exception being Halmos whose linear algebra background evidently endeared the ring basis to him.
• Since all finitary operations on {0,1} can be defined in terms of the Sheffer stroke NAND (or its dual NOR), the resulting economical basis has become the basis of choice for analyzing digital circuits, in particular gate arrays in digital electronics.

The common elements of the lattice and ring bases are the constants 0 and 1, and an associative commutative binary operation, called meet x∧y in the lattice basis, and multiplication xy in the ring basis. The distinction is only terminological. The lattice basis has the further operations of join, x∨y, and complement, ¬x. The ring basis has instead the arithmetic operation x⊕y of addition (the symbol ⊕ is used in preference to + because the latter is sometimes given the Boolean reading of join).

To be a basis is to yield all other operations by composition, whence any two bases must be intertranslatable. The lattice basis translates x∨y to the ring basis as x⊕y⊕xy, and ¬x as x⊕1. Conversely the ring basis translates x⊕y to the lattice basis as (x∨y)∧¬(x∧y).

Both of these bases allow Boolean algebras to be defined via a subset of the equational properties of the Boolean operations. For the lattice basis, it suffices to define a Boolean algebra as a distributive lattice satisfying x∧¬x = 0 and x∨¬x = 1, called a complemented distributive lattice. The ring basis turns a Boolean algebra into a Boolean ring, namely a ring satisfying x2 = x.

Emil Post gave a necessary and sufficient condition for a set of operations to be a basis for the nonzeroary Boolean operations. A nontrivial property is one shared by some but not all operations making up a basis. Post listed five nontrivial properties of operations, identifiable with the five Post's classes, each preserved by composition, and showed that a set of operations formed a basis if, for each property, the set contained an operation lacking that property. (The converse of Post's theorem, extending "if" to "if and only if," is the easy observation that a property from among these five holding of every operation in a candidate basis will also hold of every operation formed by composition from that candidate, whence by nontriviality of that property the candidate will fail to be a basis.) Post's five properties are:

• monotone, no 0-1 input transition can cause a 1-0 output transition;
• affine, representable with Zhegalkin polynomials that lack bilinear or higher terms, e.g. x⊕y⊕1 but not xy;
• self-dual, so that complementing all inputs complements the output, as with x, or the median operator xy⊕yz⊕zx, or their negations;
• strict (mapping the all-zeros input to zero);
• costrict (mapping all-ones to one).

The NAND (dually NOR) operation lacks all these, thus forming a basis by itself.