Changing between circuits

  • Thread starter sid_galt
  • Start date
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

Want to reply to this thread?

"Changing between circuits" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads