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

觀察函數(shù)

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

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

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

3.第一個乘積項是A、B、C、D的一個最小項，其余二項均不是A、B、C、D的最小項。

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

兩個邏輯變量A、B有22＝4個最小項，分別是：、、、。

三個邏輯變量A、B、C有23＝8個最小項，分別是：、、、、、、、。

四個邏輯變量A、B、C、D有24＝16個最小項。

練習：寫出A、B、C、D的十六個最小項。

最小項的性質(zhì)：

（1）對變量的任意一組取值，只有一個最小項為1，其余最小項全為0。二變量A、B的最小項為：、、、。對A、B的任意一組取值：

A=0 B=0 =1 其余三項全為0，即＝＝＝0

A=0 B=1 = 1 其余三項全為0

A=1 B=0 = 1 其余三項全為0

A=1 B=1 = 1 其余三項全為0

（2）全體最小項之和為1。（讀者自己證明）

（3）任意兩個最小項的乘積為0。

最小項的編號：

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

練習：讀者試寫出四變量A、B、C、D的十六個最小項m0、m1……m15。

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

任何邏輯函數(shù)都可化為最小項之和的標準形式

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

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

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

解一：

解二：列真值表

由真值表寫出的邏輯表達式

???

(全體最小項之和)

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

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

異或運算與同或運算

定義： 稱A與B異或，為異或運算符

A與B同或，為同或運算符

顯然：

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

由此推得：

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

同或運算則與之相反，且有

同學自己證明并牢記。

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

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

最小項的相鄰性

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

顯然，m0與m1具有相鄰性，而與不相鄰，因為他們有兩個因子不相同。m3與m4也不相鄰，而m3與m2相鄰。

相鄰的兩個最小項之和可以合并成一項，并消去一個變量。如：

卡諾圖

卡諾圖是美國工程師卡諾（Karnaugh）發(fā)明的。用小方塊（格）來表示最小項。三變量的卡諾圖畫八個小方塊（格）來表示八個最小項，四變量的卡諾圖畫十六個小方塊來表示十六個最小項?！?/P>

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

m0m1 ，m1m3 ，m3m2 ，m4m5 ，m5m7 ，m7m6 ， m0m4 ，m1m5 ，m3m7 ，m2m6都具有相鄰性，還有m0m2 ，m1m6也具有相鄰性（可理解成將卡諾圖卷成圓筒，他們在幾何上就相鄰了）。

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

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

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

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

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

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

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

解：1、畫出Y的卡諾圖

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

2、合并與化簡

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

例2．

解：1、畫出Y的卡諾圖

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

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

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

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

2． 若兩個最小項相鄰， 則可合并為一項，且消去一個因子。

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

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

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

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

我們來分析一個實際問題：

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

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

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

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

只開大閘門泄洪

大小閘門同時泄洪

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

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

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

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

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

無關(guān)項

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

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

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

給定約束條件 AB+CD=0

約束條件

解：

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