Question 1 of 5: Boolean Expression Evaluation and a Dual Crossbar-Switch Network

Question 1: Boolean Expression Evaluation and a Dual Crossbar-Switch Network (25 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. (a) $A=1,\ B=0,\ C=0$ in $X=(\overline{A\oplus B})\oplus C + A\cdot C$. (b) A 4-data-input ($A,B,C,D$), 2-output ($F,G$), 2-select ($S_1,S_0$) network whose functional table is reproduced above; $S_1,S_1',S_0,S_0'$ are all available as primary signals (no inverters need to be built).

Find. (a) the value of $X$, with justification. (b)(i) an AND/OR-gate schematic for $F$ and $G$; (b)(ii) the same network built from 2-input NAND gates only.

Approach. (a) Substitute the given bits directly into the expression, evaluating XOR/complement/AND/OR left to right. (b) Read $F$ and $G$ off the table as two 4:1-multiplexer selects that share the same decode logic, write the SOP equations, realize them with 2-input AND/OR gates, then systematically replace every AND with a NAND+inverter and every OR with a NAND-of-inverted-inputs (a valid conversion because double inversion cancels), which by construction uses only 2-input NAND gates.

1. Part (a) — evaluate $X$ term by term. $A\oplus B = 1\oplus 0 = 1$, so $\overline{A\oplus B} = 0$. Then $0\oplus C = 0\oplus 0 = 0$. The second term $A\cdot C = 1\cdot 0 = 0$. Summing, $$X = 0 + 0 = \boxed{0}$$ Justification: with $B=C=0$ the circuit reduces to $X=\overline{A}\cdot 1+\dots$ in effect testing $A$ against itself through a double inversion, and $A\cdot C$ is forced to 0 whenever $C=0$ — both paths independently confirm $X=0$ for this input combination.
2. Part (b) — read $F,G$ as two selects sharing one decode stage. Both outputs are picked from $\{A,B,C,D\}$ by the same 2-bit select $(S_1,S_0)$, just in a different order (F: A,B,C,D forward; G: D,C,B,A reversed). Define the four mutually-exclusive decode terms $m_{00}=S_1'S_0'$, $m_{01}=S_1'S_0$, $m_{10}=S_1S_0'$, $m_{11}=S_1S_0$ (built once, reused by both outputs) directly from the table: $$F = m_{00}A + m_{01}B + m_{10}C + m_{11}D$$ $$G = m_{00}D + m_{01}C + m_{10}B + m_{11}A$$ Brute-forced against all 64 $(S_1,S_0,A,B,C,D)$ input rows — both equations reproduce the table exactly.
3. Part (b)(i) — AND/OR-gate schematic. Building $m_{00}\dots m_{11}$ from four 2-input AND gates on $(S_1'\text{ or }S_1,\ S_0'\text{ or }S_0)$, then ANDing each decode term with its data line, then OR-ing the four products, realizes $F$ with only 2-input AND/OR gates throughout (11 gates: 4 decode-AND + 4 data-AND + 3 OR, arranged as an OR2 tree). Fig. Q1(i) below shows the complete network for $F$; $G$ is built from the identical 4 decode-AND gates (shared, not duplicated) with the data-AND stage re-wired to $D,C,B,A$ instead of $A,B,C,D$ — i.e. the same 11-gate tree topology mirrored on the data side, per the $G$ equation above.
   Fig. Q1(i) — shared-decode AND/OR realization of $F$ (2-input gates throughout). $G$ reuses the same four decode gates $m_{00}\dots m_{11}$ with data inputs re-ordered $D,C,B,A$.
4. Part (b)(ii) — 2-input-NAND-only schematic. Replace every 2-input AND with a NAND followed by an inverter (itself a NAND with both inputs tied together), and every 2-input OR with a NAND fed by two inverted inputs ($x+y = \overline{\bar x\cdot \bar y}$); both substitutions are exact (the double negation at each stage cancels), so the resulting all-NAND network computes the identical function using nothing but 2-input NAND gates. Fig. Q1(ii) shows the conversion applied to the whole $F$ tree; $G$ again mirrors it with the data inputs re-ordered.
   Fig. Q1(ii) — the Fig. Q1(i) network with every AND→NAND+inverter and every OR→NAND-of-inverted-inputs, 2-input NAND gates only.