Boolean Algebra
Boolean algebra is the algebra of two-valued variables, true and false or 1 and 0, in which the basic operations are AND, OR and NOT rather than addition and multiplication of ordinary numbers. Every expression built from those operations can be evaluated by a truth table, a list of its output for every combination of inputs. It began as a nineteenth-century attempt to treat logical reasoning like arithmetic and became, a century later, the working language of digital circuit design, programming conditions, database queries and search engines.
George Boole created the system in two works, in 1847 and 1854. Boole, a self-taught English mathematician who became professor at Queen's College, Cork, published The Mathematical Analysis of Logic in 1847 and, in 1854, An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, usually shortened to The Laws of Thought. He represented classes of things by symbols and showed that logical combination obeyed algebraic rules, with the notable law that applying a selection twice gives the same result as applying it once, x × x = x, which is true only for the values 0 and 1. His original treatment of OR was more restricted than the modern one; later logicians, notably William Stanley Jevons and Charles Sanders Peirce, refined it into the inclusive OR used today. Augustus De Morgan, who published on formal logic in the same period of 1847, gave the two laws that carry his name.
The three operations and De Morgan's laws are all one needs. AND is true only when both inputs are true, OR is true when at least one is, and NOT flips a value. De Morgan's laws say that NOT (A AND B) equals (NOT A) OR (NOT B), and NOT (A OR B) equals (NOT A) AND (NOT B), so any AND can be built from OR and NOT, and vice versa. Together with identities such as A AND 1 = A, A OR 0 = A, and A OR NOT A = 1, these laws let an expression be simplified without changing its meaning. Because NAND, or NOR, alone can build every other function, a single gate type is enough to construct a whole computer, which is why NAND is the unit of choice in flash memory and in many chip libraries.
Claude Shannon's 1937 thesis turned the algebra into engineering. His MIT master's thesis, A Symbolic Analysis of Relay and Switching Circuits, showed that networks of relays could be described by Boolean expressions: switches in series behave like AND, switches in parallel like OR, and a contact that closes when a relay is off like NOT. A circuit designer could therefore write the desired behavior as an expression, simplify it algebraically, and build a circuit with fewer relays. The same method transferred from relays to tubes and transistors. In 1953 Maurice Karnaugh, working at Bell Labs and building on a 1952 chart by Edward Veitch, introduced the Karnaugh map, which lays a truth table on a grid so that adjacent cells differ by one variable and the groups of ones can be read off to minimize the expression by eye.
Boolean algebra is not just for gates, and its everyday uses are more familiar than they look. A programming condition such as logged in AND NOT banned is a Boolean expression, a bitwise operation on a computer register applies AND, OR or XOR to 32 or 64 bits at once, and permission masks, flags and graphics blending use them heavily. Library catalogs and web search ask users to combine terms with AND, OR and NOT; the SQL WHERE clause combines predicates the same way. Hardware description languages like Verilog describe chips with Boolean equations, and synthesis tools simplify them automatically. In AI hardware, the arithmetic units are ultimately assemblies of these gates, and satisfiability solvers apply Boolean reasoning to verify the chips themselves.
Common pitfalls are the difference between Boolean and ordinary algebra, and the third state that real systems add. In Boolean algebra, 1 + 1 equals 1 under OR, not 2, and A AND A equals A; the familiar rules of arithmetic do not all carry over. Another trap is operator precedence: NOT binds tighter than AND, which binds tighter than OR, so an unparenthesized search query often does not mean what a person intended. SQL adds a third value, NULL, giving three-valued logic in which a comparison with NULL is neither true nor false, so identities like A OR NOT A = 1 can fail in a query. Hardware has a similar extra state, such as an unknown or high-impedance signal.
Read Boolean algebra as the exact grammar of yes-or-no reasoning: a nineteenth-century idea about the laws of thought that Shannon showed matches the behavior of switches, which is why the same few rules govern a logic gate, a database filter and a search box.