《逻辑代数基础》PPT课件.ppt

第二章 逻辑代数基础,逻辑代数系统（布尔代数系统） 逻辑代数定义,K： 逻辑变量的集合 0,1： 是系统的两个常量 ，+, ：定义了3种逻辑运算 运算优先级由高到低：，+,第二章 逻辑代数基础,公理系统 01律 互补律 交换律 结合律 分配律,第二章 逻辑代数基础,根据以上公理推导出下面几个基本公式： 0-1律 证明： 同理可证：,第二章 逻辑代数基础,重迭律： 对合律 ： 以上8个表达式，我们通常把它们称为逻辑代数的基本公式,第二章 逻辑代数基础,逻辑函数及逻辑函数的表示 逻辑函数的表达式表示 与或范式（标准形式之一） 最小项定义 ：一个具有n个变量的逻辑函数，若与或表达式中的一个乘积项包含n个变量，每个变量以原变量或以反变量形式出现，且仅出现一次，那么这个乘积项称为该函数的一个最小项。,如当： 最小项： 符号表示：,第二章 逻辑代数基础,最小项性质 任意一个最小项，只有一组变量取值使其为1 任意两个最小项之积必为0 n个变量所有最小项之和为1,第二章 逻辑代数基础,与或范式（最小项表达式） 由给定函数的最小项之和组成的逻辑表达式，称为该函数的与或范式,第二章 逻辑代数基础,或与范式（标准形式之二） 一个具有n个变量的逻辑函数，若或与表达式中的一个和项包含n个变量，每个变量以原变量或反变量的形式出现，且仅出现一次，那么这个和项称为该逻辑函数的最大项。 如当： 最大项： 符号表示：,第二章 逻辑代数基础,最大项性质 对于任意一个最大项，只有一组变量取值可使其值为0 任意两个最大项之和必为1 所有个最大项之积必为0 对应最大项与最小项互补,第二章 逻辑代数基础,或与范式 由给定函数的最大项之积所组成的逻辑表达式，称为该函数的或与范式 。,第二章 逻辑代数基础,逻辑函数的真值表表示,最小项 最大项,第二章 逻辑代数基础,真值表的每一行对应一个最小项，函数的与或范式是由那些F1的最小项之和组成。 上例中： 真值表的每一行对应一个最大项，足标与最小项一致，函数的或与范式是由那些F0的最大项之积组成。 上例中：,第二章 逻辑代数基础,逻辑函数的卡诺图表示 卡诺图的构成方法 卡诺图构造形式：源于真值表，是真值表的图形表示，函数的最小项在真值表中按一维空间排列，而在卡诺图中按二维空间分布。 卡诺图隐含着逻辑运算，运算概念：取之于文氏（Venn）图，即集合运算的图形表示。,第二章 逻辑代数基础,变量的卡诺图,第二章 逻辑代数基础,第二章 逻辑代数基础,第二章 逻辑代数基础,逻辑函数在卡诺图中的表示 卡诺图中每一个小方块对应一个最小项，第i个小方块代表mi最小项。 最大项是卡诺图中除mi以外的所有小方块组成的区域,第二章 逻辑代数基础,用“与或”或“或与”式直接填卡诺图,第二章 逻辑代数基础,第二章 逻辑代数基础,逻辑代数的主要定理及常用公式 逻辑代数主要定理 德摩根（De Morgan）定理（反演律） 证明：先引出一条引理,第二章 逻辑代数基础,德摩根定理的一般形式：,第二章 逻辑代数基础,香农（Shannon）定理 香农定理是德摩根定理的推广，有时我们也称为反演规则。 例1： 例2：,第二章 逻辑代数基础,对偶定理 对偶定义： 例1： 例2：,第二章 逻辑代数基础,对偶定理 推理1：原函数与其对偶函数互为对偶函数，即。 推理2：两个相等函数的对偶函数必相等,第二章 逻辑代数基础,逻辑代数的常用公式 项合并 项吸收 因子吸收,第二章 逻辑代数基础,包含律 异或和同或运算,第二章 逻辑代数基础,逻辑函数的化简 代数化简 与或式化简,第二章 逻辑代数基础,第二章 逻辑代数基础,第二章 逻辑代数基础,第二章 逻辑代数基础,或与式化简 两种化简方法： 利用或与公式化简 利用对偶式化简,第二章 逻辑代数基础,卡诺图化简法 卡诺图化简与或表达式 块相邻几何相邻 、相对 、相重,第二章 逻辑代数基础,块合并块递归合并 块合并条件 块的维数相同 、满足相邻条件 卡诺图化简 用卡诺图表示一个给定函数 找出所有的素项和实质素项 求函数的最小复盖 蕴涵项（implicant）：函数的任何2i个相邻小方块组成的合并块称为蕴涵项。卡诺图中任何一个最小项和任何一个合并块都是蕴涵项，或者说函数与或表达式中任何一个乘积项都是蕴涵项。,第二章 逻辑代数基础,素项（prime implicant）：若函数的一个蕴涵项不是该函数其他任何蕴涵项的一个子集，则此蕴涵项称为素项。 实质素项（essential prime implicant）：若函数的一个素项所包含的一个最小项，没有被其它任何素项所包含，则此素项称为实质素项。,第二章 逻辑代数基础,第二章 逻辑代数基础,卡诺图化简或与表达式 将与或表达式化简成或与表达式,第二章 逻辑代数基础,将或与表达式化简成或与表达式,第二章 逻辑代数基础,列表化简法（Quine-McCluskey法） Q-M法具有普遍适用性，是卡诺图方法的一种补充，当变量个数6时一般都采用Q-M法。Q-M法实际上是一种算法，适用于计算机实现。 化简原理相同：只有一个变量不同的二个相邻项合并 化简过程类似：相邻蕴涵项项合并求所有素项求实质素项最小覆盖。 将逻辑函数F展开成与或范式,第二章 逻辑代数基础,分组 ：按最小项下标二进制表示中“1”的个数分组,第二章 逻辑代数基础,相邻项合并求素项,第二章 逻辑代数基础,寻找实质素项,第二章 逻辑代数基础,求函数最小覆盖,第二章 逻辑代数基础,行列消去法 优势行规则：设Pi Pj是简化覆盖表中 二个素项的对应行，若Pi行中所有的 “”都包含在Pj行中，则Pi为劣势行， Pj为优势行。 操作：删除劣势行，保留优势行。 优势列规则 ：设mi mj是简化覆盖表中 二个最小项所对应的列，若mi列中所有 的“”都包含在mj列中，则mi列为劣势 列，mj列为优势列。 操作：删除优势列，保留劣势列。,第二章 逻辑代数基础,第二章 逻辑代数基础,代数法 ： 目的：要