Logic Gates & Combinational Circuits

Boolean Algebra & Digital Logic

Chapter 6 · Logic Gates & Combinational Circuits

Everything so far has been symbols on a page. This chapter makes it physical: a logic gate is a real electronic component that takes voltage levels standing in for 0 and 1, and produces an output voltage exactly matching one of Chapter 2's own truth tables. Wire gates together, and Chapter 5's simplified expressions become an actual working circuit.

Combinational Circuits: Output Depends Only on Right-Now Inputs

A combinational circuit is built purely from gates with no memory anywhere in it — its output at any instant depends only on its current inputs, never on what happened before. Every circuit in this chapter is combinational. Chapter 8 introduces the genuinely different case — circuits that do remember something — which is a different kind of building block entirely, not just "combinational logic with extra wires."

Building Chapter 5's Own Simplified Circuit

Chapter 5 simplified the majority function down to xy + xz + yz. Wired directly into gates, using only 2-input AND and OR gates:

x, y ──[AND]── A1 ──┐
                     ├──[OR]── O1 ──┐
x, z ──[AND]── A2 ──┘               ├──[OR]── majority
                                     │
y, z ──[AND]── A3 ───────────────────┘

Traced and verified directly — x=1, y=1, z=0

A1 = AND(x=1, y=1) = 1. A2 = AND(x=1, z=0) = 0. A3 = AND(y=1, z=0) = 0. O1 = OR(A1=1, A2=0) = 1. Output = OR(O1=1, A3=0) = 1. Matches majority(1,1,0) = 1 exactly — and the full circuit was verified against majority() for all 8 possible inputs, not just this one trace.

Why Chapter 5's Simplification Mattered Physically

Chapter 4's own unsimplified SOP form (x'yz + xy'z + xyz' + xyz) needs real gates too — and Chapter 5's simplification isn't just a shorter formula, it's a genuinely smaller, cheaper, faster circuit.

Version	NOT gates	AND gates	OR gates	Total
Chapter 4's unsimplified SOP	3	4 (3-input each)	3 (chained 2-input)	10
Chapter 5's simplified form	0	3 (2-input each)	2 (chained 2-input)	5

This is Algorithms & Complexity's own lesson, in hardware

Fewer gates means less silicon area, less power draw, and — critically — less propagation delay: every gate a signal passes through takes real physical time, so a circuit with fewer gates in its longest signal path is a genuinely faster circuit, the exact same "fewer operations, less time" reasoning Algorithms & Complexity applied to code, now applied to voltage instead of instructions.

Real Relevance

This is literally what happens inside an FPGA or ASIC design flow: a Boolean expression gets simplified, then mapped onto real gates, then measured by exactly the gate-count and propagation-delay metrics above. Chapter 2's own NAND-completeness proof is why many real fabrication processes build every gate type shown here — AND, OR, NOT included — out of nothing but wired-together NAND gates, for manufacturing consistency.

Gate Simulation in Code

def AND(a, b): return a & b
def OR(a, b): return a | b

def majority_circuit(x, y, z):
    a1 = AND(x, y)
    a2 = AND(x, z)
    a3 = AND(y, z)
    o1 = OR(a1, a2)
    return OR(o1, a3)

def majority(x, y, z):
    return 1 if (x + y + z) >= 2 else 0

from itertools import product
assert all(majority_circuit(x,y,z) == majority(x,y,z)
           for x,y,z in product([0,1], repeat=3))
print("5-gate circuit exactly matches majority() for all 8 inputs")

Hands-On Exercises

Exercise 1

Using this chapter's own majority circuit, trace the signal through every gate for x=0, y=1, z=1, showing each gate's output, and confirm the final result matches majority(0,1,1).

📄 View solution

Exercise 2

Chapter 5's Exercise 1 simplified xy + x'y down to just y. Draw (describe in words, gate by gate) the circuit for the unsimplified form xy + x'y, count its gates (including any NOT gates needed), and compare that count to the simplified circuit, which needs zero gates at all since the output is just y directly.

📄 View solution

Exercise 3

Explain, using this chapter's own combinational-circuit definition, why a circuit that computes output = A AND (output from one clock cycle ago) could not be a combinational circuit, even though it's built entirely from an AND gate.

📄 View solution

Chapter 6 Quick Reference

Logic gate: a physical component realizing one of Chapter 2's own truth tables in real voltage levels
Combinational circuit: output depends only on current inputs — no memory anywhere (contrast: Chapter 8's sequential logic)
Chapter 5's simplified majority circuit (xy+xz+yz) traced and verified directly, gate by gate, for all 8 inputs
Simplification's real payoff: 10 gates down to 5, zero NOT gates needed — smaller, cheaper, and faster (less propagation delay)
Fewer gates in a circuit is the exact same "fewer operations, less time" idea as Algorithms & Complexity, applied to hardware instead of code
Next chapter: Building blocks — adders, multiplexers, and decoders