Logic Gates and Combinational Circuits

Core Idea

Logic gates are physical realizations of Boolean operations: AND, OR, NOT, NAND, NOR, and XOR. A combinational circuit is a directed acyclic network of gates computing a Boolean function of its inputs with no feedback. Any Boolean function can be implemented using only NAND gates (or only NOR gates), making each set functionally complete — a fact crucial for hardware manufacturing. Circuit design translates a truth table to a Boolean expression, simplifies it to minimize gates, and then maps to a gate network. The half adder and full adder demonstrate how arithmetic emerges from Boolean primitives.

How It's Best Learned

Design simple circuits — half adder, full adder, 2-to-1 multiplexer — starting from truth tables. Practice both sum-of-products and product-of-sums implementations. Prove NAND universality by constructing NOT, AND, and OR from NAND alone.

Common Misconceptions

• Confusing combinational circuits (stateless, no memory) with sequential circuits (with feedback and state).
• Thinking you need all gate types — NAND alone suffices to implement any Boolean function.
• Conflating XOR with OR: XOR outputs 1 only when inputs differ; OR outputs 1 when at least one input is 1.

Explainer

You've studied Boolean algebra — the abstract system of 0s, 1s, AND, OR, and NOT with its algebraic laws. Logic gates are the physical realization of those operations: electrical components that take voltage signals as inputs (high voltage = 1, low voltage = 0) and produce a voltage output according to a Boolean rule. A combinational circuit is a network of gates with no feedback loops — it is a directed acyclic graph of gates whose output is determined entirely by the current inputs, with no memory of past inputs. Every combinational circuit computes some Boolean function.

The standard design process flows from specification to circuit. Start with a truth table specifying the desired output for every input combination. From the rows where the output is 1, write a sum-of-products (SOP) expression: an AND term for each such row, combined with OR. This gives a correct two-level circuit. The circuit may be redundant, so apply Boolean algebra identities to reduce gate count before building. The reverse process — product-of-sums (POS) from rows where the output is 0 — is equally valid. Both are systematic translations from specification to gate network.

The surprising result of functional completeness is that you need only one gate type to build anything. The NAND gate — which outputs 0 only when both inputs are 1 — can simulate all three primitive operations: NOT(A) = NAND(A,A); AND(A,B) = NOT(NAND(A,B)); OR(A,B) = NAND(NOT A, NOT B). This means any Boolean function, however complex, can be implemented using only NAND gates. NOR gates are equally complete by a symmetric argument. Hardware manufacturers exploit this: a single type of gate can be mass-produced, and any circuit is built from multiples of it. Universality — one gate generating all others — is the key concept.

The adder circuit demonstrates how arithmetic emerges from Boolean primitives. A half adder adds two 1-bit inputs: the sum bit is XOR(A,B) (the inputs differ) and the carry is AND(A,B) (both are 1). A full adder takes three bits — two data inputs plus a carry-in — and produces a sum bit and carry-out. Chaining n full adders gives a ripple-carry adder that adds two n-bit numbers. This chain of AND, OR, and NOT gates (or equivalently, only NANDs) is what a processor uses for integer arithmetic. The entire jump from abstract Boolean operations to working hardware is made of concepts you now have.