第二章逻辑代数基础精选文档.ppt

第二章逻辑代数基础本讲稿第一页，共九十页学习要求学习要求学习要求学习要求：掌握逻辑代数的基本概念，学会用逻辑函描述逻辑问题的基本方法。掌握逻辑代数的公理、基本定理和重要规则；学会用代数法化简逻辑函数；熟练掌握用卡诺图化简逻辑函数。本讲稿第二页，共九十页2.1 2.1 逻辑代数的基本概念逻辑代数的基本概念逻辑代数是一个由逻辑变量集K，常量0和1以及“与”、“或”、“非”3种基本运算构成的一个封闭的代数系统，记为L=K,+,-,0,1。它是一个二值代数系统。常量0和1表示真和假，无大小之分。该系统满足下列公理：本讲稿第三页，共九十页公理公理1交换律交换律 A+B=B+A,A B=B A公理公理2结合律结合律(A+B)+C=A+(B+C),(A B)C=A (B C)公理公理3分配律分配律 A+(B C)=(A+B)(A+C),A(B+C)=A B+A C公理公理401律律 A+0=A,A 1=A A+1=1,A 0=0，公理公理5互补律互补律A+A=1,AA=0本讲稿第四页，共九十页2.1.1逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算逻辑变量逻辑变量逻辑变量逻辑变量：仅取值0或取值1的变量。这里0和1无大小之分，实际上代表着矛盾的双方或事件的真假，例如开关的接通与断开，电压的高和底，信号的有和无，电灯的亮和灭等等。只要是两种稳定的物理状态，都可以用0和1这两种不同的逻辑值来表征。本讲稿第五页，共九十页一、一、一、一、或或或或 运算运算运算运算如果决定某一事件发生的多个条件，只要有一个或一个以上的条件成立，事件便可发生，这种因果关系称之为或逻辑。在逻辑代数中，或逻辑关系用或运算描述。或运算又称逻辑加，其运算符为+或 ，两个变量的或运算可表示为:F=A+B 或者 F=AB读作F等于A或B,其中A、B是参加运算的两个逻辑变量，F为运算结果。意思是：只要A、B中有一个为1，则F为1；仅当A、B均为0时，F才为0。本讲稿第六页，共九十页A B F0 0 00 1 11 0 11 1 1或运算表A+uBF由“或”运算的运算表可知“或”运算的法则为：0+0=01+0=10+1=11+1=1实现或运算的逻辑电路称为或门。本讲稿第七页，共九十页二、二、二、二、与与与与 运算运算运算运算如果决定某一事件的发生的多个条件必须同时具备，事件才能发生，这种因果关系称为与逻辑。逻辑代数中与逻辑关系用与运算描述。与运算又称逻辑乘，其运算符为或。两变量的与运算可表示为FA B 或者 F=AB读作F等于A与B，意思是若A B 均为1，则F为1；否则F为0。本讲稿第八页，共九十页A B F0 0 00 1 01 0 01 1 1与运算表+uABF由“与”运算的运算表可知“与”运算法则为：0 0=01 0=00 1=01 1=1实现“与”运算的逻辑电路称为“与”门。本讲稿第九页，共九十页三、三、三、三、非非非非 运算运算运算运算如果某一事件的发生取决于条件的否定，则这种因果关系称为非逻辑。非逻辑用非运算描述。非运算又称求反运算，运算符为或.非运算可表示为F=A 或F=A读作F等于A非，意思是若A0，则F为1；反之，若A=1,则F为0。本讲稿第十页，共九十页“非运算表由“非”运算的运算表可知“非”运算法则为：A F0 11 0+uAF实现“非”运算的逻辑电路称为“非”门。本讲稿第十一页，共九十页2.1.2逻辑函数逻辑函数一、逻辑函数的定义一、逻辑函数的定义一、逻辑函数的定义一、逻辑函数的定义设某一电路的输入逻辑变量为A1,A2,An,输出逻辑变量为F。如果当A1,A2,An 的值确定后，F的值就唯一地被定下来，则F称为A1,A2,An,的逻辑函数，记为F=f(A1,A2,An)逻辑电路的功能可由相应逻辑函数完全描述。与普通函数概念相比逻辑函数有如下特点：1）逻辑变量与逻辑函数的取值只有0和1；2）逻辑函数与逻辑变量的关系由“或”、“与”、“非”运算决定。本讲稿第十二页，共九十页二、逻辑函数的相等二、逻辑函数的相等二、逻辑函数的相等二、逻辑函数的相等设有两个逻辑函数F1=f1(A1,A2,An)F2=f2(A1,A2,An)若对应于A1,A2,An的任何一组取值,F1 和F2的值都相同,则称函数F1和函数F2相等,记作F1=F2亦称函数F1与F2等价。本讲稿第十三页，共九十页2.1.3逻辑函数的表示法逻辑函数的表示法一、逻辑表达式一、逻辑表达式一、逻辑表达式一、逻辑表达式由逻辑变量、常量和逻辑运算符构成的合法表达式。进行非运算可不加括号,如 与运算符一般可省略,AB可写成AB.可根据先与后或的顺序去括号,如：(AB)(CD)ABCD例：逻辑表达式书写省略规则：本讲稿第十四页，共九十页本讲稿第十五页，共九十页二、真值表二、真值表二、真值表二、真值表真值表是一种由逻辑变量的所有可能取值组合及其对应的逻辑函数值所构成的表格.例如例如：函数 F=AB+AC 的真值表如右所示：A B C F0 0 000 0 110 1 000 1 111 0 011 0 111 1 001 1 10本讲稿第十六页，共九十页三、卡诺图三、卡诺图三、卡诺图三、卡诺图卡诺图是一种用图形描述逻辑函数的方法。本讲稿第十七页，共九十页2.2 2.2 逻辑代数的基本定理和规则逻辑代数的基本定理和规则2.2.1基本定理基本定理定理定理定理定理1 1000 101 011 111 0 0 0 1 0 0 0 1 01 1 1 推论：1=0 0=1本讲稿第十八页，共九十页定理定理2(重叠律重叠律)AAAA A A 定理定理3(吸收律吸收律)AA BA A(A+B)A定理定理4(吸收律吸收律)AA BA+BA(A+B)A B定理定理5(对合律对合律)AA定理定理6(德摩根定理德摩根定理)AB A BA B AB 定理定理7 AB+ABA(A+B)(A+B)A定理定理8(包含律包含律)AB+AC+BCAB+AC本讲稿第十九页，共九十页f(A1,A2,An)f(A1,A2,An)12.2.2逻辑代数的重要规则逻辑代数的重要规则一、代入规则一、代入规则任何一个含有变量A的逻辑等式，如果将所有出现A的位置都代之以同一个逻辑函数F，则等式仍然成立。例如例如：给定逻辑等式A(B+C)=AB+AC，若用A+BC代替A，则该等式仍然成立，即：(A+BC)(B+C)=(A+BC)B+(A+BC)C由公理5(A+A=1)同样有等式本讲稿第二十页，共九十页二、反演规则二、反演规则二、反演规则二、反演规则F(A+B)(C+D)例如例如：已知FABCD，根据反演规可得到:如果将逻辑函数F中所有的 变成+,+变成 ,0变成1,1变成0,原变量变成反变量，反变量变成原变量，所得到的新函数是原函数的反函数使用反演规则时,应注意保持原函式中运算符号的优先顺序不变。例如：例如：已知本讲稿第二十一页，共九十页三、对偶规则三、对偶规则三、对偶规则三、对偶规则如果将逻辑函数F中所有的 变成+,+变成 ,0变成1,1变成0,则所得到的新逻辑函数F的对偶式F。如果F是F的对偶式，则F也是F 的对偶式，即F与F互为对偶式。求某一函数F的对偶式时，同样要注意保持原函数的运算顺序不变。对偶规则：对偶规则：对偶规则：对偶规则：若两个逻辑函数F的G相等，则其对偶式F 和G 也相等。例:F=A+B+C F=A B C例:AB+AC+BC=AB+C 则(A+B)(A+C)(B+C)=(A+B)C本讲稿第二十二页，共九十页2.3 2.3 逻辑函数表达式的形式与变换逻辑函数表达式的形式与变换2.3.1逻辑函数表达式的基本形式逻辑函数表达式的基本形式两种基本形式：两种基本形式：两种基本形式：两种基本形式：积之和表达式与和之积表达式.积之和积之和：由若干个与项经或运算形成的表达式。例如：和之积和之积：由若干个或项经与运算形成的表达式。例如：既不是与或表达式也不是或与表达式。而本讲稿第二十三页，共九十页2.3.2逻辑函数表达式的标准形式逻辑函数表达式的标准形式一、最小项一、最小项一、最小项一、最小项如果一个具有n个变量的函数的积项包含全部n个变量,每个变量都以原变量或反变量形式出现,且仅出现一次，则这个积项被称为最小项。假如一个函数完全由最小项所组成,那么该函数表达式称为标准积之和表达式,即最小项之和.本讲稿第二十四页，共九十页变量的各组取值A B C000001010011100101110111对应的最小项及其编号最小项编 号三变量函数的最小项：本讲稿第二十五页，共九十页=m2+m3+m6+m7注意：变量的顺序.即n个变量的所有最小项之和恒等于1。所以=m(2,3,6,7)本讲稿第二十六页，共九十页最小项的性质：1）当函数以最小项之和形式表示时，可很容易列出函数及反函数的真值表（在真值表中，函数所包含的最小项填“1”）。2）当时，。3）n变量的最小项有n个相邻项。相邻项：只有一个变量不同（以相反的形式出现）。一对相邻项可以消去一个变量。本讲稿第二十七页，共九十页二、最大项二、最大项二、最大项二、最大项如果一个具有n个变量的函数的和项包含全部n个变量，每个变量都以原变量或反变量形式出现，且仅出现一次，则这个和项称为最大项。假如一个函数完全由最大项组成，那么这个函数表达式称为标准和之积表达式。本讲稿第二十八页，共九十页变量的各组取值A B C000001010011100101110111对应的最大项及其编号最大项编 号三变量函数的最大项：本讲稿第二十九页，共九十页注意：变量顺序.与最小项类似，有例如：例如：本讲稿第三十页，共九十页最大项的性质：1）当函数以最大项之积形式表示时，可很容易列出函数及反函数的真值表（在真值表中，函数所包含的最大项填“0”）。2）当时，。3）n变量的最大项有n个相邻项。相邻项：只有一个变量不同（以相反的形式出现）。一对相邻项可以消去一个变量。本讲稿第三十一页，共九十页三、两种标准形式的转换：三、两种标准形式的转换：三、两种标准形式的转换：三、两种标准形式的转换：以最小项之和的形式表示的函数可以转换成最大项之积的形式，反之亦然。=m(2,3,6,7)F(A,B,C)=m(0,1,4,5)=(A+B+C)(A+B+C)(A+B+C)(A+B+C)F(A,B,C)=m(0,1,4,5)同理且有即：最大项与最小项互补。例如：例如：M3=A+B+C=ABC=m3本讲稿第三十二页，共九十页2.3.3逻辑函数表达式的转换逻辑函数表达式的转换任何一个逻辑函数，总可以将其 转换成最小项之和及最大项之积的形式,常用代数转换法或真值表转换法.本讲稿第三十三页，共九十页一、代数转换法一、代数转换法用代数法求一个函数最小项之和的形式，一般分为两步：第一步第一步：将函数表达式变换成一般的与或式.第二步第二步：反复使用X=X(Y+Y)将非最小项的与 项 扩展为最小项。本讲稿第三十四页，共九十页例例：将F(A,B,C)=(AB+BC)AB转换成最小项之和形式本讲稿第三十五页，共九十页F(A,B,C)=m0+m1+m3+m6+m7=m(0,1,3,6,7)本讲稿第三十六页，共九十页类似地，用代数法求一个函数最大项之积的形式，也可分为两步：第一步第一步第一步第一步：将函数表达式转换成一般或与式；如果给出的函数已经是与或式或者是或与式，则可直接进行第二步。第二步第二步第二步第二步：反复使用将非最大项的或项扩展成为最大项本讲稿第三十七页，共九十页例：将F(A,B,C)=AB+AC转换成“最大项 之积的形式。解：1）F(A,B,C)=AB AC=(A+B)(A+C)2)F(A,B,C)=(A+B+CC)(A+BB+C)=(A+B+C)(A+B+C)(A+B+C)(A+B+C)F(A,B,C)=M1 M3 M6 M7=M(1,3,6,7)本讲稿第三十八页，共九十页二、真值表转换法二、真值表转换法二、真值表转换法二、真值表转换法一个逻辑函数的真值表与它的最小项表达式和最大项表达式均存在一一对应的关系。函数F的最小项表达式由使F取值为1的全部最小项之和组成。函数F的最大项表达式由使F取值为0的全部最大项之积组成。本讲稿第三十九页，共九十页和最大项之积的形式。解：解：A B C F0 0 000 0 110 1 000 1 111 0 011 0 101 1 001 1 10注意：任何一个逻辑函数的两种标准形式唯一.本讲稿第四十页，共九十页2.4 2.4 逻辑函数的简化逻辑函数的简化一般来说,逻辑函数表达式越简单,设计出来的电路也就越简单。把逻辑函数简化成最简形式称为逻辑函数的最小化,有三种常用的方法,即代数化简法、卡诺图化简法和列表化简法。本讲稿第四十一页，共九十页2.4.1代数化简法代数化简法该方法运用逻辑代数的公理、定理和规则对逻辑函数进行推导、变换而进行化简，没有固定的步骤可以遵循，主要取决于对公理、定理和规则的熟练掌握及灵活运用的程度。有时很难判定结果是否为最简。本讲稿第四十二页，共九十页一、一、一、一、与或与或与或与或 式的化简式的化简式的化简式的化简化简应满足的两个条件：1）表达式中与项的个数最少；2）在满足1）的前提下,每个与项中的变量个数最少。本讲稿第四十三页，共九十页本讲稿第四十四页，共九十页二、二、二、二、或与或与或与或与 式的化简式的化简式的化简式的化简化简应满足的两个条件：化简应满足的两个条件：1）表达式中或项的个数最少；2）在满足1）的前提下,每个或项中的变量个数最少。本讲稿第四十五页，共九十页例：F=(A+B)(A+B)(B+C)(B+C+D)解：F=(A+B)(A+B)(B+C)(B+C+D)=（A+B)(A+B)(B+C)=A(B+C)例：F=(A+B)(A+B)(B+C)(A+C)解：F=AB+AB+BC+AC=AB+AB+(B+A)C=AB+AB+ABC=AB+AB+CF=(F)=(A+B)(A+B)C本讲稿第四十六页，共九十页2.4.22.4.2卡诺图化简法卡诺图化简法卡诺图化简法卡诺图化简法该方法简单、直观、容易掌握,当变量个数小于等于6时非常有效,在逻辑设计中得到广泛应用。一、卡诺图的构成一、卡诺图的构成一、卡诺图的构成一、卡诺图的构成n个变量的卡诺图是一种由2n个方格构成的图形,每一个方格表示逻辑函数的一个最小项,所有的最小项巧妙地排列成一种能清楚地反映它们相邻关系的方格阵列。因为任意一个逻辑函数都 可表示成最小项之和的形式,所以一个函数可用图形中若干方格构成的区域来表示。本讲稿第四十七页，共九十页mo m2m1 m3 0101ABAB 0101二变量卡诺图本讲稿第四十八页，共九十页mo m2 m6 m4m1 m3 m7 m500 01 11 1001ABC00 01 11 1001ABC三变量卡诺图本讲稿第四十九页，共九十页00 01 11 1000011110ABCD 0 4 12 8 1 5 13 9 3 7 15 11 2 6 14 1000 01 11 1000011110ABCD四变量卡诺图本讲稿第五十页，共九十页定义定义定义定义：彼此只有一个变量不同，且这个不同变量互为反变量的两个最小 项(或与项)称为相邻最小项(或相邻与项).相邻最小项在卡诺图中有三种特征，即几何相邻、相对相邻和重叠相邻。卡诺图在构造上具有以下两个特点：卡诺图在构造上具有以下两个特点：1）n个变量的卡诺图由2n个小方格组成,每个小方格代表一个最小项。2）卡诺图上处在相邻、相对、相重位置的小方格所代表的最小项为相邻最小项。本讲稿第五十一页，共九十页二、逻辑函数的卡诺图表示二、逻辑函数的卡诺图表示 将逻辑函数所对应的最小项在卡诺图的相应方格中标以1，剩余方格标以0或不标。本讲稿第五十二页，共九十页1、与或式的卡诺图表示.直接将表达式的与项或最小项所对应的方格标以1.00 01 11 1001ABC11111可表示为：例如：例如：2、其它形式函数的卡诺图表示要转换成与或式再在卡诺图上表示。本讲稿第五十三页，共九十页三、卡诺图的性质三、卡诺图的性质三、卡诺图的性质三、卡诺图的性质根据定理7有AB+AB=A,它表明两 个相邻与项或最小项可以合并为一项，这一项由两个与项中相同的变量组成，可以消去两个 与项中不同的变量。在卡诺图上把相邻最小项所对应的小方格圈在一起可进行合并，以达到用一个简单与项代替若干最小项的目的。这样的圈称为卡诺圈。本讲稿第五十四页，共九十页 0101AB1 1 0101AB1 1 0101AB1 11二变量卡诺图的典型合并情况本讲稿第五十五页，共九十页00 01 11 1001ABC1 11 1AB 00 01 11 1001C1 1 1 11 1 1 101ABC00 01 11 10三变量卡诺图的典型合并情况本讲稿第五十六页，共九十页100 01 11 1000011110ABCD111111100 01 11 1000011110ABCD1111111100 01 11 1000011110ABCD1111111111四变量卡诺图的典型合并情况本讲稿第五十七页，共九十页一个卡诺圈中的小方格满足以下规律：一个卡诺圈中的小方格满足以下规律：1）卡诺圈中的小方格的数目为2m,m为整数且mn;3）2m个小方格可用(n-m)个变量的与项表示,该与项由这些最小项中的相同变量构成。2）2m个小方格含有m个不同变量和(n-m)个相同变量;4）当m=n时,卡诺圈包围整个卡诺图,可用1表示，即n个变量的全部最小项之和为1。本讲稿第五十八页，共九十页四、卡诺图化简逻辑函数的步骤：四、卡诺图化简逻辑函数的步骤：四、卡诺图化简逻辑函数的步骤：四、卡诺图化简逻辑函数的步骤：蕴涵项：蕴涵项：与或式中的每一个与项称为函数的蕴涵项；质蕴涵项：质蕴涵项：不被其它蕴涵项所包含的蕴涵项；必要质蕴涵项：必要质蕴涵项：质蕴涵项中至少有一个最小项不被其它蕴涵项所包含。本讲稿第五十九页，共九十页用卡诺图化简逻辑函数的一般步骤为：用卡诺图化简逻辑函数的一般步骤为：第一步：第一步：作出函数的卡诺图；第二步：第二步：在卡诺图上圈出函数的全部质蕴涵项；第三步：第三步：从全部质蕴涵项中找出所有必要质蕴涵项；第四步第四步：若全部必要质蕴涵项尚不能覆盖所有的1 方格，则需从剩余质蕴涵项中找出最简的所需质蕴涵项，使它和必要质蕴涵项一起构成函数的最小覆盖。本讲稿第六十页，共九十页例：例：用卡诺图化简逻辑涵数 F(A,B,C,D)=m(0,3,5,6,7,10,11,13,15)100 01 11 1000011110ABCD11111111解：解：本讲稿第六十一页，共九十页1100 01 11 1000011110ABCD111111100 01 11 1000011110ABCD1*1111*1*1*1*1*本讲稿第六十二页，共九十页例：例：用卡诺图化简逻辑函数 F(A,B,C,D)=m(2,3,6,7,8,10,12)100 01 11 1000011110ABCD111111解：解：100 01 11 1000011110ABCD111111本讲稿第六十三页，共九十页00 01 11 1000011110ABCD1*1111*1*1*1100 01 11 1000011110ABCD1*1*1*1*1本讲稿第六十四页，共九十页例：例：用卡诺图把逻辑函数 F(A,B,C,D)=M(3,4,6,7,11,12,13,14,15)化简成最简或与表达式。本讲稿第六十五页，共九十页100 01 11 1000011110ABCD001001011001001本讲稿第六十六页，共九十页2.4.42.4.4逻辑函数化简中两个实际问题的考虑逻辑函数化简中两个实际问题的考虑逻辑函数化简中两个实际问题的考虑逻辑函数化简中两个实际问题的考虑一、包含无关最小项的逻辑函数的化简一、包含无关最小项的逻辑函数的化简一、包含无关最小项的逻辑函数的化简一、包含无关最小项的逻辑函数的化简无无无无关关关关最最最最小小小小项项项项：一个逻辑函数,如果它的某些输入取值组合因受特殊原因制约而不会再现,或者虽然每种输入取值组合都可能出现,但此时函数取值为1还是为0无关紧要,那么这些输入取值组合所对应的最小项称为无关最小项。无关最小项可以随意加到函数表达式中，或不加到函数表达式中，并不影响函数的实际逻辑功能。本讲稿第六十七页，共九十页A B C DF0 0 0 0d0 0 0 1d0 0 1 0d0 0 1 110 1 0 010 1 0 110 1 1 000 1 1 101 0 0 001 0 0 101 0 1 011 0 1 111 1 0 011 1 0 1d1 1 1 0d1 1 1 1d100 01 11 1000011110ABCD11111例例例例：给定某电路的逻辑函数真值表如下，求F的最简与或式。解：1)不考虑无关最小项：本讲稿第六十八页，共九十页1100 01 11 1000011110ABCD1111dddddd2)考虑无关最小项：本讲稿第六十九页，共九十页二、多输出逻辑函数的化简二、多输出逻辑函数的化简二、多输出逻辑函数的化简二、多输出逻辑函数的化简.对于多输出逻辑函数，如果孤立地将单个输出一一化简，然后直接拼在一起，通常并不能保证整个电路最简，因为各个输出函数之间往往存在可供共享的部分。多输出逻辑函数化简的标准：多输出逻辑函数化简的标准：2）在满足上述条件的前提下，各不同与项中所含的变量总数最少。1）所有逻辑表达式包含的不同与项总数最小；本讲稿第七十页，共九十页例例例例：多输出函数.对应的卡诺图为100 01 11 1001ABC1 1F1100 01 11 1001ABC1 1F2本讲稿第七十一页，共九十页从多输出函数化简的观点来看，它们不是最佳的，应该是：对应的卡诺图为100 01 11 1001ABC1 1F11 1100 01 11 1001ABCF2本讲稿第七十二页，共九十页列表化列表化简简法法 n n列表化简法是列表化简法是Quine-Mccluskey提出的一提出的一种系统化简法，故也称作种系统化简法，故也称作Q-M法，也称作表法，也称作表格法。这种方法具有严格的算法，虽然其格法。这种方法具有严格的算法，虽然其工作量大、方法繁琐，但便于计算机化简工作量大、方法繁琐，但便于计算机化简多变量逻辑函数。多变量逻辑函数。吉林大学计算机科学与技术学院本讲稿第七十三页，共九十页列表化列表化简简法法 Q-M法化简逻辑函数的步骤如下：法化简逻辑函数的步骤如下：n n第一步，将函数表示成最小项表达式。第一步，将函数表示成最小项表达式。第一步，将函数表示成最小项表达式。第一步，将函数表示成最小项表达式。n n第二步，找出函数的全部质蕴涵项。第二步，找出函数的全部质蕴涵项。第二步，找出函数的全部质蕴涵项。第二步，找出函数的全部质蕴涵项。1 1、将、将、将、将n n变量函数中的相邻最小项合并，消去相异的一个变量，变量函数中的相邻最小项合并，消去相异的一个变量，变量函数中的相邻最小项合并，消去相异的一个变量，变量函数中的相邻最小项合并，消去相异的一个变量，得到得到得到得到(n-1)(n-1)个变量的与项（蕴涵项）。个变量的与项（蕴涵项）。个变量的与项（蕴涵项）。个变量的与项（蕴涵项）。这时如果存在不能合这时如果存在不能合这时如果存在不能合这时如果存在不能合并的最小项，它便是所寻找的部分质蕴涵项。并的最小项，它便是所寻找的部分质蕴涵项。并的最小项，它便是所寻找的部分质蕴涵项。并的最小项，它便是所寻找的部分质蕴涵项。2 2、再将相邻的（、再将相邻的（、再将相邻的（、再将相邻的（n-1n-1）个变量的与项合并，消去相异的一个变量，）个变量的与项合并，消去相异的一个变量，）个变量的与项合并，消去相异的一个变量，）个变量的与项合并，消去相异的一个变量，得到（得到（得到（得到（n-2n-2）个变量的与项（蕴涵项）个变量的与项（蕴涵项）个变量的与项（蕴涵项）个变量的与项（蕴涵项），这里如果存在不能合，这里如果存在不能合，这里如果存在不能合，这里如果存在不能合并的（并的（并的（并的（n-1n-1）个变量的与项，则它们也是所寻找的质蕴涵项。）个变量的与项，则它们也是所寻找的质蕴涵项。）个变量的与项，则它们也是所寻找的质蕴涵项。）个变量的与项，则它们也是所寻找的质蕴涵项。如此进行下去，直到不能再合并为止。得全部的质蕴涵项。如此进行下去，直到不能再合并为止。得全部的质蕴涵项。如此进行下去，直到不能再合并为止。得全部的质蕴涵项。如此进行下去，直到不能再合并为止。得全部的质蕴涵项。数字逻辑电路吉林大学计算机科学与技术学院本讲稿第七十四页，共九十页列表化列表化简简法法 n n第三步，找出函数的必要质蕴涵项。第三步，找出函数的必要质蕴涵项。先画出质蕴涵表，然后在表上找出仅属于一个质蕴先画出质蕴涵表，然后在表上找出仅属于一个质蕴先画出质蕴涵表，然后在表上找出仅属于一个质蕴先画出质蕴涵表，然后在表上找出仅属于一个质蕴涵项的最小项，则包含该最小项的质蕴涵项就是必要质涵项的最小项，则包含该最小项的质蕴涵项就是必要质涵项的最小项，则包含该最小项的质蕴涵项就是必要质涵项的最小项，则包含该最小项的质蕴涵项就是必要质蕴涵项。蕴涵项。蕴涵项。蕴涵项。n n第四步，找出函数的最小覆盖。第四步，找出函数的最小覆盖。第四步，找出函数的最小覆盖。第四步，找出函数的最小覆盖。当第三步找出的必要质蕴涵项不能包含函数的全当第三步找出的必要质蕴涵项不能包含函数的全当第三步找出的必要质蕴涵项不能包含函数的全当第三步找出的必要质蕴涵项不能包含函数的全部最小项时，可以通过行、列消去法，找出最小覆盖部最小项时，可以通过行、列消去法，找出最小覆盖部最小项时，可以通过行、列消去法，找出最小覆盖部最小项时，可以通过行、列消去法，找出最小覆盖的其他必要质蕴涵项。最小覆盖指包含函数的全部最的其他必要质蕴涵项。最小覆盖指包含函数的全部最的其他必要质蕴涵项。最小覆盖指包含函数的全部最的其他必要质蕴涵项。最小覆盖指包含函数的全部最小项的最小质蕴涵项集合。小项的最小质蕴涵项集合。小项的最小质蕴涵项集合。小项的最小质蕴涵项集合。数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院本讲稿第七十五页，共九十页列表化列表化简简法法 用用Q-M法化简函数法化简函数:数字逻辑电路吉林大学计算机科学与技术学院 111111111 ABCD0001111000 01 11 10 本讲稿第七十六页，共九十页列表化列表化简简法法（1 1）找出全部质蕴涵项）找出全部质蕴涵项）找出全部质蕴涵项）找出全部质蕴涵项 做最小项分组表并找出不能合并者做最小项分组表并找出不能合并者做最小项分组表并找出不能合并者做最小项分组表并找出不能合并者:将最小项将最小项将最小项将最小项mmi i按变量取值表示成二进制数；其次，再根据这些二进按变量取值表示成二进制数；其次，再根据这些二进按变量取值表示成二进制数；其次，再根据这些二进按变量取值表示成二进制数；其次，再根据这些二进制数中所包含制数中所包含制数中所包含制数中所包含1 1的个数从少到多的次序进行分组排队；最后，把含有的个数从少到多的次序进行分组排队；最后，把含有的个数从少到多的次序进行分组排队；最后，把含有的个数从少到多的次序进行分组排队；最后，把含有1 1的个数相同的最小项划分成一组，组内按下标的个数相同的最小项划分成一组，组内按下标的个数相同的最小项划分成一组，组内按下标的个数相同的最小项划分成一组，组内按下标i i的取值从小到大排列，的取值从小到大排列，的取值从小到大排列，的取值从小到大排列，如此制成最小项分组。如此制成最小项分组。如此制成最小项分组。如此制成最小项分组。从含有从含有从含有从含有1 1个数最少的那组开始，在相邻组内比较最小项，将只有个数最少的那组开始，在相邻组内比较最小项，将只有个数最少的那组开始，在相邻组内比较最小项，将只有个数最少的那组开始，在相邻组内比较最小项，将只有一个变量值不同的两个最小项合并，消去一个变量，并在已合并的最一个变量值不同的两个最小项合并，消去一个变量，并在已合并的最一个变量值不同的两个最小项合并，消去一个变量，并在已合并的最一个变量值不同的两个最小项合并，消去一个变量，并在已合并的最小项的右边小项的右边小项的右边小项的右边P Pi i栏内做记号栏内做记号栏内做记号栏内做记号“”“”，表示该项已被合并。在不能合并的，表示该项已被合并。在不能合并的，表示该项已被合并。在不能合并的，表示该项已被合并。在不能合并的最小项的右边最小项的右边最小项的右边最小项的右边P Pi i栏内填入栏内填入栏内填入栏内填入P P1 1，则，则，则，则 就是所寻找的质就是所寻找的质就是所寻找的质就是所寻找的质蕴涵项。注意合并最小项只能处于相邻的两组内，而不能处蕴涵项。注意合并最小项只能处于相邻的两组内，而不能处蕴涵项。注意合并最小项只能处于相邻的两组内，而不能处蕴涵项。注意合并最小项只能处于相邻的两组内，而不能处于同组或隔组内。于同组或隔组内。于同组或隔组内。于同组或隔组内。数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院本讲稿第七十七页，共九十页列表化列表化简简法法 数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院 1111111115154 4011101117 73 3 101010101010P P1 1100110019 9011001106 6010101015 52 2010001004 4001000102 21 1000000000 00 0P Pi i变变变变量量量量ABCDABCD最小最小最小最小项项项项编编编编号号号号组组组组号号号号（1 1的个数）的个数）的个数）的个数）最小项分组表最小项分组表最小项分组表最小项分组表 本讲稿第七十八页，共九十页列表化列表化简简法法 做（做（n-1）个变量与项分组表并找出不能合并者）个变量与项分组表并找出不能合并者:在最小项合并过程中，用符号在最小项合并过程中，用符号在最小项合并过程中，用符号在最小项合并过程中，用符号“”“”表示被消去的变表示被消去的变表示被消去的变表示被消去的变量，这样便得到若干个带有量，这样便得到若干个带有量，这样便得到若干个带有量，这样便得到若干个带有“”“”的与项，或称作合并项。的与项，或称作合并项。的与项，或称作合并项。的与项，或称作合并项。按照对最小项的分组方法，对带有按照对最小项的分组方法，对带有按照对最小项的分组方法，对带有按照对最小项的分组方法，对带有“”“”的与项进行分组。的与项进行分组。的与项进行分组。的与项进行分组。对相邻组中的对相邻组中的对相邻组中的对相邻组中的“”“”处于相同位置的那些与项进行合并，处于相同位置的那些与项进行合并，处于相同位置的那些与项进行合并，处于相同位置的那些与项进行合并，已合并的与项做记号已合并的与项做记号已合并的与项做记号已合并的与项做记号“”“”，并记入，并记入，并记入，并记入PiPi栏；在不能合并的栏；在不能合并的栏；在不能合并的栏；在不能合并的与项的与项的与项的与项的PiPi栏内记入栏内记入栏内记入栏内记入P2P2和和和和P3P3，则，则，则，则 也是质蕴涵项。也是质蕴涵项。也是质蕴涵项。也是质蕴涵项。数字逻辑电路吉林大学计算机科学与技术学院本讲稿第七十九页，共九十页列表化列表化简简法法 组组组组号号号号（1 1）最小最小最小最小项项项项编编编编号号号号变变变变量量量量ABCDABCDP Pi i0 00 02 2000000 0 04 40 00000 1 12 26 6010010 2 21010010010P P2 24 45 5010010 4 46 60100102 25 57 7011011 6 67 7011011 3 37 71515111111P P3 3数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院 1111111115154 4011101117 73 3 101010101010P P1 1100110019 9011001106 6010101015 52 2010001004 4001000102 21 1000000000 00 0P Pi i变变变变量量量量ABCDABCD最小最小最小最小项项项项编编编编号号号号组组组组号号号号（1 1的个数）的个数）的个数）的个数）最小项分组表最小项分组表最小项分组表最小项分组表（n-1n-1）个变量与项分组表）个变量与项分组表）个变量与项分组表）个变量与项分组表本讲稿第八十页，共九十页列表化列表化简简法法 做（做（n-2）个变量与项分组表并找出不能合并者：）个变量与项分组表并找出不能合并者：在（在（在（在（n-1n-1）个变量与项合并过程中，也用符号）个变量与项合并过程中，也用符号）个变量与项合并过程中，也用符号）个变量与项合并过程中，也用符号“”“”表表表表示被消去的变量，这样便得到若干个带有两个示被消去的变量，这样便得到若干个带有两个示被消去的变量，这样便得到若干个带有两个示被消去的变量，这样便得到若干个带有两个“”“”的与项。的与项。的与项。的与项。按照上述的分组方法，得到（按照上述的分组方法，得到（按照上述的分组方法，得到（按照上述的分组方法，得到（n-2n-2）个变量与项分组表。）个变量与项分组表。）个变量与项分组表。）个变量与项分组表。由表可以看出，仅有的两（由表可以看出，仅有的两（由表可以看出，仅有的两（由表可以看出，仅有的两（n-2n-2）个变量与项不能）个变量与项不能）个变量与项不能）个变量与项不能再合并，在再合并，在再合并，在再合并，在PiPi栏内分别记入栏内分别记入栏内分别记入栏内分别记入P4P4和和和和P5P5，P4P4和和和和P5P5就是最后就是最后就是最后就是最后所寻找的质蕴涵项。所寻找的质蕴涵项。所寻找的质蕴涵项。所寻找的质蕴涵项。数字逻辑电路吉林大学计算机科学与技术学院本讲稿第八十一页，共九十页列表化列表化简简法法 组组组组号号号号（1 1的个数）的个数）的个数）的个数）最小最小最小最小项项项项编编编编号号号号变变变变量量量量ABCDABCDP Pi i 0 00 0 2 24 4 6 60000P P4 41 14 4 5 56 6 7 70101P P5 5数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院组组组组号号号号（1 1）最小最小最小最小项项项项编编编编号号号号变变变变量量量量ABCDABCDP Pi i0 00 02 2000000 0 04 40 00000 1 12 26 6010010 2 21010010010P P2 24 45 5010010 4 46 60100102 25 57 7011011 6 67 7011011 3 37 71515111111P P3 3（n-2n-2）个变量与项分组表）个变量与项分组表）个变量与项分组表）个变量与项分组表（n-1n-1）个变量与项分组表）个变量与项分组表）个变量与项分组表）个变量与项分组表本讲稿第八十二页，共九十页列表化列表化简简法法 列出全部质蕴涵项列出全部质蕴涵项由上述分析可得全部质蕴涵由上述分析可得全部质蕴涵项：项：数字逻辑电路吉林大学计算机科学与技术学院本讲稿第八十三页，共九十页列表化列表化简简法法（2 2）找出必要质蕴涵项）找出必要质蕴涵项）找出必要质蕴涵项）找出必要质蕴涵项 将函数的最小项和上述的质蕴涵项做序列表，并在质将函数的最小项和上述的质蕴涵项做序列表，并在质将函数的最小项和上述的质蕴涵项做序列表，并在质将函数的最小项和上述的质蕴涵项做序列表，并在质蕴涵项包含的最小项下面填入符号蕴涵项包含的最小项下面填入符号蕴涵项包含的最小项下面填入符号蕴涵项包含的最小项下面填入符号“”,“”,即做所谓质蕴即做所谓质蕴即做所谓质蕴即做所谓质蕴涵表。涵表。涵表。涵表。找出那些仅属于一个质蕴涵项的最小项，如找出那些仅属于一个质蕴涵项的最小项，如找出那些仅属于一个质蕴涵项的最小项，如找出那些仅属于一个质蕴涵项的最小项，如m0m0仅属仅属仅属仅属于于于于P4P4；m5m5仅属于仅属于仅属于仅属于P5P5；m9m9仅属于仅属于仅属于仅属于P1P1；m10m10仅属于仅属于仅属于仅属于P