布爾代數(shù)在開關(guān)電路設(shè)計(jì)中的應(yīng)用

1、布爾代數(shù)在計(jì)算機(jī)方面的應(yīng)用 信管一班 趙建強(qiáng)20151008111 布爾代數(shù)在開關(guān)電路設(shè)計(jì)中的應(yīng)用。開關(guān)是一種具有一個(gè)輸入和一個(gè)輸出的器件，我們將若干個(gè)開關(guān)的串聯(lián)與并聯(lián)構(gòu)成的電路稱為開關(guān)電路(Switching Circuits)。整個(gè)開關(guān)電路從功能上可看作是一個(gè)開關(guān)，把電路接通記為1，把電路斷開記為0。而開關(guān)電路中的開關(guān)也要么處于接通狀態(tài)，要么處于斷開狀態(tài)，這兩種狀態(tài)也可以用二值布爾代數(shù)來描述。一個(gè)具有n個(gè)獨(dú)立開關(guān)組成的開關(guān)電路稱為n元開關(guān)電路。整個(gè)開關(guān)電路是否接通完全取決于這些開關(guān)的狀態(tài)以及連接方式（串聯(lián)、并聯(lián)或反相），因而可以這些開關(guān)的函數(shù)。稱這樣的函數(shù)為開關(guān)函數(shù)(Switching F

2、unction)，可以寫成一個(gè)二值n元布爾式，稱為線路的布爾表達(dá)式。線路布爾式的構(gòu)造原則：串聯(lián)對(duì)應(yīng)布爾式中的積，并聯(lián)對(duì)應(yīng)布爾和，反相對(duì)應(yīng)布爾補(bǔ)。接通條件相同的線路稱為等效線路，兩個(gè)開關(guān)電路是等效的，當(dāng)且僅當(dāng)它們對(duì)應(yīng)的開關(guān)函數(shù)是等價(jià)的。找等效線路的目的是化簡(jiǎn)線路，使線路中包含的接點(diǎn)盡可能地少。利用布爾代數(shù)可設(shè)計(jì)一些具有指定性質(zhì)的節(jié)點(diǎn)線路，數(shù)學(xué)上即是按給定的真值表構(gòu)造相應(yīng)的布爾表達(dá)式（最后經(jīng)過適當(dāng)?shù)暮?jiǎn)化），理論上涉及到范式理論，但形式上并不難構(gòu)造。這樣就可以設(shè)計(jì)出符合要求的開關(guān)電路。例1 在舉重比賽中，通常設(shè)三名裁判：一名為主裁，另兩名為副裁。競(jìng)賽規(guī)則規(guī)定運(yùn)動(dòng)員每次試舉必須獲得主裁及至少一名副裁的

3、認(rèn)可，方算成功。裁判員的態(tài)度只能同意和不同意兩種；運(yùn)動(dòng)員的試舉也只有成功與失敗兩種情況。舉重問題可用邏輯代數(shù)加以描述：用A、B、C三個(gè)邏輯變量表示主副三裁判：取值1表示同意（成功），取值0表示不同意（失?。?。舉重運(yùn)動(dòng)員用L表示，取值1表示成功，0表示失敗。顯然，L由A、B、C決定。L為A、B、C的邏輯函數(shù)。列表如下，該表稱為邏輯函數(shù)L的真值表：ABC000001010011100101110111L00000111從真值表可看出L取值為1只有三項(xiàng)，A、B、C的取值分別為101、110、和111三種情況L才等于1。A*C、A*B*、A*B*C三項(xiàng)與上述三種取值對(duì)應(yīng)。由于上述三種情況之一出現(xiàn)就可判

4、定L成功，故L=(A*C)(A*B*)(A*B*C)=(A*C)(A*B*C)(A*B*)(A*B*C)=(A*C)(A*B)=A*(CB)根據(jù)上述布爾式來設(shè)計(jì)就可以得到舉重裁判的控制電路。其中K由主裁控制，K和K分別由兩個(gè)副裁控制。布爾代數(shù)在邏輯線路設(shè)計(jì)中的應(yīng)用。開關(guān)是一種只有一個(gè)輸入的器件。對(duì)于多輸入單輸出的情形則就要用邏輯門電路來實(shí)現(xiàn)。邏輯門電路可以用來做“與”、“或”、“非”等邏輯運(yùn)算。電子數(shù)字計(jì)算機(jī)芯片里使用成千上萬個(gè)微小的邏輯部件，它們都是由各種布爾邏輯元件邏輯門和觸發(fā)器組成的。同時(shí)一個(gè)邏輯門的輸出可以用為另一個(gè)邏輯門的輸入。因此由邏輯元件可以組成各種邏輯網(wǎng)絡(luò)，這樣任何復(fù)雜的邏輯關(guān)

5、系都可以由邏輯元件經(jīng)過相應(yīng)的組合來實(shí)現(xiàn)，使其具有復(fù)雜的邏輯判斷功能。這樣得到的邏輯電路可以用一個(gè)布爾式表示。通過對(duì)邏輯電路所對(duì)應(yīng)的布爾式進(jìn)行化簡(jiǎn)，我們就能分析電路有功能，并簡(jiǎn)化電路，既降低成本又提高可靠性。圖論1、圖論的歷史。圖論以圖為研究對(duì)象的數(shù)學(xué)分支。圖論中的圖指的是一些點(diǎn)以及連接這些點(diǎn)的線的總體。通常用點(diǎn)代表事物，用連接兩點(diǎn)的線代表事物間的關(guān)系。圖論則是研究事物對(duì)象在上述表示法中具有的特征與性質(zhì)的學(xué)科。在自然界和人類社會(huì)的實(shí)際生活中，用圖形來描述和表示某些事物之間的關(guān)系既方便又直觀。例如，國家用點(diǎn)表示，有外交關(guān)系的國家用線連接代表這兩個(gè)國家的點(diǎn)，于是世界各國之間的外交關(guān)系就被一個(gè)圖形描述

6、出來了。另外我們常用工藝流程圖來描述某項(xiàng)工程中各工序之間的先后關(guān)系，用網(wǎng)絡(luò)圖來描述某通訊系統(tǒng)中各通訊站之間信息傳遞關(guān)系，用開關(guān)電路圖來描述IC中各元件電路導(dǎo)線連接關(guān)系等等。事實(shí)上，任何一個(gè)包含了某種二元關(guān)系的系統(tǒng)都可以用圖形來模擬。由于我們感興趣的是兩對(duì)象之間是否有某種特定關(guān)系，所以圖形中兩點(diǎn)之間連接與否最重要，而連接線的曲直長短則無關(guān)緊要。由此經(jīng)數(shù)學(xué)抽象產(chǎn)生了圖的概念。研究圖的基本概念和性質(zhì)、圖的理論及其應(yīng)用構(gòu)成了圖論的主要內(nèi)容。圖論的產(chǎn)生和發(fā)展經(jīng)歷了二百多年的歷史，大體上可分為三個(gè)階段：第一階段是從1736年到19世紀(jì)中葉。當(dāng)時(shí)的圖論問題是盛行的迷宮問題和游戲問題。最有代表性的工作是著名數(shù)

7、學(xué)家L.Euler于1736年解決的哥尼斯堡七橋問題(Konigsberg Seven Bridges Problem)。東普魯士的哥尼斯堡城(現(xiàn)今是俄羅斯的加里寧格勒，在波羅的海南岸）位于普雷格爾(Pregel)河的兩岸，河中有一個(gè)島，于是城市被河的分支和島分成了四個(gè)部分，各部分通過7座橋彼此相通。如同德國其他城市的居民一樣，該城的居民喜歡在星期日繞城散步。于是產(chǎn)生了這樣一個(gè)問題：從四部分陸地任一塊出發(fā)，按什么樣的路線能做到每座橋經(jīng)過一次且僅一次返回出發(fā)點(diǎn)。這就是有名的哥尼斯堡七橋問題。哥尼斯堡七橋問題看起來不復(fù)雜，因此立刻吸引所有人的注意，但是實(shí)際上很難解決。瑞士數(shù)學(xué)家(Leonhard

8、Euler)在1736年發(fā)表的“哥尼斯堡七橋問題”的文章中解決了這個(gè)問題。這篇論文被公認(rèn)為是圖論歷史上的第一篇論文，Euler也因此被譽(yù)為圖論之父。歐拉把七橋問題抽象成數(shù)學(xué)問題-一筆畫問題，并給出一筆畫問題的判別準(zhǔn)則，從而判定七橋問題不存在解。Euler是這樣解決這個(gè)問題的：將四塊陸地表示成四個(gè)點(diǎn)，橋看成是對(duì)應(yīng)結(jié)點(diǎn)之間的連線，則哥尼斯堡七橋問題就變成了：從A，B，C，D任一點(diǎn)出發(fā)，通過每邊一次且僅一次返回原出發(fā)點(diǎn)的路線(回路)是否存在？Euler證明這樣的回路是不存在的。第二階段是從19世紀(jì)中葉到1936年。圖論主要研究一些游戲問題：迷宮問題、博弈問題、棋盤上馬的行走線路問題。一些圖論中的著名

9、問題如四色問題(1852年)和Hamilton環(huán)游世界問題(1856年)也大量出現(xiàn)。同時(shí)出現(xiàn)了以圖為工具去解決其它領(lǐng)域中一些問題的成果。1847年德國的克?；舴?G.R.Kirchoff)將樹的概念和理論應(yīng)用于工程技術(shù)的電網(wǎng)絡(luò)方程組的研究。1857年英國的凱萊(A.Cayley)也獨(dú)立地提出了樹的概念，并應(yīng)用于有機(jī)化合物的分子結(jié)構(gòu)的研究中。1936年匈牙利的數(shù)學(xué)家哥尼格(D.Konig)寫出了第一本圖論專著有限圖與無限圖的理論(Theory of directed and Undirected Graphs)。標(biāo)志著圖論作為一門獨(dú)立學(xué)科。第三階段是1936年以后。由于生產(chǎn)管理、軍事、交通運(yùn)輸、

10、計(jì)算機(jī)和通訊網(wǎng)絡(luò)等方面的大量問題的出現(xiàn)，大大促進(jìn)了圖論的發(fā)展。特別是電子計(jì)算機(jī)的大量應(yīng)用，使大規(guī)模問題的求解成為可能。實(shí)際問題如電網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電路設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)以及社會(huì)科學(xué)中的問題所涉及到的圖形都是很復(fù)雜的，需要計(jì)算機(jī)的幫助才有可能進(jìn)行分析和解決。目前圖論在物理、化學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、社會(huì)科學(xué)及經(jīng)濟(jì)管理等幾乎所有學(xué)科領(lǐng)域都有應(yīng)用。2、平面圖和印刷電路板的設(shè)計(jì)。有時(shí)候，實(shí)際問題要求我們把圖畫在平面上，使得不是節(jié)點(diǎn)的地方不能有邊交叉，這在圖論中就是判斷一個(gè)圖是否是平面圖的問題。像印刷電路板(Printed Circuit Board，PCB)（單層印刷電路

11、板，多層印刷電路板）幾乎會(huì)出現(xiàn)在每一種電子設(shè)備中。PCB的主要功能是提供上頭各項(xiàng)零件的相互電氣連接。隨著電子設(shè)備越來越復(fù)雜，需要的元件越來越多，PCB上頭的導(dǎo)線與元件也越來越密集了。 板子本身的基板是由絕緣隔熱、不易彎曲的材料制作而成。在表面可以看到的細(xì)小線路材料是銅箔，原本銅箔是覆蓋在整個(gè)板子上的，而在制造過程中部份被蝕刻處理掉，留下來的部份就變成網(wǎng)狀的細(xì)小線路了。這些線路被稱作導(dǎo)線或布線，并用來提供PCB上元件的電路連接。 因此在設(shè)計(jì)和制造印刷電路板時(shí)，首先要解決的問題是判定一個(gè)給定的電路圖是否能印刷在同一層板上而使民線不發(fā)生短路？若可以，怎樣給出具體的布線方案？將要印刷的電路圖看成是一個(gè)

12、無向簡(jiǎn)單連通圖G，其中頂點(diǎn)代表電子元件，邊代表導(dǎo)線，于是上述問題歸結(jié)為判定G是否是平面圖？若G是平面圖，由怎樣給出它的一個(gè)平面表示來？平面圖的判斷問題，在數(shù)學(xué)上已由波蘭數(shù)學(xué)家?guī)炖蟹蛩够?Kuratowski) 于1930年解決。庫拉托夫斯基定理給出的充要條件看似簡(jiǎn)單，但實(shí)現(xiàn)起來很難。但是許多研究拓?fù)鋱D論的數(shù)學(xué)家提出了比較有效的圖的平面性判定的準(zhǔn)則，如DMP方法以就是其中的一個(gè)有代表性方法。3、圖的著色和四色問題。 圖的著色起源于“四色問題”。四色問題又稱四色猜想，是世界近代三大數(shù)學(xué)難題之一。四色問題是說畫在紙上的每張地圖只需要用4種顏色就能使具有共同邊界的國家不會(huì)有相同的顏色。用數(shù)學(xué)語言表示

13、，就是將平面任意地細(xì)分為不相重迭的區(qū)域，每一個(gè)區(qū)域總可以用1，2，3，4這四個(gè)數(shù)字之一來標(biāo)記，而不會(huì)使相鄰的兩個(gè)區(qū)域得到相同的數(shù)字。這里所指的相鄰區(qū)域，是指有一整段邊界是公共的。如果兩個(gè)區(qū)域只相遇于一點(diǎn)或有限多點(diǎn)，就不叫相鄰的。因?yàn)橛孟嗤念伾o它們著色不會(huì)引起混淆。四色猜想的提出來自英國。1852年，畢業(yè)于倫敦大學(xué)的格思里(F.Guthrie)來到一家科研單位搞地圖著色工作時(shí)，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都著上不同的顏色。”這個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？他和在大學(xué)讀書的弟弟格里斯決心試一試。兄弟二人為證明這一問題而使用的稿紙已經(jīng)堆了

14、一大疊，可是研究工作沒有進(jìn)展。1852年10月23日，他的弟弟就這個(gè)問題的證明請(qǐng)教了他的老師、著名數(shù)學(xué)家德·摩爾根(De Morgan)，摩爾根也沒有能找到解決這個(gè)問題的途徑，于是寫信向自己的好友、著名數(shù)學(xué)家漢密爾頓爵士(W.R. Hamilton)請(qǐng)教。漢密爾頓接到摩爾根的信后，對(duì)四色問題進(jìn)行論證。但直到1865年漢密爾頓逝世為止，問題也沒有能夠解決。起初，這個(gè)問題并沒有引起數(shù)學(xué)家們的注意，認(rèn)為這是一個(gè)不證即明的事實(shí)。但經(jīng)過一些嘗試之后，發(fā)現(xiàn)并不是那么回事。1878年，英國當(dāng)時(shí)最著名的數(shù)學(xué)家凱利(A. Cayley)正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的

15、問題。世界上許多一流的數(shù)學(xué)家都紛紛參加了證明四色猜想的大會(huì)戰(zhàn)。18781880年兩年間，著名的律師兼數(shù)學(xué)家肯普(Kempe)和泰勒(Taylor)兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四色猜想從此也就解決了。但是后來人們發(fā)現(xiàn)他們都錯(cuò)了。后來，越來越多的數(shù)學(xué)家雖然對(duì)此絞盡腦汁，但一無所獲。于是，人們開始認(rèn)識(shí)到，這個(gè)貌似容易的題目，其實(shí)是一個(gè)可與費(fèi)馬大定理相媲美的難題。不過肯普的證明雖然失敗了，但它在證明中提供的思想和方法仍然是后來許多數(shù)學(xué)家沖擊四色問題的基礎(chǔ)。美國數(shù)學(xué)家富蘭克林于1939年證明了22國以下的地圖都可以用四色著色。1950年，有人從22國推進(jìn)到35國。19

16、60年，有人又證明了39國以下的地圖可以只用四種顏色著色；隨后又推進(jìn)到了50國。但是這種推進(jìn)仍然十分緩慢。電子計(jì)算機(jī)問世以后，由于演算速度迅速提高，加之人機(jī)對(duì)話的出現(xiàn)，大大加快了對(duì)四色猜想證明的進(jìn)程。1976年6月，美國伊利諾大學(xué)的阿佩爾(Appel)、哈肯(Haken)和柯齊(Koch)三人合作編制了一個(gè)程序，在美國伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上，用了1260個(gè)小時(shí)，作了100多億次邏輯判斷，給出了四色猜想證明，轟動(dòng)了世界。這是一百多年來吸引許多數(shù)學(xué)家與數(shù)學(xué)愛好者的大事，當(dāng)兩位數(shù)學(xué)家將他們的研究成果發(fā)表的時(shí)候，當(dāng)?shù)氐泥]局在當(dāng)天發(fā)出的所有郵件上都加蓋了“四色足夠”的特制郵戳，以慶祝這一難

17、題獲得解決。“四色問題”的被證明不僅解決了一個(gè)歷時(shí)100多年的難題，而且成為數(shù)學(xué)史上一系列新思維的起點(diǎn)。在“四色問題”的研究過程中，不少新的數(shù)學(xué)理論隨之產(chǎn)生，也發(fā)展了很多數(shù)學(xué)計(jì)算技巧。如將地圖的著色問題化為圖論問題，豐富了圖論的內(nèi)容。不僅如此，“四色問題”在有效地設(shè)計(jì)航空班機(jī)日程表、設(shè)計(jì)計(jì)算機(jī)的編碼程序上都起到了推動(dòng)作用。不過不少數(shù)學(xué)家并不滿足于計(jì)算機(jī)取得的成就，他們認(rèn)為應(yīng)該有一種簡(jiǎn)捷明快的書面證明方法。直到現(xiàn)在，仍由不少數(shù)學(xué)家和數(shù)學(xué)愛好者在尋找更簡(jiǎn)潔的證明方法。4、運(yùn)輸網(wǎng)絡(luò)。自從克?；舴蜻\(yùn)用圖論從事電路網(wǎng)絡(luò)的結(jié)構(gòu)分析以來，網(wǎng)絡(luò)理論的研究和應(yīng)用就越來越廣泛。特別是近幾十年來，電路網(wǎng)絡(luò)、運(yùn)輸網(wǎng)絡(luò)

18、、通訊網(wǎng)絡(luò)等與工程和應(yīng)用密切相關(guān)的課題受到了高度的重視。無自回路的有向賦權(quán)圖稱為網(wǎng)絡(luò)(Network)。在一個(gè)網(wǎng)絡(luò)中，有向邊上的權(quán)稱為容量(Capacity)。網(wǎng)絡(luò)中入度為0的結(jié)點(diǎn)稱為源(Source)，用字母s表示；出度為0的結(jié)點(diǎn)稱為匯(Trap),用字母t表示。在某些問題，只考慮有單一源和單一匯的網(wǎng)絡(luò)（即運(yùn)輸網(wǎng)絡(luò)），而在另一些問題中（如通訊網(wǎng)絡(luò)），根本就不考慮源和匯。運(yùn)輸網(wǎng)絡(luò)的實(shí)際意義可以用公路網(wǎng)、鐵路網(wǎng)、和供水系統(tǒng)、電網(wǎng)等來說明，也就是“貨物從產(chǎn)地s，通過若干中轉(zhuǎn)站，到達(dá)目的地t”這類情形的一般模型。這里將源和匯分別看成是貨物的產(chǎn)地和目的地，其他結(jié)點(diǎn)是中轉(zhuǎn)站，有向邊是連接兩站的道路（公路

19、、鐵路、水管或電線等），容量則是某一段道路允許的通行能力的上限。在運(yùn)輸網(wǎng)絡(luò)中要考慮的是從源到匯的實(shí)際流通量，顯然它與每條有向邊的容量有關(guān)，也和每個(gè)結(jié)點(diǎn)的轉(zhuǎn)運(yùn)能力有關(guān)。對(duì)運(yùn)輸貨物來講，除了容量之外，每條邊還被賦予一個(gè)非負(fù)實(shí)數(shù)，這一組數(shù)若滿足以下條件：?jiǎn)挝粫r(shí)間內(nèi)通過每條道路運(yùn)送的貨物總量不能超過道路的容量；每一個(gè)中轉(zhuǎn)站的流入量等于流出量；源的流出量等于匯的總流入量（即網(wǎng)絡(luò)的流量(Discharge)）。則稱這組數(shù)為該運(yùn)輸網(wǎng)絡(luò)的一個(gè)流(Flow)。一個(gè)運(yùn)輸網(wǎng)絡(luò)中具有可能的最大值的流稱為最大流。在一個(gè)運(yùn)輸網(wǎng)絡(luò)中，可能不止一個(gè)最大流，即可能有幾個(gè)不同的流，都具有最大值。給定運(yùn)輸網(wǎng)絡(luò)求其最大流的問題，就是

20、怎樣使給定網(wǎng)絡(luò)在單位時(shí)間運(yùn)輸量最大的問題，并且確定當(dāng)網(wǎng)絡(luò)的流量最大時(shí)的流。最大流問題的解決顯然在現(xiàn)實(shí)生活中有很重大的應(yīng)用價(jià)值。5、通訊網(wǎng)絡(luò)。網(wǎng)絡(luò)應(yīng)用的另一重要方面是通訊網(wǎng)絡(luò)，如電話網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)、管理信息系統(tǒng)、醫(yī)療數(shù)據(jù)網(wǎng)絡(luò)、銀行數(shù)據(jù)網(wǎng)絡(luò)、開關(guān)網(wǎng)絡(luò)等等。這些網(wǎng)絡(luò)的基本要求是網(wǎng)絡(luò)中各用戶能夠快速安全地傳遞信息，不產(chǎn)生差錯(cuò)和故障，同時(shí)使建造和維護(hù)網(wǎng)絡(luò)所需費(fèi)用低。通訊網(wǎng)絡(luò)中最重要的整體問題是網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。根據(jù)用途和性能指標(biāo)的不同要求，通訊網(wǎng)絡(luò)有不同的拓?fù)浣Y(jié)構(gòu)，如環(huán)形網(wǎng)絡(luò)、樹形網(wǎng)絡(luò)、星形網(wǎng)絡(luò)、分布式網(wǎng)絡(luò)、網(wǎng)狀網(wǎng)絡(luò)及混合型網(wǎng)絡(luò)等等。通訊網(wǎng)絡(luò)是一個(gè)強(qiáng)連通的有向圖。除了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)之外，通訊網(wǎng)絡(luò)還要考慮

21、流量和控制問題、網(wǎng)絡(luò)的可靠性等問題。圖論中的連通度在通訊網(wǎng)絡(luò)中有著重要的應(yīng)用，是大規(guī)?；ミB容錯(cuò)網(wǎng)絡(luò)可靠性的有效性分析的基礎(chǔ)。當(dāng)然網(wǎng)絡(luò)的可靠性涉及的因素很多，但是從通訊網(wǎng)絡(luò)作為一個(gè)強(qiáng)連通的有向圖來說，一個(gè)具有最佳連通性的網(wǎng)絡(luò)就不易出現(xiàn)阻礙問題。6、二元樹的應(yīng)用-前綴碼(哈夫曼編碼)。在通訊系統(tǒng)中，常用二進(jìn)制來表示字符。但由于字符出現(xiàn)的頻率不一樣以及為了保密的原因，能否用不等長的二進(jìn)制數(shù)表示不同的字符，使傳輸?shù)男畔⑺玫目偞a元盡可能少呢？但是不等長的編碼方案給編碼和譯碼帶來了困難。為了解決這個(gè)問題，我們引入了前綴碼（哈夫曼編碼）。設(shè)abcd為一個(gè)長為n的字符串，則a,ab,abc分別為它的長為1,2,n-1的前綴(Pr