開關(guān)電路與布爾代數(shù).

1、開關(guān)電路與布爾代數(shù) 開關(guān)電路與布爾代數(shù)是根據(jù)教育部制訂的普通高中數(shù)學(xué)課程標(biāo)準(zhǔn)(實驗) 選修系列4第10個專題“開關(guān)電路與布爾代數(shù)”的要求編寫的，根據(jù)標(biāo)準(zhǔn)的要求,教科書以開關(guān)電路設(shè)計為背景引入一種類似數(shù)的對象并引入這些對象之間的運算.因為,在初中物理中,我們都學(xué)習(xí)了基本電路串聯(lián)電路和并聯(lián)電路，已經(jīng)熟悉了這些電路的基本功能, 也能熟練地利用這些電路搭建較為復(fù)雜的電路，那么能不能用數(shù)學(xué)來幫助我們刻畫這些現(xiàn)象呢?于是,我們將對這種新的運算系統(tǒng)進行探討,得出類似于“數(shù)的運算”的各種性質(zhì)，最后應(yīng)用這個數(shù)學(xué)理論, 徹底解決開關(guān)電路的設(shè)計問題，這就是本專題將要解決的問題.本專題以設(shè)計由三人控制一個電燈的電路為

2、背景，從開關(guān)電路設(shè)計，提出一個具體問題，將電路設(shè)計數(shù)學(xué)化為電路代數(shù)和電路多項式，再數(shù)學(xué)地研究電路和電路多項式，完全解決最初提出的問題,完整地給出一個電路代數(shù)的數(shù)學(xué)模型，這也是布爾代數(shù)的一個實際應(yīng)用,從中可感受到數(shù)學(xué)化的抽象過程，以及數(shù)學(xué)理論的應(yīng)用價值.一、背景知識介紹布爾代數(shù)又稱邏輯代數(shù)，正是以它的創(chuàng)立者英國數(shù)學(xué)家喬治.布爾（G.Boole）而命名.1815年生于倫敦的布爾家境貧寒，父親是位鞋匠，無力供他讀書.他的學(xué)問主要來自于自學(xué).年僅12歲，布爾就掌握了拉丁文和希臘語，后來又自學(xué)了意大利語和法語.16歲開始任教以維持生活，從20歲起布爾對數(shù)學(xué)產(chǎn)生了濃厚興趣，廣泛涉獵著名數(shù)學(xué)家牛頓、拉普拉斯

3、、拉格朗日等人的數(shù)學(xué)名著，并寫下大量筆記.這些筆記中的思想，1847年被用于他的第一部著作邏輯的數(shù)學(xué)分析之中.1854年，已經(jīng)擔(dān)任柯克大學(xué)教授的布爾再次出版思維規(guī)律的研究邏輯與概率的數(shù)學(xué)理論基礎(chǔ).以這兩部著作，布爾建立了一門新的數(shù)學(xué)學(xué)科.l      在布爾代數(shù)里，布爾構(gòu)思出一個關(guān)于0和1的代數(shù)系統(tǒng)，用基礎(chǔ)的邏輯符號系統(tǒng)描述物體和概念.這種代數(shù)不僅廣泛用于概率和統(tǒng)計等領(lǐng)域，更重要的是，它為今后數(shù)字計算機開關(guān)電路設(shè)計提供了最重要數(shù)學(xué)方法.l      布爾一生發(fā)表了50多篇科學(xué)論文、兩部教科書和兩

4、卷數(shù)學(xué)邏輯著作.為了表彰他的成功，都柏林大學(xué)和牛津大學(xué)先后授予這位自學(xué)的成才的數(shù)學(xué)家榮譽學(xué)位，他還被推選為英國皇家學(xué)會會員. 開關(guān)電路與布爾代數(shù)的關(guān)系信息論的創(chuàng)始人克勞德·香農(nóng)（C. E. Shannon）對現(xiàn)代電子計算機的產(chǎn)生和發(fā)展有重要影響，是電子計算機理論的重要奠基人之一，1938年，香農(nóng)發(fā)表了著名的論文繼電器和開關(guān)電路的符號分析，首次用布爾代數(shù)進行開關(guān)電路分析，并證明布爾代數(shù)的邏輯運算，可以通過繼電器電路來實現(xiàn)，明確地給出了實現(xiàn)加，減，乘，除等運算的電子電路的設(shè)計方法.這篇論文成為開關(guān)電路理論的開端l      香農(nóng)在貝爾實驗

5、室工作中進一步證明，可以采用能實現(xiàn)布爾代數(shù)運算的繼電器或電子元件來制造計算機，香農(nóng)的理論還為計算機具有邏輯功能奠定了基礎(chǔ)，從而使電子計算機既能用于數(shù)值計算，又具有各種非數(shù)值應(yīng)用功能，使得以后的計算機在幾乎任何領(lǐng)域中都得到了廣泛的應(yīng)用.l      1840年取得了博士學(xué)位，香農(nóng)在AT&T貝爾實驗室里度過了碩果累累的15年.他用實驗證實，完全可以采用繼電器元件制造出能夠?qū)崿F(xiàn)布爾代數(shù)運算功能的計算機.1948年，申龍又發(fā)表了另一篇至今還在閃爍光芒的論文通信的數(shù)學(xué)基礎(chǔ)， 從而給自己贏來“信息論之父”的桂冠.l   

6、;1956年，他參與發(fā)起了達特默斯人工智能會議，成為這一新學(xué)科的開山鼻祖之一.他不僅率先把人工智能運用于電腦下棋方面，而且發(fā)明了一個能自動穿越迷宮的電子老鼠，以此證明計算機可以通過學(xué)習(xí)提高智能.l   計算機運行的時候，程序就象一系列或真或假的命題，當(dāng)命題進入電路時，按布爾代數(shù)他們將電路打開或關(guān)閉，例如當(dāng)兩個真的命題進入一個電路時.電路打開，但是當(dāng)一個真的命題和一個假的命題進入一個電路時，電路關(guān)閉，利用布爾代數(shù)，我們就可以把數(shù)以百計的電路結(jié)合起來，并編寫出充滿想象力的計算機應(yīng)用程序. l 今天，布爾代數(shù)已成為我們生活中的一部分，因為我們的汽車、音響、電視和其它用具

7、中都有計算機技術(shù)，它幾乎無處不在，無所不能.實際上大多數(shù)人還沒有意識.二、開關(guān)電路 開關(guān)電路就是由開關(guān)經(jīng)多次并聯(lián)、串聯(lián)與反演所得到的電路. 每一開關(guān)有兩種狀態(tài):通和不通,每一電路也有兩種狀態(tài): 通和不通.下面將用小寫英文字母表示開關(guān), 大寫英文字母表示電路, 但由一個開關(guān)a組成的電路，仍記作a.并聯(lián)和串聯(lián)電路我們在初中就見過了，已經(jīng)很熟悉了，現(xiàn)簡單說下電路的反演，它就是指在開關(guān)a“通”時，電路A的狀態(tài)是“不通”，開關(guān)a“不通”時，電路A的狀態(tài)是“通”，這樣的電路在物理上是可以實現(xiàn)的. 一般地對任意電路A , B 也可經(jīng)并聯(lián),串聯(lián)或反演得到新的電路,它們順序記作“A 并聯(lián)B”、“A串聯(lián)B”、“A

8、 的反演”. 原來A 、B 的狀態(tài)與這些新作成的電路的狀態(tài)之間的關(guān)系列表如下:電路A 電路B A并聯(lián)B通 通 通通 不通 通不通 通 通不通 不通 不通電路A 電路B A串聯(lián)B通 通 通通 不通 不通不通 通 不通不通 不通 不通電路A A 的反演通 不通不通 通  我們已很習(xí)慣數(shù)學(xué)中常用的符號化方法. 只要把上面各表中的狀態(tài)“通”、“不通”用簡單符號表示,就能大大簡化. 我們借用數(shù)字“1”表示“通”,借用數(shù)字“0”表示“不通”. 當(dāng)然在這里“1”,“0”已失去原來的數(shù)字意義, 只是代表“通”,“不通”.我們再進一步符號化, 而將用“+”表示“并聯(lián)”,用“·”表示“串聯(lián)”,

9、用“- ”表示“反演”,這樣A + B 就是“A 并聯(lián)B”, A ·B 就是“A 串聯(lián)B”, 就是“A 的反演”,于是我們就有:A B A + B1 1 11 0 10 1 10 0 0A B A ·B1 1 11 0 00 1 00 0 0A 1 00 1現(xiàn)在來看看經(jīng)過這些符號化后，我們能得什么.任何一個電路，例如A（如圖），可表成一個“代數(shù)”式：當(dāng)然每一個類似上面這樣由一些小寫字母（表示開關(guān)）經(jīng)“+”,“·”,“- ”, 以及適當(dāng)?shù)睦ㄌ栠B接起來的式子也給出一個電路來.欲知電路A 的效應(yīng),例如當(dāng)a = 1 (開關(guān)a 處于“通”狀態(tài)) , b = 0 , c =

10、1 , d = 1 時A 的狀態(tài)是什么,只把這些值代入上面的式子, 按照上表提供的規(guī)則進行計算一下便得,這就是:( (1 ·0) + (1 ·1) ) + 1 = (0 + 1) + 0 = 1 +0 = 1 ,即此時A 的狀態(tài)是“通”.在本節(jié)最后,我們提出下面一個具體問題:設(shè)計一個使三個人控制一個電燈的電路. 也就是說,設(shè)計一個由三個開關(guān)a , b , c 組成的電路A = f ( a , b , c) 使得任一開關(guān)狀態(tài)的改變都使電路A = f ( a , b , c) 的狀態(tài)改變, 即實現(xiàn)下表效應(yīng)的電路Aa b c A = f ( a , b , c)0 0 0 00

11、0 1 10 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1 這是電路設(shè)計最基本最重要的問題:實現(xiàn)我們所要求效應(yīng)的電路. 我們將在下一節(jié)完全解決這一問題.三 布爾(Boole) 代數(shù)1.布爾代數(shù)在上一節(jié)開關(guān)電路的介紹之后, 在數(shù)學(xué)中引入下面定義就是水到渠成的事了:定義1 設(shè)集合B = 0 ,1 . 在集合B 上規(guī)定三個運算,分別記作“+”(加) ,“·”(乘) ,“- ”(非) ,如下：+ : 0 + 0 = 0 0 + 1 = 11 + 0 = 11 + 1 = 1·: 0 ·0 = 00 ·1 = 01 ·

12、0 = 01 ·1 = 1- : = 1= 0集合B 連同這三個運算一起B(yǎng) = 0 ,1 , + , ·,- 稱之為布爾代數(shù). 把新定義的布爾代數(shù)和我們熟悉的整數(shù)系相對比. 這里的B = 0 ,1 相當(dāng)于整數(shù)集Z= 0 , ±1 , ±2 , , B 的加法“+”(“·”) 可和Z 的加(乘) 法對比. B 中還有運算“- ”,這是Z 中沒有的. 這一簡單對比使我們想到數(shù)的加法,乘法適合交換律, 結(jié)合律, 還有乘法對加法的分配律, 而這些算律在我們進行計算時提供很大方便. 現(xiàn)在來看一看,這些算律對布爾代數(shù)是否成立.和初中代數(shù)中用字母a , b

13、, c , ,代數(shù)任意數(shù)一樣, 我們對布爾代數(shù)B 也引入變元a , b , c , ,但這里該提醒的是:B 上的變元只能代表B 中的元素,即0 或1.今證布爾代數(shù)中加法, 乘法適合交換律和結(jié)合律,即證在B 中有:a + b = b + a , a ·b = b ·a( a + b) + c = a + ( b + c) , （1）( a ·b) ·c = a ·( b ·c)在數(shù)學(xué)證明之前,我們看一下( a ·b) ·c = a ·( b ·c) 在開關(guān)電路中說明什么.( a ·b)

14、·c 可解釋為開關(guān)電路,而a ·( b ·c) 可解釋為開關(guān)電路. 一眼就看出,這兩個電路是等效的,這說明( a ·b) ·c = a ·( b ·c) . 你可以把這個說明看成B 中乘法適合結(jié)合律的“物理證明”, 也可以把這個電路背景的說明看成是物理上強烈支持這個數(shù)學(xué)結(jié)果,因而仍需要一個數(shù)學(xué)證明. 下面給出( a ·b) ·c = a ·( b ·c) 的數(shù)學(xué)證明,這就是驗算,當(dāng)a , b , c 取B = 0 ,1 中任意值時, ( a ·b) ·c 都等于a

15、·( b ·c) ,這可從下表中看出a b c ( a ·b) ·c a ·( b ·c)0 0 0 (0 ·0) ·0 = 0 ·0 = 0 0 ·(0 ·0) = 0 ·0 = 00 0 1 (0 ·0) ·1 = 0 ·1 = 0 0 ·(0 ·1) = 0 ·0 = 00 1 0 (0 ·1) ·0 = 0 ·0 = 0 0 ·(1 ·0) = 0 ·

16、;0 = 00 1 1 · ·1 0 0 · ·1 0 1 · ·1 1 0 · ·1 1 1 (1 ·1) ·1 = 1 ·1 = 1 1 ·(1 ·1) = 1 ·1 = 1這里我們嚴(yán)格地按照定義1 中的規(guī)定進行討論的,在數(shù)學(xué)上定義1 是我們對布爾代數(shù)B 進行討論的唯一依據(jù).類似地可以給出(1) 中其它三個等式的數(shù)學(xué)證明(以及“物理證明”) .把布爾代數(shù)與數(shù)系相對比,數(shù)系還提示我們:應(yīng)該考慮考慮乘法對加法的分配律是否在布爾代數(shù)B 中也成立,有趣的是,不

17、但在B 中a ·( b + c)= a ·b + a ·c 成立,并且也有加法對乘法的分配律, a + ( b ·c) = ( a + b) ·( a + c) ,它們的數(shù)學(xué)證明以及“物理證明”我們類似可以一樣地完成.把布爾代數(shù)與開關(guān)電路相聯(lián)系, 物理也會給我們一些啟示,那樣一些等式在布爾代數(shù)B 中可能是對的,例如,兩個開關(guān)a 并聯(lián)和由一個開關(guān)a作成的電路是等效的,這提示我們a + a = a 在B中該是對的, 類似地a ·a = a 在B 中也該是對的.下面定理匯集了布爾代數(shù)中常用的基本等式:定理1 在布爾代數(shù)B = 0 ,1 ,

18、+ , ·,-中下列等式成立;1) a + b = b + a (加法交換律) ,a ·b = b ·a (乘法交換律) ;2) ( a + b) + c = a + ( b + c) (加法結(jié)合律) ,( a ·b) ·c = a ·( b ·c) (乘法結(jié)合律) ;3) a ·( b + c) = a ·b + a ·c (乘法對加法的分配律) ,a + ( b ·c) = ( a + b) ·( a + c) (加法對乘法的分配律)4) a + 0 = a , a &#

19、183;1 = a ,a + 1 = 1 , a ·0 = 0 ;5) a + a = a (加法的冪等律) ,a ·a = a (乘法的冪等律) ;6) ;7) , ；8) ， 證明6) 的證明:當(dāng)a = 0 時, ，而當(dāng)a=1時，.故當(dāng)a取任意值時，都有 .6）得證 7）的證明如下表a b 0 0 = 1 + 1 = 10 1 = 1 + 0 = 11 0 = 0 + 1 = 11 1 = 0 + 0 = 0其它的證明類似都可完成. 這里很多定律，特別是5），和數(shù)的運算規(guī)則很不一樣，但在布爾代數(shù)中卻是成立的.2.布爾多項式 把布爾代數(shù)B 上的一些變元以及0 和1 用布爾

20、代數(shù)B 的三個運算逐次運算(合理聯(lián)結(jié)) 起來的式子,就叫做布爾多項式.例如等等都是布爾多項式，但，例如卻不是布爾多項式，因為它不是合理聯(lián)結(jié)起來的，對它我們無法逐次進行運算.下面我們來說明什么時候兩個布爾多項式是相等的，我們規(guī)定：兩個布爾多項式相等，當(dāng)且僅當(dāng)其中變元取定任意值時，這兩個布爾多項式的值相等.也就是說，我們是從“函數(shù)觀點”來看待他們相等，而不管它們形式上是否一樣，例如布爾多項式和是相等的.我們知道，在中學(xué)討論數(shù)系上的多項式時有兩個問題，一是化簡（去括號、合并同類項等），二是標(biāo)準(zhǔn)形式.先來說多項式的化簡，化簡時每一步只能根據(jù)定理1中的各種算律，不能有一點馬虎.為了方便，我們約定“先乘后

21、加”，“略去乘號”，并將隨時隨地使用結(jié)合律、交換律.根據(jù)冪等律，永遠可用a代替aa，因而化簡后,可使乘積中同一因子只出現(xiàn)一次, 類似地, 化簡時可用a 代替a + a ,因而在求和時可認(rèn)定每一加項只出現(xiàn)一次,根據(jù)定理1 中4) ,布爾多項式在化簡后沒有“常數(shù)項”,因為若“常數(shù)項”是0 ,則可略去;若它是1 ,則整個布爾多項式就等于1 了,所以除布爾多項式本身是0 或1 外,可認(rèn)定它們沒有“常數(shù)項”,類似地,我們可認(rèn)定每一乘積前是沒有“系數(shù)”的.作為舉例, 我們來化簡上面第二個布爾多項式.下面我們來考慮布爾多項式的標(biāo)準(zhǔn)形式，還是以上面布爾多項式為例，該多項式涉及a,b,c三個變元，化簡結(jié)果雖已得

22、“積之和”的形式，但這些乘積項中有的只出現(xiàn)兩個變元，甚至只含一個變元，很不整齊，我們希望每一乘積項三個變元全部出現(xiàn)，利用定理1，特別是及a ·1 = a，這是可以辦到的，作法如下：這樣，這個三個變元a,b,c的布爾多項式就化成“和之積”的形式且在每一乘積項中三個變元都各出現(xiàn)一次，即得到這個布爾多項式的標(biāo)準(zhǔn)形式.從這個例子我們看到每個布爾多項式都可以化成標(biāo)準(zhǔn)形式.由 , , 中各取一個元素作成的乘積共個，除上式中最后一個式子所出現(xiàn)的7 個外,還有一個,就是,而三元布爾多項式的標(biāo)準(zhǔn)形式就是從這8 個乘積中取出一部分作和而得,這樣,三元布爾多項式的標(biāo)準(zhǔn)形式共有個(取全部8 個乘積作和而得到

23、的布爾多項式,你將知道,就是布爾多項式1 , 而一個乘積都不取的情況, 我們把它理解為布爾多項式0) , 一般地我們有, n 個變元布爾多項式的標(biāo)準(zhǔn)形式的個數(shù)是. 直接按照兩個布爾多項式相等的定義去判斷布爾多項式的相等,就得進行大量的驗算,很麻煩,在這里標(biāo)準(zhǔn)形式提供極大的方便,因為我們有定理2 兩個標(biāo)準(zhǔn)形式的布爾多項式相等當(dāng)且僅當(dāng)它們具有完全相同的形式.這樣,只需把它們化成標(biāo)準(zhǔn)形式,再看看這兩個標(biāo)準(zhǔn)形式是不是完全一樣就可判斷它們是否相等,方便多了.至此我們對布爾代數(shù)的“代數(shù)”部分的討論暫告一段落.下面我們來討論布爾代數(shù)上的函數(shù)布爾函數(shù).定義2 以布爾代數(shù)B 上n 個變元x1 , x2 ,xn

24、為自變量, 且在B = 0 ,1 中取值的函數(shù)f (x1 , x2 ,xn)稱為n 元布爾函數(shù).例如在§1 最末的那個表就給出一個三元布爾函數(shù). 我們知道數(shù)系上的n 元函數(shù)多得不得了,復(fù)雜的不得了,而n 元多項式函數(shù)只是其中非常特殊的一小部分.然而對布爾代數(shù)上的n 元布爾函數(shù)情況就簡單多了,熟悉排列組合的同學(xué)可以很快算出,共有個不同的n 元布爾函數(shù),這樣由定理2 , n 元布爾多項式的個數(shù)也是,所以每一個n 元布爾函數(shù)都可以用n 元布爾多項式去實現(xiàn),這就等于說,每一布爾函數(shù)都可以用一個開關(guān)電路實現(xiàn), 然而實際上我們必需要知道, 對給定的n 元布爾函數(shù)究竟是哪個n 元布爾多項式能實現(xiàn)它

25、, 這是該進一步要解決的問題.下面我們直接、徹底地解決用n 元布爾多項式實現(xiàn)n 元布爾函數(shù)的問題, 并且不依賴于上面這個計數(shù)結(jié)果,通過1 末這個具體例子來說明,它是一個三元布爾函數(shù),其定義域由8個形如( a , b ,c) 的點組成, 并且要求在( a , b , c) = (0 ,0 ,1) ,(0 ,1 ,0) , (1 ,0 ,0) , (1 ,1 ,1) 處布爾函數(shù)f ( a , b , c)取值1 ,在其它處f ( a , b , c) 取值0.如果我們會造一個布爾多項式,它在一點說是(0 ,0 ,1) 上取值1 ,而在其余點上取值0 ,則一切問題就解決了; 只要把取值為1 的各點相應(yīng)的這種布爾多項式加起來就行了, 找到這樣的布爾多項式是很容易的; 就是,它只當(dāng)a = 0 , b = 0 ,c = 1時取值1 ,而在其它情形, a , b , c 中必至少有一個是0 ,因而其乘積 必是0 ,這樣在(0 ,0 ,1) 上取1 ,在其余點上取0 的布爾多項式是 ;在(0 ,1 ,0) 上取1 ,在其余點上取0 的布爾