第三節：數位邏輯之化簡

　　數位邏輯化簡的目的，乃在求得減少輸入變數出現的數目，及利用數位電路實現時，使邏輯閘數目減至最小。化簡的工作並無特殊的原則可保證得到最後的答案，唯一可用的方法，為試探的步驟，即引用熟悉的基本定理、假說以及其它方法來運算。
一般常用數位電子之化簡方法可分為：(1)布爾代數化簡法 (2)卡諾圖化簡法(3)列表法等三項。

小節內容

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

【例4-5】：化簡

解：
　　


【例4-6】：化簡

解：
　　


【例4-7】：化簡

解：
　　


【例4-8】：化簡

解：
　　


【例4-9】：化簡

解：
　　


【例4-10】：化簡

解：
　　


【例4-11】：化簡

解：
　　


【例4-12】：化簡

解：
　　

二、卡諾圖（Karnaugh Maps）化簡法： 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)。請注意，其中三變數以上狀態排列方式為00 01 11 10，而非00 01 10 11，因為相鄰的兩個狀態只能有一位元的變化。

　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　圖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所發表；後來由Mc Cluskey修正，所以又稱為Quine-Mc Cluskey法。
　　現在就以實例說明這種列表法的化簡步驟，最後再歸納其重點。
下面將以化簡布爾代數式為例，說明列表法的化簡步驟。

步驟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運算結合之後即為最簡式: