數(shù)字邏輯課件-邏輯函數(shù)的表格化簡法

3.邏輯函數(shù)的表格化簡法適合于變量較多的邏輯函數(shù)化簡法—表格化簡法。（1）變量的個數(shù)不受限制，可以比較多；（2）規(guī)律性比較強，適合于計算機邏輯函數(shù)化簡。其缺點是：對于變量較多的函數(shù)，用人工表格法化簡就很繁瑣。表格法化簡的基本思想類似于卡諾圖法，即應用公式：與項·A+與項·

=與項，就可以形成一個新的較簡的“與”項。表格法化簡的步驟如下：(1)把需簡化的邏輯函數(shù)展開成最小項之和的形式。(2)將各最小項mi下角標i表示成二進制數(shù)，再根據(jù)其中各位有“1”的個數(shù)由少到多分組排隊。重復使用的公式，在組與組之間進行逐－搜索，尋找相鄰兩項（即兩個二進制數(shù)除一位不同外，其余各位均相同）。若有則合并成一項并把它記下，同時在這相鄰兩項旁做一記號“√”。把所有存在于組與組之間的相鄰項都找到后便可得到一組含有（n－1）個變量的與項（仍以二進制代碼表示，“1”表示原變量，“0”表示反變量，“－”表示已消去的變量）。對得到的（n－1）個變量的與項也采用同樣的方法：分組、搜索相鄰項合并成一項并做以記號“√”，記下新項，便可得到一組含有（n－2）個變量的項。再重復同樣的方法，依次類推。我們可以逐步從（n－2），（n－3），…個變量項中得到含有（n－3），（n－4），…個變量的各項，一直進行到最后一組以致其中各項已無法相鄰合并為止。這時，在所有各項旁沒有記號“√”的項就是我們需要的項，稱為質蘊涵項（Primeimplicant），亦即不含多余變量的項，也就是它再不能同其它項合并而得到變量更少的項了。請看下面的例子： 先把最小項分組排隊，如表1-3-9(a)，組號最小項編號變量ABCD

0000001480010000126100110010131113141101101101114151111表1-3-9(a)最小項分組排隊組號最小項編號變量ABCD

000000√261001100101√√3111314110110110111√√√4151111√表1-3-9(a)最小項分組排隊在相鄰組之間逐一搜索尋找相鄰項，合并成新的“與”項，得到一組含有3個變量的“與”項，見表1-3-9(b)，組號最小項編號變量ABCD

00,40,800－0000－P1P214,68,100－100－01P3P426,1410,1110,14011－－10101－1P5√√313,1514,1511,151－11－11111－1P6√√表1-3-9(b)(n-1)個變量的與項然后再重復上述過程。值得說明的是：在表1-3-9(b)中尋找相鄰項時，相鄰項除一位不同外，其余各位均相同的含意也包括兩項中在同一位置有“－”，如“－101”與“－111”是相鄰項，可合并為“－1－1”。見下表1-3-9(c)。把表1-3-9(b)和表1-3-9(c)中無法再合并的質蘊涵項分別記作P1…P7。組號最小項編號變量ABCD

210,1114,15－1－1

P7

表1-3-9(c)(n-2)個變量的與項圖1-3-19函數(shù)以質蘊涵項表示函數(shù)F就是這些質蘊涵項之和，但它不是最簡的結果。畫出函數(shù)F的卡諾圖，如圖1-3-19所示。從圖中看出：各組間搜索的結果，只是把所有的質蘊涵項找出，但有些質蘊涵項是不必要的，或者說是重復的。例如：P5中沒有包含新的“1”塊。所以，還要從質蘊涵項中找出必要的質蘊涵項。圖1-3-19函數(shù)以質蘊涵項表示（3）選出必要的質蘊涵項先把全部質蘊涵項列表如表1-3-10(a)，表的每一行對應一個質蘊涵項，每一列對應一個最小項，把每個質蘊涵項所包含的最小項在表中打“×”，假如，P4中包含最小項m8和m10，就在P4行的m8，m10列打“×”，這張表稱為質蘊涵表。

miPm0m4m6m8m10m11m13m14m15P1P2P3P4P5P6P7××××××××××××××××表1-3-10(a)質蘊涵表為尋找必要質蘊涵項，先尋找出那些最小項僅僅屬于一個質蘊涵項，在表1-3-10(a)中，m11僅屬于P7，m13僅屬于P6。如果質蘊涵表的一列中只有一個“×”，那么就表示此最小項僅屬于一個質蘊涵項，因此該質蘊涵項就一定是必要的，由于P6，P7已選定為必要質蘊涵項，在選其它必要質蘊涵項時，可把P6，P7從質蘊涵表中刪去。表1-3-10(a)質蘊涵表

miPm0m4m6m8m10m11m13m14m15P1P2P3P4P5P6P7××××××××××××××××因為P6不僅包含m13，還包含m15；P7不僅包含m11，還包含m10，m14，m15，因此在從表1-3-10(a)中刪去P6，P7的同時，可把它們所包含的最小項m10，m11，m13，m14，m15均刪去，表1-3-10(a)質蘊涵表

miPm0m4m6m8m10m11m13m14m15P1P2P3P4P5P6P7××××××××××××××××這樣，表1-3-10(a)就可簡化為表1-3-10(b)。往后的任務就是要在P1，P2，P3，P4，P5中選出其余的必要質蘊涵項，使之包含m0，m4，m6，m8。

從簡化質蘊涵表中選取必要質蘊涵項有表達式法與行列消去法兩個辦法。先介紹表達式法。表1-3-10(b)簡化質蘊涵表

miPm0m4m6m8

P1P2P3P4P5××××××××由表1-3-10(b)可知，m0包含在P1和P2中，即質蘊涵的組合為（P1+P2），m8包含在P2和P4中，即（P2+P4）。要同時包含m0，m8的質蘊涵組合為此式表明要包含m0，m8有四種選取方法：或選取P1“與”P2；或選取P1“與”P4；或選取P2；或選取P2“與”P4。為滿足最簡“與或”式的要求，應選P2為必要質蘊涵項。表1-3-10(b)簡化質蘊涵表

miPm0m4m6m8

P1P2P3P4P5××××××××應選P3為必要質蘊涵項。因此用表格法化簡的F最簡式為簡化結果與用圖1-3-20所示卡諾圖簡化結果是一致的。

圖1-3-20圖1-3-19化簡結果同理，同時包含m4，m6的質蘊涵組合為行列消去法

行列消去法用于簡化質蘊涵表中行數(shù)和列數(shù)都比較多的情況。以表1-3-11(a)所示的簡化質蘊涵表為例。先進行行消去法。

miP

m2

m4

m6

m10P2P3P4P5P6××××××××檢查表1-3-11(a)可發(fā)現(xiàn)，P5行所包含的m4也包含在P4之中，而且P4除包含m4外，還包含了m6，假如選P4也就不必要再考慮P5了，這樣P5行就可從表1-3-11(a)中刪去。表1-3-11(a)簡化質蘊涵表如果有兩行（Pi和Pj行），其中Pi行的“×”全部包含在Pj行中，那么Pi行就可從表中刪去。同理，P6所包含的m10也是P3所包含的。所以P6行也可刪去。這樣，行消去后的質蘊涵表如右表1-3-11(b)所示。這就是行消去法。檢查表1-3-11(b)發(fā)現(xiàn)，在m4列中有“×”的P4行中，在m6列處也有“×”，因此可把m6列刪去。同理，在m10列中有“×”的P3行中，在m2列處也有“×”，因此可把m2列刪去。最后剩下的為P3覆蓋m10，P4覆蓋m4，當然，P3，P4也分別覆蓋了m2和m6。一般來說，表1-3-11(b)行消去后的簡化質蘊涵表

miP

m2m4m6m10

P2P3P4××××××如果mi列中記有“×”號的各列中，在mj列中也記有“×”號，那么，可將mj刪去（注意：刪去的是mj列，而不是mi列）。這就是列消去法。經(jīng)行、列消去后剩下的P3，P4就是必要質蘊涵項。對于復雜的質蘊涵表，行列消去法必須反復進行。必須指出，行、列消去次序不影響簡化結果。通常，可以將表達式法和行列消去法結合進行。先用行列消去法把質蘊涵項盡量簡化，再用表達式法。行列消去法對未簡化的質蘊涵表也是適用的。用表格法化簡變量數(shù)目較多的邏輯函數(shù)，只要按上述步驟進行，最終也是可以得到最簡函數(shù)的。例1-15用表格法化簡邏輯函數(shù)(1)將各最小項按其對應二進制數(shù)中“1”的個數(shù)由少到多分組排隊（表1-3-12(a)）。組號最小項編號變量ABCD

000000√111000√

2369121100011010010011√√√P1371111101101√√4151111√表1-3-12(a)最小項分組排隊組號最小項編號變量ABCD

00,1－000

P211,31,91－00100－√√23,73,116,79,1111－0110－－1101－01√√P3√37,1511,15111－11－1√√表1-3-12(b)(n-1)個變量的與項(2)求全部質蘊涵項。對表1-3-12(a)進行組間搜索。合并相鄰最小項得新的與項記在表1-3-12(b)中，并在相鄰最小項右側打“√”。組號最小項編號變量ABCD

11,3,9,111－0－P423,7,11,1511－－P5表1-3-12(c)(n-2)個變量的與項再對表1-3-12(b)進行組間搜索，尋找相鄰項，相鄰項合并后得新的“與”項記在表1-3-12(c)中，并在相鄰項的右側打“√”。

mi

P

m0m1

m3

m6

m7

m9m11

m12

m15P1P2P3P4P5×××××××××××××表1-3-13(a)質蘊涵表(3)選出必要的質蘊涵項。質蘊涵表如表1-3-13(a)，用行列消去法對表1-3-13(a)進行簡化，先進行列消去法，m0列的“×”號完全包含在m1列中，m6列的“×”號完全包含在m7列中，m9列的“×”號完全包含在m11列中，可消去m1，m7，m11列，得到表1-3-13(b)，mi

P

m0m3

m6

m9m12

m15P1P2P3P4P5×××××××再對表1-3-13(b)作行消去，因為各P行之間均無包含關系，所以無P行可消去。檢查表1-3-13(b)發(fā)現(xiàn)，在m9列中有“×”的P4行中，在m3列處也有“×”，因此可把m3列刪去。表1-3-13(b)簡化質蘊涵表mi

P

m0m6

m9m12

m15P1P2P3P4P5×××××表1-3-13(c)表1-3-13(c)為最簡，由表得出必要質蘊涵項為：P1，P2，P3，P4，P5共5個。（4）寫出簡化的邏輯表達式4.具有無關項的邏輯函數(shù)的化簡在實際的邏輯設計中，常常會出現(xiàn)這樣的情況：某些輸入組合不影響邏輯函數(shù)值，即與函數(shù)輸出無關。我們把這些輸入組合稱為無關項。無關項發(fā)生在以下兩種情況：(1)輸入變量的某些組合在正常情況下不會出現(xiàn)。例如，用三個邏輯變量A，B，C分別表示一臺電動機的正轉、反轉和停止命令，A=1表示正轉，B=1表示反轉，C=1表示停止。正常操作時，ABC的取值只能是001，010，100。而其他組合：000，011，101，110或111不允許出現(xiàn)，這五種組合就稱為約束項。(2)輸入變量的某些組合時，邏輯函數(shù)的值可以是“0”，也可以是“1”，并不影響電路的功能。例如，四位二進制共有16種代碼組合，如用其中的10種表示十進制的0～9十個數(shù)，其余的6種組合不使用，如果這些組合出現(xiàn)時，函數(shù)值是任意的，因此這些組合就稱為任意項。約束項和任意項統(tǒng)稱為無關項。既然無關項是不會出現(xiàn)的一種輸入組合，或者說，就是出現(xiàn)無關項，人們對其函數(shù)值是不關心的，那么此時函數(shù)值可以任意選?。夯蛘哌x“0”，或者選“1”。但具體取值時應以能使函數(shù)盡量簡化為原則。

例：設計一電路來判別用二進制編碼表示的十進制數(shù)是否大于等于5。電路的真值表見表1-3-14。當輸入小于5時，輸出0；當輸入大于等于5時輸出為1；當輸入代碼為ABCD=0101～1111時，輸出為“任意”，記作“φ”（也可表示為“×”，“－”，“d”）。ABCDF00000

10000

01000

11000

00100

10101

01101

11101

00011

10011

0101φ

1101φ

0011φ

1011φ

0111φ

1111φ表1-3-14由真值表作卡諾圖（圖1-3-21(a)）。圖1-3-21具有無關項的邏輯函數(shù)的化簡(a)把無關項對應的函數(shù)值當作1；為了化簡函數(shù)，可把這些“任意值”作為“1”來考慮，則簡化結果為

圖1-3-21具有無關項的邏輯函數(shù)的化簡(b)把無關項對應的函數(shù)值當作0如果把任意值作為“0”來處理（圖1-3-21(b)），則簡化結果為可見，前一表達式者比后一表達式要簡單。

合理使用無關項，可使設計得到簡化。對含有無關項的卡諾圖來說，它的畫圈原則為：①1塊必圈；②0塊必不圈；③φ塊（或記“×”塊）或圈，或不圈，以有利于化簡為原則。當然，每圈必包含一個新的“1”塊。對包含無關項的邏輯函數(shù)表達式來說，除需指出包含有哪些最小項外，還須指出含有哪些無關項，如上例中函數(shù)F可用如下形式表示：Σd后括號內(nèi)的為無關項序號。

例1-17化簡邏輯函數(shù)

解：畫卡諾圖，如圖1-3-22，圖中無關項的小方格內(nèi)填“×”，按以上原則畫圈后得這意味著在m2，m6，m14三個無關項的小方格內(nèi)填“1”，m10的小方格內(nèi)填“0”。圖1-3-22例1-17的卡諾圖包含無關項的邏輯函數(shù)用表格法化簡時，只需在列表和構成相鄰項時，把無關項考慮在內(nèi)，而在列質蘊涵表時則不把無關項列出，其余均與前述方法相同。最大項和標準或與表達式（最大項之積）1.最大項的定義設A1，A2，…，An是n個邏輯變量，M是n個變量之和，如果在M中，每一個變量都以原變量或反變量的形式出現(xiàn)一次，且僅出現(xiàn)一次，則稱M為這n個邏輯變量的一個最大項。對n個變量來說，共有2n個最大項。例如，對于邏輯變量A，B，C，由于n=3，所以有2n=8個最大項：

這8個最大項以及各自的真值表示于下表。0

0序號

最大項編號變量取值M0M1M2M3M5M6M7ABC000

0111111

110011

0111

1112010

11

01

11

1

1301