小節內容

一般常用數位電子之化簡方法可分為：(1)布爾代數化簡法(2)卡諾圖化簡法(3)列表法等三項。

小節內容. 一、布爾代數化簡法 二、卡諾圖（Karnaugh Maps）化簡 ... 第三節：數位邏輯之化簡 １.２.３.４.５.摘要.習題 　　數位邏輯化簡的目的，乃在求得減少輸入變數出現的數目，及利用數位電路實現時，使邏輯閘數目減至最小。

化簡的工作並無特殊的原則可保證得到最後的答案，唯一可用的方法，為試探的步驟，即引用熟悉的基本定理、假說以及其它方法來運算。

一般常用數位電子之化簡方法可分為：(1)布爾代數化簡法(2)卡諾圖化簡法(3)列表法等三項。

小節內容 一、布爾代數化簡法 二、卡諾圖（KarnaughMaps）化簡法表 三、列表法 一、布爾代數化簡法 　　這是利用如表4-1布爾代數的基本定理與假說來做數位邏輯化簡的方法。

【例4-5】：化簡 解： 　　 【例4-6】：化簡 解： 　　 【例4-7】：化簡 解： 　　 【例4-8】：化簡 解： 　　 【例4-9】：化簡 解： 　　 【例4-10】：化簡 解： 　　 【例4-11】：化簡 解： 　　 【例4-12】：化簡 解： 　　 二、卡諾圖（KarnaughMaps）化簡法： Top 　　卡諾圖為簡化布爾代數式的一種圖解法。

當方程式的Literal少於5或6個時，這是一種最常用的方法。

它是根據下列的布爾恆等式而來的： 　　 上述恆等式表示，如果某一變數，與它的補數有〝+〞的性質存在，則此變數可以省略。

例如：在此例中變數C與它的補數有〝+〞的關係存在，則此變數可自方程式中完全除去。

卡諾圖利用圖解技巧辨認此等變數，是一種很好的方法。

1.積之和（SOP）的化簡 　　在數位電子的應用上，常以積之和的形式出現，這裡先行討論。

　　　　　　　　　　　　 　　　　　　　　　　　　（a）真值表　　　　　　　（b）卡諾圖 　　　　　　　　　　　　　　圖4-3三變數真值表及其卡諾圖 　　用卡諾圖來表示布爾方程式和真值表很相似。

圖4-3所示者為一個三變數之卡諾圖表示法。

從圖中可以看出，相鄰的方格中，只有一個變數的值改變，此正好與格雷碼的性質相同。

　　圖4-3（a）為其真值表，圖（b）為其卡諾圖之表示。

由圖（a）中看出其函數為1之情況有二： 　　 　　而圖（b）為其對應之卡諾圖。

　　卡諾圖中任一方格內所表示變數邏輯狀態，是利用其對應的行列之標記來辨認。

由圖（b）可看出，函數為1之方程式為： 　　 　　　　　　　　　　　　 　　　　　　　　　　（a）真值表　　　　　　　　　　　（b）卡諾圖 　　　　　　　　　　　　　　圖4-4四變數真值表及其卡諾圖 　　圖4-4為四變數之卡諾圖。

在圖（b）中卡諾圖左上角之方格子，行之標示為00（表示C和D都為0）；而列之標記也為00（表示A和B都為0），因此，表示這一方格的4個變數都為0；這就是真值表中的第一列。

同理，圖中第三列與第二行交叉上的方格，表示A＝1、B＝1、C＝0、D＝1，此對應真值表中的第14列。

請注意，無論哪一行，每一進行，C、D只改變一種狀態，絕不同時改變。

同樣的，列也如此。

畫卡諾圖，註明標示時，這是必須的方法。

在圖4-4之四變數真值表中，其函數為1之情況有5種，分別表示在圖（b）卡諾圖中之對應方格中。

　　卡諾圖中，每一個為1的方格，都代表一組布爾方程式。

因此，卡諾圖可以減少項的數目；同時也可減少項中的文字符號。

文字符號的英文為Literal，意思表示為一個字或一個符號。

　　用卡諾圖簡化方程式時，如圖4-5～圖4-6所示二方法，將相鄰為1的用實線連在一起而成一群，每群代表一個蘊含項，蘊含項的英文為implicant，本意為含蓄，暗示的，包含等意思。

方程式中，蘊含項代表一項。

把一群1化成為蘊含項的方法如下： 　　(1).每一個蘊含項儘可能加大，可以包括8、4、2，或者只有一個方格。

　　(2).如圖4-6所示，蘊含項可以重疊。

　　(3).如圖4-7所示，最右邊的一行可看成和最左邊的一行相鄰；最上面的一列可看成和最下面的一列相鄰。

　　如圖4-8所示，把所有的1組成一群的方法有好幾種，可用數學的方法，選擇蘊含項數量最少的一種。

　　卡諾圖上的每一個蘊含項代表簡化後方程式的一項，書寫方程式時，這些項目係OR在一起。

　　如果在一蘊含項中，有一變數同時有真實和補數兩種型態出現，就可以在此項目中將此變數消去。

如果有一變數，在蘊含項中的各方格內，都以同樣的型態出現，就必須保留下來。

例如在圖4-5右邊蘊含項的兩方格，C為邏輯1、D為0，而A都為0則需得留下來；但是B是一格為0而另一格為1，因此B可消去，而代表此一蘊含項的就是。

而左邊四格的蘊含項為，因為A和D都有實數和其補數同時存在，所以可消去。

最後的方程式成為： 　　　　　　　　　　　　　　　 　　　　　　　圖4-5卡諾圖化簡實例之一　　　　　　圖4-6卡諾圖化簡實例之二 　　相同的，圖4-6所表示之方程式為： 　　 　　請注意，只有一格的蘊含項無法消去任何一個變數，一個兩格的蘊含項可以消去一個變數，而四格的蘊含項可以消去二個；而八格的蘊含項可以消去三個。

　　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　　圖4-7卡諾圖化簡實例之三 　　　　　　　　　　　　　　　　　　　 　　圖4-8的卡諾圖，表示出三種不同形式之化簡，其化簡後之方程式分別為： 　　 　　　　　　　 　　　　　　　　　　　　　　　　圖4-8卡諾圖化簡實例之四 　　圖4-9為一特殊的情況。

在此卡諾圖中，四格蘊含項中的每一格，同時為二格蘊含項中的一部份化簡時先考慮兩格蘊含項，再考慮四格蘊含項，若四格蘊含項都已被考慮到，因此蘊含項之BD項可以不寫出。

此簡化後之方程式為： 　　 　　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　圖4-9卡諾圖化簡實例之五 　　在圖4-10的情況下，其所需要的蘊含項為實線所圈出的和虛線中的任一個，這些是方程式所需要的項。

其所依據的法則為： 　　方程式中必須包括方格中為1的各項，但是重覆的蘊含項可以不予考慮。

其方程式可以為： 　　或 　　 　　　　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　圖4-10卡諾圖化簡實例六 綜合以上所述，卡諾圖化簡的步驟為： (1).先將真值表列出。

(2).選擇符合輸入變數個數的卡諾圖(請參考圖4-11~4-14)。

請注意，其中三變數以上狀態排列方式為00011110，而非00 011011，因為相鄰的兩個狀態只能有一位元的變化。

　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　圖4-11二變數卡諾圖 　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　圖4-12三變數卡諾圖 　　　　　　　　　　　　　　 　　　　　　　　　　　　　　圖4-13三變數卡諾圖另外一種表示方式 　　　　　　　　 　　　　　　　　　　　　　　　　　　圖4-14四變數卡諾圖 (3).將真值表填入卡諾圖中對應位置。

(4).將所有圖中的1圈選。

圈選原則： 　　(a)1的圈選可重複。

　　(b)以2的次方數(1,2,4,8…)，儘可能圈選相鄰最多的方塊。

　　(c)每次圈選均需含有未被圈選過的1，直到全部的1圈選完畢。

(5).觀察圈選方塊各變數的狀態，若有改變(0→1、1→0)，則去掉該變數(化簡)。

(6).將每個圈選的方塊依照步驟5化簡，再將化簡後的函數OR(+)起來。

【卡諾圖化簡示範】 化簡函數F=Σ(1,2,3,6,7,9,10,14) 步驟1：列出真值表 步驟2：選擇四變數的卡諾圖 步驟3：將真值表填入卡諾圖中的對應位置 步驟4：圈選所有1的部份 步驟5：化簡所圈選的方塊 步驟6：合併圈選結果(用OR(+)連接) 2.和之積（POS）之化簡 　　和之積的化簡方式和積之和的化簡方式類似，只要經過一些小修改就可得到和之積的形式。

我們以【例4-13】及【例4-14】來說明。

【例4-13】將下式化簡成和之積的形式 解： 【例4-14】將下式化簡成和之積的形式 解： 1.先求函數的補數。

　 2.將函數式填入卡諾圖中化簡，注意需要在對應到之最小項的方塊標0。

　 3.再求的補數即為答案。

　 三、列表法 Top 　　當變數不超過5個或6個時，卡諾圖是一種很簡便的方法。

但變數增加時，卡諾圖法就不是很好的簡化方法。

　　列表法最早是由Quine所發表；後來由McCluskey修正，所以又稱為Quine-McCluskey法。

　　現在就以實例說明這種列表法的化簡步驟，最後再歸納其重點。

下面將以化簡布爾代數式為例，說明列表法的化簡步驟。

步驟1： 　　將布爾代數式表示成全及項，並分組列出（如表4-2）。

分組的原則是：第0組有0個〝1〞，第1組有1個〝1〞，第2組有2個〝1〞...，依此類推。

　　　　　　　　　　　　　　　　　　表4-2列表法步驟1 　　　　　　　　　　　　 步驟2： 　　當兩乘積項作OR運算時，若相同位元的值為互補，則此位元可省略，如，由於第0組與第1組，第1組與第2組，第2組與第3組中"1"的個數都只相差1個，因此，可以以上述的方式加以化簡，如表4-2所示。

第0組的0可與第1組的1、2、4分別化簡成表4-3的項次〝0,1〞、〝0,2〞、〝0,4〞三項，以〝x〞代表被省略的位元，同時只要是被化簡過的項次，就在表4-2的使用標記欄註記。

如此，將表4-2的所有項次皆化簡過一次以後，只要是沒有註記的項次便是無法再化簡的乘積項，而這些乘積項便是最後化簡的結果。

在本例中，於表4-2的項次皆可做化簡，因此可得到表4-3的項次、內容與表4-2的使用標記狀態。

　　　　　　　　　　　　　　　　　　表4-3列表法步驟2 　　　　　　　　　　　　　　 步驟3： 　　利用表4-3，表4-4再度重複步驟2的動作，此時可得到表4-3項次"4，12"為無法化簡，故於使用標記欄註記為輸出，代表"×100"為最簡輸出的一個乘積項""。

　　　　　　　　　　　　　　　　　　表4-4列表法步驟3-1 　　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　表4-5列表法步驟3-2 　　　　　　　　　 步驟4： 　　同理，化簡表4-4後可得到表4-5與表4-4的使用標記；此時表4-5中只剩下一個乘積項，故此乘積項無法再化簡，因此註記為輸出。

步驟5： 　　將所有化簡過程中註記為輸出的項次以OR運算結合之後即為最簡式: 　　　　　　　　　　　　　　　 Top