Boolean algebra (structure)

In mathematics, a Boolean algebra ( or Boolean Association ) is a special algebraic structure which generalizes the properties of the logical operators AND, OR, NOT, and the properties of the set-theoretical shortcuts average, union, complement. Equivalent to Boolean algebras are Boolean rings emanating from AND and exclusive OR (exclusive OR ) or average and symmetric difference.

• Two-element Boolean algebra 4.1
• 4.2 algebra
• 4.3 Other Examples

The History

The Boolean algebra is named after George Boole, because it goes back to its logical calculus of 1847, in which he applied for the first time algebraic methods in the class logic and propositional logic. Its present form it owes the development by mathematician John Venn, William Stanley Jevons, Charles Peirce, Ernst Schröder and Giuseppe Peano. In Boole's original algebra multiplication corresponds to AND, the addition, however, neither the exclusive nor the exclusive OR inclusive OR ( "at least one of them is true"). The Boole - called successor went against it from the inclusive OR: Schröder developed in 1877 the first formal system of axioms of Boolean algebra in additive notation. Peano brought it in 1888 in its present form (see below) and led the symbols and. The propositional OR sign comes from Russell 1906; Arend Heyting 1930 led the symbols and a. The name " Boolean algebra " or "boolean algebra " coined Henry Maurice Sheffer until 1913. 's Exclusive EITHER - OR, the Boole's original algebra comes closer, put only Ivan Ivanovich Žegalkin 1927 the Boolean ring based on the Marshall Harvey Stone in 1936 the name gave.

Definition

The redundant system of axioms of Peano ( derived with additional axioms ) characterizes a Boolean algebra as a set with zero element 0 and unit element 1, on which the two -digit links and and a one-digit shortcut are defined by the following axioms ( original numbering of Peano ):

Each formula in a Boolean algebra has a dual formula that conversely arises by replacing 0 by 1 and and. Is that a valid formula, then so is its dual formula, as in the Peano axioms, respectively ( n) and ( n ').

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

Definition as an association

A Boolean algebra is a distributive complementary association. This definition is only for the links, and then comprises the existence of 0 and 1 and the independent axioms (1) (1 ' ) (2) (2' ) (11) (11 ' ) (4) (9) ( 9 ') of the equivalent system of axioms of Peano. On a Boolean algebra can be defined as in any association by a partial order; with her have two elements a supremum and an infimum. In the set-theoretic interpretation is equivalent to the subset order.

Definition to Huntington

A more compact definition is the axiom system to Huntington:

A Boolean algebra is a set with two links, such that for all elements, and the following applies:

• Commutativity: (1) and (1 ')
• Distributivity ( 4) and (4 ')
• Existence of third elements: there are elements, and such that ( 5) and (5 ')
• Existence of complements: for each, so that (9) and (9 ')

( The sometimes separately required seclusion of the links is here already in the formulation of " shortcuts " included. )

From these four axioms can be any law above and other derived. Also can be derived from the axiom system, which initially requires only the existence of neutral and complementary elements whose uniqueness derived, that is, it can only have one element, an identity element, and give to each element only a complement.

Spelling

The operators of Boolean algebras are listed in different ways. In the logical interpretation as conjunction, disjunction and negation to write it as, and and verbalized it as AND, OR, NOT or AND, OR, NOT. In the set-theoretic interpretation as the average, union and complement as they are, and write (). To emphasize the abstraction in general Boolean algebra symbol pairs as well, or may be used. Mathematicians occasionally write · for AND and for OR (due to their remote similarity to multiplication and addition of other algebraic structures ) and set NOT an overline, a tilde ~, or an appended prime characters dar. This notation is also in switching algebra description of the Boolean function digital circuits usual; there we often use the defined shortcuts NAND ( NOT AND ), NOR ( NOT OR ) and XOR (EXCLUSIVE OR).

In this article, the operator symbols, and used.

Examples

Two-element Boolean algebra

Boolean algebra, the most important is only the two elements 0 and 1, the links are defined as follows:

This algebra has applications in propositional logic, where 0 is interpreted as "false " and 1 as "true". The links correspond to the logical connectives AND, OR, NOT. Expressions in this algebra are called Boolean expressions.

Also, for digital circuits, this algebra is used and referred to as Boolean algebra. Here 0 and 1 correspond to two states of stress in the switch function of OFF and ON. The input-output behavior of each sorts of 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 each equation in which only variables, 0 and 1 by and linked are exactly fulfilled in any Boolean algebra for each variable assignment when they are in the two-element algebra is satisfied for each variable assignment (which you can simply test ). For example, the following two statements are valid (consensus rules, Eng. Consensus theorem ) of any Boolean algebra:

In propositional logic we call these rules resolution rules.

Algebra

The power set of a set S is with intersection and union to a Boolean algebra. Where 0 is the empty set and 1 = S and the negation of the complement; the special case S = yields the singleton powerset with 1 = 0 Also, each containing S, with respect to union and complement completed portion of the power set of S is a Boolean algebra, which is called a subset of association or algebra. The representation theorem of Stone states that every Boolean algebra is isomorphic (see below ) to a set algebra is. It follows that the thickness of each finite Boolean algebra is a power of two.

About the Venn diagrams illustrating the Boolean algebra laws, such as distributive and de - Morgan's laws. In addition, based on their form as KV diagram a well-known method of systematic simplification of Boolean expressions in the algebra.

Other examples

The set of all finite or koendlichen subsets of forms with intersection and union is a Boolean algebra.

For each natural number n the set of all positive divisors of n gcd and lcm the shortcuts is a distributive limited association. Where 1 is the zero element, and n is the unit element. The association is Boolean if and only if n is square-free. This association is called divider Association of n

Is a ring with identity, then we define the set

All idempotent elements of the center. Use the links

Is a Boolean algebra.

Is a Hilbert space and the set of orthogonal projections onto, then we define two orthogonal projections and

Should be equal to or where. In both cases to a Boolean algebra. The case is in the spectral theory of meaning.

Homomorphisms

A homomorphism between Boolean algebras is a Verbandshomomorphismus, the 0 and 1 maps 0 to 1, ie are all:

It follows that for all a in A. The class of all Boolean algebras is with this Homomorphismenbegriff a category. If a homomorphism f additionally bijective, then that means isomorphism, and and are called isomorphic.

Boolean rings

A different perspective on Boolean algebras consists in the so-called Boolean rings: These are rings with identity which are additionally idempotent, ie meet the Idempotenzgesetz. Each idempotent ring is commutative. The addition in the Boolean ring corresponds to the set-theoretic interpretation of the symmetric difference and propositional logic interpretation of the alternative EITHER - OR ( exclusive OR, XOR ); the multiplication corresponds to the averaging or the conjunction AND.

Boolean rings are always self-inverse, because it is and so that the inverse operation is defined. Because of this property they also own, if 1 and 0 are different, always the characteristics 2 The smallest such Boolean ring is also a body with the following link panels:

The power series ring modulo over this body is also a Boolean ring, as is identified with and provides the idempotence. This algebra has already been used Žegalkin 1927 as a variant of the original algebra of Boole, the basis laid the field of real numbers, which still makes no Boolean ring.

Every Boolean ring corresponds to a Boolean algebra by the following definitions:

Conversely, every Boolean algebra is a Boolean ring by the following definitions:

In addition, a mapping is a homomorphism of Boolean algebras if and only if it is a ring homomorphism Boolean ( with preservation of one) rings.

Representation theorem of Stone

For any topological space the set of all closed open subsets is a Boolean algebra with intersection and union. The representation theorem of Stone, proved by Marshall Harvey Stone, stating that, conversely, for every Boolean algebra is a topological space (more precisely, a Stone space, that is a totally disconnected compact Hausdorff space ) exists in which she as the Boolean algebra closed open sets is realized. The kit even provides a contravariant equivalence between the category of Stone spaces with continuous maps and the category of Boolean algebras and their homomorphisms ( the contravariance explained by the fact that the for ever, the Boolean algebra of closed open sets in by archetype education from results, not vice versa through the formation of the image).