Using induction to prove universality of gate

Question

Can we use induction to prove gate(like NAND) is universal. If so how?

Answer 1

This is what I meant by "induction on circuits." So define the "size" of a circuit as the number of gates in it. So if you have two "ANDs" and a "NOT" together, regardless of how it's put together, has size 3.

Now consider the proposition $P(n)$, which says "every (traditional) circuit of size at most $n$ has an equivalent circuit made only of NAND gates." This is what you prove by induction.

The BASE case ($n=1$) is single-gate circuits: your AND and OR and NOT and what-have-you. It's enough to do just OR and NOT (for example), since ($A$ AND $B$) is equivalent to NOT((NOT $A$) OR (NOT $B$))).

The STEP case (assume $P(n)$; prove $P(n+1)$) goes like this, and is completely standard across all arguments. Take any circuit of size $n+1$. This is formed by taking a circuit of size $n$ and adding one more gate. We can replace the original circuit with just NANDs (since $P(n)$ is true) and the new circuit with just NANDs (since $P(1)$ is true; this is our base case) and the result is a circuit which is equivalent to the original, but has only NANDs.

This is the inductive argument. So you can see the only thing that has anything to do with NAND is the base case; if you can do NOT and OR, you can do everything.

If this is still unclear let me know in a comment.