2.1 命题与逻辑联结词

第 1 章的许多定义中都出现了“且”“或”“非”。例如，当一个元素既属于 $A$ 且属于 $B$ 时，它属于 $A\cap B$。当时我们使用的是这些词的日常含义；从本章开始，我们要把它们变成含义精确、可以计算的逻辑语言。

本节先认识逻辑中最小的单位——能够判断真假的陈述，再学习如何组合多个陈述。

学完本节后，你将能够：

• 区分命题、问题、命令与缺少信息的语句；

• 用 $p$、$q$ 等字母为命题命名；

• 读懂并计算否定、合取、析取与异或；

• 使用括号和运算优先级消除歧义。

命题必须作出一个真假确定的陈述

命题（proposition）是具有唯一确定真值的陈述句。真值只有两种：真，记作 $\mathrm{T}$；假，记作 $\mathrm{F}$。

先看两个例子：

冒号前的字母是命题的简短名称。命题 $p$ 为真，命题 $q$ 为假。错误的陈述仍然可以是命题，因为“是不是命题”取决于真值是否已经确定，而不取决于真值是否为真。

判断一句话时，按顺序问两个问题：

1. 它是在陈述事实，还是在提问或发出命令？

2. 已有信息是否足以确定唯一真值？

下面的比较说明为什么两个问题都不可缺少：

最后一句叫作开放语句（open statement）。若把 $x$ 替换成 $6$，它就成为真命题 $6>4$；若把 $x$ 替换成 $2$，它就成为假命题 $2>4$。符号 $x$ 是变量（variable），也就是可以接收不同取值的占位符。

开放语句通常可以通过两种方式变成命题：

• 给每个变量指定具体取值；

• 用“对所有”或“存在”等量词说明要怎样考虑变量。

第 2.3 节会从头讲解量词。本节只需抓住一个边界：如果尚未指定的变量能够改变真假，语句就还没有唯一真值。

在调查游戏中，不要根据一句话“听起来是否可信”来分类。先判断它是否在陈述事实，再检查所需信息是否完整。证物“$10<3$”虽然为假，仍应放入命题档案。

从原子命题到复合命题

把一个命题当作不可继续拆分的完整陈述时，它叫作原子命题（atomic proposition）。例如，可以令

逻辑联结词（logical connective）用来修改或组合命题，组合结果叫作复合命题（compound proposition）。复合命题的真值完全由各部分的真值和使用的联结词决定。

否定会翻转一个真值

$p$ 的否定（negation）记作 $\neg p$，读作“非 $p$”。它会翻转真值：

若 $p$ 表示“传感器已启动”，那么 $\neg p$ 表示“传感器没有启动”。否定作用于一个完整命题。当被否定部分较复杂时，要用括号标明范围：

表示“并非 $p$ 与 $q$ 同时为真”。

合取要求两边同时成立

$p$ 与 $q$ 的合取（conjunction）记作

读作“$p$ 且 $q$”。只有两部分都为真时，合取才为真。

若 $p$ 表示“门禁卡有效”，$q$ 表示“密码正确”，那么同时要求两项检查通过的访问规则就是 $p\land q$。任何一项失败，整个合取都为假。

析取要求至少一边成立

$p$ 与 $q$ 的析取（disjunction）记作

读作“$p$ 或 $q$”。标准数学逻辑中的“或”是兼或：$p$ 为真、$q$ 为真或二者都为真时，析取都为真；只有两边都为假时，结果才为假。

这与第 1 章的并集完全衔接。元素属于 $A\cup B$ 的条件是属于 $A$ 或属于 $B$，交集中的元素也包括在内。

日常语言有时会用“或”表示“只能二选一”。这种运算叫作异或（exclusive disjunction，简称 XOR），本课程记作 $p\oplus q$。只有两个真值不同时，异或才为真。

表格列出了 $p$、$q$ 的全部四种取值。第 2.2 节会讲解怎样主动构造这样的真值表，而不只是读取现成表格。

从最内层开始计算复合命题

假设 $p=\mathrm{T}$ 且 $q=\mathrm{F}$，计算

把计算拆成小步骤：

1. 因为 $q=\mathrm{F}$，否定后得到 $\neg q=\mathrm{T}$。

2. $p$ 与 $q$ 中至少一项为真，所以 $p\lor q=\mathrm{T}$。

3. 最外层变成 $\mathrm{T}\land\mathrm{T}$，因此完整表达式为真。

括号用来说明哪些部分构成一个整体。省略括号时，本课程采用以下优先级：

因此，$\neg p\land q$ 表示 $(\neg p)\land q$，而不是 $\neg(p\land q)$。即使优先级能够确定含义，只要读者可能犹豫，也应主动加上括号。清楚的符号表达本身就是正确推理的一部分。

可以使用下面的固定计算流程：

1. 写出每个原子命题的真值；

2. 先计算最内层括号；

3. 应用否定；

4. 依次计算合取和析取；

5. 写出最终真值，并保留中间结果以便检查。

电路台把真假变成可以观察的信号。不要只测试当前亮起的一组输入；必须检查全部四种输入世界。只有四位输出指纹处处相同，两个电路的行为才一致。第 2.2 节会把这个观察正式定义为逻辑等价。

通向下一节

现在，只要有人给出 $p$、$q$ 的真值，我们就能计算复合命题。但怎样证明一条规则对所有可能输入都成立？第 2.2 节会把全部可能世界组织成真值表，再用真值表解释蕴含和逻辑等价。