1.1 命题逻辑

逻辑从已经足够完整、可以判断真假的陈述开始。这个区别看起来简单， 但在整门课里都非常重要：一旦一句话还没有封闭，就不能把它当作命题来处理。

命题与真假值

定义

命题

命题是一个具有确定真假值的陈述。它要么是真的，要么是假的，没有第三种情况。

这个定义的目的不是把逻辑弄得更抽象，而是区分哪些句子已经可以检验， 哪些句子仍然不完整。

例子：

• $2 + 2 = 4$ 是命题。
• 每个偶数都可以被 2 整除 是命题。
• 请打开门。 不是命题，因为它是命令。
• 如果没有指定 $x$，$x + 1 = 3$ 还不是命题。

常见错误

含有自由变量的公式不会自动变成命题

如果一句话的真假仍然依赖未指定的变量，那么它就是开放句，不是完整陈述。 你必须先赋值，或者以后用量词把它绑定起来。

例题

判断哪些句子是命题

考虑以下三句：

1. $7$ 是质数。
2. $x + 1 = 3$。
3. 请关门。

第 1 句是命题，而且是真的。第 2 句不是命题，因为要看 $x$ 取什么值：$x = 2$ 时为真，$x = 0$ 时为假。第 3 句不是命题，因为它是请求，不是主张。相比之下， 在实数范围内，$x^2 + 1 > 0$ 对每个实数 $x$ 都为真，但在给 $x$ 赋值或用量词 绑定以前，它仍然是开放句。

逻辑分析只有在句子足够完整时才能开始。未封闭的句子，不适合直接做真值表分析。

布尔连接词

课程里会反复用到五个连接词：

这些不是普通口语的缩写，而是逻辑语言的基本符号，用来拼出更复杂的陈述。

优先次序只有部分规定：

1. $¬$
2. $∧$ 和 $∨$ 同一层级
3. $→$ 和 $↔$

$∧$ 和 $∨$ 之间没有先后，因此同时出现时必须加括号。下面的例子把这个问题直接展示出来：

例题

先解析，再阅读

字符串 $¬A ∧ B ∨ C$ 有两种可能读法：

$$\neg A \land B \lor C$$

它可以表示 $(¬A ∧ B) ∨ C$，即 $A$ 假且 $B$ 真，或者 $C$ 真；也可以表示 $¬A ∧ (B ∨ C)$，即 $A$ 假并且 $B$、$C$ 至少一个为真。这是两个不同的公式。

如果你想表达别的意思，就一定要明确加括号。

逻辑公式是精确对象。括号不是装饰，而是决定句子真正内容的一部分。

语法、作用域与真值函数

良构公式用递归方式生成。原子命题 $A$ 是公式；如果 $φ$ 是公式，那么 $¬φ$ 也是公式，并且 $¬$ 恰好只有一个运算对象。如果 $φ$、$ψ$ 是公式，那么 $(φ ∧ ψ)$、$(φ ∨ ψ)$、$(φ → ψ)$、$(φ ↔ ψ)$ 都是公式，每个二元连接词恰好 需要两个完整的运算对象。因此 $P ∧ ∨ Q$ 不是公式。

$A → B ∧ ¬C$ 没有歧义：先算 $¬$，再算 $∧$，最后算 $→$， 所以它是 $A → (B ∧ ¬C)$。同样，$¬A ↔ B ∨ C$ 是 $¬A ↔ (B ∨ C)$，因为 $∨$ 在 $↔$ 之前计算。这里的双条件比较 $¬A$ 与 $B ∨ C$ 的真假值，并不是把整个析取式否定。

给原子命题指定 $T$ 或 $F$ 后，每个连接词都能按其直接运算对象的值确定一个 结果；因此同一赋值总是给同一公式同一个真值。这就是公式的 truth function， 而真值表把它的全部输入输出记录下来。

真值表与逻辑等价

当你知道各个命题的真假值之后，就可以计算复合公式的真假。真值表就是用来记录这件事的。

定理

常用等价式

下面这些等价式是基本工具，应该尽量熟记：

$$P → Q \equiv ¬P ∨ Q$$$$P ↔ Q \equiv (P → Q) ∧ (Q → P)$$$$¬(P ∧ Q) \equiv ¬P ∨ ¬Q$$$$¬(P ∨ Q) \equiv ¬P ∧ ¬Q$$$$¬¬P \equiv P$$

这些不是哲学命题，而是真值表恒等式。

例题

用真值表检查蕴含

$P → Q$ 只会在一种情况下为假：$P$ 真而 $Q$ 假。其余情况都为真。

$P$	$Q$	$P → Q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

所以 $P → Q$ 不是说 $P$ 和 $Q$ 都真，而是排除了“前件真、后件假”这种情况。

很多人会把 $P → Q$ 读成因果句。在逻辑里，它不是故事式的因果，而是真值条件。

推理规则

课程里会反复用到几种有效推理模式。

定理

常见推理模式

如果 $P → Q$ 和 $P$ 都真，那么 $Q$ 一定真。这叫 modus ponens。

如果 $P → Q$ 和 $¬Q$ 都真，那么 $¬P$ 一定真。这叫 modus tollens。

如果 $P → Q$ 和 $Q → R$ 都真，那么 $P → R$ 一定真。这叫 hypothetical syllogism。

如果 $P ∨ Q$ 和 $¬P$ 都真，那么 $Q$ 一定真。这叫 disjunctive syllogism。

这些模式之所以重要，是因为它们像合法运算：前提真，结论就一定真。

例题

一条有效的推理链

假设你知道

$$A → B,\qquad B → C,\qquad A.$$

你可以先由第一句和第三句推出 $B$，再由第二句推出 $C$。

所以结论 $C$ 能从前提逻辑地推出。

这是两次使用 modus ponens：先由 $A$ 推出 $B$，再由 $B$ 推出 $C$。

常见错误

不要混淆有效与无效的推理模式

由 $P → Q$ 和 $Q$，你不能推出 $P$。这个谬误叫 affirming the consequent。

由 $P → Q$ 和 $¬P$，你不能推出 $¬Q$。这个谬误叫 denying the antecedent。

否定前件的反模型

对论证 $P → Q$、$¬P$，所以 $¬Q$，取 $P = F$、$Q = T$。因为前件为假， 蕴含式为真；$¬P$ 也为真；但 $¬Q$ 为假。这个赋值同时满足两个前提而否定结论， 所以该论证无效。

把条件翻译成公式

布尔字母代表一个完整命题，连接词则记录完整命题怎样组合。因此，翻译英文 句子要分两步：先说明每个字母代表什么，再按原句的范围选择连接词和括号。

例题

必要条件与充分条件

令 $D$ 表示“这个整数能被 4 整除”，令 $E$ 表示“这个整数是偶数”。 “被 4 整除是成为偶数的充分条件”翻译为 $D → E$。同一个关系也可以说成 “偶数是被 4 整除的必要条件”：只要 $D$ 成立，$E$ 就必须成立。措辞次序改变了， 但箭头仍然从被假定的条件指向必须跟随的条件。

逆命题 $E → D$ 是另一条断言，原句并没有许可它。2 是反例：2 是偶数，却不能 被 4 整除。

因为 $∧$ 和 $∨$ 在课程约定中处于同一层级，$A ∧ B ∨ C$ 有歧义。要表达“$A$ 和 $B$，或者 $C$”，写 $(A ∧ B) ∨ C$；要表达“$A$，并且 $B$ 或 $C$”，写 $A ∧ (B ∨ C)$。两式可能在同一赋值下给出不同真假值，所以必须先确定分组。

有效性究竟问什么

论证由前提和结论组成。当每一种让全部前提为真的赋值也让结论为真时，论证就是 有效的。这是在说公式之间的关系，并不是说这些前提在现实中确实为真。

定理

用被禁止的一行检验有效性

对前提 $P_1, ..., P_n$ 和结论 $Q$，寻找一行：所有 $P_i$ 都真而 $Q$ 为假。 若找到，这一行就是反模型，论证无效；若找不到，论证有效。等价地，公式

$$(P_1 \land \cdots \land P_n) \to Q$$

是永真式。

例题

肯定后件的反模型

以前提 $P → Q$、$Q$ 推出结论 $P$。取 $P = F$、$Q = T$：因为前件为假，$P → Q$ 为真；第二个前提 $Q$ 也为真；但结论 $P$ 为假。因此一行就足以否定有效性。 前提为假的行不能完成这个任务，因为有效性只要求检查所有前提都成立的行。

这也说明逻辑等价与推理有效性不能混为一谈。$φ ≡ ψ$ 表示两个公式每一行都给出 相同真假值；“$φ$，所以 $ψ$”只要求不存在 $φ$ 真而 $ψ$ 假的行。只要 $φ → ψ$ 是永真式，该推理就有效；除非 $ψ → φ$ 也永真，否则逆向推理未必有效。

否定并化简命题

否定作用于整个范围内的命题。要否定“$P$ 且 $Q$”，应写 $¬(P ∧ Q)$，不能直接 写 $¬P ∧ ¬Q$；用德摩根律后才得到等价式 $¬P ∨ ¬Q$。同样，$¬(P → Q)$ 只在 蕴含式唯一为假的那一行成立，所以

$$¬(P → Q) \equiv P \land ¬Q.$$

例题

改写被否定的蕴含式

先用 $A → B ≡ ¬A ∨ B$，再逐步使用德摩根律和双重否定：

$$¬(A → B) \equiv ¬(¬A ∨ B) \equiv ¬¬A \land ¬B \equiv A \land ¬B.$$

最后的公式正好说明前件真而后件假，也就是蕴含式失败的条件。

这种改写是有控制的化简过程：先移除蕴含，再用德摩根律把否定推进合取或析取， 最后消去双重否定。每一步都是等价变形，所以前后公式定义同一个真值函数。

从语法到意义的检查

写好公式以后，还要分别检查它的语法和意义。语法检查问：每个连接词的两边是否是 完整公式，括号是否配对，优先次序是否造成了预期的结构。意义检查问：在一个指定的 真假指派下，是否按照连接词的定义计算出了唯一结果。前一个问题防止把开放句当命题， 后一个问题防止把口语中的“如果”误读成因果关系。

例题

同一组原子命题的不同结构

令 $A$ 表示“今天下雨”，$B$ 表示“地面湿”，$C$ 表示“我带伞”。公式 $(A → B) ∧ C$ 要求两个部分都真；公式 $A → (B ∧ C)$ 则只在下雨时要求地面湿并且 带伞。取 $A = F,\,B = F,\,C = T$，前一个公式为真，后一个公式也为真；再取 $A = T,\,B = T,\,C = F$，前一个为假而后一个也为假。要找到它们确实不同的赋值， 取 $A = F,\,B = T,\,C = F$：前一个仍为假，后一个为真。这个过程显示括号决定的是 连接词作用范围，而不是表面上的符号排列。

如果题目问“是否能从前提推出结论”，应把前提和结论分开写，再寻找全部前提真而结论 假的行。若题目问“两个公式是否等价”，则必须比较两条完整的最终列；只找到一条相同 的行没有证明作用。把问题类型先辨认清楚，可以避免用等价证明代替有效性证明。

蕴含、反模型与证明方向

蕴含不宣称前件为真，也不表示因果关系。它的真值条件恰好排除前件真而后件假的赋值。逆命题反转箭头；逆否命题还同时否定两端。

逆否命题的推导

$P\to Q$ 等价于 $\neg P\lor Q$。逆否命题 $\neg Q\to\neg P$ 等价于 $\neg\neg Q\lor\neg P$，即 $Q\lor\neg P$；交换律又给出原来的析取式。因此 两者在每个赋值下都等价。

例题

区分逆命题与逆否命题

令 $P$ 表示“正在下雨”，$Q$ 表示“地面是湿的”。逆命题 $Q\to P$ 说地面湿就一定 下雨；洒水器可以使地面湿而不下雨，所以这是另一条可能失败的断言。逆否命题 $\neg Q\to\neg P$ 说地面干就没有下雨，并且与原蕴含式等价。

Modus tollens 要检查两个前提

假设 $P\to Q$ 和 $\neg Q$ 都真。第二个前提迫使 $Q=F$；若 $P=T$，第一个 前提便为假。因此 $P=F$，即 $\neg P$。排除 $(T,F)$ 这一行的是第一个前提； 检验有效性时必须保留每个前提。

快速检查

思考检查

按课程约定，$¬A ∧ B ∨ C$ 是否没有歧义？如果有，请写出两种括号方式。

记住 $¬$ 最先，而 $∧$ 和 $∨$ 处于同一优先层级。

解答 · 答案

它有歧义。两种括号方式是 $(¬A ∧ B) ∨ C$ 和 $¬A ∧ (B ∨ C)$。

思考检查

$P → Q$ 和 $¬P ∨ Q$、$P ∧ Q$，哪个等价？

看蕴含的真假条件。

解答 · 答案

$¬P ∨ Q$ 和 $P → Q$ 等价。

思考检查

推理 $P → Q$、$Q$，所以 $P$ 有效吗？

试想 $P$ 其实为假的情况。

解答 · 答案

无效。这个谬误叫 affirming the consequent。

探索真值条件

用互动表试验你自己写出来的公式。

下一步：计算真值表

继续阅读 1.2 真值表与逻辑等价，把本节的语法和真值规则组织成检验公式的完整方法。