Boolean algebras are models of the equational theory of two values; this definition is equivalent to the lattice and ring definitions.
Boolean algebra is a mathematically rich branch of abstract algebra. Stanford Encyclopaedia of Philosophy defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1 (whose interpretation need not be numerical). Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under some operations satisfying certain equations.
Just as there are basic examples of groups, such as the group of integers and the symmetric group of permutations of objects, there are also basic examples of Boolean algebras such as the following. The algebra of binary digits or bits 0 and 1 under the logical operations including disjunction, conjunction, and negation. Applications include the propositional calculus and the theory of digital circuits. The algebra of sets under the set operations including union, intersection, and complement. Applications are far-reaching because set theory is the standard foundations of mathematics. Boolean algebra thus permits applying the methods of abstract algebra to mathematical logic and digital logic.
Unlike groups of finite order, which exhibit complexity and diversity and whose first-order theory is decidable only in special cases, all finite Boolean algebras share the same theorems and have a decidable first-order theory. Instead, the intricacies of Boolean algebra are divided between the structure of infinite algebras and the algorithmic complexity of their syntactic structure.
Definition Boolean algebra treats the equational theory of the maximal two-element finitary algebra, called the Boolean prototype, and the models of that theory, called Boolean algebras. These terms are defined as follows.
An algebra is a family of operations on a set, called the underlying set of the algebra. We take the underlying set of the Boolean prototype to be {0,1}.
An algebra is finitary when each of its operations takes only finitely many arguments. For the prototype each argument of an operation is either or , as is the result of the operation. The maximal such algebra consists of all finitary operations on {0,1}.
The number of arguments taken by each operation is called the arity of the operation. An operation on {0,1} of arity , or -ary operation, can be applied to any of possible values for its arguments. For each choice of arguments, the operation may return or , whence there are -ary operations.
The prototype therefore has two operations taking no arguments, called zeroary or nullary operations, namely zero and one. It has four unary operations, two of which are constant operations, another is the identity, and the most commonly used one, called negation, returns the opposite of its argument: if , if . It has sixteen binary operations; again two of these are constant, another returns its first argument, yet another returns its second, one is called conjunction and returns 1 if both arguments are 1 and otherwise 0, another is called disjunction and returns 0 if both arguments are 0 and otherwise 1, and so on. The number of -ary operations in the prototype is the square of the number of -ary operations, so there are ternary operations, quaternary operations, and so on.
A family is indexed by an index set. In the case of a family of operations forming an algebra, the indices are called operation symbols, constituting the language of that algebra. The operation indexed by each symbol is called the denotation or interpretation of that symbol. Each operation symbol specifies the arity of its interpretation, whence all possible interpretations of a symbol have the same arity. In general it is possible for an algebra to interpret distinct symbols with the same operation, but this is not the case for the prototype, whose symbols are in one-one correspondence with its operations. The prototype therefore has -ary operation symbols, called the Boolean operation symbols and forming the language of Boolean algebra. Only a few operations have conventional symbols, such as for negation, for conjunction, and for disjunction. It is convenient to consider the -th -ary symbol to be as done below in the section on truth tables.
An equational theory in a given language consists of equations between terms built up from variables using symbols of that language. Typical equations in the language of Boolean algebra are , , , and .
An algebra satisfies an equation when the equation holds for all possible values of its variables in that algebra when the operation symbols are interpreted as specified by that algebra. The laws of Boolean algebra are the equations in the language of Boolean algebra satisfied by the prototype. The first three of the above examples are Boolean laws, but not the fourth since .
The equational theory of an algebra is the set of all equations satisfied by the algebra. The laws of Boolean algebra therefore constitute the equational theory of the Boolean prototype.
A model of a theory is an algebra interpreting the operation symbols in the language of the theory and satisfying the equations of the theory. A Boolean algebra is any model of the laws of Boolean algebra.
That is, a Boolean algebra is a set and a family of operations thereon interpreting the Boolean operation symbols and satisfying the same laws as the Boolean prototype.
If we define a homologue of an algebra to be a model of the equational theory of that algebra, then a Boolean algebra can be defined as any homologue of the prototype.
Example 1. The Boolean prototype is a Boolean algebra, since trivially it satisfies its own laws. It is thus the prototypical Boolean algebra. We did not call it that initially in order to avoid any appearance of circularity in the definition.
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 in the lattice basis, and multiplication in the ring basis. The distinction is only terminological. The lattice basis has the further operations of join, , and complement, . The ring basis has instead the arithmetic operation 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 to the ring basis as , and as . Conversely the ring basis translates to the lattice basis as .
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 and , called a complemented distributive lattice. The ring basis turns a Boolean algebra into a Boolean ring, namely a ring satisfying .
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. but not ; self-dual, so that complementing all inputs complements the output, as with , or the median operator , 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.
Truth tables The finitary operations on {0,1} may be exhibited as truth tables, thinking of 0 and 1 as the truth values false and true. They can be laid out in a uniform and application-independent way that allows us to name, or at least number, them individually. These names provide a convenient shorthand for the Boolean operations. The names of the -ary operations are binary numbers of bits. There being such operations, one cannot ask for a more succinct nomenclature. Note that each finitary operation can be called a switching function.
This layout and associated naming of operations is illustrated here in full for arities from 0 to 2.
+ Truth tables for the Boolean operations of arity up to 2+ Constants0 1+ Unary operations00 1 0 110 0 1 1+ Binary operations000 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1100 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1010 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1110 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
These tables continue at higher arities, with rows at arity , each row giving a valuation or binding of the variables and each column headed giving the value of the -th -ary operation at that valuation. The operations include the variables, for example is while is (as two copies of its unary counterpart) and is (with no unary counterpart). Negation or complement appears as and again as , along with (, which did not appear at arity 1), disjunction or union as , conjunction or intersection as , implication , exclusive-or symmetric difference as , set difference as , and so on.
As a minor detail important more for its form than its content, the operations of an algebra are traditionally organized as a list. Although we are here indexing the operations of a Boolean algebra by the finitary operations on {0,1}, the truth-table presentation above serendipitously orders the operations first by arity and second by the layout of the tables for each arity. This permits organizing the set of all Boolean operations in the traditional list format. The list order for the operations of a given arity is determined by the following two rules.
(i) The -th row in the left half of the table is the binary representation of with its least significant or -th bit on the left ("little-endian" order, originally proposed by Alan Turing, so it would not be unreasonable to call it Turing order).