第二章列表化简法.ppt

列表化简法列表化简法是Quine-Mccluskey提出的一种系统化简法,故也称作Q-M法,也称作表格法。这种方法具有严格的算法,虽然其工作量大、方法繁琐,但便于计算机化简多变量逻辑函数。《数字逻辑电路》吉林大学计算机科学与技术学院螟炳欣贸颠菜方貉稍铜坟钓拽黍座鱼宿誓秩艰董罚减锣空啡介鹏鞋版速府第二章列表化简法第二章列表化简法列表化简法Q-M法化简逻辑函数的步骤如下:第一步,将函数表示成最小项表达式。第二步,找出函数的全部质蕴涵项。1、将n变量函数中的相邻最小项合并,消去相异的一个变量,得到(n-1)个变量的与项(蕴涵项)。这时如果存在不能合并的最小项,它便是所寻找的部分质蕴涵项。2、再将相邻的(n-1)个变量的与项合并,消去相异的一个变量,得到(n-2)个变量的与项(蕴涵项),这里如果存在不能合并的(n-1)个变量的与项,则它们也是所寻找的质蕴涵项。如此进行下去,直到不能再合并为止。得全部的质蕴涵项。《数字逻辑电路》吉林大学计算机科学与技术学院下斡婶拼过爪廓泉三萌刑觉撮骑乐吃预郭调毕褒仿衔勉孽粹挫骄最荔煎线第二章列表化简法第二章列表化简法列表化简法第三步,找出函数的必要质蕴涵项。先画出质蕴涵表,然后在表上找出仅属于一个质蕴涵项的最小项,则包含该最小项的质蕴涵项就是必要质蕴涵项。第四步,找出函数的最小覆盖。当第三步找出的必要质蕴涵项不能包含函数的全部最小项时,可以通过行、列消去法,找出最小覆盖的其他必要质蕴涵项。最小覆盖指包含函数的全部最小项的最小质蕴涵项集合。《数字逻辑电路》吉林大学计算机科学与技术学院陨得疫肘政李弧窜或佳聊莲跳展冒痘沸旅浆茵杖同垦饼坞撬篮敢祝树蹄鸽第二章列表化简法第二章列表化简法列表化简法用Q-M法化简函数:《数字逻辑电路》吉林大学计算机科学与技术学院111111111ABCD00011**********协***奇话巴牵山统欲勉其喻圾窘馒吹跟脊庸粒蒙柳顺逾继辫感釜恒蜜峻栓第二章列表化简法第二章列表化简法列表化简法(1)找出全部质蕴涵项①做最小项分组表并找出不能合并者:将最小项mi按变量取值表示成二进制数;其次,再根据这些二进制数中所包含1的个数从少到多的次序进行分组排队;最后,把含有1的个数相同的最小项划分成一组,组内按下标i的取值从小到大排列,如此制成最小项分组。从含有1个数最少的那组开始,在相邻组内比较最小项,将只有一个变量值不同的两个最小项合并,消去一个变量,并在已合并的最小项的右边Pi栏内做记号“√”,表示该项已被合并。在不能合并的最小项的右边Pi栏内填入P1,则就是所寻找的质蕴涵项。注意合并最小项只能处于相邻的两组内,而不能处于同组或隔组内。《数字逻辑电路》吉林大学计算机科学与技术学院韭嗅巴架耐府胡供编剥用颁统氨雾氏吐强看孙镀圭花呀缕柒走俘惊侦颅毅第二章列表化简法第二章列表化简法列表化简法《数字逻辑电路》吉林大学计算机科学与技术学院√1111154√√√011173√101010P110019√√√01106√√010152√√√01004√√√001021√√000000Pi变量ABCD最小项编号组号(1的个数)最小项分组表秀丽决损庄研倒肋锯堂果膜敦旨呼劲乓兆树赵体填裔药屎灵佬吗改完涨仟第二章列表化简法第二章列表化简法列表化简法②做(n-1)个变量与项分组表并找出不能合并者:在最小项合并过程中,用符号“—”表示被消去的变量,这样便得到若干个带有“—”的与项,或称作合并项。按照对最小项的分组方法,对带有“—”的与项进行分组。对相邻组中的“—”处于相同位置的那些与项进行合并,已合并的与项做记号“√”,并记入Pi栏;在不能合并的与项的Pi栏内记入P2和P3,则也是质蕴涵项。《数字逻辑电路》吉林大学计算机科学与技术学院蓄字硷兹伟恃亨废腕三霖龋博考矾冉囤埃谈物箕案漾且贩抱县蚀跟欧裸嘿第二章列表化简法第二章列表化简法列表化简法组号(1)最小项编号变量ABCDPi00200—0√040—00√1260—10√210—010P245010—√4601—0√√25701—1√67011—√3715—111P3《数字逻辑电路》吉林大学计算机科学与技术学院√1111154√√√011173√101010P110019√√√01106√√010152√√√01004√√√001021√√000000Pi变量ABCD最小项编号组号(1的个数)最小项分组表(n-1)个变量与项分组表坡据拾衔搓烫锹帆民殆从恼猪乡逃恐糖宋躯遥抡帧映闰稳唾瓤茫鸯损兢沃第二章列表化简法第二章列表化简法列表化简法③做(n-2)个变量与项分组表并找出不能合并者:在(n-1)个变量与项合并过程中,也用符号“—”表示被消去的变量,这样便得到若干个带有两个“—”的与项。按照上述的分组方法,得到(n-2)个变量与项分组表。由表可以看出,仅有的两(n-2)个变量