语义学：导言

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

1. 第 1 题来自前面的单元给出一个函数在每个变元上的值，再给出一条规则，计算它在 $\sigI\varphi\psi$ 上的值，所依据的是 $\varphi$、$\psi$ 以及它在两者上的值，就定义了公式上的一个函数。是什么保证这样恰好定义了一个函数？

   唯一可读性：每个复合公式都只能以一种方式分解为它的首个圆盘和它的两个成分。

   规则总是返回 $0$ 或 $1$。

   什么也不能保证：必须逐个公式检查其值，而公式有无穷多个，这做不到。

   缩写 $\neg$、$\vee$ 和 $\wedge$ 也具有唯一可读性。

2. 第 2 题来自前面的单元按照课程的正式缩写，$(\varphi \vee \varphi)$ 是哪个公式？

   与 $\neg\neg\varphi$ 是同一个符号串。

   就是 $\varphi$ 本身，根据幂等律。

   $(\varphi \downarrow \varphi)$。

   哪个也不是：析取要求两个不同的公式。

3. 第 3 题来自前面的单元要用对复杂度的归纳证明所有公式都具有某一性质，需要处理哪些情形？

   变元和唯一的形成规则 $\sigI\varphi\psi$，即 $(\varphi \downarrow \psi)$。

   变元、否定、合取和析取。

   只有规则 $(\varphi \downarrow \psi)$：变元是它的特例。

   变元和六个联结词 $\neg$、$\vee$、$\wedge$、$\rightarrow$、$\leftrightarrow$ 和 $\veebar$。

4. 第 4 题来自前面的单元按照归纳法那一课的定义，把公式 $\alpha$ 换成公式 $\beta$（在 $\varphi$ 中作代入）时，$\alpha$ 的哪些出现会被改变？

   它作为子公式的所有出现，同时改变。

   只有第一个，从左到右读符号串时的第一个。

   只有在缩写写法中看得见的那些。

   $\alpha$ 的出现，然后还有在 $\beta$ 的副本中出现的那些。

5. 第 5 题一个赋值使 $p$ 取值 $0$，使 $q$ 取值 $1$。如果 $(\varphi \downarrow \psi)$ 取值 $1$ 当且仅当 $\varphi$ 和 $\psi$ 都取值 $0$，那么公式 $(p \downarrow (q \downarrow p))$ 取什么值？

   $1$。

   $0$，因为 $q$ 的值为 $1$。

   不知道其余变元的值就无法计算。

   取决于成分如何组合。

6. 第 6 题$\not\models \varphi$ 是什么意思？

   某个赋值给 $\varphi$ 的值为 $0$：$\varphi$ 不是有效式。

   $\varphi$ 是矛盾式。

   没有任何赋值满足 $\varphi$。

   $\varphi$ 在课程的系统中不可推演。

7. 第 7 题已知 $\Gamma \cup \{\varphi\} \models \psi$：每个满足 $\Gamma$ 和 $\varphi$ 的赋值都满足 $\psi$。由此可得什么？

   $\Gamma \models (\varphi \rightarrow \psi)$。

   $\Gamma \models \psi$。

   $\Gamma \models (\psi \rightarrow \varphi)$。

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

8. 第 8 题公式 $(v_{1} \vee \neg v_{1})$ 是有效式。根据统一代入定理，下列哪个公式是有效式？

   $(\neg v_{2} \vee \neg\neg v_{2})$。

   $(v_{1} \vee \neg v_{2})$。

   $(\neg v_{2} \vee \neg v_{3})$。

   哪个也不是：统一代入只允许把一些变元换成另一些变元。

9. 第 9 题按照课程的约定，不加括号写出的表达式 $v_{1} \wedge v_{2} \wedge v_{3}$ 表示哪个公式？

   $((v_{1} \wedge v_{2}) \wedge v_{3})$。

   $(v_{1} \wedge (v_{2} \wedge v_{3}))$。

   两种组合都是，因为它们是同一个符号串。

   哪个也不是：不加括号，表达式什么也不表示。

10. 第 10 题一个二元真值函数指派一个值（$0$ 或 $1$）给四行 $(1, 1)$、$(1, 0)$、$(0, 1)$ 和 $(0, 0)$ 中的每一行。二元真值函数共有多少个？

11. 第 11 题一个只用 $\wedge$ 和 $\vee$ 由变元写成的公式，可能取值 $0$ 吗？这里考虑的是把 $1$ 给所有变元的那个赋值。

    不能：每个只用 $\wedge$ 和 $\vee$ 写成的公式在这个赋值下都取值 $1$。

    能，只要嵌套足够多的合取和析取。

    能：既然或非单独就够用，合取与析取也够用。

    不写出每个公式的真值表就无法知道。

12. 第 12 题文字是一个变元或一个变元的否定。下列公式中哪个是文字？

    $\neg v_{2}$。

    $\neg\neg v_{1}$。

    $(v_{1} \wedge v_{2})$。

    $\top$。

13. 第 13 题合取范式 $(\neg v_{1} \vee v_{2} \vee v_{1}) \wedge (v_{3} \vee \neg v_{2})$ 是有效式吗？

    不是：第二个子句不含任何互补对，把 $0$ 给 $v_{3}$、把 $1$ 给 $v_{2}$ 的赋值否证它。

    是：第一个子句含有互补对，有一个就够了。

    是，因为它是可满足的。

    没有八行的真值表就无法判定。

14. 第 14 题要把公式化为析取范式，就把合取对析取分配。正确的规则是哪一条？

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$。

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \vee \chi))$。

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$。

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee \chi)$。

15. 第 15 题一个电路中有两个正向开关，分别由拉杆 $p$ 和 $q$ 控制，串联在一起，这一组又与一个由拉杆 $r$ 控制的正向开关并联。哪个公式说出电路何时导通？

    $((p \wedge q) \vee r)$。

    $((p \vee q) \wedge r)$。

    $((p \wedge q) \wedge r)$。

    $((p \vee q) \vee r)$。