邏輯函數(shù)的卡諾圖法化簡(33)市公開課一等獎省賽課獲獎

12.5.1卡諾圖化簡基本原理[例]ABC與ABC

互為相鄰項(xiàng)。相鄰項(xiàng)能夠利用吸收律進(jìn)行合并，合并時可消去相異變量。F=

ABC+ABC

=

AB(C+C

)=AB。

不過，若

F=

ABCD+ABC+BC+ABC，顯然，該函數(shù)式難于找到相鄰項(xiàng)。P21

吸收定律看成一個整體

特點(diǎn)：兩個乘積項(xiàng)只有一個因子互為反變量，其余因子均相同，稱之為相鄰項(xiàng)，又稱邏輯相鄰項(xiàng)

。例題化簡以下函數(shù)：F=AB+AB=AF=ABC+ABC=AB2.4邏輯函數(shù)卡諾圖法化簡第1頁2（1）最小項(xiàng)：假如一個函數(shù)某個乘積項(xiàng)包含了函數(shù)全部變量，其中每個變量都以原變量或反變量形式出現(xiàn)，且僅出現(xiàn)一次，則這個乘積項(xiàng)稱為該函數(shù)一個標(biāo)準(zhǔn)積項(xiàng)，通常稱為最小項(xiàng)。

3個變量A、B、C可組成8個最小項(xiàng)：1、邏輯函數(shù)最小項(xiàng)及其性質(zhì)問題提出：邏輯函數(shù)

F=

ABC+ABC

，之所以易于看出它們乘積項(xiàng)是邏輯相鄰項(xiàng)，是因?yàn)樗鼈兠恳粋€乘積項(xiàng)中都包含了全部變量。而F=

ABCD+ABC+BC+ABC，每個乘積項(xiàng)沒有包含全部變量，所以邏輯相鄰關(guān)系不直觀。于是引入了最小項(xiàng)概念。2.4.2邏輯函數(shù)標(biāo)準(zhǔn)式——最小項(xiàng)表示式第2頁3（2）最小項(xiàng)表示方法：通慣用符號mi來表示最小項(xiàng)。下標(biāo)i確實(shí)定：把最小項(xiàng)中原變量記為1，反變量記為0，當(dāng)變量次序確定后，能夠按次序排列成一個二進(jìn)制數(shù)，則與這個二進(jìn)制數(shù)相對應(yīng)十進(jìn)制數(shù)，就是這個最小項(xiàng)下標(biāo)i。

3個變量A、B、C8個最小項(xiàng)能夠分別表示為：為了下面用卡諾圖法化簡第3頁4任何一個邏輯函數(shù)都能夠表示成唯一一組最小項(xiàng)之和，稱為標(biāo)準(zhǔn)與或表示式，也稱為最小項(xiàng)表示式2、邏輯函數(shù)標(biāo)準(zhǔn)式——最小項(xiàng)表示式為了下面用卡諾圖法化簡第4頁5

規(guī)律：任何一個邏輯函數(shù)都能展開成最小項(xiàng)表示式，變換方式有兩種：（1）邏輯函數(shù)——>真值表——>最小項(xiàng)表示式Y(jié)=ABY=AB+AB+AB=A(B+B)+AB=A+AB=A+B摩根定理:Y=AB=A+B比如:

假如列出了函數(shù)真值表，則只要將函數(shù)值為1那些最小項(xiàng)相加，便是函數(shù)最小項(xiàng)表示式。將真值表中函數(shù)值為0那些最小項(xiàng)相加，便可得到反函數(shù)最小項(xiàng)表示式。原函數(shù)反函數(shù)第5頁6m1＝ABCm5＝ABCm3＝ABCm2＝ABC為了下面用卡諾圖法化簡第6頁7（2）對于不是最小項(xiàng)表示式與或表示式，可利用代數(shù)法（去反、脫括號、配項(xiàng)（公式A＋A＝1和A(B+C)＝AB＋AC））展開成最小項(xiàng)表示式。為了下面用卡諾圖法化簡第7頁81、卡諾圖引入卡諾圖：是將任意兩個相鄰最小項(xiàng)在圖中位置也使之為相鄰。2.4.3用卡諾圖表示邏輯函數(shù)邏輯相鄰項(xiàng)

：兩個乘積項(xiàng)只有一個因子互為反變量，其余因子均相同，稱之為邏輯相鄰項(xiàng)。邏輯相鄰項(xiàng)能夠利用吸收律進(jìn)行合并，合并時可消去相異變量。不過邏輯相鄰項(xiàng)在位置上不一定相鄰，這給合并消元帶來了不便。

引入第8頁92、卡諾圖畫法1）二變量卡諾圖

每個2變量最小項(xiàng)有兩個最小項(xiàng)與它相鄰2）三變量卡諾圖

每個3變量最小項(xiàng)有3個最小項(xiàng)與它相鄰m0=AB，m1=AB，m3=AB它們是否相鄰？答：是第9頁10每個4變量最小項(xiàng)有4個最小項(xiàng)與它相鄰最左列最小項(xiàng)與最右列對應(yīng)最小項(xiàng)也是相鄰（可卷性或可折性）最上面一行最小項(xiàng)與最下面一行對應(yīng)最小項(xiàng)也是相鄰(可卷性或可折性)3）四變量卡諾圖卡諾圖構(gòu)圖思想：（見書中29頁）4個角也相鄰aaaa第10頁11

（1）邏輯函數(shù)是以真值表或者以最小項(xiàng)表示式給出：在卡諾圖上那些與給定邏輯函數(shù)最小項(xiàng)相對應(yīng)方格內(nèi)填入1，其余方格內(nèi)填入0。m1m4m3m7m6m11m15m143、用卡諾圖表示邏輯函數(shù)第11頁12

（2）邏輯函數(shù)以普通邏輯表示式給出：先將函數(shù)變換為與或表示式（無須變換為最小項(xiàng)之和形式），然后在卡諾圖上與每一個乘積項(xiàng)所包含那些最小項(xiàng)（該乘積項(xiàng)就是這些最小項(xiàng)公因子）相對應(yīng)方格內(nèi)填入1，其余方格內(nèi)填入0。變換為與或表示式含ＡＤ公因子含ＢＣ公因子第12頁13（3）假如求得了函數(shù)Ｙ反函數(shù)Ｙ，則對Ｙ中所包含各個最小項(xiàng)，在卡諾圖對應(yīng)方格內(nèi)填入0，其余方格內(nèi)填入1。變換為反函數(shù)DCBDCAABY+++=ABBDCDAC第13頁144、卡諾圖性質(zhì)（1）任何兩個（21個）標(biāo)1相鄰最小項(xiàng)，能夠合并為一項(xiàng)，并消去一個變量（消去互為反變量因子，保留公因子）。第14頁15（2）任何4個（22個）標(biāo)1相鄰最小項(xiàng)，能夠合并為一項(xiàng)，并消去2個變量。第15頁16ＡＤＢＤＢＤＢＤ第16頁17（3）任何8個（23個）標(biāo)1相鄰最小項(xiàng)，能夠合并為一項(xiàng)，并消去3個變量。ＤＢ第17頁18邏輯表示式或真值表卡諾圖1111111111000000002.4.4利用卡諾圖化簡邏輯函數(shù)第18頁19合并最小項(xiàng)①圈越大越好，但每個圈中標(biāo)１方格數(shù)目必須為個。②同一個方格可同時畫在幾個圈內(nèi)，但每個圈都要有新方格，不然它就是多出。③不能遺漏任何一個標(biāo)１方格。最簡與或表示式ＢＤＣＤＡＣＤ冗余項(xiàng)2233閱讀書中32頁例題2.5.1將化減后乘積項(xiàng)相與即得最簡與或表示式第19頁20①在有些情況下，最小項(xiàng)圈法不只一個，得到各個乘積項(xiàng)組成與或表示式各不相同，哪個是最簡，要經(jīng)過比較、檢驗(yàn)才能確定。ＡＣＤ＋ＢＣＤ＋ＡＢＣ＋ＡＤ不是最簡ＢＣＤ＋ＡＢＣ＋ＡＤ最簡兩點(diǎn)說明：第20頁21②在有些情況下，不一樣圈法得到與或表示式都是最簡形式。即一個函數(shù)最簡與或表示式不是唯一。ＡＣ＋ＡＢＤ＋ＡＢＣ＋ＢＣＤＡＣ＋ＡＢＤ＋ＡＢＣ＋ＡＢＤ第21頁22約束、禁止、任意、隨意、無關(guān)1、含有“約束”邏輯函數(shù)2.4.6含有“約束”邏輯函數(shù)化簡第22頁23邏輯問題分完全描述和非完全描述兩種。

完全描述就是函數(shù)每組變量不論取什么值，邏輯函數(shù)都有意義，邏輯函數(shù)與每個最小項(xiàng)都相關(guān)。

非完備描述就是在實(shí)際中變量一些取值式函數(shù)沒有意義或變量之間有一定制約關(guān)系。

完備描述邏輯問題ABCF00000101001110010111011100010010非完備描述邏輯問題010

1

000001010011100101110111FABC第23頁24例1：判斷一位十進(jìn)制數(shù)是否為偶數(shù)。不會出現(xiàn)不會出現(xiàn)不會出現(xiàn)不會出現(xiàn)不會出現(xiàn)不會出現(xiàn)

說明×111100111×111010110×110100101×110010100×101100011×10101001001001000011100010000YABCDYABCD非完備描述邏輯問題第24頁25輸入變量A，B，C，D取值為0000～1001時，邏輯函數(shù)Y有確定值，依據(jù)題意，偶數(shù)時為1，奇數(shù)時為0。

A，B，C，D取值為1010～1111情況，邏輯函數(shù)Y不會出現(xiàn)或不允許出現(xiàn)，對應(yīng)最小項(xiàng)屬于隨意項(xiàng)。用符號“φ”、“×”或“d”表示。在計算機(jī)中，專門有一條指令，叫做10進(jìn)制調(diào)整指令（DAA），在進(jìn)行BCD碼加法、減法運(yùn)算時，進(jìn)行加6和減6修正。即1010～1111狀態(tài)就不會出現(xiàn)。第25頁26例2：有三個邏輯變量A、B、C，它們分別表示一臺電動機(jī)正轉(zhuǎn)、反轉(zhuǎn)和停頓命令，A=1表示正轉(zhuǎn)，B=1表示反轉(zhuǎn)，C=1表示停頓。因?yàn)殡妱訖C(jī)任何時候只能執(zhí)行其中一個命令，所以不允許兩個以上變量同時為1。ABC取值只能是001、010、100當(dāng)中某一個，而不能是000、011、101、110、111中任何一個。所以，A、B、C是一組含有約束變量。

第26頁27

輸入變量ABC取值為001、010、100時，邏輯函數(shù)Y有確定值，依據(jù)題意，有任一命令（正轉(zhuǎn)、反轉(zhuǎn)和停頓）時為1，不然為0。ABC000111100010111000約束項(xiàng)這么，本例約束條件能夠表示為（即必須滿足）ABC+ABC+ABC+ABC+ABC≡0第27頁28約束項(xiàng)：在實(shí)際邏輯問題中，有些變量取值是不允許、不可能、不應(yīng)該出現(xiàn)，這些取值對應(yīng)最小項(xiàng)稱為約束項(xiàng)，有時又稱為禁止項(xiàng)、無關(guān)項(xiàng)、任意項(xiàng)，在卡諾圖或真值表中用×或Φ來表示。約束項(xiàng)性質(zhì)：對最小項(xiàng)來說，在任意取值條件下，每個最小項(xiàng)只有一組取值等于1；而對約束項(xiàng)來說，等于1這組取值不可能出現(xiàn)。所以約束項(xiàng)恒等于零。

約束條件：是一個值恒為0條件等式。反過來，假如某一最小項(xiàng)恒等于0，則該最小項(xiàng)就是約束項(xiàng)。任意項(xiàng)：

電路輸入變量一些組合值對輸出沒有影響，為任意項(xiàng)。無關(guān)項(xiàng)（Don'tCareTeam）：約束項(xiàng)和任意項(xiàng)總稱，用d表示。第28頁29無關(guān)項(xiàng)：與函數(shù)取值無關(guān)最小項(xiàng)。所以有時也將無關(guān)項(xiàng)叫約束項(xiàng)（禁止項(xiàng)）、任意項(xiàng)（隨意項(xiàng)）。

同例1(判斷一位十進(jìn)制數(shù)是否為偶數(shù))中任意項(xiàng)，如采取辦法，確保這些約束項(xiàng)(1010～1111)均為0或它們?yōu)?可能性就不會出現(xiàn)，這么再處理這些約束項(xiàng)時就能夠當(dāng)任意項(xiàng)處理了。

在進(jìn)行含有“約束”邏輯函數(shù)化簡時，約束項(xiàng)、禁止項(xiàng)、任意項(xiàng)、隨意項(xiàng)、無關(guān)項(xiàng)，都是一回事，對圈1有利，就取1；對圈0有利，就取0。第29頁30例1中含有隨意條件邏輯函數(shù)能夠表示成以下形式：或F=

約束條件為AB+AC=0AB+AC=0了解AB或AC同時為11項(xiàng)內(nèi)，F(xiàn)值為任意。m4m0m12m15m14m6m2m8m11m10m13第30頁31在邏輯函數(shù)化簡中，充分利用無關(guān)項(xiàng)能夠得到愈加簡單邏輯表示式，因而其對應(yīng)邏輯電路也更簡單。利用約束項(xiàng)受制約關(guān)系，我們能夠假設(shè)這些最小項(xiàng)不會被輸入，故在合并時，依據(jù)化簡需要，能夠任意設(shè)定這些約束項(xiàng)值為“0”或“1”，從而使函數(shù)更簡單。詳細(xì)地