Show that a circuit of size $s$ can be converted to a DeMorgan circuit computing the same function of size at most $2s$
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)