作业 5 · 主范式与语义证明

第 1 题正确；第 2 题错误。重言式没有使公式为假的赋值，所以它的主合取范式不含极大项，通常直接记为 $1$。

以唯一命题变量 $p$ 为变元时，公式 $p$ 同时满足两种要求。

• 析取范式：$p$、$p\lor q$、$p\land\neg r$、$p\lor\neg p$；
• 合取范式：五个公式全部都是。

其中“一个简单合取式”也可视为只有一项的析取范式，“一个简单析取式”也可视为只有一项的合取范式。

1. 主合取范式为 $p\lor\neg q\lor r$，是可满足但非重言式；

2. 主合取范式为

   $$(p\lor q\lor r)\land(p\lor\neg q\lor r) \land(\neg p\lor\neg q\lor r),$$

   是可满足但非重言式；

3. 源答案化简为 $p\lor q$，是可满足但非重言式；

4. 化简为 $1$，是重言式；

5. 主析取范式为

   $$(\neg p\land\neg q\land\neg r)\lor(p\land q\land r),$$

   是可满足但非重言式；

6. 化简为 $0$，是矛盾式。其主合取范式包含 $p,q$ 的全部四个极大项。

源提交没有把每一题的另一种主范式完整誊清；我不补充冒充源答案。

$p\land\neg q\land r$ 是主析取范式中的一个极小项，$p\lor q\lor r$ 是主合取范式中的一个极大项。其余公式含重复项、混合层次或同一项中正负文字不合要求，不是规范的主范式。

若 $A\lor B\models C$，任何满足 $A$ 的赋值也满足 $A\lor B$，故满足 $C$；所以 $A\models C$。对 $B$ 同理。

反过来，若 $A\models C$ 且 $B\models C$，任何满足 $A\lor B$ 的赋值至少满足 $A,B$ 之一，因而都满足 $C$。

任取满足 $\Gamma$ 的赋值。至少一个 $p_i$ 为真，由 $p_i\to q_i$ 得对应 $q_i$ 为真；而两两互斥条件保证其他 $q_j$ 都为假。

于是对任意 $j$：若 $q_j$ 真，它就是被选中的那个指标，对应 $p_j$ 真；若 $q_j$ 假，$q_j\to p_j$ 自动为真。故所有 $q_j\to p_j$ 的合取为真。