数字逻辑与逻辑设计课件 第2章 逻辑代数基础.ppt

1、,逻 辑 代 数 基 础,第 二 章,第2章 逻辑代数基础,逻辑代数是数字系统逻辑设计的理论基础和重要数学工具！,1847年,英国数学家乔治布尔(G.Boole)提出了用数学分析方法表示命题陈述的逻辑结构，并将形式逻辑归结为一种代数演，从而诞生了著名的“布尔代数”。 1938年，克劳德向农(C.E.Shannon)将布尔代数应用于电话继电器的开关电路，提出了“开关代数”。 随着电子技术的发展，集成电路逻辑门已经取代了机械触点开关，故人们更习惯于把开关代数叫 做逻辑代数。,2.1 逻辑代数的基本概念,2.2 逻辑代数的基本定理和规则,2.3 逻辑函数表达式的形式与转换,本 章 教 学 内 容,2

2、.4 逻辑函数的化简,2.5 正负逻辑问题,掌握逻辑函数及其表示方法,掌握逻辑函数化简方法 -代数化简法和卡诺图化简法,掌握常用的逻辑运算。,本章的教学目标,掌握逻辑代数的运算公式和重要规则,逻辑代数L是一个封闭的代数系统，它由一个逻辑变量集K，常量0和1以及“或”、“与”、“非”三种基本运算所构成，记为L=K,+,-,0,1。该系统应满足下列公理。,公 理 1 交 换 律 对于任意逻辑变量A、B，有 A + B = B + A；AB = B A,公 理 2 结 合 律 对于任意的逻辑变量A、B、C，有 (A + B) + C = A + ( B + C ) ( AB ) C = A( B C

3、 ),2.1 逻辑代数的基本概念,公 理 3 分 配 律 对于任意的逻辑变量A、B、C，有 A + ( BC ) = (A + B)(A + C) ； A( B + C) = AB + AC,公 理 4 01 律 对于任意逻辑变量A，有 A + 0 = A ； A 1 = A A + 1 = 1 ； A 0 = 0,公理是一个代数系统的基本出发点，无需加以证明。,公 理 5 互 补 律 对于任意逻辑变量A，存在唯一的，使得,（一）逻辑变量,取值：逻辑0、逻辑1。逻辑0和逻辑1不代表数值大小，仅表示相互矛盾、相互对立的两种逻辑状态,（二）基本逻辑运算,与运算,或运算,非运算,一、逻辑变量及基本逻

4、辑运算,与逻辑真值表,与逻辑关系表,1.与逻辑,开关A,开关B,灯F,断 断 断 合 合 断,合 合,灭 灭 灭,亮,A,B,F,1 0,1 1,0 1,0 0,0,0,1,0,基本逻辑运算,一、逻辑变量及基本逻辑运算,只有决定某一事件的所有条件 全部具备，这一事件才能发生,2.1 逻辑代数的基本概念,或逻辑真值表, 1,A,B,F,1 0,1 1,0 1,0 0,1,1,1,0,F= A + B+ .+ N,2.或逻辑,一、逻辑变量及基本逻辑运算,基本逻辑运算,2.1 逻辑代数的基本概念,3.非逻辑,一、逻辑变量及基本逻辑运算,基本逻辑运算,非逻辑真值表,1,A,F,0,1,1,0,2.1

5、逻辑代数的基本概念,（三）复合逻辑运算,与非逻辑运算,或非逻辑运算,与或非逻辑运算,一、逻辑变量及基本逻辑运算,2.1 逻辑代数的基本概念,（三）复合逻辑运算,一、逻辑变量及基本逻辑运算,异或运算,A,B,F,1 0,1 1,0 1,0 0,1,1,0,0,=1,2.1 逻辑代数的基本概念,同或运算,（三）复合逻辑运算,一、逻辑变量及基本逻辑运算,2.1 逻辑代数的基本概念,（一）逻辑函数,用有限个与、或、非逻辑运算符，按某种逻辑关系将逻辑变量A、B、C、.连接起来，所得的表达式F = f（A、B、C、.）称为逻辑函数。,（二）逻辑函数的表示方法,真值表,逻辑函数式,逻辑图,波形图,取值：逻辑

6、0、逻辑1。逻辑0和逻辑1不代表数值大小，仅表示相互矛盾、相互对立的两种逻辑态,二、逻辑函数及其表示方法,2.1 逻辑代数的基本概念,F,断“0”,合“1”,亮“1”,灭“0”,0,0,0,0,1,1,0,1,二、逻辑函数及其表示方法,2.1 逻辑代数的基本概念,逻辑函数式, 挑出函数值为1的项；, 每个函数值为1的输入变量取值组合写成一个乘积项；, 这些乘积项作逻辑加。,二、逻辑函数及其表示方法,2.1 逻辑代数的基本概念,逻辑图,波形图,二、逻辑函数及其表示方法,2.1 逻辑代数的基本概念,三、逻辑函数及其相等概念,（1）逻辑表达式：由逻辑变量和与、或、非3种运算符连接起来所构成的式子。在

7、逻辑表达式中，等式右边的字母A、B、C、D等称为输入逻辑变量，等式左边的字母Y称为输出逻辑变量，字母上面没有非运算符的叫做原变量，有非运算符的叫做反变量。,（2）逻辑函数：如果对应于输入逻辑变量A、B、C、的每一组确定值，输出逻辑变量Y就有唯一确定的值，则称Y是A、B、C、的逻辑函数。记为,注意：与普通代数不同的是，在逻辑代数中，不管是变量还是函数，其取值都只能是0或1，并且这里的0和1只表示两种不同的状态，没有数量的含义。,2.1 逻辑代数的基本概念,（3）逻辑函数相等的概念：设有两个逻辑函数,它们的变量都是A、B、C、，如果对应于变量A、B、C、的任何一组变量取值，Y1和Y2的值都相同，则

8、称Y1和Y2是相等的，记为Y1=Y2。,若两个逻辑函数相等，则它们的真值表一定相同；反之，若两个函数的真值表完全相同，则这两个函数一定相等。因此，要证明两个逻辑函数是否相等，只要分别列出它们的真值表，看看它们的真值表是否相同即可。,证明等式：,2.1 逻辑代数的基本概念,（一）公理、定律与常用公式,公理,交换律,结合律,分配律,0-1律,重叠律,互补律,还原律,反演律,0 0 = 0,0 1 =1 0 =0,1 1 = 1,0+ 0 = 0,0+ 1 =1 + 0 =1,1+ 1 = 1,A B = B A,A+ B = B + A,(A B) C = A (B C),(A+ B)+ C =

9、A+ (B+ C),自等律,A ( B+ C ) = A B+ A C,A+ B C =( A+ B) (A+ C ),A 0=0 A+ 1=1,A 1=A A+ 0=A,A A=A A+ A=A,吸收律,消因律,包含律,合并律,A+A B=A A (A+B)=A,2.2 基本定理和规则,例：,法一,A B,1,1,1,0,1,1,1,0,1,0,0,0,1,0,0,0,证明方法,2.2 基本定理和规则,等式右边,公式可推广：,法二,（二） 三个基本运算规则,任何一个含有某变量的等式，如果等式中所有出现此变量的位置均代之以一个逻辑函数式，则此等式依然成立,得,由此反演律能推广到n个变量：,利用

10、反演律,2.2 基本定理和规则,对于任意一个逻辑函数式F，做如下处理：, 若把式中的运算符“.”换成“+”, “+” 换成“.”;, 常量“0”换成“1”，“1”换成“0”；, 原变量换成反变量，反变量换成原变量,那么得到的新函数式称为原函数式F的反函数式。,（二） 三个基本运算规则,2.2 基本定理和规则,（二） 三个基本运算规则反演规则,注：, 保持原函数的运算次序-先与后或，必要时适当地加入括号, 不属于单个变量上的非号有两种处理方法, 非号保留，而非号下面的函数式按反演规则变换, 将非号去掉，而非号下的函数式保留不变,F(A、B、C),其反函数为,或,例,2.2 基本定理和规则,对于任

11、意一个逻辑函数，做如下处理：,1）若把式中的运算符“.”换成“+”，“+”换成“.”；,2）常量“0”换成“1”，“1”换成“0”,得到新函数式为原函数式F的对偶式F，也称对偶函数,如果两个函数式相等，则它们对应的对偶式也相等。即 若 F1 = F2 则F1= F2。使公式的数目增加一倍。,（二） 三个基本运算规则, 对偶规则,2.2 基本定理和规则,其对偶式,（二）三个基本运算规则对偶规则, 求对偶式时运算顺序不变，且它只变换运算符和常量，其变量是不变的。,注：, 函数式中有“”和“”运算符，求反函数及对偶函数时，要将运算符“”换成“”， “”换成“”。,2.2 基本定理和规则,2.3 逻辑

12、函数表达式形式与转换,函数表达式的常用形式,逻辑函数的标准形式,一、函数表达式的常用形式,（一） 五种常用表达式,F(A、B、C),“与或”式,“或与”式,“与非与非”式,“或非或非”式,“与或非”式,（二） 表达式形式转换,利用还原律,利用反演律,2.3逻辑函数表达式形式与转换,n个变量有2n个最小项，记作mi,3个变量有23（8）个最小项,m0,m1,000,001,0,1,n个变量的逻辑函数中，包括全部n个变量的乘积项（每个变量必须而且只能以原变量或反变量的形式出现一次）,最小项,二进制数,十进制数,编号,（一） 最小项和最大项,0 0 1,A B C,0 0 0,1,0,0,0,0,0

13、,0,0,0,1,0,0,0,0,0,0,1,1,三变量的最小项,最小项的性质：, 同一组变量取值任意两个不同最小项的乘积为0。即mimj=0 (ij)；, 全部最小项之和为1，即,2. 最大项,n个变量有2n个最大项，记作i,n个变量的逻辑函数中，包括全部n个变量的和项（每个变量必须而且只能以原变量或反变量的形式出现一次）, 同一组变量取值任意两个不同最大项的和为1。即Mi+Mj=1 (ij), 全部最大项之积为0，即, 任意一组变量取值，只有一个最大项的值为0，其它最大项的值均为1,二、逻辑函数的标准形式,(二） 最小项与最大项的关系,相同编号的最小项和最大项存在互补关系,即:,mi =,

14、Mi,Mi =,mi,若干个最小项之和表示的表达式F，其反函数F可用等同个与这些最小项相对应的最大项之积表示。,=,=,2.3逻辑函数表达式形式与转换,二、逻辑函数的标准形式,2.3逻辑函数表达式形式与转换,解：F(A、B、C),二、逻辑函数的标准形式,2.3逻辑函数表达式形式与转换, 从真值表找出F为1的对应最小项,解:, 然后将这些项逻辑加,F(A、B、C),二、逻辑函数的标准形式标准积之和( 最小项）表达式,2.3逻辑函数表达式形式与转换, 逻辑电路所用门的数量少, 每个门的输入端个数少, 逻辑电路构成级数少, 逻辑电路保证能可靠地工作,2.4 逻辑函数的简化,代数法化简函数,图解法化简

15、函数,2.4 逻辑函数的简化,本讲的教学目标,1. 理解用代数法化简逻辑函数的方法 2. 掌握图形法化简逻辑函数 3. 了解卡诺图的其他应用 4. 了解逻辑函数简化中几个实际问题的处理思路,2.4 逻辑函数的简化,最简式的标准, 首先是式中乘积项最少,（一） 与或表达式的简化,一、代数法化简函数,与门的输入端个数少, 消项： 利用A + AB = A消去多余的项AB,2.4 逻辑函数的简化,解：,一、代数法化简函数与或表达式的简化,2.4 逻辑函数的简化,一、代数法化简函数,（二）或与表达式的简化,F（或与式）,F（最简与或式）,F（与或式）,F（最简或与式）,2.4 逻辑函数的简化,什么是卡

16、诺图？ 美国工程师卡诺（Karnaugh）提出了一种描述逻辑函数的特殊方法。在这个方格图中，每个小方格代表逻辑函数的一个最小项，而且几何相邻的小方格具有相邻性，即两个相邻小方格所代表的最小项仅一个变量取值不同，这种特殊的小方格图通常称之为卡诺图（K-Map）。,卡诺图实际上相当于一个矩阵式的真值表，不同的是真值表输入变量的取值是从小到大的顺序排列，而卡诺图是循环码的排布规则。,二、图形法化简函数,卡诺图是一种平面方格图，每个小方格代表一个最小项，故又称为最小项方格图。 结构特点：(1) n个变量的卡诺图由2n个小方格构成；(2) 几何图形上处在相邻、相对、相重位置的小方格所代表的最小项为相邻最

17、小项。,卡诺图的构成,卡诺图化简法具有简单、直观、容易掌握等优点，在逻辑设计中得到广泛应用。,2变量、3变量、4变量卡诺图如图(a)、(b)、(c)所示。,DE,000 001 011 010,00 01 11 10,m0 m4 m12 m8,m1 m5 m13 m9,m3 m7 m15 m11,m2 m6 m14 m10,100 101 111 110,00 01 11 10,m16 m20 m28 m24,m17 m21 m29 m25,m19 m23 m31 m27,m18 m22 m30 m26,ABC,(一）卡诺图（K图）,图中的一小格对应真值表中的一行， 即对应一个最小项，又称真值

18、图,A B,0 0,0 1,1 0,1 1,m0,m1,m2,m3,A,B,AB,A,B,1,0,1,0,m0,m1,m2,m3,mi,例如，四变量卡诺图中，如m5的4个相邻最小项分别是和m5相连的 m1，m4，m7，m13。 m2的4个相邻最小项除了与之几何相邻的m3和m6之外，另外两个是处在“相对”位置的m0 ( 同一列的两端)和m10( 同一行的两端)。这种相邻称为相对相邻。,从各卡诺图可以看出，在n个变量的卡诺图中，能从图形上直观、方便地找到每个最小项的n个相邻最小项。,5变量卡诺图如图（d）所示。,此外， 处在“相重”位置的最小项相邻，如五变量卡诺图中的m3，除了几何相邻的m1，m2，m7和相对相邻的m11外，还与m19相邻。这种相邻称为重叠相邻。,用卡诺图化简逻辑函数的基本原理：把卡诺图上表征相邻最小项的相邻小方格“圈”在一起进行合并，达到用一个简单“与”项代替若干最小项的目的。 通常把用来包围那些能由一个简单“与”项代替的若干最小项的“圈”称为卡诺圈。,性质：可以从图形上直观地找出相邻最小项合并。合并的理论依据是并项定理： AB