Why is NAND primitive?

[Andreas]

Hi,

In the book, NAND is taken to be a primitive gate because all gates can be derived from it. As an exercise we utilise NAND's logic to create a NOT gate. However, a NAND gate is built with a NOT gate, so why build a NOT gate with a NAND gate?

Thanks.

[cadet1620]

One could choose AND and NOT as the primitive operators, but then you have two primitive operators which is not as elegant as having a single primitive operator.  NOR can also be used as the single primitive operator, but NAND is more common, in part because of the huge success of the 7400 series of logic ICs in the 60's - 80's.  These were made using TTL, a type of logic in which the NAND gate is the simplest gate to build (least number of transistors).  I learned NAND gate circuit synthesis in university in the 70's.  NOR gate synthesis probably got one lecture.

The reduction to a single primitive function in this system is instructive and still useful.  That is not always the case.  It is possible to build a One Instruction Computer but I sure wouldn't want to program it!

--Mark

[davidk01]

There is no theorem that says NAND is the way to go. NOR could have been used just as well and you could even use some other weird combination of AND, OR, NOT. The only important part is having the ability to flip a 0 to 1 and a 1 to 0 plus the ability to combine two bits in some non-trivial fashion.