Logic gate circuit construction

In the previous lecture, we learned about the four basic logic gates. In this lecture, we'll connect them together to build circuits that solve real-world problems.

A single logic gate is like a screw — its function is limited on its own. But combine them, and you can build arbitrarily complex functions.

Everyday analogy: building a castle with Lego bricks

Imagine you have four colors of LEGO bricks in front of you:

Green block = AND gate: Current flows only when both ends are connected
Orange block = OR gate: Current flows when either end is connected
Red block = NOT gate: On becomes off, off becomes on
Purple block = XOR gate: Current flows when the two ends are in different states

What can you build with these bricks?

a voterThree people vote, and the majority rules. This is a typical combinational logic circuit — just connect AND/OR gates to implement it.

a combination lockThe correct keys must be pressed simultaneously to unlock. This is essentially a cascade of AND gates — each key corresponds to an input, and only when all inputs are 1 does the output become 1.

an alarmIf any sensor triggers, the alarm sounds. This is essentially an application of OR gates — as long as one sensor outputs 1, the alarm rings.

Combinational logic vs sequential logic

Before we dive deeper into building circuits, let's distinguish two important concepts:

Type	Features	Output depends on	Does it have memory?	Examples
Combinational logic	Output is determined only by current input	current input value	no	Adder, majority voter, decoder
Sequential logic	Output is determined by current inputs + historical state	Current input + previously stored values	Yes	Counter, register, state machine

This lecture focuses on combinational logic.Sequential logic will be introduced in detail in Lecture 9.

A simple way to distinguish them: combinational logic is "whatever you input, I output" (like a mathematical function); sequential logic is "I still remember what you input before" (like human memory).

Circuit construction methodology: the three-step method

There is a universal three-step process for building any combinational logic circuit with logic gates:

List the truth tableStep 1: List all combinations of inputs, and write down the expected output for each case.
Write the logic expressionStep 2: For each row where the output is 1, write the corresponding "product term" (the AND combination of inputs), then connect all product terms with OR. This is called the "Sum of Products" form.
Draw circuit diagram / Write codeStep 3: Translate the logic expression into a gate-level circuit connection.

Let's practice this method through three examples, from simple to advanced.

Case 1: Two-input password lock

RequirementsCase 1: Design a simple password-checking circuit. There are two inputs A and B. Only when A=1 and B=1 does the output become 1 (unlock); otherwise, the output is 0 (locked).

This requirement is actually just an AND gate. But we can use it to demonstrate the three-step method:

Step 1: Truth table

A	B	Expected output Y
0	0	0 (lock)
0	1	0 (lock)
1	0	0 (lock)
1	1	1 (unlocked)

Step 2: Logic expression

Only the last row has output 1. The corresponding product term is: A AND B.

So: Y = A AND B

Step 3: Circuit implementation

You only need one AND gate, with A and B as inputs, and Y as the output.

Too simple? Let's look at a more practical example.

Case 2: Majority Voter (Core Case)

RequirementsThree people (A, B, C) vote on a proposal (1 means approve, 0 means reject). The proposal passes when at least two people approve (output 1).

This is a classic three-input majority voter and a must-learn case in digital circuit textbooks.

Step 1: List the truth table

Three inputs have a total of 2³= 8 combinations:

A	B	C	Number in favor	Pass/fail: Y	Description
0	0	0	0	0	No one in favor
0	0	1	1	0	Only C approves
0	1	0	1	0	Only B approves
0	1	1	2	1	B and C approve
1	0	0	1	0	Only A approves
1	0	1	2	1	A and C approve
1	1	0	2	1	A and B approve
1	1	1	3	1	Passed unanimously

Step 2: Write the logic expression

Find the rows where the output is 1 (rows 4, 6, 7, 8), and write one product term for each row:

Line 4: NOT(A) AND B AND C
Line 6: A AND NOT(B) AND C
Line 7: A AND B AND NOT(C)
Line 8: A AND B AND C

use OR connection：Y = (NOT(A) AND B AND C) OR (A AND NOT(B) AND C) OR (A AND B AND NOT(C)) OR (A AND B AND C)

This expression may look a bit long, but logically it is very clear:Y is 1 if and only if any two or three inputs are 1。

Step 3: Draw the circuit diagram with SVG

Three AND gates check whether each of the three pairs "AB", "BC", and "AC" is 11, then the OR gate aggregates the results.

Interactive demo: Python implementation of the majority voter

Example

# Three-input majority voter (example demo)
# Requirement: three people vote; it passes (output 1) only when at least two approve (1).

# ----- Reuse basic logic gates from Lecture 6 -----
def AND(a, b):
return 1 if a == 1 and b == 1 else 0

def OR(a, b):
return 1 if a == 1 or b == 1 else 0

def NOT(a):
return 1 if a == 0 else 0

# ----- Method 1: Sum-of-Products (SOP) standard form -----
def majority_voter_sop(a, b, c):
"""
The majority voter's sum-of-products implementation.
Directly derive from the truth table: find all rows where the output is 1,
Write one AND term per line, then connect with OR.
"""
term1 = AND(AND(NOT(a), b), c) # ~A·B·C
term2 = AND(AND(a, NOT(b)), c) # A·~B·C
term3 = AND(AND(a, b), NOT(c)) # A·B·~C
term4 = AND(AND(a, b), c) # A·B·C
return OR(OR(term1, term2), OR(term3, term4))

# ----- Method 2: Optimized simplified form -----
def majority_voter_optimized(a, b, c):
"""
Optimized implementation of majority voter: Y = AB + BC + AC.
This form requires fewer gates, but is logically equivalent to method one.

Why equivalent?
After expanding the SOP form of Method 1, it can be simplified using the Boolean algebra absorption law:
~A·B·C + A·~B·C + A·B·~C + A·B·C
= (~A·B·C + A·B·C) + (A·~B·C + A·B·C) + (A·B·~C + A·B·C)
= B·C·(~A+A) + A·C·(~B+B) + A·B·(~C+C)
= B·C + A·C + A·B
"""
return OR(OR(AND(a, b), AND(b, c)), AND(a, c))

# ============================================
# Print the full truth table and compare the two methods
# ============================================
print("=" * 60)
print(Three-input majority voting truth table (EXAMPLE demo))
print("=" * 60)
print()
print("┌───┬───┬───┬────────┬──────────┬──────────┐")
print(│ A │ B │ C │ Pass? │ SOP Method │ Optimization Method │)
print("├───┼───┼───┼────────┼──────────┼──────────┤")
for a in [0, 1]:
for b in [0, 1]:
for c in [0, 1]:
count = a + b + c
passed = "Pass" if count >= 2 else "Failed"
sop = majority_voter_sop(a, b, c)
opt = majority_voter_optimized(a, b, c)
print(f"│ {a} │ {b} │ {c} │ {passed} │ {sop} │ {opt} │")
print("└───┴───┴───┴────────┴──────────┴──────────┘")

# ============================================
# Gate circuit usage statistics
# ============================================
print("\n" + "=" * 60)
print(" Comparison of the number of gates used by the two methods")
print("=" * 60)
print()
print(Method 1 (SOP full form):)
print(NOT gates: 3 (~A, ~B, ~C))
print(AND gates: 4 (four AND terms, each requiring 2 two-input ANDs))
print(OR gate: 3 (combining four product terms))
print(Total: approximately 14 basic gate calls)
print()
print("Method 2 (optimized form Y = AB + BC + AC):")
print(AND gates: 3 (AB, BC, AC))
print(OR gate: 2 (combining three product terms))
print(" Total: 5 basic gate calls")
print()
print(After optimization, the gate count is reduced by about 65%!)
print("This is the engineering value of Boolean algebra simplification.")

Note the conversion process from truth table to logic expression. This is one of the core skills in digital circuit design: seeing a truth table, you can write the expression; seeing an expression, you can draw the circuit diagram. The three correspond one-to-one.

Case 3: One-bit comparator

RequirementsCompare two 1-bit binary numbers A and B. Output three signals: A>B, A=B, A<B

This is a very important basic circuit — multi-bit comparators and conditional judgments in CPUs are extended from here.

Step 1: Truth table

A	B	A > B	A = B	A < B
0	0	0	1	0
0	1	0	0	1
1	0	1	0	0
1	1	0	1	0

Step 2: Logic expression

Observe the truth table:

A > B is 1 if and only if: A=1 AND B=0. So: Greater = A AND NOT(B)
A = B is 1 if and only if：A and B Same.So：Equal = NOT(A XOR B), or说 Equal = (A AND B) OR (NOT(A) AND NOT(B))
A < B is 1 if and only if: A=0 AND B=1. Therefore: Less = NOT(A) AND B

Note that the detection of A = B is closely related to the XOR gate. An XOR output of 1 means "different"; taking NOT of it gives "equal".

Step 3: Code implementation

Example

# 1-bit comparator (example demo)
# Compare two 1-bit binary numbers A and B

def AND(a, b):
return 1 if a == 1 and b == 1 else 0

def OR(a, b):
return 1 if a == 1 or b == 1 else 0

def NOT(a):
return 1 if a == 0 else 0

def one_bit_comparator(a, b):
"""
One-bit comparator: compares A and B.
Return a tuple (Greater, Equal, Less).
"""
greater = AND(a, NOT(b)) # A > B: A=1 and B=0
less = AND(NOT(a), b) # A < B: A=0 and B=1
# A = B: neither greater nor less
# Equivalent to NOT(A XOR B), here we use another implementation
equal = AND(NOT(greater), NOT(less))
return (greater, equal, less)

# Print truth table
print("=" * 50)
print(One-bit Comparator Truth Table (EXAMPLE Demo))
print("=" * 50)
print()
print("┌───┬───┬────────┬────────┬────────┐")
print("│ A │ B │ A > B │ A = B │ A < B │")
print("├───┼───┼────────┼────────┼────────┤")
for a in [0, 1]:
for b in [0, 1]:
gt, eq, lt = one_bit_comparator(a, b)
print(f"│ {a} │ {b} │ {gt} │ {eq} │ {lt} │")
print("└───┴───┴────────┴────────┴────────┘")

# Test some useful scenarios
print("\nTest scenario: ")
a_test, b_test = 1, 0
gt, eq, lt = one_bit_comparator(a_test, b_test)
print(f"A={a_test}, B={b_test}: A>B={gt}, A=B={eq}, A<B={lt}")
print(f"Interpretation: A is greater than B" if gt else ("A equals B" if eq else "A is less than B"))

Case 4: 2-to-4 decoder

RequirementsInput a 2-bit binary number (00, 01, 10, 11), and make exactly one of the corresponding 4 output lines equal to 1, with the rest equal to 0.

The decoder is a core component in the CPU — when the CPU wants to select a register, it is essentially using a decoder.

Truth table

A1	A0	Y0	Y1	Y2	Y3
0	0	1	0	0	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	0	0	0	1

logical expression

Y0 = NOT(A1) AND NOT(A0)
Y1 = NOT(A1) AND A0
Y2 = A1 AND NOT(A0)
Y3 = A1 AND A0

Example

# 2-4 decoder (example demo)
# Input: 2-bit binary number A1 A0
# Output: exactly one of the 4 lines is 1

def AND(a, b):
return 1 if a == 1 and b == 1 else 0

def NOT(a):
return 1 if a == 0 else 0

def decoder_2to4(a1, a0):
"""
2-to-4 line decoder.
Return the list [Y0, Y1, Y2, Y3],
Exactly one of them is 1, the rest are 0.
"""
Y0 = AND(NOT(a1), NOT(a0)) # 00 → Y0
Y1 = AND(NOT(a1), a0) # 01 → Y1
Y2 = AND(a1, NOT(a0)) # 10 → Y2
Y3 = AND(a1, a0) # 11 → Y3
return [Y0, Y1, Y2, Y3]

# Print truth table
print("=" * 50)
print(2-4 Decoder Truth Table (EXAMPLE Demo))
print("=" * 50)
print()
print("┌────┬────┬────┬────┬────┬────┐")
print("│ A1 │ A0 │ Y0 │ Y1 │ Y2 │ Y3 │")
print("├────┼────┼────┼────┼────┼────┤")
for a1 in [0, 1]:
for a0 in [0, 1]:
Y = decoder_2to4(a1, a0)
print(f"│ {a1} │ {a0} │ {Y[0]} │ {Y[1]} │ {Y[2]} │ {Y[3]} │")
print("└────┴────┴────┴────┴────┴────┘")

# Show an actual usage scenario
print("\nPractical application scenario: using a decoder to select registers)
registers = ["R0", "R1", "R2", "R3"]
for a1 in [0, 1]:
for a0 in [0, 1]:
Y = decoder_2to4(a1, a0)
idx = Y.index(1) # Find which output line is 1
print(fAddress A1A0={a1}{a0} → selects register {registers[idx]})

The decoder is a classic "one-to-many" circuit. Its counterpart is the multiplexer (MUX), which is "many-to-one". Both are very common in CPU data-path design. The decoder is used to "select a target" (such as which register to write), while the multiplexer is used to "select a source" (such as which register the ALU reads data from).

Universal gates: what makes NAND and NOR special

In actual chip manufacturing, NAND and NOR gates are more "low-level" than AND and OR gates.

NAND gate = AND + NOTThat is, do AND first, then invert. NAND and NOR are called "universal gates" because each one alone can implement all Boolean functions.

Why do chips favor NAND/NOR? Because in CMOS technology:

A NAND gate requires only 4 transistors, while an AND gate requires 6 (AND = NAND + NOT).
NAND gates have faster switching speed
Therefore, the AND function in actual chips is implemented at the low level using NAND + NOT.

Next, let's verify the "universality" of the NAND gate:

Example

# Proving the universality of the NAND gate (example demo)
# NAND gate alone can implement the three basic functions: NOT, AND, OR

def NAND(a, b):
"""NAND gate: the result of AND is inverted.
Y = 0 if and only if a=1 and b=1"""
return 0 if a == 1 and b == 1 else 1

Implement NOT using NAND: NOT(A) = NAND(A, A)
def NOT_from_NAND(a):
return NAND(a, a)

# use NAND Implementation AND：AND(A,B) = NOT(NAND(A,B)) = NAND(NAND(A,B), NAND(A,B))
def AND_from_NAND(a, b):
nand_ab = NAND(a, b)
return NAND(nand_ab, nand_ab)

# Implement OR using NAND: OR(A,B) = NAND(NOT(A), NOT(B))
def OR_from_NAND(a, b):
return NAND(NOT_from_NAND(a), NOT_from_NAND(b))

# ============================================
# Verify
# ============================================
print("=" * 60)
print(Demonstrate the universality of NAND gates (EXAMPLE demo).)
print("=" * 60)

print("\n[Verify: NOT implemented by NAND]")
for a in [0, 1]:
expected = 1 if a == 0 else 0
actual = NOT_from_NAND(a)
print(f" A={a}: NOT_from_NAND = {actual}, period望 = {expected}, {'Through' if actual == expected else 'failure'}")

print("\n[Verify: AND implemented by NAND]")
for a in [0, 1]:
for b in [0, 1]:
expected = 1 if a == 1 and b == 1 else 0
actual = AND_from_NAND(a, b)
print(f" A={a}, B={b}: AND_from_NAND = {actual}, period望 = {expected}, {'Through' if actual == expected else 'failure'}")

print("\n[Verification: OR implemented with NAND])
for a in [0, 1]:
for b in [0, 1]:
expected = 1 if a == 1 or b == 1 else 0
actual = OR_from_NAND(a, b)
print(f" A={a}, B={b}: OR_from_NAND = {actual}, period望 = {expected}, {'Through' if actual == expected else 'failure'}")

print("\nConclusion: Only NAND gates are needed to construct ANY Boolean function.)
print(This is why the nand2tetris course can build an entire computer starting from NAND gates.)

nand2tetris (From NAND to Tetris) is a famous computer science course. It challenges you to build a CPU, memory, and operating system step by step using only NAND gates, and finally run a Tetris game. If you're interested in the low-level details of computers, I highly recommend it.

Interactive demo: Majority voter circuit builder (example vis-network demo)

Use belowvis-networkIt visualizes a three-input majority voter circuit (Y = AB + BC + AC).Click input nodes A, B, C to toggle 0/1, the circuit will automatically evaluate and update the colors of all wires —Redindicates the signal is 1,grayindicates the signal is 0.

Three-input majority voter (click A/B/C nodes to toggle)

A=0, B=0, C=0 → Not passed (requires at least 2 votes in favor)

Input node A Input node B Input node C AND gate OR gate Output Y

other extensions