Boolean algebra
Boolean lattice
A partially ordered set of a special type. It is a distributive lattice with a largest element "1" , the unit of the Boolean algebra, and a smallest element "0" , the zero of the Boolean algebra, that contains together with each element also its complement — the element
, which satisfies the relations
![]() |
The operations sup and inf are usually denoted by the symbols and
, and sometimes by
and
respectively, in order to stress their similarity to the set-theoretical operations of union and intersection. The notation
or
may be employed instead of
. The complement of an element in a Boolean algebra is unique.
A Boolean algebra can also be defined in a different manner. Viz. as a non-empty set with the operations ,
,
which satisfy the following axioms:
1) ,
2) ,
3) ,
4) ,
5) ,
If this approach is adopted, the order is not assumed to be given in advance, and is introduced by the following condition: if and only if
.
Other axiomatics are also possible. The axioms of a Boolean algebra reflect the analogy between the concepts of a "set" , an "event" and a "statement" . The "order" relation in a Boolean algebra can be interpreted in various ways — as set-theoretical inclusion, as causal follow-up of events, as logical follow-up of statements, etc.
In addition to the basic operations ,
,
, other operations in a Boolean algebra can be defined; among these the symmetric difference operation is particularly important:
![]() |
Alternative notations are ,
.
Any Boolean algebra is a Boolean ring with a unit element with respect to the operations of "addition" () and "multiplication" (
); any Boolean ring with a unit element can be considered as a Boolean algebra.
Boolean algebras first arose in the studies of G. Boole [1], [2] as a tool of symbolic logic. They subsequently found extensive application in other branches of mathematics — in probability theory, topology, functional analysis, etc. The applications of Boolean algebras to logic are based on the interpretation of the elements of a Boolean algebra as statements (cf. Algebra of logic), the complement being interpreted as the negation of the statement
, and the operations
and
as conjunction and disjunction, respectively. Closely related to logic is another field of application of Boolean algebras — the theory of contact schemes (cf. Contact scheme). Boolean algebras are used in the foundations of probability theory. A field of events, as studied in probability theory, is a Boolean algebra; here the inequality
means that an event
follows from an event
; the "1" , the "0" and the Boolean operations
,
and
are interpreted correspondingly.
An example of a Boolean algebra is the system of all subsets of some given set partially ordered by inclusion. Such a Boolean algebra is denoted by
; its zero is the empty set, and its unit is the set
itself. The set
is the complement of an element
; the Boolean operations
and
coincide with union and intersection, respectively.
Instead of the subsets of it is convenient to consider their characteristic functions. The system
of all such functions, with the natural order, is a Boolean algebra, which is isomorphic to the Boolean algebra
. In such a Boolean algebra the operations
,
,
, and
are interpreted as follows:
![]() |
![]() |
![]() |
![]() |
The following cases are especially important:
1)
In this case the characteristic functions of the subsets are "two-valued symbols" of the form:
![]() |
which are in number. For
, the two-element Boolean algebra, consisting only of "1" and "0" , is obtained.
2)
In this case, all possible functions, defined on the system of all binary symbols of length , and taking the values "0" and "1" only, are elements of
. They are called Boolean functions in
variables (cf. Boolean function). Every well-constructed formula of predicate logic defines some Boolean function; if two functions are identical, the formulas are equivalent.
Under certain conditions a subset of elements of a Boolean algebra
is itself a Boolean algebra with respect to the order induced from
. This is the case, in particular, if:
(a) is a principal ideal, i.e. a set of the form
; the element
then acts as the unit "1" ;
(b) is a subalgebra of a Boolean algebra
. This means that if
, it follows that
. The "0" and "1" of the initial Boolean algebra are also the "0" and "1" of the new Boolean algebra. The Boolean subalgebras of
are especially important; they are called algebras of sets. Any set
generates a certain subalgebra — the smallest subalgebra that contains
.
Homomorphisms of Boolean algebras play a special role under the mappings of Boolean algebras; they are mappings which commute with the Boolean operations. A bijective homomorphism of Boolean algebras is an isomorphism. If a Boolean algebra is generated by a set
, then all mappings of
into an arbitrary Boolean algebra have an extension to a homomorphism if and only if
is an independent set, i.e. if all elements of the form
![]() |
are non-zero. A Boolean algebra generated by an independent system is called a free Boolean algebra.
An example of a free Boolean algebra is the algebra of Boolean functions in variables considered above. Independent generators of it are the functions
![]() |
Stone's theorem: Every Boolean algebra is isomorphic to some algebra of sets, namely, the algebra of all open-and-closed sets of a totally-disconnected compactum
, defined up to a homeomorphism. This compactum is known as Stone's compactum. To a homomorphism of a Boolean algebra
into a Boolean algebra
corresponds a topological imbedding of
into
; to a subalgebra of a Boolean algebra
there corresponds a continuous image of
. The Stone compactum of a free Boolean algebra is a dyadic discontinuum.
A Boolean algebra is called complete if any set
has an upper bound
and a lower bound
. This is equivalent to
being extremal (cf. Extremally-disconnected space). Subalgebras of a complete Boolean algebra containing the bounds of all their subsets calculated in
are called regular subalgebras. The weight of a Boolean algebra
is the lowest cardinality of a complete generating set, i.e. a set which is not contained in any regular subalgebra other than
. If the weights of all non-zero principal ideals are identical, then the Boolean algebra is called uniform; such algebras invariably contain a complete generating independent set. In other words, a complete uniform Boolean algebra can be "stretched onto" a free Boolean algebra. The study of an arbitrary Boolean algebra readily reduces to the study of uniform Boolean algebras. An incomplete Boolean algebra can be completed in different ways, i.e. it can be imbedded as a subalgebra in some complete Boolean algebra.
A complete Boolean algebra is called normed if a real-valued function (a measure) is defined on it with the following properties: 1) if
, then
; 2) if
and
when
,
, then
![]() |
In probability theory, in which normed Boolean algebras are particularly important, it is usually assumed that . Here, the value of
is interpreted as the probability of an event
. The classical theory of measure and integral can largely be applied to normed Boolean algebras. Normed Boolean algebras have been completely classified [4], [5], [7]. In particular, for uniform normed Boolean algebras the only invariant is the weight. Not all Boolean algebras can be normed. Many conditions for the existence of a measure are known, but these are far from exhaustive in the problem of norming.
A Boolean algebra can be endowed with various topologies. A specially important one is the so-called -topology, which, for a normed Boolean algebra, is metrizable, and corresponds to the metric
![]() |
and is identical with the Tikhonov topology for Boolean algebras of the form . In the most general case there need not be a topology compatible with the order in a Boolean algebra.
References
[1] | G. Boole, "The mathematical analysis of logic: being an essay towards a calculus of deductive reasoning" , Macmillan (1847) |
[2] | G. Boole, "An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities" , Dover, reprint (1951) |
[3] | R. Sikorski, "Boolean algebras" , Springer (1969) |
[4] | D.A. Vladimirov, "Boolesche Algebren" , Akademie Verlag (1978) (Translated from Russian) |
[5] | P.R. Halmos, "Lectures on Boolean algebras" , v. Nostrand (1963) |
[6] | E. Rasiowa, R. Sikorski, "The mathematics of metamathematics" , Polska Akad. Nauk (1963) |
[7] | M.H. Stone, "The theory of representations for Boolean algebras" Trans. Amer. Math. Soc. , 40 (1936) pp. 37–111 |
[8] | G. Birkhoff, "Lattice theory" , Colloq. Publ. , 25 , Amer. Math. Soc. (1973) |
[9] | H. Hermes, "Einführung in die Verbandstheorie" , Springer (1967) |
[10] | A.N. Kolmogorov, "Algèbres de Boole métriques complètes" , VI Zjazd Mathematyków Polskich , Kraków (1950) |
[11] | N. Dunford, J.T. Schwartz, "Linear operators. Spectral operators" , 3 , Interscience (1971) |
[12a] | S. Kakutani, "Concrete representations of abstract ![]() |
[12b] | S. Kakutani, "Concrete representations of abstract ![]() |
[13] | D. Maharam, Proc. Nat. Acad. Sci. USA , 28 (1942) pp. 108–111 |
[14] | G.W. Mackey, "The mathematical foundations of quantum mechanics" , Benjamin (1963) |
[15] | K. Yosida, "Functional analysis" , Springer (1980) |
[16] | K. Kuratowski, "Topology" , 2 , Acad. Press (1968) (Translated from French) |
Boolean algebra. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Boolean_algebra&oldid=24193