第三部逻辑学在电路设计上的应用

1、第三部：邏輯學在電路設計上的應用1930年晚期，一位麻省理工學院的研究生Claude Shannon觀察到一般開關的電路設計與邏輯運算之間的共通性。他利用這個想法成功地解決了電路設計的問題。電腦的電路只包含了三件事：不（NOT）且（AND）或 （OR）我們稱它們為“閘”（Gate）。不我們考慮下面這個連一個三歲小孩也了解的敘述： 如果你哭鬧，我就不給你糖果；如果你不哭鬧，我就給你糖果。 這是一個與“不”有關的敘述，電腦會把它翻譯成：輸入（哭鬧）輸出（給糖果）如果輸入值是“真”的話（表示有哭鬧）就“不”給糖果如果輸入值“不”是“真”的話（表示沒有哭鬧）就給糖果我們以1表示命題為“真”，以0表示命

2、題為“偽”：輸入（哭鬧）輸出（給糖果）1 00 1且如果你把雞肉吃完，而且把菠菜吃光，我就給你糖果吃；否則，我就不給你糖果吃。這個敘述中含有兩個輸入值雞肉與菠菜。只有雞肉項與菠菜項的輸入值都是真的時候（也就是把雞肉和菠菜都吃光的時候），才可以得到糖果。輸入（雞肉）輸入（菠菜）輸出（糖果）111100010000或如果你穿了雨衣或是撐了雨傘，就不會淋溼；否則，你就會淋溼。它一樣有兩個輸入值雨衣和雨傘，不同的是只要其中一項的輸入值是真的，你就不會被雨淋溼。輸入（雨衣）輸入（雨傘）輸出（不會淋溼）111101011000這些就是電腦為你做的事，在它眼裡，這個世界的所有事，小至計算的值，大至讓太空梭在

3、火星上登陸，都能藉由許許多多的“不”“且”“或”而完成。人腦的思考模式就不是這麼單純了，我們不會永遠把事情單單分成“是”與“不是”，有時候，我們還會說“或許”（Maybe） 。就算我們不用“或許”這個字眼，我們還是常常說出一些語意不清的句子。今天天氣很好。這句話看起來是很明確，但是，怎樣才叫做天氣好呢？晴天？陰天？還是晴時多雲？它並沒有標準答案。我們只是憑著自己的感覺，很自然的說出這樣的話。電腦可沒辦法做這種事，所以當你要寫一個程式時，就要先替它把所有事情分成“真”(1)，與“偽”(0)才行。樓梯間的電燈開關有的時候樓梯間的電燈會設置兩個開關，一個在樓上，一個在樓下，這樣的裝置十分方便。當樓上

4、或樓下的開關只有一個是開著的，燈就會亮；但若兩個開關同時開著或關著的話，燈是不會亮的。這就是我們之前討論過的 EXOR的情形，還記得p EXOR q和 ( pq)( pq)的等價關係嗎？下圖告訴我們這個裝置如何用“不”“且”“或”三個閘來設計。現在讓我們以“1”表示開關是“開”著的，以“0”表示開關是“關”著的。為了方便起見，我們令第一個“且”的輸出結果為A，“不”的輸出結果為“A”，“或”的輸出結果為B，而第二個“且”的輸出結果就是“燈亮”。輸入（樓上）輸入（樓下）AAB輸出（燈亮）111010100111010111000100最後，若“燈亮”的輸出值是“1”，就表示燈泡會亮，果然對應著

5、“樓上”“樓下”的輸入值，一個是1一個是0的情形。加法器的電路圖在討論加法器的電路圖之前讓我們先了解一下二進位的加法。以下是十進位與二進位的數字對照表：十進位二進位十進位二進位0 0 8 1000 1 1 9 1001 2 10 10 1010 3 11 11 1011 4 100 12 1100 5 101 13 1101 6 110 14 1110 7 111 15 1111 二進位的四則運算與十進位的四則運算大同小異，唯一要注意的就是以二進位表示的數字，每位數都只能是0或1；就像以十進位表示的數，每位數只能是0, 1, 2, 8, 9其中的一個數。二進位的加法中，若遇到1 + 1的情形，

6、就該“進位”。以下是一個簡單的例子：11 + 101 = 1000 （3 + 5 = 8）進位數111+ )1010進位數1111+ )10100進位數11111+ )101000進位數11111+ )1011000假設P, Q為二進位的一位數（single binary digit），亦即0或1，那麼P + Q的可能情況有以下幾種：12 + 12 = 02 = 10212 + 02 = 12 = 01202 + 12 = 12 = 01202 + 02 = 02 = 002所以這個電路的輸出值必需有二個位元，一個是用來儲存左邊的位元（稱為“進位數”(carry)），一個是用來儲存右邊的位元（

7、稱為“和”(sum)）。“進位數”只有在P, Q都等於1的時候才會等於1，其他情況下皆為0。因此，我們可以在電路中放入一個“且”閘 ( PQ ) 來得到進位數。而當P, Q中一個是1另一個是0的時候，“和”就等於1。所以這可以用一個“EXOR”(PQ)( PQ) 得到。於是，要計算兩個一位元的二進位數P, Q的電路圖可以以下圖表示。這種電路稱為“半加法器”(half-adder)。其真偽值表如下：PQ進位數和1110100101010000讓我們再想想如何設計一個電路去計算兩個二進位數的加法（亦即這兩個數不只有一位元）。在一般情形下，相加某一位元時很可能會產生一個進位數，於是在計算下一位元（左

8、方的位元）的加法時，就變成要做三個一位元的數的加法原本的兩個數的位元，以及之前的位元（右方的位元）相加所產生的進位數。如以下這個例子：1 進位數112+ )1121102所以若要設計一個夠做兩個多位元的二進位數加法的電路，就要讓它有能力計算三個一位元的二進位數加法。這樣的電路稱為“完全加法器”(full-adder)。現在讓我們考慮三個一位元的二進位數P, Q, R相加，輸出值仍然是“進位數”與“和”，分別以C, S表示。P+ )Q+ )RCS完全加法器的運算中，每次也只取兩個數做相加，先將P, Q相加，其結果再與R相加，如以下的例子：12+ )02+ )1210212 + 12 = 1021

9、2我們可以將完全加法器看成是半加法器的組合：1. 利用半加法器將P, Q相加，得到二位元的數C1S1。P+ )QC1S12. 再拿C1S1與R相加。C1S1+ )RCS 方法如下：(a) 用半加法器做S1與R的加法，得到二位元的數C2S。此S即為總和的最右邊一位位元。S1+ )RC2S(b) 接著來算總和最左邊的一位位元C。首先，我們知道C1, C2不可能同時都是1如果C1是1，則P, Q都是1，因此 S1是0，所以C2不可能是1。既然C1, C2不可能同時為1，它們相加後就只會產生一個一位元的數C。而且，我們知道C只有當C1或C2是1的時候才會是1。PQRCS1111111010101101000101110010010010100000兩個完全加法器與一