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

1、数字电路与逻辑设计数字电路与逻辑设计张林行张林行第第2 2章：逻辑代数章：逻辑代数2-1 2-1 概述概述2-2 2-2 逻辑代数基本概念逻辑代数基本概念2-3 2-3 逻辑代数定理及规则逻辑代数定理及规则2-4 2-4 逻辑表达式的形式与变换逻辑表达式的形式与变换2-5 2-5 逻辑函数化简逻辑函数化简吉林大学仪器科学与电气工程学院：数字电路与逻辑设计吉林大学仪器科学与电气工程学院：数字电路与逻辑设计2-1 2-1 概述概述逻辑代数是逻辑设计的理论基础和重要数学工具。逻辑代数是逻辑设计的理论基础和重要数学工具。 虽然和普通代数一样也用字母表示变量，虽然和普通代数一样也用字母表示变量，但变量的

2、值只有但变量的值只有“1”1”和和“0”0”两种，两种，所谓所谓逻辑逻辑“1”1”和逻辑和逻辑“0”0”，代表两种相反的，代表两种相反的逻辑状态。逻辑状态。在逻辑代数中只有逻辑乘在逻辑代数中只有逻辑乘（“与与”运算运算），逻辑加（），逻辑加（“或或“运算运算）和求反（和求反（”非非“运算运算）三种基本运算。）三种基本运算。数字电路与逻辑设计：第数字电路与逻辑设计：第2章章 逻辑代数逻辑代数 逻辑代数是一种用于描述客观事物逻辑关逻辑代数是一种用于描述客观事物逻辑关系的数学方法，又称布尔代数系的数学方法，又称布尔代数 (boole(boole algebra)algebra)。 逻辑逻辑指事物因果

3、关系的规律。指事物因果关系的规律。逻辑代数描述客观事物间的逻辑关系，相应的函数逻辑代数描述客观事物间的逻辑关系，相应的函数称逻辑函数，变量称逻辑变量。称逻辑函数，变量称逻辑变量。逻辑变量和逻辑函数的取值都只有两个，逻辑变量和逻辑函数的取值都只有两个，通常用通常用 1和和 0 表示。表示。 与普通代数比较与普通代数比较用字母表示变量，用代数式描述客观事物间的关系。用字母表示变量，用代数式描述客观事物间的关系。 相似处相似处 相异处相异处独立的规律和运算法则。独立的规律和运算法则。 逻辑代数是从逻辑代数是从哲学领域哲学领域中的中的逻辑学逻辑学发展而来的。发展而来的。 18471847年年, ,英国

4、数学家英国数学家乔治乔治布尔布尔(g.boole(g.boole) )提出了用提出了用数学分析方法表示命题陈述的逻辑结构，并成功地将数学分析方法表示命题陈述的逻辑结构，并成功地将形式逻辑归结为一种代数演算，从而诞生了著名的形式逻辑归结为一种代数演算，从而诞生了著名的“布尔代数布尔代数”。 19381938年，年，克劳德克劳德香农香农(c.e.shannon(c.e.shannon) )将布尔代数应将布尔代数应用于电话继电器的开关电路，提出了用于电话继电器的开关电路，提出了“开关代数开关代数”。 随着电子技术的发展，集成电路逻辑门已经取代了随着电子技术的发展，集成电路逻辑门已经取代了机械触点开关

5、，故机械触点开关，故“开关代数开关代数”这个术语已很少使用。这个术语已很少使用。为了与为了与“数字系统逻辑设计数字系统逻辑设计”这一术语相适应，人们这一术语相适应，人们更习惯于把开关代数叫做更习惯于把开关代数叫做逻辑代数逻辑代数。 乔治乔治布尔（布尔（george boolegeorge boole，18151815年年18641864年）年）18151815年年1111月生于英格兰的林肯。他的父亲是皮匠，月生于英格兰的林肯。他的父亲是皮匠，由于家境十分贫寒，无力供他读书。他的学问主由于家境十分贫寒，无力供他读书。他的学问主要来自于自学。年仅要来自于自学。年仅1212岁的布尔就掌握了拉丁文岁的

6、布尔就掌握了拉丁文和希腊语，后来又自学了意大利语和法语。尽管和希腊语，后来又自学了意大利语和法语。尽管他曾考虑想过要当牧师，但最终他还是决定从事他曾考虑想过要当牧师，但最终他还是决定从事教育行业。布尔从教育行业。布尔从1616岁就开始任教，以此维持生岁就开始任教，以此维持生活。在协助养家的同时并为自己受教育而奋斗拼活。在协助养家的同时并为自己受教育而奋斗拼搏。而后来他还开办了自己的学校。搏。而后来他还开办了自己的学校。在备课的时候，布尔不满意当时的数学课本，便决定阅读伟大在备课的时候，布尔不满意当时的数学课本，便决定阅读伟大数学家的论文。在阅读伟大的法国数学家拉格朗日的论文时，数学家的论文。在

7、阅读伟大的法国数学家拉格朗日的论文时，布尔有了变分方面的新发现。变分是数学分析的分支，它处理布尔有了变分方面的新发现。变分是数学分析的分支，它处理的是寻求优化某些参数的曲线和曲面。从的是寻求优化某些参数的曲线和曲面。从2020岁起布尔对数学产岁起布尔对数学产生了浓厚兴趣，广泛涉猎著名数学家牛顿、拉普拉斯、拉格朗生了浓厚兴趣，广泛涉猎著名数学家牛顿、拉普拉斯、拉格朗日等人的数学名著，并写下大量笔记。这些笔记中的思想，日等人的数学名著，并写下大量笔记。这些笔记中的思想，18471847年被用于他的第一部著作年被用于他的第一部著作逻辑的数学分析逻辑的数学分析之中。之中。 18481848年，布尔出版

8、了年，布尔出版了逻辑的数学分析逻辑的数学分析，这是它对符号逻辑诸多贡献中的第一次。这是它对符号逻辑诸多贡献中的第一次。18491849年他被任命位于爱尔兰科克的皇后学院年他被任命位于爱尔兰科克的皇后学院的数学教授。的数学教授。18541854年，他出版了年，他出版了思维的规律思维的规律，这是他，这是他最著名的著作。在这本书中布尔介绍了现在最著名的著作。在这本书中布尔介绍了现在以他的名字命名的布尔代数。布尔撰写了微以他的名字命名的布尔代数。布尔撰写了微分方程和差分方程的课本，这些课本在英国分方程和差分方程的课本，这些课本在英国一直使用到一直使用到1919世纪末。世纪末。 1854 1854年，已

9、经担任柯克大学教授的布尔再次出版年，已经担任柯克大学教授的布尔再次出版思维规律的研究思维规律的研究逻辑与概率的数学理论基础逻辑与概率的数学理论基础。以这两部著作，布尔建立了一门新的数学学科。布尔以这两部著作，布尔建立了一门新的数学学科。布尔强调数学的本质不是探究对象的内容，而是研究其形强调数学的本质不是探究对象的内容，而是研究其形式，因而数学不必限于讨论数和连续量的问题，可由式，因而数学不必限于讨论数和连续量的问题，可由符号表示的一切事物都可纳入数学领域。在布尔代数符号表示的一切事物都可纳入数学领域。在布尔代数里，布尔构思出一个关于里，布尔构思出一个关于0 0和和1 1的代数系统，用基础的的代

10、数系统，用基础的逻辑符号系统描述物体和概念。这种代数不仅广泛用逻辑符号系统描述物体和概念。这种代数不仅广泛用于概率和统计等领域，更重要的是，它为今后数字计于概率和统计等领域，更重要的是，它为今后数字计算机开关电路设计提供了最重要数学方法。算机开关电路设计提供了最重要数学方法。 数字计算机首先来源于理论突破，是逻辑代数为开数字计算机首先来源于理论突破，是逻辑代数为开关电路设计奠定了的数学基础。逻辑代数又称布尔代关电路设计奠定了的数学基础。逻辑代数又称布尔代数，正是以它的创立者数，正是以它的创立者英国数学家布尔而命名英国数学家布尔而命名。19361936年香农在密西根大学获得数学与电气工程学士学位

11、，年香农在密西根大学获得数学与电气工程学士学位，然后进入然后进入mitmit念研究生。念研究生。19381938年香农在年香农在mitmit获得电气工程获得电气工程硕士学位，硕士论文题目是硕士学位，硕士论文题目是继电器与开关电路的符号继电器与开关电路的符号分析分析。当时他已经注意到电话交换电路与布尔代数之。当时他已经注意到电话交换电路与布尔代数之间的类似性，即把布尔代数的间的类似性，即把布尔代数的“真真”与与“假假”和电路系和电路系统的统的“开开”与与“关关”对应起来，并用对应起来，并用1 1和和0 0表示。于是他表示。于是他用布尔代数分析并优化开关电路，这就奠定了数字电路用布尔代数分析并优化

12、开关电路，这就奠定了数字电路的理论基础。哈佛大学的的理论基础。哈佛大学的howard gardnerhoward gardner教授说，教授说，“这这可能是本世纪最重要、最著名的一篇硕士论文。可能是本世纪最重要、最著名的一篇硕士论文。克劳德克劳德香农（香农（claude elwood shannonclaude elwood shannon，1916-20011916-2001）于）于19161916年年4 4月月3030日出生在美国密西根州的伽娄德（日出生在美国密西根州的伽娄德（gaylordgaylord）小镇，当）小镇，当时镇里只有三千居民。香农的父亲是该镇的法官，母亲是镇里时镇里只有三

13、千居民。香农的父亲是该镇的法官，母亲是镇里的中学校长。他生长在一个有良好教育的环境，不过父母给他的中学校长。他生长在一个有良好教育的环境，不过父母给他的科学影响好像还不如祖父的影响大。香农的祖父是一位农场的科学影响好像还不如祖父的影响大。香农的祖父是一位农场主兼发明家，发明过洗衣机和许多农业机械，这对香农的影响主兼发明家，发明过洗衣机和许多农业机械，这对香农的影响比较直接。此外，香农的家庭与大发明家爱迪生比较直接。此外，香农的家庭与大发明家爱迪生(thomas alva (thomas alva edisonedison，1847-1931)1847-1931)还有远亲关系。还有远亲关系。2-

14、2 2-2 逻辑代数基本概念逻辑代数基本概念数字电路与逻辑设计：第数字电路与逻辑设计：第2章章 逻辑代数逻辑代数逻辑代数逻辑代数l l是一个封闭的代数系统，它由一个是一个封闭的代数系统，它由一个逻辑变量集逻辑变量集k k，常量，常量0 0和和1 1以及以及“或或”、“与与”、“非非”三种基本运算所构成，三种基本运算所构成，记为记为l=k,+,l=k,+, ,- -,0,1,0,1。 2-2-1 逻辑变量及逻辑运算逻辑变量及逻辑运算 逻辑代数和普通代数一样，是用字母表示其值可逻辑代数和普通代数一样，是用字母表示其值可以变化的量，即以变化的量，即变量变量。所不同的是：。所不同的是：1 1在普通代数

15、中，变量的取值可以是任意实数，在普通代数中，变量的取值可以是任意实数，而逻辑代数是一种二值代数系统，而逻辑代数是一种二值代数系统，任何逻辑变量任何逻辑变量的取值只有两种可能：的取值只有两种可能：0 0或或1 1。2 2逻辑值逻辑值0 0和和1 1是用来表征矛盾的双方和判断事是用来表征矛盾的双方和判断事件真伪等的形式符号，而不代表数值大小件真伪等的形式符号，而不代表数值大小。在数。在数字系统中，开关的接通与断开，电压的高和低，字系统中，开关的接通与断开，电压的高和低，信号的有和无，晶体管的导通与截止等两种稳定信号的有和无，晶体管的导通与截止等两种稳定的物理状态，均可用的物理状态，均可用1 1和和

16、0 0这两种不同的逻辑值来这两种不同的逻辑值来表征。表征。 基本逻辑运算：与、或、非基本逻辑运算：与、或、非a bf逻辑式：逻辑式： f=a b=aba. ieeea. ieeeb. b. 标准符号标准符号c. c. 常用符号常用符号&abfffaabb与门：与门：1. 1. 与运算（逻辑乘）与运算（逻辑乘） 0 00 0 10 1 00 1 11真值表真值表 在逻辑问题中，如果决定某一事件发生的在逻辑问题中，如果决定某一事件发生的多个条件必须同时具备，事件才能发生，多个条件必须同时具备，事件才能发生，则这种因果关系称之则这种因果关系称之“与与”逻辑。逻辑。 fbffaaabb逻辑式：

17、逻辑式：f=a +b2. 2. 或运算（逻辑加）或运算（逻辑加）a bf 0 00 0 11 1 01 1 11a. ieeea. ieeeb. b. 标准符号标准符号c. c. 常用符号常用符号在逻辑问题的描述中，如果决定某一事件在逻辑问题的描述中，如果决定某一事件是否发生的多个条件中，只要有一个或一是否发生的多个条件中，只要有一个或一个以上条件成立，事件便可发生，则这种个以上条件成立，事件便可发生，则这种因果关系称之为因果关系称之为“或或”逻辑。逻辑。非门：非门：3. 3. 非运算（逻辑反）非运算（逻辑反）raf 01 10逻辑式：逻辑式：f=af=aa. ieeea. ieeeb. b.

18、 标准标准c. c. 常用常用 在逻辑问题中，如果某一事件的发生取决在逻辑问题中，如果某一事件的发生取决于条件的否定，即事件与事件发生的条件于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果关系称为之间构成矛盾，则这种因果关系称为“非非”逻辑。逻辑。0000111100abf=abf=a+bf=a0001011101110000波形图注意事项：波形图注意事项：1 1、输入波形要穷举所有可能的输入组合、输入波形要穷举所有可能的输入组合(n(n个输入变量由个输入变量由2 2n n种可能种可能) )2 2、输出波形与输入变化对应、输出波形与输入变化对应基本逻辑运算的波形图（时序图）基本逻辑

19、运算的波形图（时序图）复合逻辑运算复合逻辑运算1.1.与非逻辑与非逻辑 abf a ab bf f& 与非门与非门bafa ab bf f2.2.或非逻辑或非逻辑或非门或非门3. 3. 与或非逻辑与或非逻辑cdabf&4.4.异或逻辑异或逻辑bababafa bf0 0 00 1 11 0 11 1 0=1abf=abfbaab a bf0 0 10 1 01 0 01 1 15.5.同或逻辑同或逻辑f=a b=注意：注意： 与、或、与非、或非、与或非为多输与、或、与非、或非、与或非为多输入变量逻辑运算；入变量逻辑运算； 异或、同或为两输入变量逻辑运算；异或、同或为两输入变量逻

20、辑运算；2-2-2 2-2-2 逻辑函数及其表示逻辑函数及其表示 描述描述输入变量输入变量和和输出变量输出变量之间的因果关系。之间的因果关系。1 1逻辑函数和逻辑变量一样，取值只有逻辑函数和逻辑变量一样，取值只有0 0和和1 1两种可能两种可能 ；2 2函数和变量之间的关系是由函数和变量之间的关系是由“或或”、“与与”、“非非”3 3种基本运算决定的。种基本运算决定的。 如果对应于输入逻辑变量如果对应于输入逻辑变量a a、b b、c c、的每的每一组确定值，输出逻辑变量一组确定值，输出逻辑变量y y就有唯一确定就有唯一确定的值，则称的值，则称y y是是a a、b b、c c、的逻辑函数。的逻辑

21、函数。),.,(21naaaff abcf000001001011100110111011断断“0”合合“1”亮亮“1”灭灭“0”c开，开，f灭灭0000c合，合，a、b中中有一个合，有一个合，f亮亮11c合，合，a、b均均断，断，f灭灭0逻辑函数式逻辑函数式 挑出函数值为挑出函数值为1的项的项1 101111101111 每个函数值为每个函数值为1 1的输入变量取值组合写成一个的输入变量取值组合写成一个乘积项乘积项 这些乘积项作这些乘积项作逻辑加逻辑加输入变量取值为输入变量取值为1 1用用原变量原变量表表示示; ;反之，则用反之，则用反变量反变量表示表示abcabc、abcabc、abcab

22、cf= abc+abc+abcabc+abc+abc 逻辑函数的表示方法逻辑函数的表示方法1.1.逻辑表达式逻辑表达式 进行进行“非非”运算可不加括号运算可不加括号 “ “与与”运算符一般可省略运算符一般可省略 运算优先法则运算优先法则:(:(由高到低由高到低) ) 括号，非，与，异或，或括号，非，与，异或，或debabcecdabf)(2.2.真值表真值表 依次列出一个逻辑函数的所有输入变量取依次列出一个逻辑函数的所有输入变量取值组合及其相应函数值的表格称为真值表。值组合及其相应函数值的表格称为真值表。3.3.卡诺图卡诺图4.4.逻辑图逻辑图 用逻辑图形符号表示逻辑运算关系，与逻用逻辑图形符

23、号表示逻辑运算关系，与逻辑电路的实现相对应。辑电路的实现相对应。5.5.其他表示方法（波形图，其他表示方法（波形图，hdlhdl等）等）思考题思考题1、n个逻辑变量进行异或运算，若其中取值为个逻辑变量进行异或运算，若其中取值为1的变量个数为奇数，运算结果为？若其中取值的变量个数为奇数，运算结果为？若其中取值为为1的变量个数为偶数，运算结果为？的变量个数为偶数，运算结果为？2、依据问题、依据问题1，若，若n个变量进行同或运算，运算个变量进行同或运算，运算结果与什么因素有关？结果与什么因素有关？cs2rdwrint3hd7istrba14a15rwintrb有几个输入输出？输出与输入之间有什么关系

24、？有几个输入输出？输出与输入之间有什么关系？3. 某电路逻辑图如下：某电路逻辑图如下：2-3 2-3 逻辑代数定理及规则逻辑代数定理及规则数字电路与逻辑设计：第数字电路与逻辑设计：第2章章 逻辑代数逻辑代数2-3-1 基本定理及公式基本定理及公式定理及公式内容：定理及公式内容：课本课本p40-41（自学）（自学）要求熟记！要求熟记！证明方法：证明方法：1. 利用真值表（穷举）利用真值表（穷举）2. 利用基本定律和公式利用基本定律和公式0-1 律律重叠律重叠律互补律互补律还原律还原律分配律分配律结合律结合律交换律交换律0 aa00 aaa 1aaa 1 aaaa 011 aaaa abba cb

25、acba cabacba abba cbacba )()(cabacba aa 1. 1. 代入规则代入规则 在任何一个包含在任何一个包含a a的逻辑等式中，若以的逻辑等式中，若以另外一个逻辑式代入式中另外一个逻辑式代入式中a a的位置，则等式的位置，则等式依然成立依然成立2-3-2 2-3-2 重要规则及定理重要规则及定理例： a+bc = (a+b)(a+c) a+b(cd) = (a+b)(a+cd)= (a+b)(a+c)(a+d)2 2、反演规则、反演规则 对任一逻辑式对任一逻辑式原变量反变量反变量原变量，0110逻辑式仍然成立（可获得反函数）逻辑式仍然成立（可获得反函数）yy 注意

26、：保持原来的运算顺序注意：保持原来的运算顺序例：例：3. 对偶规则对偶规则 如果将逻辑函数表达式如果将逻辑函数表达式f f中所有的中所有的“”变成变成“+”+”，“+”+”变成变成“”，“0”0”变成变成“1”1”，“1”1”变成变成“0”0”，并保持原函数中的运算顺序不变，则所得到的新的并保持原函数中的运算顺序不变，则所得到的新的逻辑表达式称为函数逻辑表达式称为函数f f的对偶式，并记作的对偶式，并记作ff。若两个逻辑函数表达式若两个逻辑函数表达式f f和和g g相等，则其对偶式相等，则其对偶式ff和和gg也相等。也相等。 cdcbay)(y =？4、展开定理、展开定理,.)1 , 0(,.

27、)0 , 1 (,.)1 , 0(,.)0 , 1 (,.),(fafaffafafaaffadaacabf若：若：则：则：应用：化简逻辑表达式应用：化简逻辑表达式5、摩根定理、摩根定理cbacbacbacba2-4-1 2-4-1 逻辑函数表达式的常用形式逻辑函数表达式的常用形式（一）基本形式：（一）基本形式：n 与与- -或式：或式：是指由若干是指由若干“与项与项”进行进行“或或”运算构成的表达式。运算构成的表达式。 f = a + bc + bdeff = a + bc + bdefn 或或- -与式与式: :是指由若干是指由若干“或项或项”进行进行“与与”运算构成的表达式。运算构成的表

28、达式。 f = a（b+d）（）（c+d+e）注意：基本形式并不唯一注意：基本形式并不唯一 2-4 2-4 逻辑函数表达式的常用形式与标准形式逻辑函数表达式的常用形式与标准形式数字电路与逻辑设计：第数字电路与逻辑设计：第2章章 逻辑代数逻辑代数（二）与非与非式（二）与非与非式 cdabf（三）或非或非式（三）或非或非式dcbaf)(（四）与或非式（四）与或非式cdabf最小项最小项 m m ：m m是乘积项（与项）是乘积项（与项）包含包含n n个变量个变量n n个变量均以原变量或反变量的形式在个变量均以原变量或反变量的形式在m m中出现中出现且仅出现一次且仅出现一次2-4-2 2-4-2 逻辑

29、函数表达式的标准形式逻辑函数表达式的标准形式 最小项最小项之和： 积之和最大项最大项之积： 和之积最小项举例：最小项举例：两变量两变量a, b a, b 的最小项的最小项三变量三变量a,b,c a,b,c 的最小项的最小项）（4个22,abbababa）（8个32,abccabcbacbabcacbacbacba最小项的编号：最小项取值对应编号a b c十进制数0 0 0 0m00 0 1 1m10 1 0 2m20 1 1 3m31 0 0 4m41 0 1 5m51 1 0 6m61 1 1 7m7abccabcbacbabcacbacbacba最小项的性质最小项的性质在输入变量任一取值下

30、，有且仅有一个最小项的值在输入变量任一取值下，有且仅有一个最小项的值为为1 1。全体最小项之和为全体最小项之和为1 1 。任何两个最小项之积为任何两个最小项之积为0 0 。两个相邻的最小项之和可以合并，消去一对因子，两个相邻的最小项之和可以合并，消去一对因子，只留下公共因子。只留下公共因子。-相邻：仅一个变量不同的最小项相邻：仅一个变量不同的最小项n n个变量构成的最小项有个变量构成的最小项有n n个相邻最小项。个相邻最小项。baccbabcacbabcacba)(与逻辑函数最小项之和的形式：逻辑函数最小项之和的形式：例：)7 , 6 , 3()(),(mbcaabccabaabccabbcc

31、abcbay利用公式利用公式可将任何一个函数化为可将任何一个函数化为m m是相加项；是相加项；包含包含n n个因子。个因子。n n个变量均以原变量和反变量的形式在个变量均以原变量和反变量的形式在 m m 中出现一次。中出现一次。如：两变量如：两变量a, b a, b 的最大项的最大项）（4个22,babababa最大项：最大项： 最大项的性质最大项的性质在输入变量任一取值下，有且仅有一个最大在输入变量任一取值下，有且仅有一个最大项的值为项的值为0 0；全体最大项之积为全体最大项之积为0 0；任何两个最大项之和为任何两个最大项之和为1 1；只有一个变量不同的两个最大项（相邻）的只有一个变量不同的

32、两个最大项（相邻）的乘积等于各相同变量之和。乘积等于各相同变量之和。n n变量构成的最大项有变量构成的最大项有n n个相邻最大项。个相邻最大项。最大项的编号：最大项取值对应编号a b c十进制数1 1 17m71 1 06m61 0 15m51 0 04m40 1 13m30 1 02m20 0 11m10 0 00m0cbacbacbacbacbacbacbacba积之和积之和和之积和之积相互转换相互转换kikimmyiimm 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 将一个任意逻辑函数表达式转换成标准表将一个任意逻辑函数表达式转换成标准表达式有两种常用方法，一种是代数转换法，达式有

33、两种常用方法，一种是代数转换法，另一种是真值表转换法。另一种是真值表转换法。2-4-3 逻辑函数表达式的转换逻辑函数表达式的转换1.1.代数转换法代数转换法 利用逻辑代数的公理、定理和规则进行逻利用逻辑代数的公理、定理和规则进行逻辑变换，将函数表达式从一种形式变换为辑变换，将函数表达式从一种形式变换为另一种形式。另一种形式。求一个函数的标准求一个函数的标准“与与- -或或”表达式表达式 第一步：将函数表达式变换成一般第一步：将函数表达式变换成一般“与与- -或或”表达式。表达式。 第二步：反复使用以下定理将表达式中所有非最小第二步：反复使用以下定理将表达式中所有非最小项的项的“与项与项”扩展成

34、最小项。扩展成最小项。 )(babaa求一个函数标准求一个函数标准“或或- -与与”表达式表达式 第一步：将函数表达式转换成一般第一步：将函数表达式转换成一般“或或- -与与”表表达式。达式。 第二步：反复利用下面的定理把表达式中所有第二步：反复利用下面的定理把表达式中所有非最大项的非最大项的“或项或项”扩展成最大项。扩展成最大项。)(babaa2. 2. 真值表转换法真值表转换法 一个逻辑函数的真值表与它的最小项一个逻辑函数的真值表与它的最小项表达式具有一一对应的关系。假定在表达式具有一一对应的关系。假定在函数函数f f的真值表中有的真值表中有k k组变量取值使组变量取值使f f的的值为值为

35、1 1，其他变量取值下，其他变量取值下f f的值为的值为0 0，那，那么，函数么，函数f f的最小项表达式由这的最小项表达式由这k k组变组变量取值对应的量取值对应的k k个最小项相或组成。因个最小项相或组成。因此，可以通过函数的真值表写出最小此，可以通过函数的真值表写出最小项表达式。项表达式。求函数的标准求函数的标准“与与- -或或”式式 方法：真值表上使函数值为方法：真值表上使函数值为1 1的变量取值组合的变量取值组合对应的最小项相对应的最小项相“或或”即可构成一个函数的标准即可构成一个函数的标准“与与- -或或”式。式。求函数的标准求函数的标准“或或- -与与”式式 方法：真值表上使函数

36、值为方法：真值表上使函数值为0 0的变量取值组合的变量取值组合对应的最大项相对应的最大项相“与与”即可构成一个函数的标准即可构成一个函数的标准“或或- -与与”式。式。 实现某一逻辑功能的逻辑电路的复杂性与描述该功实现某一逻辑功能的逻辑电路的复杂性与描述该功能的逻辑表达式的复杂性直接相关。一般说，逻辑能的逻辑表达式的复杂性直接相关。一般说，逻辑函数表达式越简单，设计出来的相应逻辑电路也就函数表达式越简单，设计出来的相应逻辑电路也就越简单越简单。然而，从逻辑问题概括出来的逻辑函数通然而，从逻辑问题概括出来的逻辑函数通常都不是最简的。常都不是最简的。 为了降低系统成本、减小复杂度、提高可靠性，为了

37、降低系统成本、减小复杂度、提高可靠性，必须对逻辑函数进行化简。必须对逻辑函数进行化简。2-5 2-5 逻辑函数化简逻辑函数化简数字电路与逻辑设计：第数字电路与逻辑设计：第2章章 逻辑代数逻辑代数n 逻辑函数的最简形式逻辑函数的最简形式最简与最简与- -或或 表达式中表达式中的与项已经最少；的与项已经最少； 每个与项的因子也最少每个与项的因子也最少最简或最简或- -与与 表达式中的表达式中的“或或”项个数最少；项个数最少； 每个每个“或或”项中的变量个数最少项中的变量个数最少。化简方法化简方法n 代数化简法（公式法）代数化简法（公式法）n 卡诺图法卡诺图法n 列表化简法列表化简法 适合用于计算机

38、化简适合用于计算机化简 （quine-mccluskeyquine-mccluskey算法）算法）2-5-1 2-5-1 代数化简法代数化简法技巧性强，不易确定是否为最简。技巧性强，不易确定是否为最简。常用方法：并项法常用方法：并项法 吸收法吸收法 消去法消去法 配项法配项法)(1bbaababaaaabaaa参考教材参考教材 p43-45p43-45思考题思考题)(cbadcbddbcfdefgefbacefbdcaabdaadycbbdabcdbcabddabcy利用公式法化简以下函数利用公式法化简以下函数2-5-2 卡诺图化简法卡诺图化简法 卡诺图是用来化简逻辑函数的卡诺图是用来化简逻辑

39、函数的,由英由英国工程师国工程师karnaugh首先提出的首先提出的,也称卡也称卡诺图为诺图为k图。图。 卡诺图是将最小项按一定规律卡诺图是将最小项按一定规律排列的方格图，每一个最小项排列的方格图，每一个最小项占有一个小方格。占有一个小方格。 卡诺图的构成：卡诺图的构成： 卡诺图是将最小项按一定规律排列的方格图，卡诺图是将最小项按一定规律排列的方格图，每一个最小项占有一个小方格。设变量数为每一个最小项占有一个小方格。设变量数为n n，则最小项的数目为则最小项的数目为2 2n n ，相应的方格数也为，相应的方格数也为2 2n n 。 n变量卡诺图作法：变量卡诺图作法：1. 将将n个变量分配在横、

40、纵两个方向上，变量个变量分配在横、纵两个方向上，变量排列顺序自行约定。排列顺序自行约定。2. 依据横纵方向的变量个数形成依据横纵方向的变量个数形成k行，行，l列。列。3. 假定横向分配假定横向分配p个变量，纵向分配个变量，纵向分配q个变个变量（量（p+q=n),则则k=2q, l=2p4. 3. 按横纵两个方向标记变量取值的组合，按横纵两个方向标记变量取值的组合，按照格雷码顺序排列。按照格雷码顺序排列。ababa ba ba ba b( )a11000 00 11 01 1( )bab012310000111( )b10bca00000110011010001111110101326754(

41、)aaabcbcbcbca bc aaabcbcbca bc a bc a bc a bcaabbc 建立多于二变量的卡诺图，则每增加建立多于二变量的卡诺图，则每增加一个逻辑变量就一个逻辑变量就以原卡诺图的右边线以原卡诺图的右边线（或底线）为对称轴作一对称图形（或底线）为对称轴作一对称图形，对称轴左面（或上面）原数字前增加对称轴左面（或上面）原数字前增加一个一个0，对称轴右面（或下面）原数字，对称轴右面（或下面）原数字前增加一个前增加一个1。cab0100011110 m0 m2 m4 m6 m1 m3 m5 m7000111100001 11 1004 8 121 5 9133 7 11 1

42、5 2 6 10 14cdab三三变变量量四四变变量量增加的变量增加的变量 卡诺图的特性（化简原理）卡诺图的特性（化简原理）逻辑相邻性体现在卡诺图上，表现为以下几种形式逻辑相邻性体现在卡诺图上，表现为以下几种形式相接（有公共的边），相对（两侧），相重相接（有公共的边），相对（两侧），相重000111100132675412131514891110a bcd000111100000010011001000001001101110101000110111111110110001010111011001abcbcdabd逻辑相邻的两个最小项相加，可以消去一个逻辑相邻的两个最小项相加，可以消去一个相异

43、的变量。相异的变量。消异存同消异存同2 个相邻个相邻最小项有最小项有 1 个变量相异，相加可以个变量相异，相加可以消消去去这这 1 个变量个变量，化简结果为相同变量的与；，化简结果为相同变量的与；4 个相邻个相邻最小项有最小项有 2 个变量相异，相加可以消个变量相异，相加可以消去这去这 2 个变量个变量，化简结果为相同变量的与；，化简结果为相同变量的与；8 个相邻最小项有个相邻最小项有 3 个变量相异，相加可以消个变量相异，相加可以消去这去这 3 个变量，化简结果为相同变量的与；个变量，化简结果为相同变量的与；2n 个相邻最小项有个相邻最小项有 n 个变量相异，相加可以个变量相异，相加可以消去

44、这消去这 n 个变量，化简结果为相同变量的与。个变量，化简结果为相同变量的与。 卡诺图中变量的原区与反区卡诺图中变量的原区与反区000111100001 11 1004 8 121 5 9133 7 11 15 2 6 10 14cdab原区：变量取值为原区：变量取值为1 1的区域。的区域。反区：变量取值为反区：变量取值为0 0的区域。的区域。000111100001 11 1004 8 121 5 9133 7 11 15 2 6 10 14cdab 利用卡诺图化简逻辑函数的步骤利用卡诺图化简逻辑函数的步骤1、将逻辑函数用卡诺图表示；、将逻辑函数用卡诺图表示；2、圈圈：将逻辑相邻且函数值为、

45、圈圈：将逻辑相邻且函数值为1的小方格的小方格圈起来（卡诺圈）；圈起来（卡诺圈）；3、选出必要的卡诺圈，写出其对应的与项，、选出必要的卡诺圈，写出其对应的与项，这些与项的逻辑和就是该函数最简化的与这些与项的逻辑和就是该函数最简化的与或表达式。或表达式。求最简与或式求最简与或式一、将逻辑函数用卡诺图表示一、将逻辑函数用卡诺图表示1、逻辑函数以真值表形式给出、逻辑函数以真值表形式给出将真值表中每一行的取值填入卡诺图对应的方格。将真值表中每一行的取值填入卡诺图对应的方格。a b cf0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 100010101cab010001111

46、0 0 0 0 0 011 1abc0100011110 11 12、逻辑函数为标准与、逻辑函数为标准与-或式或式 将逻辑函数的将逻辑函数的最小项最小项在卡诺图上相应的方在卡诺图上相应的方格中格中填填1；其余的方格填；其余的方格填0(或不填或不填)。f=m(0,2,6,8,10,13,15)000111100001 11 101 1 1 1 1 1 1 cdab3、逻辑函数为一般与或式、逻辑函数为一般与或式化为标准与化为标准与-或式后填入卡诺图；或式后填入卡诺图；将与项直接填入卡诺图：将与项直接填入卡诺图： 找出与项中的变量组合取找出与项中的变量组合取1时所对应的行和列，时所对应的行和列，其公

47、共部分（交叉部分）填其公共部分（交叉部分）填1。abdcdadcbap),(00011110abcd000111101111001111371511134、逻辑函数为标准或、逻辑函数为标准或-与式与式 化为标准与化为标准与-或式；或式； 将逻辑函数的最大项在卡诺图上相应的方将逻辑函数的最大项在卡诺图上相应的方格中填格中填0 (或不填或不填) ；其余的方格填；其余的方格填1。)5 , 2 , 0(),(ymcbacab0100011110 0 0 1 1 110 15、逻辑函数为一般或与式、逻辑函数为一般或与式化为化为2-4中的形式后填入卡诺图；中的形式后填入卡诺图；将或项直接填入卡诺图：将或项

48、直接填入卡诺图： 找出或项中的变量组合取找出或项中的变量组合取0时所对应的行和列，时所对应的行和列，其公共部分（交叉部分）填其公共部分（交叉部分）填0（或不填），其余部分（或不填），其余部分填填1。cab000011110 0 0 0 0 01 1f=c ( a + b )11 其他非标准形式可利用公式将其转化为其他非标准形式可利用公式将其转化为 2-5之之中的形式。中的形式。f=c (a+b) =m(1,5,7)=m(0,2,3,4,6)二、圈圈。二、圈圈。将几何相邻的将几何相邻的1方格用圈圈起来（卡诺圈）。方格用圈圈起来（卡诺圈）。1、卡诺圈中包含的小方格数量必须为、卡诺圈中包含的小方格数

49、量必须为2m, 0mn(n为变量个数为变量个数)。2、卡诺圈的个数尽量少；、卡诺圈的个数尽量少；3、卡诺圈尽量大（圈的方格数量尽量多）；、卡诺圈尽量大（圈的方格数量尽量多）；4、1方格可以重复圈，但必须包含新的方格可以重复圈，但必须包含新的1方格；方格；5、必须保证所有的、必须保证所有的1方格都被圈中。方格都被圈中。圈圈要诀：圈圈要诀：1、先圈小圈；、先圈小圈；2、将小圈看作一个整体，若存在相邻关系，、将小圈看作一个整体，若存在相邻关系，可以将其圈成一个更大的圈；可以将其圈成一个更大的圈；3、依次进行，直到不能圈更大的圈为止；、依次进行，直到不能圈更大的圈为止；4、相邻关系可以采用镜像对称的方式观察，、相邻关系可以采用镜像对称的方式观察，对称轴为方格的各条边（横、纵）。若对对称轴为方格的各条边（横、纵）。若对称则相邻。称则相邻。三、选出必要的卡诺圈，写出其对应的与项，三、选出必要的卡诺圈，写出其对应的与项，这些与项的逻辑和就是该函数最简化的与这些与项的逻辑和就是该函数最简化的与-或或表达式。表达式。蕴涵项：卡诺图上的每个卡诺圈对应的与项。蕴涵项：卡诺图上的每个卡诺圈对应的与项。质蕴涵项：若卡诺圈不能被其他更大的圈所包质蕴涵项：若卡诺圈不能被其他更大的圈所包含，该卡诺圈所对应的与项；含，该卡诺圈所对应的与项；必要