吉林大学《数字电路设计基础》课程 —— 逻辑代数.ppt

数字电路与逻辑设计,张林行,第2章：逻辑代数,2-1 概述 2-2 逻辑代数基本概念 2-3 逻辑代数定理及规则 2-4 逻辑表达式的形式与变换 2-5 逻辑函数化简,吉林大学仪器科学与电气工程学院：数字电路与逻辑设计,2-1 概述,逻辑代数是逻辑设计的理论基础和重要数学工具。 虽然和普通代数一样也用字母表示变量，但变量的值只有“1”和“0”两种，所谓逻辑“1”和逻辑“0”，代表两种相反的逻辑状态。在逻辑代数中只有逻辑乘（“与”运算），逻辑加（“或“运算）和求反（”非“运算）三种基本运算。,数字电路与逻辑设计：第2章 逻辑代数,逻辑代数是一种用于描述客观事物逻辑关系的数学方法，又称布尔代数 (Boole Algebra)。 逻辑指事物因果关系的规律。,乔治布尔（George Boole，1815年1864年）1815年11月生于英格兰的林肯。他的父亲是皮匠，由于家境十分贫寒，无力供他读书。他的学问主要来自于自学。年仅12岁的布尔就掌握了拉丁文和希腊语，后来又自学了意大利语和法语。尽管他曾考虑想过要当牧师，但最终他还是决定从事教育行业。布尔从16岁就开始任教，以此维持生活。在协助养家的同时并为自己受教育而奋斗拼搏。而后来他还开办了自己的学校。,在备课的时候，布尔不满意当时的数学课本，便决定阅读伟大数学家的论文。在阅读伟大的法国数学家拉格朗日的论文时，布尔有了变分方面的新发现。变分是数学分析的分支，它处理的是寻求优化某些参数的曲线和曲面。从20岁起布尔对数学产生了浓厚兴趣，广泛涉猎著名数学家牛顿、拉普拉斯、拉格朗日等人的数学名著，并写下大量笔记。这些笔记中的思想，1847年被用于他的第一部著作逻辑的数学分析之中。,1848年，布尔出版了逻辑的数学分析，这是它对符号逻辑诸多贡献中的第一次。 1849年他被任命位于爱尔兰科克的皇后学院的数学教授。 1854年，他出版了思维的规律，这是他最著名的著作。在这本书中布尔介绍了现在以他的名字命名的布尔代数。布尔撰写了微分方程和差分方程的课本，这些课本在英国一直使用到19世纪末。,1854年，已经担任柯克大学教授的布尔再次出版思维规律的研究逻辑与概率的数学理论基础。以这两部著作，布尔建立了一门新的数学学科。布尔强调数学的本质不是探究对象的内容，而是研究其形式，因而数学不必限于讨论数和连续量的问题，可由符号表示的一切事物都可纳入数学领域。在布尔代数里，布尔构思出一个关于0和1的代数系统，用基础的逻辑符号系统描述物体和概念。这种代数不仅广泛用于概率和统计等领域，更重要的是，它为今后数字计算机开关电路设计提供了最重要数学方法。 数字计算机首先来源于理论突破，是逻辑代数为开关电路设计奠定了的数学基础。逻辑代数又称布尔代数，正是以它的创立者英国数学家布尔而命名。,1936年香农在密西根大学获得数学与电气工程学士学位，然后进入MIT念研究生。1938年香农在MIT获得电气工程硕士学位，硕士论文题目是继电器与开关电路的符号分析。当时他已经注意到电话交换电路与布尔代数之间的类似性，即把布尔代数的“真”与“假”和电路系统的“开”与“关”对应起来，并用1和0表示。于是他用布尔代数分析并优化开关电路，这就奠定了数字电路的理论基础。哈佛大学的Howard Gardner教授说，“这可能是本世纪最重要、最著名的一篇硕士论文。,克劳德香农（Claude Elwood Shannon，1916-2001）于1916年4月30日出生在美国密西根州的伽娄德（Gaylord）小镇，当时镇里只有三千居民。香农的父亲是该镇的法官，母亲是镇里的中学校长。他生长在一个有良好教育的环境，不过父母给他的科学影响好像还不如祖父的影响大。香农的祖父是一位农场主兼发明家，发明过洗衣机和许多农业机械，这对香农的影响比较直接。此外，香农的家庭与大发明家爱迪生(Thomas Alva Edison，1847-1931)还有远亲关系。,2-2 逻辑代数基本概念,数字电路与逻辑设计：第2章 逻辑代数,逻辑代数L是一个封闭的代数系统，它由一个逻辑变量集K，常量0和1以及“或”、“与”、“非”三种基本运算所构成， 记为L=K,+,-,0,1。,2-2-1 逻辑变量及逻辑运算,逻辑代数和普通代数一样，是用字母表示其值可以变化的量，即变量。所不同的是： 1在普通代数中，变量的取值可以是任意实数，而逻辑代数是一种二值代数系统，任何逻辑变量的取值只有两种可能：0或1。 2逻辑值0和1是用来表征矛盾的双方和判断事件真伪等的形式符号，而不代表数值大小。在数字系统中，开关的接通与断开，电压的高和低，信号的有和无，晶体管的导通与截止等两种稳定的物理状态，均可用1和0这两种不同的逻辑值来表征。,基本逻辑运算：与、或、非,A B,F,逻辑式： F=A B=AB,与门：,1. 与运算（逻辑乘）,0 0,0,0 1,0,1 0,0,1 1,1,真值表,在逻辑问题中，如果决定某一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之“与”逻辑。,1,F,B,F,F,A,A,A,B,B,逻辑式：F=A +B,2. 或运算（逻辑加）,A B,F,0 0,0,0 1,1,1 0,1,1 1,1,在逻辑问题的描述中，如果决定某一事件是否发生的多个条件中，只要有一个或一个以上条件成立，事件便可发生，则这种因果关系称之为“或”逻辑。,非门：,3. 非运算（逻辑反）,R,A,F,0,1,1,0,在逻辑问题中，如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果关系称为“非”逻辑。,0,0,0,0,1,1,1,1,0,0,A,B,0,0,0,1,0,1,1,1,0,1,1,1,0,0,0,0,波形图注意事项：,1、输入波形要穷举所有可能的输入组合(n个输入变量由2n种可能),2、输出波形与输入变化对应,基本逻辑运算的波形图（时序图）,复合逻辑运算,1.与非逻辑,与非门,或非门,3. 与或非逻辑,4.异或逻辑,A B,F,0 0 0 0 1 1 1 0 1 1 1 0,A B,F,0 0 1 0 1 0 1 0 0 1 1 1,5.同或逻辑 F=A B=,注意： 与、或、与非、或非、与或非为多输入变量逻辑运算； 异或、同或为两输入变量逻辑运算；,2-2-2 逻辑函数及其表示,描述输入变量和输出变量之间的因果关系。,1逻辑函数和逻辑变量一样，取值只有0和1两种可能 ； 2函数和变量之间的关系是由“或”、“与”、“非”3种基本运算决定的。,如果对应于输入逻辑变量A、B、C、的每一组确定值，输出逻辑变量Y就有唯一确定的值，则称Y是A、B、C、的逻辑函数。,F,断“0”,合“1”,亮“1”,灭“0”,0,0,0,0,1,1,0, 挑出函数值为1的项,1, 每个函数值为1的输入变量取值组合写成一个乘积项, 这些乘积项作逻辑加,逻辑函数的表示方法,1.逻辑表达式 进行“非”运算可不加括号 “与”运算符一般可省略 运算优先法则:(由高到低) 括号，非，与，异或，或,2.真值表 依次列出一个逻辑函数的所有输入变量取值组合及其相应函数值的表格称为真值表。 3.卡诺图 4.逻辑图 用逻辑图形符号表示逻辑运算关系，与逻辑电路的实现相对应。 5.其他表示方法（波形图，HDL等）,思考题,1、n个逻辑变量进行异或运算，若其中取值为1的变量个数为奇数，运算结果为？若其中取值为1的变量个数为偶数，运算结果为？ 2、依据问题1，若n个变量进行同或运算，运算结果与什么因素有关？,有几个输入输出？输出与输入之间有什么关系？,3. 某电路逻辑图如下：,2-3 逻辑代数定理及规则,数字电路与逻辑设计：第2章 逻辑代数,2-3-1 基本定理及公式,定理及公式内容：课本P40-41（自学） 要求熟记！,证明方法： 1. 利用真值表（穷举） 2. 利用基本定律和公式,0-1 律,重叠律,互补律,还原律,分配律,结合律,交换律,1. 代入规则 在任何一个包含A的逻辑等式中，若以另外一个逻辑式代入式中A的位置，则等式依然成立,2-3-2 重要规则及定理,例： A+BC = (A+B)(A+C) A+B(CD) = (A+B)(A+CD) = (A+B)(A+C)(A+D),2、反演规则 对任一逻辑式,逻辑式仍然成立（可获得反函数）,注意：保持原来的运算顺序,例：,3. 对偶规则,如果将逻辑函数表达式F中所有的“”变成“+”，“+”变成“”，“0”变成“1”，“1”变成“0”，并保持原函数中的运算顺序不变，则所得到的新的逻辑表达式称为函数F的对偶式，并记作F。 若两个逻辑函数表达式F和G相等，则其对偶式F和G也相等。,CD,C,B,A,Y,+,+,=,),(,Y =？,4、展开定理,若： 则：,应用：化简逻辑表达式,5、摩根定理,2-4-1 逻辑函数表达式的常用形式 （一）基本形式： 与-或式： 是指由若干“与项”进行“或”运算构成的表达式。 F = A + BC + BDEF 或-与式: 是指由若干“或项”进行“与”运算构成的表达式。 F = A（B+D）（C+D+E） 注意：基本形式并不唯一,2-4 逻辑函数表达式的常用形式与标准形式,数字电路与逻辑设计：第2章 逻辑代数,（二）与非与非式,（三）或非或非式,（四）与或非式,最小项 m ： m是乘积项（与项） 包含n个变量 n个变量均以原变量或反变量的形式在m中出现且仅出现一次,对于n变量函数 有2n个最小项,2-4-2 逻辑函数表达式的标准形式 最小项之和： 积之和 最大项之积： 和之积,最小项举例：,两变量A, B 的最小项 三变量A,B,C 的最小项,最小项的编号：,最小项的性质,在输入变量任一取值下，有且仅有一个最小项的值为1。 全体最小项之和为1 。 任何两个最小项之积为0 。 两个相邻的最小项之和可以合并，消去一对因子，只留下公共因子。 -相邻：仅一个变量不同的最小项 n个变量构成的最小项有n个相邻最小项。,逻辑函数最小项之和的形式：,例：,利用公式 可将任何一个函数化为,M是相加项； 包含n个因子。 n个变量均以原变量和反变量的形式在 M 中出现一次。 如：两变量A, B 的最大项,对于n变量函数 有2n个最大项,最大项：,最大项的性质,在输入变量任一取值下，有且仅有一个最大项的值为0； 全体最大项之积为0； 任何两个最大项之和为1； 只有一个变量不同的两个最大项（相邻）的乘积等于各相同变量之和。 n变量构成的最大项有n个相邻最大项。,最大项的编号：,积之和 和之积 相互转换,逻辑函数表达式的标准形式,将一个任意逻辑函数表达式转换成标准表达式有两种常用方法，一种是代数转换法，另一种是真值表转换法。,2-4-3 逻辑函数表达式的转换,代数转换法 利用逻辑代数的公理、定理和规则进行逻辑变换，将函数表达式从一种形式变换为另一种形式。,求一个函数的标准“与-或”表达式 第一步：将函数表达式变换成一般“与-或”表达式。 第二步：反复使用以下定理将表达式中所有非最小项的“与项”扩展成最小项。,求一个函数标准“或-与”表达式 第一步：将函数表达式转换成一般“或-与”表达式。 第二步：反复利用下面的定理把表达式中所有非最大项的“或项”扩展成最大项。,2. 真值表转换法,一个逻辑函数的真值表与它的最小项表达式具有一一对应的关系。假定在函数F的真值表中有k组变量取值使F的值为1，其他变量取值下F的值为0，那么，函数F的最小项表达式由这k组变量取值对应的k个最小项相或组成。因此，可以通过函数的真值表写出最小项表达式。,求函数的标准“与-或”式 方法：真值表上使函数值为1的变量取值组合对应的最小项相“或”即可构成一个函数的标准“与-或”式。 求函数的标准“或-与”式 方法：真值表上使函数值为0的变量取值组合对应的最大项相“与”即可构成一个函数的标准“或-与”式。,实现某一逻辑功能的逻辑电路的复杂性与描述该功能的逻辑表达式的复杂性直接相关。一般说，逻辑函数表达式越简单，设计出来的相应逻辑电路也就越简单。然而，从逻辑问题概括出来的逻辑函数通常都不是最简的。 为了降低系统成本、减小复杂度、提高可靠性，必须对逻辑函数进行化简。,2-5 逻辑函数化简,数字电路与逻辑设计：第2章 逻辑代数,逻辑函数的最简形式 最简与-或 表达式中的与项已经最少； 每个与项的因子也最少,最简或-与 表达式中的“或”项个数最少； 每个“或”项中的变量个数最少。,化简方法 代数化简法（公式法） 卡诺图法 列表化简法 适合用于计算机化简 （Quine-McCluskey算法）,2-5-1 代数化简法,技巧性强，不易确定是否为最简。 常用方法：并项法 吸收法 消去法 配项法,参考教材 P43-45,思考题,利用公式法化简以下函数,2-5-2 卡诺图化简法,卡诺图是用来化简逻辑函数的,由英国工程师Karnaugh首先提出的,也称卡诺图为K图。,卡诺图是将最小项按一定规律排列的方格图，每一个最小项占有一个小方格。,卡诺图的构成：,卡诺图是将最小项按一定规律排列的方格图，每一个最小项占有一个小方格。设变量数为n，则最小项的数目为2n ，相应的方格数也为2n 。,将n变量的全部最小项各用一个小方块表示，并使具有逻辑相邻性的最小项在几何位置上也相邻地排列起来。,n变量卡诺图作法：,将n个变量分配在横、纵两个方向上，变量排列顺序自行约定。 依据横纵方向的变量个数形成K行，L列。 假定横向分配p个变量，纵向分配q个变量（p+q=n),则K=2q, L=2p 3. 按横纵两个方向标记变量取值的组合，按照格雷码顺序排列。,A,A,B,BC,建立多于二变量的卡诺图，则每增加一个逻辑变量就以原卡诺图的右边线（或底线）为对称轴作一对称图形，对称轴左面（或上面）原数字前增加一个0，对称轴右面（或下面）原数字前增加一个1。,三变量,四变量,增加的变量,卡诺图的特性（化简原理）,逻辑相邻性体现在卡诺图上，表现为以下几种形式 相接（有公共的边），相对（两侧），相重,逻辑相邻的两个最小项相加，可以消去一个相异的变量。,消异存同,2 个相邻最小项有 1 个变量相异，相加可以消去这 1 个变量，化简结果为相同变量的与； 4 个相邻最小项有 2 个变量相异，相加可以消去这 2 个变量，化简结果为相同变量的与； 8 个相邻最小项有 3 个变量相异，相加可以消去这 3 个变量，化简结果为相同变量的与； 2n 个相邻最小项有 n 个变量相异，相加可以消去这 n 个变量，化简结果为相同变量的与。,卡诺图中变量的原区与反区,00,01,11,10,00,01,11,10,0,4,8,12,1,5,9,13,3,7,11,15,2,6,10,14,CD,AB,原区：变量取值为1的区域。 反区：变量取值为0的区域。,00,01,11,10,00,01,11,10,0,4,8,12,1,5,9,13,3,7,11,15,2,6,10,14,CD,AB,利用卡诺图化简逻辑函数的步骤,1、将逻辑函数用卡诺图表示； 2、圈圈：将逻辑相邻且函数值为1的小方格圈起来（卡诺圈）； 3、选出必要的卡诺圈，写出其对应的与项，这些与项的逻辑和就是该函数最简化的与或表达式。,求最简与或式,一、将逻辑函数用卡诺图表示,1、逻辑函数以真值表形式给出 将真值表中每一行的取值填入卡诺图对应的方格。,0,0,0,0,0,1,1,1,1,1,1,2、逻辑函数为标准与-或式,将逻辑函数的最小项在卡诺图上相应的方格中填1；其余的方格填0(或不填)。,F=m(0,2,6,8,10,13,15),3、逻辑函数为一般与或式, 化为标准与-或式后填入卡诺图； 将与项直接填入卡诺图： 找出与项中的变量组合取1时所对应的行和列，其公共部分（交叉部分）填1。,4、逻辑函数为标准或-与式, 化为标准与-或式； 将逻辑函数的最大项在卡诺图上相应的方格中填0 (或不填) ；其余的方格填1。,5、逻辑函数为一般或与式, 化为2-4中的形式后填入卡诺图； 将或项直接填入卡诺图： 找出或项中的变量组合取0时所对应的行和列，其公共部分（交叉部分）填0（或不填），其余部分填1。,C,AB,0,00,01,11,10,0,0,0,0,0,1,1,1,1,其他非标准形式可利用公式将其转化为 2-5之中的形式。,二、圈圈。,将几何相邻的1方格用圈圈起来（卡诺圈）。 1、卡诺圈中包含的小方格数量必须为2m, 0mn(n为变量个数)。 2、卡诺圈的个数尽量少； 3、卡诺圈尽量大（圈的方格数量尽量多）； 4、1方格可以重复圈，但必须包含新的1方格； 5、必须保证所有的1方格都被圈中。,圈圈要诀：,1、先圈小圈； 2、将小圈看作一个整体，若存在相邻关系，可以将其圈成一个更大的圈； 3、依次进行，直到不能圈更大的圈为止； 4、相邻关系可以采用镜像对称的方式观察，对称轴为方格的各条边（横、纵）。若对称则相邻。,三、选出必要的卡诺圈，写出其对应的与项，这些与项的逻辑和就是该函数最简化的与-或表达式。,蕴涵项：卡诺图上的每个卡诺圈对应的与项。 质蕴涵项：若卡诺圈不能被其他更大的圈所包含，该卡诺圈所对应的与项； 必要质蕴涵项：卡诺圈中至少有一个1方格不被其他卡诺圈包含，该卡诺圈对应的与项；,1、从卡诺圈中选出至少有一个小格是独立（不被其他卡诺圈所包围）