# 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 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 the 2nd page.

• If the fan-in is constant, you can get $O(s)$ by replacing each non-de Morgan gate with a constant size circuit computing the same function. May 28 at 6:57
• @YuvalFilmus you have to beware though, just applying de-morgan's law can exponentially increase the circuit size (each NOT will doubled, for every gate we apply the law on) May 29 at 11:23
• I don't think so. It's a gadget reduction. Every gate is replaced by a constant size gadget. May 29 at 11:44
• @YuvalFilmus all "NOT" gates need to be only in the input, so when you do some transformation [ for example: NOT($a$ AND $b$) into (NOT $a$) OR (NOT $b$) ] you have to pass the NOT gates backwards and apply the transformation until the NOT reaches the inputs. Basically, in this way - each NOT will duplicate itself $2^d$ times where $d$ is the depth of that NOT gate May 29 at 11:51
• I don’t think so. For every gate in the original circuit, you keep two gates, one computing the original function, and the other its negation. May 29 at 12:32

The idea is to "move backwards" all the not gate. Assume you have some circuit, for example $$(\cdot,\cdot)\rightarrow AND\rightarrow NOT\rightarrow OUTPUT$$
$$(\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)
• Im not sure I understand your proposal. I wanna increase the circuit size to 2s so that negation gates are only applied to the input. So, I thought of applying DeMorgan's laws backwards which will result in increasing the gates by 1 for example if you apply it to a conjuction or disjunction. Since the size of the circuit is $s$ that means there are $s$ gates so it follows that if this procedure needs to be applied to at most $s$ gates then the circuit size will increase by at most $s$, thus the resulting circuit can be at most of size $2s$. That's my thought process. May 28 at 7:40