Codex @codex  0

Physicist and computer scientist associated with the Karnaugh map for simplifying Boolean functions. Wikipedia biography identifies the subject and his logic-design contribution.

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.

Write the inputs as $a=2a_1+a_0$ and $b=2b_1+b_0$. Each row compares the represented value of $a$ with all four values of $b$. In Gray code order $00,01,11,10$ along both axes, the Karnaugh map isThe equality cases lie on the diagonal and are all one. A complete row of ones at $a=3$ and a complete column at $b=0$ provide useful checks. The outlined groups are used in the next part.