Boolean algebra

In mathematics , a Boolean algebra (or a Boolean lattice ) is a special algebraic structure that generalizes the properties of the logical operators AND, OR, NOT as well as the properties of the set- theoretic operations of average, union, complement. Equivalent to Boolean algebras are Boolean rings based on AND and EITHER-OR (exclusive-OR) or average and symmetrical difference.

Boolean algebra is the basis for the development of digital electronics and is made available in all modern programming languages. It is also used in sentence theory and statistics.

Operators

${\displaystyle \wedge }$	AND
${\displaystyle \lor }$	OR
${\displaystyle \neg }$	NOT

history

Boolean algebra is named after George Boole because it goes back to his logic calculus from 1847, in which he first used algebraic methods in class logic and propositional logic . It owes its current form to further development by mathematicians such as John Venn , William Stanley Jevons , Charles Peirce , Ernst Schröder and Giuseppe Peano . In Boole's original algebra , multiplication corresponds to AND, but addition corresponds to neither the exclusive EITHER-OR nor the inclusive OR (“at least one of both is true”). The Boolean successors mentioned, on the other hand, were based on the inclusive OR: Schröder developed the first formal axiom system of a Boolean algebra in additive notation in 1877. Peano brought his system into its current form in 1888 (see below) and introduced the symbols and . The propositional OR sign is from Russell 1906; Arend Heyting introduced the symbols and in 1930 . ${\displaystyle \cap }$ ${\displaystyle \cup }$ ${\displaystyle \lor }$ ${\displaystyle \wedge }$ ${\displaystyle \neg }$

The name of Boolean algebra ( English boolean algebra ) coined Henry M. Sheffer until 1913. The exclusive exclusive OR that Boole's algebra is original closer, put only Ivan Ivanovich Žegalkin 1927 the Boolean ring based on the Marshall Harvey Stone in 1936 gave the name.

definition

The redundant system of axioms by Peano (with additional derivable axioms) characterizes a Boolean algebra as a set with zero element 0 and one element 1, on which the two-digit links and and a one- digit link are defined, by the following axioms (original numbering from Peano): ${\displaystyle \wedge }$ ${\displaystyle \lor }$ ${\displaystyle \neg }$

Commutative laws	(1)	${\displaystyle a\land b=b\land a}$	(1')	${\displaystyle a\lor b=b\lor a}$
Associative Laws	(2)	${\displaystyle (a\land b)\land c=a\land (b\land c)}$	(2 ')	${\displaystyle (a\lor b)\lor c=a\lor (b\lor c)}$
Idempotence laws	(3)	${\displaystyle a\land a=a}$	(3 ')	${\displaystyle a\lor a=a}$
Distributive laws	(4)	${\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}$	(4 ')	${\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)}$
Laws of neutrality	(5)	${\displaystyle a\land 1=a}$	(5 ')	${\displaystyle a\lor 0=a}$
Extremal laws	(6)	${\displaystyle a\land 0=0}$	(6 ')	${\displaystyle a\lor 1=1}$
Double negation law (involution)	(7)	${\displaystyle \neg (\neg a)=a}$
De Morgan's Laws	(8th)	${\displaystyle \neg (a\land b)=\neg a\lor \neg b}$	(8th')	${\displaystyle \neg (a\lor b)=\neg a\land \neg b}$
Complementary laws	(9)	${\displaystyle a\land \neg a=0}$	(9 ')	${\displaystyle a\lor \neg a=1}$
Laws of duality	(10)	${\displaystyle \neg 0=1}$	(10 ')	${\displaystyle \neg 1=0}$
Absorption laws	(11)	${\displaystyle a\lor (a\land b)=a}$	(11 ')	${\displaystyle a\land (a\lor b)=a}$

Every formula in a Boolean algebra has a dual formula that is created by replacing 0 with 1 and with and vice versa. If one formula is valid, then it is also its dual formula, as in the Peano axiom system respectively (n) and (n '). ${\displaystyle \wedge }$ ${\displaystyle \lor }$

The complements have nothing to do with inverse elements , because the connection of an element with its complement provides the neutral element of the other connection.

Definition as an association

A Boolean algebra is a distributive complementary lattice . This definition is based only on the connections and and includes the existence of 0, 1 and and the independent axioms (1) (1 ') (2) (2') (11) (11 ') (4) (9) ( 9 ') of the equivalent axiom system of Peano. In a Boolean algebra, as in any lattice, it can be defined by a partial order ; in her two elements each have a supremum and an infimum. In the set-theoretical interpretation is equivalent to the partial set order . ${\displaystyle \wedge }$ ${\displaystyle \lor }$ ${\displaystyle \neg }$ ${\displaystyle a\leq b\iff a=a\land b}$ ${\displaystyle \leq }$ ${\displaystyle \subseteq }$

Huntington's disease definition

A more compact definition is the Huntington's system of axioms :

A Boolean algebra is a set with two links , so that for all elements , and : ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle a\in B}$ ${\displaystyle b\in B}$ ${\displaystyle c\in B}$

• Commutativity: (1) and (1 ')
• Distributivity: (4) and (4 ')
• Existence of neutral elements: There are elements and such that (5) and (5 ') ${\displaystyle 0\in B}$ ${\displaystyle 1\in B}$
• Existence of complements: for each there is such that (9) and (9 ') ${\displaystyle a\in B}$ ${\displaystyle \neg a\in B}$

(The closeness of the links, which is sometimes required separately, is already contained in the phrase "links to ".) ${\displaystyle B}$

All of the above-mentioned laws and others can also be derived from these four axioms. Also from the axiom system, which initially only requires the existence of neutral and complementary elements, their uniqueness can be derived, i.e. That is, there can only be one zero element, one one element, and only one complement for each element.

Notation

The operators of Boolean algebras are noted in various ways. In the logical interpretation as conjunction, disjunction and negation, they are written as , and and verbalized as AND, OR, NOT or AND, OR, NOT. In the set-theoretical interpretation as intersection, union and complement, they are written as , and ( ). To emphasize abstraction in general Boolean algebra, pairs of symbols such as , or , are also used. ${\displaystyle \wedge }$ ${\displaystyle \lor }$ ${\displaystyle \neg }$ ${\displaystyle \cap }$ ${\displaystyle \cup }$ ${\displaystyle ^{\complement }}$ ${\displaystyle A^{\complement }}$ ${\displaystyle \sqcap }$ ${\displaystyle \sqcup }$ ${\displaystyle \ast }$ ${\displaystyle \circ }$

Mathematicians occasionally write “·” for AND and “+” for OR (because of their distant similarity to multiplication and addition of other algebraic structures) and do NOT represent with an overline, a tilde ~, or a trailing prime sign . This notation is also in the switching algebra digital to describe the boolean function circuits usual; there one often uses the definable links NAND (NOT AND), NOR (NOT OR) and XOR (EXCLUSIVE OR).

This article uses the , and operator symbols. ${\displaystyle \wedge }$ ${\displaystyle \lor }$ ${\displaystyle \neg }$

Examples

Two-element Boolean algebra

The most important Boolean algebra has only the two elements 0 and 1. The links are defined as follows:

conjunction ${\displaystyle \wedge }$ 0 1 0 0 0 1 0 1

Disjunction ${\displaystyle \lor }$ 0 1 0 0 1 1 1 1

negation   ${\displaystyle \neg }$ 0 1 1 0

This algebra has uses in propositional logic , where 0 is interpreted as "false" and 1 as "true". The links correspond to the logical links AND, OR, NOT. Expressions in this algebra are called Boolean expressions . ${\displaystyle {\land },{\lor },{\neg }}$

This algebra is also used for digital circuits and is known as switching algebra . Here 0 and 1 correspond to two voltage states in the switch function of OFF and ON. The input-output behavior of any possible digital circuit can be modeled by a Boolean expression.

The two-element Boolean algebra is also important for the theory of general Boolean algebras, since every equation in which only variables, 0 and 1 are linked by and , is fulfilled in any Boolean algebra for every variable assignment if and only if it is in the two-element algebra is fulfilled for every variable assignment (which can be easily tested). For example, the following two statements (consensus rules apply Engl .: Consensus theorem ) of any Boolean algebra: ${\displaystyle {\land },}$ ${\displaystyle \lor }$ ${\displaystyle \neg }$

${\displaystyle (a\lor b)\land (\neg a\lor c)\land (b\lor c)=(a\lor b)\land (\neg a\lor c)}$

${\displaystyle (a\land b)\lor (\neg a\land c)\lor (b\land c)=(a\land b)\lor (\neg a\land c)}$

In propositional logic , these rules are called resolution rules .

Set algebra

The power set of a set becomes a Boolean algebra with intersection, union and complement , where 0 is the empty set and 1 is the whole set . The special case results in the one-element power set with 1 = 0. Each containing sub-range of the power set of closed with regard to union and complement is also a Boolean algebra, which is referred to as a subset lattice or set algebra . The representation theorem of Stone states that every Boolean algebra isomorphic (see below) is an algebra. It follows that the power of any finite Boolean algebra is a power of two. ${\displaystyle S}$ ${\displaystyle A^{\complement }:=\{x\mid \left(x\in S\right)\land \left(x\not \in A\right)\}}$ ${\displaystyle \emptyset }$ ${\displaystyle S}$ ${\displaystyle S=\emptyset }$ ${\displaystyle S}$ ${\displaystyle S}$

The set algebra uses the Venn diagrams to illustrate Boolean laws, for example distributive and de Morgan's laws. In addition, a well-known method of systematic simplification of Boolean expressions in switching algebra is based on its form as a KV diagram .

Further examples of Boolean set algebras come from topology . The set of closed open sets of a topological space forms a Boolean algebra with the usual operations for the union, the intersection and the complement of sets. The regularly closed sets and the regularly open sets represent with the respective regularized set operations , and also Boolean algebras. ${\displaystyle \cap ^{\ast }}$ ${\displaystyle \cup ^{\ast }}$ ${\displaystyle \mathrm {C} ^{\ast }}$

Other examples

The set of all finite or finite subsets of forms a Boolean algebra with intersection and union. ${\displaystyle \mathbb {N} _{0}}$

For every natural number n the set of all positive factors of n with the links gcd and lcm is a distributive bounded lattice. 1 is the zero element and n is the one element. The lattice is Boolean if and only if n is square-free . This association is called the divisor association of n .

If a ring is one element, then we define the set ${\displaystyle R}$

${\displaystyle A=\{e\in R\mid e^{2}=e{\text{ und }}ex=xe{\text{ für alle }}x\in R\}}$

of all idempotent elements of the center . With the shortcuts

${\displaystyle e\lor f=e+f-ef,\quad e\land f=ef}$

becomes a Boolean algebra. ${\displaystyle A}$

Is a Hilbert space and the amount of orthogonal projections on , then one defined for two orthogonal and ${\displaystyle H}$ ${\displaystyle P(H)}$ ${\displaystyle H}$ ${\displaystyle P}$ ${\displaystyle Q}$

${\displaystyle P\lor Q=P+Q-nPQ,\quad P\land Q=PQ}$,

where should be equal or . Either way it becomes a Boolean algebra. The case matters in spectral theory. ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle 2}$ ${\displaystyle P(H)}$ ${\displaystyle n=2}$

Homomorphisms

A homomorphism between Boolean algebras is a union homomorphism that maps 0 to 0 and 1 to 1; This means that applies to all : ${\displaystyle A,B}$ ${\displaystyle f\colon A\to B}$ ${\displaystyle x,y\in A}$

• ${\displaystyle f(x\land y)=f(x)\land f(y)}$
• ${\displaystyle f(x\lor y)=f(x)\lor f(y)}$
• ${\displaystyle f(0)=0,\quad f(1)=1}$

It follows that for all a in A . The class of all Boolean algebras becomes a category with this homomorphism concept . If a homomorphism f is also bijective , then it is called isomorphism , and and are called isomorphic . ${\displaystyle f(\neg a)=\neg f(a)}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$

Boolean rings

Another way of looking at Boolean algebras is what are known as Boolean rings : These are rings with one element that are also idempotent , i.e. they fulfill the idempotency law. Every idempotent ring is commutative . The addition in the Boolean ring corresponds to the symmetrical difference in the set-theoretical interpretation and to the alternative EITHER-OR (exclusive-OR, XOR ) in the propositional interpretation ; the multiplication corresponds to the formation of the average or the conjunction AND. ${\displaystyle a\cdot a=a}$

Boolean rings are always self-inverse, because and , so that the inverse operation can be defined. Because of this property, if 1 and 0 are different, they always have the characteristic 2. The smallest such Boolean ring is at the same time a body with the following tables: ${\displaystyle \,a+a=0}$ ${\displaystyle \,-a=a}$

${\displaystyle \cdot }$ 0 1 0 0 0 1 0 1

${\displaystyle +}$ 0 1 0 0 1 1 1 0

The power series ring modulo above this body is also a Boolean ring, because it is identified with and provides the idempotence. Žegalkin used this algebra as early as 1927 as a variant of Boole's original algebra, which was based on the field of real numbers, which does not yet result in a Boolean ring. ${\displaystyle \,x\cdot x+x}$ ${\displaystyle \,x\cdot x+x}$ ${\displaystyle \,0}$

Every Boolean ring corresponds to a Boolean algebra by the following definitions: ${\displaystyle (R,{+},{-},{\cdot },1,0)}$ ${\displaystyle (R,{\land },{\lor },{\neg },1,0)}$

${\displaystyle x\lor y=x+y+xy}$

${\displaystyle x\land y=xy}$

${\displaystyle \neg x=x+1}$

Conversely, every Boolean algebra becomes a Boolean ring by the following definitions: ${\displaystyle (A,{\land },{\lor },{\neg },1,0)}$ ${\displaystyle (A,{+},{-},{\cdot },1,0)}$

${\displaystyle a+b=(a\land \neg b)\lor (b\land \neg a)}$

${\displaystyle \,-a=a}$

${\displaystyle a\cdot b=a\land b}$

Furthermore, a mapping is a homomorphism of Boolean algebras if and only if it is a ring homomorphism (with preservation of one) of Boolean rings. ${\displaystyle f\colon A\to B}$

Representation set by Stone

→ Main article : Representation set for Boolean algebras

For any topological space , the set of all closed open subsets is a Boolean algebra with intersection and union. Stone's representation theorem, proven by Marshall Harvey Stone , says that, conversely, for every Boolean algebra there is a topological space (more precisely a Stone space , i.e. a totally disconnected , compact Hausdorff space ) in which it is its Boolean algebra of closed open sets is realized. The theorem even provides a contravariant equivalence between the category of Stone spaces with continuous mappings and the category of Boolean algebras with their homomorphisms (the contravariance is explained by the fact that for continuous the Boolean algebra of closed open sets is derived from the formation of an archetype from that of results, not the other way around by forming the image). ${\displaystyle f\colon X\to Y}$ ${\displaystyle X}$ ${\displaystyle Y}$

See also

• Bitwise operator
• Boolean function
• Boolean differential calculus
• Boolean operator
• Boolean retrieval
• Half ring
• Heyting algebra
• Logic gate
• Logical connection
• Relational algebra

literature

• Marshall Harvey Stone : The Theory of Representations for Boolean Algebras. In: Transactions of the American Mathematical Society. 40, 1936, ISSN  0002-9947 , pp. 37-111.
• DA Vladimirov: Boolean algebras (= mathematical textbooks and monographs. Division 2: Mathematical monographs. Vol. 29, ISSN  0076-5430 ). Edited in German by G. Eisenreich . Akademie-Verlag, Berlin 1972.

Web links

Wikiversity: A lecture on Boolean algebras as part of a discrete math  course - course materials

• J. Donald Monk:  The Mathematics of Boolean Algebra. In: Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy .
• Online calculator for simplifying expressions using the axioms of boolean algebra.

Individual evidence

1. ↑ Givant, Steven; Halmos, Paul (2009). Introduction to Boolean Algebras. Undergraduate Texts in Mathematics, Springer. ISBN 978-0-387-40293-2
2. ↑ Ernst Schröder: The operating group of the logic calculus . Leipzig 1877.
3. ^ ^{A b} Giuseppe Peano: Calcolo geometrico . Bocca, Torino, 1888. Excerpt in: G. Peano: Opere scelte II, Rome 1958, pp. 3-19, there p. 5f the system of axioms.
4. ^ Bertrand Russell: The Theory of Implication. In: American Journal of Mathematics. Baltimore 28.1906, pp. 159-202. ISSN  0002-9327