逻辑代数基础(周林计).ppt

2010 4 都江堰校区周林 1 教学安排 数字电子技术 教学时数 总学时48学时 其中理论课时38学时 实验10学时 周数 10 17周 教学内容 第1章 第2章部份内容 第3章 第4章 第5章1 2节 推荐参考书 数字电子技术 西安电子科技大学出版社 江晓安主编 2010 4 都江堰校区周林 2 课程性质 数字电子技术 是计算机各专业及电子类专业必修的一门重要专业基础课 本课程主要介绍有关数字系统基本知识 基本理论 及常用数字集成电路 重点讨论数字逻辑电路分析方法 了解其设计的基本方法 从计算机的层次结构上讲 数字逻辑 是深入了解计算机 内核 的一门最关键的基础课程 教学目标 本课程的教学目标是使学生了解组成数字计算机和其它数字系统的各种数字电路 能熟练地运用基本知识和理论对各类电路进行分析 并能根据客观提出的设计要求用合适的集成电路芯片完成各种逻辑部件的设计 2010 4 都江堰校区周林 3 一 掌握课程特点 1 本课程是一门既抽象又具体的课程 在逻辑问题的提取和描述方面是抽象的 而在逻辑问题的实现上是具体的 因此 学习中既要有抽象分能力 又要善于结合实际 2 逻辑设计方法十分灵活 数字系统中 逻辑电路的分析与设计具有很大的灵活性 许多问题的处理没有固定的方法和步骤 很大程度上取决于操作者的逻辑思维推理能力 知识广度和深度 以及解决实际问题的能力 换而言之 逻辑电路的分析与设计具有较大的弹性和可塑性 3 理论知识与实际应用结合十分紧密 该课程各部分知识与实际应用直接相关 学习中必须将理论知识与实际问题联系起来 真正培养解决实际问题的能力 2010 4 都江堰校区周林 4 二 重视课堂学习 1 认真听课 听课时要紧跟教师授课思路 认真领会每一个知识要点 抓住书本上没有的内容 琢磨重点与难点 2 做好笔记 适当地记录某些关键内容 尤其是那些重点 难点 疑点 以便课后复习 思考 3 主动思考 听课时围绕教师所述内容及提出的问题 主动思考问题 寻找自己的见解 三 培养自学能力 1 认真阅读教材内容 2 善于总结 归纳 3 加强课后练习 2010 4 都江堰校区周林 5 第一章逻辑代数基础 1 1 基本概念 公式和定理 概述 1 3 逻辑函数的表示方法及其相互之间的转换 1 2 逻辑函数的化简方法 2010 4 都江堰校区周林 6 概述 一 数字系统 数字系统是一个能对数字信号进行加工 传递和存储的实体 它由实现各种功能的数字逻辑电路相互连接而成 例如 数字计算机 2 数字信号 例如 学生成绩记录 工厂产品统计 电路开关的状态等 信号的变化在时间上和数值上都是断续的 或离散的 对数字信号进行传输 处理的电子线路称为数字电路 模拟信号 信号随时间连续变化的量 对模拟信号进行传输 处理的电子线路称为模拟电路 1 什么是数字系统 2010 4 都江堰校区周林 7 例如 某控制系统框图如下图所示 数字系统中处理的是数字信号 当数字系统要与模拟信号发生联系时 必须经过模 数 A D 转换和数 模 D A 转换电路 对信号类型进行变换 2010 4 都江堰校区周林 8 二 数字逻辑电路 用来处理数字信号的电子线路称为数字电路 由于数字电路的各种功能是通过逻辑运算和逻辑判断来实现的 所以数字电路又称为数字逻辑电路或者逻辑电路 1 电路的基本工作信号是二值信号 它表现为电路中电压的 高 或 低 开关的 接通 或 断开 晶体管的 导通 或 截止 等两种稳定的物理状态 2 电路中的半导体器件一般都工作在开 关状态 数字逻辑电路具有如下特点 3 电路结构简单 功耗低 便于集成制造和系列化生产 产品价格低廉 使用方便 通用性好 4 由数字逻辑电路构成的数字系统工作速度快 精度高 功能强 可靠性好 2010 4 都江堰校区周林 9 三 逻辑代数 逻辑关系 事物间的因果关系逻辑代数 反映和处理这种逻辑关系的数学工具布尔代数 逻辑代数是英国数学家 GeorgeBoole 布尔在19世纪中叶创立的一门数学学科 所以又叫布尔代数开关代数 20世纪30年代美国工程师 ClaudeE Shannon 克劳德 香浓将逻辑代数运用到开关电路的分析中 因此又称为开关代数 逻辑变量 逻辑代数中的变量 用字母表示 二值逻辑 变量中取值只有 1 咱 0 两种 逻辑代数是分析和设计数字电路的基本数学工具 它的基本和常用运算也是数字电路要实现的重要操作 2010 4 都江堰校区周林 10 一 进位计数制 数制是人们对数量计数的一种统计规律 按进位的原则进行计数 称为进位计数制 日常生活中广泛使用的是十进制 而数字系统中使用的是二进制 每一种进位计数制都有一组特定的数码 例如十进制数有10个数码 二进制数只有两个数码 而十六进制数有16个数码 四数制及其转换 十进制中采用了0 1 9共十个基本数字符号 进位规律是 逢十进一 当用若干个数字符号并在一起表示一个数时 处在不同位置的数字符号 其值的含意不同 1 十进制 同一个字符6从左到右所代表的值依次为600 60 6 即 666 10 6 102 6 101 6 100 2010 4 都江堰校区周林 11 基数N 10 采用10个不同的数码0 1 2 9和一个小数点 进位规则 是 逢十进一 权 10i 再如 注 我们把十进制数的10个基本数码定义为 基数 在不同位数代表的数值大小的常数10i定义为 权 则十进数的特点可总结如下 上述十进制数的表示方法也可以推广到任意进制数 2010 4 都江堰校区周林 12 广义地说 一种进位计数制包含着基数和位权两个基本的因素 基数 指计数制中所用到的数字符号的个数 在基数为N计数制中 包含0 1 N 1共N个数字符号 进位规律是 逢N进一 称为N进位计数制 简称N进制 2 N进制 位权 是指在一种进位计数制表示的数中 用来表明不同数位上数值大小的一个固定常数 不同数位有不同的位权 某一个数位的数值等于这一位的数字符号乘上与该位对应的位权 N进制数的位权为N的整数次幂 例如 十进制数的位权是10的整数次幂 其个位的位权是100 十位的位权是101 一个N进制数D可以有两种表示方法 2010 4 都江堰校区周林 13 2 多项式表示法 又称按权展开法 D N Kn 1 Nn 1 Kn 2 Nn 2 K1 N1 K0 N0 K 1 R 1 K 2 N 2 K m N m 其中 N 基数 n 整数部分的位数 m 小数部分的位数 Ki N进制中的一个数字符号 其取值范围为0 Ki N 1 m i n 1 3 位权是N的整数次幂 第i位的权为Ni m i n 1 N进制的特点可归纳如下 1 有0 1 N 1共N个数字符号 2 逢N进一 10 表示N 2010 4 都江堰校区周林 14 基数N 2的进位计数制称为二进制 二进制数中只有0和1两个基本数字符号 进位规律是 逢二进一 二进制数的位权是2的整数次幂 任意一个二进制数D可以表示成 3 二进制 其中 n 整数位数 m 小数位数 Ki 为0或者1 m i n 1 D 2 Kn 1Kn 2 K1K0 K 1K 2 K m 2 Kn 1 2n 1 Kn 2 2n 2 K1 21 K0 20 K 1 2 1 K 2 2 2 K m 2 m 2010 4 都江堰校区周林 15 例如 一个二进制数1011 01可以表示成 1011 01 2 1 23 0 22 1 21 1 20 0 2 1 1 2 2 2010 4 都江堰校区周林 16 例如 二进制数A 11001 B 101 则A B A B A B A B的运算为 2010 4 都江堰校区周林 17 因为二进制中只有0和1两个数字符号 可以用电子器件的两种不同状态来表示一位二进制数 例如 可以用晶体管的截止和导通表示1和0 或者用电平的高和低表示1和0等 所以 在数字系统中普遍采用二进制 二进制的优点 运算简单 物理实现容易 存储和传送方便 可靠 二进制的缺点 数的位数太长且字符单调 使得书写 记忆和阅读不方便 因此 人们在进行指令书写 程序输入和输出等工作时 通常采用八进制数和十六进制数作为二进制数的缩写 2010 4 都江堰校区周林 18 4 二进制数的缩写形式 八进制和十六进制 1 八进制数 基数N 8的进位计数制称为八进制 八进制数中有0 1 7共8个基本数字符号 进位规律是 逢八进一 八进制数的位权是8的整数次幂 其中 n 整数位数 m 小数位数 Ki 0 7中的任何一个字符 m i n 1 例 37 41 8 3 81 7 80 4 8 1 1 8 2 2010 4 都江堰校区周林 19 2 十六进制 基数N 16的进位计数制称为十六进制 十六进制数中有0 1 9 A B C D E F共16个数字符号 其中 A F分别表示十进制数的10 15 进位规律为 逢十六进一 十六进制数的位权是16的整数次幂 任意一个十六进制数N可以表示成 其中 n 整数位数 m 小数位数 Ki 表示0 9 A F中的任何一个字符 m i n 1 例 2A 7F 2 161 A 160 7 16 1 F 16 2 2 16 10 1 7 16 15 256 42 4961 2010 4 都江堰校区周林 20 十进制数0 15及其对应的二进制数 八进制数 十六进制数如下表所示 2010 4 都江堰校区周林 21 二 几种常用进制数之间的转换 方法 多项式替代法 1 二进制数与十进制数之间的转换 1 二进制数转换为十进制数 二 十转换 将二进制数表示成按权展开式 并按十进制运算法则进行计算 所得结果即为该数对应的十进制数 例如 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 10 数制转换是指将一个数从一种进位制转换成另一种进位制 从实际应用出发 要求掌握二进制数与十进制数 八进制数和十六进制数之间的相互转换 2010 4 都江堰校区周林 22 方法 基数乘除法 十进制数转换成二进制数时 应对整数和小数分别进行处理 整数转换 采用 除2取余 的方法 小数转换 采用 乘2取整 的方法 2 1 整数转换 除2取余 法 将十进制整数D除以2 取余数计为K0 再将所得商除以2 取余数记为K1 依此类推 直至商为0 取余数计为Kn 1为止 即可得到与N对应的n位二进制整数Kn 1 K1K0 2 十进制数转换为二进制数 十 二转换 2010 4 都江堰校区周林 23 分析 假设某十进数为D10 对应二进制数为 Kn 1Kn 2 K1K0 则 D10 Kn 1Kn 2 K1K0 Kn 1 2n 1 Kn 2 2n 2 K1 21 K0 2 Kn 1 2n 2 Kn 2 2n 3 K1 K0 将上式两边同时除以2 两边的商和余数相等 所得的商为 Kn 1 2n 2 Kn 2 2n 3 K1 而余数为K0 同理将这个商写成 两边再同时除2 则所得之余数为K1 以此类推 就可求出对应的二进制数的第一位系数 这就叫除2取余法 用到其它进制就叫除基取余法 2010 4 都江堰校区周林 24 例如 35 10 2 0 1 K5 高位 即 35 10 100011 2 2010 4 都江堰校区周林 25 例如 0 6875 10 2 2 小数转换 乘2取整 法 将十进制小数D乘以2 取积的整数记为K 1 再将积的小数乘以2 取整数记为K 2 依此类推 直至其小数为0或达到规定精度要求 取整数记作K m为止 即可得到与D对应的m位二进制小数0 K 1K 2 K m 即 0 6875 10 0 1011 2 2010 4 都江堰校区周林 26 注意 当十进制小数不能用有限位二进制小数精确表示时 可根据精度要求 求出相应的二进制位数近似地表示 一般当要求二进制数取m位小数时 可求出m 1位 然后对最低位作0舍1入处理 即 0 323 10 0 0101 2 例如 0 323 10 2 保留4位小数 2010 4 都江堰校区周林 27 即 25 625 10 11001 101 2 若一个十进制数既包含整数部分 又包含小数部分 则需将整数部分和小数部分分别转换 然后用小数点将两部分结果连到一起 例如 25 625 10 2 2010 4 都江堰校区周林 28 2 二进制数与八进制数 十六进制数之间的转换 由于八进制的基本数字符号0 7正好和3位二进制数的取值000 111对应 所以 二进制数与八进制数之间的转换可以按位进行 1 二进制数与八进制数之间的转换 1 二进制数转换成八进制数 以小数点为界 分别往高 往低每3位为一组 最后不足3位时用0补充 然后写出每组对应的八进制字符 即为相应八进制数 例如 11100101 01 2 8 即 11100101 01 2 345 2 8 2010 4 都江堰校区周林 29 即 56 7 8 101110 111 2 例如 56 7 8 2 2 八进制数转换成二进制数时 只需将每位八进制数用3位二进制数表示 小数点位置保持不变 2010 4 都江堰校区周林 30 二进制数与十六进制数之间的转换同样可以按位进行 只不过是4位二进制数对应1位十六进制数 即4位二进制数的取值0000 1111分别对应十六进制字符0 F 2 二进制数与十六进制数之间的转换 1 二进制数转换成十六进制数 以小数点为界 分别往高 往低每4位为一组 最后不足4位时用0补充 然后写出每组对应的十六进制字符即可 例如 101110 011 2 16 即 101110 011 2 2E 6 2010 4 都江堰校区周林 31 2 十六进制数转换成二进制数时 只需将每位十六进制数用4位二进制数表示 小数点位置保持不变 例如 5A B 16 2 即 5A B 1011010 1011 2 2010 4 都江堰校区周林 32 五二进制代码 一 十进制数的二进制编码 BCD码 用4位二进制代码对十进制数字符号进行编码 简称为二 十进制代码 或称BCD BinaryCodedDecimal 码 BCD码既有二进制的形式 又有十进制的特点 常用的BCD码有8421码 2421码和余3码 用二进制数表示文字 符号等信息的过程叫做编码 用来进行编码之后的二进数数称为二进制代码 一 8421码 8421码 是用4位二进制码表示一位十进制字符的一种有权码 4位二进制码从高位至低位的权依次为23 22 21 20 即为8 4 2 1 故称为8421码 2010 4 都江堰校区周林 33 按8421码编码的0 9与用4位二进制数表示的0 9完全一样 所以 8421码是一种人机联系时广泛使用的中间形式 1 8421码中不允许出现1010 1111六种组合 因为没有十进制数字符号与其对应 2 十进制数字符号的8421码与相应ASCII码的低四位相同 这一特点有利于简化输入输出过程中BCD码与字符代码的转换 注意 8421码与十进制数之间的转换是按位进行的 即十进制数的每一位与4位二进制编码对应 3 8421码与十进制数之间的转换 258 10 001001011000 8421码 0001001000001000 8421码 1208 10 2010 4 都江堰校区周林 34 例如 28 10 11100 2 00101000 8421 2 8421码与二进制的区别 二 2421码 2421码 是用4位二进制码表示一位十进制字符的另一种有权码 4位二进制码从高位至低位的权依次为2 4 2 1 故称为2421码 若一个十进制字符X的2421码为a3a2a1a0 则该字符的值为X 2a3 4a2 2a1 1a0 例如 1101 2421码 7 10 1 2421码不具备单值性 例如 0101和1011都对应十进制数字5 为了与十进制字符一一对应 2421码不允许出现0101 1010的6种状态 2 注意 2010 4 都江堰校区周林 35 2 2421码是一种对9的自补代码 即一个数的2421码只要自身按位变反 便可得到该数对9的补数的2421码 例如 具有这一特征的BCD码可给运算带来方便 因为直接对BCD码进行运算时 可利用其对9的补数将减法运算转化为加法运算 3 应与二进制数进行区别 2010 4 都江堰校区周林 36 2 余3码与十进制数进行转换时 每位十进制数字的编码都应余3 例如 256 10 010110001001 余3码 1000100110011011 余3码 5668 10 注意 1 余3码中不允许出现0000 0001 0010 1101 1110和1111六种状态 3 余3码是一种对9的自补代码 三 余3码 余3码 是由8421码加上0011形成的一种无权码 由于它的每个字符编码比相应8421码多3 故称为余3码 例如 十进制字符5的余3码等于5的8421码0101加上0011 即为1000 2010 4 都江堰校区周林 37 十进制数字符号0 9与8421码 2421码和余3码的对应关系如下表所示 2010 4 都江堰校区周林 38 本次课小结 1 了解数字信号 数字系统的基本概念 2 了解逻辑代数的基本概念 3 熟悉和掌握进位计数制间的转换 4 熟悉常用进制代码 作业 P681 2 1 2 3 4 1 3 3 4 5 2010 4 都江堰校区周林 39 1 1基本概念 公式和定理 1 1 1逻辑变量及基本逻辑运算 1 1 2公式和定理及规则 公理和定理 若干常用公式 关于等式的三个规则 2010 4 都江堰校区周林 40 1 1 1逻辑变量及基本逻辑运算 一 变量 逻辑代数和普通代数一样 是用字母表示其值可以变化的量 即变量 所不同的是 1 在普通代数中 变量的取值可以是任意实数 而逻辑代数是一种二值代数系统 任何逻辑变量的取值只有两种可能性 取值0或取值1 2 逻辑值0和1是用来表征矛盾的双方和判断事件真伪的形式符号 无大小 正负之分 在数字系统中 开关的接通与断开 电压的高和低 信号的有和无 晶体管的导通与截止等两种稳定的物理状态 均可用1和0这两种不同的逻辑值来表征 2010 4 都江堰校区周林 41 二 基本逻辑关系和基本逻辑运算 描述一个数字系统 必须反映一个复杂系统中各开关元件之间的联系 这种相互联系反映到数学上就是几种逻辑运算关系 对应这几种逻辑关系 逻辑代数中定义了 与 或 非 三种基本运算 一 与逻辑关系及与逻辑运算 1 与逻辑关系 当决定一件事的各个条件全部具备时 这件事才会发生 这样的因果关系称之为与逻辑关系 例如 在右上图所示电路中 两个开关串联控制同一个灯 显然 仅当两个开关均闭合时 灯才能亮 否则 灯灭 这个电路就是一个与的逻辑关系 2010 4 都江堰校区周林 42 2 与 逻辑运算 分析事件的逻辑运算关系的步骤为 1 设定变量 用A B表示开关 Y表示灯 则电路中灯Y和开关A B之间的关系即可用功能表表示出来 2 状态赋值 假定开关闭合状态用1表示 断开状态用0表示 灯亮用1表示 灯灭用0表示 3 列真值表 用 穷举法 描述逻辑函数中各逻辑变量的取值组合和逻辑函数值对应关系的表格 与 逻辑关系如真值表所示 由表反映的逻辑关系可得出与逻辑的代数表达式 Y A B或者Y A B即 若A B均为1 则Y为1 否则 Y为0 在逻辑代数中 与 逻辑关系用 与 运算描述 其运算符号为 有时也用 表示 2010 4 都江堰校区周林 43 3 与 运算的运算法则 0 0 01 0 00 1 01 1 1与逻辑功能 见0得0 全1为1 数字系统中 实现 与 运算关系的逻辑电路称为 与 门 二 或 逻辑关系及或逻辑运算1 或逻辑关系 如果决定某一事件是否发生的多个条件中 只要有一个或一个以上条件成立 事件便可发生 则这种因果关系称之为 或 逻辑 例如 用两个开关并联控制一个灯的照明控制电路 可以看出 当开关S1 S2中有一个闭合或者两个均闭合时 灯H即亮 因此 灯H与开关S1 S2之间的关系是 或 逻辑关系 2010 4 都江堰校区周林 44 2 或逻辑运算 同样 假定开关断开用0表示 开关闭合用1表示 灯灭用0表示 灯亮用1表示 则灯Y与开关A B的关系如真值表所示 即 A B中只要有一个为1 则Y为1 仅当A B均为0时 Y才为0 由表可得出 Y A B或者Y A B读作 Y等于A或B 逻辑代数中 或 逻辑用 或 运算描述 其运算符号为 有时也用 表示 两变量 或 运算的关系可表示为 2010 4 都江堰校区周林 45 3 或 运算的运算法则 0 0 01 0 10 1 11 1 1或逻辑功能 见1得1 全0为0 实现 或 运算关系的逻辑电路称为 或 门 三 非 逻辑关系及 非 逻辑运算1 非 逻辑关系 如果某一事件的发生取决于条件的否定 即事件与事件发生的条件之间构成矛盾 则这种因果关系称为 非 逻辑 例如 在右图所示电路中 开关与灯并联 显然 仅当开关断开时 灯亮 一旦开关闭合 则灯灭 则电路中灯Y与开关A的关系即为 非 逻辑关系 2010 4 都江堰校区周林 46 3 非 运算的运算法则 数字系统中实现 非 运算功能的逻辑电路称为 非 门 有时又称为 反相器 2 非 逻辑运算 在逻辑代数中 非 逻辑用 非 运算描述 其运算符号为 有时也用 表示 非 运算的逻辑关系可表示为 令开关断开用0表示 开关闭合用1表示 灯亮用1表示 灯灭用0表示 则电路中灯Y与开关A的关系即为下表所示 非 运算关系 读作 Y等于A非 即 若A为0 则Y为1 若A为1 则Y为0 2010 4 都江堰校区周林 47 三 逻辑函数及几种常用复合逻辑运算 逻辑代数中函数的定义与普通代数中函数的定义类似 即是随自变量变化的因变量 但和普通代数中函数的概念相比 逻辑函数具有如下特点 1 逻辑函数和逻辑变量一样 取值只有0和1两种可能 2 函数和变量之间的关系是由 与 或 非 三种基本运算决定的 Y A B Y A B叫逻辑表达式 式中A B称为逻辑输入变量 Y为逻辑输出变量 字母上面无反号的为原变量 有反号的叫做反变量 Y A B中A B之间是与的逻辑关系 Y是A和B的与函数 而Y A B中A B之间是或逻辑关系 Y是A和B的或函数 一 逻辑函数的定义 2010 4 都江堰校区周林 48 逻辑电路输出函数的取值是由逻辑变量的取值和电路本身的结构决定的 任何一个逻辑电路的功能都可由相应的逻辑函数完全描述 因此 能够借助抽象的代数表达式对电路加以分析研究 从数字系统研究的角度看 逻辑函数的定义如下 一般说来 如果某逻辑电路的输入逻辑变量A1 A2 的取值确定之后 输出逻辑变量Y的值也被唯一地确定了 那么就称Y是A1 A2 的逻辑函数 并写成Y F A1 A2 如右图所示 2010 4 都江堰校区周林 49 逻辑函数和普通代数中的函数一样存在是否相等的问题 什么叫做两个逻辑函数相等呢 有两个相同变量的逻辑函数Y1 f1 A1 A2 An 和Y2 f2 A1 A2 An 若对应于逻辑变量A1 A2 An的任何一组取值 Y1和Y2的值都相同 则称函数Y1和Y2相等 记作Y1 Y2 如何判断两个逻辑函数是否相等 通常有两种方法 一种方法是真值表法 即两个真值表完全相同 另一种方法是代数法 两个逻辑表达式一样 2010 4 都江堰校区周林 50 二 几种常用复合逻辑运算及符号 1 与非逻辑运算 逻辑功能 见0得1 全1为0 实现与非逻辑的门电路称为 与非 门 AB 2010 4 都江堰校区周林 51 2 或非运算 3 与或非运算 逻辑功能 见1得0 全0为1 实现或非逻辑的门电路称为 或非 门 逻辑功能 仅当每一个 与项 均为0时 才能使Y为1 否则Y为0 实现与或非逻辑的门电路称为 与或非 门 AB CD A B 2010 4 都江堰校区周林 52 4 异或运算 异或是一种二变量逻辑运算 当两个变量取值相同时 逻辑函数值为0 当两个变量取值不同时 逻辑函数值为1 实现异或运算的逻辑门称为 异或门 2010 4 都江堰校区周林 53 1 逻辑代数是分析和设计数字电路的重要工具 利用逻辑代数 可以把实际逻辑问题抽象为逻辑函数来描述 并且可以用逻辑运算的方法 解决逻辑电路的分析和设计问题2 与 或 非是3种基本逻辑关系 也是3种基本逻辑运算 与非 或非 与或非 异或则是由与 或 非3种基本逻辑运算复合而成的4种常用逻辑运算 3 作业 P681 2 1 3 5 1 4 本次课小结 2010 4 都江堰校区周林 54 上次课复习 1 与运算 Y A B 2 或运算 Y A B 异或运算 2010 4 都江堰校区周林 55 1 1 2公式和定理及规则 因为二值逻辑中只有0和1两个常量 逻辑变量的取值不是0就是1 而最基本的逻辑运算又只有与 或 非三种 所以常量之间的关系也只有下面给出常用的 组 它们既是逻辑代数中的基本运算规则同 又叫公理 一 基本公式 常量之间的关系 公式10 0 0公式20 1 0公式31 1 11 1 11 0 10 0 0 公理是一个代数系统的基本出发点 无需加以证明 公式4 2010 4 都江堰校区周林 56 三 基本定律 与普通代数相似的定理对于任意逻辑变量A B C 有交换律公式8A B B A公式8 A B B A结合律公式9 A B C A B C 公式9 A B C A B C 分配律公式10A B C A B A C公式10 A B C A B A C 2010 4 都江堰校区周林 57 交换律 结合律与普通代数的相应定律在形式上完全相同 而分配律在普通代数中只有乘法对加法的分配律 公式10所示 而在逻辑代数中 还有加法对乘法的分配律 公式10 所示 为了区别 将 公式10 和 公式10 分别称为第一分配律和第二分配律 以上各个定律证明可以用真值表来进行 将各个变量分别用1和0代入等式的左右来验证 但应注意 必须考虑变量的所有可能的取值组合 例如第二分配律 可列出真值表 可见等式两边相等 原等式成立 例如证明公式10 A B C A B A C 00000 00010 00100 11111 01111 01111 01111 11111 2010 4 都江堰校区周林 58 四 逻辑代数的一些特殊定理 反演律 公式12 还原律 公式13 同一律 公式11A A AA A A 加法对乘法的分配律 2010 4 都江堰校区周林 59 公式13 A 2010 4 都江堰校区周林 60 五 关于等式的三个重要规则 逻辑代数有3条重要规则 即代入规则 反演规则和对偶规则 例如 给定逻辑等式A B C AB AC 若等式中的C都用 C D 代替 则该逻辑等式仍然成立 即A B C D AB A C D 代入规则的正确性是显然的 因为任何逻辑函数都和逻辑变量一样 只有0和1两种可能的取值 任何一个含有变量A的逻辑等式 如果将所有出现A的位置都代之以同一个逻辑函数Y 则等式仍然成立 这个规则称为代入规则 一 代入规则 2010 4 都江堰校区周林 61 代入规则的意义 利用代入规则可以将逻辑代数公理 定理中的变量用任意函数代替 从而推导出更多的等式 这些等式可直接当作公使用 无需另加证明 注意 使用代入规则时 必须将等式中所有出现同一变量的地方均以同一函数代替 否则代入后的等式将不成立 例如 若用逻辑函数Y f A1 A2 An 代替公理A 1中的变量A 便可得到等式f A1 A2 An A1 A2 An 1 即一个函数和其反函数进行 或 运算 其结果为1 2010 4 都江堰校区周林 62 二 反演规则 反演规则实际是公式12的推广 可通过公式12和代入规则得到证明 显然 运用反演规则可以很方便地求出一个函数的反函数 例如 已知函数 根据反演规则可得到 2010 4 都江堰校区周林 63 注意 使用反演规则时 应保持原函数式中运算符号的优先顺序不变 不是一个变量上的反号应保持不变 三 对偶规则 如果将逻辑函数表达式Y中所有的 变成 变成 0 变成 1 1 变成 0 变量不变 并保持原函数中的运算顺序不变 则所得到的新的逻辑表达式称为函数Y的对偶式 并记作Y 例如 例如 已知函数 根据反演规则得到的反函数应该是 而不应该是 错误 2010 4 都江堰校区周林 64 注意 如果Y的对偶式是Y 则Y 的对偶式就是Y 即 Y Y 可见Y和Y 互为对偶式 若逻辑函数表达式的对偶式就是原函数表达式本身 即Y Y 则称函数Y为自对偶函数 多次应用分配律 2010 4 都江堰校区周林 65 注意 求逻辑表达式的对偶式时 同样要保持原函数的运算顺序不变 显然 利用对偶规则可以使定理 公式的证明减少一半 若两个逻辑函数表达式Y和F相等 则其对偶式Y 和F 也相等 这一规则称为对偶规则 根据对偶规则 当已证明某两个逻辑表达式相等时 即可知道它们的对偶式也相等 例如已知AB C BC AB C 根据对偶规则对等式两端的表达式取对偶式 即可得到等式 A B C B C A B C 2010 4 都江堰校区周林 66 公式14A B A A A B A A 六 若干常用公式 合并律 公式15A A B A A A B A 吸收律1 公式15说明 在一个与或表达式中 如果一个乘积项是另一个乘积项的因子 则这另外一个乘积项是多余的 2010 4 都江堰校区周林 67 公式16 吸收律2 公式17 吸收律3 公式16说明 在一个与或表达式中 如果一个乘积项的反是另一个乘积项的因子 则这个因子是多余的 证明 2010 4 都江堰校区周林 68 公式17证明 公式17 推论 2010 4 都江堰校区周林 69 公式18 公式19 2010 4 都江堰校区周林 70 七 关于异或运算的一些公式 前面对异或运算已有了定义 其表达式为 同或逻辑与异或逻辑的关系既互为相反 又互为对偶 即有 2010 4 都江堰校区周林 71 1 交换律 A B B A2 结合律 A B C A B C 3 分配律 A B C A B A C 5 异或逻辑的因果互换关系 如果A B C则有A C BB C A 证明 A B B C BA 0 C BA B C 2010 4 都江堰校区周林 72 1 正理解代入规则 反演规则 对偶规则 2 逻辑代数的公式和定理是推演 变换及化简逻辑函数的依据 要掌握常用公式及定理 如合并公式 吸收公式 3 作业 P691 5 本次课小结 2010 4 都江堰校区周林 73 一 代入规则 二 反演规则 三 对偶规则 公式14A B A A A B A A 公式15A A B A A A B A 公式16 吸收律2 公式17 吸收律3 上次课复习 2010 4 都江堰校区周林 74 1 2逻辑函数的化简方法 化简逻辑函数 经常用到的方法有两种 一种叫做公式法化简 就是用逻辑代数中的公式定理进行化简 另一种称为图形法化简 用来进行化简的工具是卡诺图 一般地说 逻辑函数的表达式越简单 实现它的电路也越简单 经济可靠 在讲逻辑函数化简前 先介绍一下逻辑函数表达的基本形式及标准形式 实现某一逻辑功能的逻辑电路的复杂性与描述该功能的逻辑表达式的复杂性直接相关 一般说 逻辑函数表达式越简单 设计出来的相应逻辑电路也就越简单 为了降低系统成本 减小复杂度 提高可靠性 必须对逻辑函数进行化简 由于 与 或 表达式和 或 与 表达式可以很方便地转换成任何其他所要求的形式 因此 从这两种基本形式出发讨论函数化简问题 并将重点放在 与 或 表达式的化简上 2010 4 都江堰校区周林 75 一 逻辑函数表达式的两种基本形式 两种基本形式 指 与 或 表达式和 或 与 表达式 一 与 或 表达式 与 或 表达式 是指由若干 与项 进行 或 运算构成的表达式 每个 与项 可以是单个变量的原变量或者反变量 也可以由多个原变量或者反变量相 与 组成 概述 逻辑函数表达式的形式与变换 任何一个逻辑函数 其表达式的形式都不是唯一的 下面从分析与应用的角度出发 介绍逻辑函数表达式的基本形式 标准形式及其相互转换 2010 4 都江堰校区周林 76 与项 有时又被称为 积项 相应地 与 或 表达式又称为 积之和 表达式 二 或 与 表达式 或项 有时又被称为 和项 相应地 或 与 表达式又称为 和之积 表达式 或 与 表达式 是指由若干 或项 进行 与 运算构成的表达式 每个 或项 可以是单个变量的原变量或者反变量 也可以由多个原变量或者反变量相 或 组成 例如 D均为 或项 将这4个 或项 相 与 便可构成一个4变量函数的 或 与 表达式 即 2010 4 都江堰校区周林 77 该逻辑函数是 与 或 式 不是 是 或 与 式 也不是 但不论什么形式都可以变换成两种基本形式 1 2 1逻辑函数的标准与或式和最简式 逻辑函数的两种基本形式都不是唯一的 例如 为了在逻辑问题的研究中使逻辑功能能和唯一的逻辑表达式对应 引入了逻辑函数表达式的标准形式 逻辑函数表达式的标准形式是建立在最小项和最大项概念的基础之上的 逻辑函数表达式可以被表示成任意的混合形式 例如 2010 4 都江堰校区周林 78 一 标准与或表达式 1 定义 如果一个具有n个变量的函数的 与项 包含全部n个变量 每个变量都以原变量或反变量形式出现一次 且仅出现一次 则该 与项 被称为最小项 有时又将最小项称为标准 与项 一 最小项的概念 2 最小项的数目 n个变量可以构成2n个最小项 例如 3个变量A B C可以构成8个最小项 2010 4 都江堰校区周林 79 3 最小项的表示方法 最小项编号 通常用符号mi来表示最小项 下标i的确定 把最小项中的原变量记为1 反变量记为0 当变量顺序确定后 可以按顺序排列成一个二进制数 则与这个二进制数相对应的十进制数 就是这个最小项的下标i 如 3变量A B C的8个最小项可以分别表示为 2010 4 都江堰校区周林 80 4 最小项的性质 任意一个最小项 只有一组变量取值使其值为1 取1的机会最小 故称 最小项 n个变量的全部最小项之和必为1 任意两个不同最小项相之积必为0 即mi mj 0 2010 4 都江堰校区周林 81 性质4 n个变量构成的最小项有n个相邻最小项 任意两个相邻项是满足互补律的 相邻最小项 是指除一个变量互为相反外 其余部分均相同的最小项 例如 三变量最小项ABC有三个相邻项 二 标准与或表达式 任何一个逻辑函数都可以表示成唯一的一组最小项之和 称为标准与或表达式 也称为最小项表达式 是组成逻辑函数的基本单元 2010 4 都江堰校区周林 82 1 定义 如果一个具有n个变量函数的 或项 包含全部n个变量 每个变量都以原变量或反变量形式出现一次 且仅出现一次 则该 或项 被称为最大项 有时又将最大项称为标准 或项 二 标准或与表达式 数目 n个变量可以构成2n个最大项 例如 3个变量A B C可构成以下8个最大项 一 最大项的概念 2010 4 都江堰校区周林 83 3 性质 最大项具有如下四条性质 2 最大项的简写表示法 用Mi表示最大项 下标i的取值规则是 将最大项中的原变量用0表示 反变量用1表示 由此得到一个二进制数 与该二进制数对应的十进制数即下标i的值 例如 3变量A B C构成的最大项可用M5表示 因为 2010 4 都江堰校区周林 84 1 任意一个最大项 仅有一组变量取值使其值为0 其值为1的变量取值组合数最多的一种 或项 因而将其称为最大项 2 相同变量构成的两个不同最大项相 或 为1 即Mi Mj 1 3 n个变量的全部最大项相 与 为0 记为 2010 4 都江堰校区周林 85 性质4 n个变量构成的最大项有n个相邻最大项 相邻最大项是指除一个变量互为相反外 其余变量均相同的最大项 4 最小项和最大项的关系 在同一问题中 下标相同的最小项和最大项互为反函数 或者说 相同变量构成的最小项mi和最大项Mi之间存在互补关系 即 例如 由3变量A B C构成的最小项m3和最大项M3之间有 2010 4 都江堰校区周林 86 二 标准 或 与 表达式 由若干最大项相 与 构成的逻辑表达式称为标准 或 与 表达式 也叫做最大项表达式 该表达式又可简写为 2010 4 都江堰校区周林 87 一 最简与或式 乘积项的个数最少 每个乘积项中相乘的变量个数也最少的与或表达式 叫最简与或表达式 二 最简与非 与非式 非号最少 每个非号下面相乘的变量个数也最少的与非 与非式 写法 在最简与或表达式的基础上 两次取反 再用反演律去掉下面的反号 三 逻辑函数的最简表达式 2010 4 都江堰校区周林 88 解 三 最简或与式 括号个数最少 每个括号中相加的变量的个数也最少的或与式 写法 在反函数最简与或表达式的基础上 取反 再用反演律对掉反号 解 写出上式的反函数 取反 例如写出函数的最简或与式 2010 4 都江堰校区周林 89 四 最简或非 或非式 非号个数最少 非号下面相加变量的个数最少的或非 或非式 写法 在最简或与式基础上 两次取反 再用反演律去掉下面的反号 例如写出函数的最简或非 或非表达与式 五 最简与或非式 在非号下面相加的乘积项的个数最少 每个乘积项中相乘的变量个数也最少的与或非式 叫最简与或非表达式 写法 在最简或非 或非式基础上 用反演律去掉大反号下面的小反号 结论 只要得到了函数的与或式 再用摩根定理进行适当变换 任何一个逻辑函数式都可以通过逻辑变换写成以上五种形式 2010 4 都江堰校区周林 90 1 2 2逻辑函数的公式化简法 公式化简法就是运用逻辑代数的公理 定理和规则对逻辑函数进行化简的方法 这种方法没有固定的步骤可以遵循 主要取决于对逻辑代数中公理 定理和规则的熟练掌握及灵活运用的程度 一 与 或 表达式的化简 几种常用方法如下 1 并项法 利用定理 将两个 与 项合并成一个 与 项 合并后消去一个变量 例如 2010 4 都江堰校区周林 91 解 先用摩根定理展开与非项 再用吸收法即可得 2010 4 都江堰校区周林 92 实际应用中遇到的逻辑函数往往比较复杂 化简时应灵活使用所学的公理 定理及规则 综合运用各种方法 下面举例说明 2010 4 都江堰校区周林 93 例1化简 解 例2化简 解 2010 4 都江堰校区周林 94 二 或 与 表达式的化简 用代数化简法化简 或 与 表达式可直接运用公理 定理中的 或 与 形式 并综合运用前面介绍 与 或 表达式化简时提出的各种方法进行化简 例如 化简 解 吸收定理 多余项定理 2010 4 都江堰校区周林 95 当对公理 定理中的 或 与 形式不太熟悉时 可以采用两次对偶法 具体如下 第一步 对 或 与 表达式表示的函数Y求对偶 得到 与 或 表达式Y 第二步 求出Y 的最简 与 或 表达式 第三步 对Y 再次求对偶 即可得到Y的最简 或 与 表达式 例如 化简 解 第一步 求Y的对偶式Y 第二步 化简Y 第三步 对Y 求对偶 得到Y的最简 或 与 表达式 2010 4 都江堰校区周林 96 解 例1 2 16化简逻辑函数 利用 再举几个例子 例1 2 17化简逻辑函 解法1 解法2 Y Y 2010 4 都江堰校区周林 97 解 利用反演律 配项法 利用 利用A AB A 利用A AB A 利用 例3 1 7化简逻辑函数 Y 2010 4 都江堰校区周林 98 1 正确理解最小项概念 2 熟悉标准与或表达式 3 熟悉最小项的表示方法及性质 4 了解最大项的概念及表示方法 5 了解逻辑函数的转换及几种最简表达式方法 本次课小结 2010 4 都江堰校区周林 99 代数化简法的优点是 不受变量数目的约束 当对公理 定理和规则十分熟练时 化简比较方便 缺点是 没有一定的规律和步骤 技巧性很强 而且在很多情况下难以判断化简结果是否最简 作业 P691 8 1 3 5 1 9 2 4 6 6 掌握公式法化简的基础方法 并项 吸收 消去 配项等方法 结论 逻辑函数的化简结果不是唯一的 2010 4 都江堰校区周林 100 什么是卡诺图 三变量卡诺图 1 2 3逻辑函数的卡诺图化简法 卡诺图 真值表的方格图形式 变量分为行 列两组 以格雷码形式排列在图旁 对应的最小项填在格内 这就是变量卡诺图 2010 4 都江堰校区周林 101 一 逻辑变量的卡诺图 1 变量卡诺图指画成正方形或矩形的图形 图中分割出若干个小方格 每个小方格对应一个变量最小项 该方格图则称为变量卡诺图 亦称最小项方块图 一 逻辑变量的卡诺图的画法 2 对于n个变量数 正方形或矩形分割出的小方块数应有2n个 3 变量取值顺序应按格雷码 循环码 排列 这点很重要 这样才能保证相邻性 然后将这些最小项按照相邻性排列起来 即用小方格几何位置上的相邻性来表示最小项逻辑上的相邻性 2010 4 都江堰校区周林 102 英文 GrayCode 又称作葛莱码 二进制循环码 是1880年法国工程师Jean Maurice EmlleBaudot 让莫里斯 埃米尔教授 发明 由贝尔实验室的FrankGray在20世纪40年代提出的的一种编码 格雷码是一种无权码 采用绝对编码方式 典型格雷码是一种具有反射特性和循环特性的单步自补码 它的循环 单步特性消除了随机取数时出现重大误差的可能 它的反射 自补特性使得求反非常方便 格雷码属于可靠性编码 是一种错误最小化的编码方式 而自然二进制码可以直接由数 模转换器转换成模拟信号 但某些情况 例如从十进制的3转换成4时二进制码的每一位都要变 使数字电路产生很大的尖峰电流脉冲 而格雷码则没有这一缺点 它是一种数字排序系统 其中的所有相邻整数在它们的数字表示中只有一个数字不同 它在任意两个相邻的数之间转换时 只有一个数位发生变化 它大大地减少了由一个状态到下一个状态时逻辑的混淆 另外由于最大数与最小数之间也仅一个数不同 故通常又叫格雷反射码或循环码 格雷码 Gray 简介 2010 4 都江堰校区周林 103 二进制码 格雷码 编码 从最右边一位起 依次将每一位与左边一位异或 XOR 作为对应格雷码该位的值 最左边一位不变 相当于左边是0 格雷码 二进制码 解码 最高位与格雷码相同 从格雷码左边第二位起 将每位与二进制高位的值异或 作为该位二进制的值 最左边一位依然不变 由Bi Gi 公式为 Gi Bi 1 Bi如求二进制码 0110 B的格雷码 G0 1 0 1 G1 1 1 0 G2 0 1 1 G3 0 0 0 由Gi Bi 公式为 Bi Bi 1 Gi如求格雷码 0110 G的二进制码 B3 0 B2 0 1 1 B1 1 1 0 B0 0 0 0 2010 4 都江堰校区周林 104 如果两个相邻最小项出现在同一个逻辑函数中 可以合并为一项 同时消去互为反变量的那个量 如 卡诺图中是按格雷码填的最小项 则就能保证最小项间具有逻辑相邻性 如图 2010 4 都江堰校区周林 105 2变量 3变量 4变量卡诺图如图 a b c 所示 二 变量卡诺图的构成 2010 4 都江堰校区周林 106 三 卡诺图在构造上具有以下几个特点 1 n个变量的卡诺图由2n个小方格组成 每个小方格代表一个最小项 2 用几何相邻形象地表示变量各个最小项在逻辑上的相邻性 几何相邻 包括三种情况 1 相接 紧挨着的 2 相对 任意一行或一列的两头 3 相重