奎因-麦克拉斯基算法

✍ dations ◷ 2025-07-02 14:46:52 #布尔代数,算法

奎因-麦克拉斯基算法(Quine-McCluskey算法)是最小化布尔函数的一种方法。它在功能上等同于卡诺图,但是它具有文字表格的形式,因此它更适合用于电子设计自动化算法的实现,并且它还给出了检查布尔函数是否达到了最小化形式的确定性方法。

方法涉及两步:

尽管在处理多于四个变量的时候比卡诺图更加实用,奎因-麦克拉斯基算法也有使用限制,因为它解决的问题是NP-困难的:奎因-麦克拉斯基算法的运行时间随输入大小而呈指数增长。可以证明对于个变量的函数,素蕴涵项的数目的上界是3/。如果 = 32,则可能超过6.1 * 1014,或617万亿个素蕴涵项。有大量变量的函数必须使用潜在的非最优的启发式方法来最小化。

最小化一个任意的函数:

你能轻易的形成这个表的规范的积之和表达式,简单的通过总和这个函数求值为一的那些极小项(除掉那些不关心项):

当然,这的确不是最小化的。为了优化,所有求值为一的极小项都首先放到极小项表中,不关心项也可以加入这个表中与极小项组合:

现在你可以开始把极小项同其他极小项组合在一起。如果两个项只有一个二进制位的数值不同,则可以这个位的数值可以替代为一个横杠,来指示这个数字无关紧要。不再组合的项标记上 "*"。

没有项可以继续进一步这样组合,所以现在我们构造一个本质量蕴涵项表。纵向是刚才生成的素蕴涵项,横向是早先指定的极小项。

这里的每个本质素蕴涵项都标记了星号 - 第二个素蕴涵项能被第三个和第四个所覆盖,而第三个素蕴涵能被第二个和第一个所覆盖,因此都不是本质的。如果一个素蕴涵项是本质的,则同希望的一样,它必须包含在最小化的布尔等式中。在某些情况下,本质量蕴涵形不能覆盖所有的极小项,此时可采用额外的简约过程。最简单的“额外过程”是反复试验,而更系统的方式是Petrick方法。在当前这个例子中,本质量蕴涵项不能处理所有的极小项,你可以组合这两个本质量蕴涵项与两个非素蕴涵项中的一个而生成:

最终的等式在功能上等价于最初的(冗长)等式:

f A , B , C , D = A B C D + A B C D + A B C D + A B C D + A B C D + A B C D + A B C D + A B C D {\displaystyle f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+ABCD'+ABCD\,}

相关

  • 心房颤动心房颤动(英语:Atrial fibrillation,简称:Af 或 A-fib),又称为心房微颤、房颤、心房纤维性颤动、心房纤颤、房性纤颤等,是心脏不正常节律/心律不整的一种,特色是心脏快速而不规则的
  • 日落综合征日落症候群是部分老人痴呆症或阿兹海默症患者的其中一种病征,发病率由一成至三成不等,患者一到日落、傍晚时刻,就开始出现焦躁、躁动、幻觉、甚至产生攻击倾向。日落症候群的成
  • 詹姆斯二世詹姆斯二世(1430年10月16日-1460年8月3日)苏格兰斯图亚特王朝国王。苏格兰国王詹姆斯一世之子。周岁生日前,詹姆斯二世的孖生兄长罗斯西公爵亚历山大(英语:Alexander Stewart, Duk
  • 膦酸酯膦酸酯和膦酸是含有C-PO(OH)2或C-P(OR)2的有机磷化合物基团(其中R是烷基或芳基)。通常作为盐处理的膦酸通常是白色。它是难挥发的固体,难溶于有机溶剂,但可溶于水和醇。许多商业
  • 古希腊宗教节庆:庞提克大草原高加索地区东亚东欧南欧庞提克大草原北方/东方大草原欧洲地区南亚地区西伯利亚大草原欧洲高加索地区印度印度-雅利安民族伊朗民族欧洲民族东亚印欧民族欧洲
  • 斯洛文尼亚广播电视台斯洛文尼亚广播电视台(斯洛文尼亚语:Radiotelevizija Slovenija)是斯洛文尼亚的国家公共广播电视机构,总部位于卢比安纳,另外在科佩尔和马里博尔拥有地区广播中心。斯洛文尼亚广
  • 麦丽丝麦丽丝(1956年11月-),蒙古族,中国电影导演、编剧,内蒙古电影制片厂一级导演。她曾与丈夫塞夫共同获得1998年第18届中国电影金鸡奖最佳导演奖,还曾两次获得中国电影华表奖优秀导演奖
  • 奥斯卡·闵可夫斯基奥斯卡·闵可夫斯基(Oskar Minkowski 1858年1月13日-1931年7月18日)德国生物化学家、布雷斯劳大学教授,胰岛素的发现者。数学家赫尔曼·闵可夫斯基的哥哥、天天物理学家鲁道夫·
  • A Shared Dream“A Shared Dream”是韩国的男子组合U-KISS的第1枚原创日语专辑。于2012年2月29日发行。唱片公司为avex trax。
  • 比洛利比洛利(Biloli),是印度马哈拉施特拉邦Nanded县的一个城镇。总人口13430(2001年)。该地2001年总人口13430人,其中男性6922人,女性6508人;0—6岁人口2218人,其中男1156人,女1062人;识字率