Boolean algebra
From Exampleproblems
 For a basic intro to sets, Boolean operations, Venn diagrams, truth tables, and Boolean applications, see Boolean logic.
 For the use of binary numbers in computer systems, please see the article binary arithmetic.
In mathematics, a Boolean algebra (sometimes Boolean lattice) is an algebraic structure (that is, a set of objects, called elements, together with operations on those elements, which take one or two elements and return another element). The elements can be thought of in various ways; one of the most common is to think of them as generalized truth values. As a simple example, there might be three conditions that can be independently true or false. An element of the Boolean algebra might then specify exactly which ones are true; the Boolean algebra itself would be the collection of all eight possibilities, together with ways of combining them.
A related subject that is sometimes referred to as Boolean algebra is Boolean logic, which might be defined as what all Boolean algebras have in common. It consists of relationships among elements of a Boolean algebra that always hold, no matter which Boolean algebra one starts with. Since the algebra of logic gates and some electrical circuits is formally the same, Boolean logic is studied in engineering and computer science, as well as in mathematical logic.
The operations on a Boolean algebra are referred to as AND, OR and NOT. For the structure to be a Boolean algebra, these operations must behave as they would on the twoelement Boolean algebra (the one whose only elements are TRUE and FALSE).
Boolean algebras are named after George Boole, an English mathematician at University College Cork. The algebraic system of logic Boole formulated is distinct from that described in this article in some small but important respects.
Contents 
Formal definition
A Boolean algebra is a set A, supplied with two binary operations (logical AND), (logical OR), a unary operation / ~ (logical NOT) and two elements 0 (logical FALSE) and 1 (logical TRUE), such that, for all elements a, b and c of set A, the following axioms hold:
associativity commutativity absorption distributivity complements
The first three pairs of axioms above: associativity, commutativity and absorption, mean that (A, , ) is a lattice. Thus a Boolean algebra can also be equivalently defined as a distributive complemented lattice.
From these axioms, one can show that the smallest element 0, the largest element 1, and the complement ¬a of any element a are uniquely determined. For all a and b in A, the following identities also follow:
idempotency boundedness 0 and 1 are complements de Morgan's laws involution
Examples
 The simplest Boolean algebra has only two elements, 0 and 1, and is defined by the rules:


 It has applications in logic, interpreting 0 as false, 1 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 twoelement 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 inputoutput behavior. Furthermore, every possible inputoutput behavior can be modeled by a suitable Boolean expression.
 The twoelement 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 twoelement Boolean algebra (which can always be checked by a trivial brute force algorithm). This can for example be used to show that the following laws (Consensus theorems) are generally valid in all Boolean algebras:
 (a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)
 (a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)
 The twoelement 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 twoelement Boolean algebra (which can always be checked by a trivial brute force algorithm). 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 set S forms a Boolean algebra with the two operations ∨ := ∪ (union) and ∧ := ∩ (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.
 For any natural number n, the set of all positive divisors of n forms a distributive lattice if we write a ≤ b for a  b. This lattice is a Boolean algebra if and only if n is squarefree. 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 ∨ := ∪ (union) and ∧ := ∩ (intersection).
 If R is an arbitrary ring and we define the set of central idempotents by
A = { e ∈ R : e^{2} = e, ex = xe, ∀x ∈ R }
then the set A becomes a Boolean algebra with the operations e ∨ f := e + f − ef and e ∧ f := ef.
Order theoretic properties
Like any lattice, a Boolean algebra (A, , ) gives rise to a partially ordered set (A, ≤) by defining
 a ≤ b iff a = a b
(which is also equivalent to b = a b).
In fact one can also define a Boolean algebra to be a distributive lattice (A, ≤) (considered as a partially ordered set) with least element 0 and greatest element 1, within which every element x has a complement ¬x such that
 x ¬x = 0 and x ¬x = 1
Here and are used to denote the infimum (meet) and supremum (join) of two elements. Again, if complements in the above sense exist, then they are uniquely determined.
The algebraic and the order theoretic perspective can usually can be used interchangeably and both are of great use to import results and concepts from both universal algebra and order theory. In many practical examples an ordering relation, conjunction, disjunction, and negation are all naturally available, so that it is straightforward to exploit this relationship.
Principle of duality
One can also apply general insights from duality in order theory to Boolean algebras. Especially, the order dual of every Boolean algebra, or, equivalently, the algebra obtained by exchanging and , is also a Boolean algebra. In general, any law valid for Boolean algebras can be transformed into another valid, dual law by exchanging 0 with 1, with , and ≤ with ≥.
Other notation
The operators of Boolean algebra may be represented in various ways. Often they are simply written as AND, OR and NOT. In describing circuits, NAND (NOT AND), NOR (NOT OR) and XOR (eXclusive OR) may also be used. Mathematicians, engineers, and programmers often use + for OR and · for AND (since in some ways those operations are analogous to addition and multiplication in other algebraic structures and this notation makes it very easy to get sum of products form for people who are familiar with normal algebra) and represent NOT by a line drawn above the expression being negated.
Here we use another common notation with "meet" for AND, "join" for OR, and ¬ for NOT. (Readers using textonly browsers will see LaTeX codes instead of the wedge symbols they represent.)
Homomorphisms and isomorphisms
A homomorphism between the Boolean algebras A and B is a function f : A → B such that for all a, b in A:
 f(a b) = f(a) f(b)
 f(a b) = f(a) f(b)
 f(0) = 0
 f(1) = 1
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 category. An isomorphism from A to B is a homomorphism from A to B which is bijective. The inverse of an isomorphism is also an isomorphism, and we call the two Boolean algebras A and B isomorphic. From the standpoint of Boolean algebra theory, they cannot be distinguished; they differ only in the notation of their elements.
Boolean rings, ideals and filters
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.
Representing Boolean algebras
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 closedopen sets in some (compact totally disconnected Hausdorff) topological space.
Axiomatics for Boolean algebras
In 1933, the American mathematician Edward Vermilye Huntington (18741952) showed the following axiomatization for Boolean algebra:
 Commutativity: x + y = y + x.
 Associativity: (x + y) + z = x + (y + z).
 Huntington equation: n(n(x) + y) + n(n(x) + n(y)) = x.
The unary functional symbol n may be read as 'complement'.
Herbert Robbins then posed the following question: Can the Huntington equation be shortened as follows, and is this new equation, together with associativity and commutativity, a basis for Boolean algebra? With this collection of axioms called a Robbins algebra, the question then becomes: Is every Robbins algebra a Boolean algebra?
Axiomatization for Robbins algebra:
 Commutativity: x + y = y + x.
 Associativity: (x + y) + z = x + (y + z).
 Robbins Equation: n(n(x + y') + n(x + n(y))) = x.
This question remained open from the 1930s, and became a favorite question of Alfred Tarski and his students.
In 1996, William McCune at Argonne National Laboratory, building upon the work of Larry Wos, Steve Winker, and Bob Veroff, answered this longstanding question in the affirmative: Every Robbins algebra is a Boolean algebra. This work was done using McCune's automated reasoning program EQP.
See also
 Boolean function
 Boolean logic
 Canonical form (Boolean algebra)
 Complete Boolean algebra
 Formal system
 Forcing (mathematics)
 Heyting algebra
 Karnaugh map
 List of Boolean algebra topics
 Logic gate
 Venn diagram
External links
 Article on The Mathematics of Boolean Algebra at the Stanford Encyclopedia of Philosophybg:Булева алгебра
bn:বুলিয়ান বীজগণিত ca:Àlgebra de Boole cs:Booleova algebra de:Boolesche Algebra es:Álgebra de Boole fa:جبر بولی fr:Algèbre de Boole (logique) gl:Álxebra de Boole hr:Booleova algebra io:Booleana algebro id:Aljabar Boolean it:Algebra di Boole he:אלגברה בוליאנית lt:Būlio algebra nl:Booleaanse algebra ja:ブール代数 pl:Algebra Boole'a pt:Álgebra booleana ru:Булева алгебра sr:Булова алгебра sl:Booleova algebra sv:Boolesk algebra th:พีชคณิตแบบบูล tr:Boole cebiri uk:Булева алгебра zh:布尔代数