Question 1 of 6: Boolean minimisation and hazards

Question 1: Boolean minimisation and hazards (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. The three-variable function $f = A\overline{C} + A\overline{B} + \overline{A}\,\overline{B}\,C$ over inputs $A,B,C$.

Find. A direct gate realisation, the minimal SoP and PoS forms, a K-map confirmation, and hazard-free versions of each.

Approach. Realise the expression literally, tabulate the minterms, minimise on a Karnaugh map for both the 1-cells (SoP) and the 0-cells (PoS), then test each two-level form for logic hazards and add the covering consensus term where a hazard exists.

(a) Direct synthesis

Written as it stands, $f$ is the OR of three product terms — two two-input ANDs ($A\overline{C}$ and $A\overline{B}$) and one three-input AND ($\overline{A}\,\overline{B}\,C$) — with inverters generating $\overline{A},\overline{B},\overline{C}$.

(b) Algebraic minimisation

Evaluating the expression gives the on-set $f=\sum m(1,4,5,6)$. Grouping the 1-cells:

1. Combine the two A=1 cells that share C=0. $m_4,m_6 \Rightarrow A\overline{C}$.
2. Combine the two B=0,C=1 cells. $m_1,m_5 \Rightarrow \overline{B}C$.
3. Discard the redundant term. $A\overline{B}$ ($m_4,m_5$) is fully covered by the two groups above, so it drops out, giving the minimal SoP $$\boxed{f = A\overline{C} + \overline{B}\,C}$$

For the PoS form, minimise the 0-cells $\overline{f}=\sum m(0,2,3,7)$. They group as $\overline{A}\,\overline{C}$ ($m_0,m_2$) and $BC$ ($m_3,m_7$), so $\overline{f}=\overline{A}\,\overline{C}+BC$. Complementing with De Morgan:

$$\boxed{f = (A+C)(\overline{B}+\overline{C})}$$

(c) K-map verification

The map below confirms both forms: the shaded pairs are the SoP groups $A\overline{C}$ (green, $m_4,m_6$) and $\overline{B}C$ (blue, $m_1,m_5$); the two empty 0-cell pairs $m_0m_2$ and $m_3m_7$ give the PoS factors $(A+C)$ and $(\overline{B}+\overline{C})$.

(d) Hazard analysis

A static-1 hazard exists in the SoP wherever two adjacent 1-cells are covered by different product terms. Cells $m_4=100$ ($A\overline{C}$) and $m_5=101$ ($\overline{B}C$) are adjacent (they differ only in $C$): with $A=1,B=0$, toggling $C$ hands the output from one AND gate to the other, and a momentary 0-glitch can appear. The cure is the consensus term of $A\overline{C}$ and $\overline{B}C$ with respect to $C$, namely $A\overline{B}$ — exactly the term dropped in part (b):

$$\boxed{f_{\text{hazard-free}} = A\overline{C} + \overline{B}\,C + A\overline{B}}$$

By duality the PoS has a static-0 hazard between the adjacent 0-cells $m_2=010$ (factor $A+C$) and $m_3=011$ (factor $\overline{B}+\overline{C}$). Adding the consensus sum term $(A+\overline{B})$ removes it:

$$f_{\text{hazard-free}} = (A+C)(\overline{B}+\overline{C})(A+\overline{B})$$