Boolean algebra

In mathematics and computer science, Boolean algebras are algebraic structures which "capture the essence" of the logical operations AND, OR and NOT as well as the set theoretic operations union, intersection and complement.

Specifically, Boolean algebra was an attempt to use algebraic techniques to deal with expressions in the propositional calculus.

Today, Boolean algebras find many applications in electronic design. They were first defined by George Boole in the middle of the 19th century and first applied to switching by Claude Shannon in the 20th century.

The operators of Boolean algebra may be repesented 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 often use + for OR and . for AND (since in some ways those operations are analogous to addition and multiplication in other algebraic structures) and represent NOT by a line drawn above the expression being negated.

Here we use another common notation with ∧ (or ^ for browsers that don't support the character) for AND, &or (or v) for OR, and ¬ (or ~) for NOT.

Table of contents 1 Definition and first consequences 2 Examples 3 Homomorphisms and isomorphisms 4 Boolean rings, ideals and filters 5 Representing Boolean algebras

Definition and first consequences

A Boolean algebra is a lattice (A, ∧ , ∨) with the following four additional properties:

1. bounded below: There exists an element 0, such that a ∨ 0 = a for all a in A.
2. bounded above: There exists an element 1, such that a ∧ 1 = a for all a in A.
3. distributive law: For all a, b, c in A, (a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c).
4. existence of complements: For every a in A there exists an element ¬a in A such that a ∨ ¬a = 1 and a ∧ ¬a = 0.

From these axioms, one can directly show that the smallest element 0 and the largest element 1 are unique, that every element has only one complement, that

a ∧ 0 = 0 and a ∨ 1 = 1,

¬1 = 0 and ¬0 = 1,

and that deMorgan's laws

¬(a ∨ b) = (¬a) ∧ (¬b) and ¬(a ∧ b) = (¬a) ∨ (¬b)

are valid. The dual version of the distributive law,

(a ∧ b) ∨ c = (a ∨ c) ∧ (b ∨ c)

also holds true. In general, any law valid about Boolean algebras can be transformed into another valid, "dual" law by replacing 0 by 1 and ∧ by ∨.

Like any lattice, a Boolean algebra can be seen as a partially ordered set by defining

a ≤ b iff a = a ∧ b

(which is also equivalent to b = a ∨ b).

Examples

The most important Boolean algebra has only two elements, 0 and 1, and is defined by the rules

   ∨  0  1     ∧   0  1
       ----         ----
   0 | 0  1     0 | 0  0
   1 | 1  1     1 | 0  1

It has applications in logic, where 0 is interpreted as "false", 1 is "true", ∧ is "and", ∨ is "or", and ¬ is "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 digital circuits, 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 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 power set 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.

For any natural number n, the set of all positive divisors of n forms a lattice if we write a ← b for a divides 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 ∨ = union and ∧ = intersection.

If R is an arbitrary ring and we define the set of central idempotents by

A = { e in R : e² = e and ex = xe for all x in R }

then the set A becomes a Boolean algebra with the operations e ∨ f = e + f + ef and e ∧ f = ef.

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 only differ 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 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; in particular, the number of elements of every finite Boolean algebra is a power of two.

The celebrated Stone representation theorem states that every Boolean algebra A is isomorphic to the Boolean algebra of all closed-open sets in some (compact totally disconnected T1) topological space. This space can be defined as the space of all maximal ideals in A, with the sets {M : M is a maximal ideal that doesn't contain a} for a in A as base of the topology.

The Stone representation theorem cannot be proven within ZF. It is equivalent to the Boolean Prime Ideal Theorem which states every Boolean algebra has a prime ideal. Both can be proven using the Axiom of Choice. But the Stone representation theorem is strictly weaker than the axiom of choice.

---

See also: formal system[?], logic gate, Karnaugh map, Venn diagram