Boolean Algebra

A Boolean algebra is a mathematical structure that is similar to a Boolean ring, but that is defined using the meet and join operators instead of the usual addition and multiplication operators. Explicitly, a Boolean algebra is the partial order on subsets defined by inclusion (Skiena 1990, p. 207), i.e., the Boolean algebra of a set is the set of subsets of that can be obtained by means of a finite number of the set operations union (OR), intersection (AND), and complementation (NOT) (Comtet 1974, p. 185). A Boolean algebra also forms a lattice (Skiena 1990, p. 170), and each of the elements of is called a Boolean function. There are Boolean functions in a Boolean algebra of order (Comtet 1974, p. 186).

In 1938, Shannon proved that a two-valued Boolean algebra (whose members are most commonly denoted 0 and 1, or false and true) can describe the operation of two-valued electrical switching circuits. In modern times, Boolean algebra and Boolean functions are therefore indispensable in the design of computer chips and integrated circuits.

Boolean algebras have a recursive structure apparent in the Hasse diagrams illustrated above for Boolean algebras of orders , 3, 4, and 5. These figures illustrate the partition between left and right halves of the lattice, each of which is the Boolean algebra on elements (Skiena 1990, pp. 169-170). The Hasse diagram for the Boolean algebra of order is implemented as BooleanAlgebra[n] in the Wolfram Language package Combinatorica` . It is isomorphic to the -hypercube graph.

A Boolean algebra can be formally defined as a set of elements , , ... with the following properties:

1. has two binary operations, (logical AND, or "wedge") and (logical OR, or "vee"), which satisfy the idempotent laws

(1)

the commutative laws

			(2)
			(3)

and the associative laws

			(4)
			(5)

2. The operations satisfy the absorption law

(6)

3. The operations are mutually distributive

			(7)
			(8)

4. contains universal bounds (the empty set) and (the universal set) which satisfy

			(9)
			(10)
			(11)
			(12)

5. has a unary operation of complementation, which obeys the laws

			(13)
			(14)

(Birkhoff and Mac Lane 1996).

In the slightly archaic terminology of (Bell 1986, p. 444), a Boolean algebra can be defined as a set of elements , , ... with binary operators (or ; logical OR) and (or ; logical AND) such that

1a. If and are in the set , then is in the set .

1b. If and are in the set , then is in the set .

2a. There is an element (zero) such that for every element .

2b. There is an element (unity) such that for every element .

3a. .

3b. .

4a. .

4b. .

5. For every element there is an element such that and .

6. There are at least two distinct elements in the set .

Huntington (1933ab) presented the following basis for Boolean algebra:

1. Commutativity: .

2. Associativity: .

3. Huntington axiom: .

H. Robbins then conjectured that the Huntington axiom could be replaced with the simpler Robbins axiom,

(15)

The algebra defined by commutativity, associativity, and the Robbins axiom is called Robbins algebra. Computer theorem proving demonstrated that every Robbins algebra satisfies the second Winkler condition, from which it follows immediately that all Robbins algebras are Boolean (McCune, Kolata 1996).

Wolfram Web Resources