第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ù)化簡(jiǎn)法 2.6 邏輯函數(shù)的卡諾圖化簡(jiǎn) 2.7 非完全描述邏輯函數(shù)的化簡(jiǎn),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ù)量的大小，而僅僅是作為一種符號(hào)，代表事物矛盾雙方的兩種狀態(tài)。,邏輯函數(shù)與普通代數(shù)中的函數(shù)相似，它是隨自變量的變化而變化的因變量。因此，如果用自變量和因變量分別表示某一事件發(fā)生的條件和結(jié)果，那么該事件的因果關(guān)系就可以用邏輯函數(shù)來描述。 數(shù)字電路的輸入、輸出量一般用高、低電平來表示，高、低電平也可以用二值邏輯1和0來表示。同時(shí)數(shù)字電路的輸出與輸入之間的關(guān)系是一種因果關(guān)系， 因此它可以用邏輯函數(shù)來描述，并稱為邏輯電路。對(duì)于任何一個(gè)電路，若輸入邏輯變量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é)果的所有條件同時(shí)具備時(shí)，結(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 與邏輯實(shí)例,表 2-1 與邏輯運(yùn)算真值表,與邏輯可以用邏輯表達(dá)式表示為 F=AB,在邏輯代數(shù)中，將與邏輯稱為與運(yùn)算或邏輯乘。

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

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

6、極管或門,3. 非運(yùn)算(邏輯反) 非運(yùn)算(邏輯反)是邏輯的否定：當(dāng)條件具備時(shí)，結(jié)果不會(huì)發(fā)生；而條件不具備時(shí)，結(jié)果一定會(huì)發(fā)生。例如，在圖2-7所示的開關(guān)電路中，只有當(dāng)開關(guān)A斷開時(shí)，燈F才亮，當(dāng)開關(guān)A閉合時(shí)，燈F反而熄滅。燈F的狀態(tài)總是與開關(guān)A的狀態(tài)相反。這種結(jié)果總是同條件相反的邏輯關(guān)系稱為非邏輯。非邏輯的真值表如表2-3所示，其邏輯表達(dá)式為,通常稱A為原變量，A為反變量。,圖 2-7 非邏輯實(shí)例,表 2-3 非邏輯運(yùn)算真值表,圖 2-8 非門邏輯符號(hào),圖 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) 以上定律可以用真值表證明，也可以用公式證明。例如， 證明加對(duì)乘的分配律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 三個(gè)重要規(guī)則 1. 代入規(guī)則 任何一個(gè)邏輯等式，如果將等式兩邊所出現(xiàn)的某一變量都代之以同一邏輯函數(shù)，則等式仍然成立，這個(gè)規(guī)則稱為代入規(guī)則。 由于邏輯函數(shù)與邏輯變量一樣，只有0、1兩種取值， 所以代入規(guī)則的正確性不難理解。運(yùn)用代入規(guī)則可以擴(kuò)大基本定律的運(yùn)用范圍。 例如，已知A+B=AB(反演律)，若用F=B+C代替等式中的B，則可以得到適用于多變量的反演律， 即,2. 反演規(guī)則 對(duì)于任意一個(gè)邏輯函數(shù)式F，如果將其表達(dá)式中所有的算符“”換成“+”， “+”換成“”，常量“0”換成“

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

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

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

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 與非門、 或非門和與或非門的邏輯符號(hào) (a) 與非門； (b) 或非門； (c) 與或非門,2. 異或和同或邏輯運(yùn)算 異或邏輯的含義是：當(dāng)兩個(gè)輸入變量相異時(shí)，輸出為1； 相同時(shí)輸出為0。 是異或運(yùn)算的符號(hào)。 異或運(yùn)算也稱模2加運(yùn)算。 異或邏輯的真值表如表2-5所示， 其邏輯表達(dá)式為,表 2-5 異或邏輯真值表,圖 2-11 異或門和同或門的邏輯符號(hào)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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