资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,列表化简法,列表化简法是,Quine-Mccluskey,提出的一种系统化简法，故也称作,Q-M,法，也称作表格法。这种方法具有严格的算法，虽然其工作量大、方法繁琐，但便于计算机化简多变量逻辑函数。,数字逻辑电路,吉林大学计算机科学与技术学院,列表化简法,Q-M,法化简逻辑函数的步骤如下：,第一步，将函数表示成最小项表达式。,第二步，找出函数的全部质蕴涵项。,1,、将,n,变量函数中的相邻最小项合并，消去相异的一个变量，得到,(n-1),个变量的与项（蕴涵项）。这时如果存在不能合并的最小项，它便是所寻找的部分质蕴涵项。,2,、再将相邻的（,n-1,）个变量的与项合并，消去相异的一个变量，得到（,n-2,）个变量的与项（蕴涵项），这里如果存在不能合并的（,n-1,）个变量的与项，则它们也是所寻找的质蕴涵项。,如此进行下去，直到不能再合并为止。得全部的质蕴涵项。,数字逻辑电路,吉林大学计算机科学与技术学院,列表化简法,第三步，找出函数的必要质蕴涵项。,先画出质蕴涵表，然后在表上找出仅属于一个质蕴涵项的最小项，则包含该最小项的质蕴涵项就是必要质蕴涵项。,第四步，找出函数的最小覆盖。,当第三步找出的必要质蕴涵项不能包含函数的全部最小项时，可以通过行、列消去法，找出最小覆盖的其他必要质蕴涵项。最小覆盖指包含函数的全部最小项的最小质蕴涵项集合。,数字逻辑电路,吉林大学计算机科学与技术学院,列表化简法,用,Q-M,法化简函数,:,数字逻辑电路,吉林大学计算机科学与技术学院,1,1,1,1,1,1,1,1,1,AB,CD,00,01,11,10,00 01 11 10,列表化简法,（,1,）找出全部质蕴涵项,做最小项分组表并找出不能合并者,:,将最小项,m,i,按变量取值表示成二进制数；其次，再根据这些二进制数中所包含,1,的个数从少到多的次序进行分组排队；最后，把含有,1,的个数相同的最小项划分成一组，组内按下标,i,的取值从小到大排列，如此制成最小项分组。,从含有,1,个数最少的那组开始，在相邻组内比较最小项，将只有一个变量值不同的两个最小项合并，消去一个变量，并在已合并的最小项的右边,P,i,栏内做记号“,”,，表示该项已被合并。在不能合并的最小项的右边,P,i,栏内填入,P,1,，则 就是所寻找的质蕴涵项。注意合并最小项只能处于相邻的两组内，而不能处于同组或隔组内。,数字逻辑电路,吉林大学计算机科学与技术学院,列表化简法,数字逻辑电路,吉林大学计算机科学与技术学院,1 1 1 1,15,4,0 1 1 1,7,3,1 0 1 0,10,P,1,1 0 0 1,9,0 1 1 0,6,0 1 0 1,5,2,0 1 0 0,4,0 0 1 0,2,1,0 0 0 0,0,0,P,i,变量,A B C D,最小项,编号,组号,（,1,的个数）,最小项分组表,列表化简法,做（,n-1,）个变量与项分组表并找出不能合并者,:,在最小项合并过程中，用符号“,”,表示被消去的变量，这样便得到若干个带有“,”,的与项，或称作合并项。按照对最小项的分组方法，对带有“,”,的与项进行分组。对相邻组中的“,”,处于相同位置的那些与项进行合并，已合并的与项做记号“,”,，并记入,Pi,栏；在不能合并的与项的,Pi,栏内记入,P2,和,P3,，则,也是质蕴涵项。,数字逻辑电路,吉林大学计算机科学与技术学院,列表化简法,组号,（,1,）,最小项,编号,变量,A B C D,P,i,0,0,2,0 0,0,0,4,0,0 0,1,2,6,0 1 0,2,10,0 1 0,P,2,4,5,0 1 0 ,4,6,0 1 0,2,5,7,0 1 1,6,7,0 1 1 ,3,7,15,1 1 1,P,3,数字逻辑电路,吉林大学计算机科学与技术学院,1 1 1 1,15,4,0 1 1 1,7,3,1 0 1 0,10,P,1,1 0 0 1,9,0 1 1 0,6,0 1 0 1,5,2,0 1 0 0,4,0 0 1 0,2,1,0 0 0 0,0,0,P,i,变量,A B C D,最小项,编号,组号,（,1,的个数）,最小项分组表,（,n-1,）个变量与项分组表,列表化简法,做（,n-2,）个变量与项分组表并找出不能合并者：,在（,n-1,）个变量与项合并过程中，也用符号“,”,表示被消去的变量，这样便得到若干个带有两个“,”,的与项。按照上述的分组方法，得到（,n-2,）个变量与项分组表。,由表可以看出，仅有的两（,n-2,）个变量与项不能再合并，在,Pi,栏内分别记入,P4,和,P5,，,P4,和,P5,就是最后所寻找的质蕴涵项。,数字逻辑电路,吉林大学计算机科学与技术学院,列表化简法,组号,（,1,的个数）,最小项,编号,变量,A B C D,P,i,0,0,2,4,6,0 0,P,4,1,4,5,6,7,0 1 ,P,5,数字逻辑电路,吉林大学计算机科学与技术学院,组号,（,1,）,最小项,编号,变量,A B C D,P,i,0,0,2,0 0,0,0,4,0,0 0,1,2,6,0 1 0,2,10,0 1 0,P,2,4,5,0 1 0 ,4,6,0 1 0,2,5,7,0 1 1,6,7,0 1 1 ,3,7,15,1 1 1,P,3,（,n-2,）个变量与项分组表,（,n-1,）个变量与项分组表,列表化简法,列出全部质蕴涵项,由上述分析可得全部质蕴涵,项：,数字逻辑电路,吉林大学计算机科学与技术学院,列表化简法,（,2,）找出必要质蕴涵项,将函数的最小项和上述的质蕴涵项做序列表，并在质蕴涵项包含的最小项下面填入符号“,”,即做所谓质蕴涵表。,找出那些仅属于一个质蕴涵项的最小项，如,m0,仅属于,P4,；,m5,仅属于,P5,；,m9,仅属于,P1,；,m10,仅属于,P2,；,m15,仅属于,P3,；并在相应的,处加圆圈。,质蕴涵项,P1,P5,均包含一个不属于其他质蕴涵项的最小项，即它们均包含一个，所以它们均为必要质蕴涵项，并在其左边加“,”,号。,数字逻辑电路,吉林大学计算机科学与技术学院,列表化简法,数字逻辑电路,吉林大学计算机科学与技术学院,P,1,P,2,P,3,P,4,P,5,m,0,m,2,m,4,m,5,m,6,m,7,m,9,m,10,m,15,m,i,P,i,质蕴涵表,列表化简法,（,3,）找出函数的最小覆盖,在上述的必要质蕴涵项,P1,P5,中，找出它们所包含的全部最小项，并在相应的最小项上面做记号“,”,。从表中可以看出，必要蕴涵项,P1,P5,包含函数的所有的最小项，也就是说，,P1,P5,构成了函数的最小覆盖，因此，函数的最简与或式为：,数字逻辑电路,吉林大学计算机科学与技术学院,列表化简法,数字逻辑电路,吉林大学计算机科学与技术学院,1,1,1,1,1,1,1,1,1,AB,CD,00,01,11,10,00 01 11 10,1,1,1,1,1,1,1,1,1,AB,CD,00,01,11,10,00 01 11 10,化简函数：,列表化简法,数字逻辑电路,吉林大学计算机科学与技术学院,用,Q-M,法化简函数：,m,i,p,i,m,2,m,4,m,6,m,8,m,9,m,10,m,12,m,13,m,15,p,1,p,2,p,3,p,4,p,5,*p,6,*p,7,函数,F,的质蕴涵表,列表化简法,数字逻辑电路,吉林大学计算机科学与技术学院,行列消去法的规则如下：,1,、行消去法规则是：保留优势行，消去劣势行。,2,、列消去法规则是：保留劣势列，消去优势列。,P,1,P,2,P,3,P,4,P,5,m,2,m,4,m,6,m,10,m,i,P,i,简化质蕴涵表,优势行和劣势行,若有质蕴涵项,i,和,j,两行，其中,j,行中的“,”,完全包含在,i,行之中，则称,i,行为优势行，,j,行为劣势行。,优势列和劣势列,若有最小项,m,k,和,m,l,两列，其中,m,l,中的“,”,完全包含中,m,k,列之中，则称,m,k,为优势列，,m,l,为劣势列。,
展开阅读全文