资源预览内容
第1页 / 共18页
第2页 / 共18页
第3页 / 共18页
第4页 / 共18页
第5页 / 共18页
第6页 / 共18页
第7页 / 共18页
第8页 / 共18页
第9页 / 共18页
第10页 / 共18页
亲,该文档总共18页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
列表化列表化简简简简法法 列表化简法是列表化简法是Quine-MccluskeyQuine-Mccluskey提出的一提出的一 种系统化简法,故也称作种系统化简法,故也称作Q-MQ-M法,也称作表法,也称作表 格法。这种方法具有严格的算法,虽然其格法。这种方法具有严格的算法,虽然其 工作量大、方法繁琐,但便于计算机化简工作量大、方法繁琐,但便于计算机化简 多变量逻辑函数。多变量逻辑函数。数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院列表化列表化简简简简法法 Q-MQ-M法化简逻辑函数的步骤如下:法化简逻辑函数的步骤如下: 第一步,将函数表示成最小项表达式。第一步,将函数表示成最小项表达式。 第二步,找出函数的全部质蕴涵项。第二步,找出函数的全部质蕴涵项。1 1、将、将n n变量函数中的相邻最小项合并,消去相异的一个变变量函数中的相邻最小项合并,消去相异的一个变 量,得到量,得到(n-1)(n-1)个变量的与项(蕴涵项)。个变量的与项(蕴涵项)。 这时如果存在这时如果存在 不能合并的最小项,它便是所寻找的部分质蕴涵项。不能合并的最小项,它便是所寻找的部分质蕴涵项。2 2、再将相邻的(、再将相邻的(n-1n-1)个变量的与项合并,消去相异的一)个变量的与项合并,消去相异的一 个变量,得到(个变量,得到(n-2n-2)个变量的与项(蕴涵项)个变量的与项(蕴涵项) ,这里如,这里如 果存在不能合并的(果存在不能合并的(n-1n-1)个变量的与项,则它们也是所)个变量的与项,则它们也是所 寻找的质蕴涵项。寻找的质蕴涵项。如此进行下去,直到不能再合并为止。得全部的质蕴涵项如此进行下去,直到不能再合并为止。得全部的质蕴涵项 。数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院列表化列表化简简简简法法 第三步,找出函数的必要质蕴涵项。第三步,找出函数的必要质蕴涵项。先画出质蕴涵表,然后在表上找出仅属于一先画出质蕴涵表,然后在表上找出仅属于一 个质蕴涵项的最小项,则包含该最小项的质蕴涵个质蕴涵项的最小项,则包含该最小项的质蕴涵 项就是必要质蕴涵项。项就是必要质蕴涵项。 第四步,找出函数的最小覆盖。第四步,找出函数的最小覆盖。当第三步找出的必要质蕴涵项不能包含函数当第三步找出的必要质蕴涵项不能包含函数 的全部最小项时,可以通过行、列消去法,找出的全部最小项时,可以通过行、列消去法,找出 最小覆盖的其他必要质蕴涵项。最小覆盖指包含最小覆盖的其他必要质蕴涵项。最小覆盖指包含 函数的全部最小项的最小质蕴涵项集合。函数的全部最小项的最小质蕴涵项集合。数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院列表化列表化简简简简法法 用用Q-MQ-M法化简函数法化简函数 : :数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院111111111AB CD 00 01 11 1000 01 11 10 列表化列表化简简简简法法 (1 1)找出全部质蕴涵项)找出全部质蕴涵项做最小项分组表并找出不能合并者做最小项分组表并找出不能合并者: :将最小项将最小项mmi i按变量取值表示成二进制数;其次,再根按变量取值表示成二进制数;其次,再根 据这些二进制数中所包含据这些二进制数中所包含1 1的个数从少到多的次序进行分的个数从少到多的次序进行分 组排队;最后,把含有组排队;最后,把含有1 1的个数相同的最小项划分成一组的个数相同的最小项划分成一组 ,组内按下标,组内按下标i i的取值从小到大排列,如此制成最小项分的取值从小到大排列,如此制成最小项分 组。组。从含有从含有1 1个数最少的那组开始,在相邻组内比较最小个数最少的那组开始,在相邻组内比较最小 项,将只有一个变量值不同的两个最小项合并,消去一个项,将只有一个变量值不同的两个最小项合并,消去一个 变量,并在已合并的最小项的右边变量,并在已合并的最小项的右边P Pi i栏内做记号栏内做记号“ “”,表,表 示该项已被合并。在不能合并的最小项的右边示该项已被合并。在不能合并的最小项的右边P Pi i栏内填入栏内填入P P1 1,则,则 就是所寻找的质蕴涵项。注意合并最就是所寻找的质蕴涵项。注意合并最 小项只能处于相邻的两组内,而不能处于同组或隔组内。小项只能处于相邻的两组内,而不能处于同组或隔组内。数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院列表化列表化简简简简法法 数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院 1 1 1 11 1 1 115154 4 0 1 1 10 1 1 17 73 3 1 0 1 01 0 1 01010P P1 11 0 0 11 0 0 19 9 0 1 1 00 1 1 06 6 0 1 0 10 1 0 15 52 2 0 1 0 00 1 0 04 4 0 0 1 00 0 1 02 21 1 0 0 0 00 0 0 00 00 0P Pi i变变变变量量 A B C DA B C D最小最小项项项项 编编编编号号组组组组号号 (1 1的个数)的个数)最小项分组表最小项分组表 列表化列表化简简简简法法 做(做(n-1n-1)个变量与项分组表并找出不能合并者)个变量与项分组表并找出不能合并者: :在最小项合并过程中,用符号在最小项合并过程中,用符号“ “”表示被消表示被消 去的变量,这样便得到若干个带有去的变量,这样便得到若干个带有“ “”的与项,的与项, 或称作合并项。按照对最小项的分组方法,对带或称作合并项。按照对最小项的分组方法,对带 有有“ “”的与项进行分组。对相邻组中的的与项进行分组。对相邻组中的“ “”处于处于 相同位置的那些与项进行合并,已合并的与项做相同位置的那些与项进行合并,已合并的与项做 记号记号“ “”,并记入,并记入PiPi栏;在不能合并的与项的栏;在不能合并的与项的PiPi栏栏 内记入内记入P2P2和和P3P3,则,则 也是质蕴涵项。也是质蕴涵项。数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院列表化列表化简简简简法法 组组组组 号号 (1 1)最小最小 项项项项 编编编编号号变变变变量量 A B C DA B C DP Pi i0 00 02 20 0 0 0 0 0 0 04 40 0 0 00 0 1 12 26 60 1 00 1 0 2 21010 0 1 0 0 1 0P P2 24 45 50 1 0 0 1 0 4 46 60 1 00 1 0 2 25 57 70 1 10 1 1 6 67 70 1 1 0 1 1 3 37 71515 1 1 1 1 1 1P P3 3数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院 1 1 1 11 1 1 115154 4 0 1 1 10 1 1 17 73 3 1 0 1 01 0 1 01010P P1 11 0 0 11 0 0 19 9 0 1 1 00 1 1 06 6 0 1 0 10 1 0 15 52 2 0 1 0 00 1 0 04 4 0 0 1 00 0 1 02 21 1 0 0 0 00 0 0 00 00 0P Pi i变变变变量量 A B C DA B C D最小最小 项项项项 编编编编号号组组组组号号 (1 1的个数)的个数)最小项分组表最小项分组表 (n-1n-1)个变量与项分组表)个变量与项分组表列表化列表化简简简简法法 做(做(n-2n-2)个变量与项分组表并找出不能合并者:)个变量与项分组表并找出不能合并者:在(在(n-1n-1)个变量与项合并过程中,也用符号)个变量与项合并过程中,也用符号“ “ ”表示被消去的变量,这样便得到若干个带有两个表示被消去的变量,这样便得到若干个带有两个 “ “”的与项。按照上述的分组方法,得到(的与项。按照上述的分组方法,得到(n-2n-2)个)个 变量与项分组表。变量与项分组表。由表可以看出,仅有的两(由表可以看出,仅有的两(n-2n-2)个变量与项不)个变量与项不 能再合并,在能再合并,在PiPi栏内分别记入栏内分别记入P4P4和和P5P5,P4P4和和P5P5就就 是最后所寻找的质蕴涵项。是最后所寻找的质蕴涵项。数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院列表化列表化简简简简法法 组组组组号号 (1 1的个数)的个数)最小最小项项项项 编编编编号号变变变变量量 A B C DA B C DP Pi i0 00 0 2 24 4 6 6 0 00 0P P4 41 14 4 5 56 6 7 7 0 1 0 1 P P5 5数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院组组组组 号号 (1 1)最小最小 项项项项 编编编编号号变变变变量量 A B C DA B C DP Pi i0 00 02 20 0 0 0 0 0 0 04 40 0 0 00 0 1 12 26 60 1 00 1 0 2 21010 0 1 0 0 1 0P P2 24 45 50 1 0 0 1 0 4 46 60 1 00 1 0 2 25 57 70 1 10 1 1 6 67 70 1 1 0 1 1 3 37 71515 1 1 1 1 1 1P P3 3(n-2n-2)个变量与项分组表)个变量与项分组表(n-1n-1)个变量与项分组表)个变量与项分组表列表化列表化简简简简法法 列出全部质蕴涵项列出全部质蕴涵项由上述分析可得全部质蕴涵由上述分析可得全部质蕴涵项:数字逻辑电路数字逻辑电路吉林大学计算机科学与技术学院列表化列表化简简简简法法 (2 2)找出必要质蕴涵项)找出必要质蕴涵项将函数的最小项和上述的质蕴涵项做序列表将函数的最小项和上述的质蕴涵项做序列表 ,并在质蕴涵项包含的最小项下面填入符号,并在质蕴涵项包含的最小项下面填入符号“ “”,”, 即做所谓质蕴涵表。即做所谓质蕴涵表。找出那些仅属于一个质蕴涵项的最小项,如找出那些仅属于一个质蕴涵项的最小项,如 m0m0仅属于仅属于P4P4;m5m5仅属于仅属于P5P5;m9m9仅属于仅属于P1P1; m10m10仅属于仅属于P2P2;m15
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号