= Solution
The <minority Boolean function> is one at input assignments $000,001,010,100$. Put $a$ on the rows and $bc$ in <Gray code> order $00,01,11,10$ on the columns. The <Karnaugh map> has rows $1101$ and $1000$. Pair the cell $000$ with each of its three one-cell neighbours; the horizontal pair across the two map edges is valid because those columns are adjacent.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/digital-systems-linear-algebra-introduction-to-formal-proof-minority-karnaugh.png]
{title=Three essential pairs in the three-input minority Karnaugh map}
The pairs give
$$
\boxed{m=\neg a\neg b\lor\neg a\neg c\lor\neg b\neg c.}
$$
Generate $A=\neg a,B=\neg b,C=\neg c$ with three <NOT gates>. Then use
$$
n_1=\operatorname{NAND}(A,B),\quad n_2=\operatorname{NAND}(A,C),\quad n_3=\operatorname{NAND}(B,C),\quad m=\operatorname{NAND}(n_1,n_2,n_3).
$$
<De Morgan laws> show that the final <NAND gate> computes the required disjunction of the three products. This uses three two-input <NAND gates> and one three-input <NAND gate>, besides the input <inverters>. If only two-input <NAND gates> are available, replace the final three-input gate by $t=\operatorname{NAND}(n_1,n_2)$, $u=\operatorname{NAND}(t,t)$, $m=\operatorname{NAND}(u,n_3)$.
The three pairs are essential: the one-input assignments $001,010,100$ each have only $000$ as an adjacent one-cell, so no pair can be omitted from this <disjunctive normal form>.
Back to article page
