1. 1. 最后写在最前
  2. 2. 习题 2.1 说明下列联结词不是真值函数联结词。
  3. 3. 习题 2.2 将下列语句符号化（给出“词典”）。
  4. 4. 习题 2.3 将下列论说符号化（给出“词典”），并判断它们是否有效（给出理由）。
  5. 5. 习题 2.4 填写空格，使下列命题都成立。
  6. 6. 习题 2.5 给出下列公式的真值表。
  7. 7. 习题 2.6 判断下列说法的对错，并给出理由。
  8. 8. 习题 2.7 在每个括号中画 $\cmark$ 或 $\xmark$。分别表明“可以是”和“一定不是”。
  9. 9. 习题 2.8 设 $\phi$ 和 $\psi$ 为任意公式。判断下列命题的真假：
  10. 10. 习题 2.9 设 $\phi$ 和 $\psi$ 为任意公式。在每个括号中画 $\cmark$ 或 $\xmark$，分别表明“对”和“错”：
  11. 11. 习题 2.10 设 $\phi$ 和 $\psi$ 为任意公式。在每个括号中画 $\cmark$ 或 $\xmark$，分别表明“对”和“错”：
  12. 12. 习题 2.11 说明怎样用化简真值表方法证明一个公式重言蕴含另一个公式，或重言等值于另一个公式。
  13. 13. 习题 2.12 设 $\phi$，$\psi$ 和 $\chi$ 为任意公式。用（简化）真值表方法说明下列命题都成立：
  14. 14. 习题 2.13 设 $\phi$，$\psi$ 和 $\chi$ 为任意公式。用（简化）真值表方法说明下列每一组中的公式都是重言等值的：
  15. 15. 习题 2.14 用（简化）真值表方法说明下列各命题都不成立：
  16. 16. 习题 2.15 用（简化）真值表方法说明下列形式的公式都是重言式：
  17. 17. 习题 2.16 用（简化）真值表方法说明下列形式的公式都是矛盾式：
  18. 18. 习题 2.17 用（简化）真值表方法说明下列形式的公式都是或然式：
  19. 19. 习题 2.18 设 $\Gamma = \{\psi_0, \cdots, \psi_n\}$ 为任意的又穷公式集，$\phi$ 为任意公式。给出下列命题成立的理由：
  20. 20. 习题 2.19 设 $\phi,\psi,\phi_0,\cdots,\phi_n$ 为任意公式且 $\Gamma=\{\phi_0,\cdots,\phi_n\}$。给出下列命题成立的理由：
  21. 21. 习题 2.19 将下列公式改写为使用波兰学派记法的公式。完成后，不看下列公式，把那些使用波兰学派记法的公式再改写成我们这个语言的公式，然后再和下列公式对照：

符号逻辑讲义 第二章 习题

, ,

最后写在最前

  • 根据 《符号逻辑讲义》勘误，习题 2.9 和习题 2.10，“可以是”应为“对”，“一定不是”应为“错”。改完了题目还是有点奇怪，不过知道大概要测试的是什么差不多就行了。
  • 用简化真值表法的题没有写序号，这样不怎么好参考，写又很麻烦，反正也不难。
  • 习题 2.18 和 习题 2.19 答得不好，勉强写了些。
  • 波兰学派记法简直是乱码。

习题 2.1 说明下列联结词不是真值函数联结词。

下面每道题中，填入的句子都是真的，构成的符合句中第一句是真的，第二句是假的。

  • 因为 今天是星期天 ，所以 今天不用上班 。
    因为 今天是星期天 ，所以 太阳从东边升起 。

  • 可以想象 1+1=2 。
    可以想象 地球绕着太阳转 。（假定生活在天文学极不普及而简单的加减法已普及的年代或地区)

  • 昨天 太阳从东边升起 。
    昨天 爱因斯坦提出了相对论 。

  • 张三相信 1+1=2 。
    张三相信 地球绕着太阳转 。（假定生活在天文学极不普及而简单的加减法已普及的年代或地区)

  • 李四认为 1+1=2 。
    李四认为 地球绕着太阳转 。

  • 王五知道 1+1=2 。
    王五知道 地球绕着太阳转 。

  • 政客喜欢说 世界人口不断增长 。
    政客喜欢说 1+1=2 。

  • 从平民的角度看 太阳从东边升起 。
    从平民的角度看 老国王没有死 。（假定老国王装作病死隐居）

习题 2.2 将下列语句符号化（给出“词典”）。

  • 不是所有的人都讲道理。
    $p$：所有人都讲道理。

  • 如果在选举时你不去投票，那么你就要忍受我选的白痴。
    $p$：在选举时你不去投票。$q$：你要忍受我选的白痴。

  • 张三是李四的祖先当且仅当李四是张三的后代。
    $p$：张三是李四的祖先。$q$：李四是张三的后代。

  • 除非有奇迹出现，中国足球队5年内挤不进世界16强。
    $p$：有奇迹出现。$q$：中国足球队5年内挤进世界16强。

  • 张三只有坚持锻炼才有好身体；但并非只要他坚持锻炼就有好身体。
    $p$：张三坚持锻炼。$q$：张三有好身体。

  • 如果张三一进大学就知道自己想做什么，那么，他大学期间不会浪费太多时间，而他的成绩也不会太差。
    $p$：张三一进大学就知道自己想做什么。$q$：张三大学期间会浪费太多时间。
    $r$：张三的成绩会太差。

  • 要么明天有海战，要么明天没有海战；但明天不必然有海战，而且明天也不必然没有海战。
    $p$：明天有海战。$q$：明天必然有海战。

习题 2.3 将下列论说符号化（给出“词典”），并判断它们是否有效（给出理由）。

  • 如果今天是星期三，那么明天有逻辑课。因此，如果明天没有逻辑课，则今天不是星期三。

    “词典”：$p$：今天是星期三。$q$：明天有逻辑课。
    符号化：$p \to q\; / \therefore \lnot q \to \lnot p$。真值表是：

    没有反例，所以是有效的。

  • 要么士兵拿破仑想当将军，要么士兵拿破仑不想当将军。如果士兵拿破仑想当将军，那么他不是一个好士兵。如果士兵拿破仑不想当将军，那么他也不是一个好士兵。所以士兵拿破仑不是一个好士兵。

    “词典”：$p$：士兵拿破仑想当将军。$q$：士兵拿破仑是一个好士兵。
    符号化：$p \lor \lnot p,\; p \to \lnot q,\; \lnot p \to \lnot q\; / \therefore \lnot q$。真值表是：

    没有反例，所以是有效的。

  • 如果上帝死了，那么做什么坏事都是可以的。如果做什么坏事都是可以的，那么我考试作弊也是可以的。所以，如果上帝死了，我考试作弊是可以的。

    “词典”：$p$：上帝死了。$q$：做什么坏事都是可以的。$r$：我考试作弊是可以的。
    符号化：$p \to q,\; q \to r\; \therefore p \to r$。真值表是：

    没有反例，所以是有效的。

  • 花都是红的当且仅当李四不是色盲。花不都是红的。所以李四是色盲。

    “词典”：$p$：花都是红的。$q$：李四是色盲。
    符号化：$p \leftrightarrow \lnot q,\; \lnot p\; \therefore q$。真值表是

    没有反例，所以是有效的。

  • 如果 $a$ 是正整数，则 $a$ 有唯一的后继，并且 $a$ 有唯一的前驱。$a$ 要么并未有唯一的后继，要么并非由唯一的前驱。所以 $a$ 不是正整数。

    “词典”：$p$：$a$ 是正整数。$q$：$a$ 有唯一的后继。$r$：$a$ 有唯一的前驱。
    符号化：$p \to q \land r,\; \lnot q \lor \lnot r\; \therefore \lnot p$。真值表是：

    没有反例，所以是有效的。

习题 2.4 填写空格，使下列命题都成立。

  • 一个否定式是假的当且仅当 它否定的公式是真的 。
  • 一个合取式是假的当且仅当 它的其中一个合取支是假的 。
  • 一个析取式是假的当且仅当 它的两个析取支都是假的 。
  • 一个蕴含式是假的当且仅当 它的前件是真的而后件是假的 。
  • 一个等值式是假的当且仅当 它的两个直接子公式真值不同 。

习题 2.5 给出下列公式的真值表。

  • $\lnot\lnot p \to p$

  • $p \to (\lnot p \to q)$

  • $p \to p \land q$

  • $p \land q \to p \lor q$

  • $p \lor q \to p \land q$

  • $p \lor q \to \lnot (p \to q)$

  • $p \lor q \to \lnot (p \to \lnot q)$

  • $(p \to q) \to \lnot (\lnot q \to \lnot p)$

  • $\lnot (p \lor q) \to \lnot p \land \lnot q$

  • $\lnot (p \land q) \to \lnot p \lor \lnot q$

  • $(p \to q) \lor (q \to p)$

  • $(\lnot p \to q) \to ((\lnot p \to \lnot q) \to p)$

  • $(p \to (q \to r)) \to ((r \to q) \to (r \to p))$

  • $(p \leftrightarrow q) \leftrightarrow \lnot(p \land q) \lor \lnot (\lnot p \land \lnot q)$

  • $(p \lor q) \land (p \lor r) \to p \lor (q \land r)$

习题 2.6 判断下列说法的对错，并给出理由。

  • 任一公式都或者是重言式，或者是矛盾式，或者是或然式；并且只能是这三种公式中的一种。

    设 $p$ 是原子公式，可以列出真值表知道 $p$ 是或然式，$p \lor \lnot p$ 是重言式，$p \land \lnot p$ 是矛盾式，所以一个公式可能是重言式、矛盾式或这是或然式。

    若一个公式不是这三种公式的一种，那么它的真值表中至少有一行的真值既不是 $\T$ 也不是 $\F$，但这是不可能的，因为公式都有真值而且真值只有 $\T$ 和 $\F$，因此任一公式都或者是重言式，或者是矛盾式，或者是或然式。

    若公式是重言式，它的真值表的每一行都是 $\T$，没有任何一行是 $\F$，所以不可能是矛盾式或者是或然式；若公式是矛盾式，它的真值表的每一行都是 $\F$，没有任何一行是 $\T$，所以不可能是重言式或者是或然式；若公式是或然式，它的真值表中一些行是 $\T$，所以不可能是矛盾式，而且由于真值表中有一些行是 $\F$ 所以不可能是重言式。因此只能是三种公式中的一种。

    综上所得这个说法是对的。

  • 对任意公式集 $\Gamma$ 和任意公式 $\phi$，$\Gamma$ 或者重言蕴含 $\phi$ 或者重言蕴含 $\lnot \phi$。

    说法是错的。可以给出反例 $\Gamma = \{ p \}$，$\phi = q$，分别画出联合真值表：

    可以看出第一个表的第二行和第二个表的第一行都是前提全部为真而结论为假。

  • 对任意公式 $\phi$ 和 $\psi$，$\phi$ 或者与 $\psi$ 重言等价或者与 $\lnot \psi$ 重言等价。

    说法是错的。可以给出反例 $\phi = p$ 而 $\psi = q$。

  • 对任意公式 $\phi$，或者 $\phi$ 可满足或者 $\lnot \phi$ 可满足。

    说法是对的。由于 $\phi$ 是公式，它或者是重言式，或者是矛盾式，或者是或然式。若 $\phi$ 是重言式或或然式，它的真值表有值为 $\T$ 的行，所以可满足；若 $\phi$ 是否定式，$\phi$ 的真值表的每一行都是 $\F$ 而 $\lnot \phi$ 的真值表的每一行都是 $\T$，因此 $\lnot \phi$ 可满足。

习题 2.7 在每个括号中画 $\cmark$ 或 $\xmark$。分别表明“可以是”和“一定不是”。

如果正确的画法中有两个 $\xmark$，由于任一公式都或者是重言式，或者是矛盾式，或者是或然式，并且只能是这三种公式中的一种，所以最后一个一定是画 $\cmark$ 且可以读作“一定是”。

  • 重言式与重言式的析取：($\cmark$) 重言式，($\xmark$) 矛盾式，($\xmark$) 或然式。

  • 重言式与矛盾式的析取：($\cmark$) 重言式，($\xmark$) 矛盾式，($\xmark$) 或然式。

  • 重言式与或然式的析取：($\cmark$) 重言式，($\xmark$) 矛盾式，($\xmark$) 或然式。

  • 以重言式为前件的蕴含式：($\cmark$) 重言式，($\cmark$) 矛盾式，($\cmark$) 或然式。

  • 以重言式为前件、矛盾式为后件的蕴含式：($\xmark$) 重言式，($\cmark$) 矛盾式，($\xmark$) 或然式。

  • 以重言式为前件、或然式为后件的蕴含式：($\xmark$) 重言式，($\xmark$) 矛盾式，($\cmark$) 或然式。

  • 以矛盾式为前、后件的蕴含式：($\cmark$) 重言式，($\xmark$) 矛盾式，($\xmark$) 或然式。

  • 以矛盾式为件、重言式为后件的蕴含式：($\cmark$) 重言式，($\xmark$) 矛盾式，($\xmark$) 或然式。

  • 以矛盾式为件、或然式为后件的蕴含式：($\cmark$) 重言式，($\xmark$) 矛盾式，($\xmark$) 或然式。

  • 以或然式为前件的蕴含式：($\cmark$) 重言式，($\xmark$) 矛盾式，($\cmark$) 或然式。

  • 以或然式为前件、重言式为后件的蕴含式：($\cmark$) 重言式，($\xmark$) 矛盾式，($\xmark$) 或然式。

  • 以或然式为前件、矛盾式为后件的蕴含式：($\xmark$) 重言式，($\xmark$) 矛盾式，($\cmark$) 或然式。

  • 两端都是重言式的等值式：($\cmark$) 重言式，($\xmark$) 矛盾式，($\xmark$) 或然式。

  • 两端分别是重言式和矛盾式的等值式：($\xmark$) 重言式，($\cmark$) 矛盾式，($\xmark$) 或然式。

  • 两端分别是重言式和或然式的等值式：($\xmark$) 重言式，($\xmark$) 矛盾式，($\cmark$) 或然式。

  • 两端都是矛盾式的等值式：($\cmark$) 重言式，($\xmark$) 矛盾式，($\xmark$) 或然式。

  • 两端分别是矛盾式和或然式的等值式：($\xmark$) 重言式，($\xmark$) 矛盾式，($\cmark$) 或然式。

  • 两端都是或然式的等值式：($\cmark$) 重言式，($\cmark$) 矛盾式，($\cmark$) 或然式。

习题 2.8 设 $\phi$ 和 $\psi$ 为任意公式。判断下列命题的真假：

  • $\phi \land \psi$ 是重言式当且仅当 $\phi$ 是重言式且 $\psi$ 是重言式。
    真。

  • $\phi \lor \psi$ 是重言式当且仅当 $\phi$ 是重言式或 $\psi$ 是重言式。
    假。若 $\phi \lor \psi$ 是重言式，可能 $\phi$ 和 $\psi$ 都是或然式，如 $\phi = p$，$\psi = \lnot p$。

  • $\phi \to \psi$ 是重言式当且仅当如果 $\phi$ 是重言式那么 $\psi$ 是重言式。
    假。当如果 $\phi$ 是重言式那么 $\psi$ 是重言式，如果 $\phi$ 是或然式而 $\psi$ 是矛盾式，与条件不矛盾，但 $\phi \to \psi$ 是或然式。

  • $\phi \leftrightarrow \psi$ 是重言式当且仅当或者 $\phi$ 和 $\psi$ 都是重言式或者 $\phi$ 和 $\psi$ 都是不是重言式。
    假。可以举反例：$\phi = p$，$\psi = p$。$\phi$ 和 $\psi$ 都是或然式，但 $\phi \leftrightarrow \psi$ 是重言式。

  • $\phi$ 是重言式当且仅当 $\lnot \phi$ 不是重言式。
    假。若 $\lnot \phi$ 是或然式，所以不是重言式，但 $\phi$ 也是或然式而不是重言式。

  • $\phi \land \psi$ 是矛盾式当且仅当 $\phi$ 是矛盾式且 $\psi$ 是矛盾式。
    假。反例：当 $\phi$ 是矛盾式而 $\psi$ 是重言式，$\phi \land \psi$ 也是矛盾式。

  • $\phi \land \psi$ 是矛盾式当且仅当或者 $\phi$ 是矛盾式或者 $\psi$ 是矛盾式。
    假。反例：$\phi = p$，$\psi = \lnot p$。$\phi$ 和 $\psi$ 都是或然式，但 $\phi \land \psi$ 也是矛盾式。

  • $\phi \land \psi$ 是矛盾式当且仅当如果 $\phi$ 是矛盾式那么 $\psi$ 是矛盾式。
    假。当如果 $\phi$ 是矛盾式那么 $\psi$ 是矛盾式，如果 $\phi$ 和 $psi$ 都是重言式，与条件不矛盾，但 $\phi \land \psi$ 是重言式。

  • $\phi \leftrightarrow \psi$ 是矛盾式当且仅当或者 $\phi$ 和 $\psi$ 都是矛盾式或者 $\phi$ 和 $\psi$ 都不是矛盾式。
    假。反例：当 $\phi$ 是矛盾式而 $\psi$ 是重言式，$\phi \leftrightarrow \psi$ 也是矛盾式。

  • $\phi$ 是矛盾式当且仅当 $\lnot \phi$ 不是矛盾式。
    假。反例：当 $\lnot \phi$ 是或然式，$\lnot \phi$ 不是矛盾式，但 $\phi$ 是或然式。

  • $\phi \land \psi$ 是或然式当且仅当 $\phi$ 是或然式且 $\psi$ 是或然式。
    假。反例：当 $\phi$ 是或然式而 $\psi$ 是重言式，$\phi \land \psi$ 也是或然式。

  • $\phi \land \psi$ 是或然式当且仅当 $\phi$ 是或然式或者 $\psi$ 是或然式。
    假。反例：当 $\phi = p$ 而 $\psi = \lnot p$，两个都是或然式，但 $\phi \land \psi$ 是矛盾式。

  • $\phi \land \psi$ 是或然式当且仅当如果 $\phi$ 是或然式那么 $\psi$ 是或然式。
    假。反例：当 $\phi = p$ 而 $\psi = \lnot p$，两个都是或然式，但 $\phi \land \psi$ 是矛盾式。

  • $\phi \leftrightarrow \psi$ 是或然式当且仅当 $\phi$ 和 $\psi$ 都是或然式或者 $\phi$ 和 $\psi$ 都不是或然式。
    假。反例：当 $\phi$ 是或然式而 $\psi$ 是重言式，$\phi \leftrightarrow \psi$ 也是或然式。

  • $\phi$ 是或然式当且仅当 $\lnot \phi$ 不是或然式。
    假。若 $\phi$ 是或然式，$\lnot \phi$ 还是或然式。

习题 2.9 设 $\phi$ 和 $\psi$ 为任意公式。在每个括号中画 $\cmark$ 或 $\xmark$，分别表明“对”和“错”：

  • 如果 $\phi \leftrightarrow \psi$ 是重言式，那么 $\phi$ 是重言式当且仅当 $\psi$ 是重言式 ($\cmark$)，矛盾式 ($\xmark$)，或然式 ($\xmark$)。

  • 如果 $\phi \leftrightarrow \psi$ 是重言式，那么 $\phi$ 是矛盾式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\cmark$)，或然式 ($\xmark$)。

  • 如果 $\phi \leftrightarrow \psi$ 是重言式，那么 $\phi$ 是或然式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\xmark$)，或然式 ($\cmark$)。

  • 如果 $\phi \leftrightarrow \psi$ 是矛盾式，那么 $\phi$ 是重言式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\cmark$)，或然式 ($\xmark$)。

  • 如果 $\phi \leftrightarrow \psi$ 是矛盾式，那么 $\phi$ 是矛盾式当且仅当 $\psi$ 是重言式 ($\cmark$)，矛盾式 ($\xmark$)，或然式 ($\xmark$)。

  • 如果 $\phi \leftrightarrow \psi$ 是矛盾式，那么 $\phi$ 是或然式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\xmark$)，或然式 ($\cmark$)。

  • 如果 $\phi \leftrightarrow \psi$ 是或然式，那么 $\phi$ 是重言式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\xmark$)，或然式 ($\cmark$)。

  • 如果 $\phi \leftrightarrow \psi$ 是或然式，那么 $\phi$ 是矛盾式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\xmark$)，或然式 ($\cmark$)。

  • 如果 $\phi \leftrightarrow \psi$ 是或然式，那么 $\phi$ 是或然式当且仅当 $\psi$ 是重言式 ($\cmark$)，矛盾式 ($\cmark$)，或然式 ($\cmark$)。

习题 2.10 设 $\phi$ 和 $\psi$ 为任意公式。在每个括号中画 $\cmark$ 或 $\xmark$，分别表明“对”和“错”：

  • 如果 $\phi \to \psi$ 是重言式，那么 $\phi$ 是重言式当且仅当 $\psi$ 是重言式 ($\cmark$)，矛盾式 ($\xmark$)，或然式 ($\xmark$)。

  • 如果 $\phi \to \psi$ 是重言式，那么 $\phi$ 是矛盾式当且仅当 $\psi$ 是重言式 ($\cmark$)，矛盾式 ($\cmark$)，或然式 ($\cmark$)。

  • 如果 $\phi \to \psi$ 是重言式，那么 $\phi$ 是或然式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\xmark$)，或然式 ($\cmark$)。

  • 如果 $\phi \to \psi$ 是矛盾式，那么 $\phi$ 是重言式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\cmark$)，或然式 ($\xmark$)。

  • 如果 $\phi \to \psi$ 是矛盾式，那么 $\phi$ 是矛盾式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\xmark$)，或然式 ($\xmark$)。

  • 如果 $\phi \to \psi$ 是矛盾式，那么 $\phi$ 是或然式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\xmark$)，或然式 ($\xmark$)。

  • 如果 $\phi \to \psi$ 是或然式，那么 $\phi$ 是重言式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\xmark$)，或然式 ($\cmark$)。

  • 如果 $\phi \to \psi$ 是或然式，那么 $\phi$ 是矛盾式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\xmark$)，或然式 ($\xmark$)。

  • 如果 $\phi \to \psi$ 是或然式，那么 $\phi$ 是或然式当且仅当 $\psi$ 是重言式 ($\xmark$)，矛盾式 ($\cmark$)，或然式 ($\cmark$)。

习题 2.11 说明怎样用化简真值表方法证明一个公式重言蕴含另一个公式，或重言等值于另一个公式。

要用化简真值表方法证明一个公式 $\phi$ 重言蕴含另一个公式 $\psi$，先假设作为 $\phi$ 为真而 $\psi$ 为假，据此推算子公式的真值，如果这个过程中遇到某个公式既真又假，那么 $\phi$ 重言蕴含 $\psi$，如果没有遇到，则 $\phi$ 不重言蕴含 $\psi$。

要用化简真值表方法证明一个公式 $\phi$ 重言等值于另一个公式 $\psi$，先假设 $\phi$ 为真而 $\psi$ 为假，据此推算子公式的真值，如果这个过程中没有遇到某个公式既真又假，那么 $\phi$ 不重言等值于 $\psi$，否则重新假设 $\phi$ 为假而 $\psi$ 为真后推算子公式的真值，如果这个过程中遇到某个公式既真又假，那么 $\phi$ 重言等值于 $\psi$，如果没有遇到，则 $\phi$ 不重言等值于 $\psi$。

习题 2.12 设 $\phi$，$\psi$ 和 $\chi$ 为任意公式。用（简化）真值表方法说明下列命题都成立：

  • $\phi \vDash_0 \phi$

  • $\psi \vDash_0 \phi \lor \psi$

  • $\phi,\psi \vDash_0 \phi \land \psi$

  • $\phi \vDash_0 \phi \to \phi$

  • $\phi \vDash_0 \psi \to \phi$

  • $\phi, \phi \to \psi \vDash_0 \psi$

  • $\psi, \lnot \psi \vDash_0 \phi$

  • $\phi \lor \psi, \lnot \psi \vDash_0 \phi$

  • $\lnot (\phi \to \lnot \psi) \vDash_0 \phi$

  • $\lnot (\phi \to \lnot \psi) \vDash_0 \psi$

  • $\phi \to \lnot \psi, \psi \vDash_0 \lnot \phi$

  • $\phi \to \psi, \chi \to \phi \vDash_0 \chi \to \phi$

  • $\phi \land \psi \vDash_0 \psi \land \phi$

  • $\phi \lor \psi \vDash_0 \psi \lor \phi$

  • $\phi \land \psi \vDash_0 \psi \lor \phi$

  • $(\phi \to \phi) \to \psi \vDash_0 \psi$

  • $\lnot \phi \land \lnot \psi \vDash_0 \lnot (\phi \lor \psi)$

  • $\lnot \phi \land \lnot \psi \vDash_0 \lnot (\phi \land \psi)$

  • $\phi \leftrightarrow \psi, \phi \vDash_0 \psi$

  • $\phi \leftrightarrow \psi, \psi \vDash_0 \phi$

习题 2.13 设 $\phi$，$\psi$ 和 $\chi$ 为任意公式。用（简化）真值表方法说明下列每一组中的公式都是重言等值的：

  • $\phi \to \psi, \lnot \phi \lor \psi, \lnot(\phi \land \lnot \psi)$

  • $\phi \lor \psi, \lnot(\lnot \phi \land \lnot \psi), \lnot \phi \to \psi$

  • $\phi \land \psi, \lnot(\lnot \phi \lor \lnot \psi), \lnot (\phi \to \lnot \psi)$

  • $\phi \leftrightarrow \psi, (\phi \to \psi) \land (\psi \to \phi), (\phi \land \psi) \lor (\lnot \phi \land \lnot \psi)$

习题 2.14 用（简化）真值表方法说明下列各命题都不成立：

  • $p \vDash_0 p \land q$

  • $p \lor q \vDash_0 p$

  • $p \to q, q \vDash_0 p$

  • $p \to q \vDash_0 q$

  • $p \land q \vDash_0 (p \to r) \land (q \to r)$

  • $p \lor q \vDash_0 (p \to r) \lor (q \to r)$

  • $p \leftrightarrow q \vDash_0 p$

  • $p \leftrightarrow q \vDash_0 q$

习题 2.15 用（简化）真值表方法说明下列形式的公式都是重言式：

  • $\phi \leftrightarrow \lnot \lnot \phi$

  • $\phi \to (\psi \to \phi)$

  • $\phi \to (\lnot \phi \to \psi)$

  • $\lnot \phi \to \lnot(\phi \land \psi)$

  • $\lnot \psi \to \lnot(\phi \land \psi)$

  • $\lnot (\phi \lor \psi) \leftrightarrow \lnot \phi \land \lnot \psi$

  • $\lnot (\phi \land \psi) \leftrightarrow \lnot \phi \lor \lnot \psi$

  • $\lnot (\lnot \phi \to \psi) \to \lnot \phi$

  • $\lnot (\lnot \phi \to \psi) \to \lnot \psi$

  • $(\phi \to \psi) \to ((\phi \to \lnot \psi) \to \lnot \phi)$

  • $(\phi \leftrightarrow \psi) \to (\psi \leftrightarrow \phi)$

  • $(\phi \leftrightarrow (\psi \leftrightarrow \chi)) \leftrightarrow ((\phi \leftrightarrow \psi) \leftrightarrow \chi)$

  • $\phi \lor (\psi_0 \land \cdots \land \phi_k) \leftrightarrow (\phi \lor \psi_0) \land \cdots \land (\phi \lor \psi_k)$

  • $\phi \land (\psi_0 \lor \cdots \lor \phi_k) \leftrightarrow (\phi \land \psi_0) \lor \cdots \lor (\phi \land \psi_k)$

习题 2.16 用（简化）真值表方法说明下列形式的公式都是矛盾式：

  • $\phi \land \lnot (\lnot \phi \to \psi)$

  • $(\phi \to \lnot \phi) \land (\lnot \phi \to \phi)$

  • $(\phi \lor \psi) \land (\lnot \phi \land \lnot \psi)$

  • $\lnot (\phi \to \psi) \land \lnot (\psi \to \phi)$

  • $(\lnot \phi \to \lnot \psi) \land \lnot((\lnot \phi \to \psi) \to \phi)$

  • $(\phi \to (\psi \to \chi)) \land \lnot ((\phi \to \psi) \to (\phi \to \chi))$

  • $(\phi \leftrightarrow \psi) \leftrightarrow (\lnot \phi \leftrightarrow \psi)$

  • $(\phi \leftrightarrow \psi) \leftrightarrow (\phi \leftrightarrow \lnot \psi)$

习题 2.17 用（简化）真值表方法说明下列形式的公式都是或然式：

  • $\phi \to \psi$

  • $\phi \to \lnot \lnot \lnot \phi$

  • $(\psi \to \psi) \to \phi$

  • $\lnot \phi \to \lnot (\phi \lor \psi)$

  • $\lnot \psi \to \lnot (\phi \lor \psi)$

  • $(\lnot \phi \to \psi) \to ((\phi \to \psi) \to \lnot \psi)$

  • $(\phi \leftrightarrow \psi) \to \phi \land \psi$

  • $(\phi \leftrightarrow \psi) \to \lnot \phi \land \lnot \psi$

习题 2.18 设 $\Gamma = \{\psi_0, \cdots, \psi_n\}$ 为任意的又穷公式集，$\phi$ 为任意公式。给出下列命题成立的理由：

  • 如果 $\Gamma$ 可满足，那么对于任何公式集 $\Delta$，$\Gamma \cap \Delta$ 也可满足；

    如果 $\Gamma$ 可满足，$\psi_0, \cdots, \psi_n$ 可能全部为真，由于 $\Gamma \cap \Delta$ 是 $\Gamma$ 的子集，此时也全部为真，因此是可满足的。

  • 如果 $\Gamma$ 不可满足，那么对任意公式集 $\Delta$，$\Gamma \cap \Delta$ 也不可满足；

    如果 $\Gamma$ 不可满足，任何情况下 $\psi_0, \cdots, \psi_n$ 中总有值为假的公式，因此 $\Gamma \cap \Delta$ 在任何情况下也会有值为假的公式，不可能同时为真，因此不可满足。

  • $\Gamma \cap \{\lnot \phi\}$ 不可满足当且仅当 $\Gamma$ 重言蕴含 $\phi$；

    $\Gamma \cap \{\lnot \phi\}$ 不可满足，则不可能存在 $\psi_0, \cdots, \psi_n$ 和 $\lnot \phi$ 都为真，即不可能有 $\psi_0, \cdots, \psi_n$ 同时为真而 $\phi$ 为假，根据重言蕴含的定义，$\Gamma$ 重言蕴含 $\phi$；如果 $\Gamma$ 重言蕴含 $\phi$，不可能有 $\psi_0, \cdots, \psi_n$ 同时为真而 $\phi$ 都为假，即不可能有 $\psi_0, \cdots, \psi_n$ 和 $\lnot \phi$ 都为真，因此 $\Gamma \cap \{\lnot \phi\}$ 不可满足。

  • 对任意 $i \leqslant n$，$\Gamma$ 不可满足当且仅当 $\Gamma - \{\psi_i\}$ 重言蕴含 $\lnot \psi_i$；

    如果 $\Gamma$ 不可满足，当 $\psi_i$ 为假，那么 $\lnot \psi_i$ 为真；当 $\psi_i$ 为真，由于 $\Gamma$ 不可满足，因此 $\Gamma - \{\psi_i\}$ 中至少有一个公式的真值是假，因此不可能是 $\Gamma - \{\psi_i\}$ 都为真的情况，由于 $\psi_i$ 必定为真或假，在两种情况下都不可能出现 $\Gamma - \{\psi_i\}$ 都为真而 $\lnot \psi_i$ 为假的情况，因此 $\Gamma - \{\psi_i\}$ 重言蕴含 $\lnot \psi_i$。

    如果 $\Gamma - \{\psi_i\}$ 重言蕴含 $\lnot \psi_i$，那么不可能出现 $\Gamma - \{\psi_i\}$ 的元素都为真而 $\lnot \psi_i$ 为假的情况，也就是说不可能出现 $\Gamma - \{\psi_i\}$ 的元素都为真且 $\psi_i$ 为真，即不可能有 $\Gamma$ 的元素全都是真的情况，因此 $\Gamma$ 不可满足。

  • 如果 $\Gamma$ 不可满足，那么 $\Gamma$ 重言蕴含 $\phi$；

    如果 $\Gamma$ 不可满足，那么不可能有 $\psi_0, \cdots, \psi_n$ 可能全部为真的情况，因此不可能有 $\psi_0, \cdots, \psi_n$ 可能全部为真而 $\phi$ 为假的情况，因此 $\Gamma$ 重言蕴含 $\phi$。

  • 如果 $\lnot \phi$ 不可满足，那么 $\Gamma$ 重言蕴含 $\phi$；

    如果 $\lnot \phi$ 不可满足，那么 $\lnot \phi$ 是矛盾式，即 $\phi$ 是重言式，因此不可能 $\psi_0, \cdots, \psi_n$ 可能全部为真而 $\phi$ 为假的情况，因为 $\phi$ 总是真的，因此 $\Gamma$ 重言蕴含 $\phi$。

  • 如果 $\Gamma$ 重言蕴含 $\phi$，并且 $\Gamma$ 可满足，那么 $\phi$ 也是可满足的；

    因为 $\Gamma$ 可满足，存在 $\psi_0, \cdots, \psi_n$ 全部为真的情况，由于 $\Gamma$ 重言蕴含 $\phi$，不可能 $\psi_0, \cdots, \psi_n$ 可能全部为真而 $\phi$ 为假的情况，因此当 $\psi_0, \cdots, \psi_n$ 全部为真时 $\phi$ 必然为真，即 $\phi$ 可能为真，因此 $\phi$ 是可满足的。

  • 如果 $\Gamma$ 重言蕴含 $\phi$ 并且 $\Gamma$ 重言蕴含 $\lnot \phi$，那么 $\Gamma$ 不可满足。

    因为 $\Gamma$ 重言蕴含 $\phi$，所以不可能 $\Gamma$ 的元素都为真且 $\phi$ 为假；因为 $\Gamma$ 重言蕴含 $\lnot \phi$，所以不可能 $\Gamma$ 的元素都为真且 $\phi$ 为真；由于 $\phi$ 要么真要么假，因此不可能 $\Gamma$ 的元素都为真，即 $\Gamma$ 不可满足。

习题 2.19 设 $\phi,\psi,\phi_0,\cdots,\phi_n$ 为任意公式且 $\Gamma=\{\phi_0,\cdots,\phi_n\}$。给出下列命题成立的理由：

  • $\phi$ 重言蕴含 $\psi$ 当且仅当 $\phi \to \psi$ 是重言式；

    由蕴含式的真值表可知 $\phi \to \psi$ 为假当且仅当 $\phi$ 为真而 $\psi$ 为假，若 $\phi$ 重言蕴含 $\psi$，有定义可知没有 $\phi$ 为真而 $\psi$ 为假的情况，因此 $\phi \to \psi$ 不可能为假，由定义可知 $\phi \to \psi$ 是重言式。

    如果 $\phi \to \psi$ 是重言式，不可能有 $\phi$ 为真而 $\psi$ 为假的情况，因此 $\phi$ 重言蕴含 $\psi$。

  • $\phi$ 重言等值于 $\psi$ 当且仅当 $\phi \leftrightarrow \psi$ 是重言式，当且仅当 $\psi \to \phi$ 与 $\phi \to \psi$ 都是重言式；

    若 $\phi$ 重言等值于 $\psi$，那么 $\phi$ 与 $\psi$ 的真值必然相同，由等值式和蕴含式的真值表可知，$\phi \leftrightarrow \psi$ 是重言式，$\psi \to \phi$ 与 $\phi \to \psi$ 也都是重言式。

    当 $\phi \leftrightarrow \psi$ 是重言式， $\phi$ 与 $\psi$ 的真值同时为真或同时为假，因此 $\phi$ 重言等值于 $\psi$。

    当 $\psi \to \phi$ 与 $\phi \to \psi$ 都是重言式，列出它们的联合真值表可知当 $\psi \to \phi$ 与 $\phi \to \psi$ 同时为真时，$\phi$ 与 $\psi$ 的真值相同，因此 $\phi$ 重言等值于 $\psi$。

  • $\Gamma$ 重言蕴含 $\phi$ 当且仅当 $\phi_0 \land \cdots \land \phi_n \to \psi$ 是重言式；

    如果 $\Gamma$ 重言蕴含 $\psi$，不存在 $\Gamma$ 全部为真而 $\psi$ 为假的情况，即不存在 $\phi_0 \land \cdots \land \phi_n$ 为真而 $\psi$ 为假的情况，因此 $\phi_0 \land \cdots \land \phi_n \to \psi$ 不可能为假，$\phi_0 \land \cdots \land \phi_n \to \psi$ 是重言式。

    如果 $\phi_0 \land \cdots \land \phi_n \to \psi$ 是重言式，不可能有 $\phi_0 \land \cdots \land \phi_n$ 为真而 $\psi$ 为假，而 $\phi_0 \land \cdots \land \phi_n$ 为真当且仅当 $\phi_0 \cdots \phi_n$ 全都为真，所以不可能有 $\Gamma$ 的元素都为真而 $\psi$ 为假，根据定义，$\Gamma$ 重言蕴含 $\psi$。

  • $\phi_0 \land \cdots \land \phi_n \to \psi$ 与 $\phi_0 \land \cdots \land \phi_{n-1} \to (\phi_n \to \psi)$ 重言等值；$(n \geqslant 1)$

    根据 (ii)，只需要用简化真值表方法证明 $(\phi_0 \land \cdots \land \phi_n \to \psi) \to (\phi_0 \land \cdots \land \phi_{n-1} \to (\phi_n \to \psi))$ 和 $(\phi_0 \land \cdots \land \phi_{n-1} \to (\phi_n \to \psi)) \to (\phi_0 \land \cdots \land \phi_n \to \psi)$ 都是重言式。

  • 如果 $\phi$ 是重言式，那么 $\Gamma$ 重言蕴含 $\phi$；

    根据 (iii)，只需用简化真值表方法证明 $\phi_0 \land \cdots \land \phi_n \to \phi$ 是重言式

  • $\Gamma$ 可满足当且仅当 $\phi_0 \land \cdots \land \phi_n$ 或者是或然式或者是重言式；

    如果 $\Gamma$ 可满足，那么它的联合真值表有全都是真的行，如果只有部分行如此，也就是说有，这些行 $\phi_0 \land \cdots \land \phi_n$ 的真值是真，其他的行 $\phi_0 \cdots \phi_n$ 有真有假，所以 $\phi_0 \land \cdots \land \phi_n$ 的真值是假的，因此 $\phi_0 \land \cdots \land \phi_n$ 有真有假，是或然式；如果全部行都是所有真值都是真，那么 $\phi_0 \land \cdots \land \phi_n$ 显然是重言式。

    如果 $\phi_0 \land \cdots \land \phi_n$ 或者是或然式或者是重言式，即 $\phi_0 \land \cdots \land \phi_n$ 可能为真，也就是说可能有 $\phi_0 \cdots \phi_n$ 全部为真，所以 $\Gamma$ 可满足。

  • $\Gamma$ 不满足当且仅当 $\phi_0 \land \cdots \land \phi_n$ 是矛盾式；

    反证法。由于一个公式只能是或然式、重言式和或然式三种中的一种。当 $\Gamma$ 不满足，如果 $\phi_0 \land \cdots \land \phi_n$ 不是矛盾式，那么他就是或然式或者是重言式，如此一来 $\Gamma$ 是可满足的，与条件矛盾。当 $\phi_0 \land \cdots \land \phi_n$ 是矛盾式，如果 $\Gamma$ 可满足，那么 $\phi_0 \land \cdots \land \phi_n$ 或者是或然式或者是重言式，与条件矛盾。

  • 如果 $\phi$ 是重言式，那么 $\Gamma$ 是可满足的当且仅当 $\Gamma \cup \{\phi\}$ 是可满足的；

    若 $\Gamma$ 是可满足的，那么存在 $\{\phi_0,\cdots,\phi_n\}$ 都是真的，由于 $\phi$ 是重言式，此时 $\{\phi_0,\cdots,\phi_n,\phi\}$ 也是真的，所以 $\Gamma \cup \{\phi\}$ 是可满足的。

    若 $\Gamma \cup \{\phi\}$ 是可满足的，则存在 $\{\phi_0,\cdots,\phi_n,\phi\}$ 都是真的，此时 $\{\phi_0,\cdots,\phi_n\}$ 都是真的，所以 $\Gamma$ 是可满足的。

  • 如果 $\phi_i\;(i \leqslant n)$ 是重言式，那么 $\Gamma$ 是可满足的当且仅当 $\Gamma - \{\phi_i\}$ 是可满足的；

    由 (vii) 可知 $\Gamma - \{\phi_i\}$ 是可满足当且仅当 $\Gamma - \{\phi_i\} \cup \{\phi_i\} = \Gamma$ 是可满足的；

  • 如果 $\phi$ 是矛盾式，那么 $\Gamma \cap \{\phi\}$ 也是不可满足的；

    如果 $\phi$ 是矛盾式，那么 $\{\phi\}$ 不可满足，由习题2.18 的 (ii) 可知 $\Gamma \cap \{\phi\}$ 是不可满足的。

  • 如果 $\phi_i\;(i \leqslant n)$ 是矛盾式，那么 $\Gamma$ 是不可满足的。

    如果 $\phi_i\;(i \leqslant n)$ 是矛盾式，那么 $\Gamma$ 的联合真值表的每一行至少都有一个真值是假，不可能存在真值都为真的行，所以不可满足。

习题 2.19 将下列公式改写为使用波兰学派记法的公式。完成后，不看下列公式，把那些使用波兰学派记法的公式再改写成我们这个语言的公式，然后再和下列公式对照：

  • $p \to q \lor p$
    $CpAqp$

  • $p \to ((p \to q) \to q)$
    $CpCCpqq$

  • $p \land \lnot (\lnot p \to q)$
    $KpNCNpq$

  • $(p \to \lnot p) \land (\lnot p \to p)$
    $KCpNpCNpp$

  • $(p \lor q) \land (\lnot p \land \lnot q)$
    $KApqKNpNq$

  • $\lnot (p \to q) \land \lnot (q \to p)$
    $KNCpqNCqp$

  • $(q \to q) \to p$
    $CCqqp$

  • $q \land \lnot q \to p$
    $CKqNqp$

  • $(p \lor q) \land \lnot q \to p$
    $CKApqNqq$

  • $(q \to \lnot p) \to (p \to \lnot q)$
    $CCqNpCpNq$

  • $(r \to (p \to q)) \to ((r \to p) \to (r \to q))$
    $CCrCpqCCrpCrq$

  • $\lnot p \land \lnot q \to \lnot (p \lor q)$
    $CKNpNqNApq$

  • $\lnot p \lor \lnot q \to \lnot (p \land q)$
    $CANpNqNKpq$

  • $(\lnot p \to \lnot q) \land \lnot ((\lnot p \to q) \to p)$
    $KCNpNqNCCNpqp$

  • $(p \to (q \to r)) \land \lnot ((p \land q) \to (p \lor r))$
    $KCpCqrNCKpqApr$

  • $(p \leftrightarrow q) \to (\lnot p \lor \lnot q)$
    $CEpqANpNq$

  • $(\lnot p \lor q) \to (p \land q \to \lnot q)$
    $CANpqCKpqNq$

  • $(p \leftrightarrow q) \to \lnot q \land \lnot p$
    $CEpqKNqNp$