第1章邏輯代數(shù)基礎(chǔ)

第一章

邏輯代數(shù)基礎(chǔ)

（續(xù)2）1.3邏輯函數(shù)的化簡(jiǎn)掌握邏輯函數(shù)的化簡(jiǎn)方法?；緝?nèi)容和要求

1.3.1邏輯函數(shù)的不同形式與化簡(jiǎn)邏輯函數(shù)的形式多種多樣，一個(gè)邏輯問(wèn)題可以用多種形式的邏輯函數(shù)來(lái)表示，而每一種函數(shù)對(duì)應(yīng)一種邏輯電路。邏輯函數(shù)的表達(dá)形式通常有五種：與或表達(dá)式與非-與非表達(dá)式與或非表達(dá)式或與表達(dá)式或非-或非表達(dá)式

例如：與-或式與非-與非式與或非式或與式或非-或非式圖1.3.1同一邏輯的五種邏輯圖

一個(gè)邏輯函數(shù)的真值表是唯一的，但同一函數(shù)的邏輯表達(dá)式有多種形式，或繁或簡(jiǎn)。

簡(jiǎn)單的形式對(duì)應(yīng)簡(jiǎn)潔的電路，煩瑣的形式對(duì)應(yīng)復(fù)雜的電路。而在工程實(shí)踐中，總希望電路的結(jié)構(gòu)簡(jiǎn)單，用較少的邏輯器件實(shí)現(xiàn)某一邏輯功能，為此就需要對(duì)邏輯函數(shù)進(jìn)行化簡(jiǎn)或變換，以簡(jiǎn)化電路、節(jié)省器件、降低成本，提高系統(tǒng)可靠性。例如，函數(shù)：如果直接由該函數(shù)式得到電路圖，則如下圖所示。圖1.3.2F原函數(shù)的邏輯圖

但如果將此函數(shù)化簡(jiǎn)后變成:F=AC+B則只要兩個(gè)門(mén)就夠了，如下圖所示。圖1.3.3函數(shù)化簡(jiǎn)后的邏輯圖對(duì)于邏輯函數(shù)化簡(jiǎn)，并沒(méi)有一個(gè)嚴(yán)格的原則，但通常遵循以下幾條：(1)邏輯電路所用的邏輯門(mén)最少；(2)各邏輯門(mén)的輸入端要少；(3)邏輯電路所用的級(jí)數(shù)要少；(4)邏輯電路能可靠地工作?；?jiǎn)邏輯函數(shù)時(shí)一般先求最簡(jiǎn)與或表達(dá)式。如果工程上需要用其他電路形式實(shí)現(xiàn)，再利用前述轉(zhuǎn)換方法求得所需的邏輯函數(shù)表達(dá)式?；?jiǎn)邏輯函數(shù)的主要方法有公式化簡(jiǎn)法(代數(shù)法)、卡諾圖化簡(jiǎn)法以及適用于編制計(jì)算機(jī)輔助分析程序的Q-M化簡(jiǎn)法(列表法)等。本課程主要介紹前兩種化簡(jiǎn)方法。1.3.2邏輯函數(shù)的公式化簡(jiǎn)法

公式化簡(jiǎn)法就是利用邏輯代數(shù)中的公式和定理消去函數(shù)式中多余乘積項(xiàng)和多余因子，以求得函數(shù)式的最簡(jiǎn)形式。顯然，這種方法的基礎(chǔ)是熟記并靈活運(yùn)用所學(xué)邏輯代數(shù)的公式。公式化簡(jiǎn)常用方法有：1、并項(xiàng)法

并項(xiàng)法就是利用公式將兩項(xiàng)合并成一項(xiàng)，并消去一個(gè)變量。而且，根據(jù)代入規(guī)則可知，A和B均可以是任何復(fù)雜的邏輯式。例如：2、消項(xiàng)法就是利用公式：A+AB=A及消去(吸收)多余的乘積項(xiàng)。A和B同樣也可以是任何復(fù)雜的邏輯式。例如：

(根據(jù)多余項(xiàng)公式消去BD，再將展開(kāi))3、吸收法利用吸收律A+AB=A、和吸收(消去)多余的乘積項(xiàng)或多余因子。例如：4、配項(xiàng)法利用重疊律A+A=A、互補(bǔ)律A+A=1和吸收律AB+AC+BC=AB+AC先配項(xiàng)或添加多余項(xiàng)，然后再逐步化簡(jiǎn)。如：(添多余項(xiàng)AB)(去掉多余項(xiàng)AB)

作業(yè)P37、P381.131.141.3.3邏輯函數(shù)的卡諾圖化簡(jiǎn)法

卡諾圖（KarnaughMap）由美國(guó)工程師卡諾（Karnaugh）首先提出，故稱(chēng)卡諾圖，簡(jiǎn)稱(chēng)K圖。

它是一種按相鄰規(guī)則排列而成的最小項(xiàng)方格圖，利用相鄰項(xiàng)不斷合并的原則可以使邏輯函數(shù)得到化簡(jiǎn)。這種方法簡(jiǎn)便直觀，是邏輯函數(shù)化簡(jiǎn)的一種常用的比較快捷的方法，尤其適合于輸入變量小于5個(gè)的邏輯函數(shù)化簡(jiǎn)。1、卡諾圖結(jié)構(gòu)在邏輯函數(shù)真值表中，輸入變量的每一種組合都和一個(gè)最小項(xiàng)相對(duì)應(yīng)，這種真值表也稱(chēng)最小項(xiàng)真值表。

卡諾圖就是根據(jù)最小項(xiàng)真值表按一定規(guī)則排列的方格圖?？ㄖZ圖將邏輯變量分成兩組，每一組變量取值組合按循環(huán)碼規(guī)則排列，圖中的每一個(gè)小方格代表真值表上的一行。因此，真值表有多少行，卡諾圖就有多少個(gè)小方格。

卡諾圖的結(jié)構(gòu)特點(diǎn)是需要保證邏輯函數(shù)的邏輯相鄰關(guān)系，即圖上的幾何相鄰關(guān)系。為保證上述相鄰關(guān)系，每相鄰方格的變量組合之間只允許一個(gè)變量取值不同。為此，卡諾圖的變量標(biāo)注均采用循環(huán)碼。所謂循環(huán)碼，是指相鄰兩組編碼之間只有一個(gè)變量值不同的編碼。對(duì)于兩變量，4種取值組合按00→01→11→10排列。這里的相鄰包含頭、尾兩組，即00與10也相鄰。一個(gè)變量卡諾圖：有21=2個(gè)最小項(xiàng)，因此有兩個(gè)方格，如圖所示：外標(biāo)的0表示取A的反變量，1表示取A的原變量。二變量卡諾圖：有2２=4個(gè)最小項(xiàng)，因此有四個(gè)方格，如圖所示。外標(biāo)的0、1含義與前一樣。三變量卡諾圖：有23=8個(gè)最小項(xiàng)，其卡諾圖如圖所示。0BCA01132457600011110四變量卡諾圖：有24=16個(gè)最小項(xiàng)，其卡諾圖如圖所示。10ABCD013245761213151489110001111000011110五變量卡諾圖：有25=32個(gè)最小項(xiàng)，其卡諾圖如圖所示。7ABCDE0001111011001326548911101415131224252726303129281617191822232120000001011010111101100

從以上分析可以看出，卡諾圖具有如下特點(diǎn)：(1)n變量卡諾圖有2n個(gè)方格，對(duì)應(yīng)表示2n個(gè)最小項(xiàng)。每當(dāng)變量數(shù)增加一個(gè)，卡諾圖的方格數(shù)就擴(kuò)大一倍。

(2)卡諾圖中任何相鄰位置的兩個(gè)最小項(xiàng)都是相鄰項(xiàng)。即兩個(gè)最小項(xiàng)中除一個(gè)變量不同外，其他的變量都相同，這兩個(gè)最小項(xiàng)叫做邏輯上具有相鄰性。變量取值順序按格雷碼(循環(huán)碼)排列，以確保各相鄰行（列）之間只有一個(gè)變量取值不同，從而保證了卡諾圖具有這一重要特點(diǎn)。相鄰位置包括三種情況：一是相接，即緊挨著；二是相對(duì)，即任意一行或一列的兩頭；三是相重，即對(duì)折起來(lái)位置重合。卡諾圖的主要缺點(diǎn)是隨著輸入變量增加圖形迅速?gòu)?fù)雜，相鄰項(xiàng)不那么直觀。因此，卡諾圖只適于表示6個(gè)以下變量的邏輯函數(shù)。2、邏輯函數(shù)的卡諾圖表示法若邏輯函數(shù)式是最小項(xiàng)表達(dá)式，則可在相應(yīng)變量的卡諾圖中直接表示出該函數(shù)。如：在卡諾圖相應(yīng)方格中填上1，其余填0。上述函數(shù)的卡諾圖表示如下圖1.3.4所示。圖1.3.4邏輯函數(shù)用卡諾圖表示【例】用卡諾圖表示邏輯函數(shù)。如果邏輯函數(shù)不是最小項(xiàng)表達(dá)式形式，則先將邏輯函數(shù)變換成最小項(xiàng)表達(dá)式，然后再填寫(xiě)卡諾圖?？ㄖZ圖見(jiàn)下圖1.3.5?！纠坑每ㄖZ圖表示邏輯函數(shù)解：圖1.3.5上例卡諾圖如果給出的是邏輯函數(shù)真值表，只要一一對(duì)應(yīng)填入函數(shù)值即可，更加方便。實(shí)際中，一般函數(shù)式也可直接用卡諾圖表示。

例：將用卡諾圖表示。解：逐項(xiàng)用卡諾圖表示，然后再合起來(lái)即可。：在B=1,C=0對(duì)應(yīng)方格(不管A，D取值)，得m4、m5、m12、m13，在對(duì)應(yīng)位置填1；：在C=1,D=0所對(duì)應(yīng)的方格中填1，即m2、m6、m10、m14；：在B=0，C=D=1對(duì)應(yīng)方格中填1，即m3、m11；：在A=C=0,D=1對(duì)應(yīng)方格中填1，即m1、

m5；ABCD：即m15。圖1.3.5邏輯函數(shù)直接用卡諾圖表示3、相鄰最小項(xiàng)合并規(guī)律(1)兩個(gè)相鄰項(xiàng)合并為一項(xiàng)，消去一個(gè)取值不同的變量，保留相同變量；(2)四個(gè)相鄰項(xiàng)合并為一項(xiàng)，消去兩個(gè)取值不同的變量，保留相同變量；(3)八個(gè)相鄰項(xiàng)合并為一項(xiàng)，消去三個(gè)取值不同的變量，保留相同變量。2個(gè)相鄰1格合并消去一個(gè)變量

ABC01(a)1100011110ABC01(b)1100011110ABC0001111001(c)11ABCD00011110(d)1100011110ABCD00011110(e)11000111102個(gè)相鄰1格合并消去一個(gè)變量

1ABCD00011110(f)100011110(g)ABCD0001111011000111104個(gè)相鄰1格合并消去兩個(gè)變量

ABC01(b)111100011110ABC0001111001(c)1111ABCD00011110(d)111100011110ABCD00011110(e)111100011110ABC01(a)1111000111104個(gè)相鄰1格合并消去兩個(gè)變量

ABCD00011110(f)111100011110(g)1ABCD0001111011100011110

8個(gè)相鄰1格合并消去三個(gè)變量

A1BC01(a)111111100011110ABCD00011110(b)0001111011111111ABCD00011110(c)1111000111101111

8個(gè)相鄰1格合并消去三個(gè)變量

ABCD0001111000011110(d)11111111ABCDE00011110(e)11111111000001011010110111101100

按以上規(guī)律可知，16個(gè)相鄰項(xiàng)合并的規(guī)律。需要指出：合并規(guī)律是2n個(gè)最小項(xiàng)的相鄰項(xiàng)合并，不滿足2n關(guān)系的最小項(xiàng)不可合并。如2、4、8、16個(gè)相鄰項(xiàng)可合并，其它均不能合并，而且相鄰關(guān)系是封閉的，如m0、m1、m3、m2四個(gè)最小項(xiàng)，m0與m1，m1與m3，m3與m2均相鄰，且m2和m0還相鄰。這樣的2n個(gè)相鄰最小項(xiàng)可合并。而m0、m1、m3、m7，由于m0與m7不相鄰，因而這四個(gè)最小項(xiàng)不可合并為一項(xiàng)。

(4)為1的格都不能漏圈，否則，最后化簡(jiǎn)出的表達(dá)式與所給函數(shù)不相等。(5)在不違反(1)~(4)原則下，合并圈應(yīng)盡可能大，圈的個(gè)數(shù)盡可能少。圈大，消去變量多，與項(xiàng)中的變量數(shù)少；圈的個(gè)數(shù)少，與項(xiàng)個(gè)數(shù)也少，這樣有利于達(dá)到最簡(jiǎn)。下圖1.3.6和圖1.3.7是兩個(gè)例子。圖1.3.6圈的面積盡可能大

ABCD00011110111111110000001100011110(a)1ABCD0001111011111110000001100011110(b)圖1.3.7圈的個(gè)數(shù)盡可能少

ABCD00011110110101110011000000011110(a)1ABCD0001111010101110011000000011110(b)(6)允許為1的格重復(fù)圈，但每個(gè)圈至少應(yīng)包含1個(gè)新的1格?？梢灾貜?fù)圈的依據(jù)是同一律A＋A=A。但是，如果某個(gè)圈中所有1格都已被其他圈圈過(guò)，那么這個(gè)圈對(duì)應(yīng)的與項(xiàng)是多余項(xiàng)，如圖1.3.8所示。圖1.3.8每個(gè)圈至少應(yīng)包含一個(gè)新的最小項(xiàng)

ABCD00011110010001111110001000011110(a)0ABCD0001111010001111110001000011110(b)

用卡諾圖化簡(jiǎn)邏輯函數(shù)時(shí)，由于合并最小項(xiàng)方式不同，最后所得到的最簡(jiǎn)與或式也會(huì)不同。這種方法簡(jiǎn)單直觀、容易掌握。但是，如果邏輯變量個(gè)數(shù)大于5，就會(huì)因圖形復(fù)雜而失去實(shí)用意義。4、用卡諾圖化簡(jiǎn)邏輯函數(shù)的步驟運(yùn)用最小項(xiàng)標(biāo)準(zhǔn)式，在卡諾圖上進(jìn)行邏輯函數(shù)化簡(jiǎn)，得到的基本形式是與或邏輯。其步驟如下：(1)將原始函數(shù)用卡諾圖表示；(2)根據(jù)最小項(xiàng)合并規(guī)律畫(huà)卡諾圈，圈住全部為“１”的方格；(3)將全部卡諾圈的結(jié)果，“或”起來(lái)即得化簡(jiǎn)后的新函數(shù)；(4)由邏輯門(mén)電路，組成邏輯電路圖。例：化簡(jiǎn)解第一步：用卡諾圖表示該邏輯函數(shù)。

：對(duì)應(yīng)m3、m11對(duì)應(yīng)m4、m5、m12、m13對(duì)應(yīng)m1、m5對(duì)應(yīng)m10、m11本例函數(shù)的卡諾圖表示

第二步：畫(huà)卡諾圈圈住全部為“１”的方格。具體化簡(jiǎn)過(guò)程如下圖所示。為便于檢查，每個(gè)卡諾圈化簡(jiǎn)結(jié)果應(yīng)標(biāo)在卡諾圖上。圖1.3.9本例的化簡(jiǎn)過(guò)程

第三步：組成新函數(shù)。每一個(gè)卡諾圈對(duì)應(yīng)一個(gè)與項(xiàng)，然后再將各與項(xiàng)“或”起來(lái)得新函數(shù)。故化簡(jiǎn)結(jié)果為：第四步：畫(huà)出邏輯電路。邏輯電路如圖1.3.10所示。圖1.3.10本例化簡(jiǎn)后的邏輯圖例：化簡(jiǎn)

解：其卡諾圖及化簡(jiǎn)過(guò)程如圖1.3.11所示。圖1.3.11本例化簡(jiǎn)過(guò)程需要注意的是，在卡諾圈有多種圈法時(shí)，要注意如何使卡諾圈數(shù)目最少，同時(shí)又要盡可能地使卡諾圈大。比較圖(a)、(b)兩種圈法，顯然圖(b)圈法優(yōu)于圖(a)圈法，因?yàn)樗僖粋€(gè)卡諾圈，組成電路就少用一個(gè)與門(mén)。化簡(jiǎn)結(jié)果應(yīng)為圖(b)，邏輯圖如圖1.3.12所示。其化簡(jiǎn)函數(shù)為:圖1.3.12本例邏輯圖例：化簡(jiǎn)F(ABCD)

解：該函數(shù)的卡諾圖如下圖(a)所示?；?jiǎn)情況如圖(b)、(c)所示。圖(b)是初學(xué)者常圈成的結(jié)果，圖(c)是正確結(jié)果，即:這二者的差別在于圖(b)將m6和m14圈為二單元圈。圖(c)將m4、m6、m12、m14圈成四單元圈。前者化簡(jiǎn)結(jié)果為BCD，而后者為BD，少了一個(gè)變量。圖1.3.13本例的化簡(jiǎn)過(guò)程例：化簡(jiǎn)

解：其卡諾圖及化簡(jiǎn)過(guò)程如圖1.3.14(a)所示，邏輯圖如圖(b)所示?；?jiǎn)結(jié)果：

此例在圈的過(guò)程中注意四個(gè)角m0、m2、m8、m10可以圈成四單元圈。圖1.3.14本例化簡(jiǎn)過(guò)程及邏輯圖例：化簡(jiǎn)

解：化簡(jiǎn)過(guò)程如圖1.3.15(a)、(b)所示，(a)中出現(xiàn)了多余圈。m5、m7、m13、m15雖然可圈成四單元圈，但它的每一個(gè)最小項(xiàng)均被別的卡諾圈圈過(guò)，是多余圈，此時(shí)最佳結(jié)果應(yīng)如圖(b)所示。化簡(jiǎn)結(jié)果的邏輯電路圖如圖1.3.15(c)所示?；?jiǎn)結(jié)果:圖1.3.15本例化簡(jiǎn)過(guò)程及邏輯圖作業(yè)P381.151.201.3.4具有無(wú)關(guān)(約束)項(xiàng)的邏輯函數(shù)化簡(jiǎn)1、具有無(wú)關(guān)項(xiàng)的邏輯函數(shù)邏輯問(wèn)題分為完全描述和非完全描述兩種。如果對(duì)于輸入變量的每一組取值，邏輯函數(shù)都有確定的值，則稱(chēng)這類(lèi)函數(shù)為完全描述的邏輯函數(shù)。如果對(duì)于輸入變量的某些取值組合，邏輯函數(shù)值不確定，即函數(shù)值可以為0，也可以為1，那么稱(chēng)這類(lèi)函數(shù)為非完全描述的邏輯函數(shù)。對(duì)應(yīng)輸出函數(shù)值不確定的輸入最小項(xiàng)（或最大項(xiàng)）稱(chēng)為無(wú)關(guān)項(xiàng)。具有無(wú)關(guān)項(xiàng)的邏輯函數(shù)就是非完全描述的邏輯函數(shù)。

完全描述真值表ABCF00001111001100110101010100010010非完全描述真值表ABCF000011110011001101010101010×1×××在一些應(yīng)用中，存在以下兩種情況：(1)由于某種條件的限制(或約束)使得輸入變量的某些組合不會(huì)出現(xiàn)或者不允許出現(xiàn)，因而在這些取值下對(duì)應(yīng)的函數(shù)值是“無(wú)關(guān)”緊要的，它可以為1，也可以為0。(2)輸入變量的某些組合出現(xiàn)時(shí)，輸出可為任意值，即這些輸入組合所產(chǎn)生的輸出并不影響整個(gè)系統(tǒng)的功能，因此可以不必考慮輸出是0還是1。這樣的輸入組合所對(duì)應(yīng)的最小項(xiàng)稱(chēng)為無(wú)關(guān)項(xiàng)(或稱(chēng)任意項(xiàng)、約束項(xiàng)、隨意項(xiàng))。無(wú)關(guān)項(xiàng)一般用以下方法表示：(1)在真值表或卡諾圖中填Φ

或×，表示函數(shù)值既可為0也可為1。(2)在邏輯表達(dá)式中有兩種表示方法：①用∑m(…)表示F中

取值為“1”的所有最小項(xiàng)；用∑d(…)表示函數(shù)中的無(wú)關(guān)項(xiàng)。如：②用約束條件式表示無(wú)關(guān)項(xiàng)。例如，下式中AB=0是函數(shù)F的約束條件，表示必須保證A·B=0，即A和B不同時(shí)為1，因此，在卡諾圖中對(duì)應(yīng)AB為11的項(xiàng)是無(wú)關(guān)項(xiàng)。再例如，函數(shù)式AB+AC=0表示約束條件時(shí)，其含意指：在卡諾圖中，對(duì)應(yīng)AB為11的項(xiàng)內(nèi)，F(xiàn)值應(yīng)填入“×”，對(duì)應(yīng)AC為11的項(xiàng)內(nèi)，F(xiàn)值也應(yīng)填入“×”。對(duì)于含有無(wú)關(guān)項(xiàng)邏輯函數(shù)既可表示為：也可表示為：即不允許AB或AC或BC同為1。對(duì)于邏輯函數(shù)的化簡(jiǎn)，如果不考慮無(wú)關(guān)項(xiàng)，則不可再化簡(jiǎn)，如下圖所示。圖1.3.16不考慮無(wú)關(guān)項(xiàng)的化簡(jiǎn)邏輯函數(shù)結(jié)果為：

考慮無(wú)關(guān)項(xiàng)時(shí)邏輯函數(shù)化簡(jiǎn)如下圖。其結(jié)果為：F=A+C圖1.3.17考慮無(wú)關(guān)項(xiàng)函數(shù)化簡(jiǎn)2、具有無(wú)關(guān)項(xiàng)邏輯函數(shù)的化簡(jiǎn)化簡(jiǎn)包含無(wú)關(guān)項(xiàng)的邏輯函數(shù)時(shí)，應(yīng)充分、合理地利用無(wú)關(guān)項(xiàng)，使邏輯函數(shù)得到更加簡(jiǎn)單的結(jié)果?；?jiǎn)時(shí)，將卡諾圖中的×（或Φ）究竟作為1還是作為0來(lái)處理應(yīng)以卡諾圈數(shù)最少、卡諾圈最大為原則。因此，并不是所有的無(wú)關(guān)項(xiàng)都要覆蓋。例：化簡(jiǎn)解：化簡(jiǎn)過(guò)程如下圖所示。圖1.3.18本例化簡(jiǎn)及邏輯圖例：化簡(jiǎn)

解：化簡(jiǎn)過(guò)程如下圖所示，由于m11和m15對(duì)化簡(jiǎn)不利，因此就沒(méi)圈進(jìn)。圖1.3.19本例化簡(jiǎn)及邏輯圖例：化簡(jiǎn)

解：AB=0即表示A與B不能同時(shí)為1，則AB=11所對(duì)應(yīng)的最小項(xiàng)為無(wú)關(guān)項(xiàng)。其卡諾圖及化簡(jiǎn)過(guò)程如下圖所示。圖1.3.20本例化簡(jiǎn)過(guò)程作業(yè)P381.181.191.3.5多輸出邏輯函數(shù)化簡(jiǎn)多輸出函數(shù)的方框圖例：對(duì)多輸出函數(shù)進(jìn)行化簡(jiǎn)。

解：各自的卡諾圖和各自化簡(jiǎn)結(jié)果如下圖所示。圖1.3.21本例各函數(shù)獨(dú)立化簡(jiǎn)結(jié)果

如果將兩個(gè)輸出函數(shù)視為一個(gè)整體，其化簡(jiǎn)過(guò)程及結(jié)果如下圖所示。圖1.3.22