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

Can't understand the Fredkin gate well

  1. Dec 13, 2011 #1
    I'm having trouble understanding why the Fredkin gate is universal. I am getting nowhere when I am trying to build a NOR gate, which would prove that the Fredkin is universal.

    (There's 3 inputs, C, I1, and I2)
  2. jcsd
  3. Dec 19, 2011 #2
    I believe you can implement a NOR gate using only 2 Fredkin gates.

    Hint: use one of them as an inverter. You implement that by doing ...

    And then the other one must be a ... And you implement that by doing ...
  4. Dec 20, 2011 #3
    Thanks for the response. I actually figured it out earlier, since I was confused as to what the inputs meant at first. I thought that inputs A and B that were to be NOR-ed together were the bottom 2 inputs (aka I1 and I2 that I said on the first post) on the gate. But it's actually better to have input A be on the top of the first gate, and then input B on top of the second gate.

    Then, for inputs I1 and I2 on the first bottom gate, set them as 1 and 0, respectively. That way, we pass on "A-not" to the second gate (If A = 0, it passes 1; If A = 1, the Fredkin gate switches I1 and I2 to pass on 0 to the next gate) as I1 (for the second gate), with I2 (for the second gate) being 0 and the second "true" input B being the top of the second gate. This way, if B = 1, then the second gate's I1 and I2 switch to pass on 0. If B = 0, then the output depends on "A-not". If A = 1, then it passes 0, which it should. If A = 0, then it passes 1, which it should, since a NOR is only true if both A and B are 0.

    And you are right, only 2 Fredkin gates are necessary.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook