# Is it possible to implement SOP with 4 terms by only 3 NAND gates?

if I have a truth table for ABC and output Z

ABC Z
000 1
001 1
111 1
110 1


SOP=A'B'C'+A'B'C+ABC+ABC'

the most straight forward way will be 3 AND,1 NAND,1 OR .But, I was told this can be done with 3 NANDS... I tried simplified it, I got A'B'+AB...which can be done with 3 NANDS but,is it make sense to ignore input c?

Can someone help?

Thanks

-
Assuming Z is zero in all states not listed (otherwise, just wire the output high and don't bother with any gates) how can you compute A xnor B with three NAND gates? The output gate cannot connect to either input, since there A=1 B=0 and A=0 B=1 should both have the output low, and having either A or B would drive the output high. Even using three-input gates, I can't see any solution using less than five NAND gates. –  supercat Feb 8 '12 at 15:43
Yeah, don't exclude the other states. They could be Z=0, or Z=X (don't cares). As is, this would reduce to Z=1. –  darron Feb 8 '12 at 19:36

It makes sense, because if you look at the function, there are pairs of terms in which C appears both negated and not; so it has no influence on the output; and, if you look at the truth table, the same applies.

$${\lnot C} + {C} = 1$$ and $$AB \cdot (C+ \lnot C)=AB \cdot 1 = AB$$

So you can just discard C.

-

If you draw the Karnaugh Map (i.e. K-Map) this becomes clear:

        <--- !B --->   <--- B --->
A\BC   00     01     11     10
+------+------+------+------+
!A 0 |   1  |   1  |   0  |   0  |
+------+------+------+------+
A 1 |   0  |   0  |   1  |   1  |
+------+------+------+------+
!C -->  <--- C --->  <-- !C


The minimum cover of the map above is (!A * !B) + (A * B)

Synthesis of an OR gate from NAND gates requires three NAND gates by itself (ref). Synthesis of an AND requires two NAND gates, and synthesis of a NOT gate requires one NAND gate. Assuming you have both senses of the input signals available, you can create this logic with three NAND gates in a tree topology.

One of the NAND gates takes the two negative inputs, a second NAND gate takes the two "positive" inputs, and the third NAND gate takes the outputs of the other two NAND gates to produce the output. This can be demonstrated by drawing the logic circuit with OR and AND gates, putting "bubbles" on either side of the internal nets, and then pushing the bubbles through the OR gate on the output to create a NAND gate, leaving you with three NAND gates.

-
Did anything specify that the inputs were available in both inverted and non-inverted forms? Absent such an assumption, I don't really see any way to do the job in less than five NANDs (one solution with five NANDs would be to simply invert the inputs, and then exploit the fact that one would then have both inverting and non-inverting inputs). –  supercat Feb 8 '12 at 22:14
@supercat yes completely agree –  vicatcu Feb 8 '12 at 23:06

If you can use NAND gates with open collector (or open drain) outputs, you can do it with 3 gates. Though I do not know if that counts (maybe this is a logic problem, not a "we don't want another chip and only have 3 gates left" problem).

-
oh very clever! but it does use an additional resistor ;) –  vicatcu Feb 9 '12 at 16:09
@vicatcu, a resistor takes up less space (and costs less) than an additional logic chip. Though it would need one more resistor (for U1A output), I overlooked it. Still, two resistors are cheaper and smaller than an additional chip. –  Pentium100 Feb 9 '12 at 20:42
true, I maintain it's quite clever! –  vicatcu Feb 9 '12 at 21:09