第3章 布爾代數(shù)和數(shù)字邏輯

第3章布爾代數(shù)和數(shù)字邏輯程利新哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院3.1概述喬治.布爾發(fā)明采用代數(shù)體系表示邏輯過程的方法，被稱為布爾代數(shù)。Atanasoff應(yīng)用布爾代數(shù)設(shè)計了“直接邏輯操作”的計算機(jī)方法，成為現(xiàn)代數(shù)字計算機(jī)的基本構(gòu)想。1938年，ClaudeShannon證明了2值的布爾代數(shù)可以描述2值的電學(xué)開關(guān)電路的操作。本章主要學(xué)習(xí)布爾邏輯和計算機(jī)系統(tǒng)中的實(shí)際物理部件之間的密切聯(lián)系。3.2布爾代數(shù)布爾代數(shù)是一種二值邏輯計算機(jī)中物理電路只有開關(guān)兩種狀態(tài)，因此和布爾代數(shù)有著很好的對應(yīng)。數(shù)字電路采用高低電壓表示各種數(shù)字信息。通常用1表示高電壓，即布爾代數(shù)中的真；用0表示低電壓，即布爾代數(shù)中的假。3.2.1布爾表達(dá)式布爾代數(shù)由布爾變量和布爾操作（算符）組合在一起構(gòu)成布爾表達(dá)式。布爾函數(shù)：輸入的是若干布爾變量，經(jīng)過布爾表達(dá)式的計算，能夠得到一個布爾結(jié)果。常用布爾算符：AND（與）、OR（或）和NOT（非）真值表：將布爾函數(shù)的所有輸入值及其組合方式列成表格形式，并給出對應(yīng)組合方式的函數(shù)值。邏輯算符AND邏輯算符OR邏輯算符NOT輸入輸出xyxy000010100111返回輸入輸出xyx+y000011101111返回輸入輸出0110返回3.2.1布爾表達(dá)式布爾代數(shù)處理的是二進(jìn)制變量和相關(guān)的邏輯運(yùn)算。布爾函數(shù)：輸入輸出xyz0001000011110100000110001001011011111100011110013.2.2布爾恒等式布爾表達(dá)式通常都需要化簡，化簡的基礎(chǔ)是布爾恒等式。布爾恒等式恒等式與(AND)形式或(OR)形式一致律1x=x0+x=x零律0x=01+x=1冪等律xx=xx+x=x互補(bǔ)律互換律xy=yxx+y=y+x結(jié)合律(xy)z=x(yz)(x+y)+z=x+(y+z)分配律x+yz=(x+y)(x+z)x(y+z)=xy+xz吸收律x(x+y)=xx+xy=x德摩根律還原律3.2.3布爾表達(dá)式的化簡布爾恒等式可以用來對布爾方程進(jìn)行化簡。這樣的方法更需要技巧性。3.2.4布爾表達(dá)式的補(bǔ)布爾算符既可以作用于布爾變量，也可以作用于布爾表達(dá)式。NOT算符作用于布爾表達(dá)式，可以得到該表達(dá)式的補(bǔ)布爾表達(dá)式取補(bǔ)的意義在于：在電子線路中，實(shí)現(xiàn)原布爾表達(dá)式的補(bǔ)較為簡單。取補(bǔ)的方法：德摩根定律。3.2.5布爾函數(shù)表示方法相同的布爾函數(shù)，可以有多種表示方法為了減少混淆，需要采用標(biāo)準(zhǔn)化的方法表示布爾函數(shù)積之和：將變量乘積項(xiàng)（與）以或的形式組合起來和之積：將變量求和項(xiàng)以與的形式組合起來要利用真值表生成積之和的表達(dá)式，就是要找到真值表中輸出值為1的對應(yīng)行，將該行的輸入變量寫成積的形式。在生成的每個乘積項(xiàng)中，必須將輸入為0的變量取反。要利用真值表生成和之積的表達(dá)式，就是要找到真值表中輸出值為0的對應(yīng)行，將該行的輸入變量寫成和的形式。在生成的每個求和項(xiàng)中，必須將輸入為0的變量取反。3.3邏輯門數(shù)字電路是由一定數(shù)目的門電路作為最原始的基本單元構(gòu)成的，這些門電路是數(shù)字設(shè)計的基本構(gòu)件，可以執(zhí)行布爾代數(shù)中的邏輯操作。歸納起來，計算機(jī)的基本物理部件是晶體管，而基本的邏輯單元是門電路。3.3.1邏輯門的表示符號與門（and）或門（or）非門（not）3.3.1邏輯門的表示符號異或門（xor，）3.3.2通用門電路與非門（NAND）或非門3.3.2通用門電路與非門通常也稱為萬能門，因?yàn)橹灰褂门c非門就可以構(gòu)建所有的數(shù)字電路。使用單一與非門構(gòu)造數(shù)字電路的原因使用與非門的電路成本低使用相同模塊比使用不同模塊要容易積之和形式的布爾表達(dá)式適合用與非門實(shí)現(xiàn)，和之積形式的布爾表達(dá)式適合用或非門實(shí)現(xiàn)3.3.3多輸入的門電路門電路可以有不同數(shù)目的輸入和輸出方式3.4數(shù)字電路元件計算機(jī)由大量通過導(dǎo)線連接的門電路組成。門電路的組合通常是一些標(biāo)準(zhǔn)電路，這些標(biāo)準(zhǔn)電路組成一系列基本結(jié)構(gòu)模塊，可以構(gòu)造整個計算機(jī)系統(tǒng)，這些結(jié)構(gòu)模塊全部采用基本的“與或非”來構(gòu)建。3.4.1數(shù)字電路及其與布爾代數(shù)的相互關(guān)系簡單布爾操作對應(yīng)簡單邏輯門，復(fù)雜布爾表達(dá)式對應(yīng)于與或非操作的組合，即對應(yīng)于邏輯門的組合，即描述整個布爾表達(dá)式的邏輯圖。利用布爾代數(shù)可以分析和設(shè)計各種數(shù)字電路3.4.2集成電路門電路組成電路模塊，電路模塊組成計算機(jī)系統(tǒng)硬件體積更小能耗更低將門電路封裝在集成電路中以實(shí)現(xiàn)電路功能集成電路規(guī)模SSIMSILSIVLSIULSI3.5組合邏輯電路數(shù)字邏輯電路可分為組合邏輯電路和時序邏輯電路3.5.1基本概念輸出完全取決于任意時刻的給定輸入值。多輸出的組合邏輯電路中每個輸出對應(yīng)一個不同布爾函數(shù)3.5.2典型組合邏輯電路半加器輸入輸出xy和進(jìn)位00000110101011013.5.2典型組合邏輯電路全加器3.5.2典型組合邏輯電路多位數(shù)字相加逐級進(jìn)位加法器先行進(jìn)位加法器選擇進(jìn)位加法器存儲進(jìn)位加法器加法器中的主要延遲來自進(jìn)位，因此如何縮短進(jìn)位的產(chǎn)生過程所造成的延遲時間是關(guān)鍵加法器是計算機(jī)一個非常重要的電路3.5.2典型組合邏輯電路譯碼器從一個對應(yīng)的數(shù)值選擇某根特定的輸出線。譯碼器通常采用輸入和輸出的數(shù)目來定義。3.5.2典型組合邏輯電路多路復(fù)用器從眾多的輸入線中選擇需要的輸入線通過一組選擇信號來控制選定某個特定的輸入線3.5.2典型組合邏輯電路奇偶發(fā)生器和奇偶校驗(yàn)器3.5.2典型組合邏輯電路算術(shù)邏輯單元（ALU）3.6時序邏輯電路時序電路的輸出是當(dāng)前輸入和歷史輸入的函數(shù)時序電路的輸出與歷史輸入有關(guān)為了記憶以前的輸入，時序電路需要觸發(fā)器用于存儲。組合邏輯電路是各種門電路的綜合；時序邏輯電路是各種觸發(fā)器的綜合3.6.1時鐘信號時序電路需要對發(fā)生的事件進(jìn)行排序同步：利用時鐘對事件進(jìn)行排序異步：任意輸入的改變，均可引起電路重新計算時鐘是一種電信號，由一系列具有精確寬度和間隔的連續(xù)脈沖組成，脈沖間隔稱為時鐘周期。時序電路使用時鐘確定電路刷新的時刻3.6.3觸發(fā)器鎖存器和觸發(fā)器時序電路使用反饋實(shí)現(xiàn)對過去狀態(tài)的記憶使用特征表來描述觸發(fā)器，特征表基于電路的輸入和當(dāng)前狀態(tài)指出電路的下一狀態(tài)。Q(t)表示電路的當(dāng)前狀態(tài)，Q(t+1)表示電路的下一個狀態(tài)，或者說時鐘脈沖到來時，觸發(fā)器應(yīng)該進(jìn)入的狀態(tài)。3.6.3觸發(fā)器SR觸發(fā)器3.6.3觸發(fā)器JK觸發(fā)器3.6.3觸發(fā)器D觸發(fā)器3.6.4典型的時序邏輯電路4位寄存器3.6.4典型的時序邏輯電路二進(jìn)制計數(shù)