Namespaces
Variants
Actions

Difference between revisions of "Boolean algebra"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Anchors: subalgebra; regular)
m (fix tex)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
b0169201.png
 +
$#A+1 = 119 n = 2
 +
$#C+1 = 119 : ~/encyclopedia/old_files/data/B016/B.0106920 Boolean algebra,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''Boolean lattice''
 
''Boolean lattice''
  
A partially ordered set of a special type. It is a [[Distributive lattice|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b0169201.png" /> also its complement — the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b0169202.png" />, which satisfies the relations
+
A partially ordered set of a special type. It is a [[Distributive lattice|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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b0169203.png" /></td> </tr></table>
+
$$
 +
\sup \{ x, Cx \}  = 1,\ \
 +
\inf \{ x, Cx \}  = 0.
 +
$$
  
The operations sup and inf are usually denoted by the symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b0169204.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b0169205.png" />, and sometimes by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b0169206.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b0169207.png" /> respectively, in order to stress their similarity to the set-theoretical operations of union and intersection. The notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b0169208.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b0169209.png" /> may be employed instead of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692010.png" />. The complement of an element in a Boolean algebra is unique.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692013.png" /> which satisfy the following axioms:
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692015.png" />
+
1) $  x \lor y = y \lor x $,  
 +
$  x \wedge y = y \wedge x; $
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692017.png" />
+
2) $  x \lor (y \lor z) = (x \lor y) \lor z $,  
 +
$  x \wedge (y \wedge z) = (x \wedge y) \wedge z; $
  
3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692019.png" />
+
3) $  (x \wedge y) \lor y = y $,  
 +
$  (x \lor y) \wedge y = y; $
  
4) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692021.png" />
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692023.png" />
+
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: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692024.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692025.png" />.
+
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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692028.png" />, other operations in a Boolean algebra can be defined; among these the symmetric difference operation is particularly important:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692029.png" /></td> </tr></table>
+
$$
 +
x + {} _ {2} y  = \
 +
(x \wedge Cy) \lor
 +
(y \wedge Cx) .
 +
$$
  
Alternative notations are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692031.png" />.
+
Alternative notations are $  x \Delta y $,  
 +
$  | x - y | $.
  
Any Boolean algebra is a [[Boolean ring|Boolean ring]] with a unit element with respect to the operations of  "addition"  (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692032.png" />) and  "multiplication"  (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692033.png" />); any Boolean ring with a unit element can be considered as a Boolean algebra.
+
Any Boolean algebra is a [[Boolean ring|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 [[#References|[1]]], [[#References|[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|Algebra of logic]]), the complement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692034.png" /> being interpreted as the negation of the statement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692035.png" />, and the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692037.png" /> 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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692038.png" /> means that an event <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692039.png" /> follows from an event <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692040.png" />; the  "1" , the  "0"  and the Boolean operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692042.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692043.png" /> are interpreted correspondingly.
+
Boolean algebras first arose in the studies of G. Boole [[#References|[1]]], [[#References|[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|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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692044.png" /> partially ordered by inclusion. Such a Boolean algebra is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692045.png" />; its zero is the empty set, and its unit is the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692046.png" /> itself. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692047.png" /> is the complement of an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692048.png" />; the Boolean operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692049.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692050.png" /> coincide with union and intersection, respectively.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692051.png" /> it is convenient to consider their characteristic functions. The system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692052.png" /> of all such functions, with the natural order, is a Boolean algebra, which is isomorphic to the Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692053.png" />. In such a Boolean algebra the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692055.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692056.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692057.png" /> are interpreted as follows:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692058.png" /></td> </tr></table>
+
$$
 +
(x \lor y) (q)  = \
 +
\max \{ x (q), y (q) \} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692059.png" /></td> </tr></table>
+
$$
 +
(x \wedge y) (q)  =   \mathop{\rm min} \{ x(q), y(q) \}  = x (q) \cdot y (q),
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692060.png" /></td> </tr></table>
+
$$
 +
(Cx) (q)  = 1 - x (q),
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692061.png" /></td> </tr></table>
+
$$
 +
(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:
 
The following cases are especially important:
  
1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692062.png" />
+
1) $  Q = Q _ {n} = \{ 1 \dots n \} . $
  
 
In this case the characteristic functions of the subsets are  "two-valued symbols"  of the form:
 
In this case the characteristic functions of the subsets are  "two-valued symbols"  of the form:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692063.png" /></td> </tr></table>
+
$$
 +
= (x _ {1} \dots x _ {n} ),\ \
 +
x _ {i} = \left \{
 +
 
 +
\begin{array}{l}
 +
0,  \\
 +
1,  \\
 +
\end{array}
 +
 
 +
\right .$$
  
which are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692064.png" /> in number. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692065.png" />, the two-element Boolean algebra, consisting only of  "1"  and  "0" , is obtained.
+
which are $  2  ^ {n} $
 +
in number. For $  n = 1 $,  
 +
the two-element Boolean algebra, consisting only of  "1"  and  "0" , is obtained.
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692066.png" />
+
2) $  Q = X _ {Q _ {n}  } . $
  
In this case, all possible functions, defined on the system of all binary symbols of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692067.png" />, and taking the values  "0"  and  "1"  only, are elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692068.png" />. They are called Boolean functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692069.png" /> variables (cf. [[Boolean function|Boolean function]]). Every well-constructed formula of predicate logic defines some Boolean function; if two functions are identical, the formulas are equivalent.
+
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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692070.png" /> of elements of a Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692071.png" /> is itself a Boolean algebra with respect to the order induced from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692072.png" />. This is the case, in particular, if:
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692073.png" /> is a principal ideal, i.e. a set of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692074.png" />; the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692075.png" /> then acts as the unit  "1" ;
+
(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" ;
  
 
{{Anchor|subalgebra}}
 
{{Anchor|subalgebra}}
(b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692076.png" /> is a ''subalgebra'' of a Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692077.png" />. This means that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692078.png" />, it follows that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692079.png" />. The  "0"  and  "1"  of the initial Boolean algebra are also the  "0"  and  "1"  of the new Boolean algebra. The Boolean subalgebras of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692080.png" /> are especially important; they are called algebras of sets. Any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692081.png" /> generates a certain subalgebra — the smallest subalgebra that contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692082.png" />.
+
(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 $.
  
 
{{Anchor|homomorphism}}{{Anchor|isomorphism}}
 
{{Anchor|homomorphism}}{{Anchor|isomorphism}}
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692083.png" /> is generated by a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692084.png" />, then all mappings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692085.png" /> into an arbitrary Boolean algebra have an extension to a homomorphism if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692086.png" /> is an independent set, i.e. if all elements of the form
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692087.png" /></td> </tr></table>
+
$$
 +
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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692088.png" /> variables considered above. Independent generators of it are the functions
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692089.png" /></td> </tr></table>
+
$$
 +
f _ {i} : \
 +
f _ {i} (x)  = \
 +
f _ {i} (x _ {1} \dots x _ {n} )
 +
= x _ {i} .
 +
$$
  
Stone's theorem: Every Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692090.png" /> is isomorphic to some algebra of sets, namely, the algebra of all open-and-closed sets of a totally-disconnected compactum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692091.png" />, defined up to a homeomorphism. This compactum is known as Stone's compactum. To a homomorphism of a Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692092.png" /> into a Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692093.png" /> corresponds a topological imbedding of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692094.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692095.png" />; to a subalgebra of a Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692096.png" /> there corresponds a continuous image of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692097.png" />. The Stone compactum of a free Boolean algebra is a dyadic discontinuum.
+
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.
  
 
{{Anchor|complete}}
 
{{Anchor|complete}}
A Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692098.png" /> is called complete if any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b01692099.png" /> has an upper bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920100.png" /> and a lower bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920101.png" />. This is equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920102.png" /> being extremal (cf. [[Extremally-disconnected space|Extremally-disconnected space]]).
+
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|Extremally-disconnected space]]).
 
{{Anchor|regular}}
 
{{Anchor|regular}}
Subalgebras of a complete Boolean algebra containing the bounds of all their subsets calculated in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920103.png" /> are called ''regular'' subalgebras. The weight of a Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920104.png" /> is the lowest cardinality of a complete generating set, i.e. a set which is not contained in any regular subalgebra other than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920105.png" />. 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.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920106.png" /> (a measure) is defined on it with the following properties: 1) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920107.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920108.png" />; 2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920109.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920110.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920111.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920112.png" />, then
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920113.png" /></td> </tr></table>
+
$$
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920114.png" />. Here, the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920115.png" /> is interpreted as the probability of an event <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920116.png" />. The classical theory of measure and integral can largely be applied to normed Boolean algebras. Normed Boolean algebras have been completely classified [[#References|[4]]], [[#References|[5]]], [[#References|[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.
+
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 [[#References|[4]]], [[#References|[5]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920117.png" />-topology, which, for a normed Boolean algebra, is metrizable, and corresponds to the metric
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920118.png" /></td> </tr></table>
+
$$
 +
\rho (x, y)  = \
 +
\mu [(x \wedge Cy) \lor
 +
(Cx \wedge y)],
 +
$$
  
and is identical with the Tikhonov topology for Boolean algebras of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920119.png" />. In the most general case there need not be a topology compatible with the order in a Boolean algebra.
+
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====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G. Boole,  "The mathematical analysis of logic: being an essay towards a calculus of deductive reasoning" , Macmillan  (1847)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  G. Boole,  "An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities" , Dover, reprint  (1951)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  R. Sikorski,  "Boolean algebras" , Springer  (1969)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  D.A. Vladimirov,  "Boolesche Algebren" , Akademie Verlag  (1978)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  P.R. Halmos,  "Lectures on Boolean algebras" , v. Nostrand  (1963)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  E. Rasiowa,  R. Sikorski,  "The mathematics of metamathematics" , Polska Akad. Nauk  (1963)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  M.H. Stone,  "The theory of representations for Boolean algebras"  ''Trans. Amer. Math. Soc.'' , '''40'''  (1936)  pp. 37–111</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  G. Birkhoff,  "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc.  (1973)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  H. Hermes,  "Einführung in die Verbandstheorie" , Springer  (1967)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  A.N. Kolmogorov,  "Algèbres de Boole métriques complètes" , ''VI Zjazd Mathematyków Polskich'' , Kraków  (1950)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  N. Dunford,  J.T. Schwartz,  "Linear operators. Spectral operators" , '''3''' , Interscience  (1971)</TD></TR><TR><TD valign="top">[12a]</TD> <TD valign="top">  S. Kakutani,  "Concrete representations of abstract <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920120.png" />-spaces and the mean ergodic theorem"  ''Ann. of Math. (2)'' , '''42''' :  2  (1941)  pp. 523–537</TD></TR><TR><TD valign="top">[12b]</TD> <TD valign="top">  S. Kakutani,  "Concrete representations of abstract <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016920/b016920121.png" />-spaces (a characterization of the space of continuous functions)"  ''Ann. of Math. (2)'' , '''42''' :  4  (1941)  pp. 994–1024</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  D. Maharam,  ''Proc. Nat. Acad. Sci. USA'' , '''28'''  (1942)  pp. 108–111</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  G.W. Mackey,  "The mathematical foundations of quantum mechanics" , Benjamin  (1963)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  K. Yosida,  "Functional analysis" , Springer  (1980)</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  K. Kuratowski,  "Topology" , '''2''' , Acad. Press  (1968)  (Translated from French)</TD></TR></table>
+
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G. Boole,  "The mathematical analysis of logic: being an essay towards a calculus of deductive reasoning" , Macmillan  (1847)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  G. Boole,  "An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities" , Dover, reprint  (1951)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  R. Sikorski,  "Boolean algebras" , Springer  (1969)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  D.A. Vladimirov,  "Boolesche Algebren" , Akademie Verlag  (1978)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  P.R. Halmos,  "Lectures on Boolean algebras" , v. Nostrand  (1963)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  E. Rasiowa,  R. Sikorski,  "The mathematics of metamathematics" , Polska Akad. Nauk  (1963)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  M.H. Stone,  "The theory of representations for Boolean algebras"  ''Trans. Amer. Math. Soc.'' , '''40'''  (1936)  pp. 37–111</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  G. Birkhoff,  "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc.  (1973)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  H. Hermes,  "Einführung in die Verbandstheorie" , Springer  (1967)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  A.N. Kolmogorov,  "Algèbres de Boole métriques complètes" , ''VI Zjazd Mathematyków Polskich'' , Kraków  (1950)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  N. Dunford,  J.T. Schwartz,  "Linear operators. Spectral operators" , '''3''' , Interscience  (1971)</TD></TR><TR><TD valign="top">[12a]</TD> <TD valign="top">  S. Kakutani,  "Concrete representations of abstract $(L)$-spaces and the mean ergodic theorem"  ''Ann. of Math. (2)'' , '''42''' :  2  (1941)  pp. 523–537</TD></TR><TR><TD valign="top">[12b]</TD> <TD valign="top">  S. Kakutani,  "Concrete representations of abstract $(M)$-spaces (a characterization of the space of continuous functions)"  ''Ann. of Math. (2)'' , '''42''' :  4  (1941)  pp. 994–1024</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  D. Maharam,  ''Proc. Nat. Acad. Sci. USA'' , '''28'''  (1942)  pp. 108–111</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  G.W. Mackey,  "The mathematical foundations of quantum mechanics" , Benjamin  (1963)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  K. Yosida,  "Functional analysis" , Springer  (1980)</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  K. Kuratowski,  "Topology" , '''2''' , Acad. Press  (1968)  (Translated from French)</TD></TR></table>

Latest revision as of 21:17, 17 January 2021


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

[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 $(L)$-spaces and the mean ergodic theorem" Ann. of Math. (2) , 42 : 2 (1941) pp. 523–537
[12b] S. Kakutani, "Concrete representations of abstract $(M)$-spaces (a characterization of the space of continuous functions)" Ann. of Math. (2) , 42 : 4 (1941) pp. 994–1024
[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)
How to Cite This Entry:
Boolean algebra. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Boolean_algebra&oldid=24193
This article was adapted from an original article by D.A. Vladimirov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article