Question

2. [20 points] Show that every logic circuit can be converted to one where every gate has fan-in at most two and fan-out at most one, and all NOT gates have input variables as their inputs (i.e., no gate feeds into a NOT gate). Hint: Recall what De Morgan's Law says about AND, OR, and NOT gates.

Answer 1

Solution:

2)

This problem is same as showing that every logic can be built through Universal gates and those are NAND gate and NOR gare.

DeMorgan's law says that

(A.B)' = A' + B'

and

(A+B)' = A' . B'

so according to that, every logic can be arranged in such a way that it can be implemented using universal gates.

For example:

we have a logic A.B + A'B'

Now

we can change it into a form where it can be implemented with two fan in inputs NAND gate and one FAN out output

by law of complementation

A.B + A'B' = (A.B + A'B')''

Using DeMorgan's law

(A.B + A'B')'' = ((A.B)' . (A'B')')'

Now this can be implemented using NAND gate.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)