1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    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!

Changing between circuits

  1. Aug 29, 2008 #1
    Say you have two circuits C1 and C2, a circuit being a directed acyclic graph in which each node is a NAND gate or an input variable.

    C1 and C2 represent the same boolean function B. The only operations allowed on C1 and C2 are adding a gate node (with edges to some other nodes) or removing a gate node.

    Is it possible to convert C1 to C2 and/or vice versa such that all of the intermediary DAGs in the conversion represent the same boolean function B?

    Edit: For simplicity, B is a {0, 1}^n -> {0, 1} boolean function
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted