\[ \def\v{\overline{v}} \]
教材 1.7 紧致性和能行性
习题 1:设 \(\Sigma\) 的每个有限子集都是可满足的,证明 \(\Sigma ; \alpha\) 和 \(\Sigma ; \neg \alpha\) 中至少有一个也是如此。(这是紧致性定理证明的一部分)
提示:如果不是这样,那么对于有限子集 \(\Sigma_1 \subseteq \Sigma\) 和 \(\Sigma_2 \subseteq \Sigma\),\(\Sigma_1 ; \alpha\) 和 \(\Sigma_2 ; \neg \alpha\) 都是不可满足的。再考虑 \(\Sigma_1 \cup \Sigma_2\)。
不使用紧致性定理的证明:使用反证法。如果不是这样,则对于有限子集 \(\Sigma_1 \subseteq \Sigma\) 和 \(\Sigma_2 \subseteq \Sigma\),\(\Sigma_1 ; \alpha\) 和 \(\Sigma_2 ; \neg \alpha\) 都是不可满足的。因此 \(\Sigma_1 \cup \Sigma_2\) 也是不可满足的。这与“\(\Sigma\) 的每个有限子集都是可满足的”相矛盾。
\(Q.E.D.\)
习题 2:设 \(\Delta\) 是满足以下条件的合式公式集合:
- \(\Delta\) 的每个有限子集是可满足的,
- 对每个合式公式 \(\alpha\),要么 \(\alpha \in \Delta\) 要么 \((\neg \alpha) \in \Delta\)。
对每个命题符号 \(A\),定义真值指派 \(v\): \[ v(A) = \begin{cases} T & \text{iff } A \in \Delta, \\ F & \text{iff } A \notin \Delta \end{cases} \]
证明对每个合式公式 \(\varphi\),\(\v(\varphi) = T\) 当且仅当 \(\varphi \in \Delta\)。(这也是紧致性定理证明的一部分)
提示:对 \(\varphi\) 使用归纳法。
证明:对 \(\varphi\) 使用归纳法。
若 \(\varphi\) 为命题符号,则根据 \(v\) 的定义,\(\v(\varphi) = T\) 当且仅当 \(\varphi \in \Delta\),原命题对 \(\varphi\) 成立。
若对于构造序列长度小于 \(n\) 的所有合式公式,原命题都成立。
则对于构造序列长度为 \(n\) 的合式公式 \(\varphi\),设其构造序列为 \(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_n \rangle\)。
- 若 \(\varphi = (\lnot \alpha)\),\(\v(\lnot \alpha) = T \iff \v(\alpha) = F \iff \alpha \notin \Delta \iff (\lnot \alpha) \in \Delta\),原命题对 \(\varphi\) 显然成立;
- 若 \(\varphi = (\alpha \wedge \beta)\),\(\v(\alpha \wedge \beta) = T \iff \v(\alpha) = T \wedge \v(\beta) = T \iff \alpha \in \Delta \wedge \beta \in \Delta\)。由条件 2 可知,\(\Delta\) 对 \(\wedge\) 封闭。因此 \(\alpha \in \Delta \wedge \beta \in \Delta \iff \alpha \wedge \beta \in \Delta\)。原命题对 \(\varphi\) 成立。
- 若 \(\varphi = (\alpha \vee \beta)\),可转化为 \(\varphi = \lnot(\lnot \alpha \wedge \lnot \beta)\)。根据 1 和 2 归纳即可。
因此,原命题对所有合式公式 \(\varphi\) 成立。
\(Q.E.D.\)