計(jì)算機(jī)科學(xué)技術(shù)導(dǎo)論教程第2章

計(jì)算機(jī)科學(xué)技術(shù)的基礎(chǔ)知識(shí)

內(nèi)容提要：計(jì)算機(jī)的運(yùn)算基礎(chǔ)命題邏輯與邏輯代數(shù)基礎(chǔ)計(jì)算機(jī)的基本結(jié)構(gòu)與工作原理程序設(shè)計(jì)基礎(chǔ)算法基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)要求：通過(guò)本章的學(xué)習(xí)，應(yīng)掌握數(shù)制間的轉(zhuǎn)換方法以及數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的表示形式，理解邏輯代數(shù)、計(jì)算機(jī)的工作原理、程序設(shè)計(jì)以及算法與數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)，為學(xué)習(xí)本書(shū)的以下各章和后續(xù)課程打好基礎(chǔ)

1數(shù)制十進(jìn)制：是使用數(shù)字1、2、…、9、0等符號(hào)來(lái)表示數(shù)值且采用“逢十進(jìn)一”的進(jìn)位計(jì)數(shù)制位權(quán)表示法數(shù)制的特點(diǎn)：數(shù)字的總個(gè)數(shù)等于基數(shù)。如十進(jìn)制使用10個(gè)數(shù)字（0～9）最大的數(shù)字比基數(shù)小1。如十進(jìn)制中最大的數(shù)字為9每個(gè)數(shù)字都要乘以基數(shù)的冪次，該冪次由每個(gè)數(shù)字所在的位置決定任何一個(gè)N進(jìn)制數(shù)A＝AnAn－1…A1A0.A－1A－2…A－m2二進(jìn)制二進(jìn)制：使用數(shù)字0和1等符號(hào)來(lái)表示數(shù)值且采用“逢二進(jìn)一”的進(jìn)位計(jì)數(shù)制二進(jìn)制數(shù)制的特點(diǎn)：

僅使用0和1兩個(gè)數(shù)字最大的數(shù)字為1，最小的數(shù)字為0每個(gè)數(shù)字都要乘以基數(shù)2的冪次，該冪次由每個(gè)數(shù)字所在的位置決定

二進(jìn)制加法和乘法運(yùn)算規(guī)則：

0＋0＝0; 0×0＝0; 0＋1＝1; 0×1＝01＋0＝1; 1×0＝0; 1＋1＝1; 1×1＝1

3八進(jìn)制與十六進(jìn)制八進(jìn)制：使用數(shù)字0、1、2、3、4、5、6、7等符號(hào)來(lái)表示數(shù)值的，且采用“逢八進(jìn)一”的進(jìn)位計(jì)數(shù)制十六進(jìn)制：使用數(shù)字0、1、2、3、4、5、6、7、8、9和A、B、C、D、E、F等符號(hào)來(lái)表示數(shù)值，其中A、B、C、D、E、F分別表示數(shù)字10、11、12、13、14、15。十六進(jìn)制的計(jì)數(shù)方法為“逢十六進(jìn)一”

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

除基取余法：“除基取余，先余為低（位），后余為高（位）”〖例2-1〗（55）10＝（110111）2

2222221551276130131110余數(shù)5十進(jìn)制整數(shù)轉(zhuǎn)換為非十進(jìn)制整數(shù)（續(xù)）〖例2-2,例2-3〗（55）10=（67）8=（37）16886555516166703703余數(shù)余數(shù)6十進(jìn)制小數(shù)轉(zhuǎn)換為非十進(jìn)制小數(shù)

乘基取整法:“乘基取整，先整為高（位），后整為低（位）”〖例2-4〗（0.625）10＝（0.101）2

20.6250.251.250.521.021整數(shù)10×××7十進(jìn)制小數(shù)轉(zhuǎn)換為非十進(jìn)制小數(shù)

十進(jìn)制小數(shù)并不是都能夠用有限位的其他進(jìn)制數(shù)精確地表示,這時(shí)應(yīng)根據(jù)精度要求轉(zhuǎn)換到一定的位數(shù)為止，作為其近似值如果一個(gè)十進(jìn)制數(shù)既有整數(shù)部分，又有小數(shù)部分，則應(yīng)將整數(shù)部分和小數(shù)部分分別進(jìn)行轉(zhuǎn)換8十進(jìn)制小數(shù)轉(zhuǎn)換為非十進(jìn)制小數(shù)(續(xù))〖例2-5〗（0.32）10＝（0.0101…）2

20.320.641.2820.5620整數(shù)01×××0.282×1.121…9非十進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)位權(quán)法：把各非十進(jìn)制數(shù)按權(quán)展開(kāi)，然后求和

〖例2-7〗（10110）2＝1×24＋0×23＋1×22＋1×21＋0×20

＝16＋0＋4＋2＋0＝（22）10

〖例2-8〗（10101.1011）2＝1×24＋0×23＋1×22＋0×21＋1×20＋1×2-1+0×2－2＋1×2－3＝16＋0＋4＋0＋1＋0.5＋0＋0.125＝（21.625）10

〖例2-9〗（1207）8＝1×83＋2×82＋0×81＋7×80＝512＋128＋0＋7＝（647）10

〖例2-10〗（1B2E）16＝1×163＋B×162＋2×161＋E×160

＝1×4096＋11×256＋2×16＋14×1＝（6958）10

10二進(jìn)制與八進(jìn)制之間的轉(zhuǎn)換二進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)：以小數(shù)點(diǎn)為界，將整數(shù)部分自右向左和小數(shù)部分自左向右分別按每三位為一組（不足三位用0補(bǔ)足），然后將各個(gè)三位二進(jìn)制數(shù)轉(zhuǎn)換為對(duì)應(yīng)的一位八進(jìn)制數(shù)八進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)：把每一位八進(jìn)制數(shù)轉(zhuǎn)換為對(duì)應(yīng)的三位二進(jìn)制數(shù)

〖例2-11〗（10111001010.1011011）2＝（010111001010.101101100）2＝（2712.554）8

〖例2-12〗（456.174）8＝（100101110.001111100）2＝（100101110.0011111）2

11二進(jìn)制與十六進(jìn)制之間的轉(zhuǎn)換

二進(jìn)制數(shù)轉(zhuǎn)換為十六進(jìn)制數(shù)：以小數(shù)點(diǎn)為界，將整數(shù)部分自右向左和小數(shù)部分自左向右分別按每四位為一組，不足四位用0補(bǔ)足，然后將各個(gè)四位二進(jìn)制數(shù)轉(zhuǎn)換為對(duì)應(yīng)的一位十六進(jìn)制數(shù)十六進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)：把每一位十六進(jìn)制數(shù)轉(zhuǎn)換為對(duì)應(yīng)的四位二進(jìn)制數(shù)

〖例2-13〗（10111001010.1011011）2＝（010111001010.10110110）2

＝（5CA.B6）16

〖例2-14〗（1A9F.1BD）16＝（0001101010011111.000110111101）2

＝（1101010011111.000110111101）2

12碼制原碼表示法：用符號(hào)位和數(shù)值表示帶符號(hào)數(shù)，正數(shù)的符號(hào)位用“0”表示，負(fù)數(shù)的符號(hào)位用“1”表示，數(shù)值部分用二進(jìn)制形式表示反碼表示法：正數(shù)的反碼與原碼相同，負(fù)數(shù)的反碼為對(duì)該數(shù)的原碼除符號(hào)位外各位取反補(bǔ)碼表示法：正數(shù)的補(bǔ)碼與原碼相同，負(fù)數(shù)的補(bǔ)碼為對(duì)該數(shù)的原碼除符號(hào)位外各位取反，然后在最后一位加1數(shù)的原碼表示適合于進(jìn)行乘除運(yùn)算；補(bǔ)碼用于進(jìn)行加減運(yùn)算

13定點(diǎn)小數(shù)格式

定點(diǎn)小數(shù)格式：把小數(shù)點(diǎn)固定在數(shù)值部分最高位的左邊

數(shù)的范圍：二進(jìn)制的（m+1）位定點(diǎn)小數(shù)格式的數(shù)N，所能表示的數(shù)的范圍為｜N｜≤1－2-m比例因子：對(duì)于絕對(duì)值大于1的數(shù)，如果直接使用定點(diǎn)小數(shù)格式將會(huì)產(chǎn)生“溢出”，需根據(jù)實(shí)際需要使用一個(gè)比例因子，將原始數(shù)據(jù)按該比例縮小，以定點(diǎn)小數(shù)格式表示，得出結(jié)果后再按該比例擴(kuò)大得到實(shí)際的結(jié)果N0NnNn-1……N1.符號(hào)位數(shù)值部分小數(shù)點(diǎn)14定點(diǎn)整數(shù)格式

定點(diǎn)整數(shù)格式：把小數(shù)點(diǎn)固定在數(shù)值部分最低位的右邊數(shù)的范圍：二進(jìn)制的（m+1）位定點(diǎn)整數(shù)格式的數(shù)N，所能表示的數(shù)的范圍為｜N｜≤2m－1比例因子：對(duì)于絕對(duì)值大于該范圍的數(shù)，如果直接使用定點(diǎn)小數(shù)格式也將會(huì)產(chǎn)生“溢出”，需根據(jù)實(shí)際需要選擇一個(gè)比例因子進(jìn)行調(diào)整，使所表示的數(shù)據(jù)在規(guī)定的范圍之內(nèi)N0N-1N-2……N-m.符號(hào)位數(shù)值部分小數(shù)點(diǎn)15浮點(diǎn)表示法浮點(diǎn)表示法：小數(shù)點(diǎn)的位置不固定，一個(gè)浮點(diǎn)數(shù)分為階碼和尾數(shù)兩部分階碼：用于表示小數(shù)點(diǎn)在該數(shù)中的位置，是一個(gè)整數(shù)尾數(shù)：用于表示數(shù)的有效數(shù)值，可以采用整數(shù)或純小數(shù)兩種形式可供選擇的一種位數(shù)分配形式：設(shè)字長(zhǎng)為32位規(guī)格化的浮點(diǎn)數(shù)：為了提高浮點(diǎn)數(shù)表示的精度通常規(guī)定其尾數(shù)的最高位必須是非零的有效位，稱為浮點(diǎn)數(shù)的規(guī)格化形式

符號(hào)位尾數(shù)部分階碼部分1位8位23位16BCD碼與ASCII碼BCD碼：是一種二－十進(jìn)制的編碼，即使用四位二進(jìn)制數(shù)表示一位十進(jìn)制數(shù)十進(jìn)制數(shù)與BCD碼之間的轉(zhuǎn)換：可以按位（或四位二進(jìn)制數(shù)組）直接進(jìn)行ASCII（AmericanStandardsCommitteeofInformation）碼：是由美國(guó)信息交換標(biāo)準(zhǔn)委員會(huì)制定的、國(guó)際上使用最廣泛的字符編碼方案ASCII碼的編碼方案：采用7位二進(jìn)制數(shù)表示一個(gè)字符，把7位二進(jìn)制數(shù)分為高三位（b7b6b5）和低四位（b4b3b2b1）。7位ASCII編碼表：利用該表可以查找數(shù)字、運(yùn)算符、標(biāo)點(diǎn)符號(hào)以及控制符等字符與ASCII碼之間的對(duì)應(yīng)關(guān)系

17漢字編碼體系漢字輸入碼：由輸入設(shè)備產(chǎn)生的漢字編碼，如區(qū)位碼、國(guó)標(biāo)碼、拼音碼、新全拼、新雙拼、五筆字型碼、簡(jiǎn)碼、表形碼、自然碼智能ABC漢字輸入碼等漢字內(nèi)碼：用于計(jì)算機(jī)內(nèi)部存儲(chǔ)和處理的漢字編碼，通常是由該漢字的國(guó)標(biāo)碼的兩個(gè)字節(jié)（最高位置“1”）形成的漢字字形碼：是確定一個(gè)漢字字形點(diǎn)陣的編碼，用于漢字顯示和打印輸出。保留在存儲(chǔ)介質(zhì)中的全部漢字字形碼稱為字庫(kù)漢字交換碼：用于在不同的漢字信息處理系統(tǒng)之間或與其他計(jì)算機(jī)系統(tǒng)之間進(jìn)行信息交換漢字地址碼：表示漢字字形信息在漢字庫(kù)中的地址，用于在漢字庫(kù)中查找漢字字形信息的漢字地址碼等

18數(shù)據(jù)校驗(yàn)碼奇偶校驗(yàn)碼：在表示數(shù)據(jù)的N位代碼中增加一位奇偶校驗(yàn)位，使N＋1位中“1”的個(gè)數(shù)為奇數(shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）海明校驗(yàn)碼：在有效信息代碼中增加校驗(yàn)位，用來(lái)校驗(yàn)代碼中“1”的個(gè)數(shù)是奇數(shù)（奇校驗(yàn)）還是偶數(shù)（偶校驗(yàn)），通過(guò)奇偶校驗(yàn)可以發(fā)現(xiàn)代碼傳輸過(guò)程中的錯(cuò)誤并自動(dòng)校正應(yīng)用：數(shù)據(jù)校驗(yàn)碼用于計(jì)算機(jī)各部件之間信息傳輸以及計(jì)算機(jī)網(wǎng)絡(luò)的信息傳輸

19命題命題：一個(gè)有具體意義且能夠判斷真假的陳述句命題的真值：命題所具有的值“真”（true，簡(jiǎn)記為T）或“假”（false,簡(jiǎn)記為F）稱為其真值命題標(biāo)識(shí)符：表示命題的符號(hào)，該標(biāo)識(shí)符稱為命題常量原子命題：不能分解為更為簡(jiǎn)單的陳述句的命題復(fù)合命題：將原子命題用連接詞和標(biāo)點(diǎn)符號(hào)復(fù)合而成的命題

20“與”（∧）

“與”（∧）:兩個(gè)命題A和B的“與”（又稱為A和B的“合取”）是一個(gè)復(fù)合命題，記為A∧B。當(dāng)且僅當(dāng)A和B同時(shí)為真時(shí)A∧B為真，在其他的情況下A∧B的真值均為假A∧B的真值表:

ABA∧BTTTTFFFTFFFF21“或”（∨）

“或”（∨）：兩個(gè)命題A和B的“或”（又稱為A和B的“析取”）是一個(gè)復(fù)合命題，記為A∨B。當(dāng)且僅當(dāng)A和B同時(shí)為假時(shí)A∨B為假，在其他的情況下A∨B的真值均為真A∨B的真值表：

ABA∨BTTTTFTFTTFFF22“非”（┑）

“非”（┑）：命題A的“非”（又稱為A的“否定”）是一個(gè)復(fù)合命題，記為┑A(chǔ)。若A為真，則┑A(chǔ)為假；若A為假，則┑A(chǔ)為真┑A(chǔ)的真值表：

A┑A(chǔ)TFFT23“異或”（⊕）

“異或”（⊕）：兩個(gè)命題的A和B的“異或”（又稱為A和B的“不可兼或”）是一個(gè)復(fù)合命題，記為A⊕B。當(dāng)且僅當(dāng)A和B同時(shí)為真或者同時(shí)為假時(shí)A⊕B為假，在其他的情況下A⊕B的真值為真A⊕B的真值表：

ABA⊕BTTFTFTFTTFFF24“條件”（→）

“條件”（→）：兩個(gè)命題的A和B的“條件”是一個(gè)復(fù)合命題，記為A→B，讀作“如果A，則B”。當(dāng)且僅當(dāng)A的真值為真，B的真值為假時(shí)，A→B為假，在其他的情況下A→B的真值均為真A→B的真值表：

ABA→BTTTTFFFTTFFT25“雙條件”()

“雙條件”()：兩個(gè)命題的A和B的“雙條件”（又稱為A當(dāng)且僅當(dāng)B）是一個(gè)復(fù)合命題，讀作“A當(dāng)且僅當(dāng)B”，記為AB，。當(dāng)且僅當(dāng)A的真值與B的真值相同時(shí)，AB為真，否則AB的真值均為假AB的真值表：

ABABTTTTFFFTFFFT26命題公式命題公式：由命題變?cè)?、連接詞和括號(hào)組成的合式的式子稱為命題公式命題公式等價(jià)：如果兩個(gè)不同的命題公式P和Q，無(wú)論其命題變?cè)∈裁粗邓鼈兊恼嬷刀枷嗤?，則稱該兩個(gè)命題公式等價(jià)，記為P＝Q

〖例2-25〗證明┑（A→B）與A∧┑B是等價(jià)的

AB┑（A→B）

A∧┑B

TTFFTFTTFTFFFFFF27命題公式的等價(jià)律其中A、B、C等為命題變?cè)?，T表示“真”，F(xiàn)表示“假”零律：A∨F＝A；A∧F＝F 幺律：A∨T＝T；A∧T＝A冪等律：A∨A＝A；A∧A＝A 求補(bǔ)律：A∨┓A＝T；A∧┓A＝F交換律：A∨B＝B∨A；A∧B＝B∧A結(jié)合律：A∨（B∨C）＝（A∨B）∨C； A∧（B∧C）＝（A∧B）∧C分配律：A∧（B∨C）＝A∧B∨A∧C； A∨B∧C＝（A∨B）∧（A∨C）吸收律：A∧B∨A∧┓B＝A；（A∨B）∧（A∨┓B）＝A 狄－摩根定律：┓（A∨B）＝┓A∧┓B；┓（A∧B）＝┓A∨┓B雙重否定律：┓┓A＝A28證明狄－摩根定律〖例2-26〗證明狄－摩根定律之一： ┓（A∧B）＝┓A∨┓BAB（A∧B）┓（A∧B）┓A

┓B

┓A∨┓B

TTTFFFFTFFTFTTFTFTTFTFFFTTTT29邏輯代數(shù)等價(jià)律零律：A＋0＝A；A0＝0 幺律：A＋1＝1；A1＝A冪等律：A＋A＝A；AA＝A求補(bǔ)律：A＋A＝1；AA＝0交換律：A＋B＝B＋A； AB＝BA結(jié)合律：A＋（B＋C）＝（A＋B）＋C A（BC）＝（AB）C分配律：A（B＋C）＝AB＋AC A＋BC＝（A＋B）（A＋C）吸收律：AB＋AB＝A；（A＋B）（A＋B）＝A 狄－摩根定律：（A＋B）＝AB；（AB）＝A＋B雙重否定律：

A＝A

30邏輯函數(shù)的化簡(jiǎn)〖例2-27〗試將邏輯函數(shù)F＝A＋AB化簡(jiǎn)

解：F ＝A＋AB ＝（A＋A）(A＋B) （分配律） ＝1(A＋B) （求補(bǔ)律） ＝A＋B （幺律）〖例2-28〗試將邏輯函數(shù)F＝AB＋AB＋AB＋AB化簡(jiǎn)。解：F ＝AB＋AB＋AB＋AB ＝A（B＋B）＋A（B＋B） （分配律） ＝A＋A

（求補(bǔ)律） ＝1 （求補(bǔ)律）31計(jì)算機(jī)硬件的基本結(jié)構(gòu)輸入設(shè)備內(nèi)存儲(chǔ)器輔助存儲(chǔ)器控制器運(yùn)算器輸出設(shè)備程序原始數(shù)據(jù)運(yùn)算結(jié)果數(shù)據(jù)控制32運(yùn)算器運(yùn)算器：對(duì)二進(jìn)制數(shù)進(jìn)行運(yùn)算的部件。它在控制器的控制下執(zhí)行程序中的指令，完成各種算術(shù)運(yùn)算、邏輯運(yùn)算、比較運(yùn)算、移位運(yùn)算以及字符運(yùn)算等運(yùn)算器的組成：算術(shù)邏輯部件（ALU）完成加、減、乘、除等四則運(yùn)算以及與、或、非、移位等邏輯運(yùn)算；寄存器用來(lái)暫存參加運(yùn)算的操作數(shù)或中間結(jié)果，常用的寄存器有累加寄存器、暫存寄存器、標(biāo)志寄存器和