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 $ x $ also its complement — the element $ Cx $, which satisfies the relations

$$ \sup \{ x, Cx \} = 1,\ \ \inf \{ x, Cx \} = 0. $$

The operations sup and inf are usually denoted by the symbols $ \lor $ and $ \wedge $, and sometimes by $ \cup $ and $ \cap $ respectively, in order to stress their similarity to the set-theoretical operations of union and intersection. The notation $ \overline{x}\; , x ^ \prime $ or $ -x $ may be employed instead of $ Cx $. 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 $ C $, $ \lor $, $ \wedge $ which satisfy the following axioms:

1) $ x \lor y = y \lor x $, $ x \wedge y = y \wedge x; $

2) $ x \lor (y \lor z) = (x \lor y) \lor z $, $ x \wedge (y \wedge z) = (x \wedge y) \wedge z; $

3) $ (x \wedge y) \lor y = y $, $ (x \lor y) \wedge y = y; $

4) $ x \wedge (y \lor z) = (x \wedge y) \lor (x \wedge z) $, $ x \lor (y \wedge z) = (x \lor y) \wedge (x \lor z); $

5) $ (x \wedge Cx) \lor y = y $, $ (x \lor Cx) \wedge y = y. $

If this approach is adopted, the order is not assumed to be given in advance, and is introduced by the following condition: $ x \leq y $ if and only if $ x = x \wedge y $.

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 $ C $, $ \lor $, $ \wedge $, other operations in a Boolean algebra can be defined; among these the symmetric difference operation is particularly important:

$$ x + {} _ {2} y = \ (x \wedge Cy) \lor (y \wedge Cx) . $$

Alternative notations are $ x \Delta y $, $ | x - y | $.

Any Boolean algebra is a Boolean ring with a unit element with respect to the operations of "addition" ( $ + _ {2} $) and "multiplication" ( $ \wedge $); 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 $ Cx $ being interpreted as the negation of the statement $ x $, and the operations $ \wedge $ and $ \lor $ 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 $ x \leq y $ means that an event $ y $ follows from an event $ x $; the "1" , the "0" and the Boolean operations $ \lor $, $ \wedge $ and $ C $ are interpreted correspondingly.

An example of a Boolean algebra is the system of all subsets of some given set $ Q $ partially ordered by inclusion. Such a Boolean algebra is denoted by $ 2 ^ {Q} $; its zero is the empty set, and its unit is the set $ Q $ itself. The set $ Q \setminus x $ is the complement of an element $ x $; the Boolean operations $ \lor $ and $ \wedge $ coincide with union and intersection, respectively.

Instead of the subsets of $ Q $ it is convenient to consider their characteristic functions. The system $ X _ {Q} $ of all such functions, with the natural order, is a Boolean algebra, which is isomorphic to the Boolean algebra $ 2 ^ {Q} $. In such a Boolean algebra the operations $ \lor $, $ \wedge $, $ C $, and $ + _ {2} $ are interpreted as follows:

$$ (x \lor y) (q) = \ \max \{ x (q), y (q) \} , $$

$$ (x \wedge y) (q) = \mathop{\rm min} \{ x(q), y(q) \} = x (q) \cdot y (q), $$

$$ (Cx) (q) = 1 - x (q), $$

$$ (x + {} _ {2} y) (q) = | x (q) - y (q) | = \ x (q) + y (q) ( \mathop{\rm mod} 2) \ (q \in Q). $$

The following cases are especially important:

1) $ Q = Q _ {n} = \{ 1 \dots n \} . $

In this case the characteristic functions of the subsets are "two-valued symbols" of the form:

$$ x = (x _ {1} \dots x _ {n} ),\ \ x _ {i} = \left \{ \begin{array}{l} 0, \\ 1, \\ \end{array} \right .$$

which are $ 2 ^ {n} $ in number. For $ n = 1 $, the two-element Boolean algebra, consisting only of "1" and "0" , is obtained.

2) $ Q = X _ {Q _ {n} } . $

In this case, all possible functions, defined on the system of all binary symbols of length $ n $, and taking the values "0" and "1" only, are elements of $ X _ {Q} $. They are called Boolean functions in $ n $ 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 $ E $ of elements of a Boolean algebra $ X $ is itself a Boolean algebra with respect to the order induced from $ X $. This is the case, in particular, if:

(a) $ E $ is a principal ideal, i.e. a set of the form $ \{ {x \in X } : {x \leq u } \} $; the element $ u $ then acts as the unit "1" ;

(b) $ E $ is a subalgebra of a Boolean algebra $ X $. This means that if $ x, y \in E $, it follows that $ x \lor y, x \wedge y, Cx \in E $. The "0" and "1" of the initial Boolean algebra are also the "0" and "1" of the new Boolean algebra. The Boolean subalgebras of $ 2 ^ {Q} $ are especially important; they are called algebras of sets. Any set $ E \subset X $ generates a certain subalgebra — the smallest subalgebra that contains $ E $.

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 $ X $ is generated by a set $ E $, then all mappings of $ E $ into an arbitrary Boolean algebra have an extension to a homomorphism if and only if $ E $ is an independent set, i.e. if all elements of the form

$$ x _ {1} \wedge \dots \wedge x _ {p} \wedge Cx _ {p + 1 } \wedge \dots \wedge Cx _ {m} ,\ \ x _ {i} \in E,\ \ x _ {i} \neq x _ {k} , $$

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 $ n $ variables considered above. Independent generators of it are the functions

$$ f _ {i} : \ f _ {i} (x) = \ f _ {i} (x _ {1} \dots x _ {n} ) = x _ {i} . $$

Stone's theorem: Every Boolean algebra $ X $ is isomorphic to some algebra of sets, namely, the algebra of all open-and-closed sets of a totally-disconnected compactum $ \mathfrak O (X) $, defined up to a homeomorphism. This compactum is known as Stone's compactum, or the Stone space of $X$. To a homomorphism of a Boolean algebra $ X $ into a Boolean algebra $ Y $ corresponds a topological imbedding of $ \mathfrak O (Y) $ into $ \mathfrak O (X) $; to a subalgebra of a Boolean algebra $ X $ there corresponds a continuous image of $ \mathfrak O (X) $. The Stone compactum of a free Boolean algebra is a dyadic discontinuum.

A Boolean algebra $ X $ is called complete if any set $ E \subset X $ has an upper bound $ \sup E $ and a lower bound $ \inf E $. This is equivalent to $ \mathfrak O (X) $ being extremal (cf. Extremally-disconnected space). Subalgebras of a complete Boolean algebra containing the bounds of all their subsets calculated in $ X $ are called regular subalgebras. The weight of a Boolean algebra $ X $ is the lowest cardinality of a complete generating set, i.e. a set which is not contained in any regular subalgebra other than $ X $. 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 $ \mu $( a measure) is defined on it with the following properties: 1) if $ x \neq 0 $, then $ \mu (x) > 0 $; 2) if $ E \subset X $ and $ x \wedge y = 0 $ when $ x, y \in E $, $ x \neq y $, then

$$ \mu ( \sup E) = \ \sum _ {x \in E } \mu (x). $$

In probability theory, in which normed Boolean algebras are particularly important, it is usually assumed that $ \mu (1) = 1 $. Here, the value of $ \mu (x) $ is interpreted as the probability of an event $ x $. 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 $ (o) $- topology, which, for a normed Boolean algebra, is metrizable, and corresponds to the metric

$$ \rho (x, y) = \ \mu [(x \wedge Cy) \lor (Cx \wedge y)], $$

and is identical with the Tikhonov topology for Boolean algebras of the form $ 2 ^ {Q} $. In the most general case there need not be a topology compatible with the order in a Boolean algebra.

References[edit]