您好，歡迎來電子發(fā)燒友網(wǎng)！請登錄，新用戶？[免費注冊]

網(wǎng)站首頁最新更新資料下載技術(shù)應(yīng)用元器件電路圖網(wǎng)站導(dǎo)航

圖書首頁

當前位置：電子發(fā)燒友網(wǎng) > 圖書頻道 > 電子 > 《數(shù)字電子技術(shù)》 > 第2章邏輯函數(shù)及其化簡

第3節(jié) 邏輯函數(shù)的化簡

2.3.1邏輯函數(shù)的標準形式

邏輯函數(shù)表達式有與-或表達式和或-與表達式兩種基本形式。

所謂與-或表達式是指一個邏輯表達式中包含著若干個與項，每個與項中有一個或多個以原變量或反變量形式出現(xiàn)的變量名，所有這些與項相或就表示了一個邏輯函數(shù)。如，、、等均為與項，用這些與項就可以構(gòu)成邏輯函數(shù)的與-或表達式。即：

這個表達式有3個與項，有時我們也將與稱之為“乘積”項。于是，上述表達式可看成是由3個“乘積”項通過求“和”形成的，這樣的表達式又稱為“積之和”表達式。

所謂或-與表達式是指一個邏輯表達式中包含著若干個或項，每個或項中有任意個以原變量或反變量形式出現(xiàn)的變量名，所有這些或項相與就表示一個邏輯函數(shù)。如，、、等均為或項，用這些或項就可以構(gòu)成或-與表達式。即：

這個表達式中有3個或項，有時我們也將或項稱之為“和”項。于是，上述表達式可看成是由3個“和”項通過求“積”形成的，這樣的表達式又稱為“和之積”表達式。

任意的一個邏輯表達式，例如：

這種表示形式既不是與-或表達式，也不是或-與表達式，但可以通過“配項”然后應(yīng)用分配律轉(zhuǎn)換成與-或表達式或者或-與表達式。

一、最小項標準式

最小項標準式也稱為與-或標準式。

對于一個任意的邏輯函數(shù)表達式，例如：

（2.3.1）

其表達式并不是唯一的。根據(jù)上面介紹的分配律以及基本公式等概念，可以將表達式寫成與-或表達式：

（2.3.2）

利用公式，(2.3.2)式又可以變換為：

（2.3.3）

式(2.3.3)所表示的與-或表達式稱為最小項標準式，（2.3.3）式中的與項稱為三個變量A、B、C的最小項。

可以看出，所謂的最小項是一種與項，這種與項包含了所有的輸入變量。每個輸入變量或以原變量或以反變量的形式出現(xiàn)在與項中，且在每個與項中僅出現(xiàn)一次。

三個輸入變量為A、B、C最多可組成八個最小項：、、、、、、、。變量的其它不同的組合，如：、、等都不滿足最小項的條件，所以均不是最小項。

為了敘述和書寫方便，通常用表示最小項。如果最小項（即：與項）中的原變量記為1，反變量記為0，且當變量順序確定后，1和0按順序排列成一個二進數(shù)，則與這二進數(shù)相對應(yīng)的十進數(shù)就是最小項的下標i。表2.3.1列出了A、B、C三個變量函數(shù)可能存在的全部最小項。

表2.3.1 三個變量函數(shù)中的最小項和最大項
變量取值組合			對應(yīng)最小項及編號		對應(yīng)最大項及編號
A	B	C	最小項	編號	最大項	編號
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

因此，(2.3.1)式表示的邏輯函數(shù)可寫成：

(2.3.4)

若借數(shù)學(xué)中常用的符號“”表示累計的邏輯“加”，則邏輯函數(shù)可寫成如下形式：

（2.3.5）

其中,符號“”表示各項求或，后面括號內(nèi)的數(shù)字表示函數(shù)的各最小項。等式左邊括號內(nèi)的字母表所有的變量名和它的排列順序，變量的順序是很重要的，一旦確定后，就不能隨意改變，否則會造成表達式的錯誤。

上述例子說明，一個任意的邏輯函數(shù)均可表示為若干最小項之“和”。邏輯函數(shù)的與-或標準式就是函數(shù)的最小項標準式。

當邏輯函數(shù)用最小項標準式表示時，就能方便地列出邏輯函數(shù)及其反函數(shù)的真值表，上述例子的真值表如表2.3.2所示。

表2.3.2 函數(shù)及其反函數(shù)的真值表
A	B	C	Y
0	0	0	0	1
0	0	1	1	0
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	1	0
1	1	0	0	1
1	1	1	0	1

由表2.3.2所示真值表很容易寫出其反函數(shù)的表達式

可以看出,對于A、B、C三個變量來說,可以形成個最小項。并且，若這些最小項不包含在的與-或標準式中，則必然包含在的與-或標準式中。這個結(jié)論可以推廣到個輸入變量的情況，個輸入變量有個輸入組合，即有個最小項。對于個輸入變量的邏輯函數(shù)Y，根據(jù)邏輯代數(shù)基本定律，有

(2.3.6)

而：

(2.3.7)

所以有：

(2.3.8)

上式表明：個輸入變量所有最小項的“和”恒等于1

二、最大項標準式

最大項標準式也稱為或-與標準式。

對于一個任意的邏輯函數(shù)表達式，例如：

(2.3.9)

其表達式并不是唯一的。根據(jù)上面介紹的分配律以及基本公式等概念，可以將表達式寫成或-與表達式：

(2.3.10)

利用公式，(2.3.10)式又可改寫為：

(2.3.11)

式(2.3.11)所表示的或-與表達式稱為最大項標準式，（2.3.11）式中的或項稱為三個變量A、B、C的最大項。

可以看出，所謂的最大項是一種或項，這種或項包含了所有的輸入變量。每個輸入變量或以原變量或以反變量的形式出現(xiàn)在或項中，且在每個或項中僅出現(xiàn)一次。

三個輸入變量為A、B、C最多可組成八個最大項：，，，，，，。變量的其它不同的組合，如：，，等都不滿足最大項的條件，所以均不是最大項。

為了敘述和書寫方便，通常用表示最大項。如果最大項（即：或項）中的原變量記為0，反變量記為1，且當變量順序確定后，1和0按順序排列成一個二進數(shù)，則與這二進數(shù)相對應(yīng)的十進數(shù)就是最大項的下標i。表2.3.1列出了A、B、C三個變量函數(shù)可能存在的全部最大項。

因此，(2.3.11)式表示的邏輯函數(shù)可寫成：

(2.3.12)

若借數(shù)學(xué)中常用的符號“”表示累計的邏輯“乘”，則(2.3.12)式可寫成如下形式：

（2.3.13）

其中,符號“”表示各項求與，后面括號內(nèi)的數(shù)字表示函數(shù)的各最大項。等式左邊括號內(nèi)的字母表所有的變量名和它的排列順序，變量的順序是很重要的，一旦確定后，就不能隨意改變，否則會造成表達式的錯誤。

上述例子說明，一個任意的邏輯函數(shù)均可表示為若干最大項之“乘積”。邏輯函數(shù)的或-與標準式就是函數(shù)的最大項標準式。

當邏輯函數(shù)用最大項標準式表示時，對于組成函數(shù)的所有最大項，只要有一項最大項為0，則該函數(shù)的值就為0，否則就為1。這樣，我們就能方便地列出邏輯函數(shù)及其反函數(shù)的真值表，(2.3.13)式所表示的邏輯函數(shù)的真值表如表2.3.3所示。

表2.3.3 函數(shù)及其反函數(shù)的真值表
A	B	C	Y
0	0	0	0	1
0	0	1	0	1
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	1	0
1	1	0	1	0
1	1	1	0	1

由表2.3.3所示真值表很容易寫出其反函數(shù)的表達式

可以看出,對于A、B、C三個變量來說,可以形成個最大項。并且，若這些最大項不包含在的或-與標準式中，則必然包含在的或-與標準式中。

上述結(jié)論可以推廣到個輸入變量的情況，個輸入變量有個最大項。對于個輸入變量的邏輯函數(shù)Y，根據(jù)邏輯代數(shù)基本定律，有

(2.3.14)

而：

(2.3.15)

所以有：

(2.3.16)

上式表明：個輸入變量所有最大項的“積”恒等于0

根據(jù)上述對最小項和最大項的討論，在同一個邏輯問題中，下標相同的最小項和最大項之間存在著互補的關(guān)系。即有：

或者 (2.3.17)

三、邏輯函數(shù)表達式的轉(zhuǎn)換

任意一個邏輯函數(shù)，其表達式的形式可以多種多樣，但是各種形式的表達式是可以轉(zhuǎn)換的。并且，不論其表達式處于何種形式，總可以轉(zhuǎn)換成最小項標準式和最大項標準式的形式。求一個邏輯函數(shù)表達式的標準形式有兩種方法，一種是代數(shù)轉(zhuǎn)換法，另一種是真值表轉(zhuǎn)換法。

代數(shù)轉(zhuǎn)換法

所謂代數(shù)轉(zhuǎn)換法，就是利用邏輯代數(shù)的公式、定律和規(guī)則，將邏輯函數(shù)表達式從一種形式變換為另一種形式。下面通過例子說明之。

例2.3.1 將邏輯函數(shù)轉(zhuǎn)換成最小項標準式

解：第一步：將邏輯函數(shù)表達式變換成與-或表達式。

第二步：利用，將與-或表達式中不是最小項的與項展開成最小項，寫出邏輯函數(shù)的最小項標準式。

(2.3.18)

由例題可歸納求邏輯函數(shù)最小項標準式的步驟：

①將邏輯函數(shù)表達式變換成一般的與-或表達式。

②利用，將與-或表達式中不是最小項的與項展開成最小項，寫出邏輯函數(shù)的最小項標準式。

例2.3.2 將例2.3.1中的邏輯函數(shù)化成最大項標準式。

解：第一步：將邏輯函數(shù)表達式變換成或-與表達式。

第二步：利用，將或-與表達式中不是最大項的或項展開成最大項，寫出邏輯函數(shù)的最大項標準式。

(2.3.19)

由例題可歸納求邏輯函數(shù)最大項標準式的步驟：

①將邏輯函數(shù)表達式變換成一般的或-與表達式。

②利用，將或-與表達式中不是最大項的或項展開成最大項，寫出邏輯函數(shù)的最大項標準式。

根據(jù)上述兩個例題的結(jié)果(2.3.18)式和(2.3.19)式，對于同一個邏輯函數(shù)最小項標準式中的編號與最大項標準式中的編號具有“互補”關(guān)系。因此，只要求出了邏輯函數(shù)兩種標準式中的任意一種，另一種標準式可按其編號的“互補”規(guī)律得出。

上述邏輯函數(shù)的真值表如表2.3.4所示。由真值表可知，邏輯函數(shù)Y的值為1對應(yīng)的最小項出現(xiàn)在最小項標準式中，邏輯函數(shù)Y的值為0對應(yīng)的最大項出現(xiàn)在最大項標準式中。

表2.3.4 例2.3.1和例2.3.2邏輯函數(shù)的真值表
A	B	C	Y
0	0	0	0	M₀
0	0	1	0	M₁
0	1	0	1
0	1	1	1
1	0	0	0	M₄
1	0	1	0	M₅
1	1	0	1
1	1	1	1

由此可見，利用邏輯函數(shù)的真值表可方便地寫出邏輯函數(shù)的兩種標準式。

真值表轉(zhuǎn)換法

真值表轉(zhuǎn)換法就是首先作出邏輯函數(shù)的真值表，利用真值表與最小項和最大項的關(guān)系，直接寫出邏輯函數(shù)的兩種標準式。當代數(shù)轉(zhuǎn)換法非常復(fù)雜時，真值表轉(zhuǎn)換法就顯得十分方便。

例2.3.3 將邏輯函數(shù)表達式表示成最小項標準式和最大項標準式。

解：首先作出該邏輯函數(shù)的真值表如表2.3.5所示。

表2.3.5 例2.3.3邏輯函數(shù)的真值表
A	B	C	Y
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

由真值表2.3.5可知使邏輯函數(shù)Y的值為1的情況有四種取值組合，這些組合對應(yīng)的最小項必定出現(xiàn)最小項標準式中。所以邏輯函數(shù)表達式的兩種標準式如下：

由于邏輯函數(shù)的真值表與邏輯函數(shù)的兩種標準式存在一一對應(yīng)的關(guān)系，而任何一個邏輯函數(shù)的真值表是唯一的，所以任何一個邏輯函數(shù)的兩種標準式也是唯一的，這樣就給我們分析和研究邏輯函數(shù)帶來了很大的方便。

2.3.2 邏輯函數(shù)的代數(shù)化簡法

一、邏輯函數(shù)的最簡形式

同一個邏輯函數(shù)，其表達形式多種多樣，但是表達式越簡單，它所表示的邏輯關(guān)系也就越明確，實際應(yīng)用中便能用越少的電子器件來實現(xiàn)它。因此對于比較繁復(fù)的邏輯表達式，往往要通過化簡的方法來找出其最簡的表達式。如下列兩個邏輯函數(shù)表達式

列出它們的真值表后發(fā)現(xiàn)，其真值表完全相同，根據(jù)邏輯函數(shù)相等的定義，它們是同一個邏輯函數(shù)。但是很明顯，比簡單得多。

同一個邏輯函數(shù)，其最簡表達式的形式也是多種多樣，如最簡的與-或表達式；最簡的或-與表達式；最簡的與非-與非表達式；最簡的或非-或非表達式；最簡的與-或-非表達式等等。在眾多的最簡表達式中大都可以通過最簡的與-或表達式或者最簡的或-與表達式轉(zhuǎn)換得出，因此，一般只需研究最簡的與-或表達式和最簡的或-與表達式。

一個最簡的與-或表達式應(yīng)滿足下述兩個條件：

（1）表達式中所含與項的數(shù)目應(yīng)該最少。

（2）在滿足上述條件的前提下，每一個與項中所含變量的數(shù)目應(yīng)該最少。

同樣，最簡的或-與表達式也必須滿足兩個條件：

（1）表達式中所含或項的數(shù)目應(yīng)該最少。

（2）在滿足上述條件的前提下，每一個或項中所含變量的數(shù)目應(yīng)該最少。

在數(shù)字邏輯電路中，邏輯函數(shù)表達式滿足上述最簡條件的前提下，設(shè)計的邏輯電路結(jié)構(gòu)最簡單從而使電路最經(jīng)濟。

由于習(xí)慣上人們把最簡與-或表達式認為是邏輯函數(shù)的最簡表達式，所以本書若無特別申明時，最簡表達式就是指最簡與-或表達式。

二、邏輯函數(shù)的代數(shù)化簡法

所謂代數(shù)化簡法就是利用邏輯代數(shù)中的公律、定理、基本公式等將一個邏輯函數(shù)表達式化簡為最簡形式，即消去邏輯函數(shù)中多余的與項和每個與項中多余的變量因子。代數(shù)化簡法沒有固定的步驟，只要熟練地運用邏輯代數(shù)中常用的公式、定律和規(guī)則，便能求出最簡表達式。常用的方法有：合并項法、吸收法、消去法及配項法。

1.合并項法

利用公式將兩項合并為一項，同時消去這一對互補因子。其中既可以是變量，也可以是復(fù)雜的邏輯式。

例 2.3.4 化簡

解法1：

解法2：

⊙

2.吸收法

常利用公式消去多余項。其中既可以是變量，也可以是復(fù)雜的邏輯式。

例 2.3.5 化簡

解：

例 2.3.6 化簡

解：

3.消去法

常利用公式消去多余因子，其中既可以是變量，也可以是復(fù)雜的邏輯式。

例2.3.7 化簡

解：

4.配項法

根據(jù)基本公式可以在邏輯函數(shù)表達式中重復(fù)寫入某一項，或?qū)⒛骋怀朔e項乘以，從而將這一項展開為兩項，再與其它的項重新進行合并，消去更多的項和變量，最終得到最簡表達式。

例2.3.8 化簡

解：

例2.3.9 化簡

解：

對于化簡較為復(fù)雜的邏輯函數(shù)表達式時，往往需要綜合運用上述幾種化簡方法，才能得到最后的化簡結(jié)果。

例2.3.10 化簡

解：

用代數(shù)化簡法求最簡的或-與表達式時，可以直接運用前述介紹化簡與-或表達式中提出的各種方法的對偶公式和定律來進行；也可以采用兩次對偶法，首先對用或-與表達式表示的函數(shù)Y求出對偶式，得到與-或表達式，按與-或表達式的化簡方法求出的最簡表達式，然后，對再次求對偶，即可得到Y的最簡或-與表達式。

代數(shù)化簡法的優(yōu)點是不受變量數(shù)目的約束，當對公式、定律和規(guī)則十分熟練時化簡就比較方便。其缺點是沒有一定的規(guī)律和固定的步驟，技巧性很強，而且在很多情況下難以判斷化簡結(jié)果是否最簡。所以這種方法有很大的局限性。

2.3.3 卡諾圖化簡法

卡諾圖是上世紀五十年代美國工程師卡諾（M.Karnaugh）提出的。它邏輯關(guān)系的一種圖表示法，形象且直觀，并能說邏輯函數(shù)中的許多概念?？ㄖZ圖是數(shù)字邏輯設(shè)計中常用的一種數(shù)工具。下面將介紹卡諾圖的構(gòu)成、性質(zhì)以及應(yīng)用卡諾圖化簡邏輯函數(shù)的方法。

一、卡諾圖

卡諾圖實際上是真值表的一種變形，它與真值表具有一一對應(yīng)的關(guān)系。真值表中的一行對應(yīng)于卡諾圖中的一個點（亦稱一個單元），卡諾圖的圖形結(jié)構(gòu)具有一定的規(guī)律，直觀圖形可方便地進行邏輯運算。

例如，某邏輯函數(shù)的真值表表示形式如表2.3.6所示。用卡諾圖表示則如圖2.3.1所示?？梢钥闯稣嬷当碇械囊恍袑?yīng)于卡諾圖的一個方格單元，方格單元內(nèi)所填的值為該行邏輯函數(shù)的值。

表2.3.6 某邏輯函數(shù)的真值表
A	B	C	Y
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

將真值表變換為卡諾圖一般可以分兩步進行

1、將輸入變量分為兩組。如果是三變量，則分為一組，為另一組；如果是四變量，則為一組，為另一組。每組變量的取值組合必須按照循環(huán)碼的規(guī)律排序。所謂循環(huán)碼，指的是相鄰兩組變量的取值組合中，只能有一個變量的取值不同。如兩變量輸入時，取值組合有四種，列真值表時可以按照00，01，10，11的順序排列，在卡諾圖中不能按照這種順序，因為它不符合循環(huán)碼相鄰兩組之間只有一個變量取值不同的規(guī)則，強調(diào)相鄰性還包括頭尾兩組。因此按照循環(huán)碼的規(guī)則正確排列兩變量的取值組合時，應(yīng)為00→01→11→10。這樣把輸入變量分兩組并按循環(huán)碼的規(guī)則排列后，將真值表轉(zhuǎn)化成方格圖的形式。

2、從方格圖中可以看出，有多少個變量的取值組合，便對應(yīng)有多少個方格單元，且每個方格單元實際上就相當于真值表中的一個行，對應(yīng)于邏輯函數(shù)的一個最小項，因此，為方便邏輯運算可以在每個方格單元中填入對應(yīng)的最小項的代號。如圖2.3.2與圖2.3.3所示為三變量和四變量卡諾圖的形式。

分析圖2.3.2和圖2.3.3中最小項分布規(guī)律可以看出，幾何位置相鄰的最小項在邏輯上也具有相鄰性，任何兩個相鄰的最小項僅有一個變量是不同，包括任意一行或一列頭尾的最小項也僅有一個變量不同。因此，可以把卡諾圖的上下、左右看成一個閉合圖形。

在變量數(shù)大于、等于五以后，僅僅用幾何圖形在兩維空間的相鄰性來表示邏輯相鄰性已經(jīng)不夠了。例如圖2.3.4所示的五變量最小項卡諾圖中，除了幾何位置相鄰的最小具有相鄰性以外，以圖中雙豎線為軸線左右對稱位置上的兩個最小項也具有邏輯上的對稱性。

二、用卡諾圖表示邏輯函數(shù)

如果邏輯函數(shù)表達式是最小項之和的標準式，則只要在卡諾圖上找出那些同給定邏輯函數(shù)包含的最小項相對應(yīng)方格，然后在這些方格單元中填入1，其余方格單元中填入0，便得到了該邏輯函數(shù)的卡諾圖。為了敘述方便，我們把填入1的方格單元叫1方格，填入0的方格單元叫0方格。

例如三變量邏輯函數(shù)

編號為3、5、6、7的最小項出現(xiàn)在邏輯函數(shù)表達式中，卡諾圖中相應(yīng)編號的方格單元填入1，其余方格單元中填入0，便得到該邏輯函數(shù)的卡諾圖，如圖2.3.5所示。

例2.3.11 用卡諾圖表示邏輯函數(shù)

解：首先將化為最小項之和的形式

然后，畫出四變量卡諾圖，在編號為5、7、10、11、12、13、14、15的方格內(nèi)填1，其余方格填0，得該邏輯函數(shù)的卡諾圖，如圖2.3.6所示。

三、卡諾圖的性質(zhì)

由于卡諾圖中變量的取值組合都是按照循環(huán)碼的規(guī)則進行排列，每兩個相鄰的組合只有一個變量取值不同，因此卡諾圖中具有邏輯相鄰性的最小項可以進行合并。根據(jù)公式，當一個變量分別以原變量與反變量的形式出現(xiàn)在兩個與項中，且這兩個與項的其余部分相同，那么這兩個與項可以合并為一項。

相鄰的兩個最小項，可以合并為一項并消去一個變量。合并后只剩下公共因子。

圖2.3.7所示為兩個相鄰項進行合并的例子。圖2.3.7（a）中，兩個相鄰項為，只有變量在這兩個相鄰項中分別以原變量和反變量的形式出現(xiàn)，剩余因子相同，故有，即消去合并項中發(fā)生了0、1變化的變量，而將沒有發(fā)生變化的變量保留下來。同理可得圖（b）和圖（c）的結(jié)果。

相鄰四個最小項，可以合并為一項并消去兩個變量。合并后只包含公共因子。

圖2.3.8所示為四個相鄰項進行合并的例子。必須注意的是，四個1方格進行合并時，首尾相鄰的1方格以及四角相鄰的1方格不要遺漏。如圖 2.3.9所示。

相鄰八個最小項，可以合并為一項并消去三個變量。合并后只包含公共因子。

圖 2.3.10 列出了八個相鄰項進行合并的例子。同必須注意不要遺漏首尾相鄰的1方格。

根據(jù)上述最小項的性質(zhì)，可以歸納出合并最小項的一般規(guī)則：在一個輸入變量的卡諾圖中，若一個合并圈中存在個具有相鄰性的最小項，則這些相鄰的最小項可以合并為一項，并消去個變量，只留下由（）個沒有發(fā)生0、1變化的變量所構(gòu)成的乘積項。

四、利用卡諾圖化簡邏輯函數(shù)

為了更好的理解利用卡諾圖化簡邏輯函數(shù)的方法，首先簡要的介紹幾個基本概念：

（1）主要項：卡諾圖中，包含個相鄰1方格的合并圈且合并圈不能再擴大（即再擴大將把0方格也包含進去）所得到的合并乘積項，稱為主要項，或本原蘊含項。如圖2.3.11所示的，即為主要項。

（2）必要項：如果一個主要項圈中至少有一個“特定”的1方格沒有被其他的主要項圈覆蓋，那么這個主要項圈所圈得的合并乘積項就稱為必要項或?qū)嵸|(zhì)本原蘊含項。如圖2.3.11（a）所示的和圖2.3.11（b）所示的即為必要項。實際上，最終化簡結(jié)果中所含的乘積項個數(shù)即為必要項的個數(shù)。

（3）多余項：如果一個主要項圈中的1方格全部被其它的幾個主要項圈包含，那么這個主要項圈所圈得的合并乘積項就稱為多余項。如圖 2.3.12（b）所示的即為多余項。

利用卡諾圖化簡邏輯函數(shù)的步驟如下：

第一步：將邏輯函數(shù)變換為最小項之和的形式

第二步：畫出表示該邏輯函數(shù)的卡諾圖

第三步：找出可以合并的最小項并畫出合并圈

第四步：寫出最簡的與-或表達式

例2.3.12 化簡邏輯函數(shù)

解：（1）由于邏輯函數(shù)已給出最小項之和的標準形式，故第一步可省略。

（2）畫出表示該邏輯函數(shù)的卡諾圖，如圖2.3.13(a)所示。

（3）找出可以合并的最小項（1方格），并畫出合并圈，如圖2.3.13(b) 所示。

（4）合并最小項，并把每個合并圈對應(yīng)的與項加起來，得出最簡與-或表達式。

可以看出，在利用卡諾圖化簡邏輯函數(shù)時，關(guān)鍵在于畫合并圈。合并圈畫得不同，邏輯函數(shù)的表達式也不相同。因此畫合并圈時應(yīng)注意以下幾點：

①首先要找出孤立的1方格并畫圈。

②合并圈的范圍越大越好，但必須包含（i=0,1,2,3…）個1方格，這樣能消去的變量就越多。

③合并圈的個數(shù)越少越好，因為合并圈的個數(shù)與化簡結(jié)果中乘積項的個數(shù)相對應(yīng)，圈數(shù)越少意味著與-或表達式中與項越少。

④每個合并圈中至少要包含一個其它合并圈中沒有包含的1方格，這樣才能保證這個合并圈不是多余的。

⑤卡諾圖中所有的1方格至少要被圈一次，不能有漏畫的1方格。

這樣，把每個合并圈相對應(yīng)的與項“加”起來，就得到最簡的與-或表達式。

同理的方法，只要合并圈改為針對卡諾圖中的0方格進行，找出可合并的最大項，就可得到邏輯函數(shù)的最簡或-與表達式。

合并最大項的規(guī)律與合并最小項的規(guī)律基本一致。不同之處在于，合并最大項時必須找出0方格的相鄰性。每個合并圈可由（i=0,1,2,3…）個0方格構(gòu)成，每個合并圈對應(yīng)于一個或項，該或項由圈內(nèi)取值不變的變量相或來構(gòu)成，其中取值為0的對應(yīng)原變量，取值為1的對應(yīng)反變量。然后將每個合并圈對應(yīng)的或項進行相與，便得到最簡的或-與表達式。

例2.3.13 求函數(shù)的最簡或-與表達式

解：

（1）邏輯函數(shù)已給出最小項之和的標準形式。

（2）畫出表示該邏輯函數(shù)的卡諾圖，如圖2.3.14 (a)所示。

（3）找出可以合并的0方格（最大項），并畫出合并圈，如圖2.3.14 (b)所示

（4）合并最大項，把每個合并圈對應(yīng)的或項相乘，得到最簡或-與表達式

五、具有無關(guān)項的邏輯函數(shù)及其化簡

（1）約束項、任意項及無關(guān)項

在某些實際應(yīng)用中，邏輯函數(shù)的輸入變量取值不是任意的，如用三個輸入邏輯變量分別表示一臺電動機的正轉(zhuǎn)、反轉(zhuǎn)、停止，表示電機正轉(zhuǎn)，表示電機反轉(zhuǎn)，表示電機停止。而實際應(yīng)用中，電機只能執(zhí)行其中的一個命令，不可能允許兩個以上的變量同時為1。故的取值只能為001，010，100當中的一種，不可能是000，011，101，110，111中的任何一種，也就是說對這三個輸入變量的取值加上了限制條件。這種對輸入變量所加的限制就稱為約束。通常可以用約束條件來描述約束的內(nèi)容。如上述所舉實例，其約束條件可以表示為

或?qū)懽?/p>

同時把這些恒等于0的最小項稱為約束項。

任意項是指邏輯函數(shù)在輸入變量的某些取值組合時其輸出值不確定，可能為1，可能為0，但是對電路的功能并不影響，若用最小項表示這些取值組合，那么這些最小項便稱為任意項。

一般來說，任意項與約束項又統(tǒng)稱為無關(guān)項，在卡諾圖中用×表示，化簡邏輯函數(shù)時既可以認為它為1，也可以認為它為0。

（2）無關(guān)項在化簡邏輯函數(shù)中的應(yīng)用

在化簡具有無關(guān)項的邏輯函數(shù)時，無關(guān)項作為0方格還是作為1方格處理，前提是有利于邏輯函數(shù)的化簡及得到最簡結(jié)果。為了達到這個目的，應(yīng)使加入的無關(guān)項能與邏輯函數(shù)表達式中盡可能多的最小項具有邏輯相鄰性，同時使最小項合并圈的數(shù)目最少，而合并圈中包含的相鄰最小項的數(shù)目最多。

例2.3.14 化簡

解：這是一個具有無關(guān)項的邏輯函數(shù)表達式，其中表示所包含的無關(guān)項，在卡諾圖中可用×表示，則表示該邏輯函數(shù)表達式的卡諾圖如圖2.3.15（a）所示。

按照無關(guān)項的使用原則，其值為1，還是為0，應(yīng)看是否有利于邏輯函數(shù)的化簡。如不使用這些無關(guān)項，即將它們作為0格處理，，所得化簡結(jié)果為

若合理使用這些無關(guān)項，即將有利于化簡的無關(guān)項作1格處理，如,并與邏輯相鄰的1格構(gòu)成足夠大的合并圈，而不利于化簡的無關(guān)項如,作0格處理，如圖2.3.15(b) 所示，可得化簡結(jié)果為

由此可見，無關(guān)項的應(yīng)用應(yīng)以有利于化簡為前提。

2.3.4邏輯函數(shù)的列表化簡法

列表化簡法又稱為奎恩－麥克洛斯基法，簡稱Q－M法。從前面介紹的卡諾圖化簡法中可以看出，卡諾圖化簡的一個重要步驟是能從原邏輯函數(shù)表達式中較快的畫出表示該邏輯函數(shù)的卡諾圖。但是對于多變量邏輯函數(shù)的卡諾圖來說，不僅難畫，且其中相鄰最小項也不容易較快的找出，因為多變量邏輯函數(shù)的卡諾圖中，具有邏輯相鄰性的最小項有時在幾何位置上并不相鄰，不易觀察尋找，且多變量邏輯函數(shù)的卡諾圖化簡也較為繁雜，因此在計算機技術(shù)飛速發(fā)展的過程中，有著嚴格算法的Q－M法在任意多變量邏輯函數(shù)的化簡中脫穎而出。Q－M法雖然計算過程比較復(fù)雜，但它可以將函數(shù)化簡的問題編成程序，從而借助于計算機的高速運算處理能力很快實現(xiàn)，故Q－M法適合任意多變量的邏輯函數(shù)化簡。

這種化簡方法和卡諾圖化簡法的基本思想大致相同。它也是通過找出函數(shù)Y的全部主要項、實質(zhì)主要項以及最簡主要項集來求得最簡表達式。所不同的是，在列表化簡法中上述結(jié)果都是通過約定形式的表格，按照一定規(guī)則求得的。

用列表法化簡邏輯函數(shù)一般可以概括為以下四個步驟：

第一步：將函數(shù)表示成“最小項之和”形式，并用二進制碼表示每一個最小項。

第二步：找出函數(shù)的全部主要項。

尋找函數(shù)全部主要項的方法是先將個變量函數(shù)中的相鄰最小項合并，消去相異的一個變量，得到個變量的與項；再將相鄰的個變量的與項合并，消去相異的變量，得到個變量的與項；…。依此類推，直到不能再合并為止。所得到的全部不能再合并的與項（包括不能合并的最小項），即所要求的全部主要項。

第三步：選出函數(shù)的實質(zhì)主要項。

第四步：選擇主要項，使之能夠包含給定函數(shù)的全部最小項，從而建立函數(shù)的最簡與-或式。

以上各個步驟均是通過表格進行的，下面通過一個例子說明。

例2.3.15 用列表法化簡邏輯函數(shù)

解：

第一步：用二進制代碼表示函數(shù)中的每一個最小項，如表2.3.7所示

第二步：求函數(shù)的全部主要項。

考慮到相鄰最小項的二進制碼中的1個數(shù)只能相差1，因此，將表2.3.7中的最小項按二進制編碼中1的個數(shù)進行分組，且按1的個數(shù)的遞增順序排列在表2.3.8（Ⅰ）欄中。這樣，可以合并的最小項便只能處于相鄰的兩組內(nèi)。因此，可將（Ⅰ）欄中相鄰兩組的二進制碼逐個進行比較，找出那些只有一個變量不同的最小項合并，消去不同變量，組成個變量的與項列于表2.3.8的（Ⅱ）欄中。例如，首先將0組的最小項與1組的進行比較、合并，即消去相異的A變量，這里用“－”表示消去的變量，然后將合并后的與項列入表2.3.8的（Ⅱ）欄中。由于該與項是由和合并產(chǎn)生的，故在（Ⅰ）欄中和的右邊打上“√”標記，表示它們已經(jīng)包含在（Ⅱ）欄的與項中了，并在（Ⅱ）欄中的第二列指出相應(yīng)與項是由哪幾個最小項合并產(chǎn)生的。第0組的最小項與第1組的最小項比較完后，順序比較第0組與第2，3，4組，發(fā)現(xiàn)沒有可以合并的最小項，然后接著比較第1組和第2組的最小項。即將

表 2.3.7 函數(shù)的部分真值表
項號	A B C D	Y
0	0000	1
5	0101	1
7	0111	1
8	1000	1
9	1101	1
10	1010	1
11	1011	1
14	1110	1
15	1111	1

與，分別進行比較，顯然與不能合并，因為它們之間有多個變量不同，而與可以合并消去變量D，與可以合并消去變量C，將合并后得到的與項同樣列入（Ⅱ）欄中。依次類推，將（Ⅰ）欄中全部最小項逐一進行比較、合并，得到表的（Ⅱ）欄。在（Ⅱ）欄中的“與”項均由個變量組成，此例（Ⅱ）欄的“與”項由三個變量組成。

按上述同樣的方法，再對表2.3.8中的全部與項進行比較、合并，可形成表的第（Ⅲ）欄。如第（Ⅱ）欄中的（8，9）和（10，11），（8，10）和（9，11）可以合并為“10――”。由于第（Ⅲ）欄的與項不再相鄰，故合并到此結(jié)束。

表2.3.8 中凡是沒有打“√”標記的與項，就是不能再合并的乘積項，即該函數(shù)的全部主要項，用表示，該函數(shù)的全部主要項為

第三步：選取函數(shù)的實質(zhì)主要項。

通過建立實質(zhì)主要項表，可以選出函數(shù)的全部實質(zhì)主要項。

函數(shù)的實質(zhì)主要項是指包含實質(zhì)最小項的主要項。而實質(zhì)最小項又是指僅僅屬于一個主要項的最小項。本例的函數(shù)實質(zhì)主要項產(chǎn)生表如表2.3.9 所示。表中第一行為Y的全部最小項，第一列為上一步求得的全部主要項。實質(zhì)主要項可按下述步驟求得：

1、逐行標上各主要項覆蓋最小項的情況。例如，表中主要項可覆蓋最小項和，故在這一行與上述最小項相應(yīng)列的交叉處打上“”標記，其它各行依此類推。

2、逐列檢查標有“”的情況，凡只有一個“”號的列的相應(yīng)最小項即為實質(zhì)最小項，在“”外面打上一個圈（即“”）。例如，表中最小項各列均只有一個“”，故都在“”號外加上圈。

表2.3.8 主要項的產(chǎn)生表
（Ⅰ）最小項				（Ⅱ）個變量的“與”項				（Ⅲ）個變量的“與”項
組號				組號				組號
0	0	0000	√	0	0,8	－000		0	8，9，10，11	10――
1	8	1000	√	1	8,9	100－	√	1	10，11，14，15	1－1－
2	5	0101	√	1	8,10	10－0	√
	9	1001	√	2	5,7	01－1
	10	1010	√		9,11	10－1	√
3	7	0111	√		10,11	101－	√
	11	1011	√		10,14	1－10	√
	14	1110	√	3	7,15	－111
4
15	1111	√	11,15		1－11	√
				14,15	111－	√

3、找出包含“”號的各行，這些行對應(yīng)的主要項即為實質(zhì)主要項，在這些實質(zhì)主要項右上角加上“*”標記。例如，表中的和均為實質(zhì)主要項。

4、在表的最后一行（覆蓋情況一欄）中，標上實質(zhì)主要項覆蓋最小項的情況。凡能被實質(zhì)主要項覆蓋的最小項，在最后一行的該列上打上“√”標記，供下一步選擇主要項，使之能夠包含給定函數(shù)的全部最小項，從而建立函數(shù)的最簡與-或式。

第四步：選擇主要項，使之能夠包含給定函數(shù)的全部最小項，從而建立函數(shù)的最簡與-或式。

函數(shù)的最簡與-或式必須覆蓋全部最小項，而實質(zhì)主要項是首先必須選用的主要項。因為如果不選實質(zhì)主要項，就找不到其它主要項來包含那些實質(zhì)最小項。本例從表2.3.9 的覆蓋情況一行可知，選取實質(zhì)主要項和后即可包含函數(shù)的全部最小項。因此，該函數(shù)化簡的最終結(jié)果為

當給定函數(shù)的實質(zhì)主要項集不能覆蓋該函數(shù)的全部最小項時，還需進一步從剩余主要項集中找出所需主要項，以構(gòu)成函數(shù)的最小主要項集，這樣才能使得最終化簡結(jié)果既能包含全部最小項，同時所需乘積項又最少，即獲得最簡的與或式。

進一步找出剩余所需主要項的途徑是首先建立一個“所需主要項產(chǎn)生表”，該表是將“實質(zhì)主要項產(chǎn)生表”中的實質(zhì)主要項及其所覆蓋的最小項去掉后形成的。然后按照一定的方法從“所需主要項產(chǎn)生表”中找出所需主要項。通常采用的方法是行列消去法，其規(guī)則如下：

行消去規(guī)則：對于所需主要項產(chǎn)生表中的任意主要項和，若行中的“”號完全包含在行中，即，則可消去行。這是因為選取了主要項后不僅可以覆蓋主要項所能覆蓋的最小項，而且還可覆蓋其它最小項。

表2.3.9 實質(zhì)主要項產(chǎn)生表

	0	5	7	8	9	10	11	14	15
						×	×		×
				×		×	×
			×						×
			×
				×
覆蓋情況	√	√	√	√	√	√	√	√	√

列消去規(guī)則：對于所需主要項產(chǎn)生表中的任意最小項和，若列中的“”號完全包含在列中，即，則可消去列。這是因為選取了覆蓋的主要項后一定能覆蓋，反之則不一定。

按照上述規(guī)則消去多余的行和多余的列，可再次選出實質(zhì)主要項。該規(guī)則可重復(fù)使用，直至找出能覆蓋函數(shù)全部最小項的最小主要項集為止。下面舉例說明選取剩余主要項的方法。

例 2.3.16 已知函數(shù)的實質(zhì)主要項產(chǎn)生表如表2.3.10所示，求出該函數(shù)的剩余主要項并寫出函數(shù)最簡與或式。

表2.3.11 剩余主要項產(chǎn)生表

	0	3	8	10	11

				×	×
		×			×
		×
			×	×
	×		×
	×

表 2.3.10 函數(shù)實質(zhì)主要項產(chǎn)生表

	0	3	4	5	6	7	8	10	11
			×			×
								×	×
		×							×
		×				×
							×	×
	×						×
	×		×
覆蓋情況			√	√	√	√

解：由表2.3.10可知為實質(zhì)主要項，可覆蓋最小項。在選取作為函數(shù)Y的一個與項后，還剩下最小項未被覆蓋，因此必須從剩余的主要項中選取所需的主要項。為此，從表2.3.10中先消去和它所覆蓋的最小項，得到如表2.3.11所示的剩余主要項產(chǎn)生表。

在表2.3.11中，行中的“×”完全包含在行中，行中的“×”完全包含在行中，根據(jù)行消去規(guī)則，可消去和兩行。得到表2.3.12,它由剩余的主要項和最小項組成。從表2.3.12中還可看出，列中的“×”完全包含在列中，列中的“×” 完全包含在列中，根據(jù)列消去規(guī)則，可消去和所對應(yīng)的列，得到表2.3.13.