数字电路与逻辑设计

数字电路与逻辑设计,张林行,第2章：逻辑代数,2-1概述2-2逻辑代数基本概念2-3逻辑代数定理及规则2-4逻辑表达式的形式与变换2-5逻辑函数化简,吉林大学仪器科学与电气工程学院：数字电路与逻辑设计,2-1概述,数字电路与逻辑设计：第2章逻辑代数,逻辑代数是从哲学领域中的逻辑学发展而来的。1847年,英国数学家乔治布尔(G.Boole)提出了用数学分析方法表示命题陈述的逻辑结构，并成功地将形式逻辑归结为一种代数演算，从而诞生了著名的“布尔代数”。1938年，克劳德香农(C.E.Shannon)将布尔代数应用于电话继电器的开关电路，提出了“开关代数”。随着电子技术的发展，集成电路逻辑门已经取代了机械触点开关，故“开关代数”这个术语已很少使用。为了与“数字系统逻辑设计”这一术语相适应，人们更习惯于把开关代数叫做逻辑代数。,乔治布尔（GeorgeBoole，1815年1864年）,克劳德香农（ClaudeElwoodShannon，1916-2001）,逻辑代数是逻辑设计的理论基础和重要数学工具。,2-2逻辑代数基本概念,数字电路与逻辑设计：第2章逻辑代数,逻辑代数L是一个封闭的代数系统，它由一个逻辑变量集K，常量0和1以及“与”、“或”、“非”三种基本运算所构成，记为L=K,+,-,0,1。,2-2-1逻辑变量及逻辑运算,逻辑代数和普通代数一样，是用字母表示其值可以变化的量，即变量。所不同的是：1在普通代数中，变量的取值可以是任意实数，而逻辑代数是一种二值代数系统，任何逻辑变量的取值只有两种可能：0或1。2逻辑值0和1是用来表征矛盾的双方和判断事件真伪等的形式符号，而不代表数值大小。,基本逻辑运算：与、或、非,AB,F,逻辑式：F=AB=AB,与门：,1.与运算（逻辑乘）,00,0,01,0,10,0,11,1,真值表,在逻辑问题中，如果决定某一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之“与”逻辑。,1,F,B,F,F,A,A,A,B,B,逻辑式：F=A+B,2.或运算（逻辑加）,AB,F,00,0,01,1,10,1,11,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.异或逻辑,AB,F,000011101110,AB,F,001010100111,5.同或逻辑F=AB=,注意：与、或、与非、或非、与或非为多输入变量逻辑运算；异或、同或为两输入变量逻辑运算；,2-2-2逻辑函数及其表示,描述输入变量和输出变量之间的因果关系。,1逻辑函数和逻辑变量一样，取值只有0和1两种可能；2函数和变量之间的关系是由“或”、“与”、“非”3种基本运算决定的。,如果对应于输入逻辑变量A、B、C、的每一组确定值，输出逻辑变量Y就有唯一确定的值，则称Y是A、B、C、的逻辑函数。,输入(input)A1,A2An输出(output)F,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基本定理及公式,定理及公式内容：要求熟记！,证明方法：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代数化简法,技巧性强，不易确定是否为最简。常用方法：并项法吸收法消去法配项法,思考题,利用公式法化简以下函数,2-5-2卡诺图化简法,卡诺图是用来化简逻辑函数的,由英国工程师Karnaugh首先提出的,也称卡诺图为K图。,卡诺图是将最小项按一定规律排列的方格图，每一个最小项占有一个小方格。,卡诺图的构成：,卡诺图是将最小项按一定规律排列的方格图，每一个最小项占有一个小方格。设变量数为n，则最小项的数目为2n，相应的方格数也为2n。,将n变量的全部最小项各用一个小方块表示，并使具有逻辑相邻性的最小项在几何位置上也相邻地排列起来。,n变量卡诺图作法：,将n个变量分配在横、纵两个方向上，变量排列顺序自行约定。依据横纵方向的变量个数形成K行，L列。假定横向分配p个变量，纵向分配q个变量（p+q=n),则K=2q,L=2p3.按横纵两个方向标记变量取值的组合，按照格雷码顺序排列。,A,A,B,BC,建立多于二变量的卡诺图，则每增加一个逻辑变量就以原卡诺图的右边线（或底线）为对称轴作一对称图形，对称轴左面（或上面）原数字前增加一个0，对称轴右面（或下面