Converting a Boolean expression to only use 3-input NAND-NAND

Question

I need to convert some Boolean expression to only use 3-input NAND gates. Here is one example of an expression I'd like to convert:

F = (A * C' * D)' + (A * B' * C * D')

I would start by applying DeMorgan's law:

F' = (A * C' * D) * (A * B' * C * D')'

F = [(A * C' * D)' * (A * B' * C * D')']'

Then to convert to 3-input gates only, this is where I get confused. I tried to group the factors in the second expression like:

F = [(A * C' * D)' * ((A * B' * C)' * D')']'

However, this creates an nonequivalent expression. What procedure should I be using here instead?

Thank you!

Answer 1

Transform your expression by inverting the left term $(A \land C' \land D)$:

$$\begin{aligned} F &= (A \land C' \land D)' \lor (A \land B' \land C \land D') \\ &= A' \lor C \lor D' \lor (A \land B' \land C \land D') \end{aligned}$$

The right term $(A \land B' \land C \land D')$ can never be true, unless $A$, $B'$, $C$ and $D'$ are all true. However, in this case $(A' \lor C \lor D')$ is also true. Therefore, the expression can be simplified and rewritten

$$\begin{aligned} F &= A' \lor C \lor D' \\ &= (A \land C' \land D)' \end{aligned}$$

This is a single $3$-input NAND. If required, invert input $C$ with another NAND connecting all inputs in parallel.

For general expressions, use a Karnaugh-Veitch map to derive a minimum sum of products form and translate this to 3-input NAND gates.

My favorite tool for such tasks is Logic Friday 1. It is capable of designing multi-level logic circuits.