Boolean algebra is a branch of algebra that deals with variables that have only two possible values: true (1) and false (0). It was introduced by George Boole in the 19th century and forms the foundation of digital logic design, computer science, and set theory. Boolean algebra uses logical operations such as conjunction (AND), disjunction (OR), and negation (NOT), and is governed by a set of laws including commutativity, associativity, distributivity, and De Morgan's theorems.
1 Fundamentals
1.1 Definition and axioms
Boolean algebra is an algebraic structure defined by a set \(B\) equipped with two binary operations (usually denoted \(\land\) for AND and \(\lor\) for OR) and one unary operation ( \(\lnot\) for NOT) satisfying a set of axioms: closure, associativity, commutativity, distributivity, identity elements (0 for OR, 1 for AND), and complementation (every element has a unique complement).
1.2 Basic operations
Three fundamental operations define Boolean algebra:
1.2.1 Logical conjunction (AND)
The AND operation yields true (1) only if both operands are true. Denoted by \(\land\) or multiplication, it follows \(1 \land 1 = 1\), \(1 \land 0 = 0\), \(0 \land 1 = 0\), \(0 \land 0 = 0\).
1.2.2 Logical disjunction (OR)
OR yields true if at least one operand is true. Denoted by \(\lor\) or addition, it follows \(1 \lor 1 = 1\), \(1 \lor 0 = 1\), \(0 \lor 1 = 1\), \(0 \lor 0 = 0\).
1.2.3 Logical negation (NOT)
NOT is a unary operation that flips the value: \(\lnot 1 = 0\) and \(\lnot 0 = 1\). It is also called inversion or complement.
1.3 Truth tables
A truth table lists all possible combinations of input values and the corresponding output for a Boolean function. For an \(n\)-variable function, the table has \(2^n\) rows. For example, AND, OR, and NOT each have simple truth tables.
1.4 Boolean variables and constants
Variables in Boolean algebra take only values 0 or 1. Constants are 0 (false) and 1 (true). Expressions are built from variables, constants, and operations.
2 Algebraic structure
2.1 Boolean algebra as a lattice
A Boolean algebra is a distributive complemented lattice. Under the partial order defined by \(a \le b\) iff \(a \land b = a\), the operations \(\land\) and \(\lor\) correspond to meet and join.
2.1.1 Distributive lattice properties
The distributive laws \(a \land (b \lor c) = (a \land b) \lor (a \land c)\) and \(a \lor (b \land c) = (a \lor b) \land (a \lor c)\) hold, distinguishing Boolean algebras from general lattices.
2.1.2 Complemented lattice properties
Every element \(a\) has a unique complement \(\lnot a\) such that \(a \land \lnot a = 0\) and \(a \lor \lnot a = 1\). This property ensures boundedness.
2.2 Duality principle
Every Boolean identity remains valid if all \(\land\) and \(\lor\) are swapped and constants 0 and 1 are interchanged. This duality simplifies proofs and design.
2.3 Boolean expressions and formulas
Expressions are built from variables, constants, and operations using parentheses to indicate order of evaluation.
2.3.1 Literals, terms, and clauses
A literal is a variable or its complement. A term is a product (AND) of literals; a clause is a sum (OR) of literals. Terms and clauses are used to represent functions.
2.3.2 Canonical forms
Every Boolean function can be expressed uniquely in two standard forms:
2.3.2.1 Sum of products (SOP)
An SOP expression is an OR of AND terms (minterms). Each minterm includes every variable or its complement exactly once.
2.3.2.2 Product of sums (POS)
A POS expression is an AND of OR terms (maxterms). Each maxterm includes every variable or its complement exactly once.
3 Laws and theorems
3.1 Basic laws (commutative, associative, distributive)
These laws mirror those of ordinary arithmetic: commutativity \(a \land b = b \land a\), associativity \(a \land (b \land c) = (a \land b) \land c\), and distributivity as given above.
3.2 Identity and complement laws
Identity: \(a \land 1 = a\), \(a \lor 0 = a\). Complement: \(a \land \lnot a = 0\), \(a \lor \lnot a = 1\).
3.3 Idempotent and absorption laws
Idempotent: \(a \land a = a\), \(a \lor a = a\). Absorption: \(a \land (a \lor b) = a\), \(a \lor (a \land b) = a\).
3.4 De Morgan's theorem
De Morgan's laws state \(\lnot (a \land b) = \lnot a \lor \lnot b\) and \(\lnot (a \lor b) = \lnot a \land \lnot b\). These are fundamental for transforming expressions.
3.4.1 Generalized De Morgan's laws
For an arbitrary number of variables, \(\lnot (\bigwedge_i a_i) = \bigvee_i \lnot a_i\) and \(\lnot (\bigvee_i a_i) = \bigwedge_i \lnot a_i\).
3.5 Consensus theorem
The consensus theorem states \(a \land b \lor \lnot a \land c \lor b \land c = a \land b \lor \lnot a \land c\). The term \(b \land c\) is redundant (the consensus term) and can be eliminated.
3.5.1 Dual form of consensus
The dual is \((a \lor b) \land (\lnot a \lor c) \land (b \lor c) = (a \lor b) \land (\lnot a \lor c)\).
4 Simplification and minimization
4.1 Algebraic manipulation
Using Boolean laws and theorems, expressions can be simplified manually by factoring, applying absorption, and eliminating redundant terms. This is informal but often effective.
4.2 Karnaugh maps
A Karnaugh map (K-map) is a graphical tool for minimizing Boolean functions up to six variables. It arranges truth table entries into a grid so that adjacent cells differ by one variable.
4.2.1 Two-variable K-maps
A 2×2 grid covers two input variables. Adjacent cells are combined to form prime implicants.
4.2.2 Three-variable K-maps
An 2×4 grid (or 4×2) covers three variables. Pairs, quads, and octets of adjacent 1s are grouped.
4.2.3 Four-variable K-maps
A 4×4 grid covers four variables. Groups must be rectangular and of size powers of two; wrap-around adjacency is allowed.
4.3 Quine–McCluskey algorithm
The Quine–McCluskey method is an algorithmic tabular approach for minimizing Boolean functions, suitable for computer implementation. It systematically finds all prime implicants.
4.3.1 Prime implicant chart
After listing prime implicants, a chart identifies essential prime implicants and selects a minimal cover. This step may involve row and column dominance.
4.4 Don't-care conditions
Don't-care conditions are input combinations that never occur or for which the output is irrelevant. They can be used to further simplify expressions by treating them as 0s or 1s to form larger groups.
5 Applications
5.1 Digital logic design
Boolean algebra is the mathematical backbone of digital electronics.
5.1.1 Logic gates
Basic gates (AND, OR, NOT) implement the three operations. Additional gates such as NAND, NOR, XOR, and XNOR are derived combinations.
5.1.2 Combinational circuits
Circuits whose outputs depend only on current inputs are combinational. Examples include adders, multiplexers, decoders, and arithmetic logic units (ALUs), all designed using Boolean expressions.
5.1.3 Sequential circuits
Sequential circuits (flip-flops, registers, counters) incorporate memory. Boolean algebra helps in state transition logic and flip-flop input equations.
5.2 Computer programming
Boolean algebra underpins logical control in software.
5.2.1 Boolean data types
Most programming languages include a Boolean type (bool, boolean) with values true and false. Operations &&, ` | , !` correspond to AND, OR, NOT. |
|---|
5.2.2 Conditional expressions
Boolean expressions control branching (if-else), loops (while, for), and conditional assignments via logical operators with short-circuit evaluation.
5.2.3 Bitwise operations
Bitwise AND (&), OR (` | ), NOT (~), and XOR (^`) apply Boolean operations to each bit of integers, used for flags, masks, and low-level data manipulation. |
|---|
5.3 Set theory and logic
Boolean algebra models set operations and logical reasoning.
5.3.1 Boolean ring correspondence
Every Boolean algebra can be turned into a Boolean ring by defining addition as XOR and multiplication as AND. Conversely, every Boolean ring yields a Boolean algebra.
5.3.2 Propositional calculus
Classical propositional logic is a Boolean algebra where atomic propositions are variables, connectives are operations, and tautologies correspond to identities.
6 Extensions and related structures
6.1 Boolean rings
A Boolean ring is a ring in which every element is idempotent (\(x^2 = x\)). The correspondence with Boolean algebras is bijective: the ring operations are XOR (addition) and AND (multiplication).
6.2 Two-element Boolean algebra
The smallest nontrivial Boolean algebra has elements \(\{0,1\}\) with standard operations. It is the simplest model and the basis for all finite Boolean algebras.
6.3 Free Boolean algebras
A free Boolean algebra on a set of generators contains all expressions formed using the generators and operations, modulo the laws of Boolean algebra. It is infinite if the set of generators is infinite.
6.4 Boolean-valued functions and algebras
A Boolean-valued function on a set \(X\) is a function \(f: X \to \{0,1\}\). The collection of all such functions forms a Boolean algebra under pointwise operations. This concept generalizes to Boolean-valued models in set theory (forcing) and measure theory.