全套電子課件：數(shù)字邏輯

1、歡迎使用數(shù)字邏輯與數(shù)字系統(tǒng)設(shè)計1目錄第一章 數(shù)制與編碼1前言第一節(jié) 進位計數(shù)制1第二節(jié) 數(shù)制轉(zhuǎn)換2第三節(jié) 帶符號二進制數(shù)的表示方法4第四節(jié) 數(shù)的定點與浮點表示法7第五節(jié) 字符編碼8第六節(jié) 可靠行編碼 10習(xí)題 16 第二章 布爾代數(shù)及其邏輯實現(xiàn) 第一節(jié) 布爾代數(shù)的基本概念19 第二節(jié) 布爾代數(shù)的公式、定理和 規(guī)則22 第三節(jié) 布爾函數(shù)的基本形式25 第四節(jié) 布爾函數(shù)的代數(shù)化簡法28 第五節(jié) 布爾函數(shù)的卡諾圖化簡法30 第六節(jié) 布爾函數(shù)的實現(xiàn)37 第七節(jié) 多輸出布爾函數(shù)的化簡 與實現(xiàn)44 習(xí)題47第四章 組合邏輯電路102第一節(jié) 組合邏輯電路的分析102第二節(jié) 組合邏輯電路設(shè)計105第三節(jié) 常用

2、組合邏輯電路分析 與應(yīng)用120習(xí)題154第三章 集成邏輯門電路51 第一節(jié) 晶體管開關(guān)的特性51 第二節(jié) 基本邏輯門電路54第三節(jié) TTL集成電路 58*第四節(jié) 集成MOS門電路 80習(xí)題96 第五章 觸發(fā)器159第一節(jié) 基本觸發(fā)器159 第二節(jié) 其它觸發(fā)器162第三節(jié) 空翻現(xiàn)象及其解決方法167第四節(jié) 不同類型觸發(fā)器邏輯 功能的轉(zhuǎn)換.171第五節(jié) 觸發(fā)器的主要參數(shù)和 脈沖工作特性172習(xí)題174 目錄第七章 異步時序邏輯電路227第一節(jié) 脈沖異步時序邏輯電路227第二節(jié) 電平異步時序邏輯電路236*第三節(jié) 電平異步時序邏輯電路 的設(shè)計241第四節(jié) 邏輯電路的險象250*第五節(jié) 電平異步時序邏

3、輯電路 設(shè)計舉例257習(xí)題260第六章 同步時序邏輯電路177第一節(jié) 時序邏輯電路的基本概念177第二節(jié) 同步時序邏輯電路的分析183第三節(jié) 同步時序邏輯電路的設(shè)計187第四節(jié) 同步時序邏輯電路設(shè)計 舉例205第五節(jié) 常用同步時序邏輯電路212習(xí)題223第八章 脈沖產(chǎn)生與整形電路第一節(jié) 555時基電路 264第二節(jié) 施密特觸發(fā)器266第三節(jié) 單穩(wěn)態(tài)觸發(fā)器271第四節(jié) 多諧振蕩器278習(xí)題.280第九章 可編程邏輯器件285 第一節(jié) 只讀存儲器(ROM)286第二節(jié) 可編程邏輯陣列(PLA)294第三節(jié) 可編程陣列邏輯(PAL)301*第四節(jié) 通用陣列邏輯(GAL)308習(xí)題.337第十章 在系

4、統(tǒng)編程技術(shù)340第一節(jié) ISP技術(shù)的特點 340第二節(jié) ISP邏輯器件 344第三節(jié) ispLSI器件的結(jié)構(gòu)347*第四節(jié) 在系統(tǒng)編程和方法356*第五節(jié) ISP技術(shù)的實現(xiàn) EDA技術(shù)365*第六節(jié) EDA系統(tǒng)中的可編程集成 電路（ASIC）設(shè)計379習(xí)題381參考文獻382說明：加“*”的章節(jié)，可根據(jù)學(xué)時的安排，作為選學(xué)內(nèi)容第一章 數(shù)制與編碼本章內(nèi)容提要第一節(jié) 進位計數(shù)制第二節(jié) 數(shù)制轉(zhuǎn)換第三節(jié) 帶符號二進制數(shù)的表示方法第四節(jié) 數(shù)的定點與浮點表示法第五節(jié) 字符編碼第六節(jié) 字符編碼概述 數(shù)字計算機現(xiàn)已廣泛地應(yīng)用于科學(xué)計算、數(shù)據(jù)處理和過程控制等領(lǐng)域。數(shù)字計算機是數(shù)字系統(tǒng)中最常見、最有代表性的一種設(shè)

5、備。數(shù)字系統(tǒng)的特點是它所處理的 信息都是離散元素。 這些離散元素可以是十進制數(shù)字、某種字母、各種算符及標點符號等。離散元素通常是以二進制的形式出現(xiàn)的。為此,必須討論數(shù)的代碼特征及運算。 本章討論數(shù)制和編碼的概念。通過本章學(xué)習(xí),讀者將熟悉數(shù)字系統(tǒng)數(shù)制和編碼的表示方法、性質(zhì)及相互間的轉(zhuǎn)換,帶符號數(shù)和帶小數(shù)點數(shù)的表示方法及字符編碼,為離散元素的處理打下基礎(chǔ)。第一節(jié) 進位計數(shù)制 十進制計數(shù)制早已為人們所熟悉。在十進制計數(shù)制中,采用了10 個有序數(shù)字符號0、1、2、3、4、5、6、7、8、9 和一個小數(shù)點符號“. ”,并且是“逢十進一”。任何一個十進制數(shù), (S)10可以表示為(S)10 = kn-1

6、10n-1 + kn-2 10n-2 + + k0 100 + k-1 10-1 + + k-m 10-m 其中,ki可以是09這10個數(shù)碼中的任一個,m 和n是正整數(shù),ki、m 、n 均由(S)10決定,(S)的下標與式中的10是十進制的基數(shù)。一、十進制計數(shù)制 由于基數(shù)為10，每個數(shù)位計滿10就向高位進位,即逢十進一,所以稱它為十進制計數(shù)制。 例如,一個十進制數(shù)2003.3，可以表示為:(2003.3)10 = 2103 + 0102 + 0101 +3100 +310-1 在數(shù)字系統(tǒng)中,為了便于工程實現(xiàn),廣泛采用二進制計數(shù)制。這是因為,二進制的每一位只用兩個數(shù)碼0和1,因而可以用具有兩個不

7、同穩(wěn)定狀態(tài)的電子元件來表示,并且二進制數(shù)運算簡單,數(shù)的存儲和傳送也可用簡單而可靠的方式進行。二進制基數(shù)是2,其計數(shù)規(guī)律是逢二進一。二、二進制計數(shù)制 任意一個二進制數(shù)可以表示為:(S)2 = kn- 12n- 1 + kn -22n -2 + + k020 + k-12- 1 + + k- m2- m = 其中, ki 只能取0或1,m、n 為正整數(shù),由(S)2決定。例如,一個二進制數(shù)1011.101可以表示為: (1011.101)2 = 123 + 022 + 121 + 120 + 12- 1 + 02- 2 + 12-3 采用二進制計數(shù)制,對計算機等數(shù)字系統(tǒng)來說,數(shù)據(jù)的運算、存儲和傳送都

8、極為方便,但二進制書寫很不方便,且記憶困難,為此人們經(jīng)常采用八進制計數(shù)制和十六進制計數(shù)制來進行書寫或打印。 任意一個八進制數(shù)可以表示為 (S)8 其中, ki可取0、1、2、7 這8 個數(shù)碼之一,m和n為正整數(shù),由(S)8決定。八進制的基數(shù)是8,其計數(shù)規(guī)律是逢八進一。三、八進制計數(shù)制和十六進制計數(shù)制 例如,八進制數(shù)(537. 25)8 可以表示為(537.25)8 = 582 + 381 + 780 + 28- 1 + 58-2 任意一個十六進制數(shù)可以表示為 (S)16 其中, ki 可取0、1、2、8、9、A、B、C、D、E、F 等10 個數(shù)碼及6 個字母之一,m 和n 為正整數(shù),由(S)1

9、6決定,十六進制數(shù)的基數(shù)是16,其計數(shù)規(guī)律是逢十六進一。 例如,一個十六進制數(shù)(7FAE3. 8C)16 可以表示為(7FAE3.8C)16 = 7164 + F163 + A162 + E161 + 3160 + 816-1 + C16-2 人們習(xí)慣的是十進制數(shù),計算機及數(shù)字系統(tǒng)采用的是二進制數(shù),人們書寫時又多采用八進制數(shù)或十六進制數(shù),因此,必然產(chǎn)生各種進位計數(shù)制間的相互轉(zhuǎn)換問題,以便計算機和人之間相互理解。 對于基值大的整數(shù)轉(zhuǎn)換成基值小的整數(shù)時,一般采用除基取余法進行,例如(935)10 = (?)2 可以用如下方法: 第二節(jié) 數(shù)制轉(zhuǎn)換一、整數(shù)轉(zhuǎn)換方法 1 3 7 14 29 58 116

10、 233 467 935 2 1 1 1 0 1 0 0 1 1 1 余數(shù) 轉(zhuǎn)換結(jié)果為(935)10 = (1110100111)2 對于基值小的整數(shù)轉(zhuǎn)換成基值大的整數(shù)時,一般采用按冪展開法進行,例如:(1101001)2 =126 +125 +024 +123 +022 + 021+120 = (105)10二、小數(shù)轉(zhuǎn)換方法 0.875 0.75 0.5 0.0 2 1 1 1 0 整數(shù) 對于基值大的小數(shù)轉(zhuǎn)換成基值小的小數(shù)時,一般采用乘基取整法進行,例如(0.875)10 =(?)2 可以用如下方法:轉(zhuǎn)換結(jié)果為(0. 875)10 = (0. 1110)2 同樣對于基值小的小數(shù)轉(zhuǎn)換成基值大的

11、小數(shù)時,一般采用按冪展開法進行,例如:(0.1101)2=12-1 + 12-2 + 02 -3 + 12-4 =(0.8125)10三、二進制數(shù)與八進制數(shù)和十六進制數(shù)之間的轉(zhuǎn)換 二進制數(shù)與八進制數(shù)和十六進制數(shù)之間有著確定的對應(yīng)關(guān)系,對于二進制數(shù)與八進制數(shù)之間為每3 位二進制數(shù)對應(yīng)1 位八進制數(shù),當二進制數(shù)轉(zhuǎn)換為八進制數(shù)時,從小數(shù)點開始分別向左或向右每3 位一組劃分,不足3 位時用0填補,即可得到等值的八進制數(shù),例如: (1101011.1001)2 = (153.44)8 而八進制數(shù)轉(zhuǎn)換為二進制數(shù)時,則直接展開成3 位一組二進制數(shù)即可,然后去掉整數(shù)最高位的0和小數(shù)最低位的0,例如:(1635

12、.724)8 =(001110011101.111010100)2 = (1110011101.1110101)2 對于二進制數(shù)與十六進制數(shù)之間為每4位二進制數(shù)對應(yīng)1位十六進制數(shù),當二進制數(shù)轉(zhuǎn)換為十六進制數(shù)時,從小數(shù)點開始分別向左或向右按每4位一組劃分,不足4位時用0填補,即可得到等值的十六進制數(shù),例如:(110100111.101101)2 = (1A7.B4)16 而十六進制數(shù)轉(zhuǎn)換為二進制數(shù)時,則直接展開成4位一組二進制數(shù)即可,然后去掉整數(shù)最高位的0和小數(shù)最低位的0,例如:(3FC7.A4)16=(0011111111000111.10100100)2 = (11111111000111.

13、101001)2四、數(shù)制轉(zhuǎn)換中應(yīng)注意的問題 (1)實數(shù)轉(zhuǎn)換時應(yīng)將整數(shù)和小數(shù)分別轉(zhuǎn)換,然后再拼接起來。 (2)基值大的小數(shù)不一定有確定對應(yīng)的基值小的小數(shù),可能出現(xiàn)無限循環(huán)或無限不循環(huán)的小數(shù),例如十進制小數(shù)0.6,其等效的二進制小數(shù)0.100110011001,為一無限循環(huán)小數(shù),應(yīng)按精度要求取相應(yīng)位數(shù)。 (3)不同進位計數(shù)制可分別用后綴來標注,B表示二進制數(shù),Q表示八進制數(shù),H表示十六進制數(shù),D或缺省則表示十進制數(shù)。 例如: 139D = 10001011B= 213Q = 8BH第三節(jié) 帶符號二進制數(shù)的表示方法一、機器數(shù)與真值 帶符號二進制數(shù)在計算機內(nèi)部如何表示呢,通常將數(shù)的符號數(shù)碼化,即用0表

14、示“+ ”,用1表示“- ”, 例如: 數(shù)(-1101)2 是機器數(shù)(11101)2 的真值; 而數(shù)(+1011)2 則是(01011)2 的真值。二、原碼表示法 X 1 X0 原碼定義 X原= 1 X - 1 X0 由原碼定義可以看出,任何大于0 的數(shù)的原碼就是符號位為0,尾數(shù)為真值本身;小于0 的數(shù)的原碼符號位為1,尾數(shù)仍為真值本身,從真值求原碼就是正數(shù)前加符號0,負數(shù)前加符號1即可。例如: X = + 0. 1011, X原= 0. 1011 X = - 0. 1011, X原= 1. 1011 三、補碼表示法 原碼表示通俗易懂,而且與真值間轉(zhuǎn)換很簡單。但是用原碼表示時加/減運算很不方便

15、。例如,當A 、B 兩數(shù)相加時,還要視其同號,還是異號。若同號,則數(shù)值相加,結(jié)果符號不變;如果兩數(shù)異號,則實際做減法,并判斷兩數(shù)的絕對值,讓絕對值大的數(shù)減去絕對值小的數(shù),其結(jié)果符號與絕對值大的數(shù)相同。在整個操作中費時、費設(shè)備。為了解決這些矛盾,人們尋求一種補碼表示法。 1.補碼的概念和定義 補碼是根據(jù)同余的概念提出來的，例如： 8 4 = 8 6 (mod 10) 11 2 = 11 10 (mod 12) 其中10和12稱為模數(shù),在相應(yīng)模數(shù)下等號兩邊余數(shù)是相同的,當以10為模時84可以用86來計算,6就是以10為模4的補碼。同樣10就是以12為模2的補碼。 對于小于1 的二進制數(shù)的補碼定義如

16、下: X 0 X 1 原碼定義 X補= (mod 2) 2 X - 1 X 0或?qū)懗赏嗍? X補= X(mod 2) 2. 補碼的轉(zhuǎn)換 (1)由真值求補碼。根據(jù)補碼的定義,任何正數(shù)的補碼就是真值本身;負數(shù)的補碼按其定義為： X補 = 2 + X X = - 0. X1 X2 Xn X補 = 10.00000 + (- 0. X1 X2 Xn) = 1.11111 + 0.00001 0.X1 X2 Xn = 1. X1 X2 Xn + 0.00001 其中 1 = +2-n 從而得到由負數(shù)值求補碼的方法:符號位為1,尾數(shù)各位取反(0變1,1變0), 在末位加1(簡稱除符號位外求反加1)就是X

17、補。 (2)由原碼求補碼。由原碼和補碼的定義可知,正數(shù)的原碼和補碼相同,就是真值的表示。 對于負數(shù)X,當X = - 0. X1 X2 Xn X原= 1. X1 X2 Xn X補= 2 + X = 2 - 0. X1 X2 Xn = 1 + (1 - 0. X1 X2 Xn) = 1 + (0. X1 X2 Xn + 0.00001) 這個結(jié)果表明任何負數(shù)的補碼X補等于它的原碼除符號位以外各位“求反加1” (3)由一個數(shù)的補碼表示求其負數(shù)的表示 這是實現(xiàn)補碼減法運算的基礎(chǔ)。若X補= 0. X1 X2 Xn 則X原= 0. X1 X2 Xn -X= - 0. X1 X2 Xn -X補= 1. X1

18、 X2 Xn + 2-n若X補= 1. X1 X2 Xn 則X原= 1. X1 X2 Xn + 2-n -X = -(0. X1 X2 Xn + 2-n) -X補= 0. X1 X2 Xn + 2-n 結(jié)論:對絕對值小于1 的任何正、負數(shù)X,通過對X補連同符號位一起“求反加1”便可得到-X補,稱-X補為X補的機器負數(shù),由X補求-X補的過程稱為對X補求-X的補碼。 3.補碼的性質(zhì) (1)若用X0 表示符號位,則有 1 X 0 (2)真值0在補碼表示中是唯一的。 +0補 = 0.0000 -0補 = 10.0000 - 0.0000 = 10.0000 = 0.0000(mod2) 即+0補= -

19、0補= 0.0000 4. 補碼的運算規(guī)則 X補Y補= XY補 即補碼運算結(jié)果仍然是補碼,當結(jié)果的最高位有向上進位時,丟掉不要,即為正確結(jié)果。 5. 補碼的溢出判斷與變形補碼 當兩正數(shù)相加結(jié)果超過1 或兩負數(shù)相加結(jié)果超過-1時,其結(jié)果超出了機器所能表示數(shù)的范圍,則產(chǎn)生溢出錯誤,為能正確判斷其溢出錯誤常采用變形補碼,即采用兩位符號位。 X 1 X0 X補 = (mod4) 4 + X 0 X-1 例如: X = 0.101101 X補= 00. 101101 X = - 0.101101 X補= 11. 010011 當兩數(shù)運算結(jié)果符號位相異時,則產(chǎn)生溢出,結(jié)果符號= 01為正溢出,結(jié)果符號=

20、10為負溢出。 例如: X = 0.1101，Y = 0.1010,求X + Y補。 X補= 00.1101, Y補= 00.1010 X補Y補= 01.0111, 產(chǎn)生正溢出。四、反碼表示法 在補碼表示中,如果只求反末位不加1,就得到了另一種機器數(shù)表示法反碼表示法。可從補碼的定義推出反碼的定義為： X 1 X0 X反= (mod2 - 2-n) (22-n)X 0 X -1 其中,n為尾數(shù)的位數(shù)。 在反碼表示中0的表示不是唯一的,+0反= 0.0000,而-0反= 1.1111。 反碼的運算規(guī)則為： X反 Y反= XY 結(jié)果為反碼,如果結(jié)果的最高位有向上的進位,則應(yīng)加到結(jié)果的末位,即循環(huán)進位

21、,才能得到正確結(jié)果。第四節(jié) 數(shù)的定點與浮點表示法一、數(shù)的定點表示法 定點數(shù)是各種數(shù)據(jù)表示中最簡單,最基本的一種數(shù)據(jù)表示形式,它用于表示二進制形式具有固定比例換算的量。在定點表示中約定機器中所有數(shù)據(jù)的小數(shù)點位置是固定不變的,因而小數(shù)點就不必要再使用記號表示。 1. 定點小數(shù)格式 小數(shù)點位置固定在最高有效數(shù)位的左邊。任一定點小數(shù)表示為： N = Ns. N -1 N -2 N -3 N -m (m 為數(shù)據(jù)位數(shù))在計算機中的表示形式為： Ns . N-1 N-2 N-3 N-m 符號位 小數(shù)點 數(shù)值部分（尾數(shù)） 2. 定點整數(shù)格式 小數(shù)點固定在最低數(shù)據(jù)位的右邊,任一定點整數(shù)表示為：N = Ns Nm

22、-1 Nm-2 Nm-3 N2 N1 N0 (其中m 為數(shù)據(jù)位數(shù))在計算機中整數(shù)表示形式為： . 符號位 數(shù)值部分（尾數(shù)） 小數(shù)點 定點數(shù)可以表示為帶符號數(shù)或不帶符號數(shù)。表示算術(shù)操作數(shù)時,應(yīng)用帶符號的數(shù),一般以左邊最高位表示符號位。不帶符號的數(shù)一般表示邏輯量或某些特征值。N0N1N2Nm-2Nm-1Ns二、浮點表示法 一個數(shù)N 的浮點形式可表示為： N = MREm 其中,M(Mantissa)表示尾數(shù),E(Exponent)表示階碼,Rm (Radix)表示基數(shù)。Rm 一般為2、8、16等,由于Rm 是常數(shù),不需在數(shù)碼中表示出來,故浮點數(shù)只需用一對定點數(shù)表示。 一個尾數(shù)是M,在浮點表示中尾數(shù)

23、通常為規(guī)格化的純小數(shù),即： | M | 1/Rm 另一個是階碼,通常是整數(shù)。 浮點數(shù)在計算機中的表示形式為： 階符 階碼 數(shù)符 小數(shù)點 尾數(shù) . 小數(shù)點EnE2E1EsN-mN-2N-1.Ns尾數(shù)階碼數(shù)符第五節(jié) 字符編碼 1. ASCII碼 ASCII碼是美國信息交換標準代碼。 ASCII碼是用7位二進制碼編碼的,故可表示字符 27 = 128 其中包括:10 個十進制數(shù)(09), 52個大、小寫英文字母(AZ，az), 32個通用控制字符,34個專用字符。 我國標準“信息交換用的七位編碼字符集80GB1988”規(guī)定了信息處理交換用的圖形字符和控制字符共128個,每個字符用7位二進制數(shù)碼進行編

24、碼,與ASCII 碼兼容。 2. 十進制數(shù)編碼 在數(shù)字系統(tǒng)中十進制數(shù)也是應(yīng)用二進制數(shù)編碼的，即二進制編碼的十進制數(shù)，其中應(yīng)用最廣泛的是ASCII碼和BCD碼，ASCII碼的十進制數(shù)主要用于非數(shù)值計算，它們所表示的數(shù)串可以作為字符串來運算或操作。作為十進制數(shù)進行算術(shù)運算則采用BCD碼。 ASCII碼十進制數(shù)是用一個字節(jié)來表示的，09等10個數(shù)字用ASCII碼字符集中3039(十六進制數(shù))10個編碼表示。BCD 碼是用二進制編碼的十進制數(shù)碼(通常用8421 有權(quán)碼),每兩個十進制數(shù)占一個字節(jié)，稱為壓縮十進制數(shù)串，其符號則用BCD碼中的冗余碼來表示，如用10、12、14 或15表示“”；用11或13

25、表示“”。 對于BCD 碼表示的十進制數(shù)在進行加/ 減運算時要考慮修正問題,對8421 編碼的十進制數(shù),其修正方法是:當兩十進制數(shù)相加結(jié)果小于等于9 時,不修正;當結(jié)果大于9 或產(chǎn)生向高位進位時,均加6 修正,以得到正確結(jié)果。例如: X = 358 Y = 9298421 碼表示為： X = 0011 0101 1000 Y = 1001 0010 1001先按二進制數(shù)運算規(guī)則計算: 0011 0101 1000 ）1001 0010 1001 1100 1000 1 0001修正結(jié)果 ）0110 0000 0110 1 0010 1000 0111 其中個位和有向十位進位，個位和需修正，百位

26、和大于9，亦需進行修正得到正確結(jié)果。 X + Y = 1287 3. 漢字編碼 為了能在各個處理環(huán)節(jié)中方便和確切地表示漢字,在漢字系統(tǒng)中要涉及到各種漢字代碼，包括：漢字輸入碼、漢字交換碼、漢字機內(nèi)碼以及漢字輸出碼等。 (1)漢字輸入碼：漢字輸入碼是將漢字的不同編碼規(guī)則通過鍵盤或其他設(shè)備，以編碼形式輸入計算機。漢字輸入計算機可以通過圖像識別、漢字語音識別、漢字編碼輸入和非編碼輸入等方法。如電報明碼、國標區(qū)位碼、整字輸入、字元編碼、筆形編碼、拼音編碼等，可通過標準鍵盤擊鍵輸入。 (2)漢字機內(nèi)碼：漢字編碼輸入到計算機系統(tǒng)后，要將其轉(zhuǎn)換成計算機內(nèi)部表示漢字的機內(nèi)碼，按照程序的要求，控制計算機對機內(nèi)碼

27、進行加工處理。 (3)漢字交換碼：漢字交換碼是用于不同的漢字系統(tǒng)之間交換漢字信息的。中華人民共和國國家標準信息交換用漢字字符集GB 2312-80，共收錄一級漢字3755個，二級漢字3008個，各種圖形符號682個，共計7445個。GB 2312-80規(guī)定每個漢字、圖形符號都用兩個字節(jié)表示，每個字節(jié)7位二進制代碼，與94個可打印字符(除空格外)的ASCII字符取值范圍相同，GB 13000大字符集則收錄了10902 個漢字與字符，符合國際肆八位編碼字符集。 漢字交換碼還用區(qū)位碼。區(qū)位碼由4位數(shù)字組成，前兩位是區(qū)號0194，后兩位是位號0194。區(qū)位碼是把圖形符號分為94個區(qū)(行)，每個區(qū)又分為

28、94 位(列)，并分別標出區(qū)號、位號來表示漢字的編碼。當一個漢字在表中的位置確定之后，就能從縱、橫坐標上找到它的相應(yīng)區(qū)號與位號，區(qū)號、位號連接起來就構(gòu)成區(qū)位碼。 (4)漢字輸出碼：漢字信息加工處理后的結(jié)果如以漢字形式輸出，則又應(yīng)將漢字機內(nèi)碼再轉(zhuǎn)換成漢字交換碼或直接變換成漢字地址碼，按這些地址從漢字庫中取出漢字字形存儲碼，根據(jù)輸出設(shè)備的要求再轉(zhuǎn)換成字形輸出碼，供顯示或打印。漢字字形存儲碼是每一個漢字信息的字形點陣碼。如用1616點陣，則每一個漢字字形碼為32B;如用2424點陣，則每一個漢字字形碼為72B。第六節(jié) 可靠性編碼 為了減少代碼在形成或傳輸過程中可能產(chǎn)生的錯誤,人們常采用一些可靠的編碼

29、方法,它使代碼本身具有一種特征或能力,使代碼在形成過程中不易出錯,即使出錯也容易發(fā)現(xiàn),或能確定出錯的位置并予以糾正。 目前,常用的可靠性編碼有格雷(Gray)碼、奇偶校驗碼、漢明校驗碼和循環(huán)冗余校驗碼等。一、格雷(Gray)碼 Gray碼有多種形式,但它們都有一個共同特點,即從一個代碼變換為相鄰的另一代碼時,只有一位發(fā)生變化。表1-1 給出了一種典型的Gray碼。表1-1 典型Gray碼 從表可以看出,任何相鄰的十進制數(shù),它們的Gray碼都僅有1 位不同。 例如,7到8,二進制碼是0111到1000，4位均發(fā)生變化,而Gray碼是0100到1100,只有1位發(fā)生變化。 如在二進制碼做加1計數(shù)時

30、,從7到8，4位都要發(fā)生變化,當4 位變化不是同時發(fā)生時,在計數(shù)過程中就可能出現(xiàn)計數(shù)錯誤,Gray 碼是從編碼的形式上杜絕了出現(xiàn)這種錯誤的可能。 Gray碼與二進制碼之間有簡單的轉(zhuǎn)換關(guān)系,設(shè)二進制碼為: B = Bn Bn-1 B1 B0其對應(yīng)的Gray 碼為 G = Gn Gn-1 G1 G0則有 Gn = Bn Gi = Bi+1 Bi (i n)式中i = 0,1,2,n-1;“ ”符號表示異或運算或模2加運算。 反過來,如果已知Gray 碼,也可以用類似的方法求出對應(yīng)的二進制碼,其方法如下: Bn = Gn Bi = Bi+1Gi (i n) 例如,把二進制碼0111和1100轉(zhuǎn)換成G

31、ray碼;把Gray碼0100和1010轉(zhuǎn)換成二進制碼：二、奇偶校驗碼 二進制代碼在傳輸、存儲過程中,可能會發(fā)生錯誤,即有的1錯成了0或有的0錯成了1,奇偶校驗碼具有發(fā)現(xiàn)這種錯誤的能力。 奇偶校驗碼由兩部分組成,即由信息位和校驗位組成。信息位就是要傳輸?shù)男畔⒈旧?可以是位數(shù)不限的二進制代碼,例如并行傳輸?shù)?421BCD 碼,信息位就是4 位,校驗位是附加的冗余位,奇偶位僅1 位。 1.奇偶校驗碼的編碼方法 在信息的發(fā)送端根據(jù)信息位1的個數(shù)配成奇數(shù)個1,構(gòu)成奇校驗;若信息位1的個數(shù)配成偶數(shù)個1,則構(gòu)成偶校驗。 一般來說,對于任何n位二進制信息碼,只要增加1位校驗位,便可構(gòu)成(n+1)位的奇或偶校

32、驗碼。設(shè)奇偶校驗碼為 C1 C2 C3 Cn P則校驗位P可以表示為 P = C1 C2 C3 Cn (對偶校驗碼) 或 P = C1 C2C3Cn1 (對奇校驗碼) 2.奇偶校驗碼的校驗方法 在發(fā)送端對信息碼進行編碼后,將信息位和校驗位構(gòu)成的奇(或偶)校驗碼一起發(fā)送出去,在接收端對接收到的編碼按發(fā)送端對信息碼的編碼方法進行校驗碼生成,得到新的校驗碼P,與接收到的P相比較,相同為傳送正確,相異則說明傳送有錯。則校驗位P可以表示為： P= C1 C2 C3 Cn (對偶校驗碼)或 P= C1 C2 C3 Cn1 (對奇校驗碼)校正子 S = P + P 當 S = 0時,說明傳送正確; 當 S

33、= 1時,說明傳送錯誤。 奇偶校驗碼能發(fā)現(xiàn)代碼1位(或奇1個數(shù)位)出錯,但它不能發(fā)現(xiàn)2位(或偶數(shù)個數(shù)位)出錯。由于2位出錯的概率遠低于1位出錯的概率,所以奇偶校驗碼用來檢測代碼在傳送過程中的錯誤是很有效的。 實現(xiàn)奇偶校驗只需要在發(fā)送端增加一個奇偶形成電路和在接收端增加一個奇偶校驗電路就可以了。其原理框圖如圖1 - 1 所示。圖1-1 BCD碼奇偶校驗原理框圖 三、漢明校驗碼 奇偶校驗碼只能發(fā)現(xiàn)代碼1位(或奇數(shù)個數(shù)位)出錯,但不能定位出錯位置,因而就不能糾正錯誤,漢明校驗碼是由Richard Hamming 提出的,它實際上是一種多重奇偶校驗,即將代碼按照一定規(guī)則組織為若干小組,分組進行奇偶校驗

34、,各組的校驗信息組成一個指誤字,通過指誤字不僅可以檢測是否出錯,而且在1 位出錯的情況下能進行錯誤定位并能糾正錯誤。 1. 漢明碼的編碼方法 漢明碼也是由信息位和校驗位構(gòu)成的,但校驗位有多位。且要滿足如下漢明不等式: 2r k + r + 1 其中,k是信息位數(shù),r是校驗位數(shù)。漢明校驗是奇偶校驗的擴充,各校驗位都是由奇偶校驗方程產(chǎn)生的,可以由奇校驗方程產(chǎn)生,也可以由偶校驗方程產(chǎn)生。 設(shè)需傳送的信息碼為4位二進制碼,即 M = a1 a2 a3 a4 為了實現(xiàn)漢明校驗,按漢明不等式則需要增加3位校驗位b1、b2、b3 ,稱它們?yōu)闈h明奇偶校驗位。分別設(shè)置在2i碼位上(i = 0,1,2),即b1置

35、于20 =1碼位上,b2置于21 =2碼位上,b3置于22 =4碼位上。校驗位的取值由下列表達式求得(對偶校驗)： b1 = a1 a2 a4 b2 = a1 a3 a4 b3 = a2 a3 a4 將校驗位b1、b2、b3 分別置于相應(yīng)碼位上,就完成了漢明碼的編碼,即： n = b1 b2 a1 b3 a2 a3 a4 生成校驗位的方程為r個,每一信息位至少參加到兩個校驗方程中,某一信息位出錯,則引起多位校驗位出錯,產(chǎn)生的指誤字就可以確定出錯位置。 例如: k = 1011 b1 = 1 0 1 = 0 b2 = 1 1 1 = 1 b3 = 0 1 1 = 0 n = 0110011 2.

36、漢明碼的校驗方法 在發(fā)送端將編碼好的漢明碼發(fā)送出去后,在接收端根據(jù)接收到的信息碼和校驗碼進行檢錯和糾錯。在接收端根據(jù)下列校驗方程生成指誤字或錯誤模式(對偶校驗)。 S1 = b1 a1 a2 a4 S2 = b2 a1 a3 a4 S3 = b3 a2 a3 a4 根據(jù)求得的S1 S2 S3 的值就能夠檢測錯誤和錯誤定位。 如果接收到的代碼是正確的,則 S3 S2 S1 = 000 如果接收到的代碼有錯誤(假設(shè)只有1位錯),則S3 S2 S1 的值就是出錯碼位,只要將該位取反即可。例如:發(fā)送的代碼為： n = 0110011但接收的代碼為： n = 0110010指誤字為： S3 S2 S1

37、= 111說明第7 位出錯,將其取反就得到正確代碼0110011。四、循環(huán)冗余校驗碼 循環(huán)冗余校驗(Cyclic Redundancy Check,CRC)是目前在磁表面存儲器中應(yīng)用最廣泛的一種校驗方法,也是網(wǎng)絡(luò)和多機通信中常用的校驗方法。它所約定的校驗規(guī)則是:讓校驗碼能為某一約定代碼除盡;如果除得盡,表明代碼正確,如果除不盡,余數(shù)將指明出錯位所在位置。 任意一串數(shù)碼,很可能除不盡,將產(chǎn)生一個余數(shù)。如果讓被除數(shù)減去余數(shù),勢必能為約定除數(shù)所除盡。但減法操作可能需要借位運算,難于用簡單的拼裝方法實現(xiàn)編碼。因此采用一種模2運算,即通過模2減實現(xiàn)模2除,以模2加將所得余數(shù)拼接在被除數(shù)后面,形成一個能除

38、盡的校驗碼。當然,對除數(shù)的選擇是有條件的。模2運算是一種以按位加/ 減為基礎(chǔ)的四則運算,不考慮進位和借位。它是一種按位加/ 減或異或運算,可用異或門實現(xiàn)。 待編碼的信息是一串代碼,可能是表示數(shù)值大小的數(shù)字,也可能是字符編碼,或其他性質(zhì)的代碼。在模2除中,暫將它視為數(shù)字,可用多項式來描述?，F(xiàn)定義待編信息(被除數(shù))為M(x);約定的除數(shù)為G(x),因為它是用來產(chǎn)生余數(shù)的,所以G(x)又稱為生成多項式;所以產(chǎn)生的余數(shù)R(x),它相當于所配的冗余校驗位。 M(x)= Q(x)G(x)+ R(x) M(x)- R(x)= Q(x)G(x) 顯然,將M(x)減去余數(shù)R(x),就必定能為G(x)所除盡。因而

39、可以設(shè)想讓M(x)- R(x)作為編好的校驗碼送往輔助存儲器。當從輔助存儲器取得校驗碼時,仍用約定的多項式G(x)去除,若余數(shù)為0,表明該校驗碼正確;若余數(shù)不為0,表明有錯。再進一步由余數(shù)確定是哪一位出錯,以便糾正。 1. 編碼方法 (1)將待編碼的k 位有效信息碼組表達為多項式M(x)。 M(x)= Ck-1xk-1 +Ck-2xk-2 + + Cixi + + C1x + C0 式中Ci = 0或1。 (2)將M (x)左移r 位,得M(x)xr。這樣做的目的是空出r 位,以便拼裝r 位余數(shù)(即校驗位)。 (3)用r +1 位的生成多項式G(x),對M(x)xr 做模2除。 要產(chǎn)生r 位余

40、數(shù),所以除數(shù)應(yīng)為r +1 位。 M(x)xr/G(x) = Q(x)+ R(x)/G(x) (模2 除) (4)將左移r 位的待編有效信息與余數(shù)R(x)做模2 加(減),即拼接為循環(huán)校驗碼。M(x)xr + R(x)= Q(x)G(x)+ R(x)+ R(x)= Q(x)G(x) (模2加) 兩個相同數(shù)的模2和為0,所以M(x)xr + R(x)是一個能被G(x)除盡的數(shù)碼,可作為循環(huán)校驗碼,共n = k + r 位。由于M(x)xr 已經(jīng)空出r 位,所以與R(x)的模2加可由簡單的拼接來實現(xiàn)。 在按位運算中,模2加與模2減的結(jié)果是一致的,所以 M(x)xr -R (x)= M(x)xr +R

41、(x) 在本節(jié)中,將M(x)+ R(x)稱為循環(huán)校驗碼。在許多應(yīng)用中,常只將R(x)部分稱為校驗碼,簡寫為CRC。 例如,將4 位有效信息1100編成循環(huán)校驗碼,選擇生成多項式1011。 M(x)= x3 + x2 , 即1100 (k = 4) M(x)xr = x6 + x5 ,即1100000 (左移r = 3 位) G(x)= x3 + x + 1, 即1011 (r + 1 = 4 位) M(x)x3/G(x) =1100000/1011 =1110 + 010/1011 (模2 除) M(x)x3 + R(x)= 1100000 + 010 = 1100010 (模2 加) 把編好

42、的循環(huán)校驗碼稱為(7,4)碼,即n = 7,k = 4,出錯位之間有著唯一的對應(yīng)關(guān)系。 2. 譯碼與糾錯 將接收到的循環(huán)校驗碼,用約定的生成多項式G (x)去除。如果接收代碼無誤,則余數(shù)R(x)= 0;如果接收代碼某1 位出錯,則余數(shù)R(x)不為0,不同位出錯則余數(shù)不同,余數(shù)代碼與出錯位之間有著唯一的對應(yīng)關(guān)系。 通過上例可求出其出錯模式如表1-2所示,即余數(shù)與出錯位序號之間的對應(yīng)模式。變更待測碼字不影響錯誤模式,出錯模式只與碼制和多項式有關(guān),與碼字代碼無關(guān)。對于(7,4)CRC碼,表1-2具有通用性,可作為(7,4)碼的判別依據(jù)。當然,對于其他碼制或選用其他生成多項式,出錯模式可能不同。表1-

43、2中列舉了八種情況。一種是正確碼字,除后余數(shù)為0。其余七種是依次有1位出錯,余數(shù)不為0,與出錯位序號有唯一的對應(yīng)模式。如果有1位碼字出錯,用G(x)除后得到一個不為0的余數(shù),如果對該余數(shù)補0后繼續(xù)除,各次余數(shù)將按表1-2順序循環(huán)。例如第7位A7出錯,余數(shù)為001,補0后繼續(xù)除,得余數(shù)010,以后將依次為100、011、110、111、101,然后是001,呈循環(huán)性,故又稱循環(huán)碼。表1-2 (7,4)循環(huán)碼的出錯模式生成多項式G(x)= 1011 循環(huán)碼可以采用硬件糾錯方法,只設(shè)置余數(shù)101的譯碼輸出,對應(yīng)于第1位出錯位置;如果校驗后發(fā)現(xiàn)余數(shù)不為0,一邊對余數(shù)補0繼續(xù)做模2除,同時將被檢測碼字循

44、環(huán)左移1位;當出現(xiàn)余數(shù)101時,出錯位也移至第1位位置,可用異或門將其變反糾正,或在由第1位移往第7位的途中予以糾正;繼續(xù)移滿一個循環(huán),即共移7次,將得到一個糾正后的正確碼字。 3. 生成多項式的選取 從檢錯與糾錯的要求出發(fā),生成多項式應(yīng)能滿足下列要求:任何一位發(fā)生錯誤都應(yīng)使余數(shù)不為0,不同位發(fā)生錯誤應(yīng)當使余數(shù)不同,應(yīng)滿足余數(shù)循環(huán)規(guī)律。在計算機與通信系統(tǒng)中廣泛使用的是下列兩種標準: CCITT(國際電報電話咨詢委員會)推薦: G(x)= x16 + x15 + x2 + 1 IEEE(美國電器和電子工程師協(xié)會)推薦: G(x)= x16 + x12 + x5 + 1第二章 布爾代數(shù)及其邏輯實現(xiàn)

45、本章內(nèi)容提要第一節(jié) 布爾代數(shù)及其邏輯實現(xiàn)第二節(jié) 布爾代數(shù)的公式、定理和規(guī)則第三節(jié) 布爾函數(shù)的基本形式第四節(jié) 布爾函數(shù)的代數(shù)化簡法第五節(jié) 布爾函數(shù)的卡諾圖化簡法第六節(jié) 布爾函數(shù)的實現(xiàn)第七節(jié) 多輸出布爾函數(shù)的化簡與實現(xiàn)概述 1847 年,英國數(shù)學(xué)家喬治布爾(George Boole)提出了一個系統(tǒng)的邏輯處理方法并由此而發(fā)展成一個代數(shù)體系布爾代數(shù)。布爾代數(shù)是研究開關(guān)理論和邏輯設(shè)計的數(shù)學(xué)基礎(chǔ),已被廣泛應(yīng)用于數(shù)字系統(tǒng)設(shè)計中。 數(shù)字計算機和其他數(shù)字系統(tǒng)大量使用各種各樣的數(shù)字邏輯電路。數(shù)字邏輯電路種類很多,為了弄清它們的原理和性能,必須掌握布爾代數(shù)這一數(shù)學(xué)工具。 本章主要介紹布爾代數(shù)的基本概念、基本定理、性

46、質(zhì)、布爾函數(shù)表達式及其邏輯實現(xiàn)。第一節(jié) 布爾代數(shù)的基本概念一、布爾變量及其基本運算 布爾代數(shù)和普通代數(shù)變量一樣,用字母表示變量,布爾代數(shù)的變量稱為布爾變量。由于目前使用的器件通常只有兩個穩(wěn)定狀態(tài),它的取值只有兩種可能,即取值1或0,故又稱二值代數(shù)。計算機或其他數(shù)字系統(tǒng)無論多么復(fù)雜,它們都是由若干種最簡單的、最基本的電路(如門電路、觸發(fā)器等)所組成。第一節(jié) 布爾代數(shù)的基本概念 這些電路的工作具有下列基本特點:從電路內(nèi)部看,或是開關(guān)器件的導(dǎo)通,或是開關(guān)器件的截止;從電路的輸入、輸出看,或是電平的高低,或是脈沖的有無。由于這些電路工作在開關(guān)狀態(tài),故稱開關(guān)電路。開關(guān)電路的工作狀態(tài)可以用二值布爾代數(shù)來描

47、述,且布爾代數(shù)是研究開關(guān)理論的,所以又稱開關(guān)代數(shù)。 研究數(shù)字邏輯電路時,關(guān)心的是電路所完成的邏輯功能,而不是電的或機械的性能,因此一般只考慮輸入變量和輸出變量之間的邏輯關(guān)系,并用代數(shù)的形式來描述。輸入信號A 和B 如果是布爾變量,則輸出信號便是布爾函數(shù),且可表示為 F = f (A,B) 這種代數(shù)表達式以理想的形式來表示實際的數(shù)字邏輯電路。反映了邏輯電路的特征和功能。因此,它使我們有可能將一個具體的數(shù)字邏輯電路轉(zhuǎn)換成抽象的代數(shù)表達式而加以分析研究。 實際的邏輯關(guān)系是千變?nèi)f化的,但它們都是由或、與、非運算組成的,都是通過這三種基本運算來實現(xiàn)的。第一節(jié) 布爾代數(shù)的基本概念 1.或運算 或運算又叫邏

48、輯加。兩個變量或運算的邏輯關(guān)系可表示為F = A + B,式中“+ ”號是或運算符,有時也用“”來表示。上式讀作“F 等于A或B”,或者“F等于A加B”。變量A和B中只要有一個取值為1,則F就為1;若A和B全為0,則F為0。其邏輯關(guān)系可以用真值表來描述, 如表2 - 1 所示。第一節(jié) 布爾代數(shù)的基本概念表2 - 1 或運算第一節(jié) 布爾代數(shù)的基本概念 2.與運算 與運算又叫邏輯乘。兩個變量與運算的邏輯關(guān)系可表示為F = AB 式中“”號表示與運算符,有時也用“”來表示,通常,與運算符可以省略。上式讀作“F等于A與B”,或者“F等于A乘B”。只有當變量A 與B 都為1時,F才為1;否則,F 就為0

49、,其邏輯關(guān)系可以用真值表表2-2來描述。第一節(jié) 布爾代數(shù)的基本概念表2 - 2 與運算第一節(jié) 布爾代數(shù)的基本概念 3.非運算 非運算又稱邏輯取反。對一個變量的非運算的邏輯關(guān)系可表示為F = A ,式中符號“ - ”表示非運算符。上式讀作“F 等于A的非”,其意思是若A為1,則F為0;反之,若A為0,則F 為1。非運算的邏輯關(guān)系可以用表2-3 所示的真值表來描述。第一節(jié) 布爾代數(shù)的基本概念表2-3 非運算第一節(jié) 布爾代數(shù)的基本概念 通過以上對布爾變量及3個基本運算的定義,可以對布爾代數(shù)下個定義: 布爾代數(shù)是一個由布爾變量集K、常量0、1以及或、與、非三種運算符所構(gòu)成的代數(shù)系統(tǒng), 記為B = (K

50、,+ ,- ,0,1) 其中,布爾變量集K是指布爾代數(shù)中的所有可能變量的集合,它可用任何字母表示,但每一個變量的取值只可能為常量0或1。而且,布爾代數(shù)中只有或、與、非三種運算。第一節(jié) 布爾代數(shù)的基本概念二、布爾函數(shù)及其表示方法 布爾代數(shù)中的函數(shù)定義與普通代數(shù)中函數(shù)定義十分相似,把布爾函數(shù)與邏輯網(wǎng)絡(luò)聯(lián)系起來,布爾函數(shù)可以這樣敘述:設(shè)某一邏輯網(wǎng)絡(luò)的輸入變量為x1 ,x2 ,xn ,輸出變量為F,如圖2-1 所示。對應(yīng)于變量x1 ,x2 ,xn的每一組確定值,F就有唯一確定的值,則稱F 是變量x1 ,x2 ,xn 的布爾函數(shù)。 記為 F = f(x1 ,x2 ,xn )圖2 - 1 布爾函數(shù)第一節(jié)

51、布爾代數(shù)的基本概念 注意:布爾代數(shù)中函數(shù)的取值也只可能是0或1。這是與普通代數(shù)不同的。 布爾函數(shù)的表示方法有三種形式:布爾表達式、真值表和卡諾圖。這與普通代數(shù)中用公式、表格和圖解這三種方法來表示函數(shù)十分類似。下面分別說明這三種表示方法。第一節(jié) 布爾代數(shù)的基本概念1. 布爾表達式 布爾表達式是由布爾變量和或、與、非三種運算符所構(gòu)成的式子,這是一種用公式來表示布爾函數(shù)的方法。 例如,要表示這樣一個函數(shù)關(guān)系:當兩個變量A 和B 取值相同時,函數(shù)取值為0;否則,函數(shù)取值為1。此函數(shù)稱為異或函數(shù),可以用下列布爾表達式來表示: F = f(A,B)= B + A 顯然,只要將A和B 的四種可能取值代入這表

52、達式,驗證是正確的。第一節(jié) 布爾代數(shù)的基本概念 真值表是由輸入變量的所有可能取值組合及其對的輸出函數(shù)值所構(gòu)成的表格,這是一種用表格表示布爾函數(shù)的方法。例如,對于前面的異或函數(shù)可以用表2-4 所示的真值表來表示。 2.真值表第一節(jié) 布爾代數(shù)的基本概念 真值表中的變量為兩個,共有22種取值組合,所以該表由4 行組成。當變量為n 個時,真值表就由2n 行組成。顯然,隨著變量數(shù)目的增加,真值表的行數(shù)將急劇增加。因此,一般當變量數(shù)目不超過4 個時,用真值表表示函數(shù)比較方便。表2 - 4 異或運算第一節(jié) 布爾代數(shù)的基本概念 例如,已知下列兩個函數(shù) F = xy ， G = x + y 列出F 和G 的真值

53、表,如表2-5所示。由表可知,它們的真值表完全相同,故F 和G 是相等的,即有： xy = x + y表2 - 5 F = xy和G = x + y 的真值表第一節(jié) 布爾代數(shù)的基本概念第二節(jié) 布爾代數(shù)的公式、定理和規(guī)則 根據(jù)布爾變量的取值只有0和1以及布爾變量僅有的三種運算的定義,不難推出下列基本公式:交換律 A + B = B + A (2.1.1) AB = BA (2.1.2)結(jié)合律 (A + B)+ C = A + (B + C) (2.2.1) (AB)C = A(BC) (2.2.2)一、布爾代數(shù)的基本公式分配律 A(B + C)= AB + AC (2.3.1) A + BC =

54、 (A + B)(A + C) (2.3.2)0-1 律 A + 1 = 1 (2.4.1) A + 0 = A (2.5.1) A 1 = A (2.4.2) A 0 = 0 (2.5.2) 互補律 A + A = 1 (2.6.1) A A = 0 (2.6.2) 等冪律 A + A = A (2.7.1) A A = A (2.7.2) 吸收律 A + A B = A (2.8.1) A(A + B)= A (2.8.2) A + A B = A + B (2.9.1) A( A + B)= A B (2.9.2) 對合律(雙重否定律) A = A (2.10) 以上是布爾代數(shù)的基本公式

55、。其中式(2.1.1)(2.6.1)、式(2.1.2)(2.6.2)和式(2.10)可以作為布爾代數(shù)的公理。公理是代數(shù)系統(tǒng)的基本出發(fā)點,是客觀存在的抽象,它無需證明,但它可以用客觀存在來驗證。以此為基礎(chǔ),可以推得布爾代數(shù)的其他公式(2.7)(2.9)。 例如,式(2.7.1)的證明如下: A + A = (A + A)1 (0-1律) = (A + A)(A + A) (互補律) = A + A A (分配律) = A + 0 (互補律) = A (0-1律) 又如,式(2.9.1)的證明如下: A + AB =(A + A)(A + B) (分配律) = 1(A + B) (互補律) = A

56、 + B (0-1律) 必須指出,上述基本公式中,有些公式與普通代數(shù)中的相 同,但有些公式卻是布爾代數(shù)中所特有的。這一點請讀者在以后使用中注意。二、布爾代數(shù)的主要定理 定理1 德摩根(De Morgan)定理 (1) x1 + x2 + + xn = x1x2xn (2) x1x2xn = x1 + x2 + + xn 這就是說,n 個變量的或的非等于各變量的非的與;n 個變量的與的非等于各變量的非的或。 當變量的數(shù)目較少時,該定理可很容易用真值表證明。當變量為n 個時,則可以用數(shù)學(xué)歸納法證明。 德摩根定理是布爾代數(shù)中一個很重要且經(jīng)常使用的定理,它提供了一種變換布爾表達式的簡便方法。由于它具有

57、反演特性,即把變量的與運算改成或運算,或運算改成與運算,所以又稱反演律。 定理2 香農(nóng)(Shannon)定理 f(x1,x2,xn ,0,1,+,)=f(x1,x2 ,xn,1,0,+ ) 這就是說,任何函數(shù)的反函數(shù)(或稱補函數(shù)),可以通過對該函數(shù)的所有變量取反,并將常量1換為0,0換為1,運算符“+ ”換為“”,“”換為“+ ”而得到。 證明:根據(jù)德摩根定理,任何函數(shù)的反函數(shù)可寫成 f( x1,x2 ,xn ,0,1,+ ,) =f1(x1,x2,xn,0,1,+ ,)+f2 (x1,x2,xn ,0,1,+ ,) =f1(x1,x2,xn ,0,1,+ ,)f2 (x1,x2,xn ,0,

58、1,+ ,)或?qū)懗?f(x1,x2,xn ,0,1,+ ,) =f1(x1,x2,xn ,0,1,+ ,)f2 (x1,x2,xn ,0,1,+ ,) =f1(x1,x2,xn ,0,1,+ ,)+ f2(x1,x2,xn ,0,1,+ ,) 其中,f1 和f2 是f 的兩個部分函數(shù)。對f1 和f2 重復(fù)上述過程,直到使f 中的每個變量都用德摩根定理。由于每對f(或f的部分函數(shù))應(yīng)用一次德摩根定理,就將部分函數(shù)(或子部分函數(shù))取反,并將與、或運算變換一次,以求得函數(shù)f (或部分函數(shù))的反函數(shù)。因此,當對每個變量進行德摩根變換后,其結(jié)果必然是f(x1,x2 ,xn,1,0,+ ),證畢。 香農(nóng)定

59、理實際上是德摩根定理的推廣,它可以用在任何復(fù)雜函數(shù)。 例2-1 已知函數(shù)F =AB + AB(C + D),求其反函數(shù)F。 解: F = AB + AB(C + D)= AB AB(C + D) = (A + B)(AB + C + D)= (A + B)(A + B)+ CD 利用香農(nóng)定理,可以直接寫出 F = (A + B)(A + B + CD)三、布爾代數(shù)的重要規(guī)則 布爾代數(shù)有3 個重要規(guī)則,即代入規(guī)則、反演規(guī)則和對偶規(guī)則,現(xiàn)分別敘述如下。 1. 代入規(guī)則 任何一個含有變量X 的等式,如果將所有出現(xiàn)X 的位置,都代之以一個布爾函數(shù)F,則等式仍然成立。這個規(guī)則稱為代入規(guī)則。 由于任何一個

60、布爾函數(shù)和任何一個變量一樣,只有0或1兩種取值,顯然,以上規(guī)則是成立的。 例2-2 已知等式A + B = AB,函數(shù)F = B + C,若用F 代入此等式中的B,則有: A + (B + C)= AB + C A + (B + C)= ABC 據(jù)此可以證明n 變量的德摩根定理的成立。 2. 對偶規(guī)則 任何一個布爾函數(shù)表達式F,如果將表達式中的所有的“+ ”改成“”,“”改成“+ ”,1改成0,0改成1,而變量保持不變,則可得到一個新的函數(shù)表達式Fd ,稱Fd 為F 的對偶函數(shù)。這一規(guī)則稱為對偶規(guī)則。例如,下列為幾個原函數(shù)及其對偶函數(shù): F = A B + ABC Fd = (A + B)(A