数理逻辑-第 7 次作业

\[ \def\A{\mathfrak{A}} \def\B{\mathfrak{B}} \]

本节知识点

本节使用到教材当中的一些公理、定理和规则总结如下：

假言推理（Modus Ponen，又称 MP 规则或直言三段论）： \[ \frac{\alpha, \alpha \to \beta}{\beta} \] $\Lambda$ 是 6 组逻辑公理的集合：

重言式；
$\forall x \alpha \to \alpha^x_t$，其中 $t$ 是 $x$ 在 $\alpha$ 中的替换，即把 $\alpha$ 中出现的 $x$ 换成 $t$；
$\forall x (\alpha \to \beta) \to (\forall x \alpha \to \forall x \beta)$；
$\alpha \to \forall x \alpha$，其中 $x$ 在 $\alpha$ 中不是自由出现的（自由出现的意思是无量词限定，例如 $\forall y x + y = 2$ 中 $x$ 是自由出现的，$y$ 不是）；
$x=x$；
$x = y \to (\alpha \to \alpha')$，其中 $\alpha$ 是原子的，$\alpha'$ 是有限次的将 $\alpha$ 中的 $x$ 替换为 $y$ 得到的。

由 $\Gamma \cup \Lambda$ 和假言推理可以获得的公式集叫做 $\Gamma$ 的定理集合。

概化定理：如果 $\Gamma \vdash \varphi$ 且 $x$ 不在 $\Gamma$ 的任何公式中自由出现，则 $\Gamma \vdash \forall x \varphi$。

规则 T：如果 $\Gamma \vdash \alpha_1, \dots, \Gamma \vdash \alpha_n$，且 $\set{\alpha_1, \dots, \alpha_n}$ 重言蕴含 $\beta$ ，那么 $\Gamma \vdash \beta$。

演绎定理：如果 $\Gamma;\gamma \vdash \varphi$，那么 $\Gamma \vdash (\gamma \to \varphi)$。从右到左叫做演绎，从左到右叫演绎定理。

教材 2.4 演绎计算

习题 3：(a) 设 $\A$ 是结构，且令 $s:V \to |\A|$，在基本公式集上定义真值指派 $v$ 如下： \[ v(\alpha) = T \iff \models_\A \alpha[s] \] 证明：对于任意公式（基本与否均可），有： \[ \overline{v}(\alpha) = T \iff \models_\A \alpha[s] \]

证明：如果 $\Gamma$ 重言蕴含 $\varphi$，则 $\Gamma$ 逻辑蕴涵 $\varphi$。

证明：使用归纳法证明。对于基本公式 $\alpha$，$\overline{v}(\alpha) = v(\alpha) = T \iff \models_\A \alpha[s]$。

对于公式 $\lnot \alpha$，$\overline{v}(\alpha) = T \iff \overline{v}(\alpha) = F \iff \not \models_\A \alpha[s] \iff \models_\A \lnot \alpha[s]$。

对于公式 $\beta \to \alpha$，$\overline{v}(\beta \to \alpha) = T \iff \overline{v}(\beta) = F \lor \overline{v}(\alpha) = T \iff \models_\A \lnot \beta[s] \lor \models_\A \alpha[s] \iff \models \beta \to \alpha [s]$。

$Q.E.D.$

证明：$\Gamma$ 重言蕴含 $\varphi$，意味着对每个结构 $\A$，若对于每个 $\alpha \in \Gamma$，$\overline{v}(\alpha) = T$，有 $\overline{v}(\varphi) = T$。

因此，对每个结构 $\A$ 和 $s:V \to |\A|$，若对每个 $\alpha \in \Gamma$，都有 $\models_\A \alpha[s]$，则 $\models_\A \varphi[s]$。因此，$\Gamma \models \varphi$。

上述证明实际上展示了“重言蕴含为什么在逻辑上是对的”。

$Q.E.D.$

习题 8：设 $x$ 不在 $\alpha$ 中自由出现，证明 Q2b \[ \vdash (\alpha \to \exists x \beta) \leftrightarrow \exists x (\alpha \to \beta) \] 在同样的假设下，证明 Q3a： \[ \vdash (\forall x \beta \to \alpha) \leftrightarrow \exists x (\alpha \to \beta) \]

证明 Q2b：由规则 T，需要证明 $\vdash (\alpha \to \exists x \beta) \rightarrow \exists x (\alpha \to \beta)$ 和 $\vdash (\alpha \to \exists x \beta) \leftarrow \exists x (\alpha \to \beta)$。

通过推导、反证法和假言推理，我们可以得到第一个公式等价于 $ x () (x ) $。现在，根据第 2 组公理和假言推理，我们有 $ x () () $。此外，$ () $ 和 $ () $ 都是重言式。通过假言推理，我们得到 $ x () $ 和 $ x () $。根据推广定理，$ x () $ 重言蕴含 $ (x ) $，根据规则 T，我们得到了需要的结果。

通过推导、反证法和假言推理，我们可以得到第二个公式等价于 $ (x ) x () $。对于这个公式，基于推广定理并假设 $ x $ 没有自由出现在 $ $ 中，我们只需证明 $ (x ) () $，而通过反证法、推导和假言推理，它等价于 $ { , } x $。通过假言推理，我们只需证明 $ x $，或者通过推导 $ x $，或者通过反证法和假言推理，得到 $ x $，这是第 2 组公理的一项。

通过将 $ $ 替换为 $ $ ，将 $ $ 替换为 $ $，并使用反证法的重言式等价性，我们得到 $ (x ) x () $。

$Q.E.D.$

习题 9：（再替换引理）(a) 试证： $(\varphi_y^x)^y_x$ 一般不相等，而且以下两种情况均有可能发生：$x$ 在 $(\varphi_y^x)_x^y$ 中的某个位置上出现，而在 $\varphi$ 中同样的位置上不出现；或者反过来，$x$ 在 $\varphi$ 中的某个位置上出现，而在 $(\varphi_y^x)_x^y$ 中同样的位置上不出现。

证明：如果 $y$ 不在 $\varphi$ 中出现，那么在 $\varphi_y^x$ 和 $(\varphi_y^x)_x^y = \varphi$ 中 $x$ 可替换 $y$。提示：对 $y$ 使用归纳法。

证明：让我们暂时称变量 $ x $ （或 $ y $）的一个实例被 $ x $ 所限定当且仅当该实例位于公式 $ x $ 的某个子公式中。然后，公式 $ $ 中的每一个 $ x $ 或 $ y $ 的实例将会变成 $ x $ 或 $ y $，这取决于它是否被 $ x $ 和/或 $ y $ 限定（对于不同情况）。在其中的两种情况中，如果一个变量没有被 $ y $ 限定（无论是否被 $ x $ 限定），它最终会在 $ (^y_x)y_x $ 中变成 $ x $。如果变量被 $ y $ 限定，那么根据它是否被 $ x $ 限定，它会分别保持与 $ $ 中相同或变成 $ y $ 在 $ (^y_x)y_x $ 中。因此，当 $ y $ 可能变成 $ x $ 且 $ x $ 可能变成 $ y $ 时，我们会有若干潜在情况。基于此，设 $ = Py y Px $。那么 $ (^y_x)y_x = Px y Py $，其中一个自由 $ x $ 最终变成 $ y $，一个自由 $ y $ 最终变成 $ x $。

基于此观察，显然如果 $ $ 中没有 $ y $，那么 a) 没有 $ y $ 可以变成 $ x $（没有额外的 $ x' $），并且 b) 没有 $ x $ 被 $ y $ 所限定，因此没有 $ x $ 可以变成 $ y $（没有缺失的 $ x' $）。(b) 部分给出了一个更正式的证明。

$Q.E.D.$

证明：如建议的那样，我们通过归纳法证明该陈述。对于变量或常量符号 $ z y $，如果 $ z x $，则 $ ^z_y = (^y_x)y_x = z $，否则 $ ^z_y = y $ 且 $ (^y_x)y_x = x = z $。对于不包含 $ y $ 的项 $ t = f_i t_1 t_n $，通过归纳，$(t^y_x)y_x = f_i ((t_1)^y_x)y_x ((t_n)^y_x)y_x = f_i t_1 t_n = t$。同样，对于不包含 $ y $ 的原子公式 $\varphi = Pt_1 \ldots t_n$，通过归纳，$(\varphi^y_x)^y_x = P((t_1)^y_x)^y_x \ldots ((t_n)^y_x)^y_x = \varphi$（并且 $ x $ 可以替代 $ y $ 因为后者也是一个原子公式）。

此外，根据定义和归纳，如果不包含 $ y $ 的 $\alpha$ 和 $\beta$ 使得 $ x $ 可替代 $ y $ 在 $ ^y_x $ 和 $ ^y_x $ 中，那么 a) $ ()^y_x = ^y_x $，$ x $ 可替代 $ y $ 在其中，且 b) $ (()^y_x = ^y_x ^y_x $。此外，$ (x )^y_x = x $ 不包含任何 $ y $，因此 $ x $ 不在 $\{x, y\}$ 中，$ x $ 不自由出现在其中，$ x $ 可替代 $ y $ 在其中，且 $ ((x )^y_x)y_x = x(^y_x)y_x = x $。

$Q.E.D.$

习题 11：证明 Eq3： \[ \vdash \forall x \forall y \forall z (x = y \to y = z \to x = z) \]

证明：在数理逻辑中，$\to$ 运算符具有右结合性，即 $\alpha \to \beta \to \gamma$ 的含义是 $\alpha \to (\beta \to \gamma)$。本题的表达中不适用括号。

根据泛化定理，我们只需证明 $ x = y y = z x = z $。根据公理组 5，我们有 $ x = x $。根据公理组 6，我们有 $ x = y x = x y = x $ 和 $ y = x y = z x = z $。前两个式子根据规则 T 可以推出 $ x = y y = x $，再结合第三个式子并再次应用规则 T，可以推出 $ x = y y = z x = z $。

$Q.E.D.$