For $x \in \{0,1\}$, let $\lnot x$ denote the negation of $x$, that is $$\lnot \, x = \begin{cases}1 & \mbox{iff } x = 0\\ 0 & \mbox{iff } x = 1\end{cases}$$.
If $x \in \{0,1\}^n$, then $\lnot \, x$ denotes the component wise negation of $x$; that is: $$(\lnot \, x)_i=\left (\lnot \, x_i \mid i \in [1..n] \right )$$
Consider a circuit $C$, computing a function $f: \{0,1\}^{n} \to \{0,1\}$ using AND $(\land)$, OR $(\lor)$,and NOT $(\lnot)$ gates. Let $D$ be the circuit obtained from $C$ by replacing each AND gate by an OR gate and replacing each OR gate by an AND. Suppose $D$ computes the function $g$. Which of the following is true for all inputs $x$?
- $g(x) = \lnot \, f(x)$
- $g(x) = f(x) \land f(\lnot x)$
- $g(x) = f(x) \lor f(\lnot x)$
- $g(x) = \lnot f(\lnot x)$
- None of the above.