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.(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Changing between circuits

Can you offer guidance or do you also need help?

**Physics Forums | Science Articles, Homework Help, Discussion**