 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/digital-systems-linear-algebra-introduction-to-formal-proof/3/b/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.

Logical negation cannot be implemented, since it sends

0

1

and

1

0

, violating the defining order property. Hence these two gate types alone cannot implement every Boolean function.

 New to topics? Read the docs here!