Boolean Algebra & Simplification
Making circuits smaller and faster
Two circuits can produce exactly the same output but use wildly different numbers of gates. Boolean algebra gives you the tools to simplify logic expressions: fewer gates, less area, less power, faster timing.
And the Karnaugh map turns that algebraic process into something visual and almost mechanical. Toggle cells, spot patterns, read off the simplified expression.
Interactive Karnaugh Map
Click cells to toggle their output value (0 or 1). The simplified Boolean expression updates in real time:
Boolean Algebra Essentials
Boolean algebra operates on binary values (0 and 1) using three basic operations:
- AND (written A·B or AB) - result is 1 only when both are 1
- OR (written A+B) - result is 1 when either is 1
- NOT (written A' or ¬A) - flips the value
Key simplification rules:
- A + A·B = A (absorption)
- A + A' = 1, A·A' = 0 (complementation)
- A·B + A·B' = A (combining)
DeMorgan's Theorem
The single most useful simplification rule:
- (A·B)' = A' + B' - NOT of AND equals OR of NOTs
- (A+B)' = A'·B' - NOT of OR equals AND of NOTs
This is why NAND and NOR are interchangeable as universal gates, and DeMorgan's tells you how to convert between them.
The Karnaugh Map Method
A K-map arranges truth table outputs in a grid where adjacent cells differ by exactly one variable. You group adjacent 1s into the largest possible rectangles (sizes must be powers of 2: 1, 2, 4, 8). Each group becomes one term in the simplified expression. Larger groups = simpler terms.
Why This Matters for FPGA Design
- Resource usage - simpler expressions need fewer LUTs, leaving more room for your design
- Timing - fewer gate levels means signals arrive faster, enabling higher clock speeds
- Power - fewer switching transistors means less dynamic power consumption
- Synthesis tools do this automatically, but understanding the process helps you write HDL that synthesizes well
Frequently Asked Questions
What is a Karnaugh map?
A Karnaugh map (K-map) is a visual tool for simplifying Boolean expressions. You arrange truth table outputs in a grid where adjacent cells differ by only one variable. Then you group adjacent 1s into the largest possible rectangles (sizes must be powers of 2). Each group becomes a simplified term in your expression. K-maps make simplification visual and mechanical instead of requiring algebraic manipulation.
What is DeMorgan's theorem?
DeMorgan's theorem gives two rules: NOT(A AND B) = (NOT A) OR (NOT B), and NOT(A OR B) = (NOT A) AND (NOT B). In plain English: the complement of an AND is an OR of the complements, and vice versa. This is incredibly useful in circuit design because it lets you convert between AND/OR implementations and is the reason NAND and NOR gates are universal.
Quick Check
Test your understanding of the key concepts from this lesson.
