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.
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. To the 1890
Vorlesungen of
Ernst
Schröder the first systematic presentation of Boolean algebra
and
distributive lattices is
owed. 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 Vermilye 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 \land (called "meet" or
"and"), \lor (called "join" or "or"), a
unary operation \lnot (called "complement"
or "not") and two elements 0 and 1 (sometimes denoted by \bot and
\top), such that for all elements
a,
b and
c of
A, the following
axioms hold:
- :{| cellpadding=5
A Boolean algebra with only one element is called a
trivial
Boolean algebraor a
degenerate Boolean
algebra. (Some authors require 0 and 1 to be
distinctelements in order to exclude this case.)
It follows from the first three pairs of axioms above
(associativity, commutativity and absorption) that
- :a = a \land b if and only if
a \lor b = b.
The relation ≤ defined by
a≤
bif and only if the
above equivalent conditions hold, is a
partial orderwith least element 0 and greatest
element 1. The meet a \land bor the join a \lor bof two elements
coincides with their
infimumor
supremum, respectively, with respect to ≤.
As in every lattice, the relations \landand \lorsatisfy the first
three pairs of axioms above; the fourth pair is just
distributivity. Since the complements in a distributive lattice are
unique, to define the
involution\negit suffices to define
{\neg}aas the complement of
a.
The set of axioms is
self-dualin the sense that if one
exchanges \lorwith \landand 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.
Examples
- The simplest non-trivial Boolean algebra has only two elements,
0 and 1, and is defined by the rules:
| a \lor (b \lor c) = (a \lor b) \lor c |
| a \land (b \land c) = (a \land b) \land c |
| associativity |
|
| a \lor b = b \lor a |
| a \land b = b \land a |
| commutativity |
|
| a \lor (a \land b) = a |
| a \land (a \lor b) = a |
| absorption |
|
| a \lor (b \land c) = (a \lor b) \land (a \lor
c) |
| a \land (b \lor c) = (a \land b) \lor (a \land
c) |
| distributivity |
|
| a \lor {\neg}a = 1 |
| a \land {\neg}a = 0 |
| complements |
|
|
|
|
| \land |
0 |
1 |
|
| 0 |
| 0 |
0 |
|
| 1 |
| 0 |
1 |
|
|
|
| \lor |
0 |
1 |
|
| 0 |
| 0 |
1 |
|
| 1 |
| 1 |
1 |
|
|
- * It has applications in logic,
interpreting 0 as false, 1 as true, \land as
and, \lor as or, and \neg 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:
- ** (a \lor b) \land ({\neg}a \lor c) \land (b \lor c) \equiv (a
\lor b) \land ({\neg}a \lor c)
- ** (a \land b) \lor ({\neg}a \land c) \lor (b \land c) \equiv
(a \land b) \lor ({\neg}a \land c)
- The power set (set of all subsets) of
any given nonempty set S forms a Boolean algebra with the
two operations \lor := \cup (union) and \land := \cap
(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.
- Starting with the propositional calculus with κ
sentence symbols, form the Lindenbaum algebra (that is, the
set of sentences in the propositional calculus modulo tautology). 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 {0,1}.
- Given any linearly ordered set
with a least element, the interval algebra is the smallest algebra
of subsets of L containing all of the half-open intervals [a, b)
such that a is in L and b in either in L or equal to ∞. Interval
algebras are useful in the study of Lindenbaum-Tarski algebras; every
countable BA is isomorphic to an interval 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 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
\lor := \cup (union) and \land := \cap (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 \lor f := e + f - ef and e \land f := ef.
Homomorphisms and isomorphisms
A homomorphismbetween two
Boolean algebras Aand Bis a functionf: A→
Bsuch that for all a, bin
A:
- f(a \lor b) = f(a) \lor f(b)
- f(a \land b) = f(a) \land f(b)
- f(0) = 0\,
- f(1) = 1.\,
It then follows that f({\neg}a) = {\neg}f(a)for all ain
Aas well. The classof
all Boolean algebras, together with this notion of morphism, forms
a full subcategoryof the categoryof lattices.
A homomorphism is called a monomorphism,
epimorphismor isomorphismif it is injective, surjectiveor
bijective, respectively. The inverse map
of an isomorphism is also an isomorphism.
Boolean rings, ideals and filters
Every Boolean algebra (A, \land, \lor)gives rise to a ring(A, +, *) by defining a + b = (a
\land {\neg}b) \lor (b \land {\neg}a)(this operation is called
symmetric differencein the case
of sets and XORin the case of logic) and
a * b = a \land 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= afor all
ain A; rings with this property are called
Boolean rings.
Conversely, if a Boolean ring Ais given, we can turn it
into a Boolean algebra by defining x \lor y = x + y + xyand x \land
y = xy. 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: A→
Bis a homomorphism of Boolean algebras if and only if it
is a homomorphism of Boolean rings. The categoriesof Boolean rings and Boolean
algebras are equivalent.
An idealof the Boolean algebra Ais a subset
Isuch that for all x, yin Iwe
have x \lor yin Iand for all ain Awe
have a \land xin I. This notion of ideal coincides with
the notion of ring idealin the Boolean
ring A. An ideal Iof Ais called
primeif I≠ Aand if a \land bin
Ialways implies ain Ior bin
I. An ideal Iof Ais called
maximalif I≠ Aand if the only ideal
properly containing Iis Aitself. These notions
coincide with ring theoretic ones of prime
idealand maximal idealin the
Boolean ring A.
The dual of an idealis a filter. A
filterof the Boolean algebra Ais a subset
psuch that for all x, yin pwe
have x \land yin pand for all ain Awe
have a \lor xin p.
Representing Boolean algebras
It can be shown that every finiteBoolean 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'scelebrated representation
theorem for Boolean algebrasstates that
everyBoolean algebra Ais isomorphic to the
Boolean algebra of all clopensets in some
(compacttotally disconnectedHausdorff) topological space.
Axiomatics for Boolean algebras
In 1933, the American mathematician Edward Vermilye
Huntington(1874–1952) set out the following elegant
axiomatization for Boolean algebra. It requires just one binary
operation + and a unary
functional symboln, to be read as 'complement', which
satisfy the following laws:
- Commutativity: x + y = y +
x.
- Associativity: (x + y) + z
= x + (y + z).
- Huntington equation: n(n(x)
+ y) + n(n(x) +
n(y)) = x.
Herbert Robbinsimmediately 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 Tarskiand 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
programEQPhe 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
latticeBis a generalized Boolean lattice, if it has a
smallest element 0 and for any elements aand bin
Bsuch that a≤ b, there exists an element
xsuch that a \land x = 0and a \lor x = b. Defining
a\setminus bas the unique xsuch that (a \land b) \lor x =
aand (a \land b) \land x = 0, we say that the structure
(B,\land,\lor,\setminus,0)is a generalized Boolean
algebra, while (B,\lor,0)is a generalized Boolean
semilattice. Generalized Boolean lattices are exactly the
idealsof 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 logicas lattices of closed subspaces
for separable Hilbert spaces.
See also
References
- . See Section 2.5.
- . See Chapter 2.
- .
- .
- .
- .
- .
- .
- .
- . In 3 volumes. (Vol.1:ISBN 978-0-444-70261-6, Vol.2:ISBN
978-0-444-87152-7, Vol.3:ISBN 978-0-444-87153-4)
- . Reprinted by Dover
Publications, 1979.
External links
A monograph available free online:
|
|
|
Wikis
Quiz
Map
Search
