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

觀察函數(shù)

1.該函數(shù)有四個(gè)邏輯變量，可表示成

Y=f(A、B、C、D)

2.該函數(shù)有三個(gè)乘積項(xiàng)：第一項(xiàng)有四個(gè)因子——四個(gè)變量在乘積項(xiàng)中都出現(xiàn)了。第二項(xiàng)有三個(gè)因子——缺少變量B（或）。第三項(xiàng)缺少變量C、D（或、）。

3.第一個(gè)乘積項(xiàng)是A、B、C、D的一個(gè)最小項(xiàng)，其余二項(xiàng)均不是A、B、C、D的最小項(xiàng)。

最小項(xiàng)：n個(gè)邏輯變量A1、A2、…… An組成的邏輯系統(tǒng)中含n個(gè)因子的乘積項(xiàng)——每個(gè)變量（或）在乘積項(xiàng)中只出現(xiàn)一次，稱這樣的乘積項(xiàng)為最小項(xiàng)。

兩個(gè)邏輯變量A、B有22＝4個(gè)最小項(xiàng)，分別是：、、、。

三個(gè)邏輯變量A、B、C有23＝8個(gè)最小項(xiàng)，分別是：、、、、、、、。

四個(gè)邏輯變量A、B、C、D有24＝16個(gè)最小項(xiàng)。

練習(xí)：寫出A、B、C、D的十六個(gè)最小項(xiàng)。

最小項(xiàng)的性質(zhì)：

（1）對(duì)變量的任意一組取值，只有一個(gè)最小項(xiàng)為1，其余最小項(xiàng)全為0。二變量A、B的最小項(xiàng)為：、、、。對(duì)A、B的任意一組取值：

A=0 B=0 =1 其余三項(xiàng)全為0，即＝＝＝0

A=0 B=1 = 1 其余三項(xiàng)全為0

A=1 B=0 = 1 其余三項(xiàng)全為0

A=1 B=1 = 1 其余三項(xiàng)全為0

（2）全體最小項(xiàng)之和為1。（讀者自己證明）

（3）任意兩個(gè)最小項(xiàng)的乘積為0。

最小項(xiàng)的編號(hào)：

三變量A、B、C的八組取值000、001、……111能分別使八個(gè)最小項(xiàng)的值為1，又與十進(jìn)制數(shù)0，1……7的二進(jìn)制數(shù)表示相同。用0～7編號(hào)八個(gè)最小項(xiàng)，記為：m0、m1、m2、m3、m4、m5、m6、m7，則m7＝m111＝，……m4＝m100＝，m0＝m000＝。

練習(xí)：讀者試寫出四變量A、B、C、D的十六個(gè)最小項(xiàng)m0、m1……m15。

邏輯函數(shù)的最小項(xiàng)之和形式

任何邏輯函數(shù)都可化為最小項(xiàng)之和的標(biāo)準(zhǔn)形式

例：將下列函數(shù)化為最小項(xiàng)之和的形式

反函數(shù)的最小項(xiàng)之和表示

例：求二變量A，B的邏輯函數(shù)的反函數(shù)。

解一：

解二：列真值表

由真值表寫出的邏輯表達(dá)式

???

(全體最小項(xiàng)之和)

如三變量A,B,C的邏輯函數(shù)則必有

結(jié)論：在n個(gè)變量的邏輯系統(tǒng)中，如果Y為i個(gè)最小項(xiàng)之和，則必為余下的（n－i）個(gè)最小項(xiàng)之和。

異或運(yùn)算與同或運(yùn)算

定義： 稱A與B異或，為異或運(yùn)算符

A與B同或，為同或運(yùn)算符

顯然：

異或與同或互為反函數(shù)

由此推得：

即兩者相等為0，不相等為1

同或運(yùn)算則與之相反，且有

同學(xué)自己證明并牢記。

例1． 將下列函數(shù)化為最簡與或式。

例2． A，B的波形如下圖所示,試畫出的波形。

最小項(xiàng)的相鄰性

任何兩個(gè)最小項(xiàng)如果他們只有一個(gè)因子不同，其余因子都相同，則稱這兩個(gè)最小項(xiàng)為相鄰最小項(xiàng)。

顯然，m0與m1具有相鄰性，而與不相鄰，因?yàn)樗麄冇袃蓚€(gè)因子不相同。m3與m4也不相鄰，而m3與m2相鄰。

相鄰的兩個(gè)最小項(xiàng)之和可以合并成一項(xiàng)，并消去一個(gè)變量。如：

卡諾圖

卡諾圖是美國工程師卡諾（Karnaugh）發(fā)明的。用小方塊（格）來表示最小項(xiàng)。三變量的卡諾圖畫八個(gè)小方塊（格）來表示八個(gè)最小項(xiàng)，四變量的卡諾圖畫十六個(gè)小方塊來表示十六個(gè)最小項(xiàng)。……

觀察三變量卡諾圖發(fā)現(xiàn)這八個(gè)小方塊（最小項(xiàng)）中，凡幾何上相鄰的兩個(gè)小方塊（最小項(xiàng)）具有相鄰性――只有一個(gè)變量不同，相加后能合并成一項(xiàng)，并能消去一個(gè)變量。

m0m1 ，m1m3 ，m3m2 ，m4m5 ，m5m7 ，m7m6 ， m0m4 ，m1m5 ，m3m7 ，m2m6都具有相鄰性，還有m0m2 ，m1m6也具有相鄰性（可理解成將卡諾圖卷成圓筒，他們?cè)趲缀紊暇拖噜徚耍?/P>

在四變量卡諾圖中，m0m8 ,m1m9 ,m3m11 ,m2m6也都具有相鄰性。

思考題：為什么卡諾圖按00，01，11，10的順序，而非00，01，10，11順序畫小方塊（代表最小項(xiàng)）？

邏輯函數(shù)的卡諾圖表示及化簡

在邏輯函數(shù)的最小項(xiàng)表示一節(jié)中，已經(jīng)講過，任何一個(gè)邏輯函數(shù)都可以化為最小項(xiàng)之和的標(biāo)準(zhǔn)形式。

只要將標(biāo)準(zhǔn)形式里函數(shù)所包含的每一個(gè)最小項(xiàng)，在卡諾圖中對(duì)應(yīng)的小方塊里添上1，卡諾圖上其余的小方塊里添0（以后添0，以空格代替）――這就是邏輯函數(shù)的卡諾圖。

其實(shí)將函數(shù)化為最小項(xiàng)之和，再畫卡諾圖的過程可以簡化，函數(shù)化為最小項(xiàng)之和的過程可以省略，直接畫出卡諾圖。

例1． 畫出的卡諾圖并化簡

解：1、畫出Y的卡諾圖

Y共有四個(gè)乘積項(xiàng)，第一個(gè)乘積項(xiàng)包含第4行的四項(xiàng)：m8，m9，m11，m10；第二個(gè)乘積項(xiàng)包含第1，2行（A＝0）與第3，4列（C＝1）相交的四項(xiàng)：m3，m2，m7，m6 ；第三個(gè)乘積項(xiàng)包含第2，3行（B＝1）與第3，4列（C＝1）相交的四項(xiàng)：m7，m6，m15，m14；第四個(gè)乘積項(xiàng)表第2列的4項(xiàng)。

2、合并與化簡

從Y的卡諾圖上看到第2，3列8項(xiàng)合并，第3，4列8項(xiàng)合并，第4行合并得：

例2．

解：1、畫出Y的卡諾圖

第1項(xiàng)，顯然第4行中的4個(gè)最小項(xiàng)都含因子，而第1，2列的8個(gè)最小項(xiàng)都含因子，第4列與第1，2列相交的兩項(xiàng)m8，m9即為。第4項(xiàng)C則包含第3，4兩列的8項(xiàng)。

2、合并化簡。從卡諾圖可知

用卡諾圖化簡邏輯函數(shù)小結(jié)：

1． 畫出邏輯函數(shù)的卡諾圖。

2． 若兩個(gè)最小項(xiàng)相鄰， 則可合并為一項(xiàng)，且消去一個(gè)因子。

3． 若四個(gè)最小項(xiàng)相鄰（排列成一個(gè)矩形組），則該四個(gè)最小項(xiàng)可合并成一項(xiàng)，且可消去兩個(gè)因子。

4． 若八個(gè)最小項(xiàng)相鄰（排列成一個(gè)矩形組），則該八個(gè)最小項(xiàng)可合并成一項(xiàng)，且可消去三個(gè)因子。

5. 若十六個(gè)最小項(xiàng)相鄰（排列成一個(gè)矩形組），則該十六個(gè)最小項(xiàng)可合并成一項(xiàng)，且可消去四個(gè)因子。

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

我們來分析一個(gè)實(shí)際問題：

某水庫設(shè)有三個(gè)水位檢測點(diǎn)，裝有A、B、C三個(gè)干濕傳感

器，當(dāng)傳感器被水浸泡時(shí)輸出1，否則（不浸水時(shí)）輸出0。該水庫有大小兩個(gè)閘門GL、GS。A為警戒水位點(diǎn)，B比警戒水位A高1米，C比警戒水位高2米。防汛部規(guī)定當(dāng)水位低于警戒水位A時(shí)，關(guān)閘蓄水。當(dāng)水位超過A時(shí)，開小閘門GS放水，當(dāng)水位超過B時(shí)，開啟大閘門GL（關(guān)閉小閘門）泄洪；當(dāng)水位超過C時(shí)，大小閘門ＧLＧS同時(shí)開啟泄洪。如果用1表示閘門關(guān)閉，閘門與水庫水位之間的邏輯關(guān)系真值表如下：

說明：水位低于警戒線，關(guān)閘蓄水

水位超警戒線，只開小閘門放水

只開大閘門泄洪

大小閘門同時(shí)泄洪

從前面講過的內(nèi)容來看GL=AB，這兩個(gè)邏輯函數(shù)已經(jīng)不能再化簡了，但從現(xiàn)實(shí)角度看應(yīng)該有更簡化的結(jié)果GL=B，因?yàn)橹灰怀^B（B＝1），大閘門就要開啟，與是否超過C無關(guān)（因?yàn)镃＝1時(shí)，B也等于1），同樣。

這就是說明前面講過的內(nèi)容還有欠缺的地方。

我們觀察上面的真值表發(fā)現(xiàn)，A、B、C三個(gè)代表水位的邏輯變量，可能的取值只有000、100、110和111四種。其余四種取值001、010、011和101永遠(yuǎn)不可能出現(xiàn)。因?yàn)闆]有物理意義。如果001，C＝1，A＝B＝0這是不可能的。

自己證A、B、C永遠(yuǎn)不可能取001、010、011和101。與之對(duì)應(yīng)的四個(gè)最小項(xiàng)就永遠(yuǎn)為0。m1=0，m2=2，m3=0，m5=0或。

初等函數(shù)有定義域Y＝，不允許X取（－1，3）之間的數(shù)，邏輯函數(shù)也有類似的問題。上面講的水位檢測問題A、B、C的取值只有000、100、110、111四種情況，001、010、011和101無意義，永遠(yuǎn)不可能出現(xiàn)，與之對(duì)應(yīng)的四個(gè)最小項(xiàng)將永遠(yuǎn)為0，即。這就是下面要講的無關(guān)項(xiàng)問題。

無關(guān)項(xiàng)

由于邏輯變量的取值受到限制（約束），使得某些最小項(xiàng)（及其和）永遠(yuǎn)等于0，那些恒等于0的最小項(xiàng)就是無關(guān)項(xiàng)。

在卡諾圖中無關(guān)項(xiàng)用x表示。如對(duì)化簡邏輯函數(shù)有用，對(duì)組成更大的相鄰矩形組有用，可將他們吸收進(jìn)去（因?yàn)樗麄優(yōu)?，等于在邏輯函數(shù)中添加0）反之棄之。

例：將下列函數(shù)化為最簡與或函數(shù)式。

給定約束條件 AB+CD=0

約束條件

解：

??? .該卡諾圖上有四個(gè)矩形組
,其中m11，m13，m15三個(gè)無關(guān)項(xiàng)在化簡中沒有用到。