= Solution
Every <AND gate> and <OR gate> is a <monotone Boolean function>: changing an input from zero to one while leaving all other inputs unchanged cannot change the output from one to zero. By <structural induction> over a <Boolean circuit>, a composition of these gates is also a <monotone Boolean function>. Constant inputs do not alter that conclusion.
\b[<Logical negation> cannot be implemented], since it sends $0$ to $1$ and $1$ to $0$, violating the defining order property. Hence these two gate types alone cannot implement every <Boolean function>.
Back to article page
