布爾代數(shù)在開關電路設計中的應用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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