1.4　邏輯運算

比特的一種用法是表示“冷嗎？”或“你喜歡我的帽子嗎？”等答案為是/否的問題的答案。我們用true表示是，用false表示否，像“哪里有狗狗派對？”這樣的問題不能用是/否來回答，因此不能用比特來表示。

在人類語言中，我們經常把幾個是/否分句組合成一個句子。我們可能會說，“天冷了要穿上外套，下雨了要穿上外套”或者“下雪了要去滑雪，不上學的時候要去滑雪”。另一種說法可能是“如果天冷或下雨是真的，那么穿外套是真的”和“如果下雪是真的或上學不是真的，那么滑雪是真的”。這些都是邏輯運算，每個運算都會根據其他比特的內容產生一個新的比特結果。

1.4.1　布爾代數

正如代數是一組對數字進行運算的規則，由英國數學家George Boole在19世紀提出的布爾代數，是一組對比特進行運算的規則。與普通代數一樣，結合律、交換律和分配律也適用于布爾代數。

有三個基本的布爾運算——NOT（非）、AND（與）和OR（或），以及一個復合運算——XOR（異或）（為“exclusive-or”的簡稱），四個布爾運算描述如下：

NOT：NOT運算表示“取反”。例如，如果一個比特是假的，對該比特進行NOT運算，結果為真。如果一個比特是真，那么對該比特進行NOT運算，結果為假。

AND：此運算涉及2個比特或更多的比特。在2比特運算中，只有第一個和第二個比特均為真的時候，結果才能是真。當涉及超過2個比特時，只有當所有的比特都為真時，結果才是真。

OR：OR運算也涉及2個比特或更多的比特。在2比特運算中，如果第一個或第二個比特為真，結果為真；否則，結果為假。在超過2個比特的情況下，只要有比特為真，則結果為真。

XOR：如果第一個和第二個比特具有不同的值，則異或運算的結果為真。因為“exclusive-or”拗口，我們經常使用縮寫XOR（發音為“ex-or”）。

圖1-1將這些布爾運算以圖示的形式概括為真值表。框外的表示輸入，框內的表示輸出。真值表中，T代表True，F代表False。

圖1-2展示了NOT和AND運算的工作原理。我們可以通過跟蹤輸入路徑來找到輸出。

正如你所看到的，NOT運算只是反轉輸入的狀態。此外，AND運算只有在兩個輸入都為真的情況下才會返回真。

1.4.2　德摩根定律

19世紀，英國數學家Augustus De Morgan添加了一條只適用于布爾代數的定律，即同名的德摩根定律。該定律規定，運算a AND b相當于運算NOT(NOT a OR NOT b)，如圖1-3所示。

注意，第二列中a AND b的結果與最后一列中NOT(NOT a OR NOT b)的結果完全相同。這意味著只要有足夠的NOT運算，我們就可以用OR運算代替AND運算（反之亦然）。這是有用的，因為計算機運算的是不受它控制的來自真實世界的輸入。雖然輸入的形式是“冷”或“下雨”會比較好，但實際中它們往往是“不冷”或“不下雨”。類似于英語等語言中的雙重否定句（如“we didn't not go skiing”），德摩根定律是一個工具，除了我們已經見過的正邏輯外，它還能讓我們運算這些負邏輯命題。圖1-4展示了正邏輯和負邏輯形式的穿衣決策。

在左邊（正邏輯），我們可以用一個OR運算來進行決策。在右邊（負邏輯），德摩根定律允許我們使用一個AND運算來進行決策。如果沒有德摩根定律，我們就必須將負邏輯的情況執行為“NOT不冷OR NOT不下雨”。雖然這樣做是可行的，但每一次運算都是有金錢和性能成本的，所以最小化運算量會使成本最小化。執行NOT運算的硬件會花費真金白銀，而且下一章會講到級聯運算會減慢速度。