From Nand to Tetris系列（二）

Chapter 2. Boolean Functions and Gate Logic

電腦使用布林值(boolean)進行運算，布林值的值域為0或1(開或關)。
常見的布林運算(Boolean Operations)包含：and/or/not。

布林表達式(Boolean Expressions)就是以布林值與布林運算組成的式子，例如：

1 AND (0 OR (NOT (1))) = 1 AND (0 OR 0) = 1 AND 0 = 0

下面是一個布林函式(Boolean Functions)的例子：

f(x, y, z) = (x AND y) OR (NOT(x) AND z)

其中等號後面的式子(formula)就是函式內容。

簡化或計算(Evaluate)函式的方法可以透過列真值表(Truth Table)，或者使用布林代數(Boolean Algebra)的一些特性，例如：布林恆等式(Boolean Identities)。

下面是幾種恆等式的定律：

1. 交換率(Commutative Laws)

   (x AND y) = (y AND x)
   (x OR y) = (y OR x)

2. 關聯(Associative Laws)

   (x AND (y AND z)) = ((x AND y) AND z)
   (x OR (y OR z)) = ((x OR y) OR z)

3. 分配律(Distributive Laws)

   (x ADN (y OR z)) = (x AND y) OR (x AND z)
   (x OR (y AND z)) = (x OR y) AND (x OR z)

4. 狄摩根定律(De Morgan Laws)

   NOT(x AND y) = NOT(x) OR NOT(y)
   NOT(x OR y) = NOT(x) AND NOT(y)

布林代數簡化的例子：

NOT(NOT(x) AND NOT(x OR y))
= NOT(NOT(x) AND (NOT(x) AND NOT(y))) // De Morgan Law
= NOT((NOT(x) AND NOT(x)) AND NOT(y)) // Associative Law
= NOT(NOT(x) AND NOT(y)) // Idempotence
= NOT(NOT(x)) OR NOT(NOT(y)) // De Morgan Law
= x OR y // Double Negation

實際上在設計邏輯電路時，我們更需要的是將真值表轉換為布林表達式。
我們會設計電路上的輸入與輸出，但如何轉換或建構(Construct)成對應的邏輯閘就是一個問題。

這邊是一個例子，假設有一張真值表：

x	y	z	f
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

我們實際上只需要關心輸出為1的部分，即：

(NOT(x) AND NOT(y) AND NOT(z))
OR
(NOT(x) AND y AND NOT(z))
OR
(x AND NOT(y) AND NOT(z))

這個式子可以簡化為：

NOT(z) AND (NOT(x) OR NOT(y))

目前沒有一個演算法可以有效的進行化簡，事實上這個問題是一個NP-Hard Problem。

一個重要的定理是：任何布林函式都可以使用AND/OR/NOT運算來表達。
因此只要使用NAND邏輯閘即可表示任何布林函式。

NOT(x) = x NAND x
x AND y = NOT(x NAND y)
x OR y = NOT(NOT(x) AND NOT(y))

邏輯閘(Logic Gate)：用來實作布林函式的硬體裝置。

電路實現(Circuit Implementations)：
如果想要也可以透過電路的方式實作邏輯閘，將AND gate類比於電路的話，就類似串連，OR gate則是並聯。

Hardware Description Language (HDL)：
我們可以用一種高階語言對邏輯閘進行描述，這種方式可以方便地進行模擬。

CHIP Xor{
	// interface
	IN a, b;
	OUT out;

	// implementation
	Not(in=a, out=nota);
	Not(in=b, out=notb);
	And(a=a, b=notb, out=aAndNotb);
	And(a=nota, b=b, out=notaAndb);
	Or(a=aAndNotb, b=notaAndb, out=out);
}

Multi-bit Buses：
可以用類似陣列的寫法來表示bus，例如：a[16]代表16個bit寬的bus。
此外支援overlap的寫法，例如：a[16], out[0..10]=a
可以透過ture/false來設定bus中所有bit為1或0。