Question 2 of 8: Combinational Logic — NAND Network and a NOR-only EOR

Question 2: Combinational Logic — NAND Network and a NOR-only EOR (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Part I supplies a network of four 2-input NAND gates wired so that the first gate output $C$ feeds both of the second-rank gates, whose outputs $D$ and $E$ drive the final gate. Part II supplies nothing but the requirement that a 2-input exclusive-OR be realised from 2-input NOR gates alone.

Find. For Part I the Boolean expression at $F$, its simplest form and the equivalent single gate, plus the full truth table at $C$, $D$, $E$ and $F$; for Part II the truth table, the algebraic expression, a NOR-realisable form of it and the resulting gate array.

[Figure not reproduced: Figure 2 — Combinational logic circuit. All four gates are 2-input NAND (flat back with an output bubble), read directly from the examination drawing. See the official exam paper.]

Approach. Label each gate output in turn and propagate the NAND function forward, then apply DeMorgan's theorem to the final expression and recognise the standard form. For Part II, start from the canonical sum of products for exclusive-OR and drive it into a form built only from OR-then-invert operations, which is exactly what a NOR gate performs.

Part I [a] — the general expression. Taking the gates in order and writing $X'$ for the complement of $X$:

1. First gate. The inputs are $A$ and $B$, so $$C = \overline{A B}.$$
2. Second-rank gates. Each combines one input with $C$: $$D = \overline{A\,C} = \overline{A\,\overline{AB}}, \qquad E = \overline{B\,C} = \overline{B\,\overline{AB}}.$$
3. Output gate. Combining the two, the general expression asked for in [a] is $$F = \overline{D\,E} = \overline{\;\overline{A\,\overline{AB}} \cdot \overline{B\,\overline{AB}}\;}.$$

Part I [b] — simplification. Apply DeMorgan's theorem to the output gate first, which converts the NAND of two complements into a plain OR:

1. Remove the outer complement. Since $\overline{D\,E} = \overline{D} + \overline{E}$ and both $D$ and $E$ are themselves complements, the double negations cancel: $$F = \overline{D} + \overline{E} = A\,\overline{AB} + B\,\overline{AB}.$$
2. Factor the common term. Both products contain $\overline{AB}$, so $$F = \overline{AB}\,(A+B).$$
3. Expand the complement and multiply out. Using DeMorgan once more, $\overline{AB} = \overline{A}+\overline{B}$, hence $$F = (\overline{A}+\overline{B})(A+B) = \underbrace{\overline{A}A}_{0} + \overline{A}B + A\overline{B} + \underbrace{\overline{B}B}_{0},$$ and the two complementary products vanish, leaving $$F = \boxed{\overline{A}B + A\overline{B} = A \oplus B}$$

The network is therefore an exclusive-OR, and the answer to the question asked in [b] is yes — a single 2-input EOR (XOR) gate can replace all four NAND gates. This four-NAND arrangement is the classical minimum-gate XOR built from a single universal gate type.

Part I [c] — truth table. Evaluating each node for the four input combinations confirms the algebra:

The $F$ column is 0, 1, 1, 0 — high only when the inputs differ, which is the exclusive-OR signature obtained algebraically.

Part II [d] — truth table for the EOR gate.

Part II [e] — the general expression. Reading the two rows for which the output is 1 gives the canonical sum of products $$Y = \overline{A}B + A\overline{B}.$$

Part II [f] — conversion to NOR form. A NOR gate ORs its inputs and inverts, so the target is an expression built entirely from $\overline{X+Y}$ operations. The key manoeuvre is to produce each of the two product terms as a NOR of an input with the NOR of both inputs:

1. Form the primitive term. The first gate produces $$G_1 = \overline{A+B} = \overline{A}\,\overline{B}.$$
2. Recover the two product terms. NOR-ing $G_1$ with one input at a time gives, by DeMorgan, $$G_2 = \overline{A + G_1} = \overline{A}\,\overline{G_1} = \overline{A}\,(A+B) = \overline{A}B,$$ and symmetrically $$G_3 = \overline{B + G_1} = \overline{B}\,(A+B) = A\overline{B}.$$ The absorption $\overline{A}(A+B) = \overline{A}B$ is what makes this work.
3. Combine and invert. NOR-ing the two product terms gives the complement of the wanted function, $$G_4 = \overline{G_2+G_3} = \overline{\overline{A}B + A\overline{B}} = \overline{A \oplus B},$$ so one further inversion is required. A NOR gate with both inputs tied together is an inverter, since $\overline{X+X} = \overline{X}$, giving $$Y = \overline{G_4 + G_4} = \boxed{A \oplus B = \overline{\;\overline{A+\overline{A+B}} \; + \; \overline{B+\overline{A+B}}\;}}$$

The realisation needs five 2-input NOR gates, which is the minimum for this function using NOR alone.