演绎：导言

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

1. 第 1 题来自前面的单元符号串 $\sigI\sigI\sigO\sigI\sigO\sigO\sigI\sigO\sigI$ 是一个复合公式，形如 $\sigI\varphi\psi$。它的成分 $\varphi$ 和 $\psi$ 分别是什么？

   $\varphi = \sigI\sigO\sigI\sigO\sigO\sigI$，且 $\psi = \sigO\sigI$。

   $\varphi = \sigI\sigO\sigI$，且 $\psi = \sigO\sigO\sigI\sigO\sigI$。

   它可以有两种分解，取决于在首个圆盘之后从何处切开符号串。

   $\varphi$ 是首个圆盘之后的整个符号串，而 $\psi$ 是空串。

2. 第 2 题来自前面的单元在用强归纳法证明每个自然数 $n$ 都具有性质 $P(n)$ 时，证明 $P(n)$ 的时候可以假设什么？

   $P(m)$ 成立，这里 $m$ 是任意小于 $n$ 的自然数。

   只假设 $P(n - 1)$ 成立。

   $P(m)$ 成立，这里 $m$ 是任意小于或等于 $n$ 的自然数。

   什么也不能假设，直到分别证明了 $P(1)$ 和 $P(2)$。

3. 第 3 题来自前面的单元按照本课程的正式缩写，$(\varphi \rightarrow \psi)$ 用或非和否定写出来，是哪个公式？

   $\neg(\neg\varphi \downarrow \psi)$。

   $(\neg\varphi \downarrow \psi)$。

   $\neg(\varphi \downarrow \neg\psi)$。

   没有确定的公式：取决于决定怎样读它。

4. 第 4 题模式 A1 是 $(\varphi \rightarrow (\psi \rightarrow \varphi))$。公式 $(v_{1} \rightarrow (v_{2} \rightarrow v_{3}))$ 是 A1 的实例吗？

   不是：$\varphi$ 的第一次出现和最后一次出现处必须代入同一个公式，而这里它们是 $v_{1}$ 和 $v_{3}$。

   是，取 $\varphi := v_{1}$ 和 $\psi := v_{2}$。

   是，因为凡是后件为另一个蕴涵的蕴涵，都是 A1 的实例。

   不是，因为模式的实例不能含有变元。

5. 第 5 题在一个推演中已经有行 $\psi$ 和 $(\varphi \rightarrow \psi)$，其中 $\varphi$ 和 $\psi$ 是不同的公式。对这两行应用分离规则，可以写出哪个公式？

   没有：分离规则要求前件 $\varphi$，而现有的是后件。

   $\varphi$。

   $(\psi \rightarrow \varphi)$。

   $\neg\varphi$。

6. 第 6 题已知 $\{\varphi\} \vdash \psi$，即存在一个 $\psi$ 的推演，其唯一的前提是 $\varphi$。那么演绎定理断言什么？

   $\vdash (\varphi \rightarrow \psi)$：这个蕴涵是定理。

   $\vdash \psi$：前提可以直接删去。

   $\vdash (\psi \rightarrow \varphi)$。

   $\{\psi\} \vdash \varphi$。

7. 第 7 题不添加其他前提，由集合 $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\}$ 可推出什么？

   $(\varphi \rightarrow \chi)$。

   $\chi$，只要应用两次分离规则。

   $(\chi \rightarrow \varphi)$。

   $(\varphi \wedge \chi)$。

8. 第 8 题双重否定替换规则（双否替换）在一行中只改变子公式的一次出现，并且作用于基础语言的符号串。子公式 $\neg v_{1}$ 在 $(v_{1} \rightarrow v_{2})$ 所表示的符号串中出现几次？

   两次。

   一次，即对应于前件的那一次。

   一次也没有：这个公式不含否定。

   四次。

9. 第 9 题由 $(\neg\varphi \rightarrow \psi)$ 通过逆否律，不添加双重否定，得到哪个公式？

   $(\neg\psi \rightarrow \varphi)$。

   $(\psi \rightarrow \neg\varphi)$。

   $(\varphi \rightarrow \neg\psi)$。

   $(\neg\psi \rightarrow \neg\varphi)$。

10. 第 10 题$(\varphi \vee \psi)$ 与 $(\neg\varphi \rightarrow \psi)$ 表示同一个公式吗？

    不：前者是 $\neg(\varphi \downarrow \psi)$，后者是 $\neg(\neg\neg\varphi \downarrow \psi)$；它们是不同的公式，彼此可证等价。

    是，根据蕴涵的定义。

    是，因为两者都读作“$\varphi$ 或 $\psi$”。

    不，而且也不能由其中一个推出另一个。

11. 第 11 题已知 $\varphi \dashv\vdash \varphi'$，即二者可以互相推出。是什么保证了也有 $\neg\varphi \dashv\vdash \neg\varphi'$？

    一条定理，即等价替换，它用演绎定理和逆否律来证明。

    不需要特别的依据：只要对等价式“两边同时否定”就行。

    否定的定义，因为 $\neg\varphi$ 是 $(\varphi \downarrow \varphi)$。

    什么也不能，因为这不成立：否定可能把等价的公式分开。

12. 第 12 题由前提集 $\Gamma \cup \{\neg\varphi\}$ 推出了一个公式 $\chi$ 及其否定 $\neg\chi$。可以得出什么结论？

    $\Gamma \vdash \varphi$。

    $\Gamma \vdash \neg\varphi$。

    由 $\Gamma$ 可以推出任何公式。

    什么也不能：推出矛盾的推演什么也证明不了。

13. 第 13 题蕴涵的否定 $\neg(\varphi \rightarrow \psi)$ 等价于哪个公式？

    等价于 $(\varphi \wedge \neg\psi)$。

    等价于 $(\neg\varphi \rightarrow \neg\psi)$。

    等价于 $(\varphi \rightarrow \neg\psi)$。

    等价于 $(\neg\varphi \wedge \psi)$。