Template:Short description Template:For-multi Template:Use dmy dates 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, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra (with involution).
Every Boolean algebra gives rise to a Boolean ring, and vice versa, with ring multiplication corresponding to conjunction or meet ∧, and ring addition to exclusive disjunction or symmetric difference (not disjunction ∨). However, the theory of Boolean rings has an inherent asymmetry between the two operators, while the axioms and theorems of Boolean algebra express the symmetry of the theory described by the duality principle.Template:Sfn
HistoryEdit
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. The first systematic presentation of Boolean algebra and distributive lattices is owed to the 1890 Vorlesungen of Ernst Schröder. 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 V. 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.
DefinitionEdit
A Boolean algebra is a set Template:Math, equipped with two binary operations Template:Math (called "meet" or "and"), Template:Math (called "join" or "or"), a unary operation Template:Math (called "complement" or "not") and two elements Template:Math and Template:Math in Template:Math (called "bottom" and "top", or "least" and "greatest" element, also denoted by the symbols Template:Math and Template:Math, respectively), such that for all elements Template:Math, Template:Math and Template:Math of Template:Math, the following axioms hold:Template:Sfn
Note, however, that the absorption law and even the associativity law can be excluded from the set of axioms as they can be derived from the other axioms (see Proven properties).
A Boolean algebra with only one element is called a trivial Boolean algebra or a degenerate Boolean algebra. (In older works, some authors required Template:Math and Template:Math to be distinct elements in order to exclude this case.)Template:Citation needed
It follows from the last three pairs of axioms above (identity, distributivity and complements), or from the absorption axiom, that
- Template:Math if and only if Template:Math.
The relation Template:Math defined by Template:Math if these equivalent conditions hold, is a partial order with least element 0 and greatest element 1. The meet Template:Math and the join Template:Math of two elements coincide with their infimum and supremum, respectively, with respect to ≤.
The first four pairs of axioms constitute a definition of a bounded lattice.
It follows from the first five pairs of axioms that any complement is unique.
The set of axioms is self-dual in the sense that if one exchanges Template:Math with Template:Math and Template:Math with Template:Math 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.Template:Sfn
ExamplesEdit
- The simplest non-trivial Boolean algebra, the two-element Boolean algebra, has only two elements, Template:Math and Template:Math, and is defined by the rules:
- It has applications in logic, interpreting Template:Math as false, Template:Math as true, Template:Math as and, Template:Math as or, and Template:Math 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;Template:Refn 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:
- The power set (set of all subsets) of any given nonempty set Template:Math forms a Boolean algebra, an algebra of sets, with the two operations Template:Math (union) and Template:Math (intersection). The smallest element 0 is the empty set and the largest element Template:Math is the set Template:Math itself.
- After the two-element Boolean algebra, the simplest Boolean algebra is that defined by the power set of two atoms:
|
|
|
- The set Template:Mvar of all subsets of Template:Mvar that are either finite or cofinite is a Boolean algebra and an algebra of sets called the finite–cofinite algebra. If Template:Mvar is infinite then the set of all cofinite subsets of Template:Mvar, which is called the Fréchet filter, is a free ultrafilter on Template:Mvar. However, the Fréchet filter is not an ultrafilter on the power set of Template:Mvar.
- Starting with the propositional calculus with Template:Math sentence symbols, form the Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo logical equivalence). This construction yields a Boolean algebra. It is in fact the free Boolean algebra on Template:Math generators. A truth assignment in propositional calculus is then a Boolean algebra homomorphism from this algebra to the two-element Boolean algebra.
- Given any linearly ordered set Template:Math with a least element, the interval algebra is the smallest Boolean algebra of subsets of Template:Math containing all of the half-open intervals Template:Math such that Template:Math is in Template:Math and Template:Math is either in Template:Math or equal to Template:Math. Interval algebras are useful in the study of Lindenbaum–Tarski algebras; every countable Boolean algebra is isomorphic to an interval algebra.
- For any natural number Template:Math, the set of all positive divisors of Template:Math, defining Template:Math if Template:Math divides Template:Math, forms a distributive lattice. This lattice is a Boolean algebra if and only if Template:Math is square-free. The bottom and the top elements of this Boolean algebra are the natural numbers Template:Math and Template:Math, respectively. The complement of Template:Math is given by Template:Math. The meet and the join of Template:Math and Template:Math are given by the greatest common divisor (Template:Math) and the least common multiple (Template:Math) of Template:Math and Template:Math, respectively. The ring addition Template:Math is given by Template:Math. The picture shows an example for Template:Math. As a counter-example, considering the non-square-free Template:Math, the greatest common divisor of 30 and its complement 2 would be 2, while it should be the bottom element 1.
- Other examples of Boolean algebras arise from topological spaces: if Template:Math is a topological space, then the collection of all subsets of Template:Math that are both open and closed forms a Boolean algebra with the operations Template:Math (union) and Template:Math (intersection).
- If Template:Mvar is an arbitrary ring then its set of central idempotents, which is the set
<math display=block>A = \left\{e \in R : e^2 = e \text{ and } ex = xe \; \text{ for all } \; x \in R\right\},</math> becomes a Boolean algebra when its operations are defined by Template:Math and Template:Math.
Homomorphisms and isomorphismsEdit
A homomorphism between two Boolean algebras Template:Math and Template:Math is a function Template:Math such that for all Template:Math, Template:Math in Template:Math:
It then follows that Template:Math for all Template:Math in Template:Math. The class of all Boolean algebras, together with this notion of morphism, forms a full subcategory of the category of lattices.
An isomorphism between two Boolean algebras Template:Math and Template:Math is a homomorphism Template:Math with an inverse homomorphism, that is, a homomorphism Template:Math such that the composition Template:Math is the identity function on Template:Math, and the composition Template:Math is the identity function on Template:Math. A homomorphism of Boolean algebras is an isomorphism if and only if it is bijective.
Boolean ringsEdit
{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Every Boolean algebra Template:Math gives rise to a ring Template:Math by defining Template:Math (this operation is called symmetric difference in the case of sets and XOR in the case of logic) and Template:Math. The zero element of this ring coincides with the 0 of the Boolean algebra; the multiplicative identity element of the ring is the Template:Math of the Boolean algebra. This ring has the property that Template:Math for all Template:Math in Template:Math; rings with this property are called Boolean rings.
Conversely, if a Boolean ring Template:Math is given, we can turn it into a Boolean algebra by defining Template:Math and Template:Math.Template:SfnTemplate:Sfn 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 Template:Math 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;Template:Sfn in fact the categories are isomorphic.
Hsiang (1985) gave a rule-based algorithm to check whether two arbitrary expressions denote the same value in every Boolean ring. More generally, Boudet, Jouannaud, and Schmidt-Schauß (1989) gave an algorithm to solve equations between arbitrary Boolean-ring expressions. Employing the similarity of Boolean rings and Boolean algebras, both algorithms have applications in automated theorem proving.
Ideals and filtersEdit
{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} An ideal of the Boolean algebra Template:Mvar is a nonempty subset Template:Mvar such that for all Template:Mvar, Template:Mvar in Template:Mvar we have Template:Math in Template:Mvar and for all Template:Mvar in Template:Mvar we have Template:Math in Template:Mvar. This notion of ideal coincides with the notion of ring ideal in the Boolean ring Template:Mvar. An ideal Template:Mvar of Template:Mvar is called prime if Template:Math and if Template:Math in Template:Mvar always implies Template:Mvar in Template:Mvar or Template:Mvar in Template:Mvar. Furthermore, for every Template:Math we have that Template:Math, and then if Template:Mvar is prime we have Template:Math or Template:Math for every Template:Math. An ideal Template:Mvar of Template:Mvar is called maximal if Template:Math and if the only ideal properly containing Template:Mvar is Template:Mvar itself. For an ideal Template:Mvar, if Template:Math and Template:Math, then Template:Math or Template:Math is contained in another proper ideal Template:Mvar. Hence, such an Template:Mvar is not maximal, and therefore the notions of prime ideal and maximal ideal are equivalent in Boolean algebras. Moreover, these notions coincide with ring theoretic ones of prime ideal and maximal ideal in the Boolean ring Template:Mvar.
The dual of an ideal is a filter. A filter of the Boolean algebra Template:Mvar is a nonempty subset Template:Mvar such that for all Template:Mvar, Template:Mvar in Template:Mvar we have Template:Math in Template:Mvar and for all Template:Mvar in Template:Mvar we have Template:Math in Template:Mvar. The dual of a maximal (or prime) ideal in a Boolean algebra is ultrafilter. Ultrafilters can alternatively be described as 2-valued morphisms from Template:Mvar to the two-element Boolean algebra. The statement every filter in a Boolean algebra can be extended to an ultrafilter is called the ultrafilter lemma and cannot be proven in Zermelo–Fraenkel set theory (ZF), if ZF is consistent. Within ZF, the ultrafilter lemma is strictly weaker than the axiom of choice. The ultrafilter lemma has many equivalent formulations: every Boolean algebra has an ultrafilter, every ideal in a Boolean algebra can be extended to a prime ideal, etc.
RepresentationsEdit
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 Template:Math is isomorphic to the Boolean algebra of all clopen sets in some (compact totally disconnected Hausdorff) topological space.
AxiomaticsEdit
| Proven properties | ||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
UId2 [dual] If x ∧ i = x for all x, then i = 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
Idm2 [dual] x ∧ x = x | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
Bnd2 [dual] x ∧ 0 = 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
Abs2 [dual] x ∧ (x ∨ y) = x | |||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
|
A2 [dual] x ∧ (¬x ∧ y) = 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
B2 [dual] (x ∧ y) ∧ (¬x ∨ ¬y) = 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
C2 [dual] (x ∧ y) ∨ (¬x ∨ ¬y) = 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
DMg2 [dual] ¬(x ∧ y) = ¬x ∨ ¬y | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
D2 [dual] (x∧(y∧z)) ∧ ¬x = 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
E2 [dual] y ∨ (x∧(y∧z)) = y | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
F2 [dual] (x∧(y∧z)) ∧ ¬y = 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
G2 [dual] (x∧(y∧z)) ∧ ¬z = 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
H2 [dual] ¬((x∧y)∧z) ∨ x = 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
I2 [dual] ¬((x∧y)∧z) ∨ y = 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
J2 [dual] ¬((x∧y)∧z) ∨ z = 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
K2 [dual] (x ∧ (y ∧ z)) ∧ ¬((x ∧ y) ∧ z) = 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
L2 [dual] (x ∧ (y ∧ z)) ∨ ¬((x ∧ y) ∧ z) = 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
Ass2 [dual] x ∧ (y ∧ z) = (x ∧ y) ∧ z | |||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
| Huntington 1904 Boolean algebra axioms | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Idn1 | x ∨ 0 = x | Idn2 | x ∧ 1 = x | ||||||||||
| Cmm1 | x ∨ y = y ∨ x | Cmm2 | x ∧ y = y ∧ x | ||||||||||
| Dst1 | x ∨ (y∧z) = (x∨y) ∧ (x∨z) | Dst2 | x ∧ (y∨z) = (x∧y) ∨ (x∧z) | ||||||||||
| Cpl1 | x ∨ ¬x = 1 | Cpl2 | x ∧ ¬x = 0 | ||||||||||
| |||||||||||||
The first axiomatization of Boolean lattices/algebras in general was given by the English philosopher and mathematician Alfred North Whitehead in 1898.Template:SfnTemplate:Sfn It included the above axioms and additionally Template:Math and Template:Math. In 1904, the American mathematician Edward V. Huntington (1874–1952) gave probably the most parsimonious axiomatization based on Template:Math, Template:Math, Template:Math, even proving the associativity laws (see box).Template:Sfn He also proved that these axioms are independent of each other.Template:Sfn In 1933, Huntington set out the following elegant axiomatization for Boolean algebra.Template:Sfn It requires just one binary operation Template:Math and a unary functional symbol Template:Math, to be read as 'complement', which satisfy the following laws: Template:Olist Herbert Robbins immediately asked: If the Huntington equation is replaced with its dual, to wit: Template:Olist 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 computer program EQP he designed. For a simplification of McCune's proof, see Dahn (1998).
Further work has been done for reducing the number of axioms; see Minimal axioms for Boolean algebra.
GeneralizationsEdit
Template:Algebraic structures Removing the requirement of existence of a unit from the axioms of Boolean algebra yields "generalized Boolean algebras". Formally, a distributive lattice Template:Math is a generalized Boolean lattice, if it has a smallest element Template:Math and for any elements Template:Math and Template:Math in Template:Math such that Template:Math, there exists an element Template:Math such that Template:Math and Template:Math. Defining Template:Math as the unique Template:Math such that Template:Math and Template:Math, we say that the structure Template:Math is a generalized Boolean algebra, while Template:Math 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 linear subspaces for separable Hilbert spaces.
See alsoEdit
NotesEdit
ReferencesEdit
Works citedEdit
- Template:Cite book
- Template:Citation
- Template:Citation.
- Template:Citation
- Template:Cite journal
- Template:Cite journal
- Template:Citation.
- Template:Cite journal
- Template:Cite book
General referencesEdit
Template:More footnotes needed
- Template:Citation. See Section 2.5.
- Template:Cite journal
- Template:Citation. See Chapter 2.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation
- Template:Citation
- Template:Citation. In 3 volumes. (Vol.1:Template:ISBN, Vol.2:Template:ISBN, Vol.3:Template:ISBN)
- Template:Citation.
- Template:Citation. Reprinted by Dover Publications, 1979.
External linksEdit
- Template:Springer
- Stanford Encyclopedia of Philosophy: "The Mathematics of Boolean Algebra", by J. Donald Monk.
- McCune W., 1997. Robbins Algebras Are Boolean JAR 19(3), 263–276
- "Boolean Algebra" by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.
- Burris, Stanley N.; Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. Template:ISBN.
- {{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web
|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:BooleanAlgebra%7CBooleanAlgebra.html}} |title = Boolean Algebra |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}