Boolean algebra - Formal definition, Examples, Order theoretic properties, Homomorphisms and isomorphisms, Boolean rings, ideals and filters

An algebra on sets, devised by Boole, developed as an algebra of symbolic logic. The differences from arithmetic algebra can be illustrated by the absorption laws on sets A, B and C: A + A = A and (A + B)(A + C) = A + BC. The similarities between the algebra of sets and that of logic can be seen by comparing A ? A = A and p ? p = p, the latter being read ‘p and p implies p’, where p is a statement. The laws of Boolean algebra derive from those relating to the union and intersection of sets. There is a similar algebra governing the use of ‘and’ and (inclusive) ‘or’ with propositions; indeed if p and q are propositions and P = {x:px} (the set of x such that p is true when applied to x) and Q = {x:qx},, then ‘p and q’ is true of the x in the intersection of P and Q and ‘p or q’ is true of the set of x which are in the union of P and Q.

In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations.

For example, the logical assertion that a statement a and its negation ¬a cannot both be true,

parallels the set-theory assertion that a subset A and its complement A have empty intersection,

Because truth values can be represented as binary numbers or as voltage levels in logic circuits, the parallel extends to these as well.

The lattice interpretation helps in generalizing to Heyting algebras, which are Boolean algebras freed from the restriction that either a statement or its negation must be true.

Formal definition

A Boolean algebra is a set A, supplied with two binary operations (called AND), (called OR), a unary operation (called NOT) and two distinct elements 0 (called zero) and 1 (called one), 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. 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:

∧ 0 1 0 0 0 1 0 1

∨ 0 1 0 0 1 1 1 1

a 0 1 ¬a 1 0

It has applications in logic, interpreting 0 as false, 1 as true, ∧ as and, ∨ as or, and ¬ as not. 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) Starting with the propositional calculus with κ sentence symbols, form the Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo tautology). 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 : e2 = 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

(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. Especially, the order dual of every Boolean algebra, or, equivalently, the algebra obtained by exchanging and , is also a Boolean algebra.

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.

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. This ring has the property that a * a = a for all a in A;

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. Furthermore, a map f : A → B is a homomorphism of Boolean algebras if and only if it is a homomorphism of Boolean rings.

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. 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. 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.

Stone's celebrated representation theorem for Boolean algebras states that every Boolean algebra A is isomorphic to the Boolean algebra of all closed-open sets in some (compact totally disconnected Hausdorff) topological space.