Logic Gates and Circuits
Learning Objectives
By the end of this reading, you will be able to:
- Understand the fundamental logic gates and their operations
- Analyze and design combinational logic circuits
- Create truth tables for complex logic expressions
- Understand Boolean algebra and De Morgan's theorems
- Design arithmetic circuits including half adders, full adders, and ripple-carry adders
- Apply logic gates to solve practical computing problems
Introduction
Logic gates are the fundamental building blocks of digital circuits and, by extension, all modern computers. They perform basic logical operations on binary inputs to produce binary outputs.
Understanding logic gates is essential because:
- Every computer operation ultimately reduces to logic gate operations
- They form the basis of the CPU, memory, and all digital systems
- They bridge the gap between abstract Boolean logic and physical hardware
Boolean Algebra Fundamentals
Boolean algebra is the mathematical foundation for digital logic. It operates on binary values: TRUE/FALSE or 1/0.
Basic Boolean Operations
AND (·): True only if all inputs are true
A · B or A AND B or A ∧ B
OR (+): True if at least one input is true
A + B or A OR B or A ∨ B
NOT (¯): Inverts the input
Ā or NOT A or ¬A
Boolean Algebra Laws
Identity Laws:
A · 1 = A
A + 0 = A
Null Laws:
A · 0 = 0
A + 1 = 1
Idempotent Laws:
A · A = A
A + A = A
Inverse Laws:
A · Ā = 0
A + Ā = 1
Commutative Laws:
A · B = B · A
A + B = B + A
Associative Laws:
(A · B) · C = A · (B · C)
(A + B) + C = A + (B + C)
Distributive Laws:
A · (B + C) = (A · B) + (A · C)
A + (B · C) = (A + B) · (A + C)
De Morgan's Theorems:
¯(A · B) = Ā + B̄
¯(A + B) = Ā · B̄
The Seven Basic Logic Gates
1. NOT Gate (Inverter)
Symbol:
┌────┐
A ───┤ ┐ ├─── Ā
└────┘
Truth Table:
┌───┬───┐
│ A │ Ā │
├───┼───┤
│ 0 │ 1 │
│ 1 │ 0 │
└───┴───┘
Function: Inverts the input signal.
2. AND Gate
Symbol:
┌────┐
A ───┤ │
│ & ├─── A·B
B ───┤ │
└────┘
Truth Table:
┌───┬───┬─────┐
│ A │ B │ A·B │
├───┼───┼─────┤
│ 0 │ 0 │ 0 │
│ 0 │ 1 │ 0 │
│ 1 │ 0 │ 0 │
│ 1 │ 1 │ 1 │
└───┴───┴─────┘
Function: Output is 1 only when ALL inputs are 1.
3. OR Gate
Symbol:
┌────┐
A ───┤ │
│ ≥1 ├─── A+B
B ───┤ │
└────┘
Truth Table:
┌───┬───┬─────┐
│ A │ B │ A+B │
├───┼───┼─────┤
│ 0 │ 0 │ 0 │
│ 0 │ 1 │ 1 │
│ 1 │ 0 │ 1 │
│ 1 │ 1 │ 1 │
└───┴───┴─────┘
Function: Output is 1 when AT LEAST ONE input is 1.
4. NAND Gate (NOT-AND)
Symbol:
┌────┐
A ───┤ │○
│ & ├──── ¯(A·B)
B ───┤ │
└────┘
Truth Table:
┌───┬───┬─────────┐
│ A │ B │ ¯(A·B) │
├───┼───┼─────────┤
│ 0 │ 0 │ 1 │
│ 0 │ 1 │ 1 │
│ 1 │ 0 │ 1 │
│ 1 │ 1 │ 0 │
└───┴───┴─────────┘
Function: Opposite of AND. Output is 0 only when ALL inputs are 1.
Important: NAND is a universal gate - any logic function can be implemented using only NAND gates.
5. NOR Gate (NOT-OR)
Symbol:
┌────┐
A ───┤ │○
│ ≥1 ├──── ¯(A+B)
B ───┤ │
└────┘
Truth Table:
┌───┬───┬─────────┐
│ A │ B │ ¯(A+B) │
├───┼───┼─────────┤
│ 0 │ 0 │ 1 │
│ 0 │ 1 │ 0 │
│ 1 │ 0 │ 0 │
│ 1 │ 1 │ 0 │
└───┴───┴─────────┘
Function: Opposite of OR. Output is 1 only when ALL inputs are 0.
Important: NOR is also a universal gate.
6. XOR Gate (Exclusive OR)
Symbol:
┌────┐
A ───┤ │
│ =1 ├─── A⊕B
B ───┤ │
└────┘
Truth Table:
┌───┬───┬─────┐
│ A │ B │ A⊕B │
├───┼───┼─────┤
│ 0 │ 0 │ 0 │
│ 0 │ 1 │ 1 │
│ 1 │ 0 │ 1 │
│ 1 │ 1 │ 0 │
└───┴───┴─────┘
Function: Output is 1 when inputs are DIFFERENT.
Boolean Expression: A⊕B = A·B̄ + Ā·B
7. XNOR Gate (Exclusive NOR)
Symbol:
┌────┐
A ───┤ │○
│ =1 ├──── ¯(A⊕B)
B ───┤ │
└────┘
Truth Table:
┌───┬───┬─────────┐
│ A │ B │ ¯(A⊕B) │
├───┼───┼─────────┤
│ 0 │ 0 │ 1 │
│ 0 │ 1 │ 0 │
│ 1 │ 0 │ 0 │
│ 1 │ 1 │ 1 │
└───┴───┴─────────┘
Function: Output is 1 when inputs are the SAME (equality detector).
Combinational Logic Circuits
Combinational circuits produce outputs based solely on current inputs (no memory).
Example 1: Three-Input Majority Function
Problem: Output 1 if the majority of inputs are 1.
Truth Table:
┌───┬───┬───┬────────┐
│ A │ B │ C │ Output │
├───┼───┼───┼────────┤
│ 0 │ 0 │ 0 │ 0 │
│ 0 │ 0 │ 1 │ 0 │
│ 0 │ 1 │ 0 │ 0 │
│ 0 │ 1 │ 1 │ 1 │ ← 2 ones
│ 1 │ 0 │ 0 │ 0 │
│ 1 │ 0 │ 1 │ 1 │ ← 2 ones
│ 1 │ 1 │ 0 │ 1 │ ← 2 ones
│ 1 │ 1 │ 1 │ 1 │ ← 3 ones
└───┴───┴───┴────────┘
Boolean Expression (Sum of Products):
F = A·B·C̄ + A·B̄·C + Ā·B·C + A·B·C
F = A·B + A·C + B·C (simplified)
Circuit:
┌────┐
A ──┬───┤ │
│ │ & ├───┐
B ──┼─┬─┤ │ │
│ │ └────┘ │ ┌────┐
│ │ ├────┤ │
│ │ ┌────┐ │ │ ≥1 ├─── Output
A ──┤ └─┤ │ │ │ │
│ │ & ├───┤ └────┘
C ──┼─┬─┤ │ │
│ │ └────┘ │
│ │ │
│ │ ┌────┐ │
B ──┘ └─┤ │ │
│ & ├───┘
C ──────┤ │
└────┘
Example 2: 2-to-4 Decoder
Function: Activates one of 4 outputs based on 2-bit input.
Truth Table:
┌───┬───┬────┬────┬────┬────┐
│ A │ B │ D0 │ D1 │ D2 │ D3 │
├───┼───┼────┼────┼────┼────┤
│ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │
│ 0 │ 1 │ 0 │ 1 │ 0 │ 0 │
│ 1 │ 0 │ 0 │ 0 │ 1 │ 0 │
│ 1 │ 1 │ 0 │ 0 │ 0 │ 1 │
└───┴───┴────┴────┴────┴────┘
Boolean Expressions:
D0 = Ā·B̄
D1 = Ā·B
D2 = A·B̄
D3 = A·B
Example 3: 4-to-1 Multiplexer (MUX)
Function: Selects one of 4 inputs based on 2-bit selector.
Inputs: I0, I1, I2, I3
Selectors: S1, S0
Output: Y
┌────┬────┬────────┐
│ S1 │ S0 │ Output │
├────┼────┼────────┤
│ 0 │ 0 │ I0 │
│ 0 │ 1 │ I1 │
│ 1 │ 0 │ I2 │
│ 1 │ 1 │ I3 │
└────┴────┴────────┘
Boolean Expression:
Y = S̄1·S̄0·I0 + S̄1·S0·I1 + S1·S̄0·I2 + S1·S0·I3
Circuit Diagram:
I0 ──┬───┐
│ └─── AND ───┐
S0 ──┼───────── NOT ──┤
│ │
S1 ──┼───────── NOT ──┤
│ │
I1 ──┤ │
│ ┌─── AND ────┤
S0 ──┼───┘ │ ┌────┐
│ ├────┤ │
S1 ──┼───── NOT ──────┤ │ OR ├─── Y
│ │ │ │
I2 ──┤ │ └────┘
│ ┌─── AND ────┤
S0 ──┼───┼─── NOT ────┤
│ │ │
S1 ──┼───┘ │
│ │
I3 ──┤ │
│ └─── AND ────┘
S0 ──┤
│
S1 ──┘
Arithmetic Circuits
Half Adder
Function: Adds two single bits, producing a sum and carry.
Truth Table:
┌───┬───┬─────┬───────┐
│ A │ B │ Sum │ Carry │
├───┼───┼─────┼───────┤
│ 0 │ 0 │ 0 │ 0 │
│ 0 │ 1 │ 1 │ 0 │
│ 1 │ 0 │ 1 │ 0 │
│ 1 │ 1 │ 0 │ 1 │
└───┴───┴─────┴───────┘
Boolean Expressions:
Sum = A ⊕ B (XOR)
Carry = A · B (AND)
Circuit:
┌────┐
A ──┬───┤ │
│ │ =1 ├─── Sum
B ──┼─┬─┤ │
│ │ └────┘
│ │
│ │ ┌────┐
│ └─┤ │
│ │ & ├─── Carry
└───┤ │
└────┘
Full Adder
Function: Adds three bits (A, B, Cin), producing sum and carry out.
Truth Table:
┌───┬───┬─────┬─────┬──────┐
│ A │ B │ Cin │ Sum │ Cout │
├───┼───┼─────┼─────┼──────┤
│ 0 │ 0 │ 0 │ 0 │ 0 │
│ 0 │ 0 │ 1 │ 1 │ 0 │
│ 0 │ 1 │ 0 │ 1 │ 0 │
│ 0 │ 1 │ 1 │ 0 │ 1 │
│ 1 │ 0 │ 0 │ 1 │ 0 │
│ 1 │ 0 │ 1 │ 0 │ 1 │
│ 1 │ 1 │ 0 │ 0 │ 1 │
│ 1 │ 1 │ 1 │ 1 │ 1 │
└───┴───┴─────┴─────┴──────┘
Boolean Expressions:
Sum = A ⊕ B ⊕ Cin
Cout = (A · B) + (Cin · (A ⊕ B))
Circuit (using two half adders):
┌─────────────┐
A ───┤ │
│ Half Adder ├─── S1
B ───┤ │
└──────┬──────┘
│ C1
│
│ ┌─────────────┐
S1 ───┼────────┤ │
│ │ Half Adder ├─── Sum
Cin ──┼────────┤ │
│ └──────┬──────┘
│ │ C2
│ │
│ ┌────┐ │
└─────┤ │ │
│ OR ├────┘─── Cout
C2 ─────────┤ │
└────┘
4-Bit Ripple-Carry Adder
Function: Adds two 4-bit numbers using cascaded full adders.
A3 A2 A1 A0 (4-bit number A)
B3 B2 B1 B0 (4-bit number B)
───────────
S3 S2 S1 S0 (4-bit sum)
C4 (carry out)
Circuit:
A0 ─┐ B0 A1 ─┐ B1 A2 ─┐ B2 A3 ─┐ B3
│ │ │ │ │ │ │ │
├───┤ ├───┤ ├───┤ ├───┤
│ FA│ Cin=0 │ FA│ │ FA│ │ FA│
└─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘
│ │ Cout │ │ Cout │ │ Cout │ │ Cout
│ └──────────────┘ │ │ │ │ │
│ └──────────────┘ │ │ │
│ └──────────────┘ │
│ │
S0 S1 S2 S3 C4
Operation:
- Bit 0: Adds A0 + B0 + 0, produces S0 and C1
- Bit 1: Adds A1 + B1 + C1, produces S1 and C2
- Bit 2: Adds A2 + B2 + C2, produces S2 and C3
- Bit 3: Adds A3 + B3 + C3, produces S3 and C4
Limitation: Ripple effect causes delay (carry must propagate through all bits).
4-Bit Subtractor
Method: Use two's complement and addition
A - B = A + (two's complement of B)
= A + (NOT B + 1)
Circuit: Use a 4-bit adder with XOR gates to invert B, and set Cin=1
Sub (control)
│
├──────────────┐
│ │
A3─┐ ┌──────┼───┐ B3 │
│ │ XOR │ │ │ │
├──┤ ├───┤ │ │
│ └──────┘ │ FA│ │
└──────────┬──┤ │ │
│ └─┬─┘ │
│ │ Cout │
[Similar for bits 2, 1, 0] │
│
Cin
When Sub=0: Normal addition (B passes through XORs unchanged)
When Sub=1: Subtraction (B is inverted, Cin=1 completes two's complement)
Universal Gates
Building All Gates from NAND
NAND is universal - any logic function can be built using only NAND gates.
NOT using NAND:
A ───┬─── NAND ─── Ā
│
└─── (connect both inputs)
AND using NAND:
A ─┬─── NAND ─── NAND ─── A·B
│
B ─┘
OR using NAND:
A ─── NAND ─┬─── NAND ─── A+B
│
B ─── NAND ─┘
Building All Gates from NOR
NOT using NOR:
A ───┬─── NOR ─── Ā
│
└───
OR using NOR:
A ─┬─── NOR ─── NOR ─── A+B
│
B ─┘
AND using NOR:
A ─── NOR ─┬─── NOR ─── A·B
│
B ─── NOR ─┘
Boolean Algebra Simplification
Example: Simplify F = A·B̄·C + A·B·C + A·B·C̄
Step 1: Factor out common terms
F = A·B̄·C + A·B·C + A·B·C̄
= A·B̄·C + A·B·(C + C̄)
Step 2: Apply inverse law (C + C̄ = 1)
= A·B̄·C + A·B·1
= A·B̄·C + A·B
Step 3: Factor A
= A·(B̄·C + B)
Step 4: Expand
= A·(B̄·C + B)
= A·((B̄ + B)·(C + B)) [Distributive law]
= A·(1·(C + B))
= A·(B + C)
Result: F = A·(B + C), much simpler!
De Morgan's Theorems in Practice
Example: Simplify F = ¯(A·B + C·D̄)
Apply De Morgan:
F = ¯(A·B) · ¯(C·D̄)
= (Ā + B̄) · (C̄ + D)
Karnaugh Maps (K-Maps)
K-maps provide a visual method for Boolean simplification.
2-Variable K-Map
B
┌───┬───┐
0 │ │ │
A ├───┼───┤
1 │ │ │
└───┴───┘
3-Variable K-Map
BC
00 01 11 10
┌───┬───┬───┬───┐
0 │ │ │ │ │
A ├───┼───┼───┼───┤
1 │ │ │ │ │
└───┴───┴───┴───┘
4-Variable K-Map Example
Problem: Simplify F(A,B,C,D) with minterms: 0,1,2,5,8,9,10
CD
00 01 11 10
┌───┬───┬───┬───┐
00 │ 1 │ 1 │ 0 │ 1 │ ← AB=00
AB ├───┼───┼───┼───┤
01 │ 0 │ 1 │ 0 │ 0 │ ← AB=01
├───┼───┼───┼───┤
11 │ 0 │ 0 │ 0 │ 0 │ ← AB=11
├───┼───┼───┼───┤
10 │ 1 │ 1 │ 0 │ 1 │ ← AB=10
└───┴───┴───┴───┘
Groups:
- Group 1: Top row (00,01,10) → Ā·D̄
- Group 2: Left column (0,8) → B̄·C̄·D̄
Simplified: F = Ā·D̄ + B̄·C̄·D̄
Programming Examples
Python: Logic Gate Simulation
def NOT(a):
return 1 if a == 0 else 0
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 NAND(a, b):
return NOT(AND(a, b))
def NOR(a, b):
return NOT(OR(a, b))
def XOR(a, b):
return 1 if (a != b) else 0
def XNOR(a, b):
return NOT(XOR(a, b))
# Truth table generator
def truth_table(func, num_inputs):
print(f"Truth table for {func.__name__}:")
if num_inputs == 1:
print("A | Out")
print("--|----")
for a in [0, 1]:
print(f"{a} | {func(a)}")
elif num_inputs == 2:
print("A B | Out")
print("----|----")
for a in [0, 1]:
for b in [0, 1]:
print(f"{a} {b} | {func(a, b)}")
# Test
truth_table(XOR, 2)
Python: Full Adder
def half_adder(a, b):
"""Returns (sum, carry)"""
sum_bit = XOR(a, b)
carry = AND(a, b)
return (sum_bit, carry)
def full_adder(a, b, cin):
"""Returns (sum, cout)"""
# First half adder
s1, c1 = half_adder(a, b)
# Second half adder
sum_bit, c2 = half_adder(s1, cin)
# Combine carries
cout = OR(c1, c2)
return (sum_bit, cout)
# Test
print("Full Adder Truth Table:")
print("A B Cin | Sum Cout")
print("--------|----------")
for a in [0, 1]:
for b in [0, 1]:
for cin in [0, 1]:
sum_bit, cout = full_adder(a, b, cin)
print(f"{a} {b} {cin} | {sum_bit} {cout}")
Python: 4-Bit Adder
def ripple_carry_adder(a, b):
"""
Adds two 4-bit numbers represented as lists.
a, b: lists of 4 bits [MSB, ..., LSB]
Returns: (sum, carry_out)
"""
result = [0, 0, 0, 0]
carry = 0
# Process from LSB to MSB (right to left)
for i in range(3, -1, -1):
sum_bit, carry = full_adder(a[i], b[i], carry)
result[i] = sum_bit
return (result, carry)
# Test: 5 + 6 = 11
a = [0, 1, 0, 1] # 0101 = 5
b = [0, 1, 1, 0] # 0110 = 6
sum_bits, carry = ripple_carry_adder(a, b)
print(f" {''.join(map(str, a))} ({int(''.join(map(str, a)), 2)})")
print(f"+ {''.join(map(str, b))} ({int(''.join(map(str, b)), 2)})")
print(f"-------")
print(f"{carry}{''.join(map(str, sum_bits))} ({int(''.join(map(str, sum_bits)), 2)})")
Exercises
Basic Exercises
Truth Tables
- Create truth tables for: A·B + Ā·B̄
- Create truth table for: (A+B)·(A+C)
- Verify De Morgan's theorem: ¯(A+B) = Ā·B̄
Gate Implementation
- Implement OR using only NAND gates
- Implement XOR using AND, OR, and NOT gates
- Draw a circuit for F = A·B̄ + Ā·B
Boolean Algebra
- Simplify: A + A·B
- Simplify: A·B + A·B̄
- Simplify: (A+B)·(A+B̄)
Intermediate Exercises
Circuit Analysis
- Given F = A·B·C + A·B·C̄ + A·B̄·C, create truth table
- Simplify using Boolean algebra
- Draw the circuit using minimum gates
Combinational Circuits
- Design a 3-to-8 decoder
- Design a 2-to-1 multiplexer using only NAND gates
- Create a circuit that outputs 1 when exactly two of three inputs are 1
Arithmetic Circuits
- Design a half subtractor (difference and borrow)
- Trace a 4-bit addition: 1010 + 0111 through a ripple-carry adder
- Design a circuit to detect overflow in 4-bit addition
Advanced Exercises
K-Map Simplification
- Use K-map to simplify F(A,B,C,D) = Σm(0,1,2,5,6,7,8,9,14)
- Find minimal SOP (Sum of Products) for a 4-variable function
- Identify and eliminate redundant logic in a complex circuit
Complex Design
- Design an ALU that can perform AND, OR, ADD on 4-bit inputs
- Create a magnitude comparator for two 4-bit numbers
- Design a binary to Gray code converter
Optimization
- Compare gate count for F = A·B·C + A·B·C̄ + A·B̄·C before and after simplification
- Implement a full adder using only 5 NAND gates
- Design a carry-lookahead adder and compare to ripple-carry
Problem Solving
- Design a circuit to determine if a 4-bit number is divisible by 3
- Create a priority encoder (outputs position of highest-order 1)
- Design a parity generator/checker for 8-bit data
Summary
In this reading, we explored the fundamental building blocks of digital circuits:
Key Concepts:
- Boolean algebra provides the mathematical foundation for logic gates
- Seven basic gates: NOT, AND, OR, NAND, NOR, XOR, XNOR
- Universal gates: NAND and NOR can implement any logic function
- Combinational circuits combine gates to perform complex operations
- Arithmetic circuits: Half adders, full adders, and ripple-carry adders perform binary arithmetic
Important Skills:
- Creating and analyzing truth tables
- Simplifying Boolean expressions using algebra and K-maps
- Designing circuits from Boolean expressions
- Understanding how gates combine to create functional units
Why This Matters:
- All computer operations are built from logic gates
- Understanding gates helps you comprehend CPU operations
- Foundation for designing efficient digital circuits
- Essential for computer architecture and digital design
Further Reading
- "Digital Design and Computer Architecture" by Harris & Harris
- Karnaugh map techniques for 5+ variables
- Sequential circuits and state machines
- Hardware description languages (Verilog, VHDL)
Next Steps
Now that you understand how logic gates process binary data, you're ready to learn how the CPU orchestrates these operations to execute programs.
Next Reading: 03-cpu-architecture.md - CPU Architecture
Module 5: Computer Architecture | Reading 2 of 5