 Solution

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

Each parenthesized pair in the given Boolean function tests equality of two input bits:

(a \lor \neg c) \land (\neg a \lor c) = (a \land c) \lor (\neg a \land \neg c) .

z

is one whenever either input pair agrees. Generate the four complemented inputs with four inverters, and define the following NAND gate outputs:

u_{1} u_{3} = NAND (a, c), = NAND (b, d), u_{2} u_{4} = NAND (\neg a, \neg c), = NAND (\neg b, \neg d) .

Feed these four outputs into a single four-input NAND gate. De Morgan's laws give

z = NAND (u_{1}, u_{2}, u_{3}, u_{4}) = a c \lor \neg a \neg c \lor b d \lor \neg b \neg d .

Here juxtaposition denotes logical conjunction. The construction uses only inverters, two-input NAND gates and one four-input NAND gate, as required.

 New to topics? Read the docs here!