東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年8月実施 専門科目II 問題1

标签：

• Tokyo-University
• Mathematical-Logic

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

题目描述

设 $A$ 为命题变量，$L_i$ 为文字（命题变量或其否定）。本题称

$$L_1\land\cdots\land L_n\supset A$$

为子句；$n=0$ 时即为 $A$。设 $\Pi$ 为子句集，$M$ 为命题变量集，将 $M$ 中的变量赋真，其余赋假。若所有子句均成立，则称 $M$ 为 $\Pi$ 的模型，模型之间使用通常的集合包含关系。

（1）令

$$\Pi_0=\{P,\ P\supset Q,\ Q\land\neg R\supset S,\ P\land\neg S\land\neg T\supset T\}.$$

枚举 $\{P,Q,R,S,T\}$ 的所有满足 $\Pi_0$ 的子集。

定义 $\Pi_M$：先删除 $\Pi$ 中前件含有 $\neg B$ 且 $B\in M$ 的全部子句，再从剩余子句中删去全部否定文字。

（2）对 $M_0=\{P,Q,S\}$，求 $(\Pi_0)_{M_0}$。

（3）证明：若 $M'$ 是 $\Pi_M$ 的模型且 $M\subseteq M'$，则 $M'$ 是 $\Pi$ 的模型。

（4）证明：若 $M'$ 是 $\Pi$ 的模型且 $M'\subseteq M$，则 $M'$ 是 $\Pi_M$ 的模型。

（5）求第（2）问所得子句集的最小模型。最小模型是包含于该子句集每个模型的模型。

（6）证明：若 $\Pi_M$ 的最小模型恰为 $M$，则 $M$ 是 $\Pi$ 的极小模型，即不存在 $\Pi$ 的模型 $M''\subsetneq M$。

（7）$\Pi$ 的极小模型 $M$ 是否必是 $\Pi_M$ 的最小模型？若是则证明，否则举反例。

Kai

(1)

$P,Q$ 必为真。若 $R$ 假，则 $S$ 必真；若 $S$ 假，则 $T$ 必真。因此所有模型为

$$\boxed{\{P,Q,S\},\ \{P,Q,S,T\},\ \{P,Q,R,T\},\ \{P,Q,R,S\},\ \{P,Q,R,S,T\}.}$$

(2)

最后一条子句含 $\neg S$，被删除；第三条中的 $\neg R$ 被去掉。因此

$$\boxed{(\Pi_0)_{M_0}=\{P,\ P\supset Q,\ Q\supset S\}.}$$

(3)

考察 $\Pi$ 的任一子句。若它被删除，则其前件含 $\neg B$，其中 $B\in M\subseteq M'$；故前件在 $M'$ 下为假，子句成立。

若它被保留，当原前件在 $M'$ 下为真时，其中全部正文字也为真。由于 $M'$ 满足删去否定文字后的子句，结论必真。因此原子句成立。

(4)

任取 $\Pi_M$ 中的子句。原子句中的每个否定文字 $\neg B$ 都有 $B\notin M$，故 $B\notin M'$。若保留下来的正前件在 $M'$ 中为真，则原前件也为真，由 $M'$ 满足 $\Pi$ 可得结论为真。故 $M'$ 满足 $\Pi_M$。

(5)

由事实 $P$ 依次推出 $Q,S$，且 $\{P,Q,S\}$ 满足全部子句，故最小模型为

$$\boxed{\{P,Q,S\}.}$$

(6)

由（3）取 $M'=M$ 可知 $M$ 是 $\Pi$ 的模型。若存在 $\Pi$ 的模型 $M''\subsetneq M$，则由（4），$M''$ 也是 $\Pi_M$ 的模型。但 $M$ 是后者的最小模型，应有 $M\subseteq M''$，矛盾。故 $M$ 极小。

(7)

不一定。取

$$\Pi=\{\neg P\supset P\},\qquad M=\{P\}.$$

$P$ 为假时子句不成立，所以 $M$ 是唯一的模型，当然极小。然而 $\Pi_M=\varnothing$，其最小模型为 $\varnothing\ne M$。