Boolean Algebra & Logic

Explore truth tables, Karnaugh maps, and boolean expression minimization. Build boolean functions interactively, watch optimal groupings form, and see step-by-step simplification using algebraic laws.

Math Foundations for CS

Scenarios:

Variables:

Karnaugh Map3-variable

BC →

↑ A

Variables3

Minterms5

Groups0/2

Steps0

Truth Table3 variables, 8 rows

#	A	B	C
m0	0	0	0
m1	0	0	1
m2	0	1	0
m3	0	1	1
m4	1	0	0
m5	1	0	1
m6	1	1	0
m7	1	1	1

Expressions

Sum of Products (SOP)

F = A'B'C + A'BC + AB'C + ABC' + ABC

Boolean Laws

IdentityA + 0 = A, A . 1 = A

NullA + 1 = 1, A . 0 = 0

ComplementA + A' = 1, A . A' = 0

IdempotentA + A = A, A . A = A

AbsorptionA + AB = A

De Morgan(AB)' = A'+B'

ConsensusAB + A'C + BC = AB + A'C

K-Map Grouping Rules

Groups must be powers of 2 (1, 2, 4, 8)
Groups must be rectangular
Groups can wrap around edges
Larger groups = simpler terms
Every 1-cell must be in at least one group
Overlapping groups are allowed

InteractiveClick any output cell in the truth table or K-map to toggle between 0 and 1. The boolean expression and K-map groupings will update automatically.

1.0x

Understanding Boolean Algebra

Why Boolean Minimization Matters

Every digital circuit implements a boolean function. Minimizing the boolean expression directly reduces the number of logic gates needed, resulting in smaller, faster, and more power-efficient circuits. This optimization is fundamental to chip design, from simple microcontrollers to modern CPUs.

Approaches to Minimization

AlgebraicApply boolean algebra laws step by step. Good for learning, but can miss optimal solutions.

Karnaugh MapsVisual method for up to 4-6 variables. Group adjacent 1-cells to find minimal product terms.

Quine-McCluskeyAlgorithmic method for any number of variables. Guaranteed optimal but computationally expensive.

Key InsightIn a Karnaugh map, adjacent cells differ by exactly one variable (Gray code ordering). When two adjacent cells are both 1, the differing variable can be eliminated from the product term. This is why larger groups yield simpler expressions: a group of 4 cells in a 3-variable K-map eliminates 2 variables, leaving just 1 variable in the term. This visual insight is exactly what the algebraic Consensus theorem captures formally.

Key Concepts

Concept	Description	Example
Minterm	Product term where all variables appear	ABC' (m5)
Maxterm	Sum term where all variables appear	A+B+C' (M2)
SOP	Sum of Products canonical form	AB + A'C + BC
POS	Product of Sums canonical form	(A+B)(A'+C)
Don't Care	Output undefined for some inputs	X in truth table
Prime Implicant	Largest possible group in K-map	Group of 4 cells