元理论：导言

开始本单元之前，先测一测你的起点。这是一次简短的自我测评：不计分，结果只保存在你的浏览器中。

1. 第 1 题来自前面的单元$\Gamma \models \varphi$ 是什么意思？

   满足 $\Gamma$ 中所有公式的每个赋值都满足 $\varphi$。

   $\varphi$ 有一个从 $\Gamma$ 出发的推演。

   某个赋值同时满足 $\Gamma$ 和 $\varphi$。

   $\varphi$ 是 $\Gamma$ 中某一个公式单独的后承。

2. 第 2 题来自前面的单元下列哪一个断言与 $\Gamma \models \varphi$ 等价？

   $\Gamma \cup \{\neg\varphi\}$ 不可满足。

   $\Gamma \cup \{\varphi\}$ 可满足。

   $\Gamma \cup \{\neg\varphi\}$ 可满足。

   $\neg\varphi$ 不可满足。

3. 第 3 题来自前面的单元如果赋值 $v$ 给 $\alpha$ 赋值 $1$，那么它给 $(\alpha \downarrow \beta)$ 什么值？

   $0$，无论 $\beta$ 的值是什么。

   取决于 $\beta$：其值为 $1$，如果 $\beta$ 的值为 $0$。

   $1 - v(\beta)$。

   $1$，因为其中一个成分为真。

4. 第 4 题来自前面的单元$\varphi$ 的变元是 $v_{2}$ 和 $v_{7}$。两个赋值 $v$ 和 $w$ 在 $v_{2}$ 和 $v_{7}$ 上一致，而在其余所有变元上取相反的值。若 $v(\varphi) = 1$，关于 $w(\varphi)$ 能断言什么？

   $w(\varphi) = 1$。

   什么也不能断言，因为 $v$ 和 $w$ 在无穷多个变元上不同。

   $w(\varphi) = 0$，因为 $w$ 把 $v$ 的几乎所有值都颠倒了。

   $w(\varphi) = 1$，仅当 $v$ 和 $w$ 在 $v_{1}, \ldots, v_{6}$ 上也一致时。

5. 第 5 题来自前面的单元设 $\Gamma$ 是一个无穷公式集，使得 $\Gamma \vdash \varphi$。能断言什么？

   $\Gamma$ 的某个有穷子集推演出 $\varphi$。

   $\varphi$ 是定理。

   这个推演用到了 $\Gamma$ 中的所有公式。

   没有紧致性定理就什么也不能断言，因为 $\Gamma$ 是无穷的。

6. 第 6 题来自前面的单元已知 $\Gamma \cup \{p\} \vdash \chi$ 且 $\Gamma \cup \{\neg p\} \vdash \chi$。分情况证明允许得出什么结论？

   $\Gamma \vdash \chi$。

   什么也得不出，只要还不知道 $\Gamma$ 推演出 $p$ 还是推演出 $\neg p$。

   $\Gamma \vdash (p \leftrightarrow \chi)$。

   只有 $\Gamma \cup \{p, \neg p\} \vdash \chi$。

7. 第 7 题课程的系统是可靠的。这一性质断言什么？

   对每个集合 $\Gamma$，若 $\Gamma \vdash \varphi$，则 $\Gamma \models \varphi$。

   若 $\Gamma \models \varphi$，则 $\Gamma \vdash \varphi$。

   不存在任何公式 $\varphi$ 使得 $\vdash \varphi$ 且 $\vdash \neg\varphi$。

   每个真的公式都是定理。

8. 第 8 题设 $v$ 是把 $1$ 赋给 $p$、把 $0$ 赋给 $q$ 的赋值。卡尔马引理借助变元 $p$ 和 $q$，关于公式 $(p \leftrightarrow q)$ 断言什么？

   $\{p, \neg q\} \vdash \neg(p \leftrightarrow q)$。

   $\{p, \neg q\} \vdash (p \leftrightarrow q)$。

   $\{p, q\} \vdash \neg(p \leftrightarrow q)$。

   $\vdash \neg(p \leftrightarrow q)$。

9. 第 9 题一个演绎系统能否可靠而不完备？

   能：卢卡西维茨系统在没有双否替换规则时是可靠的，却推演不出重言式 $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$。

   不能：可靠性和完备性可以互相推出。

   不能：公理都是重言式的系统推演出所有重言式。

   能，但只有当系统不一致时才行。

10. 第 10 题紧致性定理断言什么？

    一个公式集是可满足的，当且仅当它的每个有穷子集都是可满足的。

    一个公式集是可满足的，当且仅当它的每个公式都是可满足的。

    每个无穷公式集都是可满足的。

    一个集合是可满足的，只要它的某个有穷子集是可满足的。

11. 第 11 题设 $\Gamma$ 是一个无穷公式集，使得 $\Gamma \models \varphi$。紧致性保证什么？

    $\Gamma_{0} \models \varphi$，这里 $\Gamma_{0}$ 是 $\Gamma$ 的某个有穷子集。

    $\varphi$ 是 $\Gamma$ 中某一个公式单独的后承。

    $\varphi$ 是 $\Gamma$ 的每个有穷子集的后承。

    $\varphi$ 有效。

12. 第 12 题第一课对有穷前提集证明了完备性。为什么推演的有穷性不足以把它推广到一个无穷集 $\Gamma$？

    因为有穷性谈的是 $\Gamma \vdash \varphi$，而我们手中有的是 $\Gamma \models \varphi$：需要归约到有穷部分的是后承，而不是推演，而这就是紧致性。

    足够：若 $\Gamma \models \varphi$，有穷性就给出一个有穷的 $\Gamma_{0}$，使得 $\Gamma_{0} \models \varphi$。

    因为卡尔马引理对有无穷多个变元的公式不成立。

    因为完备性对无穷前提集不成立。

13. 第 13 题子句 $\{p, \neg q, r\}$ 与 $\{q, s\}$ 的归结式是什么？

    $\{p, r, s\}$。

    $\{p, \neg q, r, q, s\}$。

    $\{p, r\}$。

    它们没有归结式，因为没有共同的文字。

14. 第 14 题为了用归结判定是否 $\{(p \vee q), \neg p\} \models q$，我们试图反驳哪个子句集？

    $\{\{p, q\}, \{\neg p\}, \{\neg q\}\}$。

    $\{\{p, q\}, \{\neg p\}, \{q\}\}$。

    $\{\{p, q\}, \{\neg p\}\}$。

    $\{\{\neg p, \neg q\}, \{p\}, \{\neg q\}\}$。

15. 第 15 题空子句 $\Box$ 能否用归结从集合 $\{\{p, q\}, \{\neg p, \neg q\}\}$ 推导出来？

    不能：这个集合是可满足的，而归结是可靠的。

    能，一步即可，同时消去两个互补对。

    能，两步：先关于 $p$，再关于 $q$。

    不能，因为两个子句都不是单元子句。