Digital Electronics

What is Digital Electronics?

Digital electronics is the branch of electronics concerned with circuits that process binary signals: signals that take one of two distinct voltage levels representing logical 0 and logical 1. The course covers how to design, build, and test systems built from logic gates, combinational circuits, sequential circuits (with memory), and ultimately simple processors.

Unlike analogue circuits, where signals vary continuously, digital circuits are inherently robust: because only two voltage levels are distinguished, small amounts of electrical noise do not corrupt the signal. This noise immunity is one reason digital systems dominate modern computing.

The Six Levels of Abstraction

Modern digital systems, such as microprocessors, contain millions of transistors. Designing such a system by modelling the behaviour of individual electrons is not feasible. Instead we manage complexity through abstraction: hiding details that are not relevant at a given level of analysis.

For an electronic computing system, eight levels of abstraction are commonly identified, from the physical to the application:

In this course we are primarily concerned with the shaded middle levels: Digital Circuits, Logic Elements, and part of Microarchitecture. The abstraction principle means that when working at the gate level, we treat each gate as a black box with a known logical function; we do not need to understand the transistor-level physics inside, though knowing something about the levels above and below helps: a device designer should understand the circuits in which the device will be used, and code cannot be optimised without understanding the architecture for which it is written.

Managing Complexity

Abstraction works because each level provides a well-defined interface to the level above. At the gate level:

• A NOT gate always inverts its input. We do not care how many transistors implement it or what voltages represent a 1.
• An AND gate always produces TRUE only when all inputs are TRUE.

This layered thinking means we can browse the web (application software level) without any regard for quantum theory or the organisation of memory in the computer. However, awareness of adjacent levels is valuable: you cannot write efficient code without understanding the architecture; you cannot design good gates without understanding the circuits they will form.

The Digital Abstraction

The key design decision in digital electronics is to represent continuous physical quantities (voltages) with discrete logical values. A voltage above a certain threshold is interpreted as logic 1; below a different threshold, logic 0. The region between these thresholds is forbidden during normal operation and is only passed through transiently during switching. This discretisation is what gives digital circuits their noise immunity and makes reliable system design possible.

Course Aims

This course aims to familiarise students with:

• Combinational logic circuits: circuits whose output depends solely on the current inputs (no memory)
• Sequential logic circuits: circuits whose output depends on current inputs and past history (they contain memory)
• How digital logic gates are built using transistors (CMOS)
• Simple processor architectures
• The design, build, and testing of digital logic systems

Course Structure (12 Lectures)

1. Combinational logic foundations: logic gates, Boolean algebra, De Morgan’s theorem, consensus theorem
2. Logic minimisation: truth tables, normal forms, Karnaugh maps, don’t-care conditions, Quine-McCluskey
3. Binary adders: half and full adders, ripple carry, fast carry generation
4. Multilevel logic and hazards: beyond two-level logic, propagation delay, static and dynamic hazards, hazard removal
5. Beyond simple logic gates: multiplexers, decoders, ROMs, PLAs, PALs, tristate buffers
6. Sequential logic: latches, flip-flops, counters, shift registers
7. FSM design: synchronous finite state machines, state diagrams, excitation tables
8. Logic implementation technologies: CMOS transistors, gate-level implementation
9. Processor architecture: brief introduction to microprocessor design

Hardware labs (four workshops of 2.5-3 hours each) run throughout Michaelmas and Lent terms.

Relationship to Later Courses

This course is a prerequisite for:

• Computer Architecture (Part IB): understanding how logic elements combine to form data paths and control units
• ECAD and Architecture Practical Classes (Part IB): practical design and implementation
• Advanced Computer Architecture (Part II)
• Advanced Topics in Computer Architecture (MPhil/Part III)

The Boolean algebra and logic minimisation techniques taught here are a core competence in Computer Science: they appear in everything from compiler optimisations to database query planning, not just in hardware design.

Logic Variables

Logic variables (also called binary variables or Boolean variables) can only take on two values. Different naming conventions are used interchangeably:

In electronic circuits these two values are represented by distinct voltage levels, e.g., a high voltage for logic 1 and a low voltage for logic 0. Using only two voltage levels gives digital circuits greater immunity to electrical noise compared with analogue circuits.

Logic Gates

A logic gate is a basic electronic circuit with one or more inputs and exactly one output. Gates are the atomic building blocks of all digital logic circuits. There are several ways to represent a logic function: a symbol (circuit diagram), a truth table (exhaustive input-output mapping), and a Boolean expression (algebraic form).

The NOT Gate (Inverter)

The NOT gate has one input and one output. Its output is the complement (inverse) of its input.

Truth table:

Boolean expression: $y = \bar{a}$

The circle (or “bubble”) on the output of the gate symbol indicates that the output is the complemented (inverted) version of the input. A NOT gate is also called an inverter.

The AND Gate

The AND gate output is TRUE only when all inputs are TRUE.

Truth table (2-input):

Boolean expression: $y = a \cdot b$ (also written as $y = ab$, or $y = a \land b$)

The dot represents the AND operation. For multiple inputs, the AND operation extends naturally: $y = a \cdot b \cdot c \cdot \ldots$; the output is 1 only when every input is 1. A 3-input AND gate has 8 rows in its truth table, with only the row (1,1,1) yielding output 1.

The OR Gate

The OR gate output is TRUE when at least one input is TRUE (the inclusive OR).

Truth table (2-input):

Boolean expression: $y = a + b$ (also written $y = a \lor b$)

The plus sign represents the OR operation (not arithmetic addition). For multiple inputs: $y = a + b + c + \ldots$; the output is 1 if any input is 1.

The XOR Gate (Exclusive OR)

The XOR gate output is TRUE when an odd number of inputs are TRUE. For two inputs, it is TRUE when exactly one input is TRUE (but not both).

Truth table (2-input):

Boolean expression: $y = a \oplus b = a \cdot \bar{b} + \bar{a} \cdot b$

The XOR can be thought of as “a OR b but NOT both”, i.e., detecting inequality: $y = 1$ iff $a \neq b$.

The NAND Gate (NOT AND)

The NAND gate is an AND gate followed by a NOT. Its output is FALSE only when all inputs are TRUE.

Truth table (2-input):

Boolean expression: $y = \overline{a \cdot b}$

Equivalently, $y = \bar{a} + \bar{b}$ (by De Morgan’s theorem, see De Morgan’s Theorem). So y is TRUE if a is FALSE or b is FALSE (or both).

The NOR Gate (NOT OR)

The NOR gate is an OR gate followed by a NOT. Its output is TRUE only when all inputs are FALSE.

Truth table (2-input):

Boolean expression: $y = \overline{a + b}$

Equivalently, $y = \bar{a} \cdot \bar{b}$ (by De Morgan’s theorem). So y is TRUE only if a is FALSE AND b is FALSE.

Universal Gates: NAND and NOR

Any Boolean function can be built using only NAND gates, or using only NOR gates. NAND and NOR are therefore called universal gates. This is important in practice because NAND and NOR gates are simpler to fabricate in many transistor technologies (particularly CMOS). The proof is straightforward: we can construct NOT, AND, and OR from NAND alone, and since {NOT, AND, OR} is functionally complete, NAND must be too.

Building NOT from NAND: tie both inputs together: $\overline{a \cdot a} = \bar{a}$.

Building AND from NAND: a NAND followed by a NOT (which is itself a NAND): $\overline{\overline{a \cdot b}} = a \cdot b$.

Building OR from NAND: apply De Morgan: $a + b = \overline{\bar{a} \cdot \bar{b}}$, which is a NAND of two complemented inputs (each complement is itself a NAND).

Similar constructions work for NOR.

Worked Example: Boiler Controller

Consider a heating boiler with the following inputs:

• $b$: chimney is blocked (1 = blocked)
• $c$: house is cold (1 = cold)
• $p$: pilot light is lit (1 = lit)
• $h$: overheat sensor triggered (1 = overheated)

Output $v$: open the main fuel valve to start the boiler (1 = open).

The valve should open if and only if: the chimney is NOT blocked AND the house is cold AND the pilot light is lit, BUT NOT if the overheat sensor is triggered.

Boolean expression:

$v = \bar{b} \cdot c \cdot p \cdot \bar{h}$

The circuit uses one NOT gate (for $\bar{b}$), one NOT gate (for $\bar{h}$), and one 4-input AND gate. If only 2-input AND gates are available, the three AND terms are cascaded: $((\bar{b} \cdot c) \cdot p) \cdot \bar{h}$.

Combining Gates: Building $z = (\overline{a}) \cdot (a + b)$

We will show how a more complex Boolean expression is implemented by connecting simpler gates. The expression $z = \bar{a} \cdot (a + b)$ involves NOT, AND, and OR operations. The circuit diagram consists of: input $a$ splits into two paths; one path goes through a NOT gate producing $\bar{a}$; the other path goes together with $b$ into an OR gate producing $(a + b)$; the outputs of the NOT and OR gates are fed into an AND gate producing the final output $z$.

Truth Table Construction

To build the truth table for this expression, evaluate it for every combination of the inputs $a$ and $b$:

1. List all input combinations: for $n$ inputs there are $2^n$ rows. Here $n = 2$, so 4 rows.
2. For each row, compute intermediate sub-expressions.
3. Combine sub-expressions to get the final output.

So $z$ is 1 only when $a = 0$ and $b = 1$. This is exactly $z = \bar{a} \cdot b$, which can be verified algebraically:

$z = \bar{a} \cdot (a + b) = \bar{a} \cdot a + \bar{a} \cdot b = 0 + \bar{a} \cdot b = \bar{a} \cdot b$

This simplification shows that the OR gate (and the second path from $a$) was redundant. The truth table reveals this directly: the only row where $z = 1$ corresponds to $\bar{a} \cdot b$. This is a preview of Boolean algebra simplification, treated fully in the next note.

Gate-Level Equivalences via De Morgan

De Morgan’s theorem gives us important equivalences between gate types:

• An AND gate with bubbles on both inputs is equivalent to a NOR gate: $\overline{\bar{a} \cdot \bar{b}} = a + b$.
• An OR gate with bubbles on both inputs is equivalent to a NAND gate: $\overline{\bar{a} + \bar{b}} = a \cdot b$.
• An AND gate with a bubble on its output is a NAND gate.
• An OR gate with a bubble on its output is a NOR gate.

Two consecutive bubbles (complement operations) cancel: a bubble on an input followed by a bubble on the output of the same gate has no net logical effect. This “bubble pushing” technique is a practical method for converting between gate types and is explored in depth in the De Morgan’s Theorem note.

Overview

Boolean algebra is the mathematical framework for reasoning about logic functions. It operates on binary variables with the operations AND (·), OR (+), and NOT (overbar). The precedence rule is: NOT binds tightest, then AND, then OR. So $a \cdot b + c$ means $(a \cdot b) + c$, not $a \cdot (b + c)$.

A combinational logic circuit has no internal stored state (no memory); its output depends solely on its current inputs. Boolean algebra describes the behaviour of such circuits and allows us to simplify them.

Basic Identities

Identities Involving Constants

Complementation

Idempotence

Involution (Double Complement)

$\overline{\overline{a}} = a$

Complementing twice returns the original value. This is also why two bubbles in series cancel.

Commutative, Associative, and Distributive Laws

Commutative

$a + b = b + a$ $a \cdot b = b \cdot a$

The order of operands does not matter for AND or OR.

Associative

$(a + b) + c = a + (b + c)$ $(a \cdot b) \cdot c = a \cdot (b \cdot c)$

Grouping does not matter, so we write $a + b + c$ or $a \cdot b \cdot c$ without parentheses.

Distributive

Boolean algebra has two distributive laws, and the second one has no analogue in ordinary algebra:

$a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ $a + (b \cdot c) = (a + b) \cdot (a + c) \qquad \text{(NEW: not true in ordinary algebra)}$

The second law can be verified by truth table or algebraic expansion:

$(a + b) \cdot (a + c) = a \cdot a + a \cdot c + b \cdot a + b \cdot c = a + a \cdot c + a \cdot b + b \cdot c = a + b \cdot c$

where the last step uses absorption (below).

Absorption Laws

$a + (a \cdot c) = a$ $a \cdot (a + c) = a$

Proof of the first: $a + a \cdot c = a \cdot 1 + a \cdot c = a \cdot (1 + c) = a \cdot 1 = a$.

Proof of the second: $a \cdot (a + c) = a \cdot a + a \cdot c = a + a \cdot c = a$ (using idempotence and the first absorption law).

Intuition: in $a + a \cdot c$, if $a = 1$ the output is 1 regardless of $c$; if $a = 0$ then $a \cdot c = 0$ and $0 + 0 = 0$. So the output is always exactly $a$.

De Morgan’s Theorem (Preview)

De Morgan’s theorem tells us how to push complements through AND and OR:

$\overline{a + b} = \bar{a} \cdot \bar{b}$ $\overline{a \cdot b} = \bar{a} + \bar{b}$

This is treated in full in the De Morgan’s Theorem note. For now, note its algebraic role: it allows us to transform AND expressions into OR expressions and vice versa.

Worked Simplification Examples

Example 1: $a \cdot b \cdot c + a \cdot b \cdot \bar{c}$

The two terms differ only in the complementation of $c$; they combine to eliminate $c$ entirely. This technique, factoring out common literals and applying $x + \bar{x} = 1$, is the core algebraic simplification method.

Example 2: Show $a \cdot (\bar{a} + b) = a \cdot b$

The term $a \cdot \bar{a}$ vanishes because a variable AND its complement is always 0.

Example 3: Show $a + (\bar{a} \cdot b) = a + b$

This uses the “new” distributive law $a + (b \cdot c) = (a + b) \cdot (a + c)$, which has no parallel in ordinary arithmetic.

Example 4: Simplify $x \cdot y + y \cdot z + x \cdot z + x \cdot y \cdot z$

We use the technique of expanding each term to include all variables (by multiplying terms by $(v + \bar{v}) = 1$ for missing variables), then cancelling:

First, expand every term to include $x$, $y$, and $z$:

• $x \cdot y = x \cdot y \cdot (z + \bar{z}) = x \cdot y \cdot z + x \cdot y \cdot \bar{z}$
• $y \cdot z = (x + \bar{x}) \cdot y \cdot z = x \cdot y \cdot z + \bar{x} \cdot y \cdot z$
• $x \cdot z = x \cdot (y + \bar{y}) \cdot z = x \cdot y \cdot z + x \cdot \bar{y} \cdot z$
• $x \cdot y \cdot z$ is already fully expanded

Now list all minterms:

$x \cdot y \cdot z$ (from $xy$), $x \cdot y \cdot \bar{z}$ (from $xy$), $x \cdot y \cdot z$ (from $yz$), $\bar{x} \cdot y \cdot z$ (from $yz$), $x \cdot y \cdot z$ (from $xz$), $x \cdot \bar{y} \cdot z$ (from $xz$), $x \cdot y \cdot z$ (from $xyz$).

Removing duplicates, the distinct minterms are: $x \cdot y \cdot z$, $x \cdot y \cdot \bar{z}$, $\bar{x} \cdot y \cdot z$, $x \cdot \bar{y} \cdot z$.

Group:

$x \cdot y \cdot z + x \cdot y \cdot \bar{z} + \bar{x} \cdot y \cdot z + x \cdot \bar{y} \cdot z$ $= x \cdot y \cdot (z + \bar{z}) + y \cdot z \cdot (x + \bar{x})$ $= x \cdot y + y \cdot z$

So the original expression simplifies to $x \cdot y + y \cdot z$.

Consensus Theorem

The consensus theorem states:

$a \cdot b + \bar{a} \cdot c + b \cdot c = a \cdot b + \bar{a} \cdot c$

The term $b \cdot c$ is the consensus of $a \cdot b$ and $\bar{a} \cdot c$: it is formed by taking the AND of all literals that appear in both terms, excluding the variable and its complement ($a$ and $\bar{a}$). The consensus term is redundant and can be added or removed without changing the function.

Proof

Dual Form

The dual of the consensus theorem (swap AND with OR, 0 with 1) gives:

$(a + b) \cdot (\bar{a} + c) \cdot (b + c) = (a + b) \cdot (\bar{a} + c)$

The dual can be proven by applying De Morgan’s theorem to both sides of the original, or by a similar algebraic expansion.

Using Consensus: Adding and Eliminating Terms

The theorem works in both directions:

• Elimination: If you see $a \cdot b + \bar{a} \cdot c + b \cdot c$, remove $b \cdot c$ to get $a \cdot b + \bar{a} \cdot c$.
• Addition: If you have $a \cdot b + \bar{a} \cdot c$ and need to combine it with other terms, you can add $b \cdot c$ without changing the function (useful for hazard removal, see Hazard Removal).

Example: Simplify $a \cdot b + \bar{a} \cdot c + b \cdot c + \bar{b} \cdot c + a \cdot \bar{b}$.

First, identify consensus terms. The term $b \cdot c$ is the consensus of $a \cdot b$ and $\bar{a} \cdot c$, so it can be removed. After removal: $a \cdot b + \bar{a} \cdot c + \bar{b} \cdot c + a \cdot \bar{b}$.

Now examine what remains. The term $\bar{b} \cdot c$ and $a \cdot \bar{b}$ look for consensus with others. But note that $\bar{a} \cdot c + \bar{b} \cdot c = \bar{a} \cdot c$ does not directly give consensus removal. In this case further algebraic inspection (or a K-map) reveals the minimal form.

Example with clear elimination: Simplify $a \cdot b + \bar{a} \cdot c + b \cdot c + \bar{b} \cdot c$.

The term $b \cdot c$ is consensus of $a \cdot b$ and $\bar{a} \cdot c$ (remove it). Check if $\bar{b} \cdot c$ is consensus of any pair: no obvious pair. Result: $a \cdot b + \bar{a} \cdot c + \bar{b} \cdot c$. Further, note $\bar{a} \cdot c + \bar{b} \cdot c = (\bar{a} + \bar{b}) \cdot c$, which cannot be simplified further without additional context. The final expression depends on the specific terms.

Summary of Boolean Laws

Statement of the Theorem

De Morgan’s theorem describes how to distribute a complement (NOT) over an AND or OR operation:

$\overline{a \cdot b} = \bar{a} + \bar{b}$

$\overline{a + b} = \bar{a} \cdot \bar{b}$

In words:

• The complement of a product equals the sum of the complements: $\overline{a \cdot b} = \bar{a} + \bar{b}$.
• The complement of a sum equals the product of the complements: $\overline{a + b} = \bar{a} \cdot \bar{b}$.

For the general form with $n$ variables:

$\overline{a \cdot b \cdot c \cdot \ldots} = \bar{a} + \bar{b} + \bar{c} + \ldots$

$\overline{a + b + c + \ldots} = \bar{a} \cdot \bar{b} \cdot \bar{c} \cdot \ldots$

Truth Table Verification

For two variables, both forms can be verified exhaustively:

The columns for $\overline{a \cdot b}$ and $\bar{a} + \bar{b}$ are identical, confirming the first form. The columns for $\overline{a + b}$ and $\bar{a} \cdot \bar{b}$ are identical, confirming the second form.

Inductive Extension to More Variables

The theorem extends to any number of variables by induction. For three variables:

$\overline{a + b + c} = \overline{(a + b) + c} = \overline{a + b} \cdot \bar{c} = (\bar{a} \cdot \bar{b}) \cdot \bar{c} = \bar{a} \cdot \bar{b} \cdot \bar{c}$

The key step applies the two-variable form treating $(a + b)$ as a single variable combined with $c$.

Similarly for the AND form:

$\overline{a \cdot b \cdot c} = \overline{(a \cdot b) \cdot c} = \overline{a \cdot b} + \bar{c} = (\bar{a} + \bar{b}) + \bar{c} = \bar{a} + \bar{b} + \bar{c}$

Practical Rule for Application

To apply De Morgan’s theorem to a Boolean expression:

1. Change all ANDs to ORs (and vice versa).
2. Complement each individual variable (put a bar over every literal).
3. Complement the entire expression (put a bar over the whole thing).

Example: Apply De Morgan to $a + b \cdot c$.

Step 1: change OR to AND, AND to OR: $a \cdot (b + c)$ Step 2: complement each variable: $\bar{a} \cdot (\bar{b} + \bar{c})$ Step 3: complement the whole: $\overline{\bar{a} \cdot (\bar{b} + \bar{c})}$

So $\overline{a + b \cdot c} = \overline{\bar{a} \cdot (\bar{b} + \bar{c})}$. We can then simplify the right-hand side further by applying De Morgan again:

$\overline{\bar{a} \cdot (\bar{b} + \bar{c})} = \overline{\bar{a}} + \overline{\bar{b} + \bar{c}} = a + (b \cdot c)$

Which returns us to the original, confirming correctness.

More usefully, De Morgan can simplify: $\overline{a + b \cdot c} = \bar{a} \cdot \overline{b \cdot c} = \bar{a} \cdot (\bar{b} + \bar{c})$.

Worked Algebraic Example

Simplify $\overline{a \cdot b + a \cdot (b + c) + b \cdot (b + c)}$.

Step 1: Apply De Morgan to the whole expression (impossible directly because it’s a sum of three terms). Instead, simplify inside first.

Inside: $a \cdot b + a \cdot (b + c) + b \cdot (b + c)$

Simplify each term algebraically before applying De Morgan:

$a \cdot b + a \cdot \overline{b + c} + b \cdot \overline{b + c}$

Apply De Morgan: $\overline{b + c} = \bar{b} \cdot \bar{c}$.

$= a \cdot b + a \cdot \bar{b} \cdot \bar{c} + b \cdot \bar{b} \cdot \bar{c}$

Note $b \cdot \bar{b} = 0$, so the third term vanishes:

$= a \cdot b + a \cdot \bar{b} \cdot \bar{c}$

Factor $a$: $= a \cdot (b + \bar{b} \cdot \bar{c})$

Using the distributive law $x + \bar{x} \cdot y = x + y$ (proved in the Boolean Algebra note):

$= a \cdot (b + \bar{c})$

Bubble Logic: Gate Equivalences

De Morgan’s theorem has an elegant interpretation in terms of gate symbols. The “bubble” on a gate input or output represents complementation.

Rule 1: Two Bubbles Cancel

Two bubbles in series (an input bubble feeding into an output bubble along the same wire) cancel and have no logical effect:

$\overline{\overline{x}} = x$

Rule 2: AND with Inverted Inputs = NOR

An AND gate with bubbles on all inputs:

$\overline{\bar{a} \cdot \bar{b}} = \bar{\bar{a}} + \bar{\bar{b}} = a + b$

So an AND gate with inverted inputs is functionally a NOR gate (and equivalently, a NOR gate with inverted inputs is an AND gate).

Rule 3: OR with Inverted Inputs = NAND

An OR gate with bubbles on all inputs:

$\overline{\bar{a} + \bar{b}} = \bar{\bar{a}} \cdot \bar{\bar{b}} = a \cdot b$

So an OR gate with inverted inputs is functionally a NAND gate.

Rule 4: Bubble Through a Gate

Moving a bubble from output to inputs changes the gate type:

• NAND: AND gate followed by bubble → bubble input OR gate: $\overline{a \cdot b} = \bar{a} + \bar{b}$
• NOR: OR gate followed by bubble → bubble input AND gate: $\overline{a + b} = \bar{a} \cdot \bar{b}$

Example 1: Implementing $f = a \cdot b + c \cdot d$ Using Only NAND Gates

The expression $f = a \cdot b + c \cdot d$ is in SOP form: two AND terms OR-ed together.

Direct implementation uses two AND gates and one OR gate.

NAND-only implementation: Apply De Morgan by double-complementing:

$f = a \cdot b + c \cdot d$ $f = \overline{\overline{a \cdot b + c \cdot d}}$ $f = \overline{\overline{a \cdot b} \cdot \overline{c \cdot d}}$

The outer complement tells us to use a NAND gate. Its inputs are $\overline{a \cdot b}$ and $\overline{c \cdot d}$, each of which is the output of a NAND gate. So the circuit is: three NAND gates. Two NAND gates feed into a third NAND gate.

Gate 1: NAND of $a$ and $b$ produces $\overline{a \cdot b}$. Gate 2: NAND of $c$ and $d$ produces $\overline{c \cdot d}$. Gate 3: NAND of the two intermediate signals produces $\overline{\overline{a \cdot b} \cdot \overline{c \cdot d}} = a \cdot b + c \cdot d$.

Example 2: Implementing $f = (a + b) \cdot (c + d)$ Using Only NOR Gates

The expression $f = (a + b) \cdot (c + d)$ is in POS form: two OR terms AND-ed together.

NOR-only implementation: Double-complement and apply De Morgan:

$f = (a + b) \cdot (c + d)$ $f = \overline{\overline{(a + b) \cdot (c + d)}}$ $f = \overline{\overline{a + b} + \overline{c + d}}$

Now the outer complement is a NOR gate. Its inputs are $\overline{a + b}$ and $\overline{c + d}$, each produced by a NOR gate. So three NOR gates in total.

Gate 1: NOR of $a$ and $b$ produces $\overline{a + b}$. Gate 2: NOR of $c$ and $d$ produces $\overline{c + d}$. Gate 3: NOR of the two intermediate signals produces $\overline{\overline{a + b} + \overline{c + d}} = (a + b) \cdot (c + d)$.

Summary of Gate Transformations

These transformations are the foundation of bubble pushing: a technique for converting a circuit from one gate type to another while preserving the logic function. They are essential when a designer must implement a circuit using only one type of gate (e.g., NAND-only or NOR-only designs, which are common in CMOS).

Statement

The consensus theorem in its most common form states:

$a \cdot b + \bar{a} \cdot c + b \cdot c = a \cdot b + \bar{a} \cdot c$

The term $b \cdot c$ is called the consensus term. It is formed by taking the AND of the terms that remain after removing the variable and its complement from the two product terms $a \cdot b$ and $\bar{a} \cdot c$: strip $a$ from $a \cdot b$ to get $b$, strip $\bar{a}$ from $\bar{a} \cdot c$ to get $c$, and AND them to get $b \cdot c$.

The dual form (swap AND with OR):

$(a + b) \cdot (\bar{a} + c) \cdot (b + c) = (a + b) \cdot (\bar{a} + c)$

Proof via Boolean Algebra

Starting from the left-hand side:

The critical trick is multiplying $b \cdot c$ by $(a + \bar{a}) = 1$. This expands the consensus term into two terms, each of which is absorbed by one of the original product terms.

Proof via Truth Table

Build the truth table for all three input variables and compute both sides:

The columns for LHS and RHS are identical, confirming the theorem. Notice that $b \cdot c$ is 1 only in rows where either $a \cdot b$ or $\bar{a} \cdot c$ is already 1, so it never adds a new 1 to the function.

Proof via Karnaugh Map Preview

Plot the function $f = a \cdot b + \bar{a} \cdot c + b \cdot c$ on a K-map (3 variables: a, b, c). The K-map for a 3-variable function uses Gray code ordering:

The term $a \cdot b$ (1 when a=1, b=1, any c) covers cells (a=1, b=1, c=0) and (a=1, b=1, c=1), i.e., bc=10 and bc=11 in the second row. Both are 1.

The term $\bar{a} \cdot c$ (1 when a=0, c=1, any b) covers cells (a=0, b=0, c=1) and (a=0, b=1, c=1), i.e., bc=01 and bc=11 in the first row. Both are 1.

The term $b \cdot c$ (1 when b=1, c=1, any a) covers (a=0, b=1, c=1) and (a=1, b=1, c=1). But both of these cells are already covered by $\bar{a} \cdot c$ and $a \cdot b$ respectively. So $b \cdot c$ is redundant: it covers no minterms that are not already covered. This visual verification matches the algebraic proof: the consensus term is always redundant on a K-map because its cells are a subset of the union of the two generating terms’ cells.

How to Identify a Consensus Term

Given two product terms, a consensus term exists if they contain exactly one variable that appears complemented in one term and uncomplemented in the other. For $a \cdot b$ and $\bar{a} \cdot c$: the variable $a$ appears uncomplemented in the first and complemented in the second. The consensus is formed by AND-ing the remaining literals: $b \cdot c$.

Example: $x \cdot \bar{y} \cdot z$ and $\bar{x} \cdot w \cdot z$

• Conflicting variable: $x$ (uncomplemented vs complemented)
• Remaining literals: $\bar{y} \cdot z$ and $w \cdot z$
• Consensus term: $\bar{y} \cdot z \cdot w$ (AND of all remaining literals from both terms)

Using Consensus to Simplify

Elimination of Consensus Terms

If you find a consensus term in an expression, you can delete it without changing the function:

$a \cdot b + \bar{a} \cdot c + b \cdot c = a \cdot b + \bar{a} \cdot c$

Example: Simplify $a \cdot b + \bar{a} \cdot c + b \cdot c + \bar{b} \cdot c + a \cdot \bar{b}$.

In this expression, $b \cdot c$ is the consensus of $a \cdot b$ and $\bar{a} \cdot c$, so eliminate it.

Now examine the remaining expression: $a \cdot b + \bar{a} \cdot c + \bar{b} \cdot c + a \cdot \bar{b}$.

Looking for other consensus terms: $a \cdot \bar{b}$ and $\bar{a} \cdot c$ do not share a conflicting variable (the variables $a$ and $b$ in the first, $\bar{a}$ and $c$ in the second; $a$ conflicts, leaving $\bar{b}$ and $c$; consensus would be $\bar{b} \cdot c$, which is already present!). So $\bar{b} \cdot c$ is the consensus of $a \cdot \bar{b}$ and $\bar{a} \cdot c$, and can be removed.

Final expression: $a \cdot b + \bar{a} \cdot c + a \cdot \bar{b}$.

Adding Consensus Terms for Simplification

Sometimes it is useful to add a consensus term to enable further simplification. This is non-obvious because adding a term makes the expression larger; but it may allow factoring or combination that yields a net reduction.

Example: Simplify $a \cdot b + a \cdot c + \bar{a} \cdot b \cdot c$.

Direct simplification does not give much leverage. Add the consensus of $a \cdot b$ and $a \cdot c$: these share $a$ in common (no conflict), so no consensus between them. The consensus of $a \cdot b$ and $\bar{a} \cdot b \cdot c$: conflicting variable $a$, remaining literals $b$ from the first and $b \cdot c$ from the second; consensus is $b \cdot b \cdot c = b \cdot c$. Add $b \cdot c$:

$a \cdot b + a \cdot c + \bar{a} \cdot b \cdot c + b \cdot c$ $= a \cdot b + a \cdot c + b \cdot c \cdot (\bar{a} + 1)$ $= a \cdot b + a \cdot c + b \cdot c$ $= a \cdot (b + c) + b \cdot c$

(Better example with a real simplification):

Example: Simplify $a \cdot \bar{b} + \bar{a} \cdot b + a \cdot \bar{c}$.

Check consensus: $a \cdot \bar{b}$ and $\bar{a} \cdot b$ have $a$ conflicting, remaining literals $\bar{b}$ and $b$, consensus $\bar{b} \cdot b = 0$ (trivial). $a \cdot \bar{b}$ and $a \cdot \bar{c}$ have no conflicting variable (both start with $a$). $\bar{a} \cdot b$ and $a \cdot \bar{c}$ have $a$ conflicting, remaining $b$ and $\bar{c}$, consensus $b \cdot \bar{c}$. Add $b \cdot \bar{c}$:

$a \cdot \bar{b} + \bar{a} \cdot b + a \cdot \bar{c} + b \cdot \bar{c}$

Now $a \cdot \bar{c} + b \cdot \bar{c} = (a + b) \cdot \bar{c}$. So:

$= a \cdot \bar{b} + \bar{a} \cdot b + (a + b) \cdot \bar{c}$

This may or may not be simpler than the original, depending on the implementation cost metric. The point is that adding a consensus term is a legitimate step that opens up new factoring possibilities.

Proof of the Dual Form

The dual of the consensus theorem is:

$(a + b) \cdot (\bar{a} + c) \cdot (b + c) = (a + b) \cdot (\bar{a} + c)$

Proof: Start from the left-hand side and apply the distributive law for OR over AND to expand, or apply De Morgan to reduce to the original form:

Let $f = (a + b) \cdot (\bar{a} + c) \cdot (b + c)$. Take the complement:

$\bar{f} = \overline{(a + b) \cdot (\bar{a} + c) \cdot (b + c)}$ $\bar{f} = \overline{a + b} + \overline{\bar{a} + c} + \overline{b + c}$ $\bar{f} = \bar{a} \cdot \bar{b} + a \cdot \bar{c} + \bar{b} \cdot \bar{c}$

Now apply the original consensus theorem to $\bar{f}$ (the variables are now $\bar{a}$, $a$, $\bar{b}$, $\bar{c}$; the conflicting variable is $\bar{a}/a$, remaining terms $\bar{b}$ and $\bar{c}$, consensus $\bar{b} \cdot \bar{c}$):

$\bar{f} = \bar{a} \cdot \bar{b} + a \cdot \bar{c}$

Take the complement again:

$f = \overline{\bar{a} \cdot \bar{b} + a \cdot \bar{c}}$ $f = \overline{\bar{a} \cdot \bar{b}} \cdot \overline{a \cdot \bar{c}}$ $f = (a + b) \cdot (\bar{a} + c)$

Which proves the dual form. This approach (complement, apply the original theorem, complement again) is a general technique for proving the dual of any Boolean identity.

Extended Consensus: Three or More Consensus Terms

Consider an expression with three product terms that each conflict with the others in a cycle:

$a \cdot b + b \cdot c + a \cdot c$

Here the consensus of $a \cdot b$ and $b \cdot c$ (conflicting on $b$) leaves $a \cdot c$, which is already the third term. The consensus of $a \cdot b$ and $a \cdot c$ (conflicting on $a$) leaves $b \cdot c$, also present. So with all three terms present, any one can be eliminated as the consensus of the other two: $a \cdot b + a \cdot c = a \cdot b + a \cdot c + b \cdot c$, but equally $b \cdot c + a \cdot c = b \cdot c + a \cdot c + a \cdot b$. The three-term expression reduces to any two of the three.

In general, when multiple consensus terms exist, eliminating them iteratively reduces the expression to a form that cannot be further simplified by consensus alone. The order of elimination can affect the intermediate expression but the final minimised form is unique for a given function (up to K-map grouping choices).

Connection to Hazard Removal

The consensus theorem is not just a simplification tool. In the context of hazards (see Static and Dynamic Hazards), the consensus term corresponds to a redundant prime implicant that, when added to a circuit, eliminates static hazards. For the function $f = a \cdot \bar{b} + \bar{a} \cdot c$, when $b = c = 1$, a change in $a$ causes a momentary glitch. Adding the consensus term $b \cdot c$ gives $f = a \cdot \bar{b} + \bar{a} \cdot c + b \cdot c$, which is logically identical but hazard-free. The consensus theorem guarantees that adding $b \cdot c$ does not change the Boolean function; it only adds a physical gate that holds the output steady during the transition.

Truth Tables

A truth table exhaustively lists every possible combination of input values and the corresponding output of a Boolean function. For a function of $n$ variables, the truth table has $2^n$ rows. The rows are conventionally listed in binary counting order (0 to $2^n - 1$), though other orderings (e.g., Gray code) are sometimes used for specific purposes.

Example: The function $f(x, y, z) = x + y \cdot z$ has the following truth table:

Minterms

A minterm of $n$ Boolean variables is a product (AND) term that includes every variable exactly once, in either complemented or uncomplemented form. For $n$ variables there are $2^n$ possible minterms.

Notation: $m_i$ denotes the minterm corresponding to row $i$ of the truth table. For a function of 3 variables ($x$, $y$, $z$), with $x$ as the most significant bit:

A minterm $m_i$ is TRUE (equals 1) for exactly one input combination: the combination corresponding to row $i$. Note that $y \cdot z$ is NOT a minterm for a 3-variable function because it omits $x$; it is simply a product term.

Disjunctive Normal Form (DNF)

The Disjunctive Normal Form (DNF), also called Sum of Products (SOP) form, expresses a Boolean function as the OR (sum, disjunction) of its minterms. Specifically:

$f = \sum m_i \quad \text{for all } i \text{ where } f = 1$

Using $\Sigma$ notation for brevity: $f = \Sigma(3, 4, 5, 6, 7)$ means the OR of minterms $m_3$, $m_4$, $m_5$, $m_6$, $m_7$.

For the example function $f = x + y \cdot z$ above, the rows where $f = 1$ are 3, 4, 5, 6, 7. The DNF is:

$f = \bar{x} \cdot y \cdot z + x \cdot \bar{y} \cdot \bar{z} + x \cdot \bar{y} \cdot z + x \cdot y \cdot \bar{z} + x \cdot y \cdot z$

DNF has the property that it is canonical: every Boolean function has exactly one DNF representation (up to reordering of minterms). This uniqueness makes DNF useful for comparing functions.

Note on terminology: The term “Sum of Products” (SOP) is often used more broadly to describe any expression that is an OR of AND terms, even if those AND terms are not minterms. For example, $f = x + y \cdot z$ is in SOP form but is NOT in DNF because the terms $x$ and $y \cdot z$ are not minterms (they omit some variables). When we want to be precise, DNF refers specifically to the OR-of-minterms form.

Maxterms

A maxterm of $n$ Boolean variables is a sum (OR) term that includes every variable exactly once, in either complemented or uncomplemented form.

Notation: $M_i$ denotes the maxterm corresponding to row $i$. The rule for constructing maxterms from the truth table: for row $i$, if the variable is 0, use the uncomplemented form; if the variable is 1, use the complemented form. (This is the opposite of the minterm rule.)

For 3 variables: