§2逻辑代数与硬件描述语言基础.ppt

2 逻辑代数与硬件描述语言基础,本章教学内容 本章教学要求 本章重点与难点,教学内容,2.1 逻辑代数 2.2.1 逻辑代数的基本定律和恒等式 2.2.2 逻辑代数的基本规则 2.1.3 逻辑代数的化简 2.2 逻辑函数的卡诺图化简法 2.2.1 最小项的定义及其性质 2.2.2 逻辑函数最小项的表达式 2.2.3 用卡诺图表示逻辑函数 2.2.4 用卡诺图化简逻辑函数 *2.3 硬件描述语言基础 Verilog HDL,教学要求,（l）掌握逻辑代数的基本定律、定理和规则； （2）掌握逻辑函数的表示方法及相互转换方法； （3）掌握逻辑函数的化简方法；,重点与难点：,重点：逻辑代数的基本定律、定理和基本规则。,难点：基本定律、定理和规则的应用。,2.1 逻辑代数,逻辑代数与普通代数相似之处在于它们都是用字母表示变量，用代数式描述客观事物间的关系。但不同的是逻辑代数是描述客观事物间的逻辑关系，逻辑函数表达式中的逻辑变量的取值和逻辑函数值都只有0和1两个值。,逻辑代数是反映逻辑变量运算规律的数学，是数字系统的理论基础和重要的数学工具。,逻辑代数是从哲学领域中的逻辑学发展而来的。1847年，英国数学家乔治布尔(G.Boole)首先提出了用数学分析方法表示命题陈述的逻辑结构，并成功地将形式逻辑归结为一种代数演算，从而诞生了著名的“布尔代数”。,2.1.1 逻辑代数的基本定律和恒等式,表2.1.1 逻辑代数定律、定理和恒等式 (P 40),三个基本规则:,1. 代入规则,2. 反演规则,3. 对偶规则,2.1.2,0-1 律,分配律,结合律,交换律,反演律,吸收律,冗余律,非(反),与（乘）,或（加）,基本定律,常用 恒等式,表2.1.1 逻辑代数定律、定理和恒等式 (P 40),2.1.2,2.1.3,非（反）,与（乘）,或（加）,0-1 律,0-1律: 逻辑常量0和1与逻辑变量间的运算规律。,与普通代数相似的定律,分配律,结合律,交换律,普通代数没有！,证明分配率：A+BA=(A+B)(A+C),(A+B)(A+C)=AA+AB+AC+BC,分配率A(B+C)=AB+AC,=A+AB+AC+BC,0-1律 AA=A,=A(1+B+C)+BC,分配率A(B+C)=AB+AC,=A+BC,0-1率A+1=1,证明：,反演律(摩根定理),证明等式：,吸收律,吸收多余的项,吸收相异的变量,吸收多余的因子,常用恒等式：,1. 代入规则,2.1.2 逻辑代数的基本规则,定义：,作用：,利用代入定理很容易把基本公式推广为多变量的形式。,在任何一个逻辑等式中，如果将等式两边出现某变量的位置，都以同一函数代替，则等式仍然成立，这就是所谓代入规则。,【例1】:用代入规则证明摩根定理二变量，也适用于多变量的情况。,【解】：已知二变量的摩根定理为：,依此类推，摩根定理对任意多个变量都成立。,若在等式两边出现某变量 B 的位置用（BC）代入，则等式仍然成立, 即 ：,定义：对于任意一个逻辑式F，若将其中所 “”换成“”，“”换成“” 0换成1，1互换成0； 原变量换成反变量，反变置换成原变量； 则F就变换成 , 这个规律叫做反演规则。,2. 反演规则,注意：在使用反演规则时还需遵守以下两条： 必需遵守“先括号、然后乘、最后加”的运算优先次序。 不属于单个变量上的反号应保留不变。,作用：,反演规则为求取已知逻辑式的反逻辑式提供了方便。,【例题】：,3. 对偶规则,定义：对于任意一个逻辑式F，若将其中所有的 “”换成“”，“”换成“”， 0换成1，1互换成0； 则F就变换成就变换成 F, 这个规律叫做对偶规则。,注意：在使用对偶规则时还需遵守以下两条： 必需遵守“先括号、然后乘、最后加”的运算优先次序。 不属于单个变量上的反号应保留不变。,利用对偶规则可从已知公式中得到更多的运算公式。,作用：,【例题1】：,P 40 表2.1.1,【例题2】：,2.1.3 逻辑函数的代数化简法,一、逻辑函数的最简与-或表达式,【例】：,(3) 最简与或表达式的特点：,(2) 逻辑函数的化简方法：, 与项（即乘积项）的个数最少； 每个乘积项中变量的个数最少；,(4) 代数法化简逻辑函数的理论依据：,(5) 代数法化简的常用方法： 并项法；吸收法；消去法；配项法。,逻辑代数的基本定律和恒等式。,(1) 逻辑函数化简的意义：逻辑表达式越简单，实现它的电路越简单，电路工作的可靠性相对就越高。,二、 逻辑函数的化简, 代数法； 卡诺图法, 并项法,利用公式 ，将两项合并为一项，并消去一个变量。,化简依据：, 吸收法,利用公式，消去多余的项。,利用公式 ，消去多余的因子。, 消去法, 配项法,利用公式 为某一项配上其所缺的变量，以便用其 它方法进行化简。, 并项法,结论：保留相同的变量，消去相异的变量。, 吸收法,运用摩根定律,利用公式，消去多余的项。,利用公式 ，消去多余的因子。, 消去法,如果一个乘积项的反是另一项的因子，则这个因子是多余的。, 配项法,利用公式 为某一项配上其所缺的变量，以便用其它方法进行化简。,卡诺图：是最小项按相邻规则作出的方框图。 作用：利用卡诺图可以直观而方便地化简逻辑函数。,【例】:对于三变量逻辑还是A、B、C来讲，有8个符合最小项定义的乘积项 除此之外,如： 等项就不是最小项。,2.2 逻辑函数的卡诺图法化简,1. 最小项的定义 在逻辑函数中设有n个逻辑变量，由这n个逻辑变量所组成的乘积项（与项）中的每个变量只以原变量或反变量的形式出现一次，且仅出现一次，那么我们把这个乘积项称为n个变量的一个最小项。,2.2 .1 最小项的定义及其性质,注：变量数与最小项数的关系： n变量的逻辑函数，有2n最小项。,表 2.2.1 三变量最小项真值表,为了分析最小项的性质，列出三变量所有最小项的真值表,如表2.2.1所示。由表2.2.1可知，最小项具有下列性质： (1) 对于任意一个最小项，有且仅有一组变量的取值使它的值等于1； (2) 任意两个不同最小项的乘积恒为0； (3) n变量的所有最小项之和恒为1。,2. 最小项的性质,3. 最小项的编号,最小项中通常用i表示最小项编号(用十进制数表示)。最小项中以原变量形式出现视为1，以反变量形式出现视为0。例如 对应的二进制数为011，对应的十进制数为3，即i=3，所以把 记为 m3 。现将三变量的最小项的编号列于表2.2.2中所示。,任何一个逻辑函数都可以表示成若干个最小项之和的形式，这样形式就是最 小项表达式，而且这种形式是惟一的。获取最小项表达式的方法有两种：,2）由一般逻辑函数式求最小项表达式的方法, 利用公式将表达式变换成一般与或式； 采用配项法，将每个乘积项（与项）都变为最小项。,2.2.2. 逻辑函数最小项表达式(逻辑函数的标准式),1）由真值表求最小项表达式的方法,复习与回顾：,结论：逻辑函数的最小项表达式 是唯一的。（P 48）,2）由一般逻辑函数式求最小项表达式的方法, 利用公式将表达式变换成一般与或式； 采用配项法，将每个乘积项（与项）都变为最小项。,1）由真值表求最小项表达式的方法；,获取最小项表达式的方法有两种：,逻辑相邻：是指两个最小项中除了一个变量取值不同外，其余的都相同，那 么这两个最小项具有逻辑上的相邻性。例如，m3= 和m7=ABC是逻辑相邻的。,几何相邻：是指在卡诺图中排列位置相邻的那些最小项。,2）卡诺图的作法,n个变量的逻辑函数，具有2n个最小项，对应的卡诺图也应有2n个小方块。,三变量卡诺图：,四变量卡诺图：,二变量卡诺图：,2.2.3. 用卡诺图表示逻辑函数,1）卡诺图的特点,求卡诺图的方法：,3） 用卡诺图表示逻辑函数,（A）由真值表求卡诺图。,（B）由最小项表达式求卡诺图。,Y(A，B，C，D)=m（0,1,3,5,6,8,10,11,15）的卡诺图。,（C）根据般逻辑表达式求卡诺图。,1）化简的依据,利用卡诺图合并最小项，实质上就是反复运用公式， 消去相异的变 量，从而得到最简的”与或”式： （1）当2个（21）相邻小方格的最小项合并时，消去1个互反变量； （2）当4个（22）相邻小方格的最小项合并时，消去2个互反变量； （3）当8个（23）相邻小方格的最小项合并时，消去3个互反变量； （4）当2n个相邻小方格的最小项合并时，消去n个互反变量(n为正整数)。,分别画出了相邻2个小方格的最小项项合并的情况。,图 2个最小项的合并,2.2.4 利用卡诺图化简逻辑函数,图8.20 2个最小项的合并,分别画出相邻4个小方格的最小项:,图 4个最小项的合并,图8.22 8个最小项的合并,分别画出相邻8个小方格的最小项:,2) 卡诺图化简法,一般按以下三个步骤进行： (1) 画出逻辑函数的卡诺图； (2) 按合并最小项的规律, 将可以合并的最小项分别用包围圈(复合圈)圈出； (3) 将每个包围圈所得的乘积项相加, 就可得到逻辑函数最简“与或”表达式。,【解】:,【例1.1】: 用卡诺图化简逻辑函数,第三步，将每个包围圈的结果相加，得:,第一步，画出Y的卡诺图,如图所示；,第二步，按合并最小项的规律画出相应的包围圈；,【例题】: 化简 Y（A,B,C,D）=m(3,4,5,7,9,13,14,15)。,最后写出最简与或式为 ：,【解】： 首先画出Y的卡诺图，如图所示。,从上述例题可知，利用卡诺图化简逻辑函数，对最小项画包围圈是比较重要的，包围圈越大，消去的变量数就越多；,注：每个包围圈中必须含2n个相邻小方格,并去掉重复的包围圈。,【例2】：（P53 例2.2.5） 4输入逻辑变量A,B, C, D,它的真值表如表2.2.3所示，用卡诺图法其求最简与一或表达式及与非一与非表达式。,【例3】：（P54 例2.2.6）,最小项应遵循的原则是：,综上所述，复并最小项应遵循的原则是： 按合并最小项的规律，对函数所有的最小项画包围圈； 包围圈的个数要最少，使得函数化简后的乘积项最少； 一般情况下，应使每个包围圈尽可能大，则每个乘积项中变量的个数最少； 最小项可以被重复使用，但每一个包围圈至少要有一个新的最小项（尚未被圈过）。 需要指出的是：用卡诺图化简逻辑函数时，由于对最小项画包围圈的方式不同，得到的最简与或式也往往不同。 卡诺图法化简逻辑函数的优点是简单、直观，容易掌握，但不适用于五变量以上逻辑函数的化简。,(1) 什么是”约束” 在前面所讨论的逻辑函数中，我们认为逻辑变量的取值是独立的，不受其它变量取值的制约。但是，在某些实际问题的逻辑关系中，变量和变量之间存在一定的制约关系。这种相互“制约”的关系就是约束。 例如：A、B、C三个变量只允许出现000、001、010、100四种取值，而011、101、110、111四种取值是不允许出现的。这就说明三个变量A、B、C之间存在着“约束”的关系。就称A、B、C是一组有约束的变量，而不允许出现的四组变量取值组合所对应的最小项称为“约束项”（或称为“任意项”、“禁止项”、“无关项”）。,2.2.5. 具有“约束”的逻辑函数的化简,既然认定约束项对应的变量取值的组合不会出现，那么其函数值是1还是0是没有意义的。也就是说，对应约束项的变量取值时，其函数值可以是任意的，既可以取0，也可以取1，这完全视需要而定，并把相对应的函数值记作“”。,(2) 约束项的意义,在本例中的约束条件为:,约束条件：所有约束项之和，其值恒为0的逻辑表达式，。,(3) 约束条件,(4)具有“约束”的逻辑函数的化简,对于具有“约束”的逻辑函数，可以利用约束项进行化简，使 逻辑表达式更为简单。,【例题】: 设输入A、B、C、D是十进制