2
\$\begingroup\$

The problem was to build an OR gate from NAND gates. I managed to do this in a kind of brute-force way just trying different variations, and finally got it but am feeling unsatisfied since I don't have the intuition.

I think I could have gotten there with DeMorgans law too:

a OR b = ~(~A AND ~B)

Is there a more intuitive "in English" intuition for why this works? I just want it for my own sake.

\$\endgroup\$
3
  • \$\begingroup\$ The way i would verbalise it is:OR low plus low equals low. NAND high plus high equals low. From that you should be able to deduce that inverting the two inputs to the nand will produce an or. \$\endgroup\$
    – Kartman
    Dec 19, 2021 at 4:05
  • \$\begingroup\$ @Kartman This is great, thanks. \$\endgroup\$
    – sco
    Dec 19, 2021 at 5:08
  • \$\begingroup\$ the intuition comes from thinking about the NAND gate inputs in more than one way ... normally you would think that both inputs must be high to get a low output ... but you can think about making one of the inputs low to get an output ... either input, or both inputs can be made low to get a high output ... that is an OR function \$\endgroup\$
    – jsotola
    Dec 19, 2021 at 5:50

3 Answers 3

2
\$\begingroup\$

If you want intuitive- think of the NAND gate- if either input goes low then the output goes high.

So if we invert the inputs (using inverters or NAND gates connected to invert) we have an OR gate.

\$\endgroup\$
1
\$\begingroup\$

As you know, an OR gate outputs "true" if its inputs are not both false.

Hmmm... did I just say "not both"? That sounds like a NAND gate to me! So what we can do is have a NAND gate somewhere in the circuit that's connected like this:

  • Input 1: A is false
  • Input 2: B is false
  • Output: A and B are not both false

First of all, that output condition is exactly the output we want for our OR gate, so we should connect the output of this NAND gate directly to the output of our circuit.

Next, how can we create a signal that means "A is false"? For that, we can just use a NAND gate where both inputs are A. Likewise, we can get "B is false" using a NAND gate where both inputs are B.

Put it all together, and you end up with that famous OR-from-NAND circuit:

A or B = (A nand A) nand (B nand B)

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

Yes, it is all about applying DeMorgan's law.

Basically you can swap OR/AND function by inverting the output and inverting all of its inputs.

DeMorgan's law is about how the Boolean AND and OR functions are analogous. Consider this truth table:

a b ~a ~b a OR b ~a AND ~b a AND b ~a OR ~b
0 0 1 1 0 1 0 1
0 1 1 0 1 0 0 1
1 0 0 1 1 0 0 1
1 1 0 0 1 0 1 0

All of the OR/AND have basically the same pattern, a column of all the same value except one that is different.

To put it in terms of detecting "all inputs":

  • (a OR b) is 0 when all inputs (a,b) are 0
  • (~a AND ~b) is 1 when all inputs (~a,~b) are 1
  • (a AND b) is 1 when all inputs (a,b) are 1
  • (~a OR ~b) is 0 when all inputs (~a,~b) are 0

To put it in terms of detecting "any input":

  • (a OR b) is 1 when any inputs (a,b) are 1
  • (~a AND ~b) is 0 when any inputs (~a,~b) are 0
  • (a AND b) is 0 when any inputs (a,b) are 0
  • (~a OR ~b) is 1 when any inputs (~a,~b) are 1

Boolean AND function is "true" ("1") if, and only if, all of its inputs are "true" ("1"). For the AND function, any "false" ("0") input dominates the output, and it doesn't matter what the other inputs are then. This is similar to the arithmetic multiplication function, where x * 0 = 0 no matter what value of x, and x * 1 = x no matter what value of x.

Boolean OR function is "false" ("0") if, and only if, all of its inputs are "false" ("0"). For the OR function, any "true" ("1") input dominates the output, and it doesn't matter what the other inputs are then. This is similar to the arithmetic addition function, where x + 0 = x no matter what value of x.

There is a symmetry between AND function and OR function: the effect of inverting the logic inputs and outputs, is that the OR/AND function is also inverted, which you can see from the truth table above. It's the same function, just swapped around in a certain way. DeMorgan's law describes this symmetry in a formal way.

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