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

主范式的应用

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 去

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

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

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

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