Can we use induction to prove gate(like NAND) is universal. If so how?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Kind of. What you want to do is figure out how to make all of the traditional gates independently (or enough as are known to be universal; e.g. NOT and OR); then "induction on circuits" says this is enough. But you don't need to see this as induction, as it gives a procedure to turn any traditional circuit into one with only NANDs in it. $\endgroup$– Richard RastCommented Sep 22, 2013 at 12:51
-
$\begingroup$ @Richard Rast Can you give any link(or name of book) where there is a formal treatment on "induction on circuits". $\endgroup$– user2179293Commented Sep 22, 2013 at 12:58
-
$\begingroup$ I knew that and,or or not can be made using NAND and this can be used to show that NAND is universal but I cant understand where induction is used. $\endgroup$– user2179293Commented Sep 22, 2013 at 12:59
-
$\begingroup$ Let me try to formalize it in a real answer. $\endgroup$– Richard RastCommented Sep 22, 2013 at 13:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
