Boolean Algebra

A mathematical object which is similar to a Boolean Ring, but which uses the meet and join operators instead of the usual addition and multiplication operators. A Boolean algebra is a set $B$ of elements $a$, $b$, ... with Binary Operators $+$ and $\cdot$ such that

1a. If $a$ and $b$ are in the set $B$, then $a+b$ is in the set $B$.

1b. If $a$ and $b$ are in the set $B$, then $a\cdot b$ is in the set $B$.

2a. There is an element $Z$ (zero) such that $a+Z=a$ for every element $a$.

2b. There is an element $U$ (unity) such that $a\cdot U=a$ for every element $a$.

3a. $a+b=b+a$

3b. $a\cdot b=b\cdot a$

4a. $a+b\cdot c=(a+b)(a+c)$

4b. $a\cdot (b+c)=a\cdot b+a\cdot c$

5. For every element $a$ there is an element $a'$ such that $a+a'=U$ and $a\cdot a'=Z$.

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

(Bell 1937, p. 444).

In more modern terms, a Boolean algebra is a Set $B$ of elements $a$, $b$, ... with the following properties:

1. $B$ has two binary operations, $\wedge$ (Wedge) and $\vee$ (Vee), which satisfy the Idempotent laws

$$a\wedge a=a\vee a=a,$$

the Commutative laws

$$a\wedge b=b\wedge a$$

$$a\vee b=b\vee a,$$

and the Associative laws

$$a\wedge(b\wedge c)=(a\wedge b)\wedge c$$

$$a\vee(b\vee c)=(a\vee b)\vee c.$$

2. The operations satisfy the Absorption Law

$$a\wedge(a\vee b)=a\vee(a\wedge b)=a.$$

3. The operations are mutually distributive

$$a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c)$$

$$a\vee(b\wedge c)=(a\vee b)\wedge(a\vee c).$$

4. $B$ contains universal bounds $O, I$ which satisfy

$$O\wedge a=O$$

$$O\vee a=a$$

$$I\wedge a=a$$

$$I\vee a=I.$$

5. $B$ has a unary operation $a\to a'$ of complementation which obeys the laws

$$a\wedge a'=O$$

$$a\vee a'=I$$

(Birkhoff and Mac Lane 1965). Under intersection, union, and complement, the subsets of any set $I$ form a Boolean algebra.

Huntington (1933a, b) presented the following basis for Boolean algebra,

1. Commutativity. $x + y = y + x$.

2. Associativity. $(x + y) + z = x + (y + z)$.

3. Huntington Equation. $n(n(x) + y) + n(n(x) + n(y)) = x$.

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

$$n(n(x + y) + n(x + n(y))) = x.$$

The Algebra defined by commutativity, associativity, and the Robbins Equation 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.

References

Bell, E. T. Men of Mathematics. New York: Simon and Schuster, 1986.

Birkhoff, G. and Mac Lane, S. A Survey of Modern Algebra, 3rd ed. New York: Macmillian, p. 317, 1965.

Halmos, P. Lectures on Boolean Algebras. Princeton, NJ: Van Nostrand, 1963.

Huntington, E. V. ``New Sets of Independent Postulates for the Algebra of Logic.'' Trans. Amer. Math. Soc. 35, 274-304, 1933a.

Huntington, E. V. ``Boolean Algebras: A Correction.'' Trans. Amer. Math. Soc. 35, 557-558, 1933.

McCune, W. ``Robbins Algebras are Boolean.'' http://www-unix.mcs.anl.gov/~mccune/papers/robbins/.