開關(guān)函數(shù)的化簡

3SimplificationofSwitchingFunctionsGoals

代數(shù)法化簡卡諾圖法化簡意義：使用盡可能少的，單一的，標(biāo)準(zhǔn)的邏輯元件來實(shí)現(xiàn)所需的邏輯關(guān)系，從而降低成本和提高可靠性。目標(biāo)：以SOP型為例：門數(shù)最少(開關(guān)函數(shù)中項(xiàng)的個(gè)數(shù))扇入最小(開關(guān)函數(shù)的項(xiàng)中變量個(gè)數(shù))

化簡邏輯表達(dá)式的意義和目標(biāo)代數(shù)法(algebramethod)化簡并項(xiàng)法： 靈活利用AB+AB=A吸收法： 靈活利用A+AB=A；A(A+B)=A消去法： 靈活利用A+AB=A+B； A(A+B)=AB代數(shù)法(algebramethod)化簡舉例F=AC+ABC+ACD+CDF=A+CDF=A(B+C)(A+B+C)(ABC)F=A+BC代數(shù)法(algebramethod)化簡其特點(diǎn)是沒有固定的技巧；較難確認(rèn)是否已經(jīng)得到最簡結(jié)果；有時(shí)候化簡的最終結(jié)果非唯一。卡諾圖是最小項(xiàng)按一定規(guī)律排列的方格圖，每一個(gè)最小項(xiàng)占有一個(gè)小方格。因?yàn)樽钚№?xiàng)的數(shù)目與變量數(shù)有關(guān)，設(shè)變量數(shù)為n，則最小項(xiàng)的數(shù)目為2n。二個(gè)變量的卡諾圖見下圖所示。圖中第一行表示，第二行表示A；第一列表示，第二列表示B。這樣四個(gè)小方格就由四個(gè)最小項(xiàng)分別對號占有，行和列的符號相交就以最小項(xiàng)的與邏輯形式記入該方格中。卡諾圖(KarnaughMaps)(K-Map)化簡法

掌握卡諾圖的構(gòu)成特點(diǎn)，就可以從印在表格旁邊的AB、CD的“0”、“1”值直接寫出最小項(xiàng)的符號表達(dá)式。例如在四變量卡諾圖中，第四行第二列相交的小方格。

表格第四行的“AB”標(biāo)為“10”，應(yīng)記為，第二列的“CD”標(biāo)為“01”，記為，所以該小格為。牢記：最小項(xiàng)1對應(yīng)原變量，0對應(yīng)補(bǔ)變量這是三變量卡諾圖

卡諾圖為什么可以用來化簡？這與最小項(xiàng)的排列滿足鄰接關(guān)系有關(guān)。因?yàn)樵谧钚№?xiàng)相加時(shí)，相鄰兩項(xiàng)就可以提出公共項(xiàng)，從而消去一個(gè)變量。以四變量為例，m12與m13相鄰接，則m12+m13為：所以，在卡諾圖中只要將有關(guān)的最小項(xiàng)重新整合，就也可以消去一些變量，使邏輯函數(shù)得到化簡。這也就是卡諾圖化簡的原理相鄰與化簡的關(guān)系卡諾圖是按相鄰關(guān)系構(gòu)建的，在幾何位置上相鄰的小格稱為物理相鄰，物理相鄰的一定邏輯相鄰(四變量以下的卡諾圖)。同時(shí)，第一行和第四行也是邏輯相鄰的；第一列和第四列也是邏輯相鄰的；四個(gè)角也是邏輯相鄰的。ABDABCBCD相鄰與化簡的關(guān)系其特點(diǎn)是：任何相鄰的兩個(gè)數(shù)值只有1位發(fā)生了變化。如：00—>01—>11—>10?想一想卡諾圖為了保持在物理上相鄰的空間其邏輯上也一定相鄰，K-Map的坐標(biāo)有什么特點(diǎn)？并且還有10—>00，這更進(jìn)一步說明了首尾也是邏輯相鄰的。相鄰與化簡的關(guān)系卡諾圖的便利僅對于簡單的邏輯表達(dá)式有效，因?yàn)樗鼩w根結(jié)底是利用了平面上人的思維能力對判斷變量相鄰關(guān)系具有敏感性這一特質(zhì)。一般卡諾圖適用于6變量以下的邏輯表達(dá)式化簡。?想一想卡諾圖化簡邏輯表達(dá)式的能力有多強(qiáng)？思考卡諾圖和真值表都等價(jià)于邏輯表達(dá)式，如果把真值表看成線性的，那卡諾圖可謂是平面上的真值表。

例如，將邏輯式填入卡諾圖。它為一個(gè)三變量的邏輯式，結(jié)果見下圖。1，與項(xiàng)是最小項(xiàng)的形式與項(xiàng)是最小項(xiàng)時(shí)，按最小項(xiàng)編號的位置直接填入。卡諾圖的填充：SOP形式的填入mi與項(xiàng)不是最小項(xiàng)的形式，按鄰接關(guān)系直接填入卡諾圖。例如2，與項(xiàng)不是最小項(xiàng)的形式先填,這是CD;這是

A,再填,這是AB，這是D。

所以處于第一第二行和第三列的交點(diǎn)上（二行一列）。

所以ABD處于第三行和第二、第三列的交點(diǎn)上（一行二列）。例：將邏輯式P=+

填入卡諾圖先填，這是B，這是；這一與項(xiàng)處于第二、第三行和第一、第二列的交點(diǎn)處（二行二列）。再填，這是，這是。這一與項(xiàng)處于第一、第四行和第一、第四列的交點(diǎn)處（二行二列）。例：將邏輯式填入卡諾圖CBBCABDABD填填

例：將邏輯式F=CD,F=D填入卡諾圖CDD

由上述各例題可以看出，與項(xiàng)中變量數(shù)越少，在卡諾圖中占的小格越多；

最小項(xiàng)在卡諾圖中占1個(gè)小格；與最小項(xiàng)相比，少一個(gè)變量占二個(gè)小格；少二個(gè)變量占四個(gè)小格；少三個(gè)變量占八個(gè)小格，…。

卡諾圖中的與項(xiàng)對應(yīng)的小格，只能一個(gè)一組；二個(gè)一組；四個(gè)一組；八個(gè)一組，…，即按2i

的規(guī)律組成矩形帶。i為缺少的變量數(shù)。以四變量為例，與項(xiàng)只有一個(gè)變量，即缺3個(gè)變量，應(yīng)占23個(gè)小格，且組成一個(gè)矩形帶；與項(xiàng)只有二個(gè)變量，即缺2個(gè)變量，應(yīng)占22個(gè)小格，且組成一個(gè)矩形帶；與項(xiàng)只有三個(gè)變量，即缺1個(gè)變量，應(yīng)占21個(gè)小格，且組成一個(gè)矩形帶。我們的任務(wù)是化簡邏輯函數(shù)，將SOP型邏輯函數(shù)填入卡諾圖后，這樣原來的邏輯函數(shù)就以最小項(xiàng)的面貌出現(xiàn)在卡諾圖中。然后，經(jīng)過重新整合，將具有“1”的小格按照2i的規(guī)律盡可能大地圈成矩形帶。這樣新得到的邏輯函數(shù)在形式上就會更簡單些。下面我們來討論如何用卡諾圖進(jìn)行化簡。也就是如何重新組合帶有“1”的小格，如何盡可能大地圈成矩形帶，以得到最簡SOP邏輯式?？偨Y(jié)

由前面的討論可知，卡諾圖中的矩形帶包括的小格越多，對應(yīng)的與項(xiàng)的變量數(shù)就越少。所以一個(gè)需要化簡的邏輯函數(shù)，填入卡諾圖后，經(jīng)過重新整合，圈出的矩形帶應(yīng)越大越好。

該邏輯式是否最簡？顯然不是最簡形式，因?yàn)?/p>

顯然對應(yīng)下面四個(gè)小格；對應(yīng)上面四個(gè)小格，中間二個(gè)小格被覆蓋，屬于公共享有。所以，為使與項(xiàng)最簡，圈矩形帶時(shí)，小格可以公用，互相覆蓋。例如左圖若把上面兩個(gè)小方格圈在一起有，下面四個(gè)小方格圈在一起有，于是邏輯式為：卡諾圖化簡步驟關(guān)于覆蓋

但是在小格覆蓋時(shí)，需要注意，每一個(gè)矩形帶中至少要有一個(gè)小格是獨(dú)立的，即沒有被其他矩形帶所覆蓋。例如下圖中，四個(gè)矩形帶對應(yīng)的與項(xiàng)分別是中間的四個(gè)小格圈成的矩形帶對應(yīng)的與項(xiàng)BD雖然最簡，但BD對應(yīng)的四個(gè)小格一一被其他四個(gè)矩形帶所覆蓋，所以就應(yīng)從最簡SOP式中取消，最簡SOP式為總之，一個(gè)矩形帶中的所有小格最少要有一個(gè)未被覆蓋，這個(gè)矩形帶所代表的與項(xiàng)才是化簡后的SOP型邏輯式中不可缺少的項(xiàng)。反之，一個(gè)矩形帶中的所有小格都被其它矩形帶所覆蓋，那么這個(gè)矩形帶所代表的與項(xiàng)就不是獨(dú)立的，如果寫入SOP型邏輯式中就是多余的。

卡諾圖化簡法的步驟如下：邏輯式填入卡諾圖，如果邏輯式不是SOP型，先將邏輯式轉(zhuǎn)換為SOP型。照最小的原則，盡可能將矩形帶圈大一些。選出至少有一個(gè)小格是獨(dú)立的矩形帶，寫出它們所對應(yīng)的最簡與項(xiàng)的邏輯和。如有遺漏，添上遺漏小格所對應(yīng)的一個(gè)最簡與項(xiàng)，它們的邏輯和就是最簡化的SOP型邏輯式。例:化簡化簡結(jié)果!小提示寫法差異并不影響結(jié)果正確性，只是習(xí)慣問題VS!小提示3變量編號習(xí)慣的不同決定了相鄰關(guān)系也不同其編號特點(diǎn)符合格雷碼；左4列和右4列關(guān)于中心成軸對稱。因而相鄰關(guān)系也呈軸對稱。BC’DEB’CD’!小提示3變量編號習(xí)慣的不同決定了相鄰關(guān)系也不同其編號特點(diǎn)不符合格雷碼；左4列和右4列成順子。因而相鄰關(guān)系也呈順子。B’CD’BC’DE!小提示最簡的表達(dá)式形式不一定是唯一的，這就意味著卡諾圖的圈法不一定是唯一的vs對POS類型邏輯表達(dá)式的化簡方法(擇1即可）：用真值表法填出所有的1項(xiàng)，然后用前面學(xué)到的方法化簡。這個(gè)方法適用于任何形式之表達(dá)式。根據(jù)M和m下標(biāo)互補(bǔ)的關(guān)系填出所有的“1”項(xiàng)。填出所有的“0”項(xiàng)，用整合“1”類似的方法整合“0”，得到最簡的POS形式。ABCD000111100001111000000000(A+B+C)(A+B+D)(A+B+D)(A+C+D)F(A,B,C,D)=∏M(0,1,5,7,8,10,11,15)POS類型邏輯表達(dá)式化簡舉例POS類型邏輯表達(dá)式化簡舉例將F(A,B,C,D)=ΠM(0,1,2,3,6,9,14)化為最簡的POS形式。注意：對于POS有：原變量用“0”表示，補(bǔ)(反、非)變量用“1”表示。!小提示答案：F=(A+B)(B+C+D)(B+C+D)SOP類型邏輯表達(dá)式化簡舉例技巧：不管是“0”也好，“1”也好。如果沒有明確要求，我們選擇容易圈的。將F(A,B,C,D)=AC+AD+BC+BD化為你喜歡的最簡形式。答案：F=（A+B)(C+D)課堂練習(xí)寫出下列函數(shù)的反演式和右式的對偶表達(dá)式F=AC+BCDF=AB+BC+AC+DF=A(B+(CD+EF)G)課堂練習(xí)用K-Map化簡下列函數(shù)為最簡SOP或最簡POS的形式。F(A,B,C)=(A+B)(AB+C)F(A,B,C,D)=AB+ACD+AC+BCF(A,B,C,D)=BC+D+D(B+C)(AD+B)IncompletelySpecifiedFunctions（非完全確定函數(shù)）非完全確定函數(shù)是指：真值表或者卡諾圖中的若干項(xiàng)函數(shù)值為“0”為“1”不確定，或不重要。非完全確定函數(shù)的化簡方式是：一切為了簡化，不確定項(xiàng)可以看作“0”或“1”。當(dāng)該非確定項(xiàng)能使函數(shù)簡化時(shí)，則取之；當(dāng)該非確定項(xiàng)不能使函數(shù)簡化時(shí)，則不取之。非完全確定函數(shù)舉例1d1d1ABC0001111001可見：根據(jù)畫圈化簡的需要：我們需要d6為0，需要d7為1。?想一想非完全確定函數(shù)一般出現(xiàn)在哪些實(shí)際場合？思考一般而言：是n元輸入變量并非都具有物理意義的場合。比如：輸入為4元變量表示的ABCD，輸出F的規(guī)則為：當(dāng)ABCD表示的