Boolean logic

Boolean logic, also known as Boolean algebra, is a branch of algebra and mathematical logic that deals with binary variables (true/false, 1/0) and logical operations. Developed by George Boole in the mid‑19th century, it provides the foundation for digital circuit design, computer programming, and formal reasoning. Boolean logic uses operators such as AND, OR, and NOT to combine or modify truth values, and its principles underpin the operation of all modern computing systems.

1 Fundamentals

1.1 Binary values and truth tables

Binary values are the two possible states in Boolean logic: true (1) and false (0). A truth table is a tabular representation that lists all possible combinations of input binary values and the corresponding output for a given logical operation. Truth tables are fundamental for defining and verifying Boolean functions.

1.2 Basic operators

1.2.1 Logical conjunction (AND)

The AND operator yields true (1) if and only if both operands are true. In Boolean notation, it is often written as A · B, A ∧ B, or A & B. The truth table for AND shows output 1 only when A = 1 and B = 1; otherwise output is 0.

1.2.2 Logical disjunction (OR)

1.2.3 Logical negation (NOT)

The NOT operator is a unary operator that inverts the input: true becomes false and false becomes true. It is written as ¬A, A', or ~A.

1.3 Derived operators

1.3.1 NAND and NOR

NAND (NOT AND) and NOR (NOT OR) are universal gates. NAND yields false only when both inputs are true; NOR yields true only when both inputs are false. Any Boolean function can be implemented using only NAND gates or only NOR gates.

1.3.2 XOR and XNOR

XOR (exclusive OR) outputs true when the inputs differ. XNOR (equivalence) outputs true when the inputs are the same. XOR is often used in arithmetic circuits and parity checks.

2 Algebraic structure

2.1 Boolean algebra axioms

Boolean algebra is defined by a set of axioms that govern the behavior of binary variables and operations.

2.1.1 Commutative, associative, distributive laws

• Commutative: A + B = B + A; A · B = B · A
• Associative: (A + B) + C = A + (B + C); (A · B) · C = A · (B · C)
• Distributive: A · (B + C) = (A · B) + (A · C); A + (B · C) = (A + B) · (A + C)

2.1.2 Identity and complement laws

• Identity: A + 0 = A; A · 1 = A
• Complement: A + A' = 1; A · A' = 0
• Double negation: (A')' = A

2.2 Boolean expressions and simplification

2.2.1 Truth table to expression

A Boolean expression can be derived from a truth table by summing (OR‑ing) the minterms (product terms) that produce an output of 1. This yields the sum‑of‑products (SOP) form. Alternatively, product‑of‑sums (POS) form is obtained from maxterms.

2.2.2 Karnaugh maps

Karnaugh maps (K‑maps) are graphical tools for simplifying Boolean expressions with up to six variables. Cells are arranged in a grid such that adjacent cells differ by only one variable, allowing visual identification of common factors. The resulting simplified expression often reduces the number of logic gates needed.

2.2.3 Quine‑McCluskey algorithm

The Quine‑McCluskey algorithm is a tabular method for minimizing Boolean functions with many variables. It systematically finds all prime implicants and then selects a minimal cover. It is suitable for computer implementation and handles don’t‑care conditions.

3 Applications

3.1 Digital logic circuits

3.1.1 Logic gates

Logic gates are electronic devices that implement Boolean operators. Basic gates include AND, OR, NOT, NAND, NOR, XOR, and XNOR. They are the building blocks of digital circuits.

3.1.1.1 Gate symbols and truth tables

Each gate has a standard schematic symbol (e.g., a curved shape for AND, a “≥1” shape for OR, a triangle with a circle for NOT) and a corresponding truth table that defines its output for all input combinations. For example, a two‑input AND gate outputs 1 only when both inputs are 1.

3.1.2 Combinational circuits (adders, multiplexers)

Combinational circuits produce outputs solely based on current inputs. Examples include half and full adders (binary addition), multiplexers (data selection), decoders, and encoders. They are designed using gate‑level Boolean expressions.

3.1.3 Sequential circuits (flip‑flops, registers)

Sequential circuits have memory; their outputs depend on both current inputs and past states. Flip‑flops (e.g., SR, D, JK) are basic memory elements. Registers, counters, and finite‑state machines are built from flip‑flops and combinational logic.

3.2 Computer science

3.2.1 Boolean data types and conditionals

3.2.2 Search and query languages (SQL, regex)

3.3 Formal logic and mathematics

3.3.1 Propositional calculus

Propositional calculus is the branch of formal logic that treats propositions as Boolean variables. Logical connectives (∧, ∨, ¬, →, ↔) correspond to Boolean operators. Truth‑table methods and natural deduction derive theorems.

3.3.2 Set theory and lattice theory

Boolean algebra is isomorphic to the algebra of sets: union corresponds to OR, intersection to AND, and complement to NOT. Every Boolean algebra forms a distributive lattice with complement, which is central to lattice theory and the study of partially ordered sets.

4 Extensions and related topics

4.1 Three‑valued logic and fuzzy logic

Three‑valued logic introduces a third truth value (e.g., unknown or undefined) beyond true and false. Fuzzy logic, developed by Lotfi Zadeh, allows degrees of truth (real numbers between 0 and 1). Both extend Boolean logic to handle incomplete or imprecise information.

4.2 Boolean algebra in abstract algebra

In abstract algebra, a Boolean algebra is a specific type of algebraic structure with operations that satisfy the Boolean axioms. It is a complemented distributive lattice. Boolean rings are an alternative representation where addition is XOR and multiplication is AND. These structures have applications in measure theory, topology, and the foundations of computation.