Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

DeMorgan's theorem, What does it logically mean? I missed it on a test!

  1. Oct 10, 2005 #1
    Hello everyone, this problem is bothering me!
    The problem states:
    Note: 'x means x is complemented, or a bar is over it.
    One of DeMorgan's theorems states that 'x+'y = 'x'y; Sipmly stated, this means that logically there is no difference between:
    (a) a NOR gate and an AND gate with inverted inputs.
    b. a NAND gate and an OR gate with inveted inputs.
    c. an AND gate and a nor gate with inverted iputs.
    d. a nor gate and a NAND gate with inverted inputs.

    I said, d, which was wrong.
  2. jcsd
  3. Oct 10, 2005 #2


    User Avatar
    Science Advisor

    I know two different versions of DeMorgan's theorem and neither one is stated like that!

    Yes, that is DeMorgan's "law"- my point is that there are several ways of stating it. One is in terms of logic: (NOT)(a OR b) is the same as (NOT a) AND (NOT b), the other is in terms of sets: the complement of the union of sets A and B is the intersection of the complements of A and B.

    Both are exactly the same thing as your statement, the first one ALMOST the same- but not given in terms of "gates"!

    Looking precisely at 'x+ 'y= '(xy) I would interpret that as (NOT a OR NOT b) is the same as NOT (a AND b) and if I have my "gates" right, that would be saying that NAND gate {NOT (a AND b)} is the same as an OR gate with inverted inputs (NOT a OR NOT b), choice (b).

    Frankly, I don't consider that a very good question because DeMorgan's law can also be phrased the other way around: ('x'y)= '(x+y). That would be (NOT x and NOT y) is the same as NOT(x or y), or "a NOR gate is the same as two AND gates with inverted inputs", choice (a).

    In any case, it would not be (d) because there is no " a NAND gate with inverted inputs."- no "double negatives".
  4. Oct 10, 2005 #3


    User Avatar
    Staff Emeritus
    Science Advisor

  5. Oct 10, 2005 #4
    thanks for the explanation! I know how to apply DeMorgan's theorem but this one screwed me!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook