数字逻辑基础.ppt

上海第二工业大学杨洁 数字电路基础 第5章逻辑代数基础 学习要点 二进制 二进制与十进制的相互转换逻辑代数的基本概念逻辑代数的公式与定理 逻辑函数化简 第5章逻辑代数基础 5 1数制与编码 5 2逻辑函数 5 3布尔代数 5 4具有约束的逻辑函数 5 1数制与编码 5 1 1进位计数制 5 1 2进位计数制转换 5 1 3二进制编码 退出 1 进位制 表示数时 仅用一位数码往往不够用 必须用进位计数的方法组成多位数码 多位数码每一位的构成以及从低位到高位的进位规则称为进位计数制 简称进位制 数制 2 基数 进位制的基数 就是在该进位制中可能用到的数码个数 3 位权 位的权数 在某一进位制的数中 每一位的大小都对应着该位上的数码乘上一个固定的数 这个固定的数就是这一位的权数 权数是一个幂 数码为 0 9 基数是10 Decimal 十进制运算规律 逢十进一 即 9 1 10 十进制数的权展开式 1 十进制 103 102 101 100称为十进制的权 各数位的权是10的幂 同样的数码在不同的数位上代表的数值不同 任意一个十进制数都可以表示为各个数位上的数码与其对应的权的乘积之和 称权展开式 即 5555 D 5 103 5 102 5 101 5 100 又如 209 04 10 2 102 0 101 9 100 0 10 1 4 10 2 2 二进制 数码为 0 1 基数是2 Binary 二进制运算规律 逢二进一 即 1 1 10 二进制数的权展开式 如 101 01 B 1 22 0 21 1 20 0 2 1 1 2 2 5 25 10 加法规则 0 0 0 0 1 1 1 0 1 1 1 10乘法规则 0 0 0 0 1 0 1 0 0 1 1 1 运算规则 各数位的权是 的幂 二进制数只有0和1两个数码 它的每一位都可以用电子元件来实现 且运算规则简单 相应的运算电路也容易实现 数码为 0 7 基数是8 O 八进制运算规律 逢八进一 即 7 1 10 八进制数的权展开式 如 207 04 8 2 82 0 81 7 80 0 8 1 4 8 2 135 0625 10 3 八进制 4 十六进制 数码为 0 9 A F 基数是16 Hexadecimal 十六进制运算规律 逢十六进一 即 F 1 10 十六进制数的权展开式 如 D8 A H 13 161 8 160 10 16 1 216 625 10 各数位的权是8的幂 各数位的权是16的幂 结论 一般地 N进制需要用到N个数码 基数是N 运算规律为逢N进一 如果一个N进制数M包含 位整数和 位小数 即 an 1an 2 a1a0 a 1a 2 a m N则该数的权展开式为 M N an 1 Nn 1 an 2 Nn 2 a1 N1 a0 N0 a 1 N 1 a 2 N 2 a m N m 由权展开式很容易将一个N进制数转换为十进制数 数制转换 1 二进制数转换为八进制数 将二进制数由小数点开始 整数部分向左 小数部分向右 每3位分成一组 不够3位补零 则每组二进制数便是一位八进制数 将N进制数按权展开 即可以转换为十进制数 1 二进制数与八进制数的相互转换 1101010 01 00 0 152 2 8 2 八进制数转换为二进制数 将每位八进制数用3位二进制数表示 011111100 010110 374 26 8 2 二进制数与十六进制数的相互转换 111010100 011 000 0 1D4 6 16 101011110100 01110110 AF4 76 16 二进制数与十六进制数的相互转换 按照每4位二进制数对应于一位十六进制数进行转换 3 十进制数转换为二进制数 采用的方法 基数连除 连乘法原理 将整数部分和小数部分分别进行转换 整数部分采用基数连除法 小数部分采用基数连乘法 转换后再合并 整数部分采用基数连除法 先得到的余数为低位 后得到的余数为高位 小数部分采用基数连乘法 先得到的整数为高位 后得到的整数为低位 所以 0 375 10 0 011 2 采用基数连除 连乘法 可将十进制数转换为任意的N进制数 25 D 11001 B 用一定位数的二进制数来表示十进制数码 字母 符号等信息称为编码 用以表示十进制数码 字母 符号等信息的一定位数的二进制数称为代码 编码 数字系统只能识别0和1 怎样才能表示更多的数码 符号 字母呢 用编码可以解决此问题 二 十进制代码 用4位二进制数b3b2b1b0来表示十进制数中的0 9十个数码 简称BCD码 8421码的权值依次为8 4 2 1 余3码由8421码加0011得到 格雷码是一种循环码 其特点是任何相邻的两个码字 仅有一位代码不同 其它位相同 用四位自然二进制码中的前十个码字来表示十进制数码 因各位的权值依次为8 4 2 1 故称8421BCD码 本节小结 日常生活中使用十进制 但在计算机中基本上使用二进制 有时也使用八进制或十六进制 利用权展开式可将任意进制数转换为十进制数 将十进制数转换为其它进制数时 整数部分采用基数除法 小数部分采用基数乘法 利用1位八进制数由3位二进制数构成 1位十六进制数由4位二进制数构成 可以实现二进制数与八进制数以及二进制数与十六进制数之间的相互转换 二进制代码不仅可以表示数值 而且可以表示符号及文字 使信息交换灵活方便 BCD码是用4位二进制代码代表1位十进制数的编码 有多种BCD码形式 最常用的是8421BCD码 5 2逻辑函数 5 2 1逻辑函数的基本概念 5 2 2逻辑代数的公式 定理和规则 5 2 3逻辑函数的表达式 事物往往存在两种对立的状态 在逻辑代数中可以抽象地表示为0和1 称为逻辑0状态和逻辑1状态 逻辑函数是按一定的逻辑关系进行运算的函数 是分析和设计数字电路的数学工具 在逻辑代数 只有 和 两种逻辑值 有与 或 非三种基本逻辑运算 还有与或 与非 与或非 异或几种导出逻辑运算 逻辑代数中的变量称为逻辑变量 用大写字母表示 逻辑变量的取值只有两种 即逻辑0和逻辑1 0和1称为逻辑常量 并不表示数量的大小 而是表示两种对立的逻辑状态 逻辑是指事物的因果关系 或者说条件和结果的关系 这些因果关系可以用逻辑运算来表示 也就是用逻辑代数来描述 1 与逻辑 与运算 与逻辑的定义 仅当决定事件 Y 发生的所有条件 A B C 均满足时 事件 Y 才能发生 表达式为 开关A B串联控制灯泡Y 两个开关必须同时接通 灯才亮 逻辑表达式为 A B都断开 灯不亮 A断开 B接通 灯不亮 A接通 B断开 灯不亮 A B都接通 灯亮 这种把所有可能的条件组合及其对应结果一一列出来的表格叫做真值表 将开关接通记作1 断开记作0 灯亮记作1 灯灭记作0 可以作出如下表格来描述与逻辑关系 功能表 实现与逻辑的电路称为与门 与门的逻辑符号 真值表 逻辑符号 2 或逻辑 或运算 或逻辑的定义 当决定事件 Y 发生的各种条件 A B C 中 只要有一个或多个条件具备 事件 Y 就发生 表达式为 开关A B并联控制灯泡Y 两个开关只要有一个接通 灯就会亮 逻辑表达式为 A B都断开 灯不亮 A断开 B接通 灯亮 A接通 B断开 灯亮 A B都接通 灯亮 实现或逻辑的电路称为或门 或门的逻辑符号 Y A B 真值表 功能表 逻辑符号 3 非逻辑 非运算 非逻辑指的是逻辑的否定 当决定事件 Y 发生的条件 A 满足时 事件不发生 条件不满足 事件反而发生 表达式为 开关A控制灯泡Y 实现非逻辑的电路称为非门 非门的逻辑符号 A断开 灯亮 A接通 灯灭 真值表 功能表 逻辑符号 4 常用的逻辑运算 1 与非运算 逻辑表达式为 2 或非运算 逻辑表达式为 3 异或运算 逻辑表达式为 4 与或非运算 逻辑表达式为 基本逻辑关系小结 5 逻辑函数及其相等概念 1 逻辑表达式 由逻辑变量和与 或 非3种运算符连接起来所构成的式子 在逻辑表达式中 等式右边的字母A B C D等称为输入逻辑变量 等式左边的字母Y称为输出逻辑变量 字母上面没有非运算符的叫做原变量 有非运算符的叫做反变量 2 逻辑函数 如果对应于输入逻辑变量A B C 的每一组确定值 输出逻辑变量Y就有唯一确定的值 则称Y是A B C 的逻辑函数 记为 注意 与普通代数不同的是 在逻辑代数中 不管是变量还是函数 其取值都只能是0或1 并且这里的0和1只表示两种不同的状态 没有数量的含义 3 逻辑函数相等的概念 设有两个逻辑函数 它们的变量都是A B C 如果对应于变量A B C 的任何一组变量取值 Y1和Y2的值都相同 则称Y1和Y2是相等的 记为Y1 Y2 若两个逻辑函数相等 则它们的真值表一定相同 反之 若两个函数的真值表完全相同 则这两个函数一定相等 因此 要证明两个逻辑函数是否相等 只要分别列出它们的真值表 看看它们的真值表是否相同即可 证明等式 逻辑函数的表示方法 1 真值表 真值表 是由变量的所有可能取值组合及其对应的函数值所构成的表格 真值表列写方法 每一个变量均有0 1两种取值 n个变量共有2i种不同的取值 将这2i种不同的取值按顺序 一般按二进制递增规律 排列起来 同时在相应位置上填入函数的值 便可得到逻辑函数的真值表 例如 当A B 1 或则B C 1时 函数Y 1 否则Y 0 2 逻辑表达式 逻辑表达式 是由逻辑变量和与 或 非3种运算符连接起来所构成的式子 函数的标准与或表达式的列写方法 将函数的真值表中那些使函数值为1的最小项相加 便得到函数的标准与或表达式 3 卡诺图 卡诺图 是由表示变量的所有可能取值组合的小方格所构成的图形 逻辑函数卡诺图的填写方法 在那些使函数值为1的变量取值组合所对应的小方格内填入1 其余的方格内填入0 便得到该函数的卡诺图 4 逻辑图 逻辑图 是由表示逻辑运算的逻辑符号所构成的图形 波形图 波形图 是由输入变量的所有可能取值组合的高 低电平及其对应的输出函数值的高 低电平所构成的图形 逻辑函数表示方法之间的转换 1 由真值表到逻辑图的转换 真值表 逻辑表达式或卡诺图 1 1 最简与或表达式 化简 2 或 2 画逻辑图 3 最简与或表达式 B A A C AC Y B A A C Y 若用与非门实现 将最简与或表达式变换乘最简与非 与非表达式 3 2 由逻辑图到真值表的转换 逻辑图 逻辑表达式 1 1 最简与或表达式 化简 2 2 从输入到输出逐级写出 最简与或表达式 3 真值表 3 本节小结 逻辑函数可用真值表 逻辑表达式 卡诺图 逻辑图和波形图5种方式表示 它们各具特点 但本质相通 可以互相转换 对于一个具体的逻辑函数 究竟采用哪种表示方式应视实际需要而定 在使用时应充分利用每一种表示方式的优点 由于由真值表到逻辑图和由逻辑图到真值表的转换 直接涉及到数字电路的分析和设计问题 因此显得更为重要 正负逻辑的概念 1 基本概念正逻辑 用高电平表示逻辑1 低电平表示逻辑0 负逻辑 用高电平表示逻辑0 低电平表示逻辑1 2 正逻辑与负逻辑的关系 按正逻辑规定 可得到表3 5所示真值表 由真值表可知 该电路是一个正逻辑的 与 门 按负逻辑规定 可得到表3 6所示真值表 由真值表可知 该电路是一个负逻辑的 或 门 即正逻辑与门等价于负逻辑或门 前面讨论各种逻辑门电路时 都是按照正逻辑规定来定义其逻辑功能的 在本课程中 若无特殊说明 约定按正逻辑讨论问题 所有门电路的符号均按正逻辑表示 布尔代数逻辑代数最初是由英国数学家布尔 G Boole 首先提出来的 被称为布尔代数 逻辑代数的变量称为逻辑变量 逻辑变量与一般代数变量不同 逻辑变量的取值只有0和1 就是说逻辑电路中只有两种逻辑状态 这里的1和0可以由数字系统中的电平的高低 开关的断通和信号的有无来表示 1 布尔代数的公式和定理 1 常量之间的关系 2 基本公式 分别令A 0及A 1代入这些公式 即可证明它们的正确性 3 基本定理 利用真值表很容易证明这些公式的正确性 如证明A B B A A B A C AA BA AC BC 分配率A B C AB AC A AB AC BC 等幂率AA A A 1 B C BC 分配率A B C AB AC A BC 0 1率A 1 1 证明分配律 A BC A B A C 证明 4 常用公式 分配率A BC A B A C 0 1率A 1 1 吸收规则 1 原变量的吸收 A AB A 证明 A AB A 1 B A 1 A 利用运算规则可以对逻辑式进行化简 例如 吸收是指吸收多余 冗余 项 多余 冗余 因子被取消 去掉 被消化了 长中含短 留下短 2 反变量的吸收 证明 例如 长中含反 去掉反 3 混合变量的吸收 证明 例如 正负相对 余全完 分配率A B C AB AC 0 1率A 1 1 例如 已知等式 用函数Y AC代替等式中的A 根据代入规则 等式仍然成立 即有 2 布尔代数运算的基本规则 1 代入规则 任何一个含有变量A的等式 如果将所有出现A的位置都用同一个逻辑函数代替 则等式仍然成立 这个规则称为代入规则 2 反演规则 对于任何一个逻辑表达式Y 如果将表达式中的所有 换成 换成 0 换成 1 1 换成 0 原变量换成反变量 反变量换成原变量 那么所得到的表达式就是函数Y的反函数Y 或称补函数 这个规则称为反演规则 例如 反演定理内容 将函数式F中所有的 变量与常数均取反 互补运算 2 不是一个变量上的反号不动 注意 用处 实现互补运算 求反运算 新表达式 F 显然 变换时 原函数运算的先后顺序不变 例1 与或式 注意括号 注意括号 例2 与或式 反号不动 反号不动 3 对偶规则 对于任何一个逻辑表达式Y 如果将表达式中的所有 换成 换成 0 换成 1 1 换成 0 而变量保持不变 则可得到的一个新的函数表达式Y Y 称为函Y的对偶函数 这个规则称为对偶规则 例如 对偶规则的意义在于 如果两个函数相等 则它们的对偶函数也相等 利用对偶规则 可以使要证明及要记忆的公式数目减少一半 例如 注意 在运用反演规则和对偶规则时 必须按照逻辑运算的优先顺序进行 先算括号 接着与运算 然后或运算 最后非运算 否则容易出错 逻辑函数的表达式 一个逻辑函数的表达式可以有与或表达式 或与表达式 与非 与非表达式 或非 或非表达式 与或非表达式5种表示形式 一种形式的函数表达式相应于一种逻辑电路 尽管一个逻辑函数表达式的各种表示形式不同 但逻辑功能是相同的 1 逻辑函数的最小项及其性质 1 最小项 如果一个函数的某个乘积项包含了函数的全部变量 其中每个变量都以原变量或反变量的形式出现 且仅出现一次 则这个乘积项称为该函数的一个标准积项 通常称为最小项 3个变量A B C可组成8个最小项 2 最小项的表示方法 通常用符号mi来表示最小项 下标i的确定 把最小项中的原变量记为1 反变量记为0 当变量顺序确定后 可以按顺序排列成一个二进制数 则与这个二进制数相对应的十进制数 就是这个最小项的下标i 3个变量A B C的8个最小项可以分别表示为 3 最小项的性质 任意一个最小项 只有一组变量取值使其值为1 全部最小项的和必为1 任意两个不同的最小项的乘积必为0 2 逻辑函数的最小项表达式 任何一个逻辑函数都可以表示成唯一的一组最小项之和 称为标准与或表达式 也称为最小项表达式 如果列出了函数的真值表 则只要将函数值为1的那些最小项相加 便是函数的最小项表达式 将真值表中函数值为0的那些最小项相加 便可得到反函数的最小项表达式 逻辑相邻 若两个最小项只有一个变量以原 反区别 其他变量均相同 则称这两个最小项逻辑相邻 逻辑相邻的项可以合并 消去一个因子 本节小结 逻辑代数是分析和设计数字电路的重要工具 利用逻辑代数 可以把实际逻辑问题抽象为逻辑函数来描述 并且可以用逻辑运算的方法 解决逻辑电路的分析和设计问题 与 或 非是3种基本逻辑关系 也是3种基本逻辑运算 与非 或非 与或非 异或则是由与 或 非3种基本逻辑运算复合而成的4种常用逻辑运算 逻辑代数的公式和定理是推演 变换及化简逻辑函数的依据 逻辑函数的化简 逻辑函数的最简表达式 逻辑函数的公式化简法 逻辑函数的图形化简法 含随意项的逻辑函数的化简 逻辑函数化简的意义 逻辑表达式越简单 实现它的电路越简单 电路工作越稳定可靠 逻辑函数的最简表达式 1 最简与或表达式 乘积项最少 并且每个乘积项中的变量也最少的与或表达式 最简与或表达式 2 最简与非 与非表达式 非号最少 并且每个非号下面乘积项中的变量也最少的与非 与非表达式 在最简与或表达式的基础上两次取反 用摩根定律去掉下面的非号 3 最简或与表达式 括号最少 并且每个括号内相加的变量也最少的或与表达式 求出反函数的最简与或表达式 利用反演规则写出函数的最简或与表达式 4 最简或非 或非表达式 非号最少 并且每个非号下面相加的变量也最少的或非 或非表达式 求最简或非 或非表达式 两次取反 最简与或非表达式 非号下面相加的乘积项最少 并且每个乘积项中相乘的变量也最少的与或非表达式 求最简或非 或非表达式 用摩根定律去掉下面的非号 用摩根定律去掉大非号下面的非号 逻辑函数的公式化简法 1 并项法 逻辑函数的公式化简法就是运用逻辑代数的基本公式 定理和规则来化简逻辑函数 若两个乘积项中分别包含同一个因子的原变量和反变量 而其他因子都相同时 则这两项可以合并成一项 并消去互为反变量的因子 运用摩根定律 运用分配律 运用分配律 2 吸收法 如果乘积项是另外一个乘积项的因子 则这另外一个乘积项是多余的 运用摩根定律 利用公式 消去多余的项 如果一个乘积项的反是另一个乘积项的因子 则这个因子是多余的 配项法 利用公式 为某项配上其所能合并的项 消去冗余项法 例 化简函数 解 先求出Y的对偶函数Y 并对其进行化简 求Y 的对偶函数 便得 的最简或与表达式 例1 例2 反演 结论 异或门可以用4个与非门实现 例3 证明 AB A B 展开 例4 化简为最简逻辑代数式 例5 将Y化简为最简逻辑代数式 利用反演定理 逻辑函数的图形化简法 卡诺图 1 卡诺图的构成 逻辑函数的图形化简法是将逻辑函数用卡诺图来表示 利用卡诺图来化简逻辑函数 将逻辑函数真值表中的最小项重新排列成矩阵形式 并且使矩阵的横方向和纵方向的逻辑变量的取值按照格雷码的顺序排列 这样构成的图形就是卡诺图 卡诺图的特点是任意两个相邻的最小项在图中也是相邻的 相邻项是指两个最小项只有一个因子互为反变量 其余因子均相同 又称为逻辑相邻项 每个2变量的最小项有两个最小项与它相邻 每个3变量的最小项有3个最小项与它相邻 每个4变量的最小项有4个最小项与它相邻 最左列的最小项与最右列的相应最小项也是相邻的 最上面一行的最小项与最下面一行的相应最小项也是相邻的 两个相邻最小项可以合并消去一个变量 逻辑函数化简的实质就是相邻最小项的合并 2 逻辑函数在卡诺图中的表示 1 逻辑函数是以真值表或者以最小项表达式给出 在卡诺图上那些与给定逻辑函数的最小项相对应的方格内填入1 其余的方格内填入0 m1 m3 m4 m6 m7 m11 m14 m15 2 逻辑函数以一般的逻辑表达式给出 先将函数变换为与或表达式 不必变换为最小项之和的形式 然后在卡诺图上与每一个乘积项所包含的那些最小项 该乘积项就是这些最小项的公因子 相对应的方格内填入1 其余的方格内填入0 变换为与或表达式 3 卡诺图的性质 1 任何两个 21个 标1的相邻最小项 可以合并为一项 并消去一个变量 消去互为反变量的因子 保留公因子 2 任何4个 22个 标1的相邻最小项 可以合并为一项 并消去2个变量 3 任何8个 23个 标1的相邻最小项 可以合并为一项 并消去3个变量 小结 相邻最小项的数目必须为个才能合并为一项 并消去个变量 包含的最小项数目越多 即由这些最小项所形成的圈越大 消去的变量也就越多 从而所得到的逻辑表达式就越简单 这就是利用卡诺图化简逻辑函数的基本原理 4 图形法化简的基本步骤 逻辑表达式或真值表 卡诺图 1 1 合并