# Boolean algebra (structure): Map

### Map showing all locations mentioned on Wikipedia article:

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets.

## History

The term "Boolean algebra" honors George Boole (1815–1864), a self-educated English mathematician. He introduced the algebraic system initially in a small pamphlet, The Mathematical Analysis of Logic, published in 1847 in response to an ongoing public controversy between Augustus De Morgan and William Hamilton, and later as a more substantial book, The Laws of Thought, published in 1854. Boole's formulation differs from that described above in some important respects. For example, conjunction and disjunction in Boole were not a dual pair of operations. Boolean algebra emerged in the 1860s, in papers written by William Jevons and Charles Sanders Peirce. To the 1890 Vorlesungen of Ernst Schröder the first systematic presentation of Boolean algebra and distributive lattices is owed. The first extensive treatment of Boolean algebra in English is A. N. Whitehead's 1898 Universal Algebra. Boolean algebra as an axiomatic algebraic structure in the modern axiomatic sense begins with a 1904 paper by Edward Vermilye Huntington. Boolean algebra came of age as serious mathematics with the work of Marshall Stone in the 1930s, and with Garrett Birkhoff's 1940 Lattice Theory. In the 1960s, Paul Cohen, Dana Scott, and others found deep new results in mathematical logic and axiomatic set theory using offshoots of Boolean algebra, namely forcing and Boolean-valued models.

## Definition

A Boolean algebra is a six-tuple consisting of a set A, equipped with two binary operations \land (called "meet" or "and"), \lor (called "join" or "or"), a unary operation \lnot (called "complement" or "not") and two elements 0 and 1 (sometimes denoted by \bot and \top), such that for all elements a, b and c of A, the following axioms hold:

A Boolean algebra with only one element is called a trivial Boolean algebraor a degenerate Boolean algebra. (Some authors require 0 and 1 to be distinctelements in order to exclude this case.)

It follows from the first three pairs of axioms above (associativity, commutativity and absorption) that
:a = a \land b     if and only if     a \lor b = b.
The relation ≤ defined by abif and only if the above equivalent conditions hold, is a partial orderwith least element 0 and greatest element 1. The meet a \land bor the join a \lor bof two elements coincides with their infimumor supremum, respectively, with respect to ≤.

As in every lattice, the relations \landand \lorsatisfy the first three pairs of axioms above; the fourth pair is just distributivity. Since the complements in a distributive lattice are unique, to define the involution\negit suffices to define {\neg}aas the complement of a.

The set of axioms is self-dualin the sense that if one exchanges \lorwith \landand 0 with 1 in an axiom, the result is again an axiom. Therefore by applying this operation to a Boolean algebra (or Boolean lattice), one obtains another Boolean algebra with the same elements; it is called its dual.

## Examples

• The simplest non-trivial Boolean algebra has only two elements, 0 and 1, and is defined by the rules:
a \lor (b \lor c) = (a \lor b) \lor c
a \land (b \land c) = (a \land b) \land c
associativity
a \lor b = b \lor a
a \land b = b \land a
commutativity
a \lor (a \land b) = a
a \land (a \lor b) = a
absorption
a \lor (b \land c) = (a \lor b) \land (a \lor c)
a \land (b \lor c) = (a \land b) \lor (a \land c)
distributivity
a \lor {\neg}a = 1
a \land {\neg}a = 0
complements
\land 0 1
0
0 0
1
0 1
\lor 0 1
0
0 1
1
1 1

* It has applications in logic, interpreting 0 as false, 1 as true, \land as and, \lor as or, and \neg as not. Expressions involving variables and the Boolean operations represent statement forms, and two such expressions can be shown to be equal using the above axioms if and only if the corresponding statement forms are logically equivalent.

* The two-element Boolean algebra is also used for circuit design in electrical engineering; here 0 and 1 represent the two different states of one bit in a digital circuit, typically high and low voltage. Circuits are described by expressions containing variables, and two such expressions are equal for all values of the variables if and only if the corresponding circuits have the same input-output behavior. Furthermore, every possible input-output behavior can be modeled by a suitable Boolean expression.

* The two-element Boolean algebra is also important in the general theory of Boolean algebras, because an equation involving several variables is generally true in all Boolean algebras if and only if it is true in the two-element Boolean algebra (which can be checked by a trivial brute force algorithm for small numbers of variables). This can for example be used to show that the following laws (Consensus theorems) are generally valid in all Boolean algebras:
** (a \lor b) \land ({\neg}a \lor c) \land (b \lor c) \equiv (a \lor b) \land ({\neg}a \lor c)
** (a \land b) \lor ({\neg}a \land c) \lor (b \land c) \equiv (a \land b) \lor ({\neg}a \land c)

• The power set (set of all subsets) of any given nonempty set S forms a Boolean algebra with the two operations \lor := \cup (union) and \land := \cap (intersection). The smallest element 0 is the empty set and the largest element 1 is the set S itself.

• The set of all subsets of S that are either finite or cofinite is a Boolean algebra.

• Starting with the propositional calculus with κ sentence symbols, form the Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo tautology). This construction yields a Boolean algebra. It is in fact the free Boolean algebra on κ generators. A truth assignment in propositional calculus is then a Boolean algebra homomorphism from this algebra to {0,1}.

• Given any linearly ordered set with a least element, the interval algebra is the smallest algebra of subsets of L containing all of the half-open intervals [a, b) such that a is in L and b in either in L or equal to ∞. Interval algebras are useful in the study of Lindenbaum-Tarski algebras; every countable BA is isomorphic to an interval algebra.

• For any natural number n, the set of all positive divisors of n forms a distributive lattice if we write ab for a | b. This lattice is a Boolean algebra if and only if n is square-free. The smallest element 0 of this Boolean algebra is the natural number 1; the largest element 1 of this Boolean algebra is the natural number n.

• Other examples of Boolean algebras arise from topological spaces: if X is a topological space, then the collection of all subsets of X which are both open and closed forms a Boolean algebra with the operations \lor := \cup (union) and \land := \cap (intersection).

• If R is an arbitrary ring and we define the set of central idempotents by
A = { eR : e2 = e, ex = xe, ∀xR }
then the set A becomes a Boolean algebra with the operations e \lor f := e + f - ef and e \land f := ef.

## Homomorphisms and isomorphisms

A homomorphismbetween two Boolean algebras Aand Bis a functionf: ABsuch that for all a, bin A:

f(a \lor b) = f(a) \lor f(b)
f(a \land b) = f(a) \land f(b)
f(0) = 0\,
f(1) = 1.\,

It then follows that f({\neg}a) = {\neg}f(a)for all ain Aas well. The classof all Boolean algebras, together with this notion of morphism, forms a full subcategoryof the categoryof lattices.

A homomorphism is called a monomorphism, epimorphismor isomorphismif it is injective, surjectiveor bijective, respectively. The inverse map of an isomorphism is also an isomorphism.

## Boolean rings, ideals and filters

Every Boolean algebra (A, \land, \lor)gives rise to a ring(A, +, *) by defining a + b = (a \land {\neg}b) \lor (b \land {\neg}a)(this operation is called symmetric differencein the case of sets and XORin the case of logic) and a * b = a \land b. The zero element of this ring coincides with the 0 of the Boolean algebra; the multiplicative identity element of the ring is the 1 of the Boolean algebra. This ring has the property that a* a= afor all ain A; rings with this property are called Boolean rings.

Conversely, if a Boolean ring Ais given, we can turn it into a Boolean algebra by defining x \lor y = x + y + xyand x \land y = xy. Since these two constructions are inverses of each other, we can say that every Boolean ring arises from a Boolean algebra, and vice versa. Furthermore, a map f: ABis a homomorphism of Boolean algebras if and only if it is a homomorphism of Boolean rings. The categoriesof Boolean rings and Boolean algebras are equivalent.

An idealof the Boolean algebra Ais a subset Isuch that for all x, yin Iwe have x \lor yin Iand for all ain Awe have a \land xin I. This notion of ideal coincides with the notion of ring idealin the Boolean ring A. An ideal Iof Ais called primeif IAand if a \land bin Ialways implies ain Ior bin I. An ideal Iof Ais called maximalif IAand if the only ideal properly containing Iis Aitself. These notions coincide with ring theoretic ones of prime idealand maximal idealin the Boolean ring A.

The dual of an idealis a filter. A filterof the Boolean algebra Ais a subset psuch that for all x, yin pwe have x \land yin pand for all ain Awe have a \lor xin p.

## Representing Boolean algebras

It can be shown that every finiteBoolean algebra is isomorphic to the Boolean algebra of all subsets of a finite set. Therefore, the number of elements of every finite Boolean algebra is a power of two.

Stone'scelebrated representation theorem for Boolean algebrasstates that everyBoolean algebra Ais isomorphic to the Boolean algebra of all clopensets in some (compacttotally disconnectedHausdorff) topological space.

## Axiomatics for Boolean algebras

In 1933, the American mathematician Edward Vermilye Huntington(1874–1952) set out the following elegant axiomatization for Boolean algebra. It requires just one binary operation + and a unary functional symboln, to be read as 'complement', which satisfy the following laws:

1. Commutativity: x + y = y + x.
2. Associativity: (x + y) + z = x + (y + z).
3. Huntington equation: n(n(x) + y) + n(n(x) + n(y)) = x.

Herbert Robbinsimmediately asked: If the Huntington equation is replaced with its dual, to wit:

4. Robbins Equation: n(n(x + y) + n(x + n(y))) = x,

do (1), (2), and (4) form a basis for Boolean algebra? Calling (1), (2), and (4) a Robbins algebra, the question then becomes: Is every Robbins algebra a Boolean algebra? This question (which came to be known as the Robbins conjecture) remained open for decades, and became a favorite question of Alfred Tarskiand his students.

In 1996, William McCune at Argonne National Laboratory, building on earlier work by Larry Wos, Steve Winker, and Bob Veroff, answered Robbins's question in the affirmative: Every Robbins algebra is a Boolean algebra.Crucial to McCune's proof was the automated reasoning programEQPhe designed. For a simplification of McCune's proof, see Dahn (1998).

## Generalizations

Removing the requirement of existence of a unit from the axioms of Boolean algebra yields "generalized Boolean algebras". Formally, a distributive latticeBis a generalized Boolean lattice, if it has a smallest element 0 and for any elements aand bin Bsuch that ab, there exists an element xsuch that a \land x = 0and a \lor x = b. Defining a\setminus bas the unique xsuch that (a \land b) \lor x = aand (a \land b) \land x = 0, we say that the structure (B,\land,\lor,\setminus,0)is a generalized Boolean algebra, while (B,\lor,0)is a generalized Boolean semilattice. Generalized Boolean lattices are exactly the idealsof Boolean lattices.

A structure that satisfies all axioms for Boolean algebras except the two distributivity axioms is called an orthocomplemented lattice. Orthocomplemented lattices arise naturally in quantum logicas lattices of closed subspaces for separable Hilbert spaces.

## References

• . See Section 2.5.
• . See Chapter 2.
• .
• .
• .
• .
• .
• .
• .
• . In 3 volumes. (Vol.1:ISBN 978-0-444-70261-6, Vol.2:ISBN 978-0-444-87152-7, Vol.3:ISBN 978-0-444-87153-4)
• . Reprinted by Dover Publications, 1979.