Boolean algebra

Lore & Background

A precursor of Boolean algebra was Gottfried Wilhelm Leibniz's algebra of concepts, which is deductively equivalent to the Boolean algebra of sets. Boole's algebra predated modern developments in abstract algebra and mathematical logic but is seen as connected to the origins of both fields. In the late 19th century, it was perfected by Jevons, Schröder, Huntington, and others, reaching the modern conception of an abstract mathematical structure. M. H.

Reader's Guide

Boolean algebra has been fundamental in the development of digital electronics and is provided for in all modern programming languages. It is also used in set theory and statistics. In the 1930s, Claude Shannon applied Boole's algebra to switching circuits, introducing switching algebra as a way to analyze and design circuits using logic gates, casting it as the two-element Boolean algebra. Efficient implementation of Boolean functions is a fundamental problem in combinational logic circuit design; modern electronic design automation tools for VLSI circuits often rely on binary decision diagrams (BDD) for logic synthesis and formal verification. Logic sentences expressible in classical propositional calculus have an equivalent expression in Boolean algebra, though it cannot capture formulas with quantifiers. The Boolean satisfiability problem (SAT) is the first problem shown to be NP-complete and is important to theoretical computer science.

Did You Know?

• Claude Shannon introduced switching algebra as the two-element Boolean algebra in the 1930s.