Boolean algebra (structure)

For an introduction to the subject, see Boolean algebra. For an alternative presentation, see Boolean algebras canonically defined.

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.[1]

Boolean lattice of subsets

History

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.

Definition

A Boolean algebra is a six-tuple consisting of a set A, equipped with two binary operations ∧ (called "meet" or "and"), ∨ (called "join" or "or"), a unary operation ¬ (called "complement" or "not") and two elements 0 and 1 (called "bottom" and "top", or "least" and "greatest" element, also denoted by the symbols ⊥ and ⊤, respectively), such that for all elements a, b and c of A, the following axioms hold:[2]

a ∨ (bc) = (ab) ∨ c a ∧ (bc) = (ab) ∧ c associativity
ab = ba ab = ba commutativity
a ∨ (ab) = a a ∧ (ab) = a absorption
a ∨ 0 = a a ∧ 1 = a identity
a ∨ (bc) = (ab) ∧ (ac)   a ∧ (bc) = (ab) ∨ (ac)   distributivity
a ∨ ¬a = 1 a ∧ ¬a = 0 complements

Note, however, that the absorption law can be excluded from the set of axioms as it can be derived by the other axioms.

A Boolean algebra with only one element is called a trivial Boolean algebra or a degenerate Boolean algebra. (Some authors require 0 and 1 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

a = ba     if and only if     ab = b.

The relation ≤ defined by ab if these equivalent conditions hold, is a partial order with least element 0 and greatest element 1. The meet ab and the join ab 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 0 with 1 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.[3]

Examples

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. 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 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:
    • (ab) ∧ (¬ac) ∧ (bc) ≡ (ab) ∧ (¬ac)
    • (ab) ∨ (¬ac) ∨ (bc) ≡ (ab) ∨ (¬ac)
  • After the two-element Boolean algebra, the simplest Boolean algebra is that defined by the power set of two atoms:
0 a b 1
0 0 0 0 0
a 0 a 0 a
b 0 0 b b
1 0 a b 1
0 a b 1
0 0 a b 1
a a a 1 1
b b 1 b 1
1 1 1 1 1
x 0 a b 1
¬x 1 b a 0
Hasse diagram of the Boolean algebra of divisors of 30.

Homomorphisms and isomorphisms

A homomorphism between two Boolean algebras A and B is a function f : AB such that for all a, b in A:

f(ab) = f(a) ∨ f(b),
f(ab) = f(a) ∧ f(b),
f(0) = 0,
f(1) = 1.

It then follows that fa) = ¬f(a) for all a in A. The class of all Boolean algebras, together with this notion of morphism, forms a full subcategory of the category of lattices.

Boolean rings

Main article: Boolean ring

Every Boolean algebra (A, ∧, ∨) gives rise to a ring (A, +, ·) by defining a + b := (a ∧ ¬b) ∨ (b ∧ ¬a) = (ab) ∧ ¬(ab) (this operation is called symmetric difference in the case of sets and XOR in the case of logic) and a · b := ab. 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 xy := x + y + (x · y) and xy := x · y. [4][5] 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 f : AB 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.[6]

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 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 ax 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 IA and if ab in I always implies a in I or b in I. Furthermore, for every aA we have that a-a = 0 ∈ I and then aI or -aI for every aA, if I is prime. An ideal I of A is called maximal if IA and if the only ideal properly containing I is A itself. For an ideal I, if aI and -aI, then I ∪ {a} or I ∪ {-a} is properly contained in another ideal J. Hence, that an I 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 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 xy in p and for all a in A we have ax in p. The dual of a maximal (or prime) ideal in a Boolean algebra is ultrafilter. Ultrafilters can alternatively be described as 2-valued morphisms from A to the two-element Boolean algebra. The statement every filter in a Boolean algebra can be extended to an ultrafilter is called the Ultrafilter Theorem and can not be proved in ZF, if ZF is consistent. Within ZF, it is strictly weaker than the axiom of choice. The Ultrafilter Theorem 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 A 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 Alfred North Whitehead in 1898.[7][8] It included the above axioms and additionally x∨1=1 and x∧0=0. 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).[9] He also proved that these axioms are independent of each other.[10] In 1933, Huntington set out the following elegant axiomatization for Boolean algebra. It requires just one binary operation + and a unary functional symbol n, to be read as 'complement', which satisfy the following laws:

  1. Commutativity: x + y = y + x.
  2. Associativity: (x + y) + z = x + (y + z).
  3. Huntington equation: n(n(x) + y) + n(n(x) + n(y)) = x.

Herbert Robbins immediately asked: If the Huntington equation is replaced with its dual, to wit:

4. Robbins Equation: n(n(x + y) + n(x + n(y))) = x,

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 automated reasoning program EQP he designed. For a simplification of McCune's proof, see Dahn (1998).

Generalizations

Removing the requirement of existence of a unit from the axioms of Boolean algebra yields "generalized Boolean algebras". Formally, a distributive lattice B is a generalized Boolean lattice, if it has a smallest element 0 and for any elements a and b in B such that ab, there exists an element x such that a ∧ x = 0 and a ∨ x = b. Defining a ∖ b as the unique x such that (a ∧ b) ∨ x = a and (a ∧ b) ∧ x = 0, we say that the structure (B,∧,∨,∖,0) is a generalized Boolean algebra, while (B,∨,0) 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 subspaces for separable Hilbert spaces.

See also

Notes

  1. Givant and Paul Halmos, 2009, p. 20
  2. Davey, Priestley, 1990, p.109, 131, 144
  3. Goodstein, R. L. (2012), "Chapter 2: The self-dual system of axioms", Boolean Algebra, Courier Dover Publications, pp. 21ff, ISBN 9780486154978.
  4. Stone, 1936
  5. Hsiang, 1985, p.260
  6. Cohn (2003), p. 81.
  7. Padmanabhan, p. 73
  8. Whitehead, 1898, p.37
  9. Huntington, 1904, p.292-293, (first of several axiomatizations by Huntington)
  10. Huntington, 1904, p.296

References

External links

A monograph available free online:

This article is issued from Wikipedia - version of the Thursday, April 21, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.