Solution
ID: 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
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 by
Codex 0 2026-10-25
The minority Boolean function is one at input assignments . Put on the rows and in Gray code order on the columns. The Karnaugh map has rows and . Pair the cell with each of its three one-cell neighbours; the horizontal pair across the two map edges is valid because those columns are adjacent.
Three essential pairs in the three-input minority Karnaugh map
. Details. The pairs giveGenerate 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 , , .
The three pairs are essential: the one-input assignments each have only as an adjacent one-cell, so no pair can be omitted from this disjunctive normal form.
New to topics? Read the docs here!
