HOME

TheInfoList



OR:

In
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures, which are set (mathematics), sets with specific operation (mathematics), operations acting on their elements. Algebraic structur ...
, a Boolean algebra or Boolean lattice is a complemented
distributive lattice In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...
. This type of
algebraic structure In mathematics, an algebraic structure or algebraic system consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplicatio ...
captures essential properties of both set operations and
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
operations. A Boolean algebra can be seen as a generalization of a
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
algebra or a field of sets, or its elements can be viewed as generalized
truth value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false''). Truth values are used in ...
s. 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 Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or Logical_equality#Inequality, logical inequality is a Logical connective, logical operator whose negation is the logical biconditional. With two inputs, X ...
or symmetric difference (not
disjunction In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
∨). However, the theory of Boolean rings has an inherent asymmetry between the two operators, while the
axiom An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
s and theorems of Boolean algebra express the symmetry of the theory described by the duality principle. __TOC__


History

The term "Boolean algebra" honors
George Boole George Boole ( ; 2 November 1815 – 8 December 1864) was a largely self-taught English mathematician, philosopher and logician, most of whose short career was spent as the first professor of mathematics at Queen's College, Cork in Ireland. H ...
(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 Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American scientist, mathematician, logician, and philosopher who is sometimes known as "the father of pragmatism". According to philosopher Paul Weiss (philosopher), Paul ...
. The first systematic presentation of Boolean algebra and
distributive lattice In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...
s 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 Garrett Birkhoff (January 19, 1911 – November 22, 1996) was an American mathematician. He is best known for his work in lattice theory. The mathematician George Birkhoff (1884–1944) was his father. Life The son of the mathematician Ge ...
's 1940 ''Lattice Theory''. In the 1960s, Paul Cohen, Dana Scott, and others found deep new results in
mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
and axiomatic set theory using offshoots of Boolean algebra, namely forcing and Boolean-valued models.


Definition

A Boolean algebra is a set , equipped with two
binary operation In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, a binary operation ...
s (called "meet" or "and"), (called "join" or "or"), a unary operation (called "complement" or "not") and two elements and in (called "bottom" and "top", or "least" and "greatest" element, also denoted by the symbols and , respectively), such that for all elements , and of , the following
axiom An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
s hold: :: 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 and to be ''distinct'' elements in order to exclude this case.) It follows from the last three pairs of axioms above (identity, distributivity and complements), or from the absorption axiom, that :     if and only if     . The relation defined by if these equivalent conditions hold, is a
partial order In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable ...
with least element 0 and greatest element 1. The meet and the join 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 with and with 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, the two-element Boolean algebra, has only two elements, and , and is defined by the rules: :* It has applications in
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
, interpreting as ''false'', as ''true'', as ''and'', as ''or'', and 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 Electrical engineering is an engineering discipline concerned with the study, design, and application of equipment, devices, and systems that use electricity, electronics, and electromagnetism. It emerged as an identifiable occupation in the l ...
; here 0 and 1 represent the two different states of one bit in a
digital circuit In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a generalization of Boolean circuits and a mathematica ...
, typically high and low
voltage Voltage, also known as (electrical) potential difference, electric pressure, or electric tension, is the difference in electric potential between two points. In a Electrostatics, static electric field, it corresponds to the Work (electrical), ...
. 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 In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
(set of all subsets) of any given nonempty set forms a Boolean algebra, an algebra of sets, with the two operations (union) and (intersection). The smallest element 0 is the
empty set In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...
and the largest element is the set itself. :* After the two-element Boolean algebra, the simplest Boolean algebra is that defined by the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
of two atoms: * The set of all subsets of that are either finite or cofinite is a Boolean algebra and an algebra of sets called the finite–cofinite algebra. If is infinite then the set of all cofinite subsets of , which is called the Fréchet filter, is a free ultrafilter on . However, the Fréchet filter is not an ultrafilter on the power set of . * Starting with the
propositional calculus The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. Sometimes, it is called ''first-order'' propositional logic to contra ...
with sentence symbols, form the Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo
logical equivalence In logic and mathematics, statements p and q are said to be logically equivalent if they have the same truth value in every model. The logical equivalence of p and q is sometimes expressed as p \equiv q, p :: q, \textsfpq, or p \iff q, depending ...
). 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 the two-element Boolean algebra. * Given any linearly ordered set with a least element, the interval algebra is the smallest Boolean algebra of subsets of containing all of the half-open intervals such that is in and is either in or equal to . Interval algebras are useful in the study of Lindenbaum–Tarski algebras; every
countable In mathematics, a Set (mathematics), set is countable if either it is finite set, finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function fro ...
Boolean algebra is isomorphic to an interval algebra. * For any
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
, the set of all positive divisors of , defining if divides , forms a
distributive lattice In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...
. This lattice is a Boolean algebra if and only if is square-free. The bottom and the top elements of this Boolean algebra are the natural numbers and , respectively. The complement of is given by . The meet and the join of and are given by the
greatest common divisor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...
() and the least common multiple () of and , respectively. The ring addition is given by . The picture shows an example for . As a counter-example, considering the non-square-free , 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 is a topological space, then the collection of all subsets of that are both open and closed forms a Boolean algebra with the operations (union) and (intersection). * If is an arbitrary ring then its set of '' central idempotents'', which is the set A = \left\, becomes a Boolean algebra when its operations are defined by and .


Homomorphisms and isomorphisms

A ''
homomorphism In algebra, a homomorphism is a morphism, structure-preserving map (mathematics), map between two algebraic structures of the same type (such as two group (mathematics), groups, two ring (mathematics), rings, or two vector spaces). The word ''homo ...
'' between two Boolean algebras and is a function such that for all , in : : , : , : , : . It then follows that for all in . The
class Class, Classes, or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used d ...
of all Boolean algebras, together with this notion of morphism, forms a
full subcategory In mathematics, specifically category theory, a subcategory of a category ''C'' is a category ''S'' whose objects are objects in ''C'' and whose morphisms are morphisms in ''C'' with the same identities and composition of morphisms. Intuitivel ...
of the category of lattices. An ''isomorphism'' between two Boolean algebras and is a homomorphism with an inverse homomorphism, that is, a homomorphism such that the composition is the identity function on , and the composition is the identity function on . A homomorphism of Boolean algebras is an isomorphism if and only if it is bijective.


Boolean rings

Every Boolean algebra gives rise to a ring by defining (this operation is called symmetric difference in the case of sets and XOR in the case of logic) and . The zero element of this ring coincides with the 0 of the Boolean algebra; the multiplicative identity element of the ring is the of the Boolean algebra. This ring has the property that for all in ; rings with this property are called Boolean rings. Conversely, if a Boolean ring is given, we can turn it into a Boolean algebra by defining and . 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 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; in fact the categories are
isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
. 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 filters

An ''ideal'' of the Boolean algebra is a nonempty subset such that for all , in we have in and for all in we have in . This notion of ideal coincides with the notion of ring ideal in the Boolean ring . An ideal of is called ''prime'' if and if in always implies in or in . Furthermore, for every we have that , and then if is prime we have or for every . An ideal of is called ''maximal'' if and if the only ideal properly containing is itself. For an ideal , if and , then or is contained in another proper ideal . Hence, such an 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 . The dual of an ''ideal'' is a ''filter''. A ''filter'' of the Boolean algebra is a nonempty subset such that for all , in we have in and for all in we have in . The dual of a ''maximal'' (or ''prime'') ''ideal'' in a Boolean algebra is '' ultrafilter''. Ultrafilters can alternatively be described as 2-valued morphisms from 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 In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes suc ...
(ZF), if ZF is
consistent In deductive logic, a consistent theory is one that does not lead to a logical contradiction. A theory T is consistent if there is no formula \varphi such that both \varphi and its negation \lnot\varphi are elements of the set of consequences ...
. Within ZF, the ultrafilter lemma is strictly weaker than the
axiom of choice In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
. 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.


Representations

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 is isomorphic to the Boolean algebra of all clopen sets in some ( compact totally disconnected Hausdorff) topological space.


Axiomatics

The first axiomatization of Boolean lattices/algebras in general was given by the English philosopher and mathematician
Alfred North Whitehead Alfred North Whitehead (15 February 1861 – 30 December 1947) was an English mathematician and philosopher. He created the philosophical school known as process philosophy, which has been applied in a wide variety of disciplines, inclu ...
in 1898. It included the above axioms and additionally and . In 1904, the American mathematician Edward V. Huntington (1874–1952) gave probably the most parsimonious axiomatization based on , , , even proving the associativity laws (see box). He also proved that these axioms are independent of each other. In 1933, Huntington set out the following elegant axiomatization for Boolean algebra. It requires just one binary operation and a unary functional symbol , 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 Alfred Tarski (; ; born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician ...
and his students. In 1996, William McCune at
Argonne National Laboratory Argonne National Laboratory is a Federally funded research and development centers, federally funded research and development center in Lemont, Illinois, Lemont, Illinois, United States. Founded in 1946, the laboratory is owned by the United Sta ...
, 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.


Generalizations

Removing the requirement of existence of a unit from the axioms of Boolean algebra yields "generalized Boolean algebras". Formally, a
distributive lattice In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...
is a generalized Boolean lattice, if it has a smallest element and for any elements and in such that , there exists an element such that and . Defining as the unique 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 In the mathematical study of logic and the physical analysis of quantum foundations, quantum logic is a set of rules for manip­ulation of propositions inspired by the structure of quantum theory. The formal system takes as its starting p ...
as lattices of closed
linear subspace In mathematics, the term ''linear'' is used in two distinct senses for two different properties: * linearity of a ''function (mathematics), function'' (or ''mapping (mathematics), mapping''); * linearity of a ''polynomial''. An example of a li ...
s for separable
Hilbert space In mathematics, a Hilbert space is a real number, real or complex number, complex inner product space that is also a complete metric space with respect to the metric induced by the inner product. It generalizes the notion of Euclidean space. The ...
s.


See also


Notes


References


Works cited

* * *. * * * *. * *


General references

*. See Section 2.5. * *. See Chapter 2. *. *. *. *. * * *. In 3 volumes. (Vol.1:, Vol.2:, Vol.3:) *. *. Reprinted by
Dover Publications Dover Publications, also known as Dover Books, is an American book publisher founded in 1941 by Hayward and Blanche Cirker. It primarily reissues books that are out of print from their original publishers. These are often, but not always, book ...
, 1979.


External links

* *
Stanford Encyclopedia of Philosophy The ''Stanford Encyclopedia of Philosophy'' (''SEP'') is a freely available online philosophy resource published and maintained by Stanford University, encompassing both an online encyclopedia of philosophy and peer-reviewed original publication ...
:
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 The Wolfram Demonstrations Project is an Open source, open-source collection of Interactive computing, interactive programmes called Demonstrations. It is hosted by Wolfram Research. At its launch, it contained 1300 demonstrations but has grown t ...
, 2007. * Burris, Stanley N.; Sankappanavar, H. P., 1981.
A Course in Universal Algebra.
' Springer-Verlag. . * {{DEFAULTSORT:Boolean Algebra (Structure) Algebraic structures Ockham algebras