L2第二章逻辑代数基础.ppt

第二章逻辑代数基础 学习要求 掌握逻辑代数的基本概念 学会用逻辑函数描述逻辑问题的基本方法 掌握逻辑代数的公理 基本定理和重要规则 学会用代数法化简逻辑函数 熟练掌握用卡诺图化简逻辑函数 2 1逻辑代数的基本概念 逻辑代数是一个由逻辑变量集K 常量0和1以及 与 或 非 3种基本运算构成的一个封闭的代数系统 记为L K 0 1 它是一个二值代数系统 常量0和1表示真和假 无大小之分 2 1 1逻辑变量与逻辑函数 一 逻辑变量 仅取值0或取值1的变量 这里0和1无大小之分 实际上代表着矛盾的双方或事件的真假 例如开关的接通与断开 电压的高和底 信号的有和无 电灯的亮和灭等等 只要是两种稳定的物理状态 都可以用0和1这两种不同的逻辑值来表征 二 逻辑函数的定义 设某一电路的输入逻辑变量为A1 A2 An 输出逻辑变量为F 如果当A1 A2 An的值确定后 F的值就唯一地被定下来 则F称为A1 A2 An 的逻辑函数 记为F f A1 A2 An 逻辑电路的功能可由相应逻辑函数完全描述 与普通函数概念相比逻辑函数有如下特点 1 逻辑变量与逻辑函数的取值只有0和1 2 逻辑函数与逻辑变量的关系由 或 与 非 运算决定 三 逻辑函数的相等 设有两个逻辑函数 F1 f1 A1 A2 An F2 f2 A1 A2 An 若对应于A1 A2 An的任何一组取值 F1和F2的值都相同 则称函数F1和函数F2相等 记作F1 F2 亦称函数F1与F2等价 等号 不表示两边数值相等 仅表示一种等价 等效的逻辑关系 一 或 运算 如果决定某一事件发生的多个条件 只要有一个或一个以上的条件成立 事件便可发生 这种因果关系称之为 或 逻辑 在逻辑代数中 或 逻辑关系用 或 运算描述 或 运算又称逻辑加 其运算符为 或 两个变量的 或 运算可表示为 F A B或者F A B 读作 F等于A或B 其中A B是参加运算的两个逻辑变量 F为运算结果 意思是 只要A B中有一个为1 则F为1 仅当A B均为0时 F才为0 2 1 2基本逻辑运算 或 运算表 由 或 运算的运算表可知 或 运算的法则为 0 0 01 0 10 1 11 1 1 实现 或 运算的逻辑电路称为 或 门 F A B 二 与 运算 如果决定某一事件的发生的多个条件必须同时具备 事件才能发生 这种因果关系称为 与 逻辑 逻辑代数中 与 逻辑关系用 与 运算描述 与 运算又称逻辑乘 其运算符为 或 两变量的 与 运算可表示为F A B或者F A B读作 F等于A与B 意思是若A B均为1 则F为1 否则F为0 与 运算表 由 与 运算的运算表可知 与 运算法则为 0 0 01 0 00 1 01 1 1 实现 与 运算的逻辑电路称为 与 门 F A B 三 非 运算 如果某一事件的发生取决于条件的否定 则这种因果关系称为 非 逻辑 非 逻辑用 非 运算描述 非 运算又称求反运算 运算符为 或 非 运算可表示为 读作 F等于A非 意思是若A 0 则F为1 反之 若A 1 则F为0 非 运算表 由 非 运算的运算表可知 非 运算法则为 实现 非 运算的逻辑电路称为 非 门 公理1交换律A B B A A B B A 公理2结合律 A B C A B C A B C A B C 公理3分配律A B C A B B C A B C A B A C 公理40 1律A 0 A A 1 AA 1 1 A 0 0 满足下列公理 2 1 3逻辑函数的表示法 一 逻辑表达式 由逻辑变量 常量和逻辑运算符构成的合法表达式 进行 非 运算可不加括号 如 与 运算符一般可省略 A B可写成AB 可根据先 与 后 或 的顺序去括号 如 AB CD AB CD 例 逻辑表达式书写省略规则 常用逻辑表达式的读法 二 真值表 真值表是一种由逻辑变量的所有可能的取值组合及其对应的逻辑函数值所构成的表格 三 卡诺图 卡诺图是一种用图形描述逻辑函数的方法 卡诺图是由表示逻辑变量的所有可能组合的小方格构成的图形 可以表示并化简逻辑函数 2 2逻辑代数的基本定理和规则 2 2 1基本定理 定理10 0 01 0 10 1 11 1 10 0 01 0 00 1 01 1 1 定理2 重叠律 A A AA A A 定理3 吸收律 A A B AA A B A 2 2 2逻辑代数的重要规则 一 代入规则 任何一个含有变量A的逻辑等式 如果将所有出现A的位置都代之以同一个逻辑函数F 则等式仍然成立 二 反演规则 如果将逻辑函数F中所有的 变成 变成 0 变成 1 1 变成 0 原变量变成反变量 反变量变成原变量 所得到的新函数是原函数的反函数 使用反演规则时 应注意保持原函式中运算符号的优先顺序不变 例如 已知 例 利用反演规则求下列逻辑函数的反函数 解 三 对偶规则 如果将逻辑函数F中所有的 变成 变成 0 变成 1 1 变成 0 则所得到的新逻辑函数F的对偶式F 如果F 是F的对偶式 则F也是F 的对偶式 即F与F 互为对偶式 求某一函数F的对偶式时 同样要注意保持原函数的运算顺序不变 对偶规则应用 若两个逻辑函数F和G相等 则其对偶式F 和G 也相等 A B C 则 例 利用对偶规则求下列逻辑函数的对偶式 解 2 3逻辑函数表达式的形式与变换 2 3 1逻辑函数表达式的基本形式 两种基本形式 积之和 表达式与 和之积 表达式 2 3 2逻辑函数表达式的标准形式 一 最小项 如果一个具有n个变量的函数的 积 项包含全部n个变量 每个变量都以原变量或反变量形式出现 且仅出现一次 则这个 积 项被称为最小项 假如一个函数完全由最小项所组成 那么该函数表达式称为标准 积之和 表达式 即 最小项之和 三变量函数的最小项 N个变量 可构成2n个最小项 通常用mi表示最小项 各乘积项中原变量记为1 反变量记为0 得到二进制数 对应的十进制数为下标i m2 m3 m6 m7 注意 变量的顺序 即n个变量的所有最小项之和恒等于1 所以 m 2 3 6 7 最小项的性质 2 当函数以最小项之和形式表示时 可很容易列出函数及反函数的真值表 在真值表中 函数所包含的最小项填 1 4 n变量的最小项有n个相邻项 相邻项 只有一个变量不同 以相反的形式出现 一对相邻项可以消去一个变量 1 对任何一个最小项mi 只有一组变量的取值能使其值为1 例ABC 只有在A B C的取值分别为1 0 1时 其值才为1 二 最大项 如果一个具有n个变量的函数的 和 项包含全部n个变量 每个变量都以原变量或反变量形式出现 且仅出现一次 则这个 和 项称为最大项 假如一个函数完全由最大项组成 那么这个函数表达式称为标准 和之积 表达式 三变量函数的最大项 N个变量 可构成2n个最大项 通常用Mi表示最大项 或项中原变量记为0 反变量记为1 得到二进制数 对应的十进制数为下标i 注意 变量顺序 与最小项类似 有 例如 最大项的性质 2 当函数以最大项之积形式表示时 可很容易列出函数及反函数的真值表 在真值表中 函数所包含的最大项填 0 4 n变量的最大项有n个相邻项 相邻项 只有一个变量不同 以相反的形式出现 一对相邻项可以消去一个变量 1 对任何一个最大项Mi 只有一组变量的取值能使其值为0 例A B C 只有在A B C的取值分别为0 1 0时 其值才为0 三 两种标准形式的转换 以最小项之和的形式表示的函数可以转换成最大项之积的形式 反之亦然 m 2 3 6 7 且有 即 最大项与最小项互补 摩根律 2 3 3逻辑函数表达式的转换 任何一个逻辑函数 总可以将其转换成 最小项之和 及 最大项之积 的形式 常用代数转换法或真值表转换法 一 代数转换法 用代数法求一个函数 最小项之和 的形式 一般分为两步 第一步 将函数表达式变换成一般的 与或 式 F A B C m0 m1 m3 m6 m7 m 0 1 3 6 7 类似地 用代数法求一个函数 最大项之积 的形式 也可分为两步 第一步 将函数表达式转换成一般 或与 式 如果给出的函数已经是 或与 式 则可直接进行第二步 第二步 反复在非最大项的和项中加上它所缺变量的 原 反 之积 使用分配率 直到把全部和项都变成最大项 F A B C M1 M3 M6 M7 M 1 3 6 7 二 真值表转换法 一个逻辑函数的真值表与它的最小项表达式和最大项表达式均存在一一对应的关系 函数F的最小项表达式由使F取值为1的全部最小项之和组成 函数F的最大项表达式由使F取值为0的全部最大项之积组成 和 最大项之积 的形式 解 注意 任何一个逻辑函数的两种标准形式唯一 2 4逻辑函数的简化 一般来说 逻辑函数表达式越简单 设计出来的电路也就越简单 把逻辑函数简化成最简形式称为逻辑函数的最小化 有三种常用的方法 即代数化简法 卡诺图化简法和列表化简法 2 4 1代数化简法 该方法运用逻辑代数的公理 定理和规则对逻辑函数进行推导 变换而进行化简 没有固定的步骤可以遵循 主要取决于对公理 定理和规则的熟练掌握及灵活运用的程度 有时很难判定结果是否为最简 一 与或 式的化简 化简应满足的两个条件 1 表达式中 与项 的个数最少 2 在满足1 的前提下 每个 与项 中的变量个数最少 二 或与 式的化简 化简应满足的两个条件 1 表达式中 或项 的个数最少 2 在满足1 的前提下 每个 或项 中的变量个数最少 解 A B C 解 2 4 2卡诺图化简法 该方法简单 直观 容易掌握 当变量个数小于等于6时非常有效 在逻辑设计中得到广泛应用 一 卡诺图的构成 n个变量的卡诺图是一种由2n个方格构成的图形 每一个方格表示逻辑函数的一个最小项 所有的最小项巧妙地排列成一种能清楚地反映它们相邻关系的方格阵列 因为任意一个逻辑函数都可表示成 最小项之和 的形式 所以一个函数可用图形中若干方格构成的区域来表示 二变量卡诺图 三变量卡诺图 四变量卡诺图 定义 彼此只有一个变量不同 且这个不同变量互为反变量的两个最小项 或 与项 称为相邻最小项 或相邻 与项 相邻最小项在卡诺图中有三种特征 即几何相邻 相对相邻和重叠相邻 卡诺图在构造上具有以下两个特点 1 n个变量的卡诺图由2n个小方格组成 每个小方格代表一个最小项 2 卡诺图上处在相邻 相对 相重位置的小方格所代表的最小项为相邻最小项 二 逻辑函数的卡诺图表示 将逻辑函数所对应的最小项在卡诺图的相应方格中标以1 剩余方格标以0或不标 1 与或 式的卡诺图表示 直接将表达式的 与项 或 最小项 所对应的方格标以1 2 其它形式函数的卡诺图表示要转换成 与或 式再在卡诺图上表示 三 卡诺图的性质 在卡诺图上把相邻最小项所对应的小方格 圈 在一起可进行合并 以达到用一个简单 与项 代替若干最小项的目的 这样的 圈 称为 卡诺圈 二变量卡诺图的典型合并情况 AB 三变量卡诺图的典型合并情况 四变量卡诺图的典型合并情况 一个卡诺圈中的小方格满足以下规律 1 卡诺圈中的小方格的数目为2m m为整数且m n 3 2m个小方格可用 n m 个变量的 与项 表示 该 与项 由这些最小项中的相同变量构成 2 2m个小方格含有m个不同变量和 n m 个相同变量 4 当m n时 卡诺圈包围整个卡诺图 可用1表示 即n个变量的全部最小项之和为1 四 卡诺图化简逻辑函数的步骤 蕴涵项 与或 式中的每一个 与项 称为函数的蕴涵项 质蕴涵项 不被其它蕴涵项所包含的蕴涵项 必要质蕴涵项 质蕴涵项中至少有一个最小项不被其它蕴涵项所包含 用卡诺图化简逻辑函数的一般步骤为 第一步 作出函数的卡诺图 第二步 在卡诺图上圈出函数的全部质蕴涵项 第三步 从全部质蕴涵项中找出所有必要质蕴涵项 第四步 若全部必要质蕴涵项尚不能覆盖所有的1方格 则需从剩余质蕴涵项中找出最简的所需质蕴涵项 使它和必要质蕴涵项一起构成函数的最小覆盖 例 用卡诺图化简逻辑涵数F A B C D m 0 3 5 6 7 10 11 13 15 解 例 用卡诺图化简逻辑函数F A B C D m 2 3 6 7 8 10 12 解 例 用卡诺图把逻辑函数F A B C D M 3 4 6 7 11 12 13 14 15 化简成最简 或与 表达式 1 2 4 4逻辑函数化简中两个实际问题的考虑 一 包含无关最小项的逻辑函数的化简 无关最小项 一个逻辑函数 如果它的某些输入取值组合因受特殊原因制约而不会再现 或者虽然每种输入取值组合都可能出现 但此时函数取值为1还是为0无关紧要 那么这些输入取值组合所对应的最小项称为无关最小项 无关最小项可以随意加到函数表达式中 或不加到函数表达式中 并不影响函数的实际逻辑功能 例 给定某电路的逻辑函数真值表如下 求F的最简 与或 式 解 1 不考虑无关最小项 2 考虑无关最小项 二 多输出逻辑函数的化简 对于多输出逻辑函数 如果孤立地将单个输出一一化简 然后直接拼在一起 通常并不能保证整个电路最简 因为各个输出函数之间往往存在可供共享的部分 多输出逻辑函数化简的标准 2 在满足上述条件的前提下 各不同 与项 中所含的变量总数最少 1 所有逻辑表达式包含的不同 与项 总数最小 例 多输出函数 对应的卡诺图为 从多输出函数化简的观点来看 它们不是最佳的 应该是 列表化简法 列表化简法是Quine Mccluskey提出的一种系统化简法 故也称作Q M法 也称作表格法 这种方法具有严格的算法 虽然其工作量大 方法繁琐 但便于计算机化简多变量逻辑函数 Q M法化简逻辑函数的步骤如下 第一步 将函数表示成最小项表达式 第二步 找出函数的全部质蕴涵项 1 将n变量函数中的相邻最小项合并 消去相异的一个变量 得到 n 1 个变量的与项 蕴涵项 这时如果存在不能合并的最小项 它便是所寻找的部分质蕴涵项 2 再将相邻的 n 1 个变量的与项合并 消去相异的一个变量 得到 n 2 个变量的与项 蕴涵项 这里如果存在不能合并的 n 1 个变量的与项 则它们也是所寻找的质蕴涵项 如此进行下去 直到不能再合并为止 得全部的质蕴涵项 第三步 找出函数的必要质蕴涵项 先画出质蕴涵表 然后在表上找出仅属于一个质蕴涵项的最小项 则包含该最小项的质蕴涵项就是必要质蕴涵项 第四步 找出函数的最小覆盖 当第三步找出的必要质蕴涵项不能包含函数的全部最小项时 可以通过行 列消去法 找出最小覆盖的其他必要质蕴涵项 最小覆盖指包含函数的全部最小项的最小质蕴涵项集合 用Q M法化简函数 1 找出全部质蕴涵项 做最小项分组表并找出不能合并者 将最小项mi按变量取值表示成二进制数 其次 再根据这些二进制数中所包含1的个数从少到多的次序进行分组排队 最后 把含有1的个数相同的最小项划分成一组 组内按下标i的取值从小到大排列 如此制成最小项分组 从含有1个数最少的那组开始 在相邻组内比较最小项 将只有一个变量值不同的两个最小项合并 消去一个变量 并在已合并的最小项的右边Pi栏内做记号 表示该项已被合并 在不能合并的最小项的右边Pi栏内填入P1 则就是所寻找的质蕴涵项 注意合并最小项只能处于相邻的两组内 而不能处于同组或隔组内 做 n 1 个变量与项分组表并找出不能合并者 在最小项合并过程中 用符号 表示被消去的变量 这样便得到若干个带有 的与项 或称作合并项 按照对最小项的分组方法 对带有 的与项进行分组 对相邻组中的 处于相同位置的那些与项进行合并 已合并的与项做记号 并记入Pi栏 在不能合并的与项的Pi栏内记入P2和P3 则也是质蕴涵项 n 1 个变量与项分组表 做 n 2 个变量与项分组表并找出不能合并者 在 n 1 个变量与项合并过程中 也用符号 表示被消去的变量 这样便得到若干个带有两个 的与项 按照上述的分组方法 得到 n 2 个变量与项分组表 由表可以看出 仅有的两 n 2 个变量与项不能再合并 在Pi栏内分别记入P4和P5 P4和P5就是最后所寻找的质蕴涵项 n 2 个变量与项分组表 n 1 个变量与项分组表 列出全部质蕴涵项由上述分析可得全部质蕴涵项 2 找出必要质蕴涵项将函数的最小项和上述的质蕴涵项做序列表 并在质蕴涵项包含的最小项下面填入符号 即做所谓质蕴涵表 找出那些仅属于一个质蕴涵项的最小项 如m0仅属于P4 m5仅属于P5 m9仅属于P1 m10仅属于P2 m15仅属于P3 并在相应的 处加圆圈 质蕴涵项P1 P5均包含一个不属于其他质蕴涵项的最小项 即它们均包含一个 所以它们均为必要质蕴涵项 并在其左边加 号 质蕴涵表 3 找出函数的最小覆盖在上述的必要质蕴涵项P1 P5中 找出它们所包含的全部最小项 并在相应的最小项上面做记号 从表中可以看出 必要蕴涵项P1 P5包含函数的所有的最小项 也就是说 P1 P5构成了函数的最小覆盖 因此 函数的最简与或式为 化简函数 用Q M法化简函数 函数F的质蕴涵表 行列消去法的规则如下 1 行消去法规则是 保留优势行 消去劣势行 2 列消去法规则是 保留劣势列 消去优势列 优势行和劣势行 若有质蕴涵项i和j两行 其中j行中的 完全包含在i行之中 则称i行为优势行 j行为劣势行 优势列和劣势列 若有最小项mk和ml两列 其中ml中的 完全包含中mk列之中 则称mk为优势列 ml为劣势列