Can C1 and C2 be converted while maintaining the same boolean function B?

[sid_galt]

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

 

[fresh_42]

Here is a list you could look at for Boolean normal forms:
https://en.wikipedia.org/wiki/Conjunctive_normal_formhttps://en.wikipedia.org/wiki/Disjunctive_normal_formhttps://www.cmi.ac.in/~madhavan//courses/theorem-proving-2014/slides/slides-18mar2014.pdf