最后更新: 2025-01-21 20:54 ● 参与者查看: 12 次纠错分享参与项目词条搜索

消解算法

消解算法
输入：合式公式 $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}
$$

上一篇：消解规则

下一篇：没有了

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