计算机科学技术导论教程第2章

计算机科学技术的基础知识

内容提要：计算机的运算基础命题逻辑与逻辑代数基础计算机的基本结构与工作原理程序设计基础算法基础数据结构基础要求：通过本章的学习，应掌握数制间的转换方法以及数据在计算机内部的表示形式，理解逻辑代数、计算机的工作原理、程序设计以及算法与数据结构的基本知识，为学习本书的以下各章和后续课程打好基础

1数制十进制：是使用数字1、2、…、9、0等符号来表示数值且采用“逢十进一”的进位计数制位权表示法数制的特点：数字的总个数等于基数。如十进制使用10个数字（0～9）最大的数字比基数小1。如十进制中最大的数字为9每个数字都要乘以基数的幂次，该幂次由每个数字所在的位置决定任何一个N进制数A＝AnAn－1…A1A0.A－1A－2…A－m2二进制二进制：使用数字0和1等符号来表示数值且采用“逢二进一”的进位计数制二进制数制的特点：

仅使用0和1两个数字最大的数字为1，最小的数字为0每个数字都要乘以基数2的幂次，该幂次由每个数字所在的位置决定

二进制加法和乘法运算规则：

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

3八进制与十六进制八进制：使用数字0、1、2、3、4、5、6、7等符号来表示数值的，且采用“逢八进一”的进位计数制十六进制：使用数字0、1、2、3、4、5、6、7、8、9和A、B、C、D、E、F等符号来表示数值，其中A、B、C、D、E、F分别表示数字10、11、12、13、14、15。十六进制的计数方法为“逢十六进一”

4十进制整数转换为非十进制整数

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

2222221551276130131110余数5十进制整数转换为非十进制整数（续）〖例2-2,例2-3〗（55）10=（67）8=（37）16886555516166703703余数余数6十进制小数转换为非十进制小数

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

20.6250.251.250.521.021整数10×××7十进制小数转换为非十进制小数

十进制小数并不是都能够用有限位的其他进制数精确地表示,这时应根据精度要求转换到一定的位数为止，作为其近似值如果一个十进制数既有整数部分，又有小数部分，则应将整数部分和小数部分分别进行转换8十进制小数转换为非十进制小数(续)〖例2-5〗（0.32）10＝（0.0101…）2

20.320.641.2820.5620整数01×××0.282×1.121…9非十进制数转换为十进制数位权法：把各非十进制数按权展开，然后求和

〖例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二进制与八进制之间的转换二进制数转换为八进制数：以小数点为界，将整数部分自右向左和小数部分自左向右分别按每三位为一组（不足三位用0补足），然后将各个三位二进制数转换为对应的一位八进制数八进制数转换为二进制数：把每一位八进制数转换为对应的三位二进制数

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

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

11二进制与十六进制之间的转换

二进制数转换为十六进制数：以小数点为界，将整数部分自右向左和小数部分自左向右分别按每四位为一组，不足四位用0补足，然后将各个四位二进制数转换为对应的一位十六进制数十六进制数转换为二进制数：把每一位十六进制数转换为对应的四位二进制数

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

＝（5CA.B6）16

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

＝（1101010011111.000110111101）2

12码制原码表示法：用符号位和数值表示带符号数，正数的符号位用“0”表示，负数的符号位用“1”表示，数值部分用二进制形式表示反码表示法：正数的反码与原码相同，负数的反码为对该数的原码除符号位外各位取反补码表示法：正数的补码与原码相同，负数的补码为对该数的原码除符号位外各位取反，然后在最后一位加1数的原码表示适合于进行乘除运算；补码用于进行加减运算

13定点小数格式

定点小数格式：把小数点固定在数值部分最高位的左边

数的范围：二进制的（m+1）位定点小数格式的数N，所能表示的数的范围为｜N｜≤1－2-m比例因子：对于绝对值大于1的数，如果直接使用定点小数格式将会产生“溢出”，需根据实际需要使用一个比例因子，将原始数据按该比例缩小，以定点小数格式表示，得出结果后再按该比例扩大得到实际的结果N0NnNn-1……N1.符号位数值部分小数点14定点整数格式

定点整数格式：把小数点固定在数值部分最低位的右边数的范围：二进制的（m+1）位定点整数格式的数N，所能表示的数的范围为｜N｜≤2m－1比例因子：对于绝对值大于该范围的数，如果直接使用定点小数格式也将会产生“溢出”，需根据实际需要选择一个比例因子进行调整，使所表示的数据在规定的范围之内N0N-1N-2……N-m.符号位数值部分小数点15浮点表示法浮点表示法：小数点的位置不固定，一个浮点数分为阶码和尾数两部分阶码：用于表示小数点在该数中的位置，是一个整数尾数：用于表示数的有效数值，可以采用整数或纯小数两种形式可供选择的一种位数分配形式：设字长为32位规格化的浮点数：为了提高浮点数表示的精度通常规定其尾数的最高位必须是非零的有效位，称为浮点数的规格化形式

符号位尾数部分阶码部分1位8位23位16BCD码与ASCII码BCD码：是一种二－十进制的编码，即使用四位二进制数表示一位十进制数十进制数与BCD码之间的转换：可以按位（或四位二进制数组）直接进行ASCII（AmericanStandardsCommitteeofInformation）码：是由美国信息交换标准委员会制定的、国际上使用最广泛的字符编码方案ASCII码的编码方案：采用7位二进制数表示一个字符，把7位二进制数分为高三位（b7b6b5）和低四位（b4b3b2b1）。7位ASCII编码表：利用该表可以查找数字、运算符、标点符号以及控制符等字符与ASCII码之间的对应关系

17汉字编码体系汉字输入码：由输入设备产生的汉字编码，如区位码、国标码、拼音码、新全拼、新双拼、五笔字型码、简码、表形码、自然码智能ABC汉字输入码等汉字内码：用于计算机内部存储和处理的汉字编码，通常是由该汉字的国标码的两个字节（最高位置“1”）形成的汉字字形码：是确定一个汉字字形点阵的编码，用于汉字显示和打印输出。保留在存储介质中的全部汉字字形码称为字库汉字交换码：用于在不同的汉字信息处理系统之间或与其他计算机系统之间进行信息交换汉字地址码：表示汉字字形信息在汉字库中的地址，用于在汉字库中查找汉字字形信息的汉字地址码等

18数据校验码奇偶校验码：在表示数据的N位代码中增加一位奇偶校验位，使N＋1位中“1”的个数为奇数（奇校验）或偶数（偶校验）海明校验码：在有效信息代码中增加校验位，用来校验代码中“1”的个数是奇数（奇校验）还是偶数（偶校验），通过奇偶校验可以发现代码传输过程中的错误并自动校正应用：数据校验码用于计算机各部件之间信息传输以及计算机网络的信息传输

19命题命题：一个有具体意义且能够判断真假的陈述句命题的真值：命题所具有的值“真”（true，简记为T）或“假”（false,简记为F）称为其真值命题标识符：表示命题的符号，该标识符称为命题常量原子命题：不能分解为更为简单的陈述句的命题复合命题：将原子命题用连接词和标点符号复合而成的命题

20“与”（∧）

“与”（∧）:两个命题A和B的“与”（又称为A和B的“合取”）是一个复合命题，记为A∧B。当且仅当A和B同时为真时A∧B为真，在其他的情况下A∧B的真值均为假A∧B的真值表:

ABA∧BTTTTFFFTFFFF21“或”（∨）

“或”（∨）：两个命题A和B的“或”（又称为A和B的“析取”）是一个复合命题，记为A∨B。当且仅当A和B同时为假时A∨B为假，在其他的情况下A∨B的真值均为真A∨B的真值表：

ABA∨BTTTTFTFTTFFF22“非”（┑）

“非”（┑）：命题A的“非”（又称为A的“否定”）是一个复合命题，记为┑A。若A为真，则┑A为假；若A为假，则┑A为真┑A的真值表：

A┑ATFFT23“异或”（⊕）

“异或”（⊕）：两个命题的A和B的“异或”（又称为A和B的“不可兼或”）是一个复合命题，记为A⊕B。当且仅当A和B同时为真或者同时为假时A⊕B为假，在其他的情况下A⊕B的真值为真A⊕B的真值表：

ABA⊕BTTFTFTFTTFFF24“条件”（→）

“条件”（→）：两个命题的A和B的“条件”是一个复合命题，记为A→B，读作“如果A，则B”。当且仅当A的真值为真，B的真值为假时，A→B为假，在其他的情况下A→B的真值均为真A→B的真值表：

ABA→BTTTTFFFTTFFT25“双条件”()

“双条件”()：两个命题的A和B的“双条件”（又称为A当且仅当B）是一个复合命题，读作“A当且仅当B”，记为AB，。当且仅当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表示“假”零律：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结合律：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逻辑代数等价律零律：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结合律：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逻辑函数的化简〖例2-27〗试将逻辑函数F＝A＋AB化简

解：F ＝A＋AB ＝（A＋A）(A＋B) （分配律） ＝1(A＋B) （求补律） ＝A＋B （幺律）〖例2-28〗试将逻辑函数F＝AB＋AB＋AB＋AB化简。解：F ＝AB＋AB＋AB＋AB ＝A（B＋B）＋A（B＋B） （分配律） ＝A＋A

（求补律） ＝1 （求补律）31计算机硬件的基本结构输入设备内存储器辅助存储器控制器运算器输出设备程序原始数据运算结果数据控制32运算器运算器：对二进制数进行运算的部件。它在控制器的控制下执行程序中的指令，完成各种算术运算、逻辑运算、比较运算、移位运算以及字符运算等运算器的组成：算术逻辑部件（ALU）完成加、减、乘、除等四则运算以及与、或、非、移位等逻辑运算；寄存器用来暂存参加运算的操作数或中间结果，常用的寄存器有累加寄存器、暂存寄存器、标志寄存器和