第3章布爾代數與邏輯函數化簡

第三章布爾代數與邏輯函數化簡3.1基本公式和法則3.2邏輯函數的代數法化簡3.3卡諾圖化簡第一頁，編輯于星期六：二十點四十五分。一、基本公式

邏輯常量運算公式邏輯變量與常量的運算公式0

·

0

=

00

·

1

=

01

·

0

=

01

·

1

=

10

+

0

=

00

+

1

=

11

+

0

=

11

+

1

=

10–1律重疊律互補律還原律0+A=A1+A=11·A=A0·A=0A+A=AA·A=A

3.1基本公式和規(guī)則第二頁，編輯于星期六：二十點四十五分。二、基本定律

(一)

與普通代數相似的定律

交換律

A+B=B+AA·B=B·A結合律(A+B)+C=A+(B+C)(A·B)·C=A·(B·C)分配律

A(B+C)=AB+AC

A+BC=(A+B)(A+C)普通代數沒有！利用真值表邏輯等式的證明方法

利用基本公式和基本定律第三頁，編輯于星期六：二十點四十五分。111111111100

例1

證明等式A+BC=(A+B)(A+C)解：真值表法公式法右式=(A+B)(A+C)用分配律展開=AA+AC+BA+BC=A+AC+AB+BC=A(1+C+B)+BC=A·1+BC=A+BC0000ABCA+BC(A+B)(A+C)000001010011100101110111=左式第四頁，編輯于星期六：二十點四十五分。

(二)

邏輯代數的特殊定理

吸收律A+AB=A

A+AB=A(1+B)=A

第五頁，編輯于星期六：二十點四十五分。0011111011011100A+BA·BA

B0011001000011100A·BA+BA

B

(二)

邏輯代數的特殊定理

吸收律

A+AB=A

推廣公式：思考：(1)若已知

A+B=A+C，則

B=C嗎？

(2)若已知

AB=AC，則B=C嗎？

推廣公式：摩根定律

(又稱反演律)第六頁，編輯于星期六：二十點四十五分。三、重要規(guī)則

(一)

代入規(guī)則

A

A

A

A均用代替A均用代替B均用C代替利用代入規(guī)則能擴展基本定律的應用。

將邏輯等式兩邊的某一變量均用同一個邏輯函數替代，等式仍然成立。第七頁，編輯于星期六：二十點四十五分。例2

證明解這是兩變量的求反公式，若將等式兩邊的B用B+C代入便得到這樣就得到三變量的摩根定律。第八頁，編輯于星期六：二十點四十五分。變換時注意：(1)不能改變原來的運算順序。(2)反變量換成原變量只對單個變量有效，而長非

號保持不變?？梢?，求邏輯函數的反函數有兩種方法：利用反演規(guī)則或摩根定律。原運算次序為

(二)

反演規(guī)則

對任一個邏輯函數式

Y，將“·”換成“+”，“+”換成“·”，“0”換成“1”，“1”換成“0”，原變量換成反變量，反變量換成原變量，則得到原邏輯函數的反函數。第九頁，編輯于星期六：二十點四十五分。

(三)

對偶規(guī)則

對任一個邏輯函數式

Y，將“·”換成“+”，“+”換成“·”，“0”換成“1”，“1”換成“0”，則得到原邏輯函數式的對偶式

Y

。

對偶規(guī)則：兩個函數式相等，則它們的對偶式也相等。

應用對偶規(guī)則可將基本公式和定律擴展。變換時注意：(1)

變量不改變

(2)不能改變原來的運算順序A+AB=AA·(A+B)=A

第十頁，編輯于星期六：二十點四十五分。四、基本公式應用1.證明等式例3用公式證明解第十一頁，編輯于星期六：二十點四十五分。2.邏輯函數不同形式的轉換

邏輯函數的形式是多種多樣的，一個邏輯問題可以用多種形式的邏輯函數來表示，每一種函數對應一種邏輯電路。邏輯函數的表達形式通?？煞譃槲宸N：與或表達式、與非-與非表達式、與或非表達式、或與表達式、或非-或非表達式。第十二頁，編輯于星期六：二十點四十五分。例4

將函數與或表達式轉換為其它形式。解(1)與非-與非式。將與或式兩次取反，利用摩根定律可得(2)與或非式。首先求出反函數然后再取反一次即得與或非表達式

_____CABACAABF+=+=第十三頁，編輯于星期六：二十點四十五分。(3)或與式。

將與或非式用摩根定律展開，即得或與表達式如下：(4)或非-或非式。將或與表達式兩次取反，用摩根定律展開一次得或非-或非表達式第十四頁，編輯于星期六：二十點四十五分。圖3–1同一邏輯的五種邏輯圖第十五頁，編輯于星期六：二十點四十五分。一、邏輯函數及其表示方法

邏輯函數描述了某種邏輯關系。常采用真值表、邏輯函數式、卡諾圖和邏輯圖等表示。1.真值表列出輸入變量的各種取值組合及其對應輸出邏輯函數值的表格稱真值表。列真值表方法(1)按

n位二進制數遞增的方式列出輸入變量的各種取值組合。(2)分別求出各種組合對應的輸出邏輯值填入表格。3.2邏輯函數的代數法化簡第十六頁，編輯于星期六：二十點四十五分。00000111011101111111011110110011110101011001000111100110101000101100010010000000YDCBA輸出變量輸入變量4個輸入變量有24

=16種取值組合。第十七頁，編輯于星期六：二十點四十五分。2.邏輯函數式表示輸出函數和輸入變量邏輯關系的表達式。又稱邏輯表達式，簡稱邏輯式。邏輯函數式一般根據真值表、卡諾圖或邏輯圖寫出。

(1)找出函數值為1的項。(2)將這些項中輸入變量取值為1的用原變量代替，取值為0的用反變量代替，則得到一系列與項。(3)將這些與項相加即得邏輯式。真值表邏輯式例如

ABC1000111100110101000100100100YCBA011010001111

邏輯式為第十八頁，編輯于星期六：二十點四十五分。3.邏輯圖運算次序為先非后與再或，因此用三級電路實現(xiàn)之。由邏輯符號及相應連線構成的電路圖。

根據邏輯式畫邏輯圖的方法:將各級邏輯運算用相應邏輯門去實現(xiàn)。例如畫的邏輯圖反變量用非門實現(xiàn)與項用與門實現(xiàn)相加項用或門實現(xiàn)第十九頁，編輯于星期六：二十點四十五分。例1圖示為控制樓道照明的開關電路。兩個單刀雙擲開關

A和

B分別安裝在樓上和樓下。上樓之前，在樓下開燈，上樓后關燈；反之，下樓之前，在樓上開燈，下樓后關燈。試畫出控制功能與之相同的邏輯電路。(1)

分析邏輯問題，建立邏輯函數的真值表11YAB0000110110(2)根據真值表寫出邏輯式解：方法：找出輸入變量和輸出函數，對它們的取值作出邏輯規(guī)定，然后根據邏輯關系列出真值表。設開關A、B合向左側時為0狀態(tài)，合向右側時為1狀態(tài)；Y表示燈，燈亮時為1狀態(tài)，燈滅時為0狀態(tài)。則可列出真值表為第二十頁，編輯于星期六：二十點四十五分。(3)畫邏輯圖

與或表達式(可用2個非門、

2個與門和1個或門實現(xiàn))異或非表達式(可用1個異或門和1個非門實現(xiàn))設計邏輯電路的基本原則是使電路最簡。第二十一頁，編輯于星期六：二十點四十五分。二、邏輯函數式化簡的意義與標準

化簡意義使邏輯式最簡，以便設計出最簡的邏輯電路，從而節(jié)省元器件、優(yōu)化生產工藝、降低成本和提高系統(tǒng)可靠性。不同形式邏輯式有不同的最簡式，一般先求取最簡與-或式，然后通過變換得到所需最簡式。第二十二頁，編輯于星期六：二十點四十五分。最簡與-或式標準(1)乘積項(即與項)的個數最少(2)每個乘積項中的變量數最少用與門個數最少與門的輸入端數最少

最簡與非式標準(1)非號個數最少(2)每個非號中的變量數最少用與非門個數最少與非門的輸入端數最少

第二十三頁，編輯于星期六：二十點四十五分。如直接由該函數式得到電路圖，則如圖3-3所示。圖3-3F原函數的邏輯圖第二十四頁，編輯于星期六：二十點四十五分。

但如果將函數化簡后其函數式為F=AC+B

只要兩個門就夠了，如圖3-4所示。圖3–4函數化簡后的邏輯圖第二十五頁，編輯于星期六：二十點四十五分。三、代數化簡法

運用邏輯代數的基本定律和公式對邏輯式進行化簡。并項法

運用，將兩項合并為一項，并消去一個變量。

任何兩個相同變量的邏輯項，只有一個變量取值不同(一項以原變量形式出現(xiàn)，另一項以反變量形式出現(xiàn))，我們稱為邏輯相鄰項(簡稱相鄰項)。如果函數存在相鄰項，可利用吸收律，將它們合并為一項，同時消去一個變量。第二十六頁，編輯于星期六：二十點四十五分。

解令

解利用等冪律，一項可以重復用幾次。第二十七頁，編輯于星期六：二十點四十五分。其中與其余四項均是相鄰關系，可以重復使用。解所以第二十八頁，編輯于星期六：二十點四十五分。吸收法

運用A+AB

=A和，消去多余的與項。第二十九頁，編輯于星期六：二十點四十五分。消去法

運用吸收律

，消去多余因子。第三十頁，編輯于星期六：二十點四十五分。配項法通過乘或加入零項進行配項，然后再化簡。例1

化簡例2

化簡第三十一頁，編輯于星期六：二十點四十五分。綜合靈活運用上述方法

[例]化簡邏輯式解：

應用[例]化簡邏輯式解：

應用應用AB第三十二頁，編輯于星期六：二十點四十五分。[例]化簡邏輯式解：

應用用摩根定律第三十三頁，編輯于星期六：二十點四十五分。作業(yè)：書P691(3)，2(1)(4)，3(2)(3)，4(1)(4)，5(2)(6)(8)第三十四頁，編輯于星期六：二十點四十五分。代數化簡法

優(yōu)點：對變量個數沒有限制。缺點：需技巧，不易判斷是否最簡式。

卡諾圖化簡法優(yōu)點：簡單、直觀，有一定的步驟和方法易判斷結果是否最簡。

缺點：適合變量個數較少的情況。一般用于四變量以下函數的化簡。一、代數化簡法與卡諾圖化簡法的特點3.3卡諾圖化簡第三十五頁，編輯于星期六：二十點四十五分。二、卡諾圖化簡的基本原理例解第三十六頁，編輯于星期六：二十點四十五分。n個變量有2n種組合，可對應寫出2n個乘積項，這些乘積項均具有下列特點：包含全部變量，且每個變量在該乘積項中(以原變量或反變量)只出現(xiàn)一次。這樣的乘積項稱為這n個變量的最小項，也稱為n變量邏輯函數的最小項。1.最小項的定義三、邏輯函數的標準式——最小項

第三十七頁，編輯于星期六：二十點四十五分。

一個變量A有2個最小項：二個變量AB有4個最小項：三個變量ABC有8個最小項：第三十八頁，編輯于星期六：二十點四十五分。

任何形式的邏輯式都可以轉化為標準與-或式，而且邏輯函數的標準與

-

或式是唯一的。

2.邏輯函數的最小項表達式

每一個與項都是最小項的與

-

或邏輯式稱為標準與

-

或式，又稱最小項表達式(不一定由全部最小項組成)。第三十九頁，編輯于星期六：二十點四十五分。例如是最小項表達式。而不是最小項表達式，而是一般式。

最小項表達式具有唯一性。任何邏輯函數的最小項表達式只有一個。第四十頁，編輯于星期六：二十點四十五分。3.由一般式獲得最小項表達式(1)代數法。對邏輯函數的一般式采用添項法，例如第四十一頁，編輯于星期六：二十點四十五分。(2)真值表法。將原邏輯函數A、B、C取不同值組合起來，得其真值表，而該邏輯函數是將F=1那些輸入變量相或而成的，如表3-4所示。

表3–4某邏輯函數的真值表第四十二頁，編輯于星期六：二十點四十五分。如何編號？如何根據輸入變量組合寫出相應最小項？例如

3變量邏輯函數的最小項有23=8個將輸入變量取值為1的代以原變量，取值為0的代以反變量，則得相應最小項。

簡記符號例如

1015m5m44100ABC111110101100011010001000最小項ABCm7m6m5m4m3m2m1m0輸入組合對應的十進制數765432104.最小項的編號第四十三頁，編輯于星期六：二十點四十五分。5.最小項的基本性質

(1)

對任意一最小項，只有一組變量取值使它的值為1，

而其余各種變量取值均使其值為0。三變量最小項表110000000111101000000110100100000101100010000100100001000011100000100010100000010001100000001000ABCm7m6m5m4m3m2m1m0ABC(2)

不同的最小項，使其值為1的那組變量取值也不同。(3)

對于變量的任一組取值，任意兩個最小項的乘積為0。(4)

對于變量的任一組取值，全體最小項的和為1。第四十四頁，編輯于星期六：二十點四十五分。如何將邏輯式轉化為標準與-或式呢

？[例]

將邏輯式化為標準與或式。(3)利用A+A=A，合并掉相同的最小項。0000m00001m11100m121101m131111m15=m0+m1+m12+m13+m15=∑m(0,1,12,13,15)解：(1)利用摩根定律和分配律把邏輯函數式展開為與或式。AB+(2)利用配項法化為標準與或式。第四十五頁，編輯于星期六：二十點四十五分。(一)

卡諾圖的構成

四、邏輯函數的卡諾圖表示法1.相鄰最小項

兩個最小項中只有一個變量互為反變量，其余變量均相同，稱為相鄰最小項，簡稱相鄰項。相鄰最小項重要特點：兩個相鄰最小項相加可合并為一項，

消去互反變量，化簡為相同變量相與。例如ABC+ABC=AB第四十六頁，編輯于星期六：二十點四十五分。

將n變量的2n個最小項用2n個小方格表示，并且使相鄰最小項在幾何位置上也相鄰且循環(huán)相鄰，這樣排列得到的方格圖稱為n個變量最小項卡諾圖，簡稱變量卡諾圖。2.卡諾圖及其構成方法第四十七頁，編輯于星期六：二十點四十五分。變量取0的代以反變量取1的代以原變量AB二變量卡諾圖0101000110110001AB0101m0m1m2m3ABAAB

BABABABAB四變量卡諾圖01

3

245

7

61213

15

14891110三變量卡諾圖ABC01000111

10

m6m7m4m2m3m0m5001m1ABCD00011110000111

10以循環(huán)碼排列以保證相鄰性第四十八頁，編輯于星期六：二十點四十五分。變量取0的代以反變量取1的代以原變量ABCD00011110000111

1001

3

245

7

61213

15

14891110ABCD相鄰項在幾何位置上也相鄰卡諾圖特點：循環(huán)相鄰性同一列最上與最下方格相鄰同一行最左與最右方格相鄰第四十九頁，編輯于星期六：二十點四十五分。如何寫出卡諾圖方格對應的最小項？

已知最小項如何找相應小方格？

例如

原變量取1，反變量取0。1001？ABCD0001111000011110

第五十頁，編輯于星期六：二十點四十五分。

(二)

用卡諾圖表示邏輯函數

(1)求邏輯函數真值表或者標準與-或式或者與-或式。

(2)

畫出變量卡諾圖。

(3)

根據真值表或標準與

-

或式或與

-

或式填圖?；静襟E用卡諾圖表示邏輯函數舉例

已知標準與或式畫函數卡諾圖

[例]

試畫出函數Y=∑m(0,1,12,13,15)的卡諾圖解：(1)畫出四變量卡諾圖(2)填圖邏輯式中的最小項m0、m1、m12、m13、m15對應的方格填1，其余不填。ABCD0001111000011110

0

1324576

12

13

151489

11

10

11

111

第五十一頁，編輯于星期六：二十點四十五分。已知真值表畫函數卡諾圖[例]

已知邏輯函數Y的真值表如下，試畫出Y的卡諾圖。解：(1)畫3變量卡諾圖。ABCY00010010010101101001101011011110ABC0100011110

6

7

5

4

2

31

0m0m2m4m6

1

1

1

1(2)找出真值表中Y=1對應的最小項，在卡諾圖相應方格中填1，其余不填。第五十二頁，編輯于星期六：二十點四十五分。已知一般表達式畫函數卡諾圖解：(1)將邏輯式轉化為與或式(2)作變量卡諾圖找出各與項所對應的最小項方格填1，其余不填。[例]已知，試畫出Y的卡諾圖。AB+ABCD0001111000011110(3)根據與或式填圖

11111111

1

1AB對應最小項為同時滿足A=1，

B=1的方格。BCD對應最小項為同時滿足B=1，C=0，D=1的方格AD對應最小項為同時滿足A=0，D=1的方格。第五十三頁，編輯于星期六：二十點四十五分。五、用卡諾圖化簡邏輯函數

化簡規(guī)律2

個相鄰最小項有

1個變量相異，相加可以消去這

1個變量，化簡結果為相同變量的與；

4個相鄰最小項有2個變量相異，相加可以消去這2個變量，化簡結果為相同變量的與；

8個相鄰最小項有3個變量相異，相加可以消去這3個變量，化簡結果為相同變量的與；……

2n個相鄰最小項有

n個變量相異，相加可以消去這

n個變量，化簡結果為相同變量的與。消異存同

第五十四頁，編輯于星期六：二十點四十五分。ABCD000111100001111011例如2個相鄰項合并消去

1個變量，化簡結果為相同變量相與。ABCD+ABCD=ABDABCD000111100001111011例如2個相鄰項合并消去

1個變量，化簡結果為相同變量相與。ABCD+ABCD=ABDABCD0001111000011110例如1111ABCD+ABCD+ABCD+ABCD=ACD+ACD=AD4個相鄰項合并消去2個變量，化簡結果為相同變量相與。8個相鄰項合并消去3個變量A11111

111第五十五頁，編輯于星期六：二十點四十五分。畫包圍圈規(guī)則包圍圈必須包含2n個相鄰1方格，且必須成方形。先圈小再圈大，圈越大越是好；1方格可重復圈，但須每圈有新1；每個“1”格須圈到，孤立項也不能掉。同一列最上邊和最下邊循環(huán)相鄰，可畫圈；同一行最左邊和最右邊循環(huán)相鄰，可畫圈；四個角上的1方格也循環(huán)相鄰，可畫圈。注意ABCD+ABCD+ABCD+ABCD卡諾

圖化

簡法

步驟畫函數卡諾圖

將各圈分別化簡對填1的相鄰最小項方格畫包圍圈將各圈化簡結果邏輯加

第五十六頁，編輯于星期六：二十點四十五分。m15

m9

m7

m6

m5

m4

m2

m0解：(1)畫變量卡諾圖[例]用卡諾圖化簡邏輯函數Y(A,B,C,D)=∑m(0,2,4,5,6,7,9,15)ABCD0001111000011110(2)填卡諾圖11111111(3)畫包圍圈abcd(4)將各圖分別化簡圈2個可消去

1個變量，化簡為3個相同變量相與。Yb=BCD圈4個可消去

2個變量，化簡為2個相同變量相與。孤立項Ya=ABCDYc=

AB循環(huán)相鄰

Yd=

AD(5)將各圖化簡結果邏輯加，得最簡與或式第五十七頁，編輯于星期六：二十點四十五分。解：(1)畫變量卡諾圖[例]用卡諾圖化簡邏輯函數Y(A,B,C,D)=∑m(0,2,5,7,8,10,12,14,15)ABCD0001111000011110(2)填卡諾圖11111111(4)求最簡與或式Y=1消1個剩3個(3)畫圈消2個剩2個4個角上的最小項循環(huán)相鄰第五十八頁，編輯于星期六：二十點四十五分。找

AB

=11,C

=

1

的公共區(qū)域找

A

=

1,

CD

=

01

的公共區(qū)域找

B

=

1,

D

=

1

的公共區(qū)域解：(1)畫變量卡諾圖ABCD0001111000011110(2)填圖11(4)化簡(3)畫圈[例]用卡諾圖化簡邏輯函數0011m30100m411111111要畫嗎？Y=第五十九頁，編輯于星期六：二十點四十五分。[例]化簡第六十頁，編輯于星期六：二十點四十五分。[例]已知函數真值表如下，試用卡諾圖法求其最簡與或式。ABCY00010011010001111001101011011111注意：該卡諾圖還有其他畫圈法可見，最簡結果未必唯一。解：(1)畫函數卡諾圖ABC01000111

101

1

1

111(3)化簡(2)畫圈Y=1

1

1

111ABC0100011110第六十一頁，編輯于星期六：二十點四十五分。六、其它邏輯形式的化簡1.與非邏輯形式

所謂與非式，就是全由與非門實現(xiàn)該邏輯，前面講邏輯函數相互變換時已講過，將與或式兩次求反即得與非式。第六十二頁，編輯于星期六：二十點四十五分。第六十三頁，編輯于星期六：二十點四十五分。

2.或與邏輯形式

首先從卡諾圖上求其反函數，其方法是圈“０”方格，然后再用摩根定律取反即得或與式。

例求的反函數和或與式。第六十四頁，編輯于星期六：二十點四十五分。

總結如下：在卡諾圖上圈“0”方格，其化簡結果：變量為0→原變量；變量為1→反變量，然后變量再相“或”起來，就得每一或項，最后再將每一或項“