# Rewriting a boolean expression only using NAND

So I had a truth table and using a Karnaugh map I simplified a function. I obtained.

$f = \overline{A_3}A_2\overline{A_1} + \overline{A_2}\overline{A_0} + A_3\overline{A_0}$

Then using the distributive property of boolean algebra:

$f = \overline{A_3}A_2\overline{A_1} + \overline{A_0} (\overline{A_2} + A_3)$

Ok, with this we have the minimum of logic gates to use.

Now I need to convert this to NAND. What seemed easier to me was to take the logigram (or electrical scheme) and directly change the gates to their equivalents with NAND. I obtained:

$f = \overline { \overline{\overline{A_3}A_2\overline{A_1}} \cdot \overline{\overline{A_0} \overline{A_2 \overline{A_3}}} }$

• How should I proceed algebraically to pass to one expression to another (I know I need to apply DeMorgan laws or use the complement of the function... I would thank if someone can give like a tip or something on how to start doing it.

• I'm thinking if there is any way to simplify the NAND expression... I see that I have $A_2$ twice and also $\overline{A_3}$ twice... I'm thinking if there is any way to go even further in the simplification... If someone could also give a tip on how to proceed to not ruin the rule of using NAND only. Thanks very much!

• What does "pass one expression to another" mean? Oct 18, 2016 at 4:39

Only 2-in NANDs?

I see no reason why you have to waste two NANDs to invert the same signal twice, if that was part of your question.

The way I approached your problem was to lay out a table:

\begin{align*} A_3~~A_2~~~~~~~~~~~\\ \begin{array}{c|ccccc} ~~A_1~A_0~~ & & 00 & 01 & 10 & 11 \\ \hline \\ 00 & & 1 & 1 & 1 & 1 \\ 01 & & 0 & 1 & 0 & 0 \\ 10 & & 1 & 0 & 1 & 1 \\ 11 & & 0 & 0 & 0 & 0 \end{array}\end{align*}

From this, it was pretty easy to see that three of the columns were identical and could be replaced by $\overline{A_0}$ and that the remaining column was just $\overline{A_1}$. So the new table became:

\begin{align*} A_3~~A_2~~~~~~~~~~~\\ \begin{array}{c|ccccc} & & 00 & 01 & 10 & 11 \\ \hline \\ & & \overline{A_0} & \overline{A_1} & \overline{A_0} & \overline{A_0} \end{array}\end{align*}

The result is the following:

(Clearly, you will have to replace the inverters with NAND gates. So there are a total of 7 of them.)

The first inverter and NAND gate on the left, accepting $A_2$ and $A_3$, provides an active LOW to indicate when $A_3~A_2=01$. If it is LOW, then this fact disables the NAND gate that $A_0$ goes into, at the bottom. But it enables the NAND gate where $A_1$ arrives. Either one of these are then combined (and finally inverted) to get the desired output.

Perhaps someone else might try their hand at it. But that's how I may have approached it.

You can also go an entirely algebraic approach. You say you know DeMorgan's. So you can play around with the expression you have in order to construct a series of either $\overline{A~B}$ or else $\overline{A}+\overline{B}$ identifiable terms in your expression, making adjustments as you go when you see something that isn't of that basic form.

I chose to try a different approach.

I'm not holding myself out as an expert in this, though. Perhaps one such will enter in and provide a more thorough and steel-minded, rigorous approach for you. I might learn from that, as well.

• Hi @Jonk ! Thank you very much for your answer and sorry if what I was asking wasn't very clear. What I really want to know is if there is any way to reduce the number of NAND gates in our circuit (the one you put in there)? Oct 18, 2016 at 10:51
• Also can you tell me where did you make that draw of the circuit? Thank you so much! Oct 18, 2016 at 10:55
• @GrangerObliviate It's from Logic Friday. It's not good at optimizing schematics, but it uses Espresso to optimize expressions. But it won't optimize well to NAND-only circuits, for example. It is free.
– jonk
Oct 18, 2016 at 16:29
• @GrangerObliviate I'm not aware of more than exploring a set of alternative ways. I don't know of a guaranteed algorithm that goes from a logic statement, guided by constraints you impose, to a necessarily optimum answer. I think the problem is generally NP-complete, but I don't have a paper on it to cite that proves this. I may be wrong and it's just my inexperience speaking.
– jonk
Oct 18, 2016 at 16:35

I have explained in detail how to convert a Boolean expression to NAND form algebraically, with the help of an example in this answer.

$$\ f = \overline{A_3}A_2\overline{A_1} + \overline{A_2}\overline{A_0} + A_3\overline{A_0} \$$

It is a very simple and short method, so I will do it for your expression too:

1. Take the double complement

$$\ f = \overline{\overline{{\overline{A_3}A_2\overline{A_1} + \overline{A_2}\overline{A_0} + A_3\overline{A_0}}}} \$$

2. Apply De Morgan's law for the inner expression, (outer complement is left as it is) to get it in NAND form:

$$\ f = \overline{{\overline{\overline{A_3}A_2\overline{A_1}}. \overline{\overline{A_2}\overline{A_0}}.\overline{A_3\overline{A_0}}}} \$$

• Yes, I've since learned to do that, too. My writing was almost four years ago and I really hadn't considered it much, at the time. Luckily, intuition was sufficient for me back then. ;) +1 for the addition.
– jonk
Jun 15, 2020 at 16:43