第2章邏輯代數(shù)

1、第2章 邏輯代數(shù)基礎(chǔ),2.1 邏輯代數(shù)的三種基本運(yùn)算 2.2 邏輯代數(shù)的基本定律和規(guī)則 2.3 復(fù)合邏輯 2.4 邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式 2.5 邏輯函數(shù)的代數(shù)化簡法 2.6 邏輯函數(shù)的卡諾圖化簡 2.7 非完全描述邏輯函數(shù)的化簡,2.1 邏輯代數(shù)的三種基本運(yùn)算,2.1.1 邏輯變量與邏輯函數(shù) 邏輯是指事物因果之間所遵循的規(guī)律。為了避免用冗繁的文字來描述邏輯問題，邏輯代數(shù)采用邏輯變量和一套運(yùn)算符組成邏輯函數(shù)表達(dá)式來描述事物的因果關(guān)系。 邏輯代數(shù)中的變量稱為邏輯變量，一般用大寫字母A、B、 C、表示，邏輯變量的取值只有兩種，即邏輯0和邏輯1。 0和1稱為邏輯常量。但必須指出，這里的邏輯0和1本身

2、并沒有數(shù)值意義，它們并不代表數(shù)量的大小，而僅僅是作為一種符號，代表事物矛盾雙方的兩種狀態(tài)。,邏輯函數(shù)與普通代數(shù)中的函數(shù)相似，它是隨自變量的變化而變化的因變量。因此，如果用自變量和因變量分別表示某一事件發(fā)生的條件和結(jié)果，那么該事件的因果關(guān)系就可以用邏輯函數(shù)來描述。 數(shù)字電路的輸入、輸出量一般用高、低電平來表示，高、低電平也可以用二值邏輯1和0來表示。同時數(shù)字電路的輸出與輸入之間的關(guān)系是一種因果關(guān)系， 因此它可以用邏輯函數(shù)來描述，并稱為邏輯電路。對于任何一個電路，若輸入邏輯變量A、 B、 C、 的取值確定后，其輸出邏輯變量F的值也被惟一地確定了，則可以稱F是A、 B、 C、 的邏輯函數(shù)， 并記為,

3、2.1.2 三種基本運(yùn)算,1. 與運(yùn)算(邏輯乘) 與運(yùn)算(邏輯乘)表示這樣一種邏輯關(guān)系：只有當(dāng)決定一事件結(jié)果的所有條件同時具備時，結(jié)果才能發(fā)生。例如在圖2-1所示的串聯(lián)開關(guān)電路中，只有在開關(guān)A和B都閉合的條件下，燈F才亮，這種燈亮與開關(guān)閉合的關(guān)系就稱為與邏輯。 如果設(shè)開關(guān)A、B閉合為1，斷開為0，設(shè)燈F亮為1，滅為0， 則F與A、B的與邏輯關(guān)系可以用表2-1所示的真值表來描述 所謂真值表，就是將自變量的各種可能的取值組合與其因變量的值一一列出來的表格形式。,圖 2 -1 與邏輯實例,表 2-1 與邏輯運(yùn)算真值表,與邏輯可以用邏輯表達(dá)式表示為 F=AB,在邏輯代數(shù)中，將與邏輯稱為與運(yùn)算或邏輯乘。

4、符號“”表示邏輯乘，在不致混淆的情況下，常省去符號“”。在有些文獻(xiàn)中，也采用、 及&等符號來表示邏輯乘。 實現(xiàn)與邏輯的單元電路稱為與門，其邏輯符號如圖2-2所示，其中圖(a)為我國常用的傳統(tǒng)符號，圖(b)為國外流行的符號，圖(c)為國標(biāo)符號(見附錄一)。圖2-3是一個2 輸入的二極管與門電路。圖中輸入端A、B的電位可以取兩種值：高電位+3V或低電位0V。設(shè)二極管為理想開關(guān)，并規(guī)定高電位為邏輯1，低電位為邏輯0，那么F與A、B之間邏輯關(guān)系的真值表與表2-1相同， 因而實現(xiàn)了F=AB的功能。,圖 2-2 與門的邏輯符號,圖 2-3 二極管與門,2. 或運(yùn)算(邏輯加),圖 2-4 或邏輯實例,表 2

5、-2 或邏輯運(yùn)算真值表,或邏輯可以用邏輯表達(dá)式表示為 F=A+B,或邏輯也稱為或運(yùn)算或邏輯加。符號“+”表示邏輯加。有些文獻(xiàn)中也采用、等符號來表示邏輯加。,實現(xiàn)或邏輯的單元電路稱為或門，其邏輯符號如圖2-5所示，其中圖(a)為我國常用的傳統(tǒng)符號，圖(b)為國外流行的符號， 圖(c)為國標(biāo)符號(見附錄一)。 圖2-6是一個 2 輸入的二極管或門電路。圖中輸入端A、 B的電位可以取兩種值： 高電位+3V或低電位0 V。 設(shè)二極管為理想開關(guān)，并規(guī)定高電位為邏輯1，低電位為邏輯0，則F與A、B之間邏輯關(guān)系的真值表與表2-2相同， 因此實現(xiàn)了F=A+B的功能。,圖 2-5 或門的邏輯符號,圖 2-6 二

6、極管或門,3. 非運(yùn)算(邏輯反) 非運(yùn)算(邏輯反)是邏輯的否定：當(dāng)條件具備時，結(jié)果不會發(fā)生；而條件不具備時，結(jié)果一定會發(fā)生。例如，在圖2-7所示的開關(guān)電路中，只有當(dāng)開關(guān)A斷開時，燈F才亮，當(dāng)開關(guān)A閉合時，燈F反而熄滅。燈F的狀態(tài)總是與開關(guān)A的狀態(tài)相反。這種結(jié)果總是同條件相反的邏輯關(guān)系稱為非邏輯。非邏輯的真值表如表2-3所示，其邏輯表達(dá)式為,通常稱A為原變量，A為反變量。,圖 2-7 非邏輯實例,表 2-3 非邏輯運(yùn)算真值表,圖 2-8 非門邏輯符號,圖 2-9 三極管非,2.2 邏輯代數(shù)的基本定律和規(guī)則,2.2.1 基本定律,1. 變量和常量的關(guān)系式 邏輯變量的取值只有0和1，根據(jù)三種基本運(yùn)算

7、的定義，可推得以下關(guān)系式。 0-1律： A0 =0 A+1 =1 自等律：A1=A A+0=A 重疊律：AA=A A+A=A 互補(bǔ)律：AA=0 A+A=1,2. 與普通代數(shù)相似的定律 交換律 AB=BA A+B=B+A 結(jié)合律 (AB)C=A(BC) (A+B)+C=A+(B+C) 分配律 A(B+C)=AB+AC A+BC=(A+B)(A+C) 以上定律可以用真值表證明，也可以用公式證明。例如， 證明加對乘的分配律A+BC=(A+B)(A+C)。 證： (A+B)(A+C) =AA+AB+AC+BC =A+AB+AC+BC =A(1+B+C)+BC=A+BC 因此有 A+BC=(A+B)(A

8、+C),3. 邏輯代數(shù)中的特殊定律 反演律(De Morgan定律)：,還原律：,表 2-4 反演律證明,2.2.2 三個重要規(guī)則 1. 代入規(guī)則 任何一個邏輯等式，如果將等式兩邊所出現(xiàn)的某一變量都代之以同一邏輯函數(shù)，則等式仍然成立，這個規(guī)則稱為代入規(guī)則。 由于邏輯函數(shù)與邏輯變量一樣，只有0、1兩種取值， 所以代入規(guī)則的正確性不難理解。運(yùn)用代入規(guī)則可以擴(kuò)大基本定律的運(yùn)用范圍。 例如，已知A+B=AB(反演律)，若用F=B+C代替等式中的B，則可以得到適用于多變量的反演律， 即,2. 反演規(guī)則 對于任意一個邏輯函數(shù)式F，如果將其表達(dá)式中所有的算符“”換成“+”， “+”換成“”，常量“0”換成“

9、1”，“1”換成“0”，原變量換成反變量，反變量換成原變量，則所得到的結(jié)果就是 。 稱為原函數(shù)F的反函數(shù)，或稱為補(bǔ)函數(shù)。 反演規(guī)則是反演律的推廣，運(yùn)用它可以簡便地求出一個函數(shù)的反函數(shù)。 例如：,若,則,若,則,運(yùn)用反演規(guī)則時應(yīng)注意兩點(diǎn)： 不能破壞原式的運(yùn)算順序先算括號里的，然后按“先與后或”的原則運(yùn)算。 不屬于單變量上的非號應(yīng)保留不變。,3. 對偶規(guī)則 對于任何一個邏輯函數(shù)，如果將其表達(dá)式F中所有的算符“”換成“+”, “+”換成“”，常量“0”換成“1”，“1”換成“0”， 而變量保持不變，則得出的邏輯函數(shù)式就是F的對偶式，記為F(或F*)。 例如：,以上各例中F是F的對偶式。不難證明F也是

10、F對偶式。 即F與F互為對偶式。,任何邏輯函數(shù)式都存在著對偶式。 若原等式成立， 則對偶式也一定成立。即，如果F=G,則F=G。這種邏輯推理叫做對偶原理，或?qū)ε家?guī)則。 必須注意，由原式求對偶式時，運(yùn)算的優(yōu)先順序不能改變， 且式中的非號也保持不變。 觀察前面邏輯代數(shù)基本定律和公式，不難看出它們都是成對出現(xiàn)的， 而且都是互為對偶的對偶式。 例如，已知乘對加的分配律成立，即A(B+C)=AB+AC，根據(jù)對偶規(guī)則有，A+BC=(A+B)(A+C)，即加對乘的分配律也成立。,2.2.3 若干常用公式,1. 合并律,在邏輯代數(shù)中，如果兩個乘積項分別包含了互補(bǔ)的兩個因子(如B和B)， 而其它因子都相同，那么

11、這兩個乘積項稱為相鄰項。 合并律說明，兩個相鄰項可以合并為一項， 消去互補(bǔ)量。,2. 吸收律 A+AB=A 證： A+AB=A(1+B)=A1=A 該公式說明，在一個與或表達(dá)式中，如果某一乘積項的部分因子(如AB項中的A)恰好等于另一乘積項(如A)的全部， 則該乘積項(AB)是多余的。,證：,該公式說明，在一個與或表達(dá)式中，如果一個乘積項(如A)取反后是另一個乘積項(如 的因子，則此因子 是多余的。,證：,推論：,該公式及推論說明，在一個與或表達(dá)式中，如果兩個乘積項中的部分因子互補(bǔ)(如AB項和AC項中的A和A)，而這兩個乘積項中的其余因子(如B和C)都是第三個乘積項中的因子， 則這個第三項是多

12、余的。,2.3 復(fù) 合 邏 輯,2.3.1 復(fù)合邏輯運(yùn)算和復(fù)合門,1. 與非、 或非、 與或非邏輯運(yùn)算 與非邏輯運(yùn)算是與運(yùn)算和非運(yùn)算的組合， 即,或非邏輯運(yùn)算是或運(yùn)算和非運(yùn)算的組合， 即,與或非邏輯運(yùn)算是與、或、非三種運(yùn)算的組合，即,圖 2-10 與非門、 或非門和與或非門的邏輯符號 (a) 與非門； (b) 或非門； (c) 與或非門,2. 異或和同或邏輯運(yùn)算 異或邏輯的含義是：當(dāng)兩個輸入變量相異時，輸出為1； 相同時輸出為0。 是異或運(yùn)算的符號。 異或運(yùn)算也稱模2加運(yùn)算。 異或邏輯的真值表如表2-5所示， 其邏輯表達(dá)式為,表 2-5 異或邏輯真值表,圖 2-11 異或門和同或門的邏輯符號

13、(a) 異或門； (b) 同或門,同或邏輯與異或邏輯相反，它表示當(dāng)兩個輸入變量相同時輸出為1；相異時輸出為0。 是同或運(yùn)算的符號。 同或邏輯的真值表如表2-6所示，其邏輯表達(dá)式為,表 2-6 同或邏輯真值表,由定義和真值表可見，異或邏輯與同或邏輯互為反函數(shù)，即,不僅如此，它們還互為對偶式。如果 ，G=AB， 不難證明F=G, G=F。 因此可以將“ ”作為“”的對偶符號，反之亦然。由以上分析可以看出， 兩變量的異或函數(shù)和同或函數(shù)既互補(bǔ)又對偶，這是一對特殊函數(shù)。,表 2-7 常用異或和同或運(yùn)算公式,此外，,(A的個數(shù)為偶數(shù)),(A的個數(shù)為奇數(shù)),對于一個代數(shù)系統(tǒng)， 若僅用它所定義的一組運(yùn)算符號就

14、能解決所有的運(yùn)算問題， 則稱這一組符號是一個完備的集合， 簡稱完備集。 在邏輯代數(shù)中， 與、 或、 非是三種最基本的運(yùn)算，n變量的所有邏輯函數(shù)都可以用n個變量及一組邏輯運(yùn)算符“、 +、 -”來構(gòu)成， 因此稱“、 +、 -”運(yùn)算符是一組完備集。 ,2.3.2 邏輯運(yùn)算符的完備性,但是“與、 或、 非”并不是最好的完備集， 因為它實現(xiàn)一個函數(shù)要使用三種不同規(guī)格的邏輯門。 實際上從反演律可以看出， 有了“與”和“非”可得出“或”， 有了“或”和“非”可得出“與”， 因此“與非”、 “或非”、 “與或非”運(yùn)算中的任何一種都能單獨(dú)實現(xiàn)“與、 或、 非”運(yùn)算， 這三種復(fù)合運(yùn)算每種都是完備集， 而且實現(xiàn)函數(shù)

15、只需要一種規(guī)格的邏輯門， 這就給設(shè)計工作帶來許多方便。,例如，任何一個邏輯函數(shù)式都可以通過邏輯變換寫成以下五種形式：,與或式,或與式,與非與非式,或非或非式,與或非式,圖 2-12 邏輯函數(shù)的五種形式,2.4 邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式,2.4.1 最小項和最小項表達(dá)式,1. 最小項 n個變量的最小項是n個變量的“與項”，其中每個變量都以原變量或反變量的形式出現(xiàn)一次。 兩個變量A、B可以構(gòu)成四個最小項 ，三個變量A、B、C可以構(gòu)成八個最小項 ，可見n個變量的最小項共有2n個。,表 2-8 三變量邏輯函數(shù)的最小項,最小項具有以下性質(zhì)： n變量的全部最小項的邏輯和恒為1，即, 任意兩個不同的最小項的邏

16、輯乘恒為0， 即, n變量的每一個最小項有n個相鄰項。例如，三變量的某一最小項 有三個相鄰項： 。這種相鄰關(guān)系對于邏輯函數(shù)化簡十分重要。,2. 最小項表達(dá)式標(biāo)準(zhǔn)與或式 如果在一個與或表達(dá)式中，所有與項均為最小項， 則稱這種表達(dá)式為最小項表達(dá)式，或稱為標(biāo)準(zhǔn)與或式、標(biāo)準(zhǔn)積之和式。 例如：,是一個三變量的最小項表達(dá)式， 它也可以簡寫為,任何一個邏輯函數(shù)都可以表示為最小項之和的形式： 只要將真值表中使函數(shù)值為1的各個最小項相或，便可得出該函數(shù)的最小項表達(dá)式。 由于任何一個函數(shù)的真值表是惟一的，因此其最小項表達(dá)式也是惟一的。,表 2-9 真值表,從真值表可知，當(dāng)A、B、C取值分別為001、010、 10

17、0、111時，F(xiàn)為1，因此最小項表達(dá)式由這四種組合所對應(yīng)的最小項進(jìn)行相或構(gòu)成，即,表 2-10 三變量邏輯函數(shù)的最大項,2.4.2 最大項和最大項表達(dá)式 1. 最大項 n個變量的最大項是n個變量的“或項”，其中每一個變量都以原變量或反變量的形式出現(xiàn)一次。 n個變量可以構(gòu)成2n個最大項。最大項用符號Mi表示(見表2-10)。與最小項恰好相反，對于任何一個最大項，只有一組變量取值使它為0，而變量的其余取值均使它為1。 例如，或項 僅和變量取值101對應(yīng)，故用M5表示。,最大項具有以下性質(zhì)： n變量的全部最大項的邏輯乘恒為0，即, n變量的任意兩個不同的最大項的邏輯和必等于1，即, n變量的每個最大

18、項有n個相鄰項。例如，三變量的某一最大項 有三個相鄰項：,2. 最小項與最大項之間的關(guān)系,變量數(shù)相同，編號相同的最小項和最大項之間存在互補(bǔ)關(guān)系，即,例如：,3. 最大項表達(dá)式標(biāo)準(zhǔn)或與式 在一個或與式中，如果所有的或項均為最大項，則稱這種表達(dá)式為最大項表達(dá)式，或稱為標(biāo)準(zhǔn)或與式、標(biāo)準(zhǔn)和之積表達(dá)式。 如果一個邏輯函數(shù)的真值表已給出，要寫出該函數(shù)的最大項表達(dá)式，可以先求出該函數(shù)的反函數(shù) ，并寫出 的最小項表達(dá)式，然后將 再求反，利用mi和Mi的互補(bǔ)關(guān)系便得到最大項表達(dá)式。例如，已知表2-11的真值表，可得,表 2-11 真值表,可見，最大項表達(dá)式是真值表中使函數(shù)值為0的各個最大項相與。,得出結(jié)論：任何

19、一個邏輯函數(shù)既可以用最小項表達(dá)式表示，也可以用最大項表達(dá)式表示。如果將一個n變量函數(shù)的最小項表達(dá)式改為最大項表達(dá)式時，其最大項的編號必定都不是最小項的編號， 而且這些最小項的個數(shù)和最大項的個數(shù)之和為2n。,2.5 邏輯函數(shù)的代數(shù)化簡法,1. 并項法,利用公式AB+AB=A將兩項合并成一項，并消去互補(bǔ)因子。如：,2. 吸收法 利用吸收律 A+AB=A、 和 吸收(消去)多余的乘積項或多余的 因子。 如：,(添多余項AB),(去掉多余項AB),2.6 邏輯函數(shù)的卡諾圖化簡,2.6.1 卡諾圖的構(gòu)成,在邏輯函數(shù)的真值表中， 輸入變量的每一種組合都和一個最小項相對應(yīng)，這種真值表也稱最小項真值表?？ㄖZ圖

20、就是根據(jù)最小項真值表按一定規(guī)則排列的方格圖。,表 2-12 三變量最小項,圖 2-14 四變量、五變量K圖,圖 2-13 三變量K圖,由圖2-14可以看出，K圖具有如下特點(diǎn)： n變量的卡諾圖有2n個方格，對應(yīng)表示2n個最小項。每當(dāng)變量數(shù)增加一個，卡諾圖的方格數(shù)就擴(kuò)大一倍。 卡諾圖中任何幾何位置相鄰的兩個最小項，在邏輯上都是相鄰的。由于變量取值的順序按格雷碼排列，保證了各相鄰行(列)之間只有一個變量取值不同，從而保證畫出來的最小項方格圖具有這一重要特點(diǎn)。 所謂幾何相鄰，一是相接，即緊挨著； 二是相對，即任意一行或一列的兩頭；三是相重， 即對折起來位置重合。 所謂邏輯相鄰，是指除了一個變量不同外其

21、余變量都相同的兩個與項。,例如圖2-14(b)五變量K圖中，m5在幾何位置上與m4、m7、m1、m13、m21相鄰，因此 與 相鄰， 此外還與 和 分別相鄰， 即m5有五個相鄰項?？梢娍ㄖZ圖也反映了n變量的任何一個最小項有n個相鄰項這一特點(diǎn)。 卡諾圖的主要缺點(diǎn)是隨著輸入變量的增加圖形迅速復(fù)雜， 相鄰項不那么直觀，因此它只適于用來表示6個以下變量的邏輯函數(shù)。,2.6.2 邏輯函數(shù)的卡諾圖表示法,1. 給出邏輯函數(shù)的最小項表達(dá)式 只要將構(gòu)成邏輯函數(shù)的最小項在卡諾圖上相應(yīng)的方格中填1，其余的方格填0(或不填)，則可以得到該函數(shù)的卡諾圖。也就是說，任何一個邏輯函數(shù)都等于其卡諾圖上填1的那些最小項之和。

22、 例如，用卡諾圖表示函數(shù) 時，只需在三變量卡諾圖中將m0、m3、m4、m6處填1，其余填0(或不填)，如圖2-15(a)所示。 同理， 的卡諾圖如圖 2-15(b)所示。,圖 2-15 F1、2的卡諾圖,2. 給出邏輯函數(shù)的一般與或式 將一般與或式中每個與項在卡諾圖上所覆蓋的最小項處都填1，其余的填0(或不填)，就可以得到該函數(shù)的卡諾圖。 例如，用卡諾圖表示函數(shù) 時， 先確定使每個與項為1的輸入變量取值， 然后在該輸入變量取值所對應(yīng)的方格內(nèi)填1。 ：當(dāng)ABCD=101(表示可以為0，也可以為1)時該與項為1，在卡諾圖上對應(yīng)兩個方格(m10、m11)處填1。,：當(dāng)ABCD=001時該與項為1，對

23、應(yīng)兩個方格(m2、m3)處填1。 D：當(dāng)ABCD=1時該與項為1，對應(yīng)八個方格(m1、m3、m5、m7、m9、m11、m13、m15)處填1。 AD：當(dāng)ABCD=11時該與項為1，對應(yīng)四個方格(m9、 m11、m13、m15)處填1。 某些最小項重復(fù)，只需填一次即可。,圖 2-16 F3的卡諾圖,3. 給出邏輯函數(shù)的最大項表達(dá)式 只要將構(gòu)成邏輯函數(shù)的最大項在卡諾圖相應(yīng)的方格中填0，其余的方格填1即可。也就是說，任何一個邏輯函數(shù)都等于其卡諾圖上填0的那些最大項之積。 例如，函數(shù) 的卡諾圖如圖2-17所示。 必須注意，在卡諾圖中最大項的編號與最小項編號是一致的，但對應(yīng)輸入變量的取值是相反的。,圖

24、2-17 F4的卡諾圖,4. 給出邏輯函數(shù)的一般或與式 將一般或與式中每個或項在卡諾圖上所覆蓋的最大項處都填0，其余的填1即可。 例如，將函數(shù) 填入卡諾圖時，先確定使每個或項為0時輸入變量的取值，然后在該取值所對應(yīng)的方格內(nèi)填0。,當(dāng)ABC=10時，該或項為0，對應(yīng)兩個方格,(M4、M6)處填0。,當(dāng)ABC=10時，該或項為0，對應(yīng)兩個方格,(M2、M6)處填0。,某些最大項重復(fù)，填一次即可。F5的卡諾圖如圖2-18所示。,圖 2-18 F5的卡諾圖,2.6.3 最小項合并規(guī)律,在卡諾圖中，凡是幾何位置相鄰的最小項均可以合并。 兩個相鄰最小項合并為一項，消去一個互補(bǔ)變量。在卡諾圖上該合并圈稱為單

25、元圈，它所對應(yīng)的與項由圈內(nèi)沒有變化的那些變量組成，可以直接從卡諾圖中讀出。例如，圖2-19(a) 中m1、m3合并為 ，圖2-19(b)中m0、m4合并為 。 任何兩個相鄰的單元K圈也是相鄰項，仍然可以合并，消去互補(bǔ)變量。因此，如果K圈越大，消去的變量數(shù)就越多。,圖2-19(c)、 (d)表示四個相鄰最小項合并為一項，消去了兩個變量，合并后積項由K圈對應(yīng)的沒有變化的那些變量組成。圖2-19(c)中m0、m1、m4、m5合并為 ，圖2-19(d)中m0、m2、m8、m10合并為 ，m5、m7、m13、m15合并為BD， m12、m13、m15、m14合并為AB。 圖2-19(e)表示八個相鄰最小

26、項合并為一項，消去了三個變量，即,綜上所述， 最小項合并有以下特點(diǎn)： 任何一個合并圈(即卡諾圈)所含的方格數(shù)為2i個。 必須按照相鄰規(guī)則畫卡諾圈，幾何位置相鄰包括三種情況：一是相接，即緊挨著的方格相鄰；二是相對，即一行(或一列)的兩頭、兩邊、四角相鄰；三是相重，即以對稱軸為中心對折起來重合的位置相鄰。 2m個方格合并，消去m個變量。合并圈越大，消去的變量數(shù)越多。 需要指出，上述最小項的合并規(guī)則，對最大項的合并同樣是適用的。只是因為最大項是與函數(shù)的0值相對應(yīng)，在卡諾圖中則與0格對應(yīng)，因此，最大項的合并在卡諾圖中是相鄰的0格圈在一起。,圖 2-19 最小項合并規(guī)律,2.6.4 用卡諾圖化簡邏輯函數(shù)

27、,1. 求最簡與或式 在卡諾圖上以最少的卡諾圈數(shù)和盡可能大的卡諾圈覆蓋所有填1的方格， 即滿足最小覆蓋，就可以求得邏輯函數(shù)的最簡與或式。 化簡的一般步驟是： 畫出邏輯函數(shù)的K圖。 先從只有一種圈法的最小項開始圈起，K圈的數(shù)目應(yīng)最少(與項的項數(shù)最少)，K圈應(yīng)盡量大(對應(yīng)與項中變量數(shù)最少)。, 將每個K圈寫成相應(yīng)的與項， 并將它們相或， 便得到最簡與或式。 圈圈時應(yīng)注意，根據(jù)重疊律(A+A=A)，任何一個1格可以多次被圈用，但如果在某個K圈中所有的1格均已被別的K圈圈過，則該圈為多余圈。為了避免出現(xiàn)多余圈， 應(yīng)保證每個K圈內(nèi)至少有一個1格只被圈一次。,【例 2-1】 求F= m(1, 3, 4,

28、5, 10, 11, 12, 13)的最簡與或式。 解： 畫出F的K圖(見圖2-20)。,圖 2-20 例2-1的卡諾圖, 畫K圈。按照最小項合并規(guī)律，將可以合并的最小項分別圈起來。 根據(jù)化簡原則，應(yīng)選擇最少的K圈和盡可能大的K圈覆蓋所有的1格。首先選擇只有一種圈法的BC，剩下四個1格(m1、m3、m10、m11)用兩個K圈 覆蓋。 可見一共只要用三個K圈即可覆蓋全部1格。 寫出最簡式。,【例 2-2】,求,的最簡與或式。,解： 畫出F的K圖。給出的F為一般與或式，將每個與項所覆蓋的最小項都填1，K圖如圖2-21所示。,圖 2-21 例2-2的卡諾圖, 畫K圈化簡函數(shù)。 寫出最簡與或式。 本例

29、有兩種圈法， 都可以得到最簡式。 按圖2-21(a)圈法：,按圖2-21(b)圈法：,該例說明，邏輯函數(shù)的最簡式不是惟一的。,【例 2-3】求 的最簡與或式。 解： 畫F的K圖。 這是一個五變量邏輯函數(shù)，按五變量K圖中的編號填圖，得出F的K圖如圖2 - 22所示。,圖 2-22 例2-3的卡諾圖, 畫K圈化簡函數(shù)。 先找只有一種圈法的最小項：, 寫出最簡式。,如何判斷得到的函數(shù)式是否為最簡式呢? 下面從蘊(yùn)含項的概念討論最簡式問題： 蘊(yùn)含項(Implicant)。組成邏輯函數(shù)的每一個與項(積項)稱為該函數(shù)的蘊(yùn)含項。它可以是最小項，也可以是合并項。, 本原蘊(yùn)含項(Prime Implicant)。

30、如果邏輯函數(shù)的一個蘊(yùn)含項再也不能同該函數(shù)的其它蘊(yùn)含項合并組成變量數(shù)更少的蘊(yùn)含項，則稱該蘊(yùn)含項為本原蘊(yùn)含項。實際上它對應(yīng)著卡諾圖中不能再擴(kuò)大的合并項， 即最大卡諾圈。 實質(zhì)本原蘊(yùn)含項(Essential Prime Implicant)。不能被其它蘊(yùn)含項所包含的本原蘊(yùn)含項稱為實質(zhì)本原蘊(yùn)含項。它對應(yīng)著卡諾圖中必不可少的最大卡諾圈，該圈至少包含了一個只有一種圈法的最小項。,例如，已知邏輯函數(shù)F1、F2的卡諾圖分別如圖2-23(a)、(b)所示，化簡F1時只需用 3 個最大的K圈就可以覆蓋全部1格，如果用四個K圈肯定有一個多余圈。從圖2-23(a)中看出，合并項AC為多余項，因為該圈中每個 1 格被圈

31、了兩次。因此可得出最簡與或式為,化簡圖2-23(b)的F2，只用六個最大的K圈覆蓋所有的 1 格，觀察每一個K圈都有一個 1 格只被圈過一次，因此這六個K圈都必須存在，最簡與或式為,圖 2-23 F1、F2的化簡K圖,2. 求最簡或與式 任何一個邏輯函數(shù)既可以等于其卡諾圖上填1的那些最小項之和，也可以等于其卡諾圖上填0的那些最大項之積， 因此，如果要求出某函數(shù)的最簡或與式， 可以在該函數(shù)的卡諾圖上合并那些填0的相鄰項。這種方法簡稱為圈0合并， 其化簡步驟及化簡原則與圈1合并類同，只要按圈逐一寫出或項， 然后將所得的或項相與即可。但需注意，或項由K圈對應(yīng)的沒有變化的那些變量組成，當(dāng)變量取值為0時

32、寫原變量， 取值為1時寫反變量。,【例 2-4】 求,的最簡或與式。,解： 畫出F的K圖(見圖2-24)。 圈K圈。圈0合并，其規(guī)律與圈1相同，即K圈的數(shù)目應(yīng)最少，K圈所覆蓋的0格應(yīng)盡可能多。本例用三個K圈覆蓋所有0格。 寫出最簡或與式。,圖 2-24 例2-4的卡諾圖,【例 2-5】 求,的最簡或與式。,解：, 畫出F的K圖。本例給出的F為一般或與式，因此將每個或項所覆蓋的最大項都填0，就可以得到F的K圖如圖2-25所示。 圈K圈化簡函數(shù)。 寫出最簡或與式。,當(dāng)需要將邏輯函數(shù)化為最簡與或非式時， 也可以采用合并0格的方式，即在卡諾圖上圈0格，先求出 的最簡與或式， 然后根據(jù)F=F再求出F的最簡與或非式。,圖 2-25 例2-5的卡諾圖,2.7 非完全描述邏輯函數(shù)的化簡,2.7.1 非完全描述的邏輯函數(shù),邏輯問題分為完全描述和非完全描述兩種。如果對于輸入變量的每一組取值，邏輯函數(shù)都有確定的值，則稱這類函數(shù)為完全描述邏輯函數(shù)。如果對于輸