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.
Contents |
A Boolean algebra is a six-tuple consisting of a set A, equipped with two binary operations (called "meet" or "and"),
(called "join" or "or"), a unary operation
(called "complement" or "not") and two elements 0 and 1 (sometimes denoted by ⊥ and
), such that for all elements a, b and c of A, the following axioms hold:
a ∨ (b ∨ c) = (a ∨ b) ∨ c | a ∧ (b ∧ c) = (a ∧ b) ∧ c | associativity |
a ∨ b = b ∨ a | a ∧ b = b ∧ a | commutativity |
a ∨ (a ∧ b) = a | a ∧ (a ∨ b) = a | absorption |
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) | a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) | distributivity |
a ∨ ¬a = 1 | a ∧ ¬a = 0 | complements |
A Boolean algebra with only one element is called a trivial Boolean algebra or a degenerate Boolean algebra. (Some authors require 0 and 1 to be distinct elements in order to exclude this case.)
It follows from the first three pairs of axioms above (associativity, commutativity and absorption) that
The relation ≤ defined by a ≤ b if and only if the above equivalent conditions hold, is a partial order with least element 0 and greatest element 1. The meet a ∧ b or the join a ∨ b of two elements coincides with their infimum or supremum, respectively, with respect to ≤.
As in every lattice, the relations ∧ and ∨ satisfy 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 ¬ it suffices to define ¬a as the complement of a.
The set of axioms is self-dual in the sense that if one exchanges ∨ with ∧ and 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.
|
|
|
A homomorphism between two Boolean algebras A and B is a function f : A → B such that for all a, b in A:
It then follows that f(¬a) = ¬f(a) for all a in A as well. The class of all Boolean algebras, together with this notion of morphism, forms a full subcategory of the category of lattices.
A homomorphism is called a monomorphism, epimorphism or isomorphism if it is injective, surjective or bijective, respectively. The inverse map of an isomorphism is also an isomorphism.
Every Boolean algebra (A, ,
) gives rise to a ring (A, +, *) by defining a + b = (a
¬b)
(b
¬a) (this operation is called symmetric difference in the case of sets and XOR in the case of logic) and a * b = a
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 = a for all a in A; rings with this property are called Boolean rings.
Conversely, if a Boolean ring A is given, we can turn it into a Boolean algebra by defining x y = x + y - xy and x
y = xy. Since these two operations are inverses of each other, we can say that every Boolean ring arises from a Boolean algebra, and vice versa. Furthermore, a map f : A → B is a homomorphism of Boolean algebras if and only if it is a homomorphism of Boolean rings. The categories of Boolean rings and Boolean algebras are equivalent.
An ideal of the Boolean algebra A is a subset I such that for all x, y in I we have x y in I and for all a in A we have a
x in I. This notion of ideal coincides with the notion of ring ideal in the Boolean ring A. An ideal I of A is called prime if I ≠ A and if a
b in I always implies a in I or b in I. An ideal I of A is called maximal if I ≠ A and if the only ideal properly containing I is A itself. These notions coincide with ring theoretic ones of prime ideal and maximal ideal in the Boolean ring A.
The dual of an ideal is a filter. A filter of the Boolean algebra A is a subset p such that for all x, y in p we have x y in p and for all a in A if a
x = a then a in p.
It can be shown that every finite Boolean 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's celebrated representation theorem for Boolean algebras states that every Boolean algebra A is isomorphic to the Boolean algebra of all clopen sets in some (compact totally disconnected Hausdorff) topological space.
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 symbol n, to be read as 'complement', which satisfy the following laws:
Herbert Robbins immediately asked: If the Huntington equation is replaced with its dual, to wit:
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 Tarski and 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 program EQP he designed. For a simplification of McCune's proof, see Dahn (1998).
Removing the requirement of existence of a unit from the axioms of Boolean algebra yields "generalized Boolean algebras". Formally, a distributive lattice B is a generalized Boolean lattice, if it has a smallest element 0 and for any elements a and b in B such that a ≤ b, there exists an element x such that and
. Defining
as the unique x such that
and
, we say that the structure
is a generalized Boolean algebra, while
is a generalized Boolean semilattice. Generalized Boolean lattices are exactly the ideals of 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 logic as lattices of closed subspaces for separable Hilbert spaces.
The term "Boolean algebra" honors George Boole (1815–1864), a self-educated English mathematician. He introduced the algebraic system of logic 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 Peirce. To the 1890 Vorlesungen of Ernst Schröder we owe the first systematic presentation of Boolean algebra and distributive lattices. 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.
|
|
|
A monograph available free online: