\[ \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.\)
