0
\$\begingroup\$

How should I proceed to find the minimum number of 2 input NAND gates to realize this boolean expression. I am allowed to use both complemented and non-complemented inputs.

$$F = X.Y + Y.Z + \overline{X}.\overline{Y}.\overline{Z}$$

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Welcome to EE.SE! This looks like a homework assignment. Please show what you have tried to far. \$\endgroup\$
    – winny
    Aug 25 '19 at 10:46
  • 3
    \$\begingroup\$ Homework questions with no attempt at a solution are closed. \$\endgroup\$ Aug 25 '19 at 12:26
  • 1
    \$\begingroup\$ Hint; De-morgans theorem \$\endgroup\$
    – Mitu Raj
    Aug 26 '19 at 10:29
  • \$\begingroup\$ @LeonHeller I had just asked for some hint on how to proceed with the problem as I have no clue on how to prove that any solution I arrive at is the optimal solution. I did not ask you to solve the problem for me. \$\endgroup\$ Aug 27 '19 at 15:55
  • \$\begingroup\$ Mitu gave you a great hint. Edit your question showing some effort. We are willing to help, but you have to try. We do not do the heavy lifting. \$\endgroup\$ Aug 28 '19 at 0:00
0
\$\begingroup\$

You can walk through the expression using de Morgans, a nand gate can be an inverter, an OR gate or a AND gate by combination,

enter image description here

image source: https://www.quora.com/How-do-I-convert-logic-gates-by-using-only-NAND-gates

So you walk through, build up the brute force way of making it, then go back over it to see if anything can be optimised to reduce it, e.g. doubled inverters,

enter image description here

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Please provide a citation for the graphic(s) you copied into your answer. We want to be sure to give credit to the creators. \$\endgroup\$ Aug 25 '19 at 13:32
0
\$\begingroup\$

There is no fixed procedure for doing this for multiple levels of logic. You're going to need to doodle and play with it.

Look up "bubble pushing", "pushing circles", etc. They're basically just ways of applying DeMorgan's Theorem graphically.

Bubble pushing images

Source: https://grace.bluegrass.kctcs.edu/~kdunn0001/files/Simplification/4_Simplification10.html

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.