Hogy lehet a leghatékonyabban megmutatni, hogy a NAND kapuval az összes többi logikai kapu kifejezhető?

Ha sikerul vele AND, OR es NOT kaput csinalni, meg is vagy.

[link] a 'Making other gates' fejezet.

Egy logikai kapunak két bemenete lehet, ezek értéke lehet:

0,0

1,0

0,1

1,1

, illetve mindegyik kimenet lehet 0 vagy 1. Ez összesen 2×2×2×2 = 16 féle logika. Ha azokat nem tekintjük amik mindent 1-be vagy 0-ba visznek, az 14.

A NAND és a NOR kapuk univerzálisak, azokkal a többi kifejezhető.

Ilyen kis elemszámok esetén teljesen jó bizonyítás az esetek felsorolása.

[link]

"A bemenetek és kimemetek mondjuk 0, 1 és 2."

Eddig bináris logikáról volt szó. Mikor váltottunk témát? :)

Kezd alternatív síkokra terelődni a kérdés, de az alapelv, hogy fogod a 9 sorú és 3^9 oszlopú igazságtábládat, megjelölöd rajta az a-nak (000111222) és b-nek (012012012) megfelelő oszlopot. Kiszámolod, amit a már megjelölt oszlopok között 1 NAND-szerű (legyen #) művelettel ki lehet: a#a, b#b, a#b, b#a. Bejelölöd az igazságtáblán ezt a legfeljebb 4 új oszlopot (nevezzük őket c, d, e, f-nek), és folytatod a dolgot: a#c, a#d, ... f#e, f#f. Bejelölöd az így kapott új oszlopokat. És így tovább.

Amikor megjelölsz egy új oszlopot, érdemes elmenteni, hogy melyik volt az őt előállító inputpár, hogy vissza tudd vezetni őket.

A lényeg, hogy az n. körben megkapod a legfeljebb n darab # kapuval előállítható kapukat. Ha végigérsz, és a tábla összes oszlopa be van jelölve, örülsz, hogy a # univerzális kapu a logikádban. Ha egy körben nem jelölsz be új oszlopokat, akkor vége a dalnak: az addig bejelölt oszlopoknak megfelelő kapuk előállíthatóak #-ből, a többi nem.

Igazságtáblával. Ha levezeted az AND, OR és NOT műveleteket NAND-ok kombinálásával, akkor kimutattad, hogy bármilyen AND, OR és NOT és ezek tetszőleges kombinálása leírható kizárólag NAND-dal.

Példa:

A,B,A AND B,

0,0,0

0,1,0

1,0,0

1,1,1

A,B,A NAND B, (A NAND B) NAND (A NAND B)

0,0,1,0

0,1,1,0

1,0,1,0

1,1,0,1

Ezzel kimutattuk, hogy:

A AND B = (A NAND B) NAND (A NAND B)

Hasonlóan mutatható meg, hogy

A OR B = (A NAND A) NAND (B NAND B)

Illetve:

NOT A = A NAND A

Ezekből már bármilyen logikai műveletláncra össze lehet rakni, hogy hogyan nézne ki csupa NAND-dal, csak ezt a három szabályt kell mindig alkalmazni.

Ha például van egy ilyen:

A AND B AND NOT C, akkor először be kell zárójelezni:

A AND (B AND (NOT C))

és belülről kifelé haladva kell átalakítani:

a "NOT"-ot átírva:

A AND (B AND (C NAND C))

utána meg az "AND"-okat stb..