Two-level logic

Also called: two-level, two-level circuit, two-level implementation, two-level network, two-level logic circuit

A circuit in which every input passes through at most two levels of gates, such as AND-OR for an SOP or OR-AND for a POS.

A two-level circuit has two layers of gates between the inputs and the output, assuming complemented inputs are already available.

A sum of products is built as AND-OR: one AND gate per product term, all feeding one OR gate.
A product of sums is built as OR-AND: one OR gate per sum term, all feeding one AND gate.

Why two levels? Every signal passes through at most two gates, so the circuit is fast, and the structure is regular and easy to design. Programmable logic arrays are built exactly this way.

NAND-NAND and NOR-NOR. In CMOS, NAND and NOR gates are cheaper than AND and OR. By bubble pushing, replacing every gate of an AND-OR circuit with a nand gate leaves the function unchanged: = . Likewise OR-AND becomes NOR-NOR. One catch: a single-literal term has no first-level gate, so it must enter the output gate complemented; see single literal term.

The cost of a two-level circuit is measured by its gate input count, which is why simplification aims for a minimal sop or minimal pos.

Worked examples

Example

From SOP to NAND-NAND

Build F = with NAND gates only. The circuit above is the result.

1.
AND-OR version: AND(A, C) and AND(B, D) feed an OR.
2.
Replace all three gates with NANDs. The first level now gives and .
3.
The output NAND gives , which is by De Morgan.
4.
Check A = 1, B = 0, C = 1, D = 1: g1 = 0, g2 = 1, so F = NAND(0, 1) = 1, and = 1 + 0 = 1.

Example

Reading a NOR-NOR circuit

First-level NORs take (A, B) and (C, D'); the output NOR combines them. What is F?

1.
The first level gives and .
2.
The output NOR gives .
3.
De Morgan: .
4.
So NOR-NOR reads as OR-AND, a product of sums.

Common mistakes

Reading NAND-NAND as a product of sums. NAND-NAND gives a sum of products; NOR-NOR gives a product of sums.
Feeding a single-literal term into the output NAND uncomplemented.
Counting inverters for complemented inputs when the convention says they are available for free.

Practice Two-level logic

Interactive questions with instant feedback and a worked solution for every wrong answer.

Boolean Simplification lesson full course

And 4 more in the Boolean Simplification lesson.

Practice exams

Learn it step by step

Two-level logic is taught in Boolean Simplification and Logic Gates.

Boolean Simplification →Logic Gates →

All terms