論理回路

NANDゲートだけで、NOT・AND・ORゲートを作る

オライリーの
コンピューターシステムの理論と実装」を読んでの理解を記事にしています。

NOT

NOT x = x NAND x

x = 0

NOT x = 1
x NAND x
= 0 NAND 0
= 1

x = 1

NOT x = 0
x NAND x
= 1 NAND 1
= 0

AND

x AND y = (x NAND y) NAND (x NAND y)

x,y = 0

x AND y = 0 AND 0 = 0
(x NAND y) NAND (x NAND y)
= (0 NAND 0) NAND (0 NAND 0)
= 1 NAND 1
= 0

x = 1, y = 0

x AND y = 1 AND 0 = 0
(x NAND y) NAND (x NAND y)
= (1 NAND 0) NAND (1 NAND 0)
= 1 NAND 1
= 0

x = 0, y = 1

x AND y = 0 AND 1 = 0
(x NAND y) NAND (x NAND y)
= (0 NAND 1) NAND (0 NAND 1)
= 1 NAND 1
= 0

x,y = 1

x AND y = 1 AND 1 = 1
(x NAND y) NAND (x NAND y)
= (1 NAND 1) NAND (1 NAND 1)
= 0 NAND 0
= 1

OR

x OR y = (x NAND x) NAND (y NAND y)

x,y = 0

x OR y = (0 OR 0) = 0
(x NAND x) NAND (y NAND y) 
= (0 NAND 0) NAND (0 NAND 0)
= 1 NAND 1
= 0
= x OR y

x = 1, y = 0

x OR y = 1 OR 0 = 1
(x NAND x) NAND (y NAND y) 
= (1 NAND 1) NAND (0 NAND 0)
= 0 NAND 1
= 1

x = 0, y = 1

x OR y = 0 OR 1 = 1
(x NAND x) NAND (y NAND y) 
= (0 NAND 0) NAND (1 NAND 1)
= 1 NAND 0
= 1

x,y = 1

x OR y = 1 OR 1 = 1
(x NAND x) NAND (y NAND y) 
= (1 NAND 1) NAND (1 NAND 1)
= 0 NAND 0
= 1