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

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

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

3、認(rèn)可，方算成功。裁判員的態(tài)度只能同意和不同意兩種；運動員的試舉也只有成功與失敗兩種情況。舉重問題可用邏輯代數(shù)加以描述：用A、B、C三個邏輯變量表示主副三裁判：取值1表示同意（成功），取值0表示不同意（失?。Ｅe重運動員用L表示，取值1表示成功，0表示失敗。顯然，L由A、B、C決定。L為A、B、C的邏輯函數(shù)。列表如下，該表稱為邏輯函數(shù)L的真值表：ABC000001010011100101110111L00000111從真值表可看出L取值為1只有三項，A、B、C的取值分別為101、110、和111三種情況L才等于1。A*C、A*B*、A*B*C三項與上述三種取值對應(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è)計就可以得到舉重裁判的控制電路。其中K由主裁控制，K和K分別由兩個副裁控制。布爾代數(shù)在邏輯線路設(shè)計中的應(yīng)用。開關(guān)是一種只有一個輸入的器件。對于多輸入單輸出的情形則就要用邏輯門電路來實現(xiàn)。邏輯門電路可以用來做“與”、“或”、“非”等邏輯運算。電子數(shù)字計算機(jī)芯片里使用成千上萬個微小的邏輯部件，它們都是由各種布爾邏輯元件邏輯門和觸發(fā)器組成的。同時一個邏輯門的輸出可以用為另一個邏輯門的輸入。因此由邏輯元件可以組成各種邏輯網(wǎng)絡(luò)，這樣任何復(fù)雜的邏輯關(guān)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、怎樣使給定網(wǎng)絡(luò)在單位時間運輸量最大的問題，并且確定當(dāng)網(wǎng)絡(luò)的流量最大時的流。最大流問題的解決顯然在現(xiàn)實生活中有很重大的應(yīng)用價值。5、通訊網(wǎng)絡(luò)。網(wǎng)絡(luò)應(yīng)用的另一重要方面是通訊網(wǎng)絡(luò)，如電話網(wǎng)絡(luò)、計算機(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)生差錯和故障，同時使建造和維護(hù)網(wǎng)絡(luò)所需費用低。通訊網(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ò)是一個強(qiáng)連通的有向圖。除了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)之外，通訊網(wǎng)絡(luò)還要考慮

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