Boolean algebra

A Boolean algebra is an algebraic structure equipped with two binary operations and a complementation operation, together with distinguished least and greatest elements, commonly denoted 0 and 1. The operations obey laws such as commutativity, associativity and distributivity, as well as complement laws. Although the notation resembles ordinary arithmetic, the operations have their own rules: for example, combining a proposition with itself by OR or AND does not change it.

In the standard two-valued interpretation, 0 represents false and 1 represents true. The operations correspond to logical negation (NOT), conjunction (AND) and disjunction (OR). Thus, an AND statement is true only when both inputs are true, while an OR statement is true when at least one input is true. Boolean algebra lets logical expressions be manipulated systematically while preserving their truth conditions.

Boolean algebra is not limited to two truth values. A collection of subsets of a universe can form a Boolean algebra when it contains the empty set and the whole universe and is closed under union, intersection and complement relative to that universe. In this interpretation, union plays the role of OR, intersection the role of AND, and set complement the role of NOT. The empty set and the whole universe correspond to 0 and 1.

The two-element algebra is the simplest case and provides the familiar truth-table model of propositional logic. More general Boolean algebras allow the same laws to describe relations among sets and other mathematical structures. This connection links the algebra to areas including logic, set theory and topology.

English mathematician George Boole formulated basic rules for an algebra of logic in his 1847 work The Mathematical Analysis of Logic. In 1854, he published An Investigation of the Laws of Thought, a fuller treatment connecting symbolic algebra with logical reasoning. Later mathematicians developed the theory into the abstract algebraic structure now called a Boolean algebra.

A major connection with engineering appeared in Claude E. Shannon's 1938 paper, A Symbolic Analysis of Relay and Switching Circuits. Shannon showed how the states and interconnections of relay circuits could be represented and analyzed with an algebra analogous to the calculus of propositions. This linked logical operations to the practical analysis and simplification of switching networks.

Boolean algebra is used to describe and simplify logical conditions. In digital electronics, logic gates implement Boolean operations on signals representing binary states; combinations of gates form circuits that perform calculations and control functions. A Boolean expression can be translated into a switching circuit, and algebraic identities can help simplify that expression or compare alternative circuit designs.

The theory also has applications beyond digital hardware. Its relationship to propositions and sets makes it useful in mathematical logic and set theory, while broader connections extend to areas such as information theory and probability. In each setting, the same abstract laws can be interpreted in a way suited to the objects being studied.

1847 — George Boole published The Mathematical Analysis of Logic, setting out basic rules for an algebra of logic. 1854 — Boole published An Investigation of the Laws of Thought, a fuller presentation of his logical method. 1938 — Claude Shannon published A Symbolic Analysis of Relay and Switching Circuits, demonstrating a systematic algebraic analysis of switching networks.