奎因-麦克拉斯基算法

✍ dations ◷ 2024-09-20 18:37:22 #布尔代数,算法

奎因-麦克拉斯基算法(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\,}

相关

  • 烟灰缸烟灰缸,是一个盛载烟灰、烟头的器皿,形状似一个开口碗、有盖的盒、邮箱,或者垃圾桶等。烟灰缸用料为耐燃物料,包括石、瓦、金属等。礼品公司不少利用烟灰缸表面作广告宣传。在禁
  • 公理系统数学上,一个公理系统(英语:Axiomatic system,或称公理化系统,公理体系,公理化体系)是一个公理的集合,从中一些或全部公理可以一并用来逻辑地导出定理。一个数学理论由一个公理系统和
  • 斜方正交晶系,也叫斜方晶系。 该晶系特点是没有高次对称轴,二次对称轴和对称面总和不少于三个。晶体以这三个互相垂直的二次轴或对称面法线为结晶轴。α=β=γ=90o;a≠b≠c。非均质
  • 甘博甘博(英语:Sidney David Gamble,1890年7月12日-1968年3月29日),美国社会学家。他曾四度前往中国,其间拍摄过大量有关中国的珍贵照片。甘博出生于俄亥俄州辛辛那提,他是宝洁公司创始
  • 弗朗西斯·伊西德罗·埃奇沃思弗朗西斯·伊西德罗·埃奇沃思,FBA(英语:Francis Ysidro Edgeworth,1845年2月8日-1926年2月13日),盎格鲁-爱尔兰哲学家和政治经济学家,他在1880年代对统计学方法做出了巨大贡献。从1
  • 约多省坐标:6°35′00″N 1°30′00″E / 6.5833°N 1.5000°E / 6.5833; 1.5000约多省(法语:Préfecture de Yoto),是多哥的30个省份之一,位于该国南部,由滨海区负责管辖,首府设于塔布利
  • 保罗·博伊尔保罗·约瑟夫·博伊尔(1964年11月16日-,英语:Paul Joseph Boyle,CBE, FRSE, FBA),是一名英国地理学家、教育家和学校管理者。2014年至2019年期间,担任莱斯特大学副校长。1999年至2014
  • 斯特利奥斯·马莱扎斯斯特利奥斯·马莱扎斯(Stelios Malezas)是希腊的一位足球运动员。在场上司职后卫。他现在效力于希腊超级足球联赛球队萨丁。他也代表希腊国家足球队参赛。2019年6月24日,马莱扎
  • 何佐治何佐治(1904年10月9日-1962年8月10日),字秉伦。广东省高要县银江乡坑塘村人。民国37年(1948年)在商业团体南区当选第一届立法委员
  • 兰亚里角兰亚里角(保加利亚语:нос Раняри)是南极洲的海岬,位于葛拉汉地,处于桑迪尔角东南面6.7公里和迪萨波因特门特角北端以西5.2公里,以保加利亚统治者命名。坐标:65°31′53″S