奎因-麦克拉斯基算法

✍ dations ◷ 2025-07-23 06:27:37 #布尔代数,算法

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

相关

  • 热膨胀系数 (α)热膨胀系数(Coefficient of thermal expansion,简称CTE)是指物质在热胀冷缩效应作用之下,几何特性随着温度的变化而发生变化的规律性系数。实际应用中,有两种主要的热膨胀系数,分
  • 帽子帽子是戴在头部的服饰,有遮阳、挡雨、防尘、美观、保护头部等用途。以下列出几种常见的帽子款式,详见帽子款式列表.
  • 蟋蟀雨蛙蟋蟀雨蛙(Acris gryllus)是美国东南部一种细小的树蟾。它们的外观及习性与北蝗蛙很相近,以往一直被认为是同一物种。其种小名是拉丁文蟋蟀的意思。蟋蟀雨蛙长1.6-3.2厘米,比北蝗
  • 共同市场共同市场(英语:Common market)或称单一市场(英语:Single market)。经济一体化的主要阶段并举例说明优惠贸易安排:在实行优惠贸易安排的成员间,通过协定或其他形式对全部商品或部分商
  • 圣日耳曼欧塞尔教堂圣日耳曼欧塞尔教堂(Saint-Germain-l'Auxerrois)位于巴黎卢浮宫广场2号,最近的地铁站是卢浮宫-里沃利。位于巴黎市中心,邻近塞纳河及卢浮宫,曾是法国国王的堂区,通常被视为是卢浮
  • 严肃文学严肃文学是一个含义广泛的概念,泛指创作态度严肃认真、形式拘谨而内容庄重、并具有丰富的思想内涵的文学。以福尔摩斯系列侦探文学而闻名的阿瑟·柯南·道尔在出版《血字的研
  • 二硒化铂二硒化铂是一种无机化合物,化学式为PtSe2。它是层状物质,可以分成薄层至三原子厚的单层。厚度不同,PtSe2可以展现出半金属或半导体特性。二硒化铂在自然界中以硒铂矿(Sudovikovi
  • 莱斯·亨特莱斯利·亨特(英语:Leslie Hunter,1942年8月16日-2020年3月27日),美国NBA联盟职业篮球运动员。他在1964年的NBA选秀中第2轮第9顺位被底特律活塞选中。
  • 蝴蝶刀蝴蝶刀(英语:Balisong、butterfly knife、fan knife)发源自菲律宾巴坦加斯。是一种可折叠的小刀。两个被轴承固定柄脚上的刀柄可以经由旋转而成为收纳刀片的刀鞘,打开时能以刀柄
  • 绿鞋绿鞋(Greenshoe),也称绿鞋机制或绿鞋期权,是首次公开募股(IPO)招股说明书中的一项特殊条款,指允许承销商(英语:underwriters)向投资者出售比发行人原计划更多的股票,在法律上被称为“超