命题逻辑的语义学
摘要
在本课程中，我们将学习命题逻辑的语义学，特别是表达式的真值分配以及如何通过逻辑连接词从一个表达式传播到另一个表达式。我们将引入真值表的概念，并展示否定、析取、合取、蕴涵、双向蕴涵和异或等派生连接词的真值表。此外，我们还会介绍关于一组原子表达式的分配的定义，并解释如何自然地扩展到从该集合构建的所有表达式。最后，我们将定义有效、可满足和不可满足的表达式，并展示一些重言式和矛盾式的例子。然而，我们认识到，对于复杂表达式计算真值表可能效率低下，因此我们提到寻找解决有效性或可满足性问题的替代方法。
学习目标：
在本课程结束后，学生将能够
- 解释命题逻辑的语义学
- 使用真值表表示命题逻辑中表达式的真值分配
- 建模一个带有分配的命题逻辑表达式
- 应用命题逻辑的语义规则，以确定表达式是否为重言式、矛盾或偶然式
目录
关于真值分配
命题逻辑连接词的语义学
命题逻辑中的分配
命题逻辑中的模型
命题逻辑语义学中潜伏的效率问题
关于真值分配
我们之前回顾了 命题逻辑的句法 和 演绎系统。虽然这些帮助我们回顾了 如何从一个表达式推导出另一个表达式，但并未涉及到真值分配的问题。由于我们已经讲完了关于命题逻辑中的演绎技术，现在我们将开始学习命题逻辑的语义学，探讨真值分配如何从一个表达式传播到另一个表达式。
命题逻辑连接词的语义学
逻辑连接词的语义学通过真值表引入，因为它们提供了一种简单有序的方法来表示表达式的所有可能分配。
联接否定的真值表
首先，我们将从最基本的连接词开始，即联接否定。其真值表如下所示：
| \alpha | \beta | (\alpha\downarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
真值 “1” 和 “0” 分别对应 “真” 和 “假”。真值表中的每一行代表表达式（或原子表达式）中的变量可能的一个分配。类似地，形成这些变量的表达式所在的每一列都有可能的分配结果。因此，这张表的解释告诉我们，\alpha\downarrow\beta 只有当 \alpha 和 \beta 都为假时才为真，在其他情况下为假。因此，连接词 \downarrow 被称为 联接否定。
派生连接词的真值表
基于联接否定的语义，我们可以通过其定义推导出其他连接词的语义。它们是：
| 否定： | \neg \alpha | := | (\alpha\downarrow\alpha) |
| 析取： | (\alpha \vee \beta) | := | \neg(\alpha\downarrow\beta) |
| 合取： | (\alpha \wedge \beta) | := | \neg(\neg\alpha\vee \neg\beta) |
| 蕴涵： | (\alpha \rightarrow \beta) | := | (\neg\alpha\vee \beta) |
| 双向蕴涵： | (\alpha \leftrightarrow \beta) | := | ((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha)) |
| 异或： | (\alpha \underline{\vee} \beta) | := | \neg(\alpha\leftrightarrow \beta) |
基于这些定义，我们可以计算其他连接词的真值表：
否定
| \alpha | \neg \alpha |
| 0 | 1 |
| 1 | 0 |
因此，否定连接词具有反转其作用对象的真值的特性。
析取
| \alpha | \beta | (\alpha\vee\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
因此，两表达式的析取（或简单称为“析取”）在至少一个表达式为真时为真，而当两者都为假时为假。
合取
| \alpha | \beta | (\alpha\wedge\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
因此，两表达式的合取仅在两者同时为真时为真，在其他情况下为假。因此，一个适当的名称也可以是“联合断言”。
蕴涵
| \alpha | \beta | (\alpha\rightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
因此，蕴涵的真值表总结了这样的概念：一个真命题只能蕴涵另一个真命题，而一个假命题可以蕴涵任何命题。
双向蕴涵
| \alpha | \beta | (\alpha\leftrightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
双向蕴涵形成一个真命题当且仅当组成它的两个命题具有相同的真值，在其他情况下为假。
异或
| \alpha | \beta | (\alpha\underline{\vee}\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
异或在且仅在两个命题中只有一个为真时为真，在其他情况下为假。
命题逻辑中的分配
根据之前的描述，我们对分配有了一个简单的概念；然而，为了理解我们将要探讨的内容，我们需要一个更精确的定义。如果 S=\{A_1, A_2, \cdots, A_n\} 是一个原子命题的集合，并且 \mathcal{F}(S) 是从该集合构建的所有命题的集合，那么定义如下：
定义： 一个在 S 上的 分配 是一个函数 \mathcal{A}: S \longrightarrow \{0,1\}
换句话说，在 S 上的分配为 S 中的每个原子命题赋予一个真值。在 S 上的分配 \mathcal{A} 自然地扩展到 \mathcal{F}(S) 的所有元素。如果我们有一个表达式 F\in \mathcal{F}(S)，那么在 S 上的分配 \mathcal{A} 对应于真值表中的唯一一行，并且 \mathcal{A}(F) 表示该行中 F 的真值。
一个在 S 上的分配 \mathcal{A} 也可以扩展到某些不在 \mathcal{F}(S) 中的表达式。如果 F_0 是一个不在 \mathcal{F}(S) 中的表达式，并且 S_0 是 F_0 的原子子公式的集合，那么如果所有在 S\cup S_0 上的扩展分配都为 F_0 赋予相同的值，那么定义 \mathcal{A}(F_0) 为该值。
例子：如果 A 和 B 是原子命题，并且在 \{A,B\} 上的分配 \mathcal{A} 通过 \mathcal{A}(A)=1 和 \mathcal{A}(B)=0 定义，那么我们将有：
\mathcal{A}(A\wedge B)=0 和 \mathcal{A}(A\vee B)=1
尽管没有为变量 C 确定分配，但我们可以说：
\mathcal{A}(A\wedge (C\vee \neg C))=1 和 \mathcal{A}(B\vee (C\wedge \neg C))=0
这发生在后两个表达式中，因为无论如何分配 C，总会有
\mathcal{A}(C\vee\neg C)=1 和 \mathcal{A}(C\wedge\neg C)=0
我们可以通过计算其真值表快速检查这些情况。
| C | \neg C | (C\wedge \neg C) | (C \vee \neg C) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
■ 例子结束
命题逻辑中的模型
考虑一个在表达式集合S 上的分配 \mathcal{A}。如果 F\in S 是使得 \mathcal{A}(F)=1 的表达式，则称分配 \mathcal{A} 为模型，或称 F 是由分配 \mathcal{A} 支持的，并通过写作表示
\mathcal{A}\models F。
基于此，我们提出以下定义：
定义： 如果一个表达式在任何分配下都成立，则称其为 有效。如果 F 有效，则写作 \models F 。有效表达式也称为 重言式。
例子：我们已经看到的表达式 (C\vee \neg C) 是一个 重言式。
■ 例子结束
定义： 如果一个表达式被某个分配支持，则称其为 可满足。可满足但不是重言式的表达式称为 偶然式。
定义： 如果一个表达式在任何分配下都不成立，则称其为 不可满足。不可满足的表达式称为 矛盾式。如果 F 是一个矛盾式，则写作 \not\models F 。
例子：我们已经看到的表达式 (C\wedge \neg C) 是一个 矛盾式。
■ 例子结束
重言式与矛盾式的例子
假设我们想要查看一个表达式是否有效。这就是我们在命题逻辑语义学中提出的判定问题。判定问题是任何给定输入后，结果为“是”或“否”的问题。如果给我们一个表达式 F 并问它是否有效，那么我们面临的是一个称为 有效性问题 的判定问题。同样地，如果问它是否可满足，那么我们面临的是一个 可满足性问题。在命题逻辑中，真值表提供了一个系统的方法来解决这些判定问题：如果 F 的所有可能真值都是“1”，则 F 是有效的；如果只有一些是“1”，则它是可满足的；最后，如果所有都是“0”，则它是不可满足的。
例子：考虑表达式 ((A\wedge (A \rightarrow B)) \rightarrow B)。为了确定该表达式是有效、可满足还是矛盾的，我们计算其真值表。
| A | B | (A\rightarrow B) | (A\wedge(A\rightarrow B)) | ((A\wedge(A\rightarrow B))\rightarrow B) |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
因此，我们看到 ((A\wedge(A\rightarrow B))\rightarrow B) 对所有可能的分配都为“1”，因此表达式是一个重言式。
■ 例子结束
例子：现在我们考虑表达式 (((A\rightarrow B)\rightarrow A)\wedge \neg A)。真值表的计算结果如下所示：
| A | B | (A\rightarrow B) | ((A\rightarrow B)\rightarrow A) | \neg A | (((A\rightarrow B)\rightarrow A)\wedge \neg A) |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
因此，结果是一个矛盾。
■ 例子结束
命题逻辑语义学中潜伏的效率问题
理论上，我们可以通过计算真值表来确定一个表达式是有效、偶然还是不可满足的，这不算特别困难；然而，这种易执行性是以效率为代价的。如果我们有一个由 n 个原子命题组成的表达式 F，那么我们需要计算一个有 2^n 行的真值表；例如，如果 F 是由 23 个原子命题组成的，那么其真值表将有 8,388,608 行需要计算。以这种方式进行操作虽然是机械且易于执行的，但随着表达式的复杂性增加，计算很快就会变得不可行。因此，我们的未来目标之一是找到一种不需要计算真值表的方法来解决有效性或可满足性问题。寻找这些方法是任何逻辑的核心问题之一。