Boolean Algebra (original) (raw)

Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology

Alphabetical Index New in MathWorld

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 b(A) of a set A is the set of subsets of A 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 b(A) is called a Boolean function. There are 2^(2^n) Boolean functions in a Boolean algebra of order n (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.

BooleanAlgebras

Boolean algebras have a recursive structure apparent in the Hasse diagrams illustrated above for Boolean algebras of orders n=2, 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 n-1 elements (Skiena 1990, pp. 169-170). The Hasse diagram for the Boolean algebra of order n is implemented as BooleanAlgebra[_n_] in the Wolfram Language package Combinatorica` . It is isomorphic to the n-hypercube graph.

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

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

a ^ a=a v a=a, (1)

the commutative laws

and the associative laws

2. The operations satisfy the absorption law

a ^ (a v b)=a v (a ^ b)=a. (6)

3. The operations are mutually distributive

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

5. B has a unary operation a->a^' of complementation, which obeys the laws

(Birkhoff and Mac Lane 1996).

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

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

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

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

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

3a. a v b=b v a.

3b. a ^ b=b ^ a.

4a. a v b ^ c=(a v b) ^ (a v c).

4b. a ^ (b v c)=(a ^ b) v (a ^ c).

5. For every element a there is an element a^' such that a v a^'=U and a ^ a^'=Z.

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

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

1. Commutativity: x v y=y v x.

2. Associativity: (x v y) v z=x v (y v z).

3. Huntington axiom: !(!x v y) v !(!x v !y)=x.

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

!(!(x v y) v !(x v !y))=x. (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).

See also

Boolean Function, Booleans, Huntington Axiom, Hypercube Graph, Maximal Ideal Theorem, Robbins Algebra, Robbins Axiom, Winkler Conditions, Wolfram Axiom Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Bell, E. T. Men of Mathematics. New York: Simon and Schuster, 1986.Birkhoff, G. and Mac Lane, S. A Survey of Modern Algebra, 5th ed. New York: Macmillian, p. 317, 1996.Comtet, L. "Boolean Algebra Generated by a System of Subsets." §4.4 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 185-189, 1974.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, 1933b.Kolata, G. "Computer Math Proof Shows Reasoning Power." New York Times, Dec. 10, 1996.McCune, W. "Robbins Algebras Are Boolean." http://www.cs.unm.edu/~mccune/papers/robbins/.Mendelson, E. Introduction to Boolean Algebra and Switching Circuits. New York: McGraw-Hill, 1973.Sikorski, R. Boolean Algebra, 3rd ed. New York: Springer-Verlag, 1969.Skiena, S.Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990. Wells, C. F. "Boolean Expression Manipulation." http://library.wolfram.com/infocenter/MathSource/4187/.Whitesitt, J. E. Boolean Algebra and Its Applications. New York: Dover, 1995.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1168, 2002.

Referenced on Wolfram|Alpha

Boolean Algebra

Cite this as:

Weisstein, Eric W. "Boolean Algebra." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BooleanAlgebra.html

Subject classifications