最后更新: 2025-01-21 20:54 查看: 81 次纠错评论(0) 课件开VIP

消解算法

消解算法
输入：合式公式 $A$
输出：当 $A$ 是可满足时，回答＂Yes＂；否则回答＂No＂。
1．求 $A$ 的合取范式 $S$
2．令 $S_0 \leftarrow \varnothing, S_2 \leftarrow \varnothing, S_1 \leftarrow S$ 的所有简单析取式
3．For $C_1 \in S_0$ 和 $C_2 \in S_1$
4．If $C_1, C_2$ 可以消解 then
5．计算 $C \leftarrow \operatorname{Res}\left(C_1, C_2\right)$
6．If $C=\lambda$ then
7．输出＂No＂，计算结束
8．If $C \notin S_0$ 且 $C \notin S_1$ then
9．$\quad S_2 \leftarrow S_2 \cup\{C\}$
10．For $C_1 \in S_1, C_2 \in S_1$ 且 $C_1 \neq C_2$
11．If $C_1, C_2$ 可以消解 then
12．计算 $C \leftarrow \operatorname{Res}\left(C_1, C_2\right)$
13．If $C=\lambda$ then
14．输出＂No＂，计算结束
15．If $C \notin S_0$ 且 $C \notin S_1$ then
16．$\quad S_2 \leftarrow S_2 \cup\{C\}$
17．If $S_2=\varnothing$ then
18．输出＂Yes＂，计算结束
19．Else $S_0 \leftarrow S_0 \cup S_1, S_1 \leftarrow S_2, S_2 \leftarrow \varnothing$ ，goto 3

例12 用消解算法判断下述公式是否是可满足的：

$$
\begin{aligned}
& \quad p \wedge(p \vee q) \wedge(p \vee \neg q) \wedge(q \vee \neg r) \wedge(q \vee r) \\
& \text { 解 } S=p \wedge(p \vee q) \wedge(p \vee \neg q) \wedge(q \vee \neg r) \wedge(q \vee r) \\
& \text { 循环 } 1 \quad S_0=\varnothing, S_1=\{p, p \vee q, p \vee \neg q, q \vee \neg r, q \vee r\}, S_2=\varnothing \\
& \operatorname{Res}(p \vee q, p \vee \neg q)=p \\
& \operatorname{Res}(p \vee \neg q, q \vee \neg r)=p \vee \neg r \\
& \operatorname{Res}(p \vee \neg q, q \vee r)=p \vee r \\
& \operatorname{Res}(q \vee \neg r, q \vee r)=q \\
& S_2=\{p \vee r, p \vee r, q\}
\end{aligned}
$$

循环2 $S_0=\{p, p \vee q, p \vee \neg q, q \vee \neg r, q \vee r\}, S_1=\{p \vee r, p \vee r, q\}, S_2=\varnothing$

$$
\operatorname{Res}(p \vee \neg q, q)=p
$$
$$
\begin{aligned}
&\begin{aligned}
& \operatorname{Res}(q \vee \neg r, p \vee r)=p \vee q \\
& \operatorname{Res}(q \vee r, p \vee \neg r)=p \vee q \\
& \operatorname{Res}(p \vee r, p \vee \neg r)=p \\
& S_2=\varnothing
\end{aligned}\\
&\text { 输出 "Yes" }
\end{aligned}
$$

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：消解规则

下一篇：没有了

本文对您是否有用？有用 (0) 无用 (0)