Chapter 08 of 39

Logic Gates & Boolean Algebra

Every operation a processor performs, from adding two numbers to deciding whether a branch is taken, finally comes down to tiny circuits that take some bits in and produce a bit out. These circuits are called logic gates, and the mathematics we use to describe and simplify them is Boolean algebra, developed by George Boole in the mid-1800s and applied to switching circuits by Claude Shannon in 1938.

Why should a computer architecture student care? Because a simpler Boolean expression means fewer gates, which means a smaller, cheaper, faster and less power-hungry chip. A ripple of three gate delays instead of five on a critical path can decide the clock speed of an entire processor.

Boolean algebra is an algebra over the two values 0 (false) and 1 (true), with the operations AND (·), OR (+) and NOT (′). A logic gate is a physical circuit that computes one Boolean operation.

In this chapter we cover the basic and universal gates, the laws of Boolean algebra, canonical SOP and POS forms, and simplification with Karnaugh maps, including don't-care conditions and essential prime implicants. Every law and every K-map result here was checked by brute force over all input combinations with a Python script. We use A′ for NOT A, AB for A AND B, and A + B for A OR B.


The Basic Gates

NOT, AND, OR

A

B

NOT A (A′)

AND (AB)

OR (A + B)

0

0

1

0

0

0

1

1

0

1

1

0

0

0

1

1

1

0

1

1

  • AND is 1 only when all inputs are 1 (think of switches in series).

  • OR is 1 when at least one input is 1 (switches in parallel).

  • NOT (inverter) flips its single input.

NAND, NOR, XOR, XNOR

A

B

NAND (AB)′

NOR (A + B)′

XOR A ⊕ B

XNOR (A ⊕ B)′

0

0

1

1

0

1

0

1

1

0

1

0

1

0

1

0

1

0

1

1

0

0

0

1

  • XOR (exclusive OR) is 1 when the inputs are different: A ⊕ B = A′B + AB′. For many inputs, XOR is 1 when an odd number of inputs are 1, which is why it computes parity and the sum bit of an adder.

  • XNOR is 1 when the inputs are equal: (A ⊕ B)′ = A′B′ + AB. It is the 1-bit equality comparator.

Useful XOR facts: A ⊕ 0 = A, A ⊕ 1 = A′, A ⊕ A = 0, A ⊕ A′ = 1. So XOR with a control bit acts as a controllable inverter, a trick used in the adder-subtractor circuit.

Gates in Hardware

In CMOS technology, the natural gates are the inverting ones. A 2-input NAND or NOR needs 4 transistors, while AND and OR are built as NAND or NOR followed by an inverter (6 transistors). That is one reason designers love NAND and NOR.


Universal Gates

A gate is universal (functionally complete) if every Boolean function can be built using only that type of gate. NAND and NOR are each universal.

The proof is simple: {AND, OR, NOT} can express any function (any truth table can be written as an OR of ANDs), so it is enough to build NOT, AND and OR from NAND alone:

Using NAND only                          Using NOR only
NOT A  = NAND(A, A)                      NOT A  = NOR(A, A)
A AND B = NAND( NAND(A,B), NAND(A,B) )   A OR B  = NOR( NOR(A,B), NOR(A,B) )
A OR B  = NAND( NAND(A,A), NAND(B,B) )   A AND B = NOR( NOR(A,A), NOR(B,B) )
         (by De Morgan: (A′B′)′ = A + B)          (by De Morgan: (A′ + B′)′ = AB)

XOR from Four NAND Gates

n1 = NAND(A, B)
n2 = NAND(A, n1)
n3 = NAND(B, n1)
Y  = NAND(n2, n3)  = A ⊕ B

Why it works:
n2 = (A · (AB)′)′ = (A(A′ + B′))′ = (AB′)′
n3 = (B · (AB)′)′ = (B(A′ + B′))′ = (A′B)′
Y  = (n2 · n3)′  = ((AB′)′ · (A′B)′)′ = AB′ + A′B = A ⊕ B

The minimum gate counts that often appear in exams:

Function

Minimum 2-input NAND gates

Minimum 2-input NOR gates

NOT

1

1

AND

2

3

OR

3

2

XOR

4

5

XNOR

5

4

Notice the symmetry: what is cheap with NAND is expensive with NOR and vice versa, because the two are duals. (The same four-gate structure with NOR gates gives XNOR; one more NOR as an inverter gives XOR.)


Laws of Boolean Algebra

Law

OR form

AND form (dual)

Identity

A + 0 = A

A · 1 = A

Null (domination)

A + 1 = 1

A · 0 = 0

Idempotent

A + A = A

A · A = A

Complement

A + A′ = 1

A · A′ = 0

Involution

(A′)′ = A

(same law; it is its own dual)

Commutative

A + B = B + A

AB = BA

Associative

(A + B) + C = A + (B + C)

(AB)C = A(BC)

Distributive

A + BC = (A + B)(A + C)

A(B + C) = AB + AC

Absorption

A + AB = A

A(A + B) = A

Redundant literal

A + A′B = A + B

A(A′ + B) = AB

De Morgan

(A + B)′ = A′B′

(AB)′ = A′ + B′

Consensus

AB + A′C + BC = AB + A′C

(A + B)(A′ + C)(B + C) = (A + B)(A′ + C)

Two laws surprise students coming from ordinary algebra:

  • A + BC = (A + B)(A + C): OR distributes over AND. This is false for numbers but true here. Check: if A = 1 both sides are 1; if A = 0 both sides are BC.

  • No cancellation: A + B = A + C does not imply B = C (try A = 1). There is no subtraction or division in Boolean algebra.

Duality Principle

If a Boolean identity is true, its dual is also true. The dual is obtained by swapping + with ·, and 0 with 1, while leaving variables and complements unchanged.

That is why every law above comes in a pair. Do not confuse the dual with the complement: the complement also complements every variable (De Morgan), the dual does not.

De Morgan's Theorem in Practice

To complement any expression: swap + and ·, and complement every literal. Keep the original grouping by adding brackets.

F  = A′B + CD′
F′ = (A′B)′ · (CD′)′
   = (A + B′)(C′ + D)

Proving the Consensus Theorem

The term BC is redundant in AB + A′C + BC. Proof:

BC = BC(A + A′)                 complement law: A + A′ = 1
   = ABC + A′BC
AB + A′C + ABC + A′BC
 = AB(1 + C) + A′C(1 + B)       group
 = AB + A′C                     null law: 1 + X = 1

Intuition: BC = 1 means B = 1 and C = 1. Then whatever A is, either AB (if A = 1) or A′C (if A = 0) is already 1. BC never adds anything new.

Example 1: Algebraic Simplification

Simplify F = A′B′C + A′BC + AB′C + ABC′ + ABC.

F = A′B′C + A′BC + AB′C + ABC + ABC′
  = A′C(B′ + B) + AC(B′ + B) + ABC′     group pairs
  = A′C + AC + ABC′
  = C(A′ + A) + ABC′
  = C + ABC′
  = C + AB                               redundant literal: X + X′Y = X + Y  (X = C)

Algebra works, but it needs insight to choose the right steps. Karnaugh maps make this systematic.


Canonical Forms: Minterms and Maxterms

A minterm is an AND term that contains every variable exactly once (complemented or not); it is 1 for exactly one row of the truth table. A maxterm is an OR term that contains every variable exactly once; it is 0 for exactly one row.

Row (ABC)

Minterm

Maxterm

0 (000)

m0 = A′B′C′

M0 = A + B + C

1 (001)

m1 = A′B′C

M1 = A + B + C′

5 (101)

m5 = AB′C

M5 = A′ + B + C′

7 (111)

m7 = ABC

M7 = A′ + B′ + C′

Memory aid: in a minterm, a 0 in the row number becomes a complemented variable; in a maxterm it is the opposite (a 1 becomes complemented). And Mi = (mi)′.

  • Canonical SOP (sum of products): OR of the minterms where F = 1. Written F = Σm(…).

  • Canonical POS (product of sums): AND of the maxterms where F = 0. Written F = ΠM(…).

The two lists are complementary: the row numbers missing from Σ appear in Π. For the function of Example 1:

F(A,B,C) = Σm(1, 3, 5, 6, 7) = ΠM(0, 2, 4)
         = (A + B + C)(A + B′ + C)(A′ + B + C)
Simplified SOP: C + AB
Simplified POS: (A + C)(B + C)      ← check: (A + C)(B + C) = C + AB by the distributive law

How Many Functions Are There?

A truth table of n variables has 2n rows, and each row's output can be 0 or 1 independently. So there are 22n different Boolean functions of n variables: 16 for n = 2 (which is why there are 16 possible 2-input gates) and 256 for n = 3.


Karnaugh Maps (K-maps)

Algebraic simplification relies on spotting pairs like XY + XY′ = X. A Karnaugh map arranges the truth table so that such pairs sit next to each other and you can see them.

A K-map is a grid with one cell per minterm, with rows and columns labelled in Gray code order (00, 01, 11, 10) so that any two adjacent cells, including wrap-around cells on opposite edges, differ in exactly one variable.

(Gray code was introduced in BCD, Gray Code, ASCII & Unicode; this is one of its most important uses.)

4-variable K-map: minterm numbers in each cell

           CD=00  CD=01  CD=11  CD=10
AB=00   |   0   |   1   |   3   |   2   |
AB=01   |   4   |   5   |   7   |   6   |
AB=11   |  12   |  13   |  15   |  14   |
AB=10   |   8   |   9   |  11   |  10   |

Note that columns 11 and 10 are swapped compared with normal counting, and so are rows 11 and 10. That is the Gray order.

Grouping Rules

  1. Group only 1s (for SOP), or only 0s (for POS).

  2. Group sizes must be powers of 2: 1, 2, 4, 8, 16. A group of 2k cells eliminates k variables.

  3. Groups must be rectangles (including squares). The map wraps around: the left and right edges are adjacent, top and bottom are adjacent, and so the four corners form a group of four.

  4. Make each group as large as possible, and use as few groups as possible. Groups may overlap.

  5. For each group, keep the variables that are constant across it: 1 → uncomplemented, 0 → complemented.

Example 2: Corners and Centre

Simplify F(A,B,C,D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).

           CD=00  CD=01  CD=11  CD=10
AB=00   |   1   |   0   |   0   |   1   |
AB=01   |   0   |   1   |   1   |   0   |
AB=11   |   0   |   1   |   1   |   0   |
AB=10   |   1   |   0   |   0   |   1   |

Group 1: the four corners (0, 2, 8, 10).  B = 0 and D = 0 throughout → B′D′
Group 2: the centre square (5, 7, 13, 15). B = 1 and D = 1 throughout → BD

F = B′D′ + BD   ( = (B ⊕ D)′, an XNOR )

Eight minterms of 4 literals each (32 literals) became 4 literals. The corner group is the one students miss most often.

Don't-Care Conditions

Sometimes certain input combinations can never occur (for example the patterns 1010 to 1111 in a BCD digit), or we do not care about the output for them. These are marked X (or d) in the K-map.

A don't-care cell may be treated as 1 or 0, whichever gives a simpler result. Use an X in a group only if it makes the group larger; never create a group that covers only don't-cares.

Example 3: Using Don't-Cares

Simplify F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).

           CD=00  CD=01  CD=11  CD=10
AB=00   |   X   |   1   |   1   |   X   |
AB=01   |   0   |   X   |   1   |   0   |
AB=11   |   0   |   0   |   1   |   0   |
AB=10   |   0   |   0   |   1   |   0   |

Group 1: column CD = 11 (3, 7, 15, 11)                     → CD
Group 2: m1 still needs covering. Two equally good choices:
   row AB = 00 (0, 1, 3, 2), using don't-cares 0 and 2       → A′B′
   or the square (1, 3, 5, 7), using don't-care 5            → A′D

F = CD + A′B′     or     F = CD + A′D     (both have 4 literals)

Both answers are correct minimal forms; they differ only on the don't-care inputs. In an exam, either should be accepted, but count literals to be sure both are truly minimal.


Prime Implicants and Essential Prime Implicants

For larger problems (and for computer algorithms like Quine-McCluskey), we need precise vocabulary:

  • Implicant: a product term that is 1 only where F is 1 (or don't-care). Any valid group in the K-map.

  • Prime implicant (PI): an implicant that cannot be enlarged (no bigger group contains it).

  • Essential prime implicant (EPI): a prime implicant that covers at least one 1 (minterm, not a don't-care) that no other prime implicant covers. Every minimal solution must contain all EPIs.

Procedure: find all PIs, include all EPIs, then cover any remaining 1s with as few extra PIs as possible.

In Example 3 the prime implicants are A′B′, A′D and CD. Minterm 11 is covered only by CD, so CD is essential. Minterm 1 is covered by both A′B′ and A′D, so neither of them is essential, and that is exactly why there are two minimal answers.

Example 4: No Essential Prime Implicants

F(A,B,C) = Σm(0, 1, 2, 5, 6, 7).

          BC=00  BC=01  BC=11  BC=10
A=0    |   1   |   1   |   0   |   1   |
A=1    |   0   |   1   |   1   |   1   |

Prime implicants (all pairs, no group of 4 is possible):
  A′B′ (0,1)   A′C′ (0,2)   B′C (1,5)   BC′ (2,6)   AC (5,7)   AB (6,7)

Every 1 is covered by exactly two PIs → no essential prime implicants.
The PIs form a cycle 0-1-5-7-6-2-0, and there are two minimal covers:

  Cover 1: A′B′ (0,1) + AC (5,7) + BC′ (2,6)   → all six minterms ✓
  Cover 2: A′C′ (0,2) + B′C (1,5) + AB (6,7)   → all six minterms ✓

So F = A′B′ + BC′ + AC = A′C′ + B′C + AB. This "cyclic" situation is a favourite trick question: the answer to "how many essential prime implicants?" is zero, while the number of prime implicants is six.

Example 5: A Typical Exam Problem

F(A,B,C,D) = Σm(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14). Find the PIs, the EPIs and a minimal SOP.

           CD=00  CD=01  CD=11  CD=10
AB=00   |   1   |   1   |   0   |   1   |
AB=01   |   1   |   1   |   0   |   1   |
AB=11   |   1   |   1   |   0   |   1   |
AB=10   |   1   |   1   |   0   |   0   |

C′   : the two left columns, 8 cells (0,1,4,5,8,9,12,13)
A′D′ : cells 0, 4 (col 00) and 2, 6 (col 10), rows 00-01 → wraps left/right
BD′  : cells 4, 12 (col 00) and 6, 14 (col 10), rows 01-11

PIs:  C′, A′D′, BD′
EPIs: C′  (only one covering 1, 9, ...),
      A′D′ (only one covering 2),
      BD′  (only one covering 14)

F = C′ + A′D′ + BD′

Two-Level Implementation with NAND or NOR Only

Any minimal SOP is an AND-OR circuit. By De Morgan, an AND-OR circuit is identical to a NAND-NAND circuit:

F = AB + CD
  = ((AB + CD)′)′
  = ((AB)′ · (CD)′)′
  = NAND( NAND(A,B), NAND(C,D) )

So "replace every gate of a two-level AND-OR circuit by NAND" gives the same function (single literals feeding the OR level must be inverted). Similarly, a POS (OR-AND) circuit becomes NOR-NOR. This is why SOP is natural for NAND-based logic.


Common Mistakes

  • Labelling K-map rows/columns 00, 01, 10, 11. They must be in Gray order: 00, 01, 11, 10.

  • Forgetting wrap-around and corner groups.

  • Making groups of 3 or 6. Only powers of 2 are allowed.

  • Grouping only don't-cares, or using a don't-care when it does not enlarge a group.

  • Mixing up minterm and maxterm literals. For row 101: minterm AB′C, maxterm A′ + B + C′.

  • Confusing the dual with the complement. The dual of A + BC is A(B + C); the complement is A′(B′ + C′).

  • Assuming the minimal form is unique. With cyclic PIs or don't-cares there can be several minimal answers.

  • Using ordinary algebra rules, like cancelling a common term from both sides.


GATE and Interview Questions

Q1. How many Boolean functions of 3 variables exist? How many 2-input gates are possible?

223 = 28 = 256 functions of 3 variables. For 2 inputs, 24 = 16 possible functions, so 16 possible 2-input "gates" (including trivial ones like constant 0 and constant 1).

Q2. A function is self-dual if it equals its own dual. How many self-dual functions of n variables are there?

A self-dual function satisfies F(x′) = F(x)′, so the output for each input determines the output for its complement. The 2n rows form 2n−1 complementary pairs, each with 2 choices: 22n−1 self-dual functions. For n = 3 this is 24 = 16 (checked by brute force).

Q3. What is the minimum number of 2-input NAND gates needed for XOR? For OR?

XOR needs 4 NAND gates; OR needs 3 (two to invert the inputs, one NAND to combine them, since NAND(A′, B′) = A + B).

Q4. Simplify AB + A′C + BC.

By the consensus theorem, BC is redundant: AB + A′C.

Q5. Write F(A,B,C) = Σm(1, 3, 5, 6, 7) in canonical POS form and in minimal POS form.

Canonical POS: ΠM(0, 2, 4) = (A + B + C)(A + B′ + C)(A′ + B + C). Minimal POS: group the 0s (cells 0, 2, 4) on the K-map: F′ = A′C′ + B′C′, so F = (A + C)(B + C).

Q6. Simplify F(A,B,C,D) = Σm(0, 1, 3, 7, 8, 9, 11, 15).

Prime implicants: B′C′ (0,1,8,9), B′D (1,3,9,11), CD (3,7,11,15). B′C′ is essential (only it covers 0 and 8), CD is essential (only it covers 7 and 15). Together they cover everything, so F = B′C′ + CD; B′D is a prime implicant that is not needed.

Q7. Why are NAND and NOR called universal gates?

Because NOT, AND and OR (a functionally complete set) can each be built from NAND alone or from NOR alone, so any Boolean function can be implemented using just one of them. This also simplifies chip manufacturing.

Q8. What is the difference between a prime implicant and an essential prime implicant?

A prime implicant is a group that cannot be made larger. An essential prime implicant is a prime implicant that is the only one covering some minterm; it must appear in every minimal SOP.


Summary

  • Basic gates: NOT, AND, OR; derived gates: NAND, NOR, XOR (inputs differ / odd parity), XNOR (inputs equal).

  • NAND and NOR are universal. XOR needs 4 NANDs or 5 NORs.

  • Key laws: distributive in both forms, absorption, A + A′B = A + B, De Morgan, and consensus. Every law has a dual.

  • Canonical SOP = Σ of minterms where F = 1; canonical POS = Π of maxterms where F = 0. There are 22n functions of n variables.

  • K-maps use Gray order; group 1s in rectangles of size 2k, with wrap-around, as large and as few as possible. Don't-cares are used only when they help.

  • Every minimal SOP contains all essential prime implicants; cyclic maps can have none and several minimal answers.

  • AND-OR = NAND-NAND, OR-AND = NOR-NOR.

  • Next, in Combinational Circuits: Adders, Multiplexers & Decoders, we put these gates together into the building blocks of a processor.