\[ \def\size{\mathsf{size}} \def\F{\mathcal{F}} \]
教材 1.3 解析算法
习题 3：证明引理 13B 中关于运算 \(\varepsilon_\lnot\) 的情形。
证明：对具有该性质的合适公式的集合 \(S\)，使用归纳法。
只包括一个命题的合适公式，没有符合条件的真初始段，原命题显然成立。
下面验证 \(S\) 在 \(\varepsilon_\lnot\) 下是封闭的。考虑 \(S\) 中的 \(\alpha\)，\((\lnot \alpha)\) 的真初始段如下：
- \((\)
- \((\lnot\)
- \((\lnot \alpha_0\)，其中 \(\alpha_0\) 是 \(\alpha\) 的真初始段
- \((\lnot \alpha\)
显然，\(\alpha_0 \in S\)。原命题显然正确。
\(Q.E.D.\)
习题 4：假定将合式公式的定义修改为去掉其中所有的右括号。对于
\[ ((A \wedge (\lnot B)) \to (C \vee D)) \]
我们写成：
\[ ((A \wedge (\lnot B \to (C \vee D \]
证明这种记法具有唯一可读性（即每个合式公式只有一个可能的分解方法）。提示：这种表达式具有的括号数和联结符号数相同。
证明：只需给出算法，可以根据每个该记法下的公式 \(e\) 和合式公式一一对应。
一种“自底向上”的构造算法：令 \(S\) 表示所有合式公式（包括命题符号）的集合。
对 \(e\) 中出现的每个串 \(\alpha， \beta\)，若 \(\alpha, \beta \in S\)，执行替换：
\[ ( \lnot \alpha \to (\lnot \alpha) \\ ( \alpha \wedge \beta \to ( \alpha \wedge \beta ) \\ ( \alpha \vee \beta \to ( \alpha \vee \beta ) \\ \]
重复步骤 1，直到无法执行替换。
在上述算法中，每次执行替换时在 \(e\) 中增加了一个右括号 \()\)，上述算法会在有限步骤内结束。替换后的子串都是合式公式，因此每个算法结束后 \(e\) 成为合式公式。又因为该记法下每个公式都是由某个合式公式转化而来，因此该记法下每个公式和合式公式一一对应。
\(Q.E.D.\)
教材 1.4 归纳与递归
习题 1：设 \(C\) 是由集合 \(B=\set{a, b}\) 在二元运算 \(f\) 和一元运算 \(g\) 的作用下生成的。试列出 \(C_2\) 中的所有元素。\(C_3\) 和 \(C_4\) 中各有多少元素？
\(C_1 = \set{a, b}, C_2 = \set{a, b, g(a), g(b), f(a, a), f(a, b), f(b, a), f(b, b)}\)
若不考虑元素相等的情况，\(\size(C_{n+1}) = \size(C_n)(\size(C_n) + 2)\)。
\(\size(C_1) = 2, \size(C_2) = 8, \size(C_3) = 80, \size(C_4) = 6560\)。
习题 3：本节中关于要求 \(\F\) 仅是 \(U\) 上的关系类的讨论可以进行推广。\(C_*\) 如前定义，但是如果对于每个 \(í \le n\)，我们有 \(x_i \in B\) 或者对某个 \(R \in \F\) 以及某些小于 \(i\) 的数 \(j_1, \dots, j_k\) 有 \(\langle x_{j_1}, \dots , x_{j_k}, x_i \rangle \in R\)，那么我们说 \(\langle x_0, , x_1 \dots , x_n \rangle\) 是一个构造序列。请给出 \(C^*\) 的正确定义，并证明 \(C^* = C_*\)。
TODO：如何定义集合对多元关系（而非多元函数）封闭？
“自顶向下”的 \(C^*\) 的扩展定义：
我们称 \(U\) 的子集 \(S\) 在 \(R \in \F\) 的作用下是封闭的，当且仅当只要 \(x_0 , x_1 \dots , x_n \in S\)，那么 \(\forall x_m. \langle x_0, , x_1 \dots , x_n , x_m \rangle \in R \Rightarrow x_m \in S\)。称 \(S\) 是归纳的，当且仅当 \(B \subseteq S\) 并且 \(S\) 在 \(R\) 的作用下是封闭的。令 \(C^*\) 是 \(U\) 的所有归纳子集的交集，则 \(x \in C^*\) 当且仅当 \(x\) 属于 \(U\) 的每个归纳子集。
证明 \(C^* = C_*\)：
首先验证 \(C^* \subseteq C_*\)。我们只需要证明 \(C_*\) 是归纳的，即 \(B \subseteq C_*\) 并且 \(C_*\) 在 \(R \in \F\) 的作用下是封闭的。显然 \(B = C_1 \subseteq C_*\)。如果 \(x_0 , x_1 \dots , x_n \in C_*\)，则将其构造序列进行连接，并添加每个新的元素 \(x_m\)，其中 \(\langle x_0, , x_1 \dots , x_n , x_m \rangle \in R, R \in \F\)，我们就得到了一个新的构造序列，并将 \(x_m\) 加入了 \(C_*\) 中。因此，\(C_*\) 在 \(R \in \F\) 的作用下是封闭的。
其次证明 \(C_* \subseteq C^*\)。考察构造序列 \(\langle x_0, , x_1 \dots , x_n, x_m \rangle\)，对 \(i \le n\) 进行归纳，可得到 \(x_i \in C^*\)。首先 \(x_0 \in B \subseteq C^*\)。在归纳步骤使用 \(C_*\) 的封闭特性即可。因此得到：
\[ \bigcup_n C_n = C_* = C^* = \bigcap\set{S | S 是归纳的} \]
\(Q.E.D.\)
教材 1.5 命题连接词
习题 1：设 \(G\) 是三元布尔函数，定义如下：
\[ G(F, F,F)= F, G(T, F, F) =T, \\ G(F, F,T) = T, G(T, F,T) = F, \\ G(F,T, F) =T, G(T,T, F) = F, \\ G(F,T,T)=F, G(T,T,T) = F. \]
（a）给出一个仅使用 \(\wedge, \vee, \lnot\) 的能够实现的合式公式；
（b）给出一个合式公式，其联结词最多出现 5 个。
（a）观察可知，当且仅当三个参数中只有一个 \(T\) 时，函数值为 \(T\)。
构造析取范式：
\[ G(A, B, C) = (A \wedge \lnot B \wedge \lnot C) \vee (\lnot A \wedge B \wedge \lnot C) \vee (\lnot A \wedge \lnot B \wedge C) \]
（b）将上述函数简化：
\[ G(A, B, C) = (A \wedge (B \downarrow C)) \vee (\lnot A \wedge (B + C)) \\ = (A \wedge (B \downarrow C)) \vee (A < (B + C)) \]
习题 5：证明 \(\set{\top, \bot, \lnot, \leftrightarrow , +}\) 是不完备的。提示：证明任意使用这些联结词和命题符号 \(A, B\) 的合式公式在 \(\bar{v}(\alpha)\) 的 4 种可能的取值下有偶数个取值为 \(T\)。说明：另一种方法是使用域 \(\set{0，1}\) 上的代数，任意使用这些联结词的可实现的布尔函数具有线性的特性。
证明：由于 \(\top \equiv A \vee \lnot A, \bot \equiv A \wedge \lnot A\)，其中 \(\equiv\) 表示重言等价（LaTeX 中没有重言等价符号）。即 \(\set{\top, \bot}\) 可以用其他连结词表示，因此只需要证明 \(\set{\lnot, \leftrightarrow, +}\) 是不完备的。
令 \(\alpha\) 是任意只包含 \(A, B\) 的公式，只要证明在 \(\bar v(\alpha)\) 下的四种可能取值中有偶数个为 \(T\)。显然，\(\leftrightarrow\) 和 \(+\) 都会在 \(A, B\) 的四种真值组合中产生偶数个 \(T\)。现在考虑使用 \(\lnot, \leftrightarrow, +\) 构造的任意合式公式 \(\alpha\)，我们可以对其进行递归分析：
- 如果公式是一个单一的命题符号或由 \(\leftrightarrow\) 和 \(+\) 构造，则它的真值表中 \(T\) 的个数一定是偶数。
- 如果公式是 \(\lnot \alpha\)，则 \(\lnot\) 仅会翻转公式 \(\alpha\) 的真值。因此，如果 \(\alpha\) 的真值表中 \(T\) 的个数是偶数，\(\lnot \alpha\) 的真值表中 \(T\) 的个数仍然是偶数。
因此，该联结词集合和命题符号无法构造与 \(A \vee B\) 等价的公式，该连结词集合不完备。
\(Q.E.D.\)
