奎因-麦克拉斯基算法

✍ dations ◷ 2025-09-07 15:01:06 #布尔代数,算法

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

相关

  • 支架支架(Stent)是一种应用于植入型外科手术的管状器具,以治疗体内病变的管道例如血管、食道或输尿管等,恢复管道的正常运输功能。支架一般是永久或半永久植入于患者体内,但亦可以意
  • 比较分子场方法比较分子场方法(Comparative Molecular Field Analysis),减缩写为CoMFA,是一种理论药物化学的计算方法。相比传统的QSAR方法只考虑分子的二维结构信息,要求化合物属于同系物,有
  • 黑色一月大屠杀高加索军区黑色一月大屠杀(阿塞拜疆语:Qara Yanvar),也被称为黑色星期六或一月大屠杀,是1990年1月19-20日苏联解体前实施紧急状态期间在苏联境内阿塞拜疆地区巴库的一场大屠杀。
  • 科 (生物)科(英文: family, 拉丁语:)是生物分类法中的一级,位于目和属之间,现时生物界约有800个科,科下也分亚科,而在其上亦有总科。亚科是生物分类法的一级,在科和属之间,有时亚科和属之间也
  • 和宁 (地名)和宁为朝鲜王朝开国之君太祖李成桂诞生之地,位于今朝鲜咸镜南道金野郡(旧称永兴郡)。本高句丽之地。高丽光宗六(955)年,始筑城堡。高丽成宗十五(995)年,改为和州。高丽高宗四十五(1258
  • 霍季姆利亚河霍季姆利亚河(乌克兰语:Хотімля),是乌克兰的河流,位于该国东部,流经哈尔科夫州,发源自普里科洛特涅,最终注入佩尔绍特拉夫涅韦,河道全长38公里,流域面积341平方公里。
  • BG~身边警护人~《BG~身边警护人~》(日语:BG〜身辺警護人〜),2018年1月18日于朝日电视台周四晚间九点连续剧播出。主演为木村拓哉 。2020年3月宣布开拍第二季。岛崎章(木村拓哉饰)过去曾经是一位保
  • 杜近芳杜近芳(1932年-),北京人,中国京剧表演艺术家,工旦行,师承梅兰芳。她从1951年起成为国家演员,在中国文化部中国戏曲研究院(现在的中国艺术研究院)的实验京剧团(后来的中国京剧团、中国京
  • 全局搜索全局搜索(英语:Global search),又称为全域搜索,一般而言为本地搜索(英语:Local search (Internet))的对应概念。在不同的领域该词所表示含义不完全一致。通常而言,全局搜索一般表示一
  • 人道报节人道报节(法语:Fête de l'Humanité)是法国每年9月举行的大型游园活动。该活动得名于法国共产党党报《人道报》,由《人道报》社主办。第一次人道报节举行于1930年9月,初衷是为了