# Evaluate logical expression with a couple NAND gates

I'm trying to implement a clever way to do error correction of 4 bits with the classic 3 parity bit correction and such.

I'm constrained by the number of logic gates I can use, but I'm trying to implement the following logic expression

OUT = AB(~C) + A(~B)C + (~A)BC + ABC

I have access to A, B, C, ~A, ~B, ~C, (A + B), (A + B + C), ~(AB), ~(BC) from other parts of the circuit. I also have exactly one inverters and 4 NAND gates (2 inputs per gate) to spare. Is it possible to implement the above logic function?

(I am using ~ as logical NOT)

I've messed around with De Morgan and Karnaugh maps but they don't help much when it comes to gate-specific constraints like these.

UPDATE: I've freed up 1 extra inverter and 1 extra NAND, for a total of 2 inverters and 5 NANDs.

• How many inputs on each of your NAND gates? It looks like four 3-input gates would do nicely. Oct 1 '13 at 18:51
• 2 inputs on each NAND. but if it's worth anything I'll upvote an explanation using 4 3-input gates Oct 1 '13 at 18:54
• Note that the last term can be combined with any one of the other three. Oct 1 '13 at 18:58
• yep, the k-map reveals that. i've figured out how to free up 1 more NAND gate and 1 more inverter from the rest of my circuit, so I have access to 5 now Oct 1 '13 at 19:18

I think this is a solution, after playing with the expression a bit. simulate this circuit – Schematic created using CircuitLab

Derivation:

$$AB\overline{C} + A\overline{B}C + \overline{A}BC + ABC$$ $$= AB(C+\overline{C}) + A\overline{B}C + \overline{A}BC$$ $$= AB + A\overline{B}C + \overline{A}BC$$ $$= AB + C\cdot(A\overline{B} + \overline{A}B)$$ $$= \overline{\overline{AB} \cdot \overline{C\cdot (A\overline{B} + \overline{A}B)}}$$ $$= \overline{\overline{AB} \cdot \overline{C\cdot (A+B)\cdot\overline{AB}}}$$ Turning the 3-input NAND into 2 2-input NANDs and an inverter: $$= \overline{\overline{AB} \cdot \overline{C\cdot \overline{\overline{(A+B)\cdot\overline{AB}}}}}$$

• Great work. I love logic gate derivations. I'm seeing a therapist about it.
– scld
Oct 1 '13 at 19:42
• my favorite answer, for good explanation & clever use of my existing circuitry. thanks! Oct 1 '13 at 19:46

Following up on @Dave Tweed, we can simplify the logical expression to

OUT = AB + BC + AC


Using DeMorgan's this again is equivalent to:

OUT = (AB)'' + (BC)'' + (AC)
OUT = ((AB)' (BC)')' + (AC)


This as it is, can easily be converted to a logic circuit that uses 2-input NAND gates simulate this circuit – Schematic created using CircuitLab

• However, this uses 4 more gates than available.
– scld
Oct 1 '13 at 19:15
• new development, i actually have 5 gates now. this one uses 5 gates and i can use the inverter to spare. cheers! Oct 1 '13 at 19:28
• @ejang Good to hear! I actually made a few changes. So I got rid of 2 NAND gates and put in that inverter of yours. Now this design is one you can work with! Oct 1 '13 at 19:30
• @ChrisL Sorry for not mentioning earlier: Thanks for the review. I wouldn't have gone and been able to crrect my previous errors otherwise. Oct 1 '13 at 19:31
• You can get rid of NAND1 and NAND2 because ~(AB) and ~(BC) already exist in "other parts of the circuit".
– Greg
Oct 1 '13 at 19:35