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 / 3 / c / 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.

The pairs giveGenerate $A=\neg a,B=\neg b,C=\neg c$ with three NOT gates. Then useDe 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=\mathrm{NAND}(n_1,n_2)$, $u=\mathrm{NAND}(t,t)$, $m=\mathrm{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.