數(shù)字邏輯與數(shù)字電路2

1、數(shù)字邏輯與數(shù)字電路數(shù)字邏輯與數(shù)字電路作者：徐曉光 l 邏輯函數(shù)的化簡、優(yōu)化是一個具有重大實際意義的問題，其應(yīng)用十分廣泛。例如：數(shù)字電子電路的優(yōu)化、可編程邏輯器件的設(shè)計、IP路由表化簡等，都涉及到邏輯函數(shù)的化簡問題。因此，長期以來人們對邏輯函數(shù)的化簡問題進(jìn)行了深入系統(tǒng)的研究，得到了許多卓有成效的研究成果，產(chǎn)生了許多成熟有效的邏輯函數(shù)化簡方法；如卡諾圖法、 Q-M法、銳積法等。l 近年來，隨著電子計算機(jī)的普及和應(yīng)用，使得邏輯函數(shù)的化簡問題可以在計算機(jī)的幫助下得以進(jìn)行。計算機(jī)已經(jīng)成為解決邏輯函數(shù)化簡優(yōu)化問題、進(jìn)行數(shù)字邏輯分析和設(shè)計的有力工具。l 下面我們將對邏輯化簡的理論和方法進(jìn)行詳細(xì)的介紹。2.1

2、 l 2.1.1 有關(guān)的專業(yè)術(shù)語l 1.（Sum Of Products）l 我們將表示為乘積項乘積項之和和形式的邏輯表達(dá)式稱作積之和積之和（SOP）。 如：f(A,B,C)=ABC+AC+BCl 2.（Product Of Sums）l 我們將表示為和項和項之乘積乘積形式的邏輯表達(dá)式稱作和之積和之積（POS）。 如：(A,B,C)= f(A,B,C)=(A+B+C)(A+C)(B+C)乘積項的和的形式乘積項的和的形式和項的乘積的形式和項的乘積的形式l 3.最小項l 所謂是由邏輯表達(dá)式中所有輸入變量字母組成的乘積項，每一個字母至多出現(xiàn)一次。 如邏輯函數(shù)為 f(A,B,C,D) ，則ABCD，A

3、BCD等都是最小項。l 4.最大項l 所謂是由邏輯表達(dá)式中所有輸入變量字母組成的和項，每一個字母至多出現(xiàn)一次。l 如邏輯函數(shù)為f(A,B,C,D)，則A+B+C+D， A+B+C+D都是最大項。：任何一個邏輯表達(dá)式都可以表示為最小項之和的形式，或者表示為最大項之積的形式。l 例如： f(A,B,C,D)(SOP)=ABC+AC+BC =ABC(D+D)+A(B+B)C(D+D)+(A+A)BC(D+D) =ABCD+ABCD+ABCD+ABCD+ABCD+ABCD +ABCD+ABCD+ABCD+ABCD l 再者： f(A,B,C,D)(POS)=(ABC+AC+BC) =(A+B+C+D)

4、(A+B+C+D)(A+B+C+D)(A+B+C+D) (A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D) (A+B+C+D)(A+B+C+D)l 5.關(guān)于最小項和最大項的討論l （1）我們將邏輯函數(shù)的最小項，用mi的形式來表示。其中下標(biāo)i是區(qū)分、表征最小項的10進(jìn)制數(shù)字，我們將某一個最小項按字母順序從左到右排列，將取的取值 、將取的取值 ，這樣就可以得到一個表征該最小項的二進(jìn)制數(shù)。如果將該最小項中的各個字母按這個二進(jìn)制數(shù)取值代入，該最小項恰好取值為1。最后把這個二進(jìn)制數(shù)轉(zhuǎn)換成相應(yīng)的十進(jìn)制數(shù)，就是i的值。l 例如ABCD= m15 ，ABCD= m10 等。l （2）我們

5、將邏輯函數(shù)的最大項，用Mi的形式來表示。其中下標(biāo)i是區(qū)分、表征最大項的10進(jìn)制數(shù)字，我們將某一個最大項按字母順序從左到右排列，將取的取值 、將取的取值 ，這樣就可以得到一個表征該最大項的二進(jìn)制數(shù)。如果將該最大項中的各個字母按這個二進(jìn)制數(shù)取值代入，該最大項恰好取值為0。最后把這個二進(jìn)制數(shù)轉(zhuǎn)換成相應(yīng)的十進(jìn)制數(shù)，就是i的值。l 例如A+B+C+D= M0 ， A+B+C+D= M5 等。l （3）根據(jù)最小項和最大項的定義、狄.摩根定律，有： Mi= (mi )(以POS形式表示)，mi = (Mi) (以SOP形式表示) l （3）定理1 一個邏輯表達(dá)式中所有最小項之和恒為1。(含有n個字母的邏輯表

6、達(dá)式中共有2n 個最小項) 即 (2-1)l n為邏輯表達(dá)式中所含字母的個數(shù)。l （4）定理2 一個邏輯表達(dá)式中所有最大項之積恒為0。(含有n個字母的邏輯表達(dá)式中共有2n 個最大項) 即 (2-2)l n為邏輯表達(dá)式中所含字母的個數(shù)。2101nkkm2100nkkMl （5）將任一個邏輯表達(dá)式表示成“積之和”形式的方法，就是把邏輯函數(shù)所包含的最小項找出來，相加即可。l 具體的方法可以按使邏輯表達(dá)式取值為1的原則，將對應(yīng)最小項的二進(jìn)制數(shù)找出來，得到該邏輯函數(shù)中所包含的最小項。l 因此，一個邏輯表達(dá)式也可以用f(A,B,C)=mi 來表示，如： f(A,B,C)=m0+ m3 + m5 + m6

7、等。l （6）將任一個邏輯表達(dá)式表示成“和之積”形式的方法，就是把邏輯函數(shù)所包含的最大項找出來，相乘即可。l 具體的方法可以按使邏輯表達(dá)式取值為0的原則，將對應(yīng)最大項的二進(jìn)制數(shù)找出來，得到該邏輯函數(shù)中所包含的最大項。l 因此，一個邏輯表達(dá)式也可以用 f(A,B,C)=Mj來表示，如： f(A,B,C)=M0 M3 M5 M10等。l (7)另外根據(jù)定理1，我們得到： 即mi +mj= 1 （2-3）l 式中i為邏輯表達(dá)式中最小項的下標(biāo)，j為所有下標(biāo)中除最小項之外其余的下標(biāo)。l 由邏輯代數(shù)運算的公式（1-21）可知， mj= (mi) （2-4）l 再由f(A,B,C)=mi =Mj ，得：Mj

8、 =(mi)。 由式（2-4）得：Mj= (mj) = mj ， 也即Mj = mj 。l 因此有結(jié)論如下：。1120nkkjimmml 例1： f(A,B,C)(SOP)= ABC+AC+BC =ABCD+ABCD+ABCD+ABCD+ABCD +ABCD+ABCD+ABCD+ABCD+ABCD =m15+ m14 + m7 + m6 + m3 + m2 + m13 + m12 + m5 + m4 l 則同時有： f(A,B,C)(POS)=M0M1M8M9M10M11 =(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D) (A+B+C+D) (A+B+C+D) 例2：

9、 Y =m(1,5,7,8,12,15) =M(0,2,3,4,6,9,10,11,13,14) 是一個表示邏輯函數(shù)的表格。將輸入變量橫向與縱向排列，便可畫出表格，如右圖所示。l 三、四變量卡諾圖中輸入變量橫向與縱向排列的規(guī)律，是相鄰兩行（列）之間僅有一個變量的取值不同。2.1.2 ABC00 01 11 10010 1 3 24 5 7 6十進(jìn)制數(shù)值a) 3變量的卡諾圖ABCD00 01 11 1000011110b) 4變量的卡諾圖0 1 3 24 5 7 612 13 15 148 9 11 10十進(jìn)制數(shù)值l 表格中的每一個小格子，對應(yīng)于一個最小項或最大項。l 根據(jù)邏輯表達(dá)式，將各個格子

10、填入數(shù)值：對于SOP形式的表達(dá)式，若包含該最小項，則在相應(yīng)格子中填入“1”；若不包含該最小項，就填入“0”（或者空白也可）。l 或者對于POS形式的表達(dá)式，若包含該最大項，則在相應(yīng)格子中填入“0” （或者空白也可）；若不包含該最大項，就填入“1”。l 這樣就得到了表示該邏輯函數(shù)的卡諾圖。l 例如Y=ABC+AC+BCD的卡諾圖如圖2-2所示。圖2-2 卡諾圖的填寫CDAB00 01 11 100001 11100 1 3 24 5 7 68 9 11 1012 13 15 140 1 1 10 0 1 10 0 1 10 1 0 0Y=ABC+AC+BCDl 1.合并最小項（最大項）的規(guī)律l

11、由于三、四變量卡諾圖中相鄰兩行（列）之間僅有一個變量 的 取 值 不 同 ， 根 據(jù) 邏 輯 代 數(shù) 的 公 式 A + A = 1 、AB+AC=A(B+C)和AA=0、(A+B)(A+C)=A+BC知：卡諾圖中橫向或縱向的最小項或最大項可以合并成一項。進(jìn)而，卡諾圖中的的或小方塊可以合并成一項。l 為了看清楚最小項（最大項）之間的合并關(guān)系，我們將能夠合并成一項的小方塊圈在一個圈內(nèi)。l 2.1.3 l 應(yīng)當(dāng)注意：處于一行（列）的兩端時，相當(dāng)于相鄰。排成一行（列）的四個小方塊等價于相鄰的大方塊。l 上述情形如圖2-3、2-4和2-5所示。圖2-5 八個最小項的合并l 2.l （1）（Implic

12、ant）l 在邏輯函數(shù)中，如果若干個最小項（最大項）能夠合并成一項，則稱這些最小項（最大項）構(gòu)成了一個。如：卡諾圖中任意2個相鄰的最小項、任意相鄰的4個最小項、任意相鄰的8個最小項等。l 最小項（最大項）本身也是一個蘊涵，它是最小的蘊涵。l （2）蘊涵的關(guān)系l 在邏輯函數(shù)中，根據(jù)邏輯代數(shù)的吸收律，如果一個蘊涵X能夠被另一個蘊涵Y所吸收掉，則稱“蘊涵X于蘊涵Y”。l 如：ABCD和ABCD 皆包含于AD 中。l 在卡諾圖中，如果蘊涵X包含于蘊涵Y，則蘊涵X的方塊就被包含于蘊涵Y的方塊之中，如圖2-6所示。l 在一個邏輯函數(shù)中，如果某個蘊涵是不能被其它任何蘊涵所包含的，則稱該蘊涵為，簡稱PI。l

13、例如在圖2-7中，存在4個蘊涵：ABCD、ABCD、ABCD和BCD，以及2個質(zhì)蘊涵：BCD 和 ABCD 。l （3）（Prime Implicant）l 例如在下圖中，存在5個質(zhì)蘊涵：ABC、ACD、ABC、ACD和BD，但僅有4個必要質(zhì)蘊涵：ABC、ACD、ABC和ACD。組成質(zhì)蘊涵 BD的4個最小項，全部被其它的PI所包含，故它不是EPI。l（4）（Essential Prime Implicant）l在一個邏輯函數(shù)中，如果某個質(zhì)蘊涵（PI）中包含有至少一個其它質(zhì)蘊涵所不包含的最小項（最大項），則稱該質(zhì)蘊涵為，簡稱EPI。l 3.3.（Dont care terms）l 這種情況下，在

14、對邏輯函數(shù)進(jìn)行化簡時，那些在實際問題中根本不會出現(xiàn)的輸入狀態(tài)（也即最小項或最大項），就被稱作（有些書上稱作）。l 在實際問題中，經(jīng)常會遇到這樣一類情況：邏輯函數(shù)的某些特定的輸入狀態(tài)，是肯定不會出現(xiàn)的?；蛘哒f為邏輯函數(shù)的化簡，加上了某種。l 我們在卡諾圖對應(yīng)隨意項的小方格中，填入“x”。其意義是既可以取值“1”，也可以取值“0”。l 在用卡諾圖化簡邏輯函數(shù)時，隨意項既可以以“1”參與化簡，也可以以“0”參與化簡。這是由于這些最小項（最大項）是在實際問題中根本不會出現(xiàn)的，所以它們無論取“0”還是取“1”都不會對原問題造成影響。l 究竟隨意項取“1”還是取“0”，是以實現(xiàn)邏輯化簡結(jié)果的最優(yōu)化來決定的

15、。l 圖2-9是考慮隨意項時，邏輯函數(shù)化簡的兩個實例。l 隨意項在函數(shù)中一般用di表示，例如某一帶有隨意項的邏輯函數(shù)表示為： f=(m1+m2+m7+m10)+(d5+ d6+d15)=m(1,2,7,10)+ d(5,6,15)l 4.邏輯函數(shù)化簡的目標(biāo)l 用邏輯門電路實現(xiàn)某一邏輯函數(shù)時，經(jīng)常是采用“與非門”電路來實現(xiàn)的。通過分析可知，對于SOP形式的邏輯表達(dá)式，可以用2級與非門電路完成其邏輯功能。l 例如：Y=ABC+ABD+BCD=(ABC+ABD+BCD) =(ABC)(ABD)(BCD)l 目前，用2級門電路來實現(xiàn)一個邏輯函數(shù)仍然是最為常用的邏輯設(shè)計方法。l 由于本書僅局限于用2級邏

16、輯門電路來實現(xiàn)邏輯功能，不討論用多級門電路實現(xiàn)的邏輯電路的化簡問題；因此邏輯函數(shù)化簡的目標(biāo)就是：l （1）化簡結(jié)果所得SOP形式的邏輯表達(dá)式中的乘積式項數(shù)越少越好。（2）在乘積式項數(shù)相同的情況下，各項所包含的字母數(shù)目越少越好。l 對于POS形式的邏輯表達(dá)式，情況與此類似。l 例如：ABC+ABD+ACD的化簡結(jié)果，就優(yōu)于 ABD+ACD+BCD+ABCD的化簡結(jié)果。l 5. 利用卡諾圖手工地化簡邏輯表達(dá)式，有著以下幾種方法：l （1）卡諾圖化簡算法1 從卡諾圖的質(zhì)蘊涵中，首先選取其中最大的合并項（即卡諾圖中最大的圈）。 從未被選取質(zhì)蘊涵中，選取最大的合并項（即卡諾圖中最大的圈）。但要遵循如下的

17、原則：選取的質(zhì)蘊涵，必須包含至少一個未被已經(jīng)選取質(zhì)蘊涵用過的新的最小項（最大項）。 重復(fù)步驟，直到卡諾圖中的全部最小項（最大項）已經(jīng)被選取的質(zhì)蘊涵所用過。也即選取的質(zhì)蘊涵完成了對邏輯函數(shù)的一個。 對選取的質(zhì)蘊涵進(jìn)一步分析，去除冗余的項。盡量使化簡結(jié)果最簡最優(yōu)。l （2）卡諾圖化簡算法2 在卡諾圖中首先選取出所有的。因為必要質(zhì)蘊涵覆蓋了至少一個其它質(zhì)蘊涵無法覆蓋的最小項（最大項），所以它們不可能由其它質(zhì)蘊涵來替代；即必要質(zhì)蘊涵是邏輯化簡時必須選取的。 對于剩余的非必要質(zhì)蘊涵，則應(yīng)當(dāng)采用嘗試嘗試、搜索搜索的方法，從中選出一些PI，完成邏輯函數(shù)的，達(dá)到最優(yōu)化簡的目的。l 顯然，卡諾圖化簡算法2與卡諾

18、圖化簡算法1相比，是一種十分嚴(yán)謹(jǐn)?shù)鼮閺?fù)雜的算法。l 如果將卡諾圖化簡算法2與卡諾圖化簡算法1相結(jié)合，就得到卡諾圖化簡的算法3。l （3）卡諾圖化簡算法3 在卡諾圖中首先選取出所有的。 對于剩余的非必要質(zhì)蘊涵，選取對應(yīng)（即卡諾圖中最大的圈）的質(zhì)蘊涵。但要遵循如下的原則：選取的質(zhì)蘊涵，必須包含至少一個未被已經(jīng)選取質(zhì)蘊涵用過的新的最小項（最大項）。 重復(fù)步驟，直到卡諾圖中的全部最小項（最大項）已經(jīng)被選取的質(zhì)蘊涵所用過。也即選取的質(zhì)蘊涵完成了對邏輯函數(shù)的一個覆蓋。 對選取的質(zhì)蘊涵進(jìn)一步分析，去除冗余的項。盡量使化簡結(jié)果最簡最優(yōu)。l 卡諾圖化簡算法3雖然沒有第2種方法嚴(yán)謹(jǐn)，但操作起來更為簡練。l 例2

19、-1用卡諾圖化簡邏輯表達(dá)式 f(A,B,C,D)=ABCD+ ABCD +ABCD +BCl 解：畫出4變量的卡諾圖，填入真值為1的最小項，合并化簡如圖2-10所示。l 化簡結(jié)果為：f(A,B,C,D)=ABCD+ ABD +BCl 例2-2用卡諾圖化簡邏輯表達(dá)式 f(A,B,C,D)=ABC+ ABCD +ABCD +ABCD+ADl 解：卡諾圖化簡結(jié)果如圖2-11a所示。可以看出，2-11b中四個小方塊的合并項是冗余的。l 例2-3用卡諾圖化簡邏輯函數(shù) (A,B,C,D)=m(1,2,3,4,5,6,8,9,11,12,13,14,15,)l 解：化簡結(jié)果如圖2-12所示： f(A,B,C

20、,D)=AC+BD+CD+AD+ABCl 例2-4某邏輯函數(shù)的卡諾圖見下圖a，化簡結(jié)果如下圖b所示。l 什么是SOP和POS?l 什么是最小項和最大項?l 如何找出邏輯函數(shù)中所包含的最小項?l 邏輯函數(shù)中所包含的最小項和最大項與函數(shù)的卡諾圖之間存在什么關(guān)系？l 3變量和4變量的卡諾圖，相鄰的兩行（列）有什么規(guī)律？l 為什么卡諾圖中相鄰兩個小方格中最小項可以合并？l 為什么是相鄰的4個、8個最小項能夠合并，而不是相鄰的6個最小項？l 卡諾圖中相鄰最小項合并后的結(jié)果如何確定?l 卡諾圖中為什么看起來不是相鄰、分處于一行（列）的兩端，或分處于四角的最小項實際上也是相鄰的?l 什么是蘊涵？什么是質(zhì)蘊涵

21、？什么是必要質(zhì)蘊涵？l 什么是蘊涵的包含關(guān)系？l 什么是隨意項？它也被稱做什么？l 為什么隨意項既可以當(dāng)作真值1？也可以當(dāng)作真值0?l 在考慮隨意項時，EPI的條件是什么？l 什么是邏輯函數(shù)的一個“覆蓋”？l reducel optimizel Sum Of Productsl Product Of Sumsl canonical forml minterml maxterml Karnaugh mapl cover,minimal coverl dont care termsl Essential Prime Implicantl 2.1.4 l 與四變量的卡諾圖類似，我們也可以畫出五變量和

22、六變量的卡諾圖來。如圖2-13和圖2-14所示。l 與四變量卡諾圖時一樣，五、六變量卡諾圖中“相鄰”的最小項（最大項）也可以合并化簡。但五、六變量卡諾圖中的“相鄰”關(guān)系判別要比四變量卡諾圖來得復(fù)雜。l 實際上，任何卡諾圖中最小項（最大項）的“相鄰”關(guān)系，就是通過它們彼此僅相差一個變量來決定的。如：ABCDE和ABCDE就是相鄰的。根據(jù)這個原則，我們就容易找出五、六變量卡諾圖中的“相鄰”關(guān)系了。l 通過分析，我們發(fā)現(xiàn)可以將五變量卡諾圖劃分成2個四變量卡諾圖。每個四變量卡諾圖中的合并化簡規(guī)律，與前面所述的一樣。而這2個四變量卡諾圖上，對應(yīng)位置的小方格是“相鄰”關(guān)系。如圖2-15所示。指邏輯上的相鄰

23、，而非幾何上的相鄰l 圖中，字母A、BO、P是用于標(biāo)示小方格的符號。在2個四變量卡諾圖中，寫有相同字母的兩個小方格是相鄰的。l 在劃分出的2個四變量卡諾圖中，如果具有對應(yīng)位置相同的質(zhì)蘊涵(PI)，則它們可以進(jìn)一步合并化簡。如圖2-16所示。l 同理，六變量卡諾圖也可以劃分成為4個四變量卡諾圖。而位于行（列）相同、列（行）相應(yīng)位置上的小方格，彼此兩兩相鄰。Y=BDE+BCEFl 如果在2個或者4個劃分出的四變量卡諾圖中，具有對應(yīng)位置相同的質(zhì)蘊涵(PI)，則它們可以進(jìn)一步合并化簡。如右圖所示。l 2.1.5 l 最大項函數(shù)是“和之積（POS）”形式的邏輯函數(shù)。其特點是各和項取值為0時，函數(shù)值為0。

24、各和項對應(yīng)于卡諾圖的最大項。l 所以當(dāng)應(yīng)用卡諾圖化簡最大項函數(shù)時，應(yīng)當(dāng)對圖中真值為0的最大項進(jìn)行合并化簡；并將化簡結(jié)果中各變量取非后，以POS形式輸出即可。l 最大項邏輯函數(shù)的化簡，如圖2-18所示。l 2.2 l 隨著邏輯函數(shù)的輸入變量的增加，卡諾圖的尺寸將會隨之而增大。為此，MEV卡諾圖（Map Entered Variable）技術(shù)應(yīng)運而生。所謂就是將某些輸入變量映射到卡諾圖的真值中，這樣就能夠用較小的卡諾圖表示和化簡較多輸入變量的邏輯函數(shù)。如：用44的卡諾圖來處理5變量或6變量的邏輯函數(shù)問題等。因此，MEV卡諾圖也被稱為。l 下面我們將對MEV卡諾圖的理論進(jìn)行詳細(xì)深入的分析研究。l M

25、EV卡諾圖的真值，就是填寫在MEV真值表中的內(nèi)容。前面我們知道，普通卡諾圖中的真值只有3種情況：0、1和x。而在映射變量時，情況就復(fù)雜多了。l 1.一個映射變量的情況l 所謂一個映射變量，就是將某一個輸入變量作為真值內(nèi)容的一部分，填寫到真值表中；從而使MEV卡諾圖的尺寸減小為少去一個變量的卡諾圖尺寸的邏輯化簡方法。l 為了分析的簡單起見，我們以五變量的邏輯函數(shù)為例，如圖2-19所示。l 分析可知，五變量卡諾圖中每2個橫向相鄰的小方格，映射于MEV卡諾圖中的一個小方格。例如：五變量卡諾圖中的m0、m1方格，映射到了MEV圖中第一行的左數(shù)第一個方格；五變量卡諾圖中的m4、m5方格，映射到了MEV圖

26、中第一行的右數(shù)第一個方格。其它以此類推。l 由于表示邏輯函數(shù)時，五變量卡諾圖中每個小方格都有3種可能的取值： 、 和 ；所以映像到MEV圖中后，MEV圖中小方格的取值就有9種情況(33=9)。分析后我們知道，這9 種情況為：0、1、x、E、E、xE、xE、E+xE、E+xE。l 也就是說，此時MEV卡諾圖中所填寫的真值，應(yīng)當(dāng)為：0、1、x、E、 xE、xE、E+xE、E+xE 這9種值中的某一個。l 這里取值x表示真值可以?。?、1、E、 E這4種值的任意之一。取值xE表示真值可以任意?。?、E這2者之一。取值xE表示真值可以任意?。?、E這2者之一。l 其他情況以此類推。l 例2-5畫出五變

27、量邏輯函數(shù) f =m(7,10,16,17) +d(23)的四變量MEV圖。圖2-20 例2-5的圖l 2.2.2 l 1.MEV卡諾圖化簡的法則l 除了隨意項之外，以SOP形式的邏輯函數(shù)，MEV卡諾圖中所有填寫不為0真值（對于POS形式的邏輯函數(shù)，則是不為1真值）的方格，均對應(yīng)原卡諾圖中的一個最小項（最大項），必須在化簡過程中被覆蓋掉。l 填寫有相同真值的相鄰小方格可以合并化簡。小方格的相鄰關(guān)系與普通卡諾圖的完全一致。l 填寫為1真值的方格，在合并化簡時，可以視為E+E ，或 F+F ，或EF+EF+EF+EF參與化簡。l 在合并化簡POS形式的邏輯函數(shù)時，填寫為0真值的方格，可以視為EE，

28、或FF，或(E+F)(E+F)(E+F)(E+F)參與化簡。l 2.一個映射變量MEV卡諾圖化簡的步驟l 對含有真值E的方格進(jìn)行合并化簡。l SOP函數(shù)時，填寫1真值的方格，可以參與合并（相當(dāng)于隨意項）。合并化簡的結(jié)果為f(A,B,C,D) E形式。f(A,B,C,D)為僅含字母A、B、C、D的積項，如：ABCD等。 l POS函數(shù)時，填寫0真值的方格，可以參與合并（相當(dāng)于隨意項）。合并化簡的結(jié)果為g(A,B,C,D)+E形式。 g(A,B,C,D)為僅含字母A、B、C、D的和項，如：A+B+C+D等。l 對含有真值E的方格進(jìn)行合并化簡。l SOP函數(shù)時，填寫1真值的方格，可以參與合并（相當(dāng)于

29、隨意項）。合并化簡的結(jié)果為f(A,B,C,D) E形式。f(A,B,C,D)為僅含字母A、B、C、D的積項，如：ABCD等。l POS函數(shù)時，填寫0真值的方格，可以參與合并（相當(dāng)于隨意項）。合并化簡的結(jié)果為g(A,B,C,D)+E形式。g(A,B,C,D)為僅含字母A、B、C、D的和項，如：A+B+C+D等。l 對填寫1（或0）真值的方格進(jìn)行合并化簡。l 如果填寫1（或0）真值的方格，已經(jīng)被充當(dāng)E和E各用過了至少一次，則該方格就是已經(jīng)被覆蓋了；這時該方格相當(dāng)于隨意項。否則，最后該方格還必須以真值1（或0）用至少一次。l 對于SOP函數(shù)，E+xE、E+xE可以作為1真值參與化簡。如果它們已經(jīng)作為

30、E、E用過了，則此時它們相當(dāng)于隨意項；否則，它們必須作為真值1參與化簡。l 對于POS函數(shù)，xE、xE可以作為0真值參與化簡。如果它們已經(jīng)作為E、E 用過了，則此時它們相當(dāng)于隨意項；否則，它們必須作為真值0參與化簡。l 實際上合并化簡步驟中、的順序是可以交換的，不同的次序可以導(dǎo)致優(yōu)化結(jié)果的不同。l 例2-6用MEV圖化簡邏輯函數(shù) Y=m(7,10,16,17,25,26,27)+d(23)l 解：畫出邏輯函數(shù)的MEV圖如圖2-23所示。 l 我們首先對真值為E的方格化簡，將與之相鄰的、1真值的方格充當(dāng)E參與化簡，得BCDE。l 而后對真值為E的方格化簡。與之相鄰的、1真值的方格又充當(dāng)E參與化簡

31、，得ABCE。另一個真值為E的方格與真值為xE的方格合并，得BCDE。l 對于那個既作為E用過、又作為E用過的真值為1的方格，就不必再考慮了。l 而另一個未用過、真值為1的方格,直接寫出得ABCD。l 當(dāng)輸入變量數(shù)目較多時，采用卡諾圖法對邏輯函數(shù)進(jìn)行化簡就不太實用了。因為當(dāng)輸入變量數(shù)目較多時，通過卡諾圖來尋找PI和EPI就不再容易了。而Q-M(Quine-McClusky)法卻能夠很好地解決任意多個輸入變量的邏輯函數(shù)化簡問題；同時Q-M法還是一種適宜于用計算機(jī)程序?qū)崿F(xiàn)的邏輯函數(shù)化簡法。因此在邏輯函數(shù)化簡技術(shù)領(lǐng)域中，Q-M法占有著十分重要的地位。l2.3 l Quine-McClusky法通過一

32、系列的步驟，最終求得函數(shù)的最優(yōu)化簡結(jié)果。其程序流程如圖2-28所示。l 2.3.1 l 1.使用Q-M法時蘊涵和質(zhì)蘊涵的表示方法l 當(dāng)使用Q-M法化簡邏輯函數(shù)時，我們用一個二進(jìn)制數(shù)(字符串)來表示最小項（或最大項）。如：將ABCDEFG表示為1101011、ABCDEFG表示為0101010等。l 如果兩個表示最小項（最大項）的字符串僅在某一位上數(shù)值相異，而其它各位數(shù)值都相同；則這兩個最小項（或最大項）可以合并成一個蘊涵。我們用x替換掉相異的那一位，就得到了表示該蘊涵的字符串。例如：11011001與11001001合并的結(jié)果為110 x1001。l 同理，兩個表示蘊涵的字符串如果僅在某一位上

33、數(shù)值相異，而其它各位數(shù)值都相同；則這兩個蘊涵可以合并化簡成另一個新的蘊涵。我們用x替換掉相異的那一位，就得到了表示化簡結(jié)果的字符串。如：110 x1001與110 x1000合并的結(jié)果為110 x100 x。l 也就是說，在使用Q-M法時，我們可以用由0、1和x組成的字符串來表示函數(shù)的蘊涵和質(zhì)蘊涵。l 2.用Q-M法求PI和EPI的步驟如下：l 求出邏輯函數(shù)所有的最小項（最大項）。l 將邏輯函數(shù)的最小項（最大項）用相應(yīng)的二進(jìn)制數(shù)（字符串）表示。l 分組：將表示邏輯函數(shù)最小項（最大項）的二進(jìn)制數(shù)，按它們中所含1的數(shù)目分別放置在不同的組中。l 如：第0組中是不含1的二進(jìn)制數(shù)、第1組中是含有一個1的

34、二進(jìn)制數(shù)、第2組中是含有兩個1的二進(jìn)制數(shù)對放在相鄰兩個組中的字符串逐位比較。如果它們除了在某一位數(shù)值不同外、其它各位數(shù)值均相同，則它們就能夠合并成一個新的蘊涵。l 對于能夠合并的最小項（最大項）做上標(biāo)記（一般是用打勾表示）。l 第一次生成的分組表稱為第1級分組表。l 將第1級分組表中所有帶標(biāo)記字符串的合并結(jié)果放入第2級分組表中：l 分屬于第1級分組表中兩個相鄰組、且兩個字符串僅有某一位相異時，用x將相異的那一位替換掉，即得到表示兩個最小項（最大項）合并結(jié)果的蘊涵的字符串。并對該蘊涵所覆蓋的最小項（最大項）進(jìn)行記錄。l 然后將新產(chǎn)生的字符串按照所含1的數(shù)目分組放入第2級分組表。l 如果屬于前一級

35、分組表的某些字符串不帶標(biāo)記，則也將它放入到后一級分組表中。l 對放在相鄰兩個組中的字符串逐位比較。如果它們能夠進(jìn)一步合并成新的蘊涵，則為它們加上標(biāo)記。l 按照步驟中的方法，由前一級分組表的合并結(jié)果得到后一級分組表，第n次生成的稱為第n級分組表。如此進(jìn)行，直到所有字符串全都無法進(jìn)一步化簡為止。l 此時表中存放的字符串就是函數(shù)的質(zhì)蘊涵PI了。l 對已經(jīng)獲得的質(zhì)蘊涵PI進(jìn)行檢查。如果一個PI中所覆蓋的某個最小項或最大項（必須不是隨意項），是其它PI所沒有覆蓋的；也即存在著由該PI單獨覆蓋的某個最小項（最大項）時，這個PI就是必要質(zhì)蘊涵，即EPI。l 在分組表中將找出的EPI做上標(biāo)記（一般是用*號將單

36、獨覆蓋的最小項或最大項標(biāo)出）。l 至此，邏輯函數(shù)的EPI的求解完成。l 例2-8求邏輯函數(shù)f=m(9,10,11,14,15,25,26,27,30,41,57,61)的全部PI和EPI。l 解：如圖2-26b所示，將真值表中的二進(jìn)制數(shù)分組得第1級分組表。l 第1級分組表中的內(nèi)容合并、分組后得第2級分組表，如2-26c所示。l 如：001001與001011合并得0010 x1, 001001與011001合并得0 x1001, 001001與101001合并得x01001,001010與001011合并得00101x, 001010與001110合并得001x10, 001010與01101

37、0合并得0 x1010, 101001與111001合并得1x1001, 111001與111101合并得111x01等。l 第2級分組表中的內(nèi)容合并、分組后得第3級分組表，如2-29d所示。l 如：0 x1001與1x1001合并得xx1001, 0010 x1與0110 x1合并得0 x10 x1, 00101x與01101x合并得0 x101x, 001x10與011x10合并得0 x1x10, 001x10與001x11合并得001x1x等。l 列出質(zhì)蘊涵表，即將每個PI所覆蓋的最小項情況用表格顯示出來，如圖2-27所示。l 檢查質(zhì)蘊涵表，找出被某個PI單獨覆蓋的最小項，為它們打上*號

38、。表中凡是有*號的就是必要質(zhì)蘊涵EPI?，F(xiàn)在EPI為：xx1001,0 x1x10,001x1x和111x01。l 2.3.2 l 所謂函數(shù)的，就是用最少的PI來覆蓋該函數(shù)所有的最小項（最大項）。l 分析可知：必要質(zhì)蘊涵EPI是必須選擇的PI；而對于剩下的非必要質(zhì)蘊涵，選擇哪些PI能夠構(gòu)成函數(shù)的最優(yōu)覆蓋，則不是十分明顯的。l Q-M化簡法提供了求解函數(shù)最優(yōu)覆蓋的一套完整方案，為實現(xiàn)函數(shù)的最優(yōu)化簡提出了行之有效的方法。l Q-M化簡法的算法流程如下：l 步驟1：從質(zhì)蘊涵表生成簡化質(zhì)蘊涵表l 從質(zhì)蘊涵表將EPI放入到中，把剩余的非必要質(zhì)蘊涵PI放入到中。l 從簡化質(zhì)蘊涵表中，將被化簡結(jié)果表中PI所

39、覆蓋的最小項（最大項）全部除去。這時簡化質(zhì)蘊涵表存放的是尚未被化簡結(jié)果覆蓋的最小項（最大項）的情況。l 步驟2：從簡化質(zhì)蘊涵表中除去劣勢PIl 在簡化質(zhì)蘊涵表中，如果存在某一PIi ，（將被化簡結(jié)果表中PI所覆蓋的最小項或最大項除去后）其所覆蓋的最小項（最大項）在另一個PIj中全部能夠找到、且PIj中最小項（最大項）的數(shù)目多于PIi ；則PIi 相對于PIj就是PI。l 由于PIj覆蓋的結(jié)果也一定會覆蓋PIi ，所以PIi 可以被PIj 取代。故我們找到劣勢PI后，把它們從簡化質(zhì)蘊涵表中除去。l 步驟3：循環(huán)操作l 當(dāng)除去劣勢PI后，就可能會有“某個PI中所覆蓋的某些最小項（最大項），沒有被其

40、它PI所覆蓋”的情況出現(xiàn)；也即這個PI為EPI。l 將找到的新的EPI放入到化簡結(jié)果表中，余下的PI留在簡化質(zhì)蘊涵表中。然后跳轉(zhuǎn)至步驟1的處。l 如此循環(huán)工作，直到簡化質(zhì)蘊涵表為空，完成函數(shù)的化簡為止。l 這樣的化簡過程實現(xiàn)了函數(shù)的最優(yōu)化簡，化簡結(jié)果存放在化簡結(jié)果表中。l 步驟4：從簡化質(zhì)蘊涵表中選取最低價格PI l 在上述的化簡過程中，如果某一次循環(huán)時EPI不存在、或者找不到劣勢PI，化簡工作就無法繼續(xù)下去了。這時可以采用選取最低價格PI的方法解決之。l 所謂PI，就是指在物理實現(xiàn)上價格最低的PI，也即字符串中包含x數(shù)目最多的PI。l 如果出現(xiàn)了多個字符串中x數(shù)目相同的情況，則可以任意選擇其

41、一，作為最低價格PI。l 將選取的最低價格PI放入到化簡結(jié)果表中，更新簡化質(zhì)蘊涵表。然后跳轉(zhuǎn)至步驟1的處。l 如此循環(huán)工作，直到簡化質(zhì)蘊涵表為空，完成函數(shù)的化簡為止。l 應(yīng)當(dāng)指出，選擇最低價格PI的方法，不能保證一定會得到最優(yōu)的函數(shù)覆蓋，只能保證得到較優(yōu)的化簡結(jié)果。如果要得到最優(yōu)的函數(shù)覆蓋，就要使用搜索的方法，這樣顯然會增加解決問題的難度。例2-9已知質(zhì)蘊涵表如圖2-29所示，求函數(shù)的最優(yōu)化簡結(jié)果。圖2-29 例2-9的質(zhì)蘊涵表EPIl 解：圖2-30、圖2-31、圖2-32是利用Q-M法求最優(yōu)覆蓋的過程。l 1）首先將EPI放入化簡結(jié)果表中，求得簡化質(zhì)蘊涵表，如圖2-30所示。l 2）然后，

42、檢查簡化質(zhì)蘊涵表中是否存在劣勢PI，若有則消去之。由于現(xiàn)在不存在劣勢PI，所以選擇一個最低價格PI，放入化簡結(jié)果表中；再從余下的PI中消去被該最低價格PI所覆蓋的最小項，如圖2-31所示。l 3）從簡化質(zhì)蘊涵表中消去劣勢PI：xx001。l 4）從簡化質(zhì)蘊涵表中查找EPI，如圖2-32所示。除去除去1x00 x中所中所包含的最小項包含的最小項化簡結(jié)果1x00 x選取的最低價格PI化簡結(jié)果除去除去x100 x中所中所包含的最小項包含的最小項劣勢PI找到EPIl 5）將EPI放入化簡結(jié)果表中，更新簡化質(zhì)蘊涵表，如圖2-33所示。l 6）從簡化質(zhì)蘊涵表中消去劣勢PI：0001x和1x0 x1。l 7

43、）從簡化質(zhì)蘊涵表中查找EPI，如圖2-34所示。l 8）將EPI放入化簡結(jié)果表中，更新簡化質(zhì)蘊涵表。此時化簡結(jié)果表中的PI已經(jīng)完成了函數(shù)的覆蓋，所以函數(shù)的優(yōu)化過程到此結(jié)束，化簡結(jié)果為1x00 x、x100 x、x00 x1、0 x010和110 xx。劣勢PI劣勢PI被0 x010和110 xx覆蓋l 在實際工作中，除了單輸出函數(shù)外，還會遇到多輸出函數(shù)化簡的情況。所謂，就是在一組輸入變量的情況下，同時存在多個函數(shù)輸出的問題。這時某些邏輯門電路可以被多個輸出函數(shù)所共享，整個電路的化簡工作應(yīng)當(dāng)針對所有的輸出來進(jìn)行。電路的化簡優(yōu)化應(yīng)當(dāng)是一個，這時電路的最小實現(xiàn)是指用最少的物理電路來實現(xiàn)多個輸出函數(shù)的

44、邏輯功能。2.6l 例如圖2-41是3個輸出函數(shù)的卡諾圖，其全局優(yōu)化的結(jié)果應(yīng)為：Yc=ACD，Yb=ACD+ABC，Ya=ACD+ACDl （其他內(nèi)容略去）l 2.7 是由作者本人研制編寫的、專門用于邏輯函數(shù)化簡優(yōu)化的計算機(jī)軟件。l 卡諾圖軟件具有優(yōu)異的性能，目前國內(nèi)尚未見有同類軟件的報導(dǎo)。l 卡諾圖軟件具有功能完備、使用方便等許多優(yōu)點，它既能夠用于解決邏輯設(shè)計的實際問題，也能夠用于數(shù)字邏輯課程的輔助教學(xué)。在電腦日益普及的今天，卡諾圖軟件為讀者學(xué)習(xí)、應(yīng)用數(shù)字邏輯知識提供了極好的幫助。l 在本書中附帶有卡諾圖軟件2.0光盤，以供安裝使用。l 2.7.1 l 卡諾圖軟件的主要功能有：l 1）可以進(jìn)

45、行3、4、5、6變量邏輯函數(shù)的卡諾圖化簡。l 2）具有MEV卡諾圖化簡功能。l 3）提供Q-M(奎因表)化簡功能l 4）具有銳積法、相容法化簡功能。l 5）可以對“多輸出函數(shù)”進(jìn)行化簡。l 6）具有多種輸入功能，包括真值表、最小項、最大項和表達(dá)式輸入功能等。l 其中表達(dá)式輸入功能，允許用戶直接用邏輯表達(dá)式，來輸入待優(yōu)化的邏輯函數(shù)。l 7）支持POS、SOP、正函數(shù)和反函數(shù)（有時采用正函數(shù)比采用反函數(shù)化簡結(jié)果更優(yōu)，有時則正好相反）等各種函數(shù)形式。l 8）單步操作模式，能夠清楚地顯示出邏輯化簡的每一中間步驟。l 圖2-42是卡諾圖軟件的操作界面圖。l 2.7.2 l 如圖2-43所示，卡諾圖軟件的

46、操作界面包括菜單欄、工具條、真值輸入?yún)^(qū)、化簡圖示區(qū)、化簡結(jié)果輸出文本框、公式輸入文本框、函數(shù)形式選擇框等。 l 卡諾圖軟件的各種控件功能如下：l 1.菜單欄l 文件：可執(zhí)行裝入邏輯化簡的例子、結(jié)束程序等操作。l 設(shè)置：可選擇程序工作于三元變量、四元變量、五元變量、六元變量、多輸出函數(shù)、奎因表和銳積/相容法等不同的工作狀態(tài)。l 輸入輸出：可執(zhí)行表達(dá)式輸入、選擇SOP或POS函數(shù)形式和執(zhí)行全1真值輸入、全0真輸入等操作。l 運行：可執(zhí)行函數(shù)化簡、單步化簡和清除等操作。l 幫助：可查看軟件的幫助文件、獲取軟件的版本信息和作者信息等。l 2.工具條l 工具條提供了軟件各種操作的快捷手段，工具條中各按鈕

47、的功能如圖2-44所示。l 3.真值輸入?yún)^(qū)l 卡諾圖軟件提供有多種方法來完成真值輸入的任務(wù)。利用鼠標(biāo)直接點擊真值輸入?yún)^(qū)中的真值方格，就是一種常用的真值輸入方法。此時，用鼠標(biāo)左鍵點擊某一真值方格，就可以改變方格中的值，從空(代表0值)變到1，從1變到0，從0變到x(當(dāng)“帶約束條件”被選中時)。l 當(dāng)按下Ctrl+Z鍵后，可以直接查看到各個方格所對應(yīng)最小項(最大項)的數(shù)值。因而能夠按邏輯函數(shù)的最小項(最大項)形式來輸入該函數(shù)。l 4.化簡圖示區(qū)l 當(dāng)函數(shù)輸入完畢后進(jìn)行邏輯化簡時，在化簡圖示區(qū)我們可以看到函數(shù)的化簡結(jié)果圖。化簡結(jié)果中的每一個質(zhì)蘊涵PI，都被一個彩色圖元所表示了。加上軟件具有查看化簡結(jié)

48、果的單步功能，因此軟件顯示的化簡結(jié)果具有非常直觀、生動的效果。l 5.化簡結(jié)果輸出文本框和表達(dá)式輸入文本框l 化簡結(jié)果輸出文本框用于顯示化簡結(jié)果的邏輯表達(dá)式?？ㄖZ圖軟件支持SOP和POS的函數(shù)形式。在邏輯表達(dá)式中，卡諾圖軟件“!”來表示邏輯函數(shù)的“非”邏輯。l 利用表達(dá)式輸入文本框可以直接輸入函數(shù)的邏輯表達(dá)式。表達(dá)式輸入時允許使用多重小括號。輸入完畢后回車即提交輸入的內(nèi)容。l 例如可以輸入：ABCD+(!A!C+CD)(!B+D)等。其中!X表示 X。l 6.函數(shù)形式選擇框l 卡諾圖軟件不但支持SOP和POS函數(shù)形式，還支持正函數(shù)和反函數(shù)形式。當(dāng)選擇反函數(shù)形式時，軟件按輸入真值表的反函數(shù)形式來

49、進(jìn)行邏輯化簡。l 2.7.3 l 例2-10 化簡邏輯函數(shù)f(A,B,C,D)=ABC+ACD+ABCD+ABCD 。l 分析可知函數(shù)由最小項ABCD、ABCD、ABCD、ABCD、ABCD和ABCD組成。l 用鼠標(biāo)點擊真值輸入?yún)^(qū)中相應(yīng)的方格，完成函數(shù)輸入工作。然后按“化簡”按鈕，化簡圖示區(qū)中就會顯示出化簡結(jié)果圖，同時從化簡結(jié)果文本框中讀到化簡結(jié)果的邏輯表達(dá)式：!B!C+!CD。l 以上化簡過程，如圖所示。l 例2-11 化簡邏輯函數(shù)f(A,B,C,D)=m(1,3,4,6,7,8,15)+ d(0,5)l 首先按下ctrl+z鍵，真值輸入?yún)^(qū)將顯示出各個方格的最小(大)項數(shù)值。選擇“帶約束條件

50、”選項，點擊鼠標(biāo)使m0、m5方格中的值為x，使m1、m3、m4、m6、m7、m8和m15方格中的值為1。然后按“化簡”按鈕，即可完成函數(shù)化簡，結(jié)果為：!AB+!AD+BCD+!B!C!D。l 以上化簡過程，如圖2-46 和圖2-47所示。圖2-46 查看最小項（最大項）圖2-47 例2-11中的圖l 例2-12 化簡邏輯函數(shù)f(A,B,C,D)=A+B(ACD+D(A+BC)l 點擊工具條上的“表達(dá)式輸入”按鈕，公式輸入文本框?qū)@示出來。將光標(biāo)置于公式輸入文本框中，用鍵盤輸入A+B(!A!CD+!D(A+!BC)后，按回車即可。得到的化簡結(jié)果為：A+B!CD。l 以上化簡過程，如圖2-48所示。圖2-48 例2-12的圖l 五變量和六變量的卡諾圖是如何畫出的? 圖中相鄰的兩行(列)之間仍然是只有一個變量相異嗎?l 五變量和六變量卡諾圖邏輯化簡時的“相鄰”關(guān)系，是如何確定的?l 邏輯函數(shù)按最大項化簡時與按最小項時的異同何在?l 什么是MEV？對于1個變量的MEV，1個小方格對應(yīng)于普通卡諾圖中的幾個方格？l MEV化簡的步驟是怎么樣的？l 當(dāng)變量數(shù)目較多時，應(yīng)當(dāng)采用何種方法進(jìn)行邏輯化簡？l 什么是劣勢PI? 什么是最低價格PI？l 多輸出邏輯函數(shù)邏輯化簡時，應(yīng)當(dāng)按什么原則進(jìn)行?l 卡諾圖軟件的