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

主范式的应用

1．求公式的成真成假赋值
设公式 $A$ 含 $n$ 个命题变项， $A$ 的主析取范式有 $s$ 个极小项，则 $A$有 $s$ 个成真赋值，它们是极小项下标的二进制表示，其余 $2 ^n{ }^{-} s$个赋值都是成假赋值

例如 $\quad(p \rightarrow \neg q) \rightarrow r \Leftrightarrow m_1 \vee m_3 \vee m_5 \vee m_6 \vee m_7$
成真赋值为 $001,011,101,110,111$ ，
成假赋值为 $0 0 0 , 010,100$ ．

类似地，由主合取范式也立即求出成假赋值和成真赋值．

2．判断公式的类型
设 $A$ 含 $n$ 个命题变项。
$A$ 为重言式 $\Leftrightarrow A$ 的主析取范式含全部 $2^{ n }$ 个极小项
$\Leftrightarrow A$ 的主合取范式不含任何极大项，记为1。
$A$ 为矛盾式 $\Leftrightarrow A$ 的主合析取范式含全部 $2^n$ 个极大项
$\Leftrightarrow A$ 的主析取范式不含任何极小项，记为 0 。
$A$ 为非重言式的可满足式
$\Leftrightarrow A$ 的主析取范式中至少含一个，但不是全部极小项
$\Leftrightarrow A$ 的主合取范式中至少含一个，但不是全部极大项。

例7 用主析取范式判断公式的类型：
（1）$A \Leftrightarrow \neg(p \rightarrow q) \wedge q$
（2）$B \Leftrightarrow p \rightarrow(p \vee q)$
（3）$C \Leftrightarrow(p \vee q) \rightarrow r$解
（1）$A \Leftrightarrow \neg(\neg p \vee q) \wedge q \Leftrightarrow(p \wedge \neg q) \wedge q \Leftrightarrow 0$
矛盾式
（2）$B \Leftrightarrow \neg p \vee(p \vee q) \Leftrightarrow 1 \Leftrightarrow m_0 \vee m_1 \vee m_2 \vee m_3$
重言式
（3）

$$
\begin{aligned}
C \Leftrightarrow & \neg(p \vee q) \vee r \Leftrightarrow(\neg p \wedge \neg q) \vee r \\
\Leftrightarrow & (\neg p \wedge \neg q \wedge r) \vee(\neg p \wedge \neg q \wedge \neg r) \vee(\neg p \wedge \neg q \wedge r) \\
& \vee(\neg p \wedge q \wedge r) \vee(p \wedge \neg q \wedge r) \vee(p \wedge q \wedge r)
\end{aligned}
$$

$\Leftrightarrow m _0 \vee m _1 \vee m _3 \vee m _5 \vee m _7 \quad$ 非重言式的可满足式

3．判断两个公式是否等值
例8 用主析取范式判以下每一组公式是否等值
（1）$p \rightarrow(q \rightarrow r)$ 与 $(p \wedge q) \rightarrow r$
（2）$p \rightarrow(q \rightarrow r)$ 与 $(p \rightarrow q) \rightarrow r$
解 $p \rightarrow(q \rightarrow r)=m_0 \vee m_1 \vee m_2 \vee m_3 \vee m_4 \vee m_5 \vee m_7$
$(p \wedge q) \rightarrow r=m_0 \vee m_1 \vee m_2 \vee m_3 \vee m_4 \vee m_5 \vee m_7$
$(p \rightarrow q) \rightarrow r=m_1 \vee m_3 \vee m_4 \vee m_5 \vee m_7$
显见，（1）中的两公式等值，而（2）的不等值．

4．解实际问题
例 9 某单位要从 $A , B , C$ 三人中选派若干人出国考察，需满足下述条件：
（1）若 A 去，则 C 必须去；
（2）若 $B$ 去，则 $C$ 不能去；
（3）A和B必须去一人且只能去一人。
问有几种可能的选派方案？
解 记 $p$ ：派 $A$ 去， $q$ ：派 $B$ 去，$r$ ：派 $C$ 去
（1）$p \rightarrow r$ ，
（2）$q \rightarrow \neg r$ ，
（3）$(p \wedge \neg q) \vee(\neg p \wedge q)$
求下式的成真赋值

$$
A=(p \rightarrow r) \wedge(q \rightarrow \neg r) \wedge((p \wedge \neg q) \vee(\neg p \wedge q))
$$

求 $A$ 的主析取范式

$$
\begin{aligned}
A= & (p \rightarrow r) \wedge(q \rightarrow \neg r) \wedge((p \wedge \neg q) \vee(\neg p \wedge q)) \\
\Leftrightarrow & (\neg p \vee r) \wedge(\neg q \vee \neg r) \wedge((p \wedge \neg q) \vee(\neg p \wedge q)) \\
\Leftrightarrow & ((\neg p \wedge \neg q) \vee(\neg p \wedge \neg r) \vee(r \wedge \neg q) \vee(r \wedge \neg r)) \\
& \wedge((p \wedge \neg q) \vee(\neg p \wedge q)) \\
\Leftrightarrow & ((\neg p \wedge \neg q) \wedge(p \wedge \neg q)) \vee((\neg p \wedge \neg r) \wedge(p \wedge \neg q)) \\
& \vee((r \wedge \neg q) \wedge(p \wedge \neg q)) \vee((\neg p \wedge \neg q) \wedge(\neg p \wedge q)) \\
& \vee((\neg p \wedge \neg r) \wedge(\neg p \wedge q)) \vee((r \wedge \neg q) \wedge(\neg p \wedge q)) \\
\Leftrightarrow & (p \wedge \neg q \wedge r) \vee(\neg p \wedge q \wedge \neg r)
\end{aligned}
$$

成真赋值：101，010
结论：方案1派 $A$ 与 C 去，方案 2 派 B 去

上一篇：主析取范式与主合取范式

下一篇：用成真赋值和成假赋值确定主范式

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