1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Circuit with 2 not gates

  1. Apr 30, 2010 #1

    1. The problem statement, all variables and given/known data
    You are trying to design a circuit with 3 inputs and 3 outputs. The circuit should negate each of its inputs. e.g. A-> not A, B-> not B, C-> not C. Clearly we can do this using 3 'not' gate. Is it possible to do this using 2 'not' gates and an unlimited number of 'and' and 'or' gates?

    2. Relevant equations
    None I know of.

    3. The attempt at a solution
    I'm not sure whether this is true.
    To prove it's true: Find a circuit. I've tried many with no success.
    To prove it's false: Use an information based argument? Use properties of the different gates?

    Thanks :)

    P.S. This is an OCW question from 6.080
  2. jcsd
  3. Apr 30, 2010 #2
    Someone previously asked the same question on this forum: link
  4. Apr 30, 2010 #3
    try to make a two bit signal that represents the number of 1 bits in the 3 inputs.
    these are the two bits you have to invert.

    the high bit of this is easy, that is a 3-way majority circuit.

    you can use the inverted high bit to compute the low bit.

    Once you have that, you can make a decoder that produces 4 outputs
    that are 1 if 0,1,2 or 3 of the input bits are equal to 1.

    finally to calculate a' you can comtine the cases for 0,1 and 2 1-bits in the input.

    if there are 0 1-bits in the input then a must be 0, so a' = 1
    if there is 1 1-bit in the input then a is 0 if b and c are 1.
    if there are 2 1-bits in the input then ................

    and then you can do the same for b' and c'

    Finally. What is the problem you run into, if you try to embed this circuit in to another copy of it to get more than 2 nots from 2 not gates?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook