Convert this Boolean expression so that we can implement using only NOT's and NANDS

Question

Originally I had this expression:

$$\overline{DCB}A+\overline{DC}B\overline{A}+\overline{DC}BA+\overline{D}C\overline{B}A+\overline{D}CBA+D\overline{C}BA+DC\overline{B}A$$

which I managed to simplify to:

$$\overline{D}A+\overline{DC}B\overline{A}+D\overline{C}BA+DC\overline{B}A$$

Now I must simplify this so that I can use NOT and NAND gates to create the overall circuit. How can I do this? Have I simplified enough or am I missing a few steps?

Answer 1

First, I'll use $'$ for the NOT instead of the overline ...

Now:

Any $AB$ can be rewritten as $(A \text{ nand } \ B)'$

And $A + B$ can be rewritten as $A' \text{ nand } \ B'$

Applied to your statement:

$$D'A+D'C'BA'+DC'BA+DCB'A =$$

$$\big(D'A+D'C'BA'\big)+\big(DC'BA+DCB'A\big) =$$

$$\big((D'A)' \text{ nand } \ (D'C'BA')'\big)' \text{ nand } \ \big((DC'BA)' \text{ nand } \ (DCB'A)'\big)' =$$

$$\big((D'A)' \text{ nand } \ ([D'C'][BA'])'\big)' \text{ nand } \ \big(([DC'][BA])' \text{ nand } \ ([DC][B'A])'\big)' =$$

$$\big((D' \text{ nand } \ A)'' \text{ nand } \ ([D' \text{ nand } \ C']'[B \text{ nand } \ A']')'\big)' \text{ nand } \ \big(([D \text{ nand } \ C']'[B \text{ nand } \ A]')' \text{ nand } \ ([D \text{ nand } \ C]'[B' \text{ nand } \ A]')'\big)'=$$

$$\big((D' \text{ nand } \ A)'' \text{ nand } \ ([D' \text{ nand } \ C']'\text{ nand }[B \text{ nand } \ A']')''\big)' \text{ nand } \ \big(([D \text{ nand } \ C']'\text{ nand }[B \text{ nand } \ A]')'' \text{ nand } \ ([D \text{ nand } \ C]'\text{ nand }[B' \text{ nand } \ A]')''\big)'=$$

$$\big((D' \text{ nand } \ A) \text{ nand } \ ([D' \text{ nand } \ C']'\text{ nand }[B \text{ nand } \ A']')\big)' \text{ nand } \ \big(([D \text{ nand } \ C']'\text{ nand }[B \text{ nand } \ A]') \text{ nand } \ ([D \text{ nand } \ C]'\text{ nand }[B' \text{ nand } \ A]')\big)'$$

Please note that I had to break up the groups of 4 into groups of 2 since NAND is not associative, and so you can't write something like $A \text{ nand } \ B \text{ nand } \ C \text{ nand } \ D$ like you can with the AND and OR.

Answer 2

Let us look at the truth tables ( false = 0, true = 1 ): $$\begin{array}{ccc} var&OR&AND&NAND\\00&0&0&1\\01&1&0&1\\10&1&0&1\\11&1&1&0\end{array}$$

As we can see the table for OR and NAND are "upside down" related to each other. So if we can map $11 \Leftrightarrow 00$ somehow we can translate them to each other. One way to do this is to not both variables first:

$$\begin{array}{ccc} !var&AND&NAND\\11&1&0\\10&0&1\\01&0&1\\00&0&1\end{array}$$

As we can see the column for nand is now the same as the column for or. So we have found a way to build "or" with not and nand. I'm going to assume you already know how to build and from nand and not.

Now you can just use this to build term by term, anding together until you have gotten all factors in and then use the tables above for building the OR.

Answer 3

$\overline{D}A+\overline{D}\overline{C}B\overline{A}+D\overline{C}BA+DC\overline{B}$

The common trick is to add a negation to the start and end of each wire. You get:

$$\text{nand}( \text{nand}(\overline{D},A),~ \text{nand}(\overline{D},\overline{C},B,\overline{A}),~ \text{nand}(D,\overline{C},B,A),~ \text{nand}(D,C,\overline{B}))$$

Btw don't use $\overline{DC}$ to mean $\overline{D}~\overline{C}$. They are 2 different expressions.

Answer 4

Your expression can be further simplified to

$$ AD' + BC'D' + ABC' + AB'C \enspace. $$

This can be seen in a variety of ways. My favorite is to apply the consensus theorem to the first term ($AD'$) and each of the others.

What you need to do next depends on the context. In a course that focuses on the design of logic circuits, you assume that three and four-input NAND gates exist (as they do in all mainstream logic families, starting with CMOS) and that the translation is trivial. Oftentimes problems like this one are assigned to verify that the student has understood that the translation of an AND-OR expression into a NAND-NAND expression boils down to replacing all AND gates and all OR gates with NAND gates. In your case,

$$ ((AD')' \cdot (BC'D')' \cdot (ABC')' \cdot (AB'C)')' $$

is the desired expression. Of course, this only works for AND-OR (sum of products) expressions. For OR-AND (product of sums) expressions a similar process produces NOR-NOR expressions. For more than two levels, things get interesting. Note that the input inverters don't count as one level.