Show that a circuit of size $s$ can be converted to a DeMorgan circuit computing the same function of size at most $2s$ I am trying to prove the above statement. A DeMorgan circuit is a circuit that has only $\{ \wedge, \vee, \neg \}$ gates and the negation is applied only to input variables.
So, assuming we have a circuit of size $s$ that computes a function $f: \{0,1\}^n \rightarrow \{0,1\}$. The basis for this circuit is $\{\wedge, \vee, \neg\}$ with fan-in 2 for the OR and AND gates. I am trying to prove we can convert this circuit to a DeMorgan circuit of size at most $2s$.
Intuitively and in small examples this claim makes sense to me but I would like to prove that more formally. I have searched in several papers but this claim is mostly mentioned but not proved. Can someone give me an intuition about the proof?
The above statement was mentioned in the following paper https://eccc.weizmann.ac.il/report/2018/154/ in the second paragraph of the 1st page and continuing on 2nd page.
The idea is to &quot;move backwards&quot; all the not gate. Assume you have some circuit, for example $(\cdot,\cdot)\rightarrow AND\rightarrow NOT\rightarrow OUTPUT$
Can be converted to:
$(\cdot \rightarrow NOT,\cdot \rightarrow NOT)\rightarrow OR\rightarrow OUTPUT$
Doing this without thought can increase the circuit size exponentially. So, when you see two $NOT$ gates one after another - cancel both of them out. I guarantee you this will work, but I wont prove it to you (this is your task)