Boolean Algebra

Boolean Algebra, branch of mathematics having laws and properties similar to, but different from, those of ordinary high school algebra. Formally a Boolean algebra is a mathematical system consisting of a set of elements, which may be called B, together with two binary operations, which may be denoted by the symbols Å and Ä. These operations are defined on the set B and satisfy the following axioms:

1. Å and Ä are both commutative operations. That is, for any elements x, y of the set B, it is true that xÅY = yÅx and xÄy = yÄx.

2. Each of the operations Å and Ä distributes over the other. That is, for any elements x, y, and z of the set B, it is true that xÅ (yÄz) = (xÅy) Ä(xÅz), and xÄ (yÅz) = (xÄy) Å (xÄz).

3. There exists in the set B a distinct identity element for each of the operations Å and Ä. These elements are usually denoted by the symbols 0 and 1 such that 0 ≠ 1, and have the property that 0 Åx = x and 1 Äx = x for any element x in the set B.

4. For each element x in the set B there exists a distinct corresponding element called the complement of x, usually denoted by the symbol x’. With respect to the operations Å and Ä, the element x’ has the property that xÅx’ = 1 and x Äx’ = 0.

A Boolean algebra may have other sets of axioms, all of which may be shown to be equivalent to those just given. The axioms given here are essentially those first published by the American mathematician Edward Huntington in Postulates for the Algebra of Logic (1904). The first treatment of the subject was given in 1854 by the English mathematician George Boole. It is possible to denote the operations Å and Ä by any two symbols; +, Ú, and È are sometimes used instead of Å, and ×, ^, Ç, ·, and O instead of Ä.

As an example of a Boolean algebra, consider any set X and let P(X) stand for the collection of all possible subsets of the set X. P(X) is sometimes called the power set of the set X. P(X), together with ordinary set union (È) and set intersection (Ç), forms a Boolean algebra. In fact, every Boolean algebra may be represented as an algebra of sets.

From the symmetry of the axioms with respect to the two operations and their respective identities, one is able to prove the so-called principle of duality. This principle asserts that any algebraic statement deducible from the axioms of Boolean algebra remains true if the operations Å and Ä and the identities 1 and 0 are interchanged throughout the statement. Of the many theorems that can be deduced from the axioms of a Boolean algebra, De Morgan's laws, that (xÅy)’ = x’Äy’ and that (xÄy)’ = x’Åy’, are particularly noteworthy.

The elements that are contained in the set B of a Boolean algebra may be abstract objects, or concrete things such as numbers, propositions, sets, or electrical networks. In Boole's original development, the elements of a Boolean algebra were a collection of propositions, or simple declarative sentences having the property that they were either true or false but not both. The operations were essentially conjunction and disjunction, denoted by the symbols ^ and Ú respectively. If x and y represent two propositions, then the expression xÚy (read x or y) would be true if and only if either x or y or both were true. The statement x ^ y (read x and y) would be true if and only if both x and y were true. In this type of Boolean algebra, the complement of an element or proposition is simply the negation of the statement.

A Boolean algebra of propositions and a Boolean algebra of sets are closely connected. For example, let p be the statement, “The ball is blue,” and let P be the set of all elements for which the statement p is true, that is, the set of all blue balls. P is called the truth set for the proposition p. Indeed, if P and Q are the truth sets for statements p and q, then the truth set for the statement pÚq is clearly P È Q and for p ^ q the truth set is P Ç Q.

Boolean algebra has many practical applications in the physical sciences, in electric-circuit theory and particularly in the field of computers.

As an example of an application of Boolean algebra in electrical-circuit theory, let p and q denote two propositions, that is, declarative sentences that are either true or false but not both. If each of the propositions p and q is associated with a switch that will be closed if the proposition is true, and open if the proposition is false, then the statement p ^ q may be represented by connecting the switches in series. The current will flow in this circuit if and only if both switches are closed, that is, if both p and q are true. Similarly, a circuit with switches connected in parallel can be used to represent the statement pÚq. In this case the current will flow if either p or q or both are true and the respective switches are closed. More complicated statements give rise to more complex switching circuits.