Combinational Logic Circuits: Boolean Algebra, Universal Gates, and Adders

SS2 Term 1 • Week 3

About 45 minutes

In Junior Secondary 3, you were introduced to the basic logic gates: AND, OR, and NOT. You learned that these gates examine binary inputs and generate high or low output voltages.

In SS 2, we advance from isolated gates to Combinational Logic Circuit Design. How does an Arithmetic Logic Unit actually calculate $7 + 5$ in silicon? How do hardware architects simplify equations with dozens of inputs to use the minimum number of transistors, saving silicon space and battery power?

In this lesson, we study Boolean Algebra Theorems, explore Universal Gates, and build the foundation of computer arithmetic: the Half Adder and Full Adder.

Learning Outcomes

By the end of this lesson, you will be able to:

Simplify complex logic expressions using Boolean Algebra and De Morgan's Theorems.
Synthesize elementary logic gates (NOT, AND, OR) using only NAND or NOR universal building blocks.
Analyze and construct the Half Adder and Full Adder truth tables and circuit diagrams.
Evaluate Ripple-Carry Delay in multi-bit ALU binary adders.

Key Vocabulary

Term	Technical Definition
Combinational Circuit	A digital circuit whose output depends exclusively on the current combination of input signals (no memory feedback).
Boolean Algebra	The mathematical system of logic formulated by George Boole operating on truth values ($0$ and $1$).
Universal Gate	A logic gate (specifically NAND or NOR) that can implement any Boolean function without using any other gate types.
Half Adder	A combinational circuit that computes the sum and carry of two 1-bit inputs.
Full Adder	A combinational circuit that computes the sum and carry of three inputs: two operand bits plus an incoming carry bit.
Propagation Delay	The time required for an electrical signal to travel through logic gates and produce a stable output.

Boolean Algebra Laws and Simplification

Hardware engineers simplify logic equations before manufacturing microchips to minimize gate counts, reduce power consumption, and speed up calculations.

Core Boolean Theorems:

Law	AND Form ($A \cdot B$)	OR Form ($A + B$)
Identity Law	$A \cdot 1 = A$	$A + 0 = A$
Null (Domination) Law	$A \cdot 0 = 0$	$A + 1 = 1$
Idempotent Law	$A \cdot A = A$	$A + A = A$
Complement Law	$A \cdot \overline{A} = 0$	$A + \overline{A} = 1$
Involution Law	$\overline{\overline{A}} = A$	$\overline{\overline{A}} = A$
Distributive Law	$A + (B \cdot C) = (A + B) \cdot (A + C)$	$A \cdot (B + C) = (A \cdot B) + (A \cdot C)$

De Morgan's Theorems:

De Morgan's laws allow engineers to convert between AND and OR logic by inverting variables:

First Law: $\overline{A \cdot B} = \overline{A} + \overline{B}$ (The NOT of an AND is equivalent to NOT-A OR NOT-B)
Second Law: $\overline{A + B} = \overline{A} \cdot \overline{B}$ (The NOT of an OR is equivalent to NOT-A AND NOT-B)

Universal Gates: The Power of NAND

In semiconductor manufacturing (such as TSMC or Intel fabs), it is cheaper and faster to print billions of identical gates onto a silicon wafer rather than etching dozens of different gate designs.

Because NAND is a Universal Gate, every logic function can be synthesized using NAND gates alone:

1. Constructing a NOT Gate from NAND:
   Tie both inputs together:
   A ────┬───[ NAND ]──── Output = NOT A
         └───┘

2. Constructing an AND Gate from NAND:
   A ──┬──[ NAND ]───┬──[ NAND ]─── Output = A AND B
   B ──┘              └──┘

3. Constructing an OR Gate from NAND (using De Morgan's: !(!A * !B) = A + B):
   A ─┬─[ NAND ]──┐
      └─┘         ├──[ NAND ]──── Output = A OR B
   B ─┬─[ NAND ]──┘
      └─┘

Building Arithmetic: Half Adders and Full Adders

How does a CPU add binary numbers? Let us look at single-bit addition: - $0 + 0 = 0$ - $0 + 1 = 1$ - $1 + 0 = 1$ - $1 + 1 = 10_2$ (Sum = $0$, Carry = $1$)

1. The Half Adder

Notice that the Sum column matches the XOR Gate truth table, and the Carry column matches the AND Gate truth table!

Inputs       Outputs
A   B   |   Sum   Carry
0   0   |    0      0
0   1   |    1      0
1   0   |    1      0
1   1   |    0      1

Schematic:
A ───────┬─────────[ XOR ]────── Sum (A ⊕ B)
         │        /
B ───┬───┼───────┘
     │   │
     │   └─────────[ AND ]────── Carry (A · B)
     └─────────────┘

Limitation: A Half Adder cannot accept a carry-in from a previous column. It can only add the lowest bit ($2^0$).

2. The Full Adder

To add multi-bit numbers, we need a circuit that adds three inputs: 1. Operand Bit $A$ 2. Operand Bit $B$ 3. Carry-In Bit ($C_{\text{in}}$)

A Full Adder is constructed by combining two Half Adders and one OR Gate:

Inputs             Outputs
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

$$\text{Sum} = A \oplus B \oplus C_{\text{in}}$$

$$C_{\text{out}} = (A \cdot B) + (C_{\text{in}} \cdot (A \oplus B))$$

Practical Activity: Software Logic Simulator in Python

Let us implement a software simulation of digital logic gates, a Half Adder, and a 4-bit Ripple-Carry Adder to see how silicon ALUs add multi-bit binary numbers.

Step 1: Create `logic_adder_sim.py`

# Elementary Logic Gates
def gate_not(a): return 1 if a == 0 else 0
def gate_and(a, b): return 1 if (a == 1 and b == 1) else 0
def gate_or(a, b): return 1 if (a == 1 or b == 1) else 0
def gate_xor(a, b): return 1 if a != b else 0
def gate_nand(a, b): return gate_not(gate_and(a, b))

# Half Adder Component
def half_adder(a, b):
    s = gate_xor(a, b)
    c = gate_and(a, b)
    return s, c

# Full Adder Component (Constructed from two Half Adders and an OR gate)
def full_adder(a, b, cin):
    s1, c1 = half_adder(a, b)
    s, c2 = half_adder(s1, cin)
    cout = gate_or(c1, c2)
    return s, cout

# 4-Bit Ripple Carry Adder
def ripple_carry_adder_4bit(a_bits, b_bits):
    cin = 0
    sum_bits = []
    # Iterate from LSB (index 0) to MSB (index 3)
    for i in range(4):
        s, cin = full_adder(a_bits[i], b_bits[i], cin)
        sum_bits.append(s)
    return sum_bits, cin

# Test: Add 7 (0111) + 5 (0101) = 12 (1100)
# Binary lists stored in LSB-first order:
# 7 in binary is 0111 -> [1, 1, 1, 0]
# 5 in binary is 0101 -> [1, 0, 1, 0]
A = [1, 1, 1, 0]
B = [1, 0, 1, 0]

result_bits, final_carry = ripple_carry_adder_4bit(A, B)
result_reversed = list(reversed(result_bits))

print("=== 4-Bit Ripple-Carry Adder Simulation ===")
print(f"Input A:      {'.join(map(str, reversed(A)))}  (Decimal 7)")
print(f"Input B:      {'.join(map(str, reversed(B)))}  (Decimal 5)")
print(f"Sum Bits:     {'.join(map(str, result_reversed))}  (Decimal 12)")
print(f"Final Carry:  {final_carry}")

Step 2: Run the Simulation

python logic_adder_sim.py

Expected Results and Model Output

When you run logic_adder_sim.py, you will see:

=== 4-Bit Ripple-Carry Adder Simulation ===
Input A:      0111  (Decimal 7)
Input B:      0101  (Decimal 5)
Sum Bits:     1100  (Decimal 12)
Final Carry:  0

The circuit accurately performs binary addition ($7 + 5 = 12$) by propagating the carry bit through each bit position, just like physical hardware!

Common Mistakes to Avoid

Confusing Logic Addition with Decimal Addition: In Boolean algebra, $1 + 1 = 1$ (True OR True is True). In binary arithmetic addition, $1 + 1 = 10_2$ (Sum is $0$, Carry is $1$). Keep Boolean OR operations distinct from arithmetic addition.
Forgetting Carry Propagation Delay: In a 64-bit Ripple-Carry Adder, bit 63 cannot finalize its output until the carry signal ripples through all preceding 62 adders! Modern CPUs use Carry-Lookahead Adders (CLA) to calculate carries in parallel.
Misapplying De Morgan's Theorems: Remember: when you break the bar over an expression, you must change the operator! $\overline{A \cdot B} = \overline{A} + \overline{B}$ (AND changes to OR).

Notebook Summary

Boolean Algebra provides formal mathematical rules to simplify logic circuits, reducing manufacturing cost and propagation latency.
De Morgan's Laws convert conjunctions to disjunctions and vice versa: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
NAND and NOR are Universal Gates capable of synthesizing NOT, AND, OR, and XOR circuits independently.
A Half Adder adds two 1-bit values (Sum = XOR, Carry = AND).
A Full Adder adds three 1-bit values ($A, B, C_{\text{in}}$) and forms the building block for multi-bit ALU adders.

Optional Extension Challenge

Design a 2-to-1 Multiplexer (MUX) using only logic gates. A multiplexer has two data inputs ($D_0, D_1$) and one selector input ($S$). When $S = 0$, Output $= D_0$. When $S = 1$, Output $= D_1$. Write the Boolean expression and test it in Python.