\[ \def\len{\mathsf{len}} \]
讲义 0.2.29 基数
习题 1：设 \(\alpha\) 为基数，\(\kappa\) 为集合 \(\set{\beta | \beta 是序数且与 \alpha 等势}\) 的最小元。证明：\(\kappa\) 是基数。
证明：对每个序数 \(\gamma < \kappa\)，即 \(\gamma \in \kappa\)，有 \(\gamma \subseteq \kappa\)，即 \(\gamma \prec \kappa\) 或 \(\gamma \sim \kappa\)。
又因为 \(\kappa\) 为集合中最小元，因此 \(\gamma \prec \kappa\)。
\(Q.E.D.\)
教材 1.1 命题逻辑的语言
习题 2：证明不存在长度为 2、3、6 的合式公式，但其他任意正整数长度的合式公式都可能存在。
证明：用 \(\len(\alpha)\) 表示公式 \(\alpha\) 的长度。定义谓词 \(P\)，命题 \(P(\alpha): \len(\alpha) \notin \set{2, 3, 6}\)。
对所有命题符号 \(A_n\)，\(\len(A_n) = 1\)，命题 \(P(A_n)\) 成立。
对所有非命题符号的合式公式 \(\alpha\) 归纳：
下面证明：若组成合式公式 \(\alpha\) 的合式公式 \(\beta, \gamma\) 均有 \(P(\beta), P(\gamma)\) 成立，则 \(P(\alpha)\) 成立。
- 若 \(\alpha = (\lnot \beta)\)，则 \(\len(\alpha) \ge 4\)，\(\len(\alpha) \notin \set{2, 3}\)。若 \(\len(\alpha) = 6\)，则 \(\len(\beta) = 3\)，与 \(P(\beta)\) 矛盾；
- 若 \(\alpha = (\beta \square \gamma)\)（其中 \(\square \in \set{\vee, \wedge, \to, \leftrightarrow}\)），显然 \(\len(\alpha) = \len(\beta) + \len(\gamma) + 3> 5\)。若 \(\len(\alpha) = 6\) 则 \(\len(\beta) + \len(\gamma) = 3\)，与 \(P(\beta)\) 或 \(P(\gamma)\) 矛盾。
因此，\(\len(\alpha) \notin \set{2, 3, 6}\)。
下面证明 \(\len(\alpha)\) 可以为其他任何长度。
\(\len\) 函数存在如下递归关系：
\[ \len(A_n) = 1 \\ \len((\lnot \alpha)) = \len(\alpha) + 3 \\ \len((\alpha \square A_n)) = \len(\alpha) + 4 \]
显然，\(\len(\alpha)\) 可以为 \(\set{1, 4, 5, 7, 8, 9}\) 中的任何值。根据长度为 7、8、9 的公式，可以根据 \(\len((\lnot \alpha)) = \len(\alpha) + 3\) 构造长度为大于 9 的任意整数的公式。
\(Q.E.D.\)
习题 3：设 \(\alpha\) 是一个合式公式，\(c\) 是二元连接符（\(\wedge, \vee, \to, \leftrightarrow\)）出现的次数，\(s\) 是命题符合出现的次数（例如，若 \(\alpha = (A \to (\lnot A))\)，则 \(c = 1, s = 2\)）。使用归纳法证明：\(s = c + 1\)。
证明：命题 \(P(n): 当 c = n 时，s = c + 1\)。
当 \(c = 0\) 时，\(\alpha = A\) 或 \(\alpha = (\lnot A)\)，其中 \(A\) 是命题符号。\(P(0)\) 成立。
若当 \(c \le n (n \ge 1)\) 时都有 \(P(c)\) 成立。则当 \(c = n + 1\) 时，\(\alpha = (\beta \square \gamma)\)，其中 \(c_\alpha = c_\beta + c_\gamma + 1, s_\alpha = s_\beta + s_\gamma = c_\beta + c_\gamma + 2 = c_\alpha + 1\)。此时 \(P(n+1)\) 成立。
因此，对任意 \(c \ge 0\)，都有 \(P(c)\) 成立。
\(Q.E.D.\)
教材 1.2 真值指派
习题 6：(a) 证明：如果两个真值指派 \(v_1, v_2\) 与在合式公式 \(\alpha\) 中出现的命题符号的指派是一致的，那么 \(\overline{v_1}(\alpha) = \overline{v_2}(\alpha)\)。（使用归纳法则）。
证明：设 \(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_n \rangle\) 是 \(\alpha\) 的构造序列。
\[ \forall A \in \alpha. v_1(A) = v_2(A) \\ \Rightarrow v_1(\varepsilon_1) = v_2(\varepsilon_1) \\ \Rightarrow \forall k \le n. \overline{v_1}(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_k \rangle) = \overline{v_2}(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_k \rangle) \\ \Rightarrow \overline{v_1}(\alpha) = \overline{v_2}(\alpha) \]
\(Q.E.D.\)
习题 8：（置换）\(\alpha_1, \alpha_2, \dots\) 一个合式公式的序列，对每个合式公式 \(\varphi\)，令 \(\varphi^*\) 是用 \(\alpha_n\) 置换 \(A_n\)（对所有 \(n\)）后得到的结果。
设 \(v\) 是所有命题符号的真值指派，定义 \(u\) 为满足 \(u(A_n) = \overline{v}(\alpha_n)\) 的真值指派，证明 \(\overline{u}(\varphi) = v(\varphi^*)\) 使用归纳法。
证明如果 \(\varphi\) 是重言式，那么 \(\varphi^*\) 也是。（例如，\(((A \land B) \leftrightarrow (B \land A))\) 是一个重言式，因此对任意的合式公式 \(\alpha, \beta\)，通过置换可得 \(((\alpha \land \beta) \leftrightarrow (\beta \land \alpha))\) 是重言式。）
- 证明：命题 \(P(k): \varphi 构造序列长度为 k 时，\overline{u}(\varphi) = v(\varphi^*)\)。设 \(\varphi\) 的构造序列为 \(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_k \rangle\)。对 \(k\) 进行归纳：
当 \(k = 1\) 时，\(\varepsilon_1\) 为命题符号，命题 \(P(1)\) 成立。
若当 \(k < n(n > 1)\) 时，命题 \(P(k)\) 都成立。
则当 \(k = n\) 时，\(u(\varepsilon_{n}) = v(\varepsilon_{n})\)，因此 \(\overline{u}(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_n \rangle) = \overline{v}(\langle \varepsilon_1 , \varepsilon_2 , \dots , \varepsilon_n \rangle)\)。
因此，对所有 \(k \ge 1\)，命题 \(P(k)\) 都成立。
\(Q.E.D.\)
- 证明：若 \(\varphi\) 是重言式。对任意真值指派 \(v\)，\(\overline{v}(\varphi^*) = \overline{u}(\varphi) = T\)。因此 \(\varphi^*\) 为重言式。
\(Q.E.D.\)
