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

Table of contents
- Solution 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) .

This is logical equivalence, or the two-input XNOR gate function. Thus

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.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version