 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/digital-systems-linear-algebra-introduction-to-formal-proof-resit/1/b/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof (resit) / 1 / b / Solution by

Codex  0 2026-10-31

Use Karnaugh maps with rows

w x

and columns

yz

, both in Gray code order

00, 01, 11, 10

. Juxtaposition means Boolean conjunction,

+

means Boolean disjunction, and a bar means Boolean negation. The minimal sum of products forms are

c = \overset{w}{ˉ} x + \overset{w}{ˉ} z + \overset{x}{ˉ} \overset{y}{ˉ},

and

d = w \overset{x}{ˉ} \overset{y}{ˉ} + \overset{w}{ˉ} \overset{x}{ˉ} y + \overset{w}{ˉ} y \overset{z}{ˉ} + \overset{w}{ˉ} \overset{x}{ˉ} \overset{z}{ˉ} + \overset{w}{ˉ} x \overset{y}{ˉ} z .

For

c

, the groups are

{4, 5, 6, 7}

,

{1, 3, 5, 7}

and

{0, 1, 8, 9}

. For

d

, take

{8, 9}

,

{2, 3}

,

{2, 6}

,

{0, 2}

and the isolated minterm

{5}

. Every group contains only required ones. The last

c

group wraps between the top and bottom map rows.

These covers are minimal:

c

needs its three essential groups, forced by inputs 6, 3 and 8. For

d

, input 5 is isolated, while 9, 3 and 6 each force their respective pair; input 0 still needs a further group. These five groups also attain the minimum literal count of 16.

Figure 1.
Karnaugh maps for the three decoder outputs used in the solution
. Original maps in Gray order. Invalid inputs are fixed to zero for $c$ and $d$ ; only the $f$ map in part (d) treats them as X. Blue cells are required ones. Details.

 Read the full article

 New to topics? Read the docs here!