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?