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

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

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

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

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

二進(jì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等符號來表示數(shù)值的，且采用“逢八進(jìn)一”的進(jìn)位計數(shù)制十六進(jìn)制：使用數(shù)字0、1、2、3、4、5、6、7、8、9和A、B、C、D、E、F等符號來表示數(shù)值，其中A、B、C、D、E、F分別表示數(shù)字10、11、12、13、14、15。十六進(jìn)制的計數(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ù)精確地表示,這時應(yīng)根據(jù)精度要求轉(zhuǎn)換到一定的位數(shù)為止，作為其近似值如果一個十進(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)展開，然后求和

〖例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ù)點為界，將整數(shù)部分自右向左和小數(shù)部分自左向右分別按每三位為一組（不足三位用0補足），然后將各個三位二進(jìn)制數(shù)轉(zhuǎn)換為對應(yīng)的一位八進(jìn)制數(shù)八進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)：把每一位八進(jìn)制數(shù)轉(zhuǎn)換為對應(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ù)點為界，將整數(shù)部分自右向左和小數(shù)部分自左向右分別按每四位為一組，不足四位用0補足，然后將各個四位二進(jìn)制數(shù)轉(zhuǎn)換為對應(yīng)的一位十六進(jìn)制數(shù)十六進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)：把每一位十六進(jìn)制數(shù)轉(zhuǎn)換為對應(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碼制原碼表示法：用符號位和數(shù)值表示帶符號數(shù)，正數(shù)的符號位用“0”表示，負(fù)數(shù)的符號位用“1”表示，數(shù)值部分用二進(jìn)制形式表示反碼表示法：正數(shù)的反碼與原碼相同，負(fù)數(shù)的反碼為對該數(shù)的原碼除符號位外各位取反補碼表示法：正數(shù)的補碼與原碼相同，負(fù)數(shù)的補碼為對該數(shù)的原碼除符號位外各位取反，然后在最后一位加1數(shù)的原碼表示適合于進(jìn)行乘除運算；補碼用于進(jìn)行加減運算

13定點小數(shù)格式

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

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

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

符號位尾數(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）碼：是由美國信息交換標(biāo)準(zhǔn)委員會制定的、國際上使用最廣泛的字符編碼方案ASCII碼的編碼方案：采用7位二進(jìn)制數(shù)表示一個字符，把7位二進(jìn)制數(shù)分為高三位（b7b6b5）和低四位（b4b3b2b1）。7位ASCII編碼表：利用該表可以查找數(shù)字、運算符、標(biāo)點符號以及控制符等字符與ASCII碼之間的對應(yīng)關(guān)系

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

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

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

20“與”（∧）

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

ABA∧BTTTTFFFTFFFF21“或”（∨）

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

ABA∨BTTTTFTFTTFFF22“非”（┑）

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

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

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

ABA⊕BTTFTFTFTTFFF24“條件”（→）

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

ABA→BTTTTFFFTTFFT25“雙條件”()

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

ABABTTTTFFFTFFFT26命題公式命題公式：由命題變元、連接詞和括號組成的合式的式子稱為命題公式命題公式等價：如果兩個不同的命題公式P和Q，無論其命題變元取什么值它們的真值都相同，則稱該兩個命題公式等價，記為P＝Q

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

AB┑（A→B）

A∧┑B

TTFFTFTTFTFFFFFF27命題公式的等價律其中A、B、C等為命題變元，T表示“真”，F(xiàn)表示“假”零律：A∨F＝A；A∧F＝F 幺律：A∨T＝T；A∧T＝A冪等律：A∨A＝A；A∧A＝A 求補律：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ù)等價律零律：A＋0＝A；A0＝0 幺律：A＋1＝1；A1＝A冪等律：A＋A＝A；AA＝A求補律：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ù)的化簡〖例2-27〗試將邏輯函數(shù)F＝A＋AB化簡

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

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