數(shù)字邏輯電路：第一章 數(shù)制和碼制

第一章數(shù)制和碼制1本章內(nèi)容

1.1

數(shù)制

1.2碼制

數(shù)：人認(rèn)識的是“數(shù)”

碼：機(jī)器內(nèi)部表示的“碼”數(shù)字、符號、字符等在機(jī)器里面都統(tǒng)一表示成二進(jìn)制代碼數(shù)制和碼制（1）2數(shù)制十進(jìn)制、二進(jìn)制、八進(jìn)制、十六進(jìn)制數(shù)制轉(zhuǎn)換碼制十進(jìn)制數(shù)的二進(jìn)制編碼8421碼（BCD碼）、余3碼、余3循環(huán)碼、格雷碼字符編碼7位ASCII、8位ASCII符號(正負(fù)數(shù))如何表示:原碼/補(bǔ)碼/反碼

計(jì)算機(jī)原理課程的內(nèi)容數(shù)制和碼制（2）3數(shù)制一個(gè)進(jìn)位計(jì)數(shù)包含兩個(gè)基本因素基數(shù)位權(quán)數(shù)制和碼制（3）4數(shù)制一個(gè)進(jìn)位計(jì)數(shù)包含兩個(gè)基本因素基數(shù)：數(shù)制中數(shù)碼的個(gè)數(shù)基數(shù)為R的數(shù)制（簡稱R進(jìn)制）包含0～R－1的數(shù)碼進(jìn)位規(guī)律是“逢R進(jìn)一”。數(shù)制和碼制（4）5數(shù)制一個(gè)進(jìn)位計(jì)數(shù)包含兩個(gè)基本因素位權(quán)：R進(jìn)制數(shù)中處于不同位數(shù)的數(shù)碼，代表不同的權(quán)值某個(gè)數(shù)位上的數(shù)值由本位數(shù)碼的值乘以本位對應(yīng)的固定常數(shù)該固定常數(shù)稱為位權(quán)不同的數(shù)位有不同的位權(quán)數(shù)制和碼制（5）6R進(jìn)制數(shù)N的表示方式并列表示方式

n為整數(shù)部分的數(shù)位，m為小數(shù)部分的數(shù)位，R表示基數(shù)多項(xiàng)式標(biāo)識方式Ki表示不同數(shù)位的數(shù)碼，（R－1）Ki0或數(shù)制和碼制（6）7十進(jìn)制數(shù)基數(shù)為10，數(shù)碼0～9任意一個(gè)十進(jìn)制數(shù)可以表示為權(quán)值10i如143.75數(shù)制和碼制（7）8二進(jìn)制數(shù)基數(shù)為2，數(shù)碼0，1任意一個(gè)二進(jìn)制數(shù)可以表示為權(quán)值2i如101.11數(shù)制和碼制（8）9八進(jìn)制數(shù)基數(shù)為8，數(shù)碼0～7任意一個(gè)八進(jìn)制數(shù)可以表示為十六進(jìn)制數(shù)基數(shù)為16，數(shù)碼0～9，ABCDEF任意一個(gè)十六進(jìn)制數(shù)可以表示為數(shù)制和碼制（9）10數(shù)制轉(zhuǎn)換二－十進(jìn)制互換二－八進(jìn)制互換二－十六進(jìn)制互換常識

K，M，G，T，P，E，Z…

基數(shù)轉(zhuǎn)換中常用的數(shù)11表1-12的冪表12

二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)

將二進(jìn)制數(shù)表示成按權(quán)展開式，并按十進(jìn)制運(yùn)算法則進(jìn)行計(jì)算，所得結(jié)果即為該數(shù)對應(yīng)的十進(jìn)制數(shù)。

例如，（10110.101）2=（？）10

(10110.101)2=1×24+1×22+1×21+1×2-1+1×2-3=16+4+2+0.5+0.125=(22.625)1013

十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)，整數(shù)和小數(shù)分別處理。

整數(shù)轉(zhuǎn)換——“除2取余”小數(shù)轉(zhuǎn)換——“乘2取整”

常用典型數(shù)，會心算！十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)

14整數(shù)轉(zhuǎn)換：除2取余數(shù)

例如，（35）10=（？）2

235余數(shù)217………

1

（K0）低位2

8………

1

（K1）24………0（K2）

22………

0

（K3）21………0

（K4）

0………1

（K5）高位即

(35)10=(100011)2

15

例如，（0.6875）10=（？）2

小數(shù)轉(zhuǎn)換

乘2取整數(shù)

高位

1(K-1)……

1.3750

0(K-2)……

0.7500

1(K-3)……

1.50000.6875

整數(shù)部分

×

2×

2低位

1(K-4)……

1.0000×

2×

2即:

(0.6875)10=(0.1011)2數(shù)制和碼制（11）16二－八進(jìn)制互換二－八進(jìn)制轉(zhuǎn)換：將（1101101)2轉(zhuǎn)成八進(jìn)制數(shù)八－二進(jìn)制轉(zhuǎn)換：將（573)8轉(zhuǎn)成二進(jìn)制數(shù)數(shù)制和碼制（12）17二－十六進(jìn)制互換二－十六進(jìn)制轉(zhuǎn)換：將（1101101)2轉(zhuǎn)成十六進(jìn)制數(shù)十六－二進(jìn)制轉(zhuǎn)換：將（5A3F)16轉(zhuǎn)成二進(jìn)制數(shù)數(shù)制和碼制（13）18數(shù)制碼制十進(jìn)制數(shù)的二進(jìn)制編碼8421碼（BCD碼）、余3碼、格雷碼字符編碼7位ASCII、8位ASCII數(shù)制和碼制（14）19十進(jìn)制數(shù)的二進(jìn)制編碼8421碼（BCD碼：binary-code-decimal）(有權(quán)碼)4位二進(jìn)制碼從高到低權(quán)值23(8)

,22(4)

,21(2)

,20(1)5421碼(有權(quán)碼)4位二進(jìn)制碼從高到低權(quán)值分別為5，4，2，12421碼(有權(quán)碼)4位二進(jìn)制碼從高到低權(quán)值分別為2，4，2，1余三碼(無權(quán)碼)十進(jìn)制數(shù)用余三碼表示，比8421碼在二進(jìn)制上多3余三碼＝8421碼＋（0011）220

幾種常用的編碼

十進(jìn)制數(shù)的二進(jìn)制編碼（BCD碼）

用4位二進(jìn)制代碼對十進(jìn)制數(shù)字符號進(jìn)行編碼，簡稱為二–十進(jìn)制代碼，或稱BCD(BinaryCodedDecimal)碼。

BCD碼既有二進(jìn)制的形式，又有十進(jìn)制的特點(diǎn)。常用的BCD碼有8421碼、2421碼和余3碼等。

21

十進(jìn)制數(shù)字符號0~9與8421碼、2421碼和余3碼的對應(yīng)關(guān)系0000000000011100010001010020010001001013001100110110401000100011150101101110006011011001001701111101101081000111010119100111111100十進(jìn)制字符8421碼2421碼余3碼

常用的3種BCD碼

22一、8421碼

8421碼：是用4位二進(jìn)制碼表示一位十進(jìn)制字符的一種有權(quán)碼，4位二進(jìn)制碼從高位至低位的權(quán)依次為23、22、21、20，即為8、4、2、1,故稱為8421碼。

按8421碼編碼的0～9與用4位二進(jìn)制數(shù)表示的0～9完全一樣。所以，8421碼是一種人機(jī)聯(lián)系時(shí)廣泛使用的中間形式。

8421碼中不允許出現(xiàn)1010～1111六種組合(因?yàn)闆]有十進(jìn)制數(shù)字符號與其對應(yīng))。

注意：

238421碼與十進(jìn)制數(shù)之間的轉(zhuǎn)換是按位進(jìn)行的，即十進(jìn)制數(shù)的每一位與4位二進(jìn)制編碼對應(yīng)。例如，1．8421碼與十進(jìn)制數(shù)之間的轉(zhuǎn)換(258)10

=(001001011000)8421碼

(0001001000001000)8421碼=(1208)10

例如，

(28）10

=（11100）2

=（00101000）8421

2．8421碼與二進(jìn)制的區(qū)別24二、2421碼

2421碼:是用4位二進(jìn)制碼表示一位十進(jìn)制字符的另一種有權(quán)碼，4位二進(jìn)制碼從高位至低位的權(quán)依次為2、4、2、1,故稱為2421碼。

若一個(gè)十進(jìn)制字符X的2421碼為a3a2a1a0，則該字符的值為

X=2a3+4a2+2a1+1a0

例如，(1101)2421碼=(7)10

2421碼與十進(jìn)制數(shù)之間的轉(zhuǎn)換同樣是按位進(jìn)行的，例如，

(258)10=(001010111110)2421碼

(0010000111101011)2421碼=(2185)10注意：2421碼不具備單值性。例如，0101和1011都對應(yīng)十進(jìn)制數(shù)字5。為了與十進(jìn)制字符一一對應(yīng)，2421碼不允許出現(xiàn)0101～1010的6種狀態(tài)。2421碼與十進(jìn)制數(shù)之間的轉(zhuǎn)換

25三、余3碼

余3碼：是由8421碼加上0011形成的一種無權(quán)碼，由于它的每個(gè)字符編碼比相應(yīng)8421碼多3，故稱為余3碼。

例如，十進(jìn)制字符5的余3碼等于5的8421碼0101加上0011，即為1000。

2.余3碼與十進(jìn)制數(shù)進(jìn)行轉(zhuǎn)換時(shí)，每位十進(jìn)制數(shù)字的編碼都應(yīng)余3。例如，

(256)10=(010110001001)余3碼

(1000100110011011)余3碼=(5668)10

注意:

1.余3碼中不允許出現(xiàn)0000、0001、0010、1101、1110和1111六種狀態(tài)。數(shù)制和碼制（16）26格雷碼一種無權(quán)碼編碼特點(diǎn)：任何相鄰的十進(jìn)制數(shù)的格雷碼僅有一位不同;最后1位與第1位也是僅一位不同2位：00,01,11,103位：000,001,011,010;110,111,101,100應(yīng)用:可以減少代碼變換種產(chǎn)生的錯誤,可靠性好有多種形式的格雷碼，都滿足相鄰碼之間僅有一位不同的特點(diǎn)數(shù)制和碼制（17）27十進(jìn)制數(shù)的4種格雷碼表十進(jìn)制數(shù)8421碼格雷碼1格雷碼2典型格雷碼修改格雷碼000000000000000000010100010001000100010110200100011001100110111300110010001000100101401000110011001100100501011110011101111100601101010010101011101701111011010001001111810001001110011001110910011000100011011010數(shù)制和碼制（18）28格雷碼的特點(diǎn)編碼特點(diǎn)：任何相鄰十進(jìn)制數(shù)的格雷碼僅有一位不同格雷碼1：中線對稱反射。典型格雷碼：可以對十進(jìn)制編碼，也可以對任意大的二進(jìn)制數(shù)進(jìn)行編碼。編碼規(guī)則：Gi＝Bi＋1Bi修改格雷碼：中線對稱反射，“余三循環(huán)碼”(循環(huán)碼的特點(diǎn)：相鄰兩個(gè)編碼之間只有一位數(shù)不同，而且首尾兩個(gè)編碼之間也只有一位數(shù)不同)29

轉(zhuǎn)換規(guī)則如下：

典型格雷碼與普通二進(jìn)制碼之間的轉(zhuǎn)換。

設(shè)二進(jìn)制碼為B=Bn-1Bn-2…Bi+1Bi…B1B0

對應(yīng)格雷碼為G=Gn-1Gn-2…Gi+1Gi…G1G0

有：

Gn-1=Bn-1Gi=Bi+1⊕Bi0≤i≤n-2

其中，運(yùn)算“⊕”稱為“異或”運(yùn)算，運(yùn)算規(guī)則是：

0⊕0=0；0⊕1=1；

1⊕0=1；1⊕1=0。

數(shù)制和碼制（19）30字符編碼數(shù)字系統(tǒng)中，需要對符號，文字，圖象等進(jìn)行編碼7位ASCII、8位ASCII7位ASCII編碼（教材13頁）高3位b6b5b4區(qū)分b6b5b4（000，001）：控制字符b6b5b4（010，011）：數(shù)字及通用符號b6b5b4（100，101）：大寫英文字母b6b5b4（110，111）：小寫英文字母8位數(shù)制和碼制——小結(jié)31數(shù)制十進(jìn)制、二進(jìn)制、八進(jìn)制、十六進(jìn)制數(shù)制轉(zhuǎn)換碼制十進(jìn)制數(shù)的二進(jìn)制編碼8421碼（BCD碼）、余3碼、余3循環(huán)碼、格雷碼字符編碼7位ASCII、8位ASCII原碼、補(bǔ)碼與反碼：帶符號的二進(jìn)制數(shù)編碼，將在計(jì)算機(jī)原理課程學(xué)習(xí)32心算練習(xí)：(32770)10=()2(10111.11)2=()10(10010011)8421BCD=()10

=()2(10010011)余3=()10第二章邏輯代數(shù)（1）33本章內(nèi)容

2.1邏輯代數(shù)的基本運(yùn)算與公式

2.2公式法化簡邏輯函數(shù)

2.3圖解法(卡諾圖)化簡邏輯函數(shù)

2.4邏輯函數(shù)的表格法化簡(Q-M法)第二章邏輯代數(shù)（2）342.1邏輯代數(shù)的基本運(yùn)算與公式

2.2公式法化簡邏輯函數(shù)

2.3圖解法(卡諾圖)化簡邏輯函數(shù)

2.4邏輯函數(shù)的表格法化簡(Q-M法)第二章邏輯代數(shù)（3）352.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)：又叫布爾代數(shù)，開關(guān)代數(shù)。是二進(jìn)制運(yùn)算的基礎(chǔ)，用代數(shù)方法研究邏輯問題。由英國數(shù)學(xué)家布爾和德.摩根于1847年提出。邏輯函數(shù)的表示：真值表，表達(dá)式，邏輯門。邏輯代數(shù)的基本運(yùn)算：與、或、非

(1)與運(yùn)算，邏輯乘

(2)或運(yùn)算，邏輯加

(3)非運(yùn)算，取反第二章邏輯代數(shù)（4）362.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)和普通代數(shù)的共同之處：變量和變量的運(yùn)算。邏輯代數(shù)一般用字母表示變量。邏輯變量的取值：“0”或“1”。邏輯代數(shù)的基本運(yùn)算：與、或、非第二章邏輯代數(shù)（4）372.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本運(yùn)算邏輯代數(shù)的基本公式第二章邏輯代數(shù)（5）382.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本運(yùn)算：與、或、非

(1)與運(yùn)算，邏輯乘ABF000100010111ABFABFBAF第二章邏輯代數(shù)（6）392.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本運(yùn)算：與、或、非

(2)或運(yùn)算，邏輯加ABF000101011111ABFBAF+第二章邏輯代數(shù)（7）402.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本運(yùn)算：與、或、非

(3)非運(yùn)算，取反AF0110FARAF第二章邏輯代數(shù)（8）412.1邏輯代數(shù)的基本運(yùn)算與公式其他基本的邏輯電路“與非”門：實(shí)現(xiàn)“與非”運(yùn)算的電路。ABF’＝AB000100010111BAFF=AB1110第二章邏輯代數(shù)（9）422.1邏輯代數(shù)的基本運(yùn)算與公式其他基本的邏輯電路“或非”門：實(shí)現(xiàn)“或非”運(yùn)算的電路。ABF’＝A＋B000101011111F=A＋B1000BAF+第二章邏輯代數(shù)（10）432.1邏輯代數(shù)的基本運(yùn)算與公式其他基本的邏輯電路“與或非”門：實(shí)現(xiàn)“與或非”運(yùn)算的電路。FBADC+BADC+F“與或非”門第二章邏輯代數(shù)（11）442.1邏輯代數(shù)的基本運(yùn)算與公式其他基本的邏輯電路“異或”門：實(shí)現(xiàn)“異或”運(yùn)算的電路?！爱惢颉遍TABF000101011110F=ABAB第二章邏輯代數(shù)（12）452.1邏輯代數(shù)的基本運(yùn)算與公式其他基本的邏輯電路“同或”門(“異或非”門)：實(shí)現(xiàn)“同或”運(yùn)算的電路。“同或”門ABF001100010111F=A

BAB第二章邏輯代數(shù)（13）462.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本運(yùn)算——小結(jié)基本運(yùn)算：與、或、非電路：“與”門，“或”門，“非”門常用運(yùn)算：與非、或非、與或非、異或、同或電路：“與非”門，“或非”門，“與或非”門“異或”門，“同或”門第二章邏輯代數(shù)（14）472.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本運(yùn)算邏輯代數(shù)的基本公式第二章邏輯代數(shù)（15）482.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本公式互補(bǔ)律1律0律第二章邏輯代數(shù)（16）492.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本公式交換律結(jié)合律分配律第二章邏輯代數(shù)（17）502.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本公式吸收律

反演律(德·摩根定律)第二章邏輯代數(shù)（18）512.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本公式對合律重疊律包含律第二章邏輯代數(shù)（19）522.1邏輯代數(shù)的基本運(yùn)算與公式邏輯代數(shù)的基本公式包含律推論證明：

第二章邏輯代數(shù)（20）532.1邏輯代數(shù)的基本運(yùn)算與公式——小結(jié)邏輯代數(shù)的基本運(yùn)算：基本運(yùn)算、常用運(yùn)算邏輯代數(shù)的基本公式：各種運(yùn)算基本公式

提醒注意“吸收律”，“包含律”第二章邏輯代數(shù)（21）54 2.1邏輯代數(shù)的基本運(yùn)算與公式

2.2公式法化簡邏輯函數(shù)

2.3圖解法(卡諾圖)化簡邏輯函數(shù)

2.4邏輯函數(shù)的表格法化簡(Q-M法)第二章邏輯代數(shù)（22）552.2公式法化簡邏輯函數(shù)化簡的目的讓邏輯函數(shù)表達(dá)式的含義更清楚。節(jié)省資源：用最少的電路、器件，器件的輸入也最少?；喣康牟煌磉_(dá)式結(jié)果會不同。第二章邏輯代數(shù)（23）562.2公式法化簡邏輯函數(shù)與或表達(dá)式化簡或與表達(dá)式化簡其他形式邏輯函數(shù)化簡第二章邏輯代數(shù)（24）57與或表達(dá)式化簡最簡與或表達(dá)式：1、乘積的個(gè)數(shù)最少(用門電路實(shí)現(xiàn)，用的與門數(shù)最少）2、在滿足1的條件下，乘積項(xiàng)中的變量最少(與門的輸入端最少)

表達(dá)式是否為最簡?BAC+FBAF第二章邏輯代數(shù)（25）58與或表達(dá)式化簡例1展開：合并：分配律：互補(bǔ)律：第二章邏輯代數(shù)（26）59與或表達(dá)式化簡例2反演律吸收律第二章邏輯代數(shù)（27）60與或表達(dá)式化簡例3合并：分配律：吸收律：1律：第二章邏輯代數(shù)（28）612.2公式法化簡邏輯函數(shù)與或表達(dá)式化簡或與表達(dá)式化簡其他形式邏輯函數(shù)化簡第二章邏輯代數(shù)（29）62或與表達(dá)式化簡或與表達(dá)式：最簡條件：

(1)、或項(xiàng)個(gè)數(shù)最少(或門用的最少) (2)、在滿足1的條件下，或項(xiàng)中變量數(shù)最少結(jié)果要求：化簡結(jié)果仍為或與表達(dá)式第二章邏輯代數(shù)（35）632.2公式法化簡邏輯函數(shù)與或表達(dá)式化簡或與表達(dá)式化簡其他形式邏輯函數(shù)化簡第二章邏輯代數(shù)（36）642.2公式法化簡邏輯函數(shù)其他形式邏輯函數(shù)化簡轉(zhuǎn)換為與或表達(dá)式，再化簡第二章邏輯代數(shù)（39）652.2公式法化簡邏輯函數(shù)——小結(jié)與或表達(dá)式化簡：利用基本公式化簡其他形式邏輯函數(shù)化簡：轉(zhuǎn)換為“與或”表達(dá)式，再化簡第二章邏輯代數(shù)（26）66 2.1邏輯代數(shù)的基本運(yùn)算與公式

2.2公式法化簡邏輯函數(shù)

2.3圖解法(卡諾圖)化簡邏輯函數(shù)

2.4邏輯函數(shù)的表格法化簡(Q-M法)第二章邏輯代數(shù)（27）672.3圖解法(卡諾圖)化簡邏輯函數(shù)公式法化簡的缺點(diǎn)需要復(fù)雜的計(jì)算，容易出錯；不容易判斷結(jié)果是否為最簡；圖解法優(yōu)點(diǎn)：直觀明了，過程簡單，可從圖中直接求出最簡表達(dá)式；缺點(diǎn)：函數(shù)變量不能太多，一般為4變量及4變量以下；4變量以上用卡諾圖化簡比較困難。第二章邏輯代數(shù)（28）682.3圖解法(卡諾圖)化簡邏輯函數(shù)邏輯代數(shù)中的兩個(gè)重要概念最小項(xiàng)（MinTerm）最大項(xiàng)（MaxTerm）第二章邏輯代數(shù)（29）692.3圖解法(卡諾圖)化簡邏輯函數(shù)最小項(xiàng)的定義設(shè)一個(gè)函數(shù)表達(dá)式中有n個(gè)變量，由它們組成的具有n個(gè)變量的“與項(xiàng)”中，每個(gè)變量以原變量或反變量的形式出現(xiàn)且僅出現(xiàn)一次，這個(gè)與項(xiàng)為最小項(xiàng)。例如：n=3，對A、B、C，有8個(gè)最小項(xiàng)第二章邏輯代數(shù)（30）702.3圖解法(卡諾圖)化簡邏輯函數(shù)最小項(xiàng)的性質(zhì)N個(gè)變量有2n個(gè)最小項(xiàng)。對任意最小項(xiàng)，只有一組變量取值使它的值為1，其他取值使該最小項(xiàng)為0任何邏輯函數(shù)均可表示為唯一的一組最小項(xiàng)之和，稱為標(biāo)準(zhǔn)的與或表達(dá)式某一最小項(xiàng)不是包含在F的原函數(shù)中，就是包含在F的反函數(shù)中n個(gè)變量全體最小項(xiàng)之和必為“1”第二章邏輯代數(shù)（31）712.3圖解法(卡諾圖)化簡邏輯函數(shù)最小項(xiàng)的表示將最小項(xiàng)表示為mi，i可近似認(rèn)為2進(jìn)制表示的10進(jìn)制數(shù)值

應(yīng)用舉例：n=3時(shí)8個(gè)最小項(xiàng)為（C為高位，A低位）第二章邏輯代數(shù)（32）722.3圖解法(卡諾圖)化簡邏輯函數(shù)舉例：用最小項(xiàng)表示一個(gè)函數(shù)第二章邏輯代數(shù)（33）732.3圖解法(卡諾圖)化簡邏輯函數(shù)最大項(xiàng)的定義設(shè)一個(gè)函數(shù)表達(dá)式中有n個(gè)變量，由他們組成的具有n個(gè)變量的或項(xiàng)中，每個(gè)變量以原變量或反變量的形式出現(xiàn)且僅出現(xiàn)一次，則稱這個(gè)項(xiàng)為最大項(xiàng)。例如：n=3的最大項(xiàng)為第二章邏輯代數(shù)（34）742.3圖解法(卡諾圖)化簡邏輯函數(shù)最大項(xiàng)的性質(zhì)N個(gè)變量有2n個(gè)最大項(xiàng)。對任意最大項(xiàng)，只有一組變量取值使它的值為0，其他取值使該最大項(xiàng)為1任何邏輯函數(shù)均可表示為唯一的一組最大項(xiàng)之積，稱為標(biāo)準(zhǔn)的或與表達(dá)式某一最大項(xiàng)不是包含在F的原函數(shù)中，就是包含在F的反函數(shù)中n個(gè)變量全體最大項(xiàng)之積必為“0”第二章邏輯代數(shù)（35）752.3圖解法(卡諾圖)化簡邏輯函數(shù)舉例：用最大項(xiàng)表示一個(gè)函數(shù)第二章邏輯代數(shù)（36）762.3圖解法(卡諾圖)化簡邏輯函數(shù)最大項(xiàng)與最小項(xiàng)的關(guān)系（1）對于所有的i，相同i的最大項(xiàng)與最小項(xiàng)互補(bǔ)和互為對偶式（2）對于所有的i，第二章邏輯代數(shù)（37）772.3圖解法(卡諾圖)化簡邏輯函數(shù)卡諾圖：KarnaughMap；卡諾圖：邏輯函數(shù)的圖示表示，把最小項(xiàng)填入卡諾圖，利用相鄰最小項(xiàng)的互補(bǔ)性，消去一個(gè)變量，實(shí)現(xiàn)化簡?？ㄖZ圖的構(gòu)成

(1)由矩形或正方形組成的圖形

(2)將矩形分成若干小方塊，每個(gè)小方塊對應(yīng)一個(gè)最小項(xiàng)。第二章邏輯代數(shù)（38）782.3圖解法(卡諾圖)化簡邏輯函數(shù)1變量卡諾圖整體為1只有一個(gè)變量，將大方框劃分為左、右兩部分，表示1也可以將大方框劃分為上、下兩部分，表示第二章邏輯代數(shù)（39）792.3圖解法(卡諾圖)化簡邏輯函數(shù)2變量卡諾圖：假設(shè)兩個(gè)變量分別為A和B一個(gè)變量用大方框左、右兩部分表示另一個(gè)變量用大方框上、下兩部分表示將兩圖合二為一，可得2變量卡諾圖第二章邏輯代數(shù)（40）802.3圖解法(卡諾圖)化簡邏輯函數(shù)2變量卡諾圖AB一個(gè)整體可由代表4個(gè)最小項(xiàng)的四個(gè)小方格組成：

改畫成m1

m2

m3m0

即2變量卡諾圖第二章邏輯代數(shù)（41）812.3圖解法(卡諾圖)化簡邏輯函數(shù)3變量卡諾圖一個(gè)整體分成8個(gè)小方格

BAC1000110110m1

m0

m3

m2

m5

m4

m7

m6

注意：上表頭編碼按00－01―11－10循環(huán)碼順序排列，而不是00－01－10－11

第二章邏輯代數(shù)（42）822.3圖解法(卡諾圖)化簡邏輯函數(shù)循環(huán)碼（格雷碼）循環(huán)碼的定義：相鄰兩個(gè)編碼之間只有一位數(shù)不同，而且首尾兩個(gè)編碼之間也只有一位數(shù)不同，這種編碼叫循環(huán)碼。2位循環(huán)碼:000111103位循環(huán)碼:000001011010110111101100循環(huán)碼的特點(diǎn)：每次只變一位；用在卡諾圖上，可以消去最小項(xiàng)的多余變量。第二章邏輯代數(shù)（41）833變量卡諾圖的含義BAC1000110110m1

m0

m3

m2

m5

m4

m7

m6

BAC1000110110第二章邏輯代數(shù)（41）843變量卡諾圖化簡3變量函數(shù)如何用卡諾圖化簡？

BAC1000110110第二章邏輯代數(shù)（43）852.3圖解法(卡諾圖)化簡邏輯函數(shù)4變量卡諾圖BADC0011011000110110m1

m0

m3

m2

m5

m4

m7

m6

m13

m12

m15

m14

m9

m8

m11

m10

第二章邏輯代數(shù)（43）864變量卡諾圖2個(gè)最小項(xiàng)相鄰BADC0011011000110110m1

m0

m3

m2

m5

m4

m7

m6

m13

m12

m15

m14

m9

m8

m11

m10

合并后減少1個(gè)變量第二章邏輯代數(shù)（43）874變量卡諾圖4個(gè)最小項(xiàng)相鄰BADC0011011000110110m1

m0

m3

m2

m5

m4

m7

m6

m13

m12

m15

m14

m9

m8

m11

m10

合并后減少2個(gè)變量第二章邏輯代數(shù)（43）884變量卡諾圖8個(gè)最小項(xiàng)相鄰合并后減少3個(gè)變量BADC0011011000110110m1

m0

m3

m2

m5

m4

m7

m6

m13

m12

m15

m14

m9

m8

m11

m10

第二章邏輯代數(shù)（43）89最小項(xiàng)的卡諾圖表示BAC1000110110m1

m0

m3

m2

m5

m4

m7

m6

在函數(shù)最小項(xiàng)對應(yīng)的小方塊填“1”，其他方塊填“0”；BAC10001101101

0010

0

1

1第二章邏輯代數(shù)（44）902.3圖解法(卡諾圖)化簡邏輯函數(shù)卡諾圖化簡的步驟1按照循環(huán)碼規(guī)律指定卡諾圖變量取值；2在函數(shù)最小項(xiàng)對應(yīng)的小方塊填“1”，其他方塊填“0”；3合并相鄰填“1”的小方塊，兩個(gè)方塊合并消去一個(gè)變量（一維塊）；4個(gè)方塊合并消去兩個(gè)變量（二維塊）；5使每一最小項(xiàng)至少被合并包含過一次；每個(gè)合并的圈中，至少要有一個(gè)“1”沒有被圈過，否則這個(gè)圈就是多余的。4合并過程中先找大圈合并，圈越大消去的變量越多；第二章邏輯代數(shù)（45）912.3圖解法(卡諾圖)化簡邏輯函數(shù)例1“與或”式化簡：

BAC10001101100

0

10

01

1

1化簡結(jié)果：第二章邏輯代數(shù)（46）922.3圖解法(卡諾圖)化簡邏輯函數(shù)例2“與或”式化簡：BADC001101100011011011111111第二章邏輯代數(shù)（47）932.3圖解法(卡諾圖)化簡邏輯函數(shù)例2“與或”式化簡(續(xù)）：BADC001101100011011011111111化簡結(jié)果：第二章邏輯代數(shù)（47）942.3圖解法(卡諾圖)化簡邏輯函數(shù)規(guī)則的深刻理解BADC001101100011011011111111有沒有問題？大框(AC)包含的最小項(xiàng)被4個(gè)小框完全包含，AC是多余的項(xiàng)。

最簡表達(dá)式應(yīng)為：第二章邏輯代數(shù)（44）952.3圖解法(卡諾圖)化簡邏輯函數(shù)卡諾圖化簡的步驟1按照循環(huán)碼規(guī)律指定卡諾圖變量取值；2在函數(shù)最小項(xiàng)對應(yīng)的小方塊填“1”，其他方塊填“0”；3合并相鄰填“1”的小方塊，兩個(gè)方塊合并消去一個(gè)變量（一維塊）；4個(gè)方塊合并消去兩個(gè)變量（二維塊）；5使每一最小項(xiàng)至少被合并包含過一次；每個(gè)合并的圈中，至少要有一個(gè)“1”沒有被圈過，否則這個(gè)圈就是多余的。4合并過程中先找大圈合并，圈越大消去的變量越多；第二章邏輯代數(shù)（47）96圖解法求解反函數(shù)

BAC10001101100

0

10

01

1

1化簡結(jié)果：卡諾圖中根據(jù)0化簡出的函數(shù)是原函數(shù)的反函數(shù)。理論依據(jù)：第二章邏輯代數(shù)（47）972.3圖解法(卡諾圖)化簡邏輯函數(shù)5變量函數(shù)的卡諾圖化簡CBAED000001011010110111101100000111101111111111111111第二章邏輯代數(shù)（47）985變量函數(shù)的卡諾圖化簡CBAED0000010110101101111011000001111011111111111111第二章邏輯代數(shù)（47）99卡諾圖化簡法優(yōu)點(diǎn)：直觀明了，過程簡單，可從圖中直接求出最簡表達(dá)式；缺點(diǎn)：函數(shù)變量不能太多，一般為4變量及4變量以下；4變量以上用卡諾圖化簡比較困難，容易出錯。第二章邏輯代數(shù)（48）1002.3圖解法(卡諾圖)化簡邏輯函數(shù)特殊形式的邏輯函數(shù)化簡邏輯函數(shù)的基本形式：單輸出邏輯函數(shù)，F(xiàn)＝f(A,B,C…)特殊形式的邏輯函數(shù)：

1.多輸出邏輯函數(shù)

2.包含無關(guān)項(xiàng)（Don’tCare）的邏輯函數(shù)第二章邏輯代數(shù)（49）1012.3圖解法(卡諾圖)化簡邏輯函數(shù)特殊形式的邏輯函數(shù)化簡多輸出邏輯函數(shù)：同一組輸入變量，有兩個(gè)以上的輸出。

F1＝f1(A,B,C…)F2＝f2(A,B,C…)多輸出邏輯函數(shù)的化簡：化簡時(shí)，在“與或”表達(dá)式中要盡量尋找公共的“或”項(xiàng)，使公共項(xiàng)為多個(gè)函數(shù)共享，這時(shí)從單個(gè)輸出看可能不是最簡，但總體是最簡。多輸出邏輯函數(shù)的化簡（不作為基本要求）第二章邏輯代數(shù)（50）1022.3圖解法(卡諾圖)化簡邏輯函數(shù)特殊形式的邏輯函數(shù)化簡包含無關(guān)項(xiàng)（Don’tCare）的邏輯函數(shù)：函數(shù)F的取值只和一部分最小項(xiàng)有關(guān)，另一部分最小項(xiàng)既可以取“0”，也可以取“1”，這些最小項(xiàng)稱“無關(guān)項(xiàng)”或“任意項(xiàng)”?！盁o關(guān)項(xiàng)”的兩種情況：

1.這些輸入組合不可能出現(xiàn)。

2.輸入組合雖能出現(xiàn)，但無需關(guān)心最小項(xiàng)是“1”還是“0”。第二章邏輯代數(shù)（51）103例1：設(shè)計(jì)一位十進(jìn)制數(shù)的數(shù)值范圍判斷器，當(dāng)x>=5，F(xiàn)=1；否則，F(xiàn)=0。(ABCD表示一位十進(jìn)制數(shù),A是低位,D是高位)ABCDF000001000001000110000010010101011011110100011100110101×1101×0011×1011×0111×1111×××11××××11100000BADC0011011000110110第二章邏輯代數(shù)（51）104例2：化簡函數(shù)01×11×0×01100×11BADC0011011000110110第二章邏輯代數(shù)（51）105求例2的反函數(shù)01×11×0×01100×11BADC0011011000110110有沒有問題？冗余!第二章邏輯代數(shù)（51）106求例2的反函數(shù)01×11×0×01100×11BADC0011011000110110第二章邏輯代數(shù)（51）1072.3圖解法(卡諾圖)化簡邏輯函數(shù)——小結(jié)公式法：計(jì)算復(fù)雜，容易出錯；難判斷最簡圖解法：直觀明了，過程簡單，易判斷最簡；變量數(shù)4最小項(xiàng)、最大項(xiàng)：性質(zhì)，對函數(shù)的表示圖解法化簡邏輯函數(shù)的規(guī)則圖解法求解反函數(shù)圖解法化簡包含無關(guān)項(xiàng)的邏輯函數(shù)圖解法求解包含無關(guān)項(xiàng)的反函數(shù)第二章邏輯代數(shù)（52）108 2.1邏輯代數(shù)的基本運(yùn)算與公式

2.2公式法化簡邏輯函數(shù)

2.3圖解法(卡諾圖)化簡邏輯函數(shù)

2.4邏輯函數(shù)的表格法化簡(Q-M法)第二章邏輯代數(shù)（53）1092.4邏輯函數(shù)的表格法化簡(Q-M法)公式法：計(jì)算復(fù)雜，容易出錯；難判斷最簡圖解法：直觀明了，過程簡單;易判斷最簡；變量數(shù)4

。第二章邏輯代數(shù)（53）110多變量函數(shù)（變量個(gè)數(shù)>=5）如何化簡？用新的工具完成：計(jì)算機(jī)我們能否從公式法和圖解法中得到某些啟示呢？第二章邏輯代數(shù)（53）111化簡函數(shù)第二章邏輯代數(shù)（53）112如何利用計(jì)算機(jī)進(jìn)行函數(shù)化簡？能否從公式法有所發(fā)現(xiàn)？計(jì)算機(jī)的特點(diǎn)：適合做重復(fù)而又復(fù)雜的工作！教給計(jì)算機(jī)學(xué)習(xí)公式，并識別合并項(xiàng)，很困難！第二章邏輯代數(shù)（53）11300110110001101100

00

1

0

1

0

1

1

1

1

0

11

0

1

BADC化簡函數(shù)：用卡諾圖第二章邏輯代數(shù)（53）114如何利用計(jì)算機(jī)進(jìn)行函數(shù)化簡？00110110001101100

00

1

0

1

0

1

1

1

1

0

11

0

1

BADC觀察卡諾圖通過兩個(gè)相鄰的“1”

合并減少一個(gè)變量。繼續(xù)合并相鄰項(xiàng)可再減少一個(gè)變量。問題：相鄰項(xiàng)通過組合方式合并，會產(chǎn)生重復(fù)！解決問題辦法：設(shè)計(jì)一個(gè)較好的計(jì)算機(jī)算法，既可以合并，也可以挑出必要的項(xiàng)。第二章邏輯代數(shù)（54）1152.4邏輯函數(shù)的表格法化簡(Q-M法)Q-M法是用分組表格法，基本思想是相鄰兩個(gè)最小項(xiàng)中有一個(gè)變量互補(bǔ)，這兩相鄰與項(xiàng)合成為一新的與項(xiàng)，從而消去一變量。Q-M(Quine-McCluskey)法和卡諾圖法的化簡思路是一致的。表格法優(yōu)點(diǎn)：適合于多變量的函數(shù)，化簡過程規(guī)律性強(qiáng)，適用于計(jì)算機(jī)算法實(shí)現(xiàn)。缺點(diǎn)：人工進(jìn)行表格法化簡很繁瑣。第二章邏輯代數(shù)（55）1162.4邏輯函數(shù)的表格法化簡(Q-M法)什么情況下會出現(xiàn)“相鄰兩個(gè)最小項(xiàng)中有一個(gè)變量互補(bǔ)”？從最小項(xiàng)的編號上看有什么規(guī)律？觀察：以4變量卡諾圖為例：

m10m11m9m8m14m15m13m12m6m7m5m4m2m3m1m0BADC0011011000110110m1同m0,m3,m5,m9相鄰，下標(biāo)編號：

0001與0000,0011,0101,1001m1同m4,m8,m10,m13等不相鄰，下標(biāo)編號為：0001與0100,1000,1010,1101第二章邏輯代數(shù)（56）1172.4邏輯函數(shù)的表格法化簡(Q-M法)結(jié)論：

最小項(xiàng)編號中“1”的個(gè)數(shù)差＝0，肯定不相鄰最小項(xiàng)編號中“1”的個(gè)數(shù)差>＝2，肯定不相鄰最小項(xiàng)編號中“1”的個(gè)數(shù)差＝1，可能相鄰！按照最小項(xiàng)mi下標(biāo)編號中二進(jìn)制數(shù)“1”的個(gè)數(shù)進(jìn)行分組比較，可以化簡。第二章邏輯代數(shù)（57）1182.4邏輯函數(shù)的表格法化簡(Q-M法)表格法化簡按照步驟進(jìn)行：（1）求出函數(shù)全部的質(zhì)蘊(yùn)涵項(xiàng)，（2）從質(zhì)蘊(yùn)涵項(xiàng)中選出必要的質(zhì)蘊(yùn)涵項(xiàng)。蘊(yùn)涵項(xiàng)：函數(shù)“與或”表達(dá)式中的每個(gè)“與”項(xiàng)稱為蘊(yùn)涵項(xiàng)。質(zhì)蘊(yùn)涵項(xiàng)：不能通過相鄰項(xiàng)合并的蘊(yùn)涵項(xiàng)稱為質(zhì)蘊(yùn)涵項(xiàng)。第二章邏輯代數(shù)（58）1192.4邏輯函數(shù)的表格法化簡(Q-M法)舉例：化簡函數(shù)第一步：

求出函數(shù)全部的質(zhì)蘊(yùn)涵項(xiàng)1）先把F中的各mi，按下標(biāo)i中“1”的個(gè)數(shù)，由少到多，分組排隊(duì)列表(見表I)。組號是mi中i所包含“1”的個(gè)數(shù)。11111510111334001112010110100190110620001800104010021ABCD最小項(xiàng)組號表I第二章邏輯代數(shù)（59）1202）在表I的相鄰組間進(jìn)行逐項(xiàng)搜索，尋找相鄰項(xiàng)，把可以合并的記在表II中，并在表I中相應(yīng)的最小項(xiàng)旁作記號“√”。表II所列均是變量數(shù)為n-1的與項(xiàng)（n是F的變量數(shù)），它們同樣按與項(xiàng)所含“1”的個(gè)數(shù)由少到多，分組排列。3）重復(fù)上述過程，直到不能合并為止。2.4邏輯函數(shù)的表格法化簡(Q-M法)2.4邏輯函數(shù)的Q-M法化簡12100_18,121_1113,15_01112,1310_19,130_018,10_0018,9001_4,120_104,6010_2,1001_02,6321ABCDm組號表II√√√√√√√√√1111151011133001112010110100190110620001800104010021ABCD最小項(xiàng)組號表I邏輯函數(shù)的Q-M法化簡12200_18,121_1113,15_01112,1310_19,130_018,10_0018,9001_4,120_104,6010_2,1001_02,6321ABCDm組號表II√√√√1_0_8,9,12,13P1P2P3P4P5P6P7在表I、II、III中，未打“√”的，標(biāo)以P1~P7，稱質(zhì)蘊(yùn)涵項(xiàng)。全部質(zhì)蘊(yùn)涵項(xiàng)，全部覆蓋了F的各最小項(xiàng)。1DCBAm組號表III12300110110001101100

00

1

0

1

0

1

1

1

1

0

11

0

1

BADC在卡諾圖上看全部質(zhì)蘊(yùn)涵項(xiàng)P1P2P3P4P6P7由圖可見，P1~P7覆蓋了F的全部最小項(xiàng)；對每個(gè)P項(xiàng)，它們是不能再和其它P項(xiàng)或最小項(xiàng)合并了。由圖還可見，P1~P7中有不必要的質(zhì)蘊(yùn)涵項(xiàng)：例如，若P2，P3必須，則P1就不必要。P5邏輯函數(shù)的Q-M法化簡124如何挑選必要的質(zhì)蘊(yùn)涵項(xiàng)？從卡諾圖上能否有所啟發(fā)？00110110001101100

00

1

0

1

0

1

1

1

1

0

11

0

1

BADCP1P2P3先觀察P1，P2，P3從卡諾圖中可以看出：P2，P3可能是必要項(xiàng)，P1是冗余項(xiàng)。原因：P1包含的兩個(gè)最小項(xiàng)被P2和P3所包含。有沒有什么啟發(fā)?邏輯函數(shù)的Q-M法化簡125如何挑選必要的質(zhì)蘊(yùn)涵項(xiàng)？00110110001101100

00

1

0

1

0

1

1

1

1

0

11

0

1

BADCP1P2P3如果一個(gè)P項(xiàng)中的最小項(xiàng)被其它P項(xiàng)全包含，則該P(yáng)項(xiàng)是冗余項(xiàng)。

編寫算法比較復(fù)雜，因?yàn)镻2，P3是否為冗余項(xiàng)不確定！

反過來看，先挑選必要的P項(xiàng)！如果只觀察P1、P2、P3，由于1010只被P2包含，0100只被P3包含，P2，P3為必需。邏輯函數(shù)的Q-M法化簡126如何挑選必要的質(zhì)蘊(yùn)涵項(xiàng)？繼續(xù)觀察包含全部P項(xiàng)卡諾圖發(fā)現(xiàn)P6和P7為必須保留的項(xiàng)！原因是最小項(xiàng)1111只被P6包含，1001只被P7包含。00110110001101100

00

1

0

1

0

1

1

1

1

0

11

0

1

BADCP1P2P3P4P6P7P5既然P6和P7為必須保留的項(xiàng)，保留P6和P7！邏輯函數(shù)的Q-M法化簡127由于卡諾圖用計(jì)算機(jī)處理起來較繁瑣，計(jì)算機(jī)處理表格比較方便，作出P項(xiàng)和最小項(xiàng)的對應(yīng)表質(zhì)蘊(yùn)涵項(xiàng)最小項(xiàng)P1P2P3P4P5P6P7m2m4m8m6m9m12m10m13m15邏輯函數(shù)的Q-M法化簡1282.4邏輯函數(shù)的表格法化簡(Q-M法)第二步：從全部質(zhì)蘊(yùn)涵項(xiàng)中選出必要的質(zhì)蘊(yùn)涵項(xiàng)。1）先作P1~P7和mi對應(yīng)的表格（表IV）表IV質(zhì)蘊(yùn)涵項(xiàng)最小項(xiàng)P1P2P3P4P5P6P7m2m4m8m6m9m12m10m13m151292）進(jìn)行“行列消去”:檢查所有的mi對應(yīng)的列，若在mi對應(yīng)列中只有一個(gè)△

，則該△所對應(yīng)的Pj項(xiàng)為必要；保留Pj并消去Pj對應(yīng)的行。由于Pj項(xiàng)為必要，Pj

包含的所有△對應(yīng)的列（最小項(xiàng)m）均可消去。m9列只有一個(gè)△，所以P7為必要；P7有4個(gè)△，分別對應(yīng)m8,m9,m12,m13。P7所蘊(yùn)涵的m8,m9,m12,m13均可從表中刪去。同理，P6也為必要，P6所蘊(yùn)涵的m13,m15可以從表中刪去。表IVP1P2P3P4P5P6P7m2m4m8m6m9m12m10m13m15質(zhì)蘊(yùn)涵項(xiàng)最小項(xiàng)邏輯函數(shù)的Q-M法化簡130觀察一下剩余P項(xiàng)和卡諾圖的關(guān)系00110110001101100

00

1

0

1

0

1

0

0

0

0

00

0

1

BADCP1P2P3P4P5刪除P6和P7，對應(yīng)于卡諾圖是將P6和P7包含的最小項(xiàng)改為“0”！P1P2P3P4P5m2m4m6m10質(zhì)蘊(yùn)涵項(xiàng)最小項(xiàng)觀察卡諾圖，P4和P5是冗余項(xiàng)，對應(yīng)于表中P4行只有一個(gè)△，P5行只有一個(gè)△，P4和P5行可以刪除1313）進(jìn)行“行消去”：檢查所有的Pj,對應(yīng)的行，若在Pj對應(yīng)的行中只有一個(gè)△

，再檢查該△所對應(yīng)的列mi，如果mi還有其它的△，則Pj項(xiàng)為非必要質(zhì)蘊(yùn)涵項(xiàng)F(因?yàn)槠渌腜中已經(jīng)包含了Pj

，消去Pj對應(yīng)的行。P1P2P3P4P5m2m4m6m10質(zhì)蘊(yùn)涵項(xiàng)最小項(xiàng)表VP4行只有一個(gè)△，該△對應(yīng)的m8列中還有其它的△（P3行）；P4為非必要，消去P4，同理消去P5。質(zhì)蘊(yùn)涵項(xiàng)最小項(xiàng)m2m4m6P1P2P3m10表VI1324