- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
转载请务必注明出处: https://www.cnblogs.com/the-wind/p/15764283.html 。
香农在他的硕士论文[1]中提出了开关电路的综合方法,其中提到香农展开定理,即任意n变量布尔函数 \(f(x_1,...,x_{n-1},x_n)\) 都可展开为SOP:
亦可根据布尔代数的对偶性得到等价的POS形式。SOP或POS对应布尔网络深度为2,现在一般称为两级逻辑.
这种方法很容易综合组合逻辑,其缺点是对于特定布尔函数存在指数爆炸问题(结点数可达 \(O(n^2)\) ),此外各结点的扇入扇出一般较高。为了降低开销,需要进行逻辑化简.
两级逻辑化简是输出限制于SOP/POS形式的逻辑化简。之所以希望输出仍然是两级逻辑,是因为两级逻辑具有特定优势,例如物理结构规则,传播延迟低等,过去常见于可编程逻辑器件(PLD)中.
一些概念:
变元:x1,x2,...xn 文字:变元或其否定:x1, x1',... 子句(乘积项):文字的合取:x1x2, x1'x2,... 。
逻辑化简本质上是对表达式进行等价转化以最小化代价函数的优化过程,其中代价函数评估了表达式的优劣(如对应电路的PPA)。定义SOP表达式E的代价函数为:
给定布尔函数f, \(\arg\min\limits_{E=f} \mathcal{L}(E)\) 即为两级逻辑化简的结果,其中E必须是SOP表达式.
\(\arg\min\limits_{E=f} \mathcal{L}(E)\) 具有最小的电路面积,这是因为E的子句的个数决定第二级逻辑(OR)的面积,文字的个数决定第一级逻辑(AND)的面积.
根据卡诺图,容易想到如下算法:对f的所有最小项,利用并项法则(xy + x'y = y)合并相邻两项(恰有一对互补的变元,其余文字相同),其结果是代价函数减少了2(子句个数和文字个数都减少1)。对合并得到的所有子句迭代地应用并项法,直到无法合并为止,所得子句的析取显然与f是逻辑等价的,且代价函数小于等于初值.
不幸的是,这方法有时 不能 得到最优解,举反例证明:f=xy'+x'y+yz'+y'z,无法对其应用并项法,算法结束,但事实上f=xy'+x'y+yz'和f=xy'+x'y+y'z都比原式更简。这种启发式失败了。幸运的是Quine通过引入素蕴涵项成功解决了问题,而素蕴涵的求解与上述过程类似.
要理解素蕴涵的概念,需要一些前置知识,准备好后我们将结合Quine[2]的定理,证明:
定理1 :代价函数 \(\mathcal{L}(E)\) 定义的最小SOP表达式一定是 素蕴涵项 之析取 。
这定理提供了Q-M算法的核心思路:在E的素蕴涵项的组合中寻找答案.
首先需要明确ON/OFF集与无关DC集(Don't care set)的概念。逻辑函数 \(f: \{0,1\}^n \rightarrow \{0,1,*\}\) ,f的反函数记为 \(f^{-1}\) 。ON定义为 \(f^{-1}(1)\) ,即f=1的所有最小项。OFF定义为 \(f^{-1}(0)\) 。DC定义为 \(f^{-1}(*)\) 。一个逻辑函数f可以表示为 \(f=ON \cup DC\) .
例如,给定逻辑函数g(x,y,z)=xy+z,无关项xyz,其ON集为{xyz',x'y'z,x'yz,xy'z},DC集为{xyz},OFF集为{x'y'z',x'yz',xy'z'}.
给定函数f和从句p,如果 \(p \subseteq ON \cup DC\) ,则p是f的一个 蕴涵项 。如在上面例子中 \(\{x'z\}\subseteq ON\) 。注意上述包含关系实质上为布尔代数上的偏序关系, \(p \subseteq f \iff p \preceq f\) 。下文将大量应用布尔代数的一些性质和定理而不加说明.
显然有 \(ON \subseteq \sum_{p\in f}p\) ,即f的所有蕴涵项盖住了f=1的全部最小项,且根据定义 \(OFF \not\subset \sum_{p\in f} p\) ,即不盖住f=0的最小项f.
如果p是f的蕴涵项,且f不存在其它的蕴涵项 \(p'\) 满足 \(p \subseteq p'\) ,p'具有更少的文字,那么p同时也是f的 素蕴涵项 .
下面证明定理1: 设与 \(E\) 等价的SOP表达式为 \(\Phi\) , \(\Phi\) 的每个子句为 \(e\) ,且 \(\mathcal{L}(\sum_{e \subseteq \Phi} e)\) 取最小值。 显然 \(e\subseteq \Phi\) , \(e\subseteq E\) 。 如果 \(\Phi\) 的子句中存在e不是素蕴涵,则存在 \(b\subseteq \Phi\) ,满足 \(e \subseteq b\) ,b文字数小于等于e。 所以存在 \(\varphi=(\Phi-{e})\cup b\) , \(\mathcal{L}(\sum_{b \subseteq \varphi} b) < \mathcal{L}(\sum_{e \subseteq \Phi} e)\) ,与假设矛盾 所以e必须是E的素蕴涵。 Q.E.D 。
可见算法的最优性是由素蕴涵的定义保证的,如何计算所有符合定义的素蕴含项就成为核心问题。我们在下一节证明一些引理后就可以设计出枚举素蕴涵的算法.
暂时回到整个化简算法,定理1给出了最优解的必要条件,因此只需在所有素蕴涵项 \(P\) 中找解。显然最优解 \(M \subseteq P\) 满足如下条件:
(1) \(M\) 与原始函数逻辑等价,即 \(ON \subseteq M \subseteq (ON \cup DC)\) 。
(2) \(\mathcal{L}(\sum_{p \in M} p)\) 取最小值.
子集 \(M\) 的选择是一个组合优化问题。稍后的分析将看到,其本质为集合覆盖问题(SCP).
Quine利用如下性质和定理计算蕴涵项:
并项法:xy + x'y = y 。
定理3 :y是xy + x'y的蕴涵项 。
证明: \(y是xy + x'y的蕴涵项\) \(\iff y \preceq xy + x'y\) \(\iff y(xy + x'y)' = \bf{0}\) \(\iff yy' = \bf{0}\) Q.E.D 。
定理3表明,对相邻两项(仅相差一对互补的变元)之和应用并项法可以导出一个蕴涵项.
然而定理3中的蕴涵项不一定是素蕴涵项,如下定理用于计算素蕴涵项:
定理4:如果函数f的一对蕴涵项a、b可根据并项法产生新的蕴涵项c,则a、b不是素蕴涵项.
证明: 由布尔代数性质: \(a \preceq a + b\) \(b \preceq a + b\) 又蕴涵项c是由a、b并项产生的,即 \(c = a + b\) 所以 \(a \preceq c\) 且 \(b \preceq c\) 因为a、b是f的蕴涵项, \(a \preceq f\) 、 \(b \preceq f\) 所以 \(a + b \preceq f\) ,即 \(c \preceq f\) 所以函数f存在另一个蕴涵项c,且满足 \(a \preceq c\) 且 \(b \preceq c\) 。 因为并项法结果必然少1个文字,所以c的文字少于a、b。 上述两条结论与素蕴涵项的定义矛盾,所以a、b不是素蕴涵项 Q.E.D. 。
根据定理4,可设计一种基于筛选的算法,从一组蕴涵项T中求素蕴涵:
算法中如果a、b可以并项,不能 删除 a、b,而要继续跟其它项合并。设想如果删除了a、b,就会丢失只有与a、b并项才能得到的蕴含项。这与本文一开始提到的迭代算法有所不同.
注意到布尔函数f的所有最小项都是蕴涵项,以这些蕴涵项为初始的T,运用上述算法可计算出f的所有素蕴涵项.
因为所有最小项构成原子,合并原子所得素蕴涵项没有遗漏,结果是完备的.
上述算法的P2蛮力实现需要 \(O(n^2)\) 时间。经过简单优化后,得到Quine求素蕴涵的算法:
算法1:计算所有素蕴涵项 |
---|
输入:ON:f=1的所有最小项 |
输出:PI:素蕴涵项集合 |
1. 将ON中的乘积项按反变量(变量的补)的个数分组。没有出现反变量的项归为第n组、有1个反变量的项为n-1组、……、有n个反变量的项为第0组。 |
2. 依次比较相邻两组(第 \(i\) 和 \(i+1\) , \(i-1\) 组(如果存在的话)的每一对乘积项(从第 \(i\) 组选择一个乘积项,再从第 \(i+1\) 或 \(i-1\) 组选择一个乘积项构成一对)。如果这对乘积项仅一个文字不同(形如xy与x'y),则标记这两项,根据并项法生成一个蕴涵项y。 |
3. 迭代处理:如果步骤2生成了一些蕴涵项,令ON为新生成的蕴涵项构成的集合,转到1;如果不再生成任何蕴涵项,结束。 |
经过上述步骤,所有未被标记的乘积项就是PI。 |
算法中只需相邻两个分组比较,因为不相邻的分组必不可合并.
下面举一些实例.
例1 :Quine算法计算f=x'y'z'+x'zw'+xy'zw'+xy'z'的素蕴涵项 香农展开得到最小项表达式f=x'y'z'w' + x'y'z'w + x'y'zw' + x'yzw' + xy'z'w' + xy'z'w + xy'zw' 分组、迭代计算过程如下:
最小项 + 标记 1次迭代 + 标记 2次迭代 + 标记 第0组 x'y'z'w' √ 第1组 x'y'z'w √
x'y'zw' √
xy'z'w' √
x'y'z' √
x'y'w' √
y'z'w' √第2组 x'yzw' √
xy'z'w √
xy'zw' √
y'z'w √
x'zw'
y'zw'
xy'z' √
xy'w' √
y'z'
y'w'未标记√的项:x'zw'、y'zw'、y'z'、y'w'即为所有素蕴涵项.
上述算法未考虑含无关项的情况。下面扩展上述算法使其能够处理无关项:单独标记无关项,当用并项法合并a、b两项时,如果a、b都标记为无关项,那么结果c也标记为无关项。最后所有标记了d的素蕴涵项都可以丢弃.
例2 :Quine算法计算f=yz'+xy'z(无关项d=x'z)的素蕴涵项 。
最小项 + 标记 1次迭代 + 标记 第0组 x'yz' √
x'y'z √ d第1组 x'yz √ d
xyz' √
xy'z √x'y
yz'
x'z d
y'z未标记√和 d 的项:x'y、yz'、y'z即为所有素蕴涵项.
Quine方法计算出了函数f的所有素蕴涵项 \(P\subseteq (ON \cup DC)\) 。回顾3.2,为了生成最小SOP,我们要选出P的一个子集M,该子集要满足 \(ON \subseteq M \subseteq (ON \cup DC)\) ,同时代价函数 \(\mathcal{L}(\sum_{p \in M} p)\) 要最小化,这是一个组合优化问题.
下面以例1说明该问题.
上面覆盖矩阵的行对应最小项,列对应素蕴涵项,矩阵元素 \(a_{ij}=1\) 表示第j个素蕴涵项盖住第i个最小项(事实上只需满足素蕴涵项j的所有文字都包含在最小项i中。这里粗略证明:设素蕴涵项为p,最小项为m。假设m=1,则m中每个文字=1,又因为p的所有文字都包含在m中,所以p的每个文字=1,所以p=1,所以 \(m \Rightarrow p\) ,所以 \(m \preceq p\) ).
为了满足 \(ON \subseteq M\) ,我们需要恰当选取一些列,使得这些列构成的矩阵每一行都至少有一个1。例如选择列x'zw'、y'z'和y'w'构成如下矩阵:
这个例子中矩阵每行都至少有一个1,这意味着所有最小项都至少被一个选定的素蕴涵项盖住,即 \(ON \subseteq \{x'zw', y'z', y'w'\}\) ,所以选择M={x'zw', y'z', y'w'}是可行的.
为了最小化代价函数 \(\mathcal{L}(\sum_{p \in M} p)\) ,选择的列应尽可能少;当存在多种列数相同的方案时,应优先选择文字数少的方案。例1只有唯一可行解,代价函数 \(\mathcal{L}(x'zw' + y'z' + y'w') = 10\) ,最小SOP表达式为x'zw' + y'z' + y'w'.
问题本质上是集合覆盖问题(SCP),该问题是NP-hard的。求解SCP的方法主要有分支限界法(保证最优性)和启发式算法,涉及大量剪枝和优化方法,本文无法一一列举.
这里说一种新的求解思路:将SCP编码为Max-SAT问题.
SAT问题是说判断CNF表达式的可满足性。若存在真值指派使表达式为1(即CNF的所有从句都满足),则CNF是可满足的;如果这组值不存在,则判定为不可满足(可证伪的)。 Weighted Partial Max-SAT(WPMS)是SAT的变种,将CNF表达式中的子句分成软/硬子句,要求所有硬子句都满足,同时最小化不满足的软子句的权重之和,属于优化问题.
求解上述问题,得变元赋值v0,v1,v2,...,vi,对应第i个素蕴含项是否被选中.
最近的2022 MaxSAT Evaluation结果可在 https://maxsat-evaluations.github.io/2022/rankings.html 查看,代表了SAT求解器的SOTA。 MaxSAT的求解并不是本文重点,直接调用Loandra求解器.
第3节中的例1,将Quine算法得到的素蕴含项 \(x'zw', y'zw', y'z', y'w'\) 分别编号1 2 3 4,按4.1.1节所述编写CNF文件如下:
c QM logic simplify
h 3 4 0
h 3 0
h 1 2 4 0
h 1 0
h 3 4 0
h 2 4 0
3 -1 0
3 -2 0
2 -3 0
2 -4 0
(h表示硬子句,0表示输入结束,数字开头的行表示软子句的权重,-号表示否定 \(\neg\) ) 。
执行./loandra input.txt,得到求解结果:
c ========================================[ Problem Statistics ]===========================================
c |
c | Problem Format: MaxSAT
c | Problem Type: Weighted
c | Number of variables: 4
c | Number of hard clauses: 6
c | Number of soft clauses: 4
c | Number of cardinality: 0
c | Number of PB : 0
c | Parse time: 0.00 s
c |
o 7
s OPTIMUM FOUND
v 1011
loandra给出的解为1011,对应每个素蕴含项是否可取,因此化简结果为 \(x'zw' + y'z' + y'w'\) .
[1] C. E. Shannon, "A symbolic analysis of relay and switching circuits," in Electrical Engineering, vol. 57, no. 12, pp. 713-723, Dec. 1938, doi: 10.1109/EE.1938.6431064. [2] Quine, W. V.. “The Problem of Simplifying Truth Functions.” American Mathematical Monthly 59 (1952): 521-531. 。
最后此篇关于Quine-McCluskey两级逻辑化简算法原理解析的文章就讲到这里了,如果你想了解更多关于Quine-McCluskey两级逻辑化简算法原理解析的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我读过 Ken Thompson 的经典论文 Reflections on Trusting Trust他在其中提示用户写一个 Quine作为他的论点的介绍(强烈推荐阅读)。 A quine is a
我只知道一个证明者可以翻译 Quine 在他的《逻辑方法》一书中为经典命题逻辑提供的算法(哈佛大学出版社,1982 年,第 1 章第 5 章,第 33-40 页),这个证明者在 Haskell 中,它
转载请务必注明出处: https://www.cnblogs.com/the-wind/p/15764283.html 目录 1 背景介绍:两级逻辑
我正在创建一个 Quine在 C 中,我需要在其中创建一个新的 c 文件,然后编译并执行它。 我做了一个简单的片段来理解为什么它不起作用。 我的猜测是 execv 在 fprintf 完成写入之前启动
最短的 bash quine 是空字符串: $ bash -c '' $ 生成自己的源代码作为输出的最短的非空 bash 脚本是什么? 最佳答案 19 个字符: $echo 'echo $BASH_C
最短的 bash quine 是空字符串: $ bash -c '' $ 生成自己的源代码作为输出的最短的非空 bash 脚本是什么? 最佳答案 19 个字符: $echo 'echo $BASH_C
我最近发现了这个 quine $a='$a=%c%s%c;printf($a,39,$a,39,10);%c';printf($a,39,$a,39,10); 我就是想不通。我在 google/SO
来源:Rosettacode Quine for HTML/CSS (找到 HTML/CSS 部分)。 以下代码在保存为 html 文件时,在浏览器中呈现为源代码。 HTML/CSS Q
这是一个特殊的 Haskell 程序,输出一个 Python 程序,输出一个 Ruby 程序,Ruby 程序输出原始的 Haskell 程序(来自 http://blog.sigfpe.com/200
根据标题,是否可以创建一个(非平凡的)quine在 HTML 中? 我对 HTML quine 的定义: A non-trivial HTML quine is one that is not nul
Another SO question提到了 Yusuke Endoh 的神奇 quine。 quine 是一种计算机程序,它会生成自己的源代码副本作为其唯一输出;这个做了一个转折。 A must-s
我已经创建了一个图灵完备的编程语言(已经被证明),所以一定可以写一个 quine对吧? 但是我知道的所有 quines 都将它们的源代码存储在一个字符串中,然后使用类似 chr 的内容替换其中的特殊字
This是一篇非常有趣的 wiki 文章,内容涉及无需访问物理源文件(在文件系统中)即可打印自己的源代码的程序。文章中的示例包括 C 和 Scheme quine 程序(是的,它们似乎是这样调用的)。
Quine-McCluskey 算法中的零最小项怎么办?例如西格玛 (0,1,3) 是输入那么我们是否必须在寻找主要蕴含项时忽略第一个零最小项,或者我们不关心零。?即它不包含在输出中? 最佳答案 最小
我正在查看 article on wikipdia对于这个算法,我看到了两个看似矛盾的说法: "it also gives a deterministic way to check that the
我想合并 Quine–McCluskey Algorithm与 Composite Specification Pattern . 首先,让我们考虑一下基础知识,即 C# 中的规范模式: public
今天,我在维基百科上浏览了一些随机的极客文章,以获取我每天的无用知识。我偶然发现了 quines,它们是打印自己的源代码的程序。我发现这是一种让我的大脑受伤的好方法,所以我开始在 VBA 中研究一个奎
好吧,对于那些从未遇到过这个词的人来说, quine 是一个“ self 复制”的计算机程序。更具体地说,它在执行时会生成自己的源代码副本作为其唯一输出。 当然,可以使用多种编程语言(但不是全部)开发
锁定。这个问题及其答案是locked因为这个问题是题外话,但具有历史意义。它目前不接受新的答案或互动。 编写一个程序,输出 反向 其源代码作为字符串。如果来源是 abcd efg (即 C 字符串 "
我经历了各种各样的 quine 问题,但我的任务是在没有 main() 的情况下得到一个 quine 问题,并且循环也是被禁止的。 没有循环,这很容易,但是我想不出没有 main() 怎么写。谁能帮助
我是一名优秀的程序员,十分优秀!