1、3.3 卡 諾 圖 化 簡,邏輯函數(shù)化簡方法,代數(shù)法 圖形法（卡諾（人）圖法）,卡諾圖法形象直觀，只要熟悉一些簡單的規(guī)則，便可十分迅速地將函數(shù)化簡為最簡式。 卡諾圖法是邏輯設(shè)計(jì)中一種十分有用的工具，應(yīng)用十分廣泛，希望大家熟練掌握。,卡 諾 圖 化 簡,3.3.1 卡諾圖化簡的基本原理,在應(yīng)用吸收律1(AB+AB=A)化簡時(shí)已指出： 凡是兩邏輯相鄰項(xiàng)，可合并成一頃，其合并結(jié)果保留相同變量，消去不同變量。 邏輯相鄰的概念：兩個(gè)相同變量的邏輯項(xiàng)，只有一個(gè)變量取值不同，我們稱它為邏輯相鄰項(xiàng)。 因此，如果一個(gè)邏輯函數(shù)我們能找到它的相鄰關(guān)系，只要反復(fù)應(yīng)用吸收律1就可化簡。,例,卡 諾 圖 化 簡,例 20

2、,解,上述化簡過程十分簡單，容易掌握。 但是,有時(shí)邏輯函數(shù)的邏輯相鄰關(guān)系不是十分直觀， 比如: 各項(xiàng)變量就不相同，難于尋找相鄰關(guān)系。 為了尋找相鄰關(guān)系，我們提出邏輯函數(shù)的標(biāo)準(zhǔn)式,從標(biāo)準(zhǔn)式我們可以很快找出函數(shù)各項(xiàng)之間的相鄰關(guān)系。,在介紹邏輯函數(shù)標(biāo)準(zhǔn)式之前，先說明一下最小項(xiàng)的基本概念。 最小項(xiàng)： 對(duì)于一個(gè)給定變量數(shù)目的邏輯函數(shù)， 所有變量參加相“與”的項(xiàng)叫做最小項(xiàng)。 在一個(gè)最小項(xiàng)中， 每個(gè)變量只能以原變量或反變量出現(xiàn)一次。 例如：,3.3.2 邏輯函數(shù)的標(biāo)準(zhǔn)式最小項(xiàng),一個(gè)變量A有二個(gè)最小項(xiàng)： 二個(gè)變量AB有四個(gè)最小項(xiàng)： 三個(gè)變量ABC有八個(gè)最小項(xiàng)：,最小項(xiàng),以此類推，四個(gè)變量ABCD共有24=16

3、個(gè)最小項(xiàng)，n變量共有2n個(gè)最小項(xiàng)。,1. 最小項(xiàng)標(biāo)準(zhǔn)式定義 最小項(xiàng)標(biāo)準(zhǔn)式：全部是由最小項(xiàng)組成的“與或”式。 (當(dāng)然不一定由全部最小項(xiàng)組成)。 例如,最小項(xiàng)標(biāo)準(zhǔn)式,最小項(xiàng)標(biāo)準(zhǔn)式，它的相鄰關(guān)系一目了然，而 不屬于最小項(xiàng)標(biāo)準(zhǔn)式，而是屬于一般式。,最小項(xiàng)標(biāo)準(zhǔn)式具有唯一性。任何邏輯函數(shù)的最小項(xiàng)標(biāo)準(zhǔn)式只有一個(gè)，它和邏輯函數(shù)的真值表有著嚴(yán)格的對(duì)應(yīng)關(guān)系，而函數(shù)的一般式具有多樣性，如,顯然，上面兩等式形式不同，但它們均表示同一邏輯關(guān)系，功能是相同的。 因此，為了找出邏輯函數(shù)的邏輯相鄰關(guān)系，首先就要解決如何由函數(shù)的一般式得到最小項(xiàng)標(biāo)準(zhǔn)式。,最小項(xiàng)標(biāo)準(zhǔn)式,2. 由一般式獲得最小項(xiàng)標(biāo)準(zhǔn)式,(1) 代數(shù)法,由上式可看出

4、，第二項(xiàng)缺少變量A，第三項(xiàng)缺少變量B， 我們可以分別用 和 乘第二項(xiàng)和第三項(xiàng)， 其邏輯功能不變。,對(duì)邏輯函數(shù)的一般式采用添項(xiàng)法， 例如：,這樣我們就獲得了具有同一邏輯功能的最小項(xiàng)標(biāo)準(zhǔn)式,由一般式獲得最小項(xiàng)標(biāo)準(zhǔn)式的方法,將原邏輯函數(shù)A、B、C取不同值組合起來，得其真值表，而該邏輯函數(shù)是將F=1那些輸入變量相或而成的，如表3 - 4所示。,表 3 4 某邏輯函數(shù)的真值表,(2) 真值表法,由一般式獲得最小項(xiàng)標(biāo)準(zhǔn)式的方法,從真值表上找得到,表 3 5 三變量最小項(xiàng)的編號(hào),為了方便，可對(duì)全部最小項(xiàng)進(jìn)行編號(hào)。其編號(hào)與變量的取值組合對(duì)應(yīng)，以便從它的編號(hào)聯(lián)想到它的名稱。 當(dāng)變量取值為“0”時(shí)，它以反變量形式

5、出現(xiàn)在最小項(xiàng)中， 當(dāng)變量取值為“1”時(shí)，則以原變量的形式出現(xiàn)在最小項(xiàng)中。 這樣，變量取值組合所表示的十進(jìn)制數(shù)，就是最小項(xiàng)編號(hào)的下標(biāo)。,上式可用 m1, m5, m6, m7 表示，可寫為,F(A, B, C)=m0+m3+m4+m6 +m7,F(A, B, C)=m(0, 3，4，6, 7),F(A, B, C)=(0, 3，4，6, 7),對(duì)于任意一種取值，全體最小項(xiàng)的和為1 即,(2) 兩個(gè)不同最小項(xiàng)之積為0， 即,(3) n變量有2n個(gè)最小項(xiàng)。,3. 最小項(xiàng)的性質(zhì),由最小項(xiàng)標(biāo)準(zhǔn)式可以較方便地找出相鄰關(guān)系。但仍不直觀，且有時(shí)容易漏掉一些相鄰關(guān)系，并難于確定相鄰項(xiàng)如何合并，使化簡結(jié)果最簡。為

6、此提出了卡諾圖化簡法。 卡諾圖就是用圖形將全部最小項(xiàng)巧妙地排列而構(gòu)成的正方形或矩形的方格圖，使邏輯相鄰項(xiàng)在幾何位置上相鄰，圖中分成若干個(gè)小方格， 每個(gè)小方格填入一個(gè)最小項(xiàng)，按一定的規(guī)則把小方格中所有的最小項(xiàng)進(jìn)行合并處理，就可得到最簡的邏輯函數(shù)表達(dá)式。,3.3.3 最小項(xiàng)的卡諾圖,一變量卡諾圖：有21=2個(gè)最小項(xiàng)，因此有兩個(gè)方格。外標(biāo)的“0”表示取A的反變量，“1”表示取A的原變量。 其圖如圖3- 5(a)所示。,最小項(xiàng)卡諾圖又稱為最小項(xiàng)方格圖。對(duì)于有n個(gè)變量的邏輯函數(shù)，其最小項(xiàng)有2n個(gè)，因此該邏輯函數(shù)的卡諾圖由2n個(gè)小方格構(gòu)成。,（1）一變量的卡諾圖,一變量的卡諾圖,二變量的卡諾圖有2=4個(gè)最

7、小項(xiàng)，因此有四個(gè)方格。外標(biāo)的“0”、 “1”的含義與前一樣。其圖如圖所示。,（2）二變量的卡諾圖,二變量的卡諾圖,三變量卡諾圖有23=8個(gè)最小項(xiàng)，其卡諾圖如圖所示。,（3）三變量的卡諾圖,三變量的卡諾圖,四變量卡諾圖有24=16個(gè)最小項(xiàng)， 其卡諾圖如圖所示。,（4）四變量的卡諾圖,四變量的卡諾圖,五變量卡諾圖有25=32個(gè)最小項(xiàng)， 其卡諾圖如圖所示。,（5）五變量的卡諾圖,隨著輸入邏輯變量個(gè)數(shù)的增加，圖形變得十分復(fù)雜，所以卡諾圖一般多用于六變量以內(nèi)。,從卡諾圖上可以十分容易地找出邏輯相鄰關(guān)系。凡是幾何位置相鄰，其對(duì)應(yīng)的最小項(xiàng)均是邏輯相鄰項(xiàng)。 由于卡諾圖是平面結(jié)構(gòu)，因此在反映邏輯相鄰項(xiàng)時(shí)，除了幾

8、何位置相鄰?fù)?，還應(yīng)考慮對(duì)折原理-即上下左右的最小項(xiàng)都具有相鄰關(guān)系。,例：,3.3.4 用卡諾圖表示邏輯函數(shù),對(duì)表達(dá)式中出現(xiàn)的最小項(xiàng)，在其對(duì)應(yīng)的小方格內(nèi)填上“1”； 對(duì)表達(dá)式中不出現(xiàn)的最小項(xiàng)，在其對(duì)應(yīng)的小方格內(nèi)填上“0”或者什么都不填。,例：,具體做法 （1）若邏輯函數(shù)式是最小項(xiàng)表達(dá)式,圖 3 6 邏輯函數(shù)用卡諾圖表示,展開成最小項(xiàng)標(biāo)準(zhǔn)式，在其對(duì)應(yīng)的方格內(nèi)填上“1” 或“0”或者什么都不填。也可以直接填卡諾圖。,（2）若邏輯函數(shù)式是一般式,例：將,用卡諾圖表示。,解： 展開成最小項(xiàng)標(biāo)準(zhǔn)式,很麻煩，可以直接填卡諾圖,解： 我們逐項(xiàng)用卡諾圖表示，然后再合起來即可。 ：在B=1, C=0對(duì)應(yīng)的方格(不

9、管A，D取值)，得m4、 m5、m12、m13，在對(duì)應(yīng)位置填1； ：在C=1, D=0所對(duì)應(yīng)的方格中填1，即m2、m6、m10、m14；, 直接填卡諾圖,圖 3 7 邏輯函數(shù)直接用卡諾圖表示,： 在A=C=0, D=1對(duì)應(yīng)方格中填1，即m1、m5； 即m15。 ,：在B=0，C=D=1對(duì)應(yīng)方格中填1，即m3、m11；,ABCD：,學(xué)會(huì)了用卡諾圖表示邏輯函數(shù)，就可以用卡諾圖化簡邏輯函數(shù)了,用卡諾圖化簡邏輯函數(shù),利用卡諾圖化簡邏輯函數(shù)，其原理是利用卡諾圖各項(xiàng)的相鄰性，對(duì)相鄰最小項(xiàng)進(jìn)行合并，消去互反量，以達(dá)到化簡的目的。 2個(gè)相鄰最小項(xiàng)合并，可以消去一個(gè)變量， 4個(gè)相鄰最小項(xiàng)合并，可以消去2個(gè)變量，

10、 2n個(gè)相鄰最小項(xiàng)合并，可以消去n個(gè)變量，,(1) 兩相鄰項(xiàng)可合并為一項(xiàng)， 消去一個(gè)取值不同的變量，保留取值相同的變量； (2) 四相鄰項(xiàng)可合并為一項(xiàng)， 消去兩個(gè)取值不同的變量，保留取值相同的變量。 標(biāo)注為“1”表示原變量，“0”表示反變量； (3) 八相鄰項(xiàng)可合并為一項(xiàng)，消去三個(gè)取值不同的變量，保留取值相同的變量。 (4) 16個(gè)相鄰項(xiàng)可合并為一項(xiàng)，消去四個(gè)取值不同的變量，保留取值相同的變量。 ,3.3.5 相鄰最小項(xiàng)合并規(guī)律,注意：2n個(gè)最小項(xiàng)的相鄰項(xiàng)才可合并，不滿足2n關(guān)系的最小項(xiàng)不可合并。 如21、 22 4、 23 8、 24 16項(xiàng) 相鄰項(xiàng)可合并，3、5、6、7、9 項(xiàng) 均不能合并

11、。 而且相鄰關(guān)系應(yīng)是封閉的，如m0、m1、m3、m2四個(gè)最小項(xiàng)，m0與m1，m1與m3，m3與m2均相鄰，且m2和m0還相鄰。這樣的2n個(gè)相鄰的最小項(xiàng)可合并。,圖 3 8 相鄰最小項(xiàng)合并規(guī)律,相同變量留下，不同變量消掉,3.3.6 與或邏輯化簡,運(yùn)用最小項(xiàng)標(biāo)準(zhǔn)式， 在卡諾圖上進(jìn)行邏輯函數(shù)化簡， 得到的基本形式是與或邏輯。 其步驟如下： (1) 將原始函數(shù)用卡諾圖表示； (2) 畫卡諾圈， 圈住全部“”方格 卡諾圈有多種圈法，根據(jù)最小項(xiàng)合并規(guī)律，要注意如何使卡諾圈數(shù)目最少，同時(shí)又要盡可能地使卡諾圈大，因?yàn)樗僖粋€(gè)卡諾圈，邏輯表達(dá)式就少一項(xiàng)，組成電路就少用一個(gè)與門。 (3) 將上述全部卡諾圈的結(jié)果

12、， “或”起來即得化簡后的新函數(shù)； (4) 由邏輯門電路， 組成邏輯電路圖。,對(duì)應(yīng)m4、m5、m12、m13,圖 3-9 例22函數(shù)的卡諾圖表示,第二步： 畫卡諾圈，圈住全部“”方格。 具體化簡過程見圖：相同變量留下，不同變量消掉,圖 3 10 例22的化簡過程,第三步： 組成新函數(shù)。 每一個(gè)卡諾圈對(duì)應(yīng)一個(gè)與項(xiàng)，然后再將各與項(xiàng)“或”起來得新函數(shù)。故化簡結(jié)果為,圖 3 11 例22化簡后的邏輯圖,第四步：根據(jù)新函數(shù)，畫出 的邏輯電路。,例 23 化簡,用卡諾圖表示該邏輯函數(shù)。 畫卡諾圈，圈住全部“”方格 寫出化簡后的邏輯函數(shù)表達(dá)式 比較圖(a)、 (b)兩種圈法，顯然圖(b)圈法優(yōu)于圖(a)圈法

13、，因?yàn)樗僖粋€(gè)卡諾圈，組成電路就少用一個(gè)與門。故化簡結(jié)果應(yīng)為圖(b)，其化簡函數(shù)為,圖 3 12 例23化簡過程,解 ：,圖 3 13 例23邏輯圖, 畫 的邏輯圖,例 24 化簡,化簡方法如圖(b)、 (c)所示。圖(b)是初學(xué)者常圈成的結(jié)果，圖(c)是正確結(jié)果，即,用卡諾圖表示該邏輯函數(shù)。 畫卡諾圈，圈住全部“”方格,解 ：,寫出化簡后的邏輯函數(shù)表達(dá)式,例 25 化簡,解:, 用卡諾圖表示該邏輯函數(shù) 畫卡諾圈，圈住全部“”方格 寫出化簡后的邏輯函數(shù)表達(dá)式,此例在圈的過程中注意四個(gè)角m0、m2、m8、m10可以圈成四單元圈,圖 3 15 例25化簡過程,圖 3 15 例25邏輯圖, 畫 邏輯

14、圖,例 26 化簡, 用卡諾圖表示該邏輯函數(shù) 畫卡諾圈，圈住全部“”方格 (a)中出現(xiàn)了多余圈。m5、m7、m13、m15雖然可圈成四單元圈，但它的每一個(gè)最小項(xiàng)均被別的卡諾圈圈過，是多余圈，此時(shí)最佳結(jié)果應(yīng)如圖(b)所示。 寫出化簡后的邏輯函數(shù)表達(dá)式,解:,圖 3 16 例26化簡過程,圖 3 16 例26邏輯圖, 畫 的邏輯圖,3.3.7 其它邏輯形式的化簡,將與或式兩次求反即得與非式。 其化簡步驟如下： 第一步： 在卡諾圖上圈“”方格， 求得最簡與或式； 第二步： 將最簡與或式兩次求反， 用求反律展開一次， 得到與非表示式； 第三步： 根據(jù)與非式， 用與非門組成邏輯電路。,1. 與非邏輯形式

15、,例 27 將例2226用與非門實(shí)現(xiàn)。 解: 例22與或結(jié)果為,圖 3 17 例22用與非門實(shí)現(xiàn),例23的與非式為,圖 3 18 例23的與非邏輯圖,例24的與非式為,圖 3 18 例24的與非邏輯圖,例25的與非式為,圖 3 18 例25的與非邏輯圖,例26的與非式為,圖 3 18 例26的與非邏輯圖,方法：首先從卡諾圖上求其反函數(shù)，其方法是圈“”方格， 然后再用摩根定律取反即得或與式。,2. 或與邏輯形式,求反函數(shù)和或與式。,例 28,解：,圖 3 19 求例28的反函數(shù), 用卡諾圖表示該邏輯函數(shù) 畫卡諾圈，圈住全部“0”方格 寫出化簡后的邏輯函數(shù)表達(dá)式, 再由反函數(shù)求得原函數(shù)， 利用摩根

16、定律就得或與式。,總結(jié)如下： 在卡諾圖上圈“0”方格， 其化簡結(jié)果： 變量為“0”作為原變量；變量為“1”作為反變量，然后變量再相“或”起來，就得每一或項(xiàng)，最后再將每一或項(xiàng)“與”起來而得或與式。故此例可不通過求反函數(shù)，直接由上述過程得到或與式(如圖3 - 20所示)：,圖 3 20 從卡諾圖上直接圈得或與式, 邏輯圖,圖 3 21 例28的或與邏輯圖,將或與邏輯兩次求反即得或非表示式：,3. 或非邏輯形式,按邏輯表達(dá)式即可畫出或非邏輯電路圖，如圖3 - 22所示。,圖 3 22 例28的或與邏輯圖,一般前一種途徑所得電路要多用一個(gè)反相器，所以常用后一種方法得最簡與或非式。,4. 與或非邏輯形式

17、,與或非式可從 兩種途徑得到, 與或式兩次求反， 即得與或非式。 求得反函數(shù)后，再求一次反，可得與或非式。,圖 3 23 例22、例28的與或非邏輯圖,3.3.8 無關(guān)項(xiàng)及應(yīng)用,表 3 6 完全描述,表 3 7 非完全描述,完全描述和非完全描述真值表,也可表示為,即不允許AB或AC或BC同為1。,對(duì)于含有無關(guān)項(xiàng)邏輯函數(shù)可表示為,無關(guān)項(xiàng)用d表示,圖 3 24 不考慮無關(guān)項(xiàng)的化簡,不考慮無關(guān)項(xiàng)的邏輯函數(shù)化簡,圖 3 25 考慮無關(guān)項(xiàng)函數(shù)化,利用無關(guān)項(xiàng)的邏輯函數(shù)化簡,可見，利用無關(guān)項(xiàng)常?？梢赃M(jìn)一步化簡邏輯函數(shù)。利用無關(guān)項(xiàng)化簡邏輯函數(shù)時(shí)，只將對(duì)化簡有利的無關(guān)項(xiàng)圈進(jìn)卡諾圈，對(duì)化簡無用的項(xiàng)可以不圈。,例2

18、9 化簡,解：,圖 3 26 例29化簡, 用卡諾圖表示該邏輯函數(shù) 畫卡諾圈，圈住全部“1”方格 為了使圈盡量大，可以利用無關(guān)項(xiàng) 寫出化簡后的邏輯函數(shù)表達(dá)式,圖 3 26 例29邏輯圖, 畫 的邏輯圖,例 30 化簡,圖 3 27 例30化簡, 用卡諾圖表示該邏輯函數(shù) (無關(guān)項(xiàng)用X表示) 畫卡諾圈，圈住全部“1”方格 由于m11和m15對(duì)化簡無用，因此就沒圈。 寫出化簡后的邏輯函數(shù)表達(dá)式,解：,圖 3 27 例30邏輯圖, 畫 的邏輯圖,例 31 化簡,解 :,圖 3 28 例31化簡過程, 用卡諾圖表示該邏輯函數(shù)。 AB=0即表示A與B不能同時(shí)為1，則AB=11所對(duì)應(yīng)的最小項(xiàng)，應(yīng)視為無關(guān)項(xiàng)。

19、 畫卡諾圈，圈住全部“1”方格 m7對(duì)化簡無用，因此就不圈。 寫出化簡后的邏輯函數(shù)表達(dá)式,*3.3.9 輸入只有原變量沒有反變量的邏輯函數(shù)化簡,例 32 用最少的門電路實(shí)現(xiàn)函數(shù) 解： 實(shí)現(xiàn)該邏輯的電路如圖3 - 29所示，為了獲得反變量多用了三個(gè)非門。阻塞法主要就是解決在保證功能的前提下盡可能地少用非門。,圖 3 29 例32邏輯圖,代數(shù)法又稱為綜合反變量法。我們可以證明,1. 代數(shù)法,同理我們也能證明,這樣原式,變?yōu)?圖 3 30 例32采用綜合反變量的邏輯圖,的邏輯圖,稱為綜合反變量，它的作用與 一樣。我們稱,綜合反變量雖然在一定程度上解決了少用“非門”的問題，但當(dāng)某一項(xiàng)中有兩個(gè)或更多的非

20、號(hào)時(shí)就有一定的困難。 為此我們總結(jié)出用卡諾圖進(jìn)行化簡的方法，稱為阻塞法。,中不帶非號(hào)的部分為頭部因子，,如AB、AC、CB等，而帶非號(hào)部分稱為尾部因子。,由前面的等式證明可得出，頭部因子可以隨意放入尾部因子，也可以從尾部因子中取走，而功能不變。,我們觀察在卡諾圖中圈卡諾圈時(shí)，有一個(gè)特殊的現(xiàn)象。當(dāng)卡諾圈含有全“1”方格(三變量的111即ABC方格，四變量1111即ABCD方格)，其化簡結(jié)果均為原變量。為清楚起見，我們畫卡諾圖時(shí)將全“1”方格用黑三角標(biāo)示出來，如圖331所示。,2. 阻塞法,圖 3 31 卡諾圖上表示全1方格,如以四變量為例： 二單元圈：,m13與m15 ABD m7與m15 BC

21、D m11與m15 ACD m14與m15 ABC,m5，m7，m13，m15 BD m6，m7，m14，m15 BC m9，m11，m13，m15 AD m10，m11，m14，m15 AC m3，m7，m11，m15 CD m12，m3，m14，m15 AB,四單元圈：,八單元圈：,所以，如果在化簡時(shí)每次圈卡諾圈時(shí)均含全“”方格，則就不出現(xiàn)反變量，因此也就節(jié)省了非門。但在實(shí)際的邏輯問題中，邏輯函數(shù)不一定包含全“”方格，按常規(guī)圈法必然出現(xiàn)反變量。 例如,按常規(guī)化簡得,其電路如圖3 - 32所示。,圖 3 32 化簡過程及邏輯圖,為了獲得化簡結(jié)果為原變量，我們將m7圈進(jìn)，得C。,這結(jié)果顯然與原

22、功能不一致，因?yàn)樗鼘7也看成是“”， 而實(shí)際是“”。為此，將m7作用除掉，怎樣除掉呢?,用 與圈得的結(jié)果相與即可。證明如下：,m7項(xiàng)稱為阻塞項(xiàng)。為了保證不出反變量，阻塞項(xiàng)也應(yīng)圍繞全“”方格圈。為了保證化簡結(jié)果最佳，阻塞項(xiàng)應(yīng)盡可能圈大。,原式,圖 3 33 阻塞法化簡結(jié)果,仍以上式為例，將阻塞項(xiàng)圈為m6 、m7，阻塞項(xiàng)為,其正確性證明如下：,例 33 輸入是單軌輸入，用與非門實(shí)現(xiàn),圖中A多圈了m7，應(yīng)將其扣除，故為A ABC。BC多圈了m7應(yīng)將其扣除，故應(yīng)為BC ABC，得化簡函數(shù)為,解：,圖 3 34 例33阻塞法化簡過程及邏輯圖,例 34 輸入只有原變量，用與非門實(shí)現(xiàn), 用卡諾圖表示該邏輯函數(shù)。 畫卡諾圈，圈住全部“1”方格 將m15圈住. 寫出化簡后的邏輯函數(shù)表達(dá)式,圖 3 35 例34阻塞法化簡過程,圖