6
\$\begingroup\$

I'm frequently asked in class to create a logic circuit based on some specifications. Building the circuit and deriving the equations is the easy part. We are usually told to implement our circuit using only NAND or only NOR gates (akin to a real-life scenario).

I find myself consulting pages like this once I have my equations an am about to draw the circuit. If memorizing these combinations are the only way to make a NAND or NOR exclusive circuit, then I will. But there ought to be a better way of converting everything quickly and neatly.

Anyone?

\$\endgroup\$
1
  • \$\begingroup\$ "Akin to a real-life scenario" In real life, you'd only use discrete gates for combinatorial circuits that have a couple of gates. For anything more than that, a lookup table performs better and is more economical. And lookup tables are also known as multiplexers. This was the right approach for discrete logic even in the 70s, although few people bothered to do it - because they were not taught it. As soon as the TTL and CMOS cookbooks by late Don Lancaster came out in the late 70s, this technique was popularized and anyone not using it had mostly themselves to blame :) \$\endgroup\$ Mar 16 at 3:51

6 Answers 6

14
\$\begingroup\$

If you have an existing schematic consisting of Inverters, AND, and OR Gates, then there is a simple, three step process that you can follow to convert the circuit to all NAND (you can modify the process slightly for NOR). You can use "Bubble Logic".

Let's assume you have three levels of logic. The first level, closest to your inputs, consists of inverters. The second level consists of AND gates. And the final level consists of just a single OR gate. Some textbooks may refer to this as being a "sum of products" Boolean Algebra expression.

  1. Convert all of your AND Gates to NAND Gates.
  2. Wherever you added a bubble, you've actually inverted the Boolean Algebra function on that wire. So, add another bubble to that wire and draw the bubble close to the OR gate on the output.
  3. A NAND gate is equivalent to an OR Gate whose inputs are inverted. So, if you're OR gate at the output has all of its inputs inverted, simply redraw it as a NAND gate. If it does not, then make it so by adding a bubble near the input to the OR and another bubble (inverter) somewhere else on that particular wire.

You could do a similar process for an all NOR implementation. I hope that helps!

\$\endgroup\$
2
  • \$\begingroup\$ I thought maybe I wasn't being clear enough with my question. Thanks for understanding what I meant, and this is a great answer. I have another quick one -- is there a quick way of transforming an equation into a NAND or NOR easily? Say I hadn't drawn my circuit yet and just had my equations. \$\endgroup\$
    – nopcorn
    Nov 1, 2011 at 12:07
  • \$\begingroup\$ is it possible to use this to derive the expression for XOR ie A'B+B'A \$\endgroup\$
    – Dr Deo
    Apr 28, 2014 at 19:32
6
\$\begingroup\$

Building on Bob's answer, and to your question about equations: The basic concept to remember is DeMorgen's Theorem. Using + for OR, * for AND, and ~ for NOT,

~(a + b) = ( ~a * ~b )

~(a * b) = ( ~a + ~b )

In other words, the output of a NOR gate is equivalent to the output of an AND gate with the inputs inverted. And, vice versa: The output of a NAND gate is equivalent to the output of an OR gate with the inputs inverted.

If you move the inversions all to one side you get:

(a + b) = ~( ~a * ~b )

(a * b) = ~( ~a + ~b )

In other words, an OR gate is equivalent to a NAND gate with inverted inputs, and an AND gate is equivalent to an OR gate with inverted inputs.

The trick to realize is that you can move the "bubbles" around and implement DeMorgen's theorem with the schematic. I've heard this called "the bubble game." The idea is to figure out what function you need with just "positive logic" using ANDs and ORs. Then play the bubble game and make them all NANDs and NORs with bubbles on the inputs, then move the bubbles along the lines (two on a line cancel) to make simple NANDs and NORs. Sometimes you need an extra inverter here or there, too.

The bubble game has four rules:
1) You can change ANDs or ORs to (N)ANDs and (N)ORs with bubbles on all terminals. 2) You can "push" a bubble from the output back to the inputs, making them all inverted. 3) You can "push" bubbles from all inputs through to the output, inverting the output. 4) Two bubbles on a line cancel.

Here's an example.

DeMorgan example

It turns out if we only change the output gate we can save a step or two...

enter image description here

Cheers.

\$\endgroup\$
1
  • \$\begingroup\$ how can you use this to derive the expression for xor ie A'B + B'A . Am having a hard time deriving it. \$\endgroup\$
    – Dr Deo
    Apr 28, 2014 at 19:16
1
\$\begingroup\$
  • FOR TWO- INPUT GATES:

    Inputs = A , B

    "+" = OR

    "." = AND


AND

  • OUTPUT is true if A AND B is true,
    Otherwise not true

    Output true if both A AND B are both true.

    • X = A.B

OR

  • Output is true if either A OR B is true,
    Other wise not true

    Output true if A is true OR if B is true OR if both are true.

    • X = A + B

XOR

  • Output is true if A is exclusively true OR if B is exclusively true.
    Otherwise untrue.

    • X = A./B + /A.B
      (Output = A and not B or B and not A.

NAND - output is inverted from AND
NOR output is inverted from OR
XOR leave well enough alone.


FOR N-INPUT GATES

AND

  • OUTPUT is true if A AND B AND C AND ... is true,
    otherwise not true. ALL must be true for output to be true

OR

  • Output is true if either A OR B OR C OR ... is true,
    other wise not true

    ANY one or more may be true & at least one must be true for output to be true

XOR

  • Output is true if any one of A B C D R ... is exclusively true OR if B is exclusively true. Otherwise untrue.

THEN:

NAND = NOT AND output is inverted from AND
NOR - NOT OR output is inverted from OR
XOR leave well enough alone:-)

\$\endgroup\$
0
\$\begingroup\$

That page appears to show truth tables for the basic logic functions. These are things you just need to know.

Fortunately, it's not all that mysterious or difficult. AND and OR do just what they say. For a AND gate, input A AND input B must be true (logic high) for the output to be true (logic high). For a OR gates, input A OR input B must be true for the output to be true. Yes, it's really that simple. NAND again is what it says, which is NOT-AND. The output of a NAND is the opposite (NOT) of a AND. NOR is NOT-OR. The output is opposite of a OR gate output.

This is all really simple stuff. It's like having to learn that 3 plus 2 is 5 before being able to do more complicated arithmetic.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think they are asking about how to know the transforms from using AND/OR/NOT to using either NAND gates alone or NOR gates on their own. It is something I can remember being required to do for class. \$\endgroup\$
    – Kortuk
    Nov 1, 2011 at 9:03
0
\$\begingroup\$

Just remember only addiion for OR
and Multiplication for AND Gates then
If you multiply any number with 0 then you will get 0 what ever may be the other
input then just make the result reverse such as
"If you get 0 make it 1 or if get 1 make it 0 to get the NAND gate outputs"
Same as like that
when you add any number to 1 then the output is 1 (high) what ever may be the other input
then again reverse the result you got and that will be the output for NOR gate.

To avoid the confusion just remember addition for OR and Multiplication for AND
thats it you can go furthur easily.

\$\endgroup\$
0
\$\begingroup\$

If you want to convert to NANDs, derive SoP from karnaugh maps, then all gates can be converted to NANDs.

If you want to convert to NORs, derive PoS from kmaps, then all gates can be converted to NORs.

No real thought is required once Sum of Products or Product of Sums is completed.

It can get a bit more complicated if gates are limited to X pins, but that is not the question.


Proof: Take Sum of Products \$X = A \cdot B + C \cdot D\$, which is ANDs and ORs.

To get to NANDs, we do double negation \$\left({\overline {\overline {X}} = X}\right)\$ and deMorgan's.

$$X = A \cdot B + C \cdot D$$ $$\overline {\overline {X}} = \overline {\overline {A \cdot B + C \cdot D}}$$

DeMorgan's lower bar.

$$X = \overline {\overline {A \cdot B}\ \cdot\ \overline{C \cdot D}}$$

ANDs and ORs become NANDs. Now whether you actually do the double negation and deMorgan's is immaterial. ANDs get converted into NANDs and ORs get converted into a NAND of grouped NANDs.

Similarily, Product of Sums \$X = (A + C) \cdot (B + D)\$, via double negation and deMorgan's becomes \$X = \overline{\overline{A + C} + \overline{B + D}}\$ or all NORs. Convert ORs to NORs and the ANDs to a NOR of grouped NORs.

\$\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.