4
\$\begingroup\$

The title pretty much says it all. I know that A' + B' = (AB)' is the basic transformation needed to do so (at least for NAND gates), but whenever I apply this I feel like I'm doing it wrong. For example:

C' + AB' + A'BD'

Here's what I did:

I took - C' + AB' - and made it into - (CA'B)' -

which reduced the problem to:

(CA'B)' + A'BD'

Which further reduced down to:

((CA'B)')'(AB'D)'

Is this the right way to do this? Also, why is this form sometimes wanted? It seems more complicated than the original form.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ As for why it's desired take a look at the schematic for an AND gate. It's a NAND with an inverter. By converting logic to NAND gates, you reduce transistor count. \$\endgroup\$
    – Samuel
    Nov 30, 2015 at 22:32
  • 1
    \$\begingroup\$ How to do it right? Read up on the laws of De Morgan and how a Karnaugh map works. Those are the right tools for converting to only-NAND and only-NOR circuits. \$\endgroup\$
    – Mast
    Dec 1, 2015 at 7:10
  • \$\begingroup\$ You are doing it wrong. C' + AB' in your notation maps to (C(A' + B))' rather than (CA'B)'. So that does not really help. \$\endgroup\$
    – user93233
    Dec 1, 2015 at 12:16

3 Answers 3

21
\$\begingroup\$

The most convenient form of amplifier for use in a gate - because it has high input impedance and useful voltage gain - happens to be inverting. This is true whether it is a BJT (common emitter) or FET (common source) amplifier.

Thus a gate formed of a single amplifier stage MUST have an inverting output - that means it can implement any of NAND, NOR, or NOT. (There are a very few exceptions, like ECL, whose lack of gain makes them very intolerant of voltage variations)

So if you look at an AND gate - or an OR - you will find a NAND followed by an inverter - or a NOR + inverter.

That makes AND not only more expensive and power-hungry than NAND, but also slower.

The fact that any combinational boolean expression can be rendered into sum-of-product form (AND then OR), and trivially transformed into NAND-NAND form simply by inverting all the intermediate signals (using DeMorgan to implement the OR function with NAND gates) makes a network of NAND gates incredibly attractive way of implementing it. (Ditto Product-of-Sums, using only NOR gates).

schematic

simulate this circuit – Schematic created using CircuitLab

This shows how AND and OR gates can be implemented using either NAND or NOR technologies (Exhibits A and B).

It also shows how a simple expression in SOP form (A AND B) OR C would be implemented if you simply used AND and OR gates formed from NAND blocks.

Hopefully it's obvious that all you need to do is delete pairs of inverters to arrive at the final NAND circuit.

The result uses only 2 levels of gain instead of 4 if you used AND/OR, so for the price of a little extra thought, your logic is twice as fast.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ The "(A and B) or C" could in most processes be implemented more efficiently as by adding an inverter to the output of a 3-input gate which computes "not ((A and B) or C)". In CMOS, such a gate would take 6 transistors, plus two for the output inverter, or 8 total. Two four-input nand gates as you show would take 4 transistors each, plus two for the inverter, or ten total. \$\endgroup\$
    – supercat
    Jan 17, 2017 at 20:00
  • \$\begingroup\$ @supercat Indeed yes, if you can work below the discrete gate level, there are other options open to you. \$\endgroup\$
    – user16324
    Jan 17, 2017 at 23:04
  • \$\begingroup\$ Do you know of any common terminology to describe a single gate with an arbitrary combination of AND/OR logic followed by an inverter? If a process can support both an N-input NAND and an N-input NOR, any other combination of AND and OR with N inputs that are each used once should be likewise realizable for the same number of transistors. \$\endgroup\$
    – supercat
    Jan 17, 2017 at 23:15
  • \$\begingroup\$ Sorry, not that I know of. There seems to have been an attempt to drive more universal And/Or/Invert gates (7450, 7451) but that didn't seem to last. \$\endgroup\$
    – user16324
    Jan 17, 2017 at 23:24
  • \$\begingroup\$ I find many things about the what parts exist and don't exist curious. For example, the 74HC153 and 74HC253 are alike except for the functions of pins 1 and 15 which act as enables that either force the outputs low or 3-state, but for many purposes it would be more useful to have two independent muxes without the enable controls and hazard-avoidance logic. I know of no such part, though. Muxes make great universal gates. \$\endgroup\$
    – supercat
    Jan 17, 2017 at 23:32
5
\$\begingroup\$

The point of converting functions to NAND or NOR is the fact NAND or NOR are forming a complete logic systems, which means that any boolean system can be implemented only by using the named gate. This is not the case with the OR, AND and NOT gates. Using a single type of gate is simplifying the implementation of synthesis algorithms and the underlying hardware. As for the concrete example in the question - it can be verified by checking the truth tables of the original and the resulting expression, and I believe you can do it yourself.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ As an example that only NAND or NOR gates can be used to implement any logic system, the Apollo Guidance Computer that guided the Apollo spacecraft to the moon consisted entirely of NOR logic: 2800 ICs, each with dual three-input NOR gates. \$\endgroup\$
    – tcrosley
    Nov 30, 2015 at 23:02
1
\$\begingroup\$

ANDs and ORs do not exist inside ASICs. All logic gates can be made from NANDs or NORs, so they are known as universal gates.

Transformation involves DeMorgan's (invert expression, invert terms, change operator) and Double Negation (\$ \overline { \overline{X}} = X\$).

Starting with AND / OR: \$ \overline {C} + A\overline{B} + \overline {A} B \overline{D}\$.

Take DeMorgan's.

\$ \overline{\overline{\overline {C}} ∙ \overline{A\overline{B}} ∙ \overline{\overline {A} B \overline{D}}} = \overline{C ∙ \overline{A\overline{B}} ∙ \overline{\overline {A} B \overline{D}}}\$

Now NAND - NAND.

Again starting with AND / OR: \$ \overline {C} + A\overline{B} + \overline {A} B \overline{D}\$.

Take DeMorgan's on terms.

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

Double Negation.

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

NOR - NOR (with a second NOR as a NOT gate).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.