S4-4.1 Logic Simplification & Realization

What this is and why it exists

Every digital circuit is a Boolean truth wearing gates, and this unit is the craft of saying that truth with the fewest, cheapest gates. Number systems supply the raw material, Boolean algebra the grammar, and the two minimization methods — Karnaugh maps for eyes, Quine-McCluskey for algorithms — remove the redundancy. The NAND/NOR ending is not an afterthought: real silicon is built from those two gates almost exclusively, so every design you draw eventually gets translated into them.

The vocabulary

• Radix conversion — moving a number between binary, octal, decimal and hexadecimal representations.
• Complements — one's and two's complement: subtraction rebuilt as addition, which is why hardware adders also subtract.
• SOP and POS — sum-of-products and product-of-sums; canonical forms list every minterm or maxterm explicitly.
• Karnaugh map (K-map) — the truth table folded so that adjacent cells differ in one variable; groups of 1s ARE the simplifications.
• Don't-care condition — an input combination that never occurs; the minimizer may count it either way, whichever groups better.
• Quine-McCluskey — the tabular minimization method: exhaustive pairing, then a prime-implicant chart; slower for hands, exact for programs.
• NAND/NOR realization — any logic function rebuilt from only NAND or only NOR gates, each being universal.

The mental model

Minimization is map-reading. A K-map is the truth table refolded so that physical neighbours are logical neighbours — each step to an adjacent cell flips exactly one variable (Gray-code ordering makes it so, and the edges wrap). A rectangular group of 1s sized a power of two is a product term that ignores every variable changing inside the group: bigger group, shorter term. Minimization becomes a visual game — cover every 1 with the fewest, largest groups, spending don't-cares wherever they enlarge a group and nowhere else. Up to four variables the game is quick; five and six strain the eyes, and that strain is the honest advertisement for Quine-McCluskey, which plays the identical game as tables: combine minterms differing in one bit, repeat until nothing combines (the survivors are prime implicants), then choose a minimum cover from the chart. Tedious by hand, mechanical by program — which is the point: it is the algorithmic ancestor of what synthesis tools do.

De Morgan's theorems are the translation engine at the end. Silicon prefers NAND and NOR — fewest transistors, fastest switching — and either gate alone can build everything. The translation is graphical, not algebraic: a two-level AND-OR network becomes all-NAND by double-inverting each internal wire and absorbing the inversions into the gates; OR-AND becomes all-NOR the same way. Draw it once and the bubbles stop being mysterious.

Two's complement sits underneath it all: negate by inverting and adding one, and subtraction becomes addition with no separate hardware — the reason every processor's arithmetic unit is, at heart, an adder.

What you should now be able to explain or do

Convert numbers between the four common radices and form two's complements. Minimize a four-variable function on a K-map, don't-cares included, and state the minimal SOP. Run Quine-McCluskey on a small function and read the prime-implicant chart. Convert an AND-OR network to all-NAND and an OR-AND network to all-NOR.

Check yourself