《符号逻辑讲义》笔记

第二章 命题联结词与真值表方法

2.1 联结词与复合句

命题联结词是带空格的表达式，使得以陈述句填入这些空格的结果总是陈述句。可以说是陈述句集合上的 $n$ 元函数，一旦给定有序的 $n$ 个陈述句作为其自变量的取值，该函数的值是个唯一的陈述句。

复合句是用到联结词的陈述句。不是复合句的陈述句叫简单句。复合句中被联结的句子就是它的真子句，简单句不是用联结词联结某些句子形成的，从而没有真子句。

设 $\phi$ 和 $\psi$ 都是完整的句子。$\psi$ 是 $\phi$ 的真子句，如果以空格替换 $\phi$ 中的 $\psi$，其结果是一个联结词；$\psi$ 是 $\phi$ 的子句，如果 $\psi$ 是 $\phi$ 的真子句或 $\psi = \phi$。代入联结词的定义，说 $\psi$ 是 $\phi$ 的真子句，如果以陈述句代替 $\phi$ 中的 $\psi$ 的结果总是陈述句。

复合句的子句可一个是简单句，也可以是复合句。

一个联结词及其在某复合句中所处的一个位置称为其在句中的一个出现（这里把出现用作名词）。一个联结词被称为一个复合句的主联结词，如果它在该句中的某个出现不是在该句中的任何真子句中，且不是由多元联结词用句子填入部分空格得到的联结词。一个没有歧义的复合句，都有唯一的主联结词。

设 $\psi$ 是 $\phi$ 的真子句。$\psi$ 被称为 $\phi$ 的直接子句，如果 $\psi$ 在 $\phi$ 中的某个出现不是在 $\phi$ 的任何其他真子句中的出现。简单地说，$\phi$ 的直接子句就是 $\phi$ 的主联结词联结的那些句子。

2.2 真值函数联结词和非真值函数联结词

对任意的联结词，如果以它为主联结词的复合句的真值完全由该句的直接子句的真值来决定，那么这个联结词就是真值函数联结词。如果一个联结词不是真值函数联结词，就是一个非真值函数联结词。

通过思考“真值函数”这个词理解概念的意义，真值函数的可以理解为把真值映射到唯一确定的一个真值，测试一次输入真得到输出结果真，对于一个真值函数，我们就可以期待每次输入真都是输出真。

要说明一个联结词不是真值函数联结词，可以分别填入两个真值相同的句子，若得到的两个复合句真值不同，则一定是非真值函数联结词。

2.3 符号化

常用的真值函数联结词（$\sim$ 这个符号写 $\to \sim p$ 时空格不对，所以换成 $\lnot$，这个是这样 $\to \lnot p$）

名称	符号	波兰学派记法	对应
否定	$\lnot$	N	并非，并不，不……
合取	$\land$	K	并且，但是，不是-而是……
析取	$\lor$	A	或，要么-要么，不是-就是，除非……
蕴含	$\to$	C	如果-那么，否则-除非……
等值	$\leftrightarrow$	E	当且仅当，等价于……

相对于真值函数联结词简单的句子，是指那些没有主联结词或没有真值函数联结词的句子，包括简单句（没有使用联结词）和以非真值函数联结词为主联结词得句子以及{TODO: 由量词决定了其基本结构得句子}等等。{TODO: 上述说明只是一种直观说法，不是定义}。

“只有 $p$ 才 $q$”的符号化结果是“$\lnot p \to \lnot q$”或“$q \to p$”。可以理解为“有 $p$ 不一定有 $q$，但有 $q$ 一定有 $p$”。

“$p$ 除非 $q$”的符号化结果是“$p \wedge q$”或“$\lnot q \to p$”。可以说成“$p$ 仅当非 $q$”或“要么 $p$ 要么 $q$”。

2.4 命题逻辑的基本语法

形式语言 $\mathscr{L}_0$。$\mathscr{L}$ 是花体的 $L$，$\LaTeX$ 代码是 \mathscr{L}，应该是取自 Language 的首字母。

• 初始符号
  • 命题变号：$p_0, p_1, p_2, \cdots$；
  • 联结词：$\lnot,\vee,\wedge,\to,\leftrightarrow$；
  • 左右括号：$($ 和 $)$。
• $\mathscr{L}_0$-公式是由下列形成规则形成的符号串：
  • $\mathscr{L}_0$ 的所有命题变号都是 $\mathscr{L}_0$-公式；
  • 如果 $\phi$ 是 $\mathscr{L}_0$-公式，则 $\lnot \phi$ 也是 $\mathscr{L}_0$-公式；
  • 如果 $\phi$ 和 $\psi$ 是 $\mathscr{L}_0$-公式，则 $(\phi\vee\psi)$、$(\phi\wedge\psi)$、$(\phi\to\psi)$ 和 $(\phi\leftrightarrow\psi)$ 都是 $\mathscr{L}_0$-公式；
  • 只有这些是 $\mathscr{L}_0$-公式。

公式的子公式是出现在该公式中的公式（包括自己）。如果 $\psi$ 是 $\phi$ 的子公式，且 $\psi \neq \phi$，那么 $\psi$ 是 $\phi$ 的真子公式。一个公式的主联结词是该公式构造过程的最后一步中使用的那个联结词，而它的直接子公式就是这一步中主联结词所联结的公式。

根据主联结词对公式进行分类：

• 命题变号称为 $\mathscr{L}_0$-原子公式；
• 形如 $~\phi$ 的公式称为否定式；
• 形如 $(\phi \vee \psi)$ 的公式称为析取式，$\phi$ 和 $\psi$ 称为它的析取支；
• 形如 $(\phi \wedge \psi)$ 的公式称为合取式，$\phi$ 和 $\psi$ 称为它的合取支；
• 形如 $(\phi \to \psi)$ 的公式称为蕴含式或条件句，$\phi$ 称为它的前件，$psi$ 称为它的 后件；
• 形如 $(\phi \leftrightarrow \psi)$ 称为等值式，亦称双向蕴含式或双向条件句。

2.5 真值表和真值的计算

• 否定式为真当且仅当它否定的公式是假的；
• 合取式为真当且仅当它的合取支都是真的；
• 析取式为真当且仅当它的析取支中至少一个是真的；
• 蕴含式为真当且仅当它的前件是假的或后件是真的；
• 等值式为真当且仅当它的两个直接子公式的真值相同。

2.6 若干基本予以概念的真值表刻画

• 论说形式的有效性

  • 在一个论说形式的真值表中，前提都真而结论假的每一行，都成为该论说的反例。
  • 对任何一个论说形式，如果其真值表的任何一行都不是该论说形式的反例，那么这个论说形式是有效的；否则是无效的。

• 重言蕴含

  设 $\phi_1,\cdots,\phi_n$ 和 $\psi$ 为任意公式。

  • $\{\phi_1,\cdots,\phi_n\}$ 重言蕴含 $\psi$ 当且仅当 $\phi_1,\cdots,\phi_n$ 与 $\psi$ 的联合真值表中，没有一行是 $\phi_1,\cdots,\phi_n$ 都真而 $\psi$ 假。
  • $\psi$ 是 $\{\phi_1,\cdots,\phi_n\}$ 的重言后承 当且仅当 $\{\phi_1,\cdots,\phi_n\}$ 重言蕴含 $\psi$。

  重言蕴含和论说形式有效是等价的。

• 重言等值

  • $\phi$ 与 $\psi$ 重言等值 当且仅当 $\phi$ 与 $psi$ 的联合真值表的任意一行中，$\phi$ 与 $\psi$ 都有相同的真值。等价于 $\phi$ 与 $\psi$ 相互重言蕴含。

• 可满足性

  • 设 $\Gamma$ 为任意有穷的公式集合。$\Gamma$ 是可满足的当且仅当 $\Gamma$ 中公式的联合真值表中存在某一行，该行里 $\Gamma$ 中的公式的真值都是 $T$。$\Gamma$ 是不可满足的当且仅当它不是可满足的。
  • 设 $\phi$ 为任意公式。$\phi$ 是可满足的当且仅当 $\{\phi\}$ 是可满足的。$phi$ 是不可满足的当且仅当 $\{\phi\}$ 不是可满足的。

根据公式在其真值表中的真值情况，将公式非为：

• 重言式：公式的真值表每一行都是真
• 矛盾式：公式的真值表每一行都是假
• 或然式：公式的真值表一些行真一些行假

重言蕴含、重言等值和可满足性的对象分别是论说、两个公式、公式的集合。一个论说由一组公式的集合作为前提和一个论说作为结论。重言式、矛盾式、或然式的对象是一个公式。

2.7 简化真值表方法

看上去就像反证法。例如判别一个论说形式是否有效。

• 假设论说形式的前提都真而结论假；
• 据此推算它们的直接子公式的真值，进而根据子公式的真值算出它们的直接子公式的真值；
• 若遇到某个公式既真又假，就可以判定该论说形式有效；
• 如果没有遇到这种情况，可以判定该论说形式是无效的。

也可用来判断是否是重言式、矛盾式、或然式。

第三章 命题逻辑的基本概念

3.1 对象语言里的符号和公式

{TODO: 符号的选择是任意的，我们关注的是对象语言的意义。语言学？}

3.2 真值指派和公式的真值

我们把 $\mathscr{L}_0$ 的所有命题变号的集合记作 $\textbf{Pr}$，因此 $\textbf{Pr}$ 是一个无穷集。一个真值指派（或赋值）是从 $\textbf{Pr}$ 到 $\{\T,\F\}$ 的函数 $\sigma$，它对每个命题变号 $p$ 指派一个真值 $\sigma(p)$。由于定义域是无穷集，真值指派也有无穷多个。

（真理定义）：对所有的 $\mathscr{L}_0$-公式，我们用 $\phi^\sigma$ 表示 $\phi$ 在 $\sigma$ 下的值。$\phi^\sigma$ 递归地定义如下：

$$\begin{aligned} p_n^\sigma = \T &\quad\text{iff}\quad \sigma(p_n) = \T\ (n \geqslant 0)\\ (\lnot\psi)^\sigma = \T &\quad\text{iff}\quad \psi^\sigma \neq \T\ (\text{即 } \psi^\sigma = \F)\\ (\psi \lor \chi)^\sigma = \T &\quad\text{iff}\quad \text{或者 }\psi^\sigma = \T \text{ 或者 }\chi^\sigma = \T\\ (\psi \land \chi)^\sigma = \T &\quad\text{iff}\quad \psi^\sigma = \T \text{ 并且 }\chi^\sigma = \T\\ (\psi \to \chi)^\sigma = \T &\quad\text{iff}\quad \text{或者 }\psi^\sigma \neq \T \text{ 或者 }\chi^\sigma = \T\\ (\psi \leftrightarrow \chi)^\sigma = \T &\quad\text{iff}\quad \psi^\sigma = \chi^\sigma\\ \end{aligned}$$

令 $\Gamma$ 为任意 $\mathscr{L}_0$-公式集（可以是无穷集），并令 $\sigma$ 为任意真值指派。$\sigma$ 满足 $\Gamma$（符号表示：$\sigma \vDash \Gamma$ 当且仅当对每个 $\phi \in \Gamma$，$\phi^\sigma = \T$。我们用 $\sigma \vDash \phi$ 表示 $\sigma \vDash \{\phi\}$，即 $\phi^\sigma = \T$，并用 $\sigma \nvDash \Gamma$ 和 $\sigma \nvDash \phi$ 分别表示 $\sigma \vDash \Gamma$ 和 $\sigma \vDash \phi$ 不成立。

对于每个真值指派 $\sigma$，都有 $\sigma \vDash \varnothing$。这是因为，既然 $\varnothing$ 是空集，那么就不存在 $\varnothing$ 中的公式 $\phi$ 使得 $\sigma \nvDash \varnothing$。

3.3 重言蕴含、重言等值与可满足性

• 重言蕴含

  令 $\Gamma$ 为任意 $\mathscr{L}_0$-公式集（可以是无穷集）并且 $\phi$ 为任意 $\mathscr{L}_0$-公式。$\Gamma$ 重言蕴含 $\phi$（符号表示 $\Gamma \vDash_0 \phi$）当且仅当对每一个真值指派 $\sigma$，如果 $\sigma \vDash \Gamma$ 则 $\sigma \vDash \phi$。$\phi$ 是 $\Gamma$ 的重言后承当且仅当 $\Gamma \vDash_0 \phi$。

  当 $\Delta = \{\phi_1,\ldots,\phi_n\}$ 时，可以用 $\phi_1,\ldots,\phi_n \vDash_0 \phi$ 表示 $\Delta \vDash_0 \phi$，用 $\Gamma,\phi_1,\ldots,\phi_n \vDash_0 \phi$ 表示 $\Gamma \cup \Delta \vDash_0 \phi$。当 $\Delta = \varnothing$ 时，我们用 $\vDash_0 \phi$ 表示，此时，因为对于任意真值指派 $\sigma$ 都有 $\sigma \vDash \varnothing$，所以也都有 $\sigma \vDash \phi$。

• 重言等值

  $\mathscr{L}_0$-公式 $\phi$ 和 $\psi$ 重言等值 当且仅当对每个真值指派 $\sigma$，$\phi^\sigma = \psi^\sigma$。

• 可满足性

  令 $\Gamma$ 为任意 $\mathscr{L}_0$-公式集（可以是无穷集），$\phi$ 为任意 $\mathscr{L}_0$-公式。$\Gamma$ 是可满足的当且仅当存在一个真值指派 $\sigma$ 使得 $\sigma \vDash \Gamma$；$\phi$ 是可满足的当且仅当 $\{\phi\}$ 是可满足的。$\Gamma$（或 $\phi$）是不可满足的当且仅当它不是可满足的。

3.4 重言式、矛盾式与或然式

对任意 $\mathscr{L}_0$-公式 $\phi$，$\phi$ 是

• 重言式：当且仅当对每一个真值指派 $\sigma$，$\sigma \vDash \phi$；
• 矛盾式：当且仅当对每一个真值指派 $\sigma$，$\sigma \nvDash \phi$；
• 或然式：当且仅当存在一个真值指派 $\sigma$ 使得 $\sigma \vDash \phi$，并且存在一个真值指派 $\sigma'$，使得 $\sigma' \nvDash \phi$。