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

How do I convert CC-NOT gates to OR operators?

  1. Jun 18, 2010 #1
    Fredkin Gates are supposed to be universal. So far I've gotten AND, OR and NOT out of them but I can't figure out XOR. Any help?

    I know that A XOR B = (A AND NOT B) OR (B AND NOT A), but trying to recreate that with Fredkin Gates is not very elegant... is that the only way?

    Edit: I guess I can't change the title of my thread...

    nvm this bottom part of this post, it's been solved already.

    According to Feynman Lectures in Computing, by using only C-NOT, CC-NOT and NOT gates we can recreate AND, OR and XOR gates.

    I understand how to create AND and XOR, but I can't work out the OR. I spent a good few hours pondering and trying out different truth tables but I just don't get it. Can anyone demonstrate a way?
    Last edited: Jun 18, 2010
  2. jcsd
  3. Jun 18, 2010 #2


    User Avatar
    Homework Helper

    If you have AND and NOT, then NOT ( (NOT (INPUT1)) AND (NOT (INPUT2)) ) = ((INPUT1) OR (INPUT2))
  4. Jun 18, 2010 #3
    Ahh so simple. Can't believe I forgot something so basic. Thanks, you actually helped me clear up a whole other question as well.
    Last edited: Jun 18, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook