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