讲义4代数和逻辑运算.ppt

Chapter 4,位 运算,After reading this chapter, the reader should be able to:,OBJECTIVES,掌握数据的比特运算； 掌握数据的逻辑运算； 理解逻辑运算的应用：掩模；,Figure 4-1,Operations on bits,位运算,逻辑运算,算数运算,ARITHMETIC OPERATIONS 算术运算,4.1,4.1.1 整数的算术运算,我们只研究加减，乘除可以在软件中通过连加，连减实现。 计算机中数据存储采用二进制补码形式，故我们研究二进制补码的加减运算。 1. 二进制补码中的加法 类似于十进制：列与列相加，如果有进位，就加到下一列上。,二进制数的算术运算 1、加减法 规则： 0+0= 0 ， 0+1=1， 1+0 =1 ，1+1= 0（进位1） 0-0= 0 ， 1-0 =1 ，1-1= 0 ，0-1=1 （有借位） 例： 11000100 11000100 +00100101 - 00100101 11101001 10011111,二进制补码中两个整数相加法则 两个位相加，将进位加到下一列。如果最左边的列相加后还有进位，则舍弃它。,Note:,Example 1,用二进制补码表示法将两个数相加: (+17) + (+22) (+39),Solution,Carry 进位 1 0 0 0 1 0 0 0 1 + 0 0 0 1 0 1 1 0 - Result 0 0 1 0 0 1 1 1 39,Example 2,用二进制补码表示法将两个数相加: (+24) + (-17) (+7),Solution,Carry 1 1 1 1 1 0 0 0 1 1 0 0 0 + 1 1 1 0 1 1 1 1 - Result 0 0 0 0 0 1 1 1 +7,Example 3,用二进制补码表示法将两个数相加: (-35) + (+20) (-15),Solution,Carry 1 1 1 1 1 0 1 1 1 0 1 + 0 0 0 1 0 1 0 0 - Result 1 1 1 1 0 0 0 1 -15,Example 4,用二进制补码表示法将两个数相加: (+127) + (+3) (+130),Solution,Carry 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 + 0 0 0 0 0 0 1 1 - Result 1 0 0 0 0 0 1 0 -126 (Error) An overflow has occurred. 出现溢出,在此例中，8位数据空间从-128到127，相加的结果为130不在这个区间内。为什么结果是-126?参照图4.2就会得到答案,二进制补码形式的数的表示区间 - (2N-1) - 0 - +(2N-1 1),Note:,Figure 4-2,Twos complement numbers visualization 二进制补码数示意图,当在计算机上进行算术运算时，切记运算数和结果在位分配定义的区间内。,Note:,2.二进制减法 减法与加法没什么区别，只是减数当作负数处理。,Example 5,用二进制补码表示法将两个数相减101-62: (+101) - (+62) (+101) + (-62),Solution,Carry 1 1 0 1 1 0 0 1 0 1 + 1 1 0 0 0 0 1 0 - Result 0 0 1 0 0 1 1 1 39 The leftmost carry is discarded.,LOGICAL OPERATIONS 逻辑运算,4.2,命题,命题：有具体意义且能够判断真假的陈述句。 命题的真值:命题所具有的值“真”(true，简记为T)或“假”（false,简记为F）称为其真值。 命题标识符：表示命题的符号，该标识符称为命题常量。 原子命题：不能分解为更为简单的陈述句的命题； 复合命题：将原子命题用连接词和标点符号复合而成的命题。,连接词“与”（ ） “与”( ):两个命题A和B的“与”(又称为A和B的“合取”)是一个复合命题，记为AB。当且仅当A和B同时为真时AB为真，在其他的情况下AB的真值均为假。 AB的真值表:,连接词 “或”（）,“或”（）：两个命题A和B的“或”（又称为A和B的“析取”）是一个复合命题，记为AB。当且仅当A和B同时为假时AB为假，在其他的情况下AB的真值均为真。 AB的真值表：,连接词“非”（）,“非”（）：命题A的“非”（又称为A的“否定”）是一个复合命题，记为 A。若A为真，则A为假；若A为假，则A为真。 A的真值表：,连接词 “异或”（）,“异或” （）：两个命题的A和B的“异或”（又称为A和B的“不可兼或”）是一个复合命题，记为AB。当且仅当A和B同时为真或者同时为假时AB为假，在其他的情况下AB的真值为真。 AB的真值表：,连接词“条件”（ ）,“条件”（ ）：两个命题的A和B的“条件”是一个复合命题，记为 AB,读作“如果A，则B”。 当且仅当A的真值为真，B的真值为假时，AB为假，在其他的情况下AB的真值均为真。 AB的真值表：,“双条件”( ):两个命题的A和B的“双条件”（又称为A当且仅当B）是一个复合命题，记为A B，读作“A当且仅当B”。 当且仅当A的真值与B的真值相同时， A B为真，否则A B的真值均为假。 A B的真值表：,连接词 “双条件”( ),命题公式,命题公式： 由命题变元、连接词和括号组成的合式的式子称为命题公式。 命题公式等价：如果两个不同的命题公式P和Q，无论其命题变元取什么值它们的真值都相同，则称该两个命题公式等价，记为PQ。 例2-25证明 （AB）与AB是等价的。,命题公式的等价律,其中A、B、C等为命题变元，T表示“真”，F表示“假” 零律： AFA AFF 幺律： ATT A TA 幂等律：AAA A AA 求补律：AAT AAF 交换律：ABBA ABBA,命题公式的等价律（续）,结合律： A（BC）（AB）C A（BC）（AB）C 分配律： A（BC）ABAC ABC（AB）（AC） 吸收律： ABABA （AB）（AB）A 狄摩根定律：（AB）AB （AB）AB 双重否定律： AA,证明狄摩根定律,例2-26证明狄摩根定律之一：（AB）AB。,逻辑代数的等价律,零律： A0A A 00 幺律： A11 A 1A 幂等律：AAA A AA 求补律：A 1 A 0,逻辑代数的等价律(2),逻辑函数的化简,掩码,一个二进制位模式可通过与另一个位模式进行与、或以及异或运算而被修改，这里的“另一个