Question 1 of 6: Boolean synthesis, minimisation and hazard analysis (12 marks)

Question 1: Boolean synthesis, minimisation and hazard analysis (12 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 single three-variable switching function written as a three-term sum of products, $f = A\overline{C} + A\overline{B} + \overline{A}BC$, together with the standard identity list supplied with the paper (absorption, consensus, De Morgan).

Find. (a) a gate-level realisation of f exactly as written; (b) the minimal SoP and minimal PoS forms obtained algebraically; (c) independent confirmation of both by Karnaugh map; and (d) whether the minimised two-level circuits contain a static hazard, with a glitch-free SoP if one exists.

Approach. Synthesise the expression literally first, then build the truth table (equivalently the minterm list) once and use it for the algebraic minimisation, the K-map check and the hazard search, since all three parts are different views of the same 8-row function.

(a) Direct synthesis (2 marks)

Written as it stands, the function needs one inverter for each complemented literal, one AND gate per product term, and a single OR gate to collect the three terms. Nothing is minimised at this stage — the marks are for a correct literal translation.

(b) Algebraic minimisation (4 marks)

1. Expand the function to its minterm list. Each product term covers the cells in which it evaluates to 1: $$A\overline{C} \rightarrow m_4, m_6 \qquad A\overline{B} \rightarrow m_4, m_5 \qquad \overline{A}BC \rightarrow m_3$$ so the ON-set is $f = \sum m(3,4,5,6)$ and the OFF-set is $\overline{f} = \sum m(0,1,2,7)$.
2. Factor the two A-terms. Applying the distributive identity (item 14 of the supplied list) to the first two products, $$A\overline{C} + A\overline{B} = A(\overline{B} + \overline{C}) = A \cdot \overline{BC}$$ where the second step is De Morgan (item 20). The remaining term is $\overline{A}\,(BC)$, so the whole function collapses to an exclusive-OR: $$f = A \cdot \overline{BC} + \overline{A} \cdot (BC) = \boxed{\,A \oplus BC\,}$$ This compact form is worth noting because it explains the answer to part (d), but it is a two-level plus XOR form, not a two-level SoP.
3. Minimal sum of products. Combining adjacent minterms, $m_4$ pairs with $m_5$ to give $A\overline{B}$ and with $m_6$ to give $A\overline{C}$, while $m_3$ has no adjacent 1-cell and must stand alone: $$f_{\text{SoP}} = \boxed{\,A\overline{B} + A\overline{C} + \overline{A}BC\,}$$ Three product terms, seven literals. The two terms already present in the question were therefore already prime; only the third could not be reduced.
4. Minimal product of sums. Minimise the complement first, using the same pairing on the OFF-set $\{0,1,2,7\}$: $m_0$ pairs with $m_1$ giving $\overline{A}\,\overline{B}$ and with $m_2$ giving $\overline{A}\,\overline{C}$, and $m_7$ stands alone: $$\overline{f} = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + ABC$$ Complementing both sides and applying De Morgan term by term gives $$f_{\text{PoS}} = \boxed{\,(A + C)(A + B)(\overline{A} + \overline{B} + \overline{C})\,}$$ Three sum terms, seven literals — the same cost as the SoP form, which is typical for a function that is symmetric about its own complement.

(c) Karnaugh-map check (3 marks)

The maps below reproduce both results independently of the algebra. Grouping the 1-cells gives the SoP form; grouping the 0-cells of the same map and complementing each loop gives the PoS form. Note that the $A\overline{C}$ loop wraps around the BC axis (cells $m_4$ and $m_6$ are adjacent because $BC = 00$ and $BC = 10$ differ in one bit), which is why it is drawn as two rectangles.

Both maps confirm the algebra exactly: three loops each, seven literals each, and the isolated cell ($m_3$ in the ON-set, $m_7$ in the OFF-set) forced to a full three-literal term in each case.

(d) Hazard analysis (3 marks)

A static-1 hazard exists in a two-level SoP circuit when two adjacent 1-cells are covered by different product terms and no single term covers both: as the changing input propagates, the first term can release before the second asserts, and the output dips momentarily to 0. The cure is a redundant (consensus) product term that spans the offending pair. The dual statement holds for static-0 hazards in a PoS circuit.

1. Enumerate the adjacent 1-pairs. The ON-set is $\{m_3, m_4, m_5, m_6\}$. Testing every single-bit neighbour: $m_4 \leftrightarrow m_5$ and $m_4 \leftrightarrow m_6$ are the only adjacent pairs; the neighbours of $m_3 = 011$ are $m_1, m_2$ and $m_7$, and none of them is in the ON-set, so $m_3$ is an isolated 1-cell.
2. Test each pair against the cover. The pair $(m_4, m_5)$ lies wholly inside the single term $A\overline{B}$, and the pair $(m_4, m_6)$ lies wholly inside the single term $A\overline{C}$. Every adjacent 1-pair is therefore spanned by one product term, and no input transition can hand the output from one term to another: $$\boxed{\text{the minimal SoP contains no static-1 hazard}}$$
3. Repeat on the OFF-set for the PoS form. The 0-cells are $\{m_0, m_1, m_2, m_7\}$; the adjacent pairs are $(m_0, m_1)$, covered by $\overline{A}\,\overline{B}$, and $(m_0, m_2)$, covered by $\overline{A}\,\overline{C}$, with $m_7$ isolated. By the same argument the minimal PoS contains no static-0 hazard.
4. Conclusion. Because no hazard is present, no redundant term is required and the hazard-free SoP is the minimal SoP already found: $$f_{\text{hazard-free}} = \boxed{\,A\overline{B} + A\overline{C} + \overline{A}BC\,}$$ Adding a consensus term here would only increase area and delay without removing any glitch.

The XOR identity found in part (b) is a useful sanity check on this conclusion. In $f = A \oplus BC$ the variable A reaches the output through a single path, so no static hazard in A can arise; the isolation of $m_3$ is the map-level statement of the same fact. What the circuit does exhibit — as every XOR-like function does — is the possibility of a dynamic hazard if two inputs change at once, but the question restricts attention to single-input changes, which is the standard assumption for static-hazard analysis.