数理逻辑 · 命题演算
教材：辛运帏《离散数学》(2014 版) · 自考 02324 · 建议学时 10
本章是全书的地基：先搞懂「什么是命题」「五个联结词怎么用」，后面第 2 章的推理、第 3 章的谓词逻辑都建立在这套符号系统上。命题符号化是最关键、也最常考的能力。
对照考纲，知道每个知识点学到什么程度、考到哪个层次：
| 考核内容 | 层次 | 要掌握到什么程度 |
|---|---|---|
| 命题、联结词的概念 | 领会 | 能判别是否为命题、给真值，会用联结词构造复合命题 |
| 命题符号化 | 领会 | 自然语言 → 符号，注意连接词的多义性 |
| 命题公式、重言式 / 矛盾式 / 可满足式 | 领会 | 会正确识别和判别 |
| 真值表构造、等值性判断 | 简单应用 | 能画真值表，用真值表证两个公式等价 |
| 命题定律等值演算 | 简单应用 | 熟记常用定律，熟练做等价变换 |
| 蕴涵式及其证明 | 简单应用 | 会用三种方法证 P⇒Q |
| 联结词完备集 | 领会 | 了解概念，知道最小完备集有哪些 |
命题：具有唯一真值的陈述句。
真值：为真记 T(或 1)，为假记 F(或 0)。真命题 / 假命题按真值区分。
判别命题只有两个条件：① 是陈述句；② 有唯一真值。真值唯一是灵魂——「x+1=2」「他说的话」这类真值随条件变化的语句不是命题；不知道答案但真值唯一(如「宇宙中有类似地球的生命体」)是命题。
疑问句、感叹句、祈使句都不是命题；悖论(如「我正在说谎」)也不是命题——它推出自相矛盾的结论，真值不唯一。
由原子命题经联结词连成的命题叫复合命题。数理逻辑只有这五个，含义必须精确、确定，不像自然语言那样有歧义。
| 联结词 | 名称 | 记法 | 读法 | 何时为真 | 对称性 |
|---|---|---|---|---|---|
| ¬ | 否定 | ¬P | 非 P | P 为假时 | — |
| ∧ | 合取 | P∧Q | P 并且 Q | P、Q 同为真 | 对称 |
| ∨ | 析取 | P∨Q | P 或者 Q | 至少一个为真 | 对称 |
| → | 条件 | P→Q | 如果 P 那么 Q | 仅当 P 真 Q 假时为假 | 不对称 |
| ↔ | 双条件 | P↔Q | P 当且仅当 Q | P、Q 同真值 | 对称 |
| P | ¬P |
|---|---|
| T | F |
| F | T |
自然语言对应：既…又…、不但…而且…、虽然…但是…、一面…一面…。
「与」「和」连接的是并列主语时不表示合取——「我与王强是同学」只是一个原子命题，不是 P∧Q。
| P | Q | P∧Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
注意：这里的「或」是相容或(两者可同时成立)。
自然语言的「或」有时表示相斥(两者不能同时成立，如「去美国或去欧洲」)，这种不能写成 P∨Q，要用异或：(P∧¬Q)∨(¬P∧Q)。
| P | Q | P∨Q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
只记一条：P 真且 Q 假时才为假。前件为假时，不管后件如何，整个命题为真(叫「空真」/vacuous truth)。
① 不对称：P→Q 与 Q→P 含义完全不同，位置不能换。
② 前件、后件语义上可以毫无关联——「如果雪是黑的，则房间里有 20 张桌子」是合法命题，真值只看真假不看内容。
| P | Q | P→Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
P、Q 真值相同时为真。即 P↔Q ⇔ (P→Q)∧(Q→P)，对称。英文记作 iff(if and only if)。
| P | Q | P↔Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
| 自然语言 | 符号化 | 说明 |
|---|---|---|
| 「如果 P，那么 Q」「因为 P，所以 Q」 | P→Q | P 是 Q 的充分条件 |
| 「只有 Q，才 P」「P 仅当 Q」 | P→Q | 方向别反：Q 是 P 的必要条件 |
| 「只要 P，就 Q」 | P→Q | 同充分条件 |
| 「除非 Q，否则不 P」 | ¬Q→¬P ⇔ P→Q | 「除非」用逆否变形 |
| 「P 当且仅当 Q」 | P↔Q | 充要条件 |
「如果今天不下雨，我就去公园」：设 P＝今天下雨，Q＝我去公园 → ¬P→Q。
「只有今天是星期一，明天才是星期二」：设 P＝今天是星期一，Q＝明天是星期二。「只有 Q 才 P」是 Q→P，即 Q→P。与之对照，「若今天是星期一则明天是星期二」才是 P→Q——充分与必要条件方向相反，是最高频陷阱。
设 P：今天下雨，Q：今天刮风，R：我去爬山。
(1) (P∨Q)→¬R
＝ 今天要是下雨或刮风，我就不去爬山。
(2) R→(¬P∧¬Q)
＝ 如果我去爬山了，则今天既没下雨也没刮风。
(3) P∧¬Q
＝ 今天下雨了，但没有刮风。
合式公式(命题公式)：用命题常项/变元和联结词按规则构成的符号串。
递归定义：① 原子命题是公式；② A 是公式则 (¬A) 是公式；③ A、B 是公式则 (A∧B)、(A∨B)、(A→B)、(A↔B) 是公式；④ 有限次应用 ①~③ 的才是公式。
约定：最外层括号可省；不影响运算次序的括号可省。
联结词优先级： ¬ > ∧ > ∨ > → > ↔(先否定，再合取、析取，最后条件/双条件)。「(P∨Q)→R」与「P∨(Q→R)」完全不同，括号有没有、在哪，先看优先级再判断要不要。
| 名称 | 定义 | 例子 |
|---|---|---|
| 重言式(永真式) | 所有指派下取值均为真 | ¬(P∧Q)→(¬P∨¬Q) |
| 矛盾式(永假式) | 所有指派下取值均为假 | ¬(P→Q)∧Q |
| 可满足式 | 至少存在一组成真指派 | ¬(P→Q)∧Q∨R |
三者关系：重言式一定是可满足式，但可满足式不一定是重言式。重言式常记作 T，矛盾式常记作 F。
用三步法画 P→(Q→R) 的真值表(见书表 1.7)，最后一步看最后一列：只有 PTT、QTT、RFF 这一行为假，所以成假赋值 1 个：TTF。
规律：画表必出考点是「指出成假赋值/成真赋值」，数清楚 2ⁿ 行、逐列核对，别跳步。
两个公式 A、B 在任何指派下真值都相同，称 A、B 等值，记 A⇔B。等价是重言的双条件：A⇔B ⟺ A↔B 是重言式。
| 定律 | 等值式 |
|---|---|
| 双重否定律 | ¬¬A ⇔ A |
| 幂等律 | A∨A ⇔ A，A∧A ⇔ A |
| 结合律 | (A∨B)∨C ⇔ A∨(B∨C)；(A∧B)∧C ⇔ A∧(B∧C) |
| 交换律 | A∨B ⇔ B∨A；A∧B ⇔ B∧A |
| 分配律 | A∨(B∧C) ⇔ (A∨B)∧(A∨C)；A∧(B∨C) ⇔ (A∧B)∨(A∧C) |
| 吸收律 | A∨(A∧B) ⇔ A；A∧(A∨B) ⇔ A |
| 德摩根律 | ¬(A∨B) ⇔ ¬A∧¬B；¬(A∧B) ⇔ ¬A∨¬B |
| 同一律 | A∨F ⇔ A；A∧T ⇔ A |
| 零律 | A∨T ⇔ T；A∧F ⇔ F |
| 排中律 | A∨¬A ⇔ T |
| 否定律 | A∧¬A ⇔ F |
| 蕴涵等值式 | A→B ⇔ ¬A∨B |
| 等价等值式 | A↔B ⇔ (A→B)∧(B→A) |
| 假言易位 | A→B ⇔ ¬B→¬A |
| 等价否定等值式 | A↔B ⇔ ¬A↔¬B |
| 归谬论 | (A→B)∧(A→¬B) ⇒ ¬A |
速记：去 ∧ 去 ∨ 找德摩根；去 → 找「蕴涵等值式」；要 ↔ 先拆两个 →。演算里用到最多的就是 蕴涵等值式 + 德摩根 + 分配/结合/交换 + 排中/同一。
证 P ⇔ (P∧Q)∨(P∧¬Q)：
(P∧Q)∨(P∧¬Q) ⇔ P∧(Q∨¬Q) 分配律
⇔ P∧T 排中律 ⇔ P 同一律 ✓
证 (P∨Q)→R ⇔ (P→R)∧(Q→R)：先「蕴涵等值式」拆 → 成 ¬(P∨Q)∨R，德摩根、分配，再合并回两个 →。
演算看看：
(P→Q)→R ⇔ ¬(P→Q)∨R ⇔ ¬(¬P∨Q)∨R ⇔ (P∧¬Q)∨R
P→(Q→R) ⇔ ¬P∨(¬Q∨R) ⇔ (¬P∨¬Q)∨R
取 P=F、R=F 时，前者为 F、后者为 T，真值不同 → 条件 → 不满足结合律，(P→Q)→R 不等值于 P→(Q→R)。
蕴涵：若 P→Q 是重言式，称 P 蕴涵 Q，记 P⇒Q(读「P 蕴涵 Q」，又叫永真条件式)。
注意区分：→ 是联结词(命题的一部分)，⇒ 和 ⇔ 是公式间的关系记号，不是联结词。
推证 ¬Q∧(P→Q) ⇒ ¬P：
假定 ¬Q∧(P→Q) 为 T → Q 为 F。此时若 P 为 T，则由 P→Q 得 Q 为 T，矛盾。故 P 只能为 F，即 ¬P 为 T ✓。反证法(方法三)。
| 名称 | 形式 |
|---|---|
| 化简律 | P∧Q ⇒ P；P∧Q ⇒ Q |
| 附加律 | P ⇒ P∨Q |
| 变形附加律 | ¬P ⇒ P→Q；Q ⇒ P→Q |
| 变形简化律 | ¬(P→Q) ⇒ P；¬(P→Q) ⇒ ¬Q |
| 假言推理(MP) | P∧(P→Q) ⇒ Q |
| 拒取式(MT) | (P→Q)∧¬Q ⇒ ¬P |
| 析取三段论 | (P∨Q)∧¬Q ⇒ P |
| 条件三段论 | (P→Q)∧(Q→R) ⇒ P→R |
| 等价三段论 | (P↔Q)∧(Q↔R) ⇒ P↔R |
| 构造二难(析取/合取) | (P→Q)∧(R→S)∧(P∨R) ⇒ Q∨S；(P∧R) ⇒ Q∧S |
| 前后件附加 | P→Q ⇒ (P∨R)→(Q∨R)；P→Q ⇒ (P∧R)→(Q∧R) |
联结词完备集：用集合里的联结词能表示出任意 n 元真值函数的公式，就称它是完备集。
由等值式逐层化简，可得一串越来越小的完备集：
S₁ = {¬, ∧, ∨, →, ↔} → S₂ = {¬, ∧, ∨, →} → S₃ = {¬, ∧} 或 S₄ = {¬, ∨}
与非 P↑Q ⇔ ¬(P∧Q)；或非 P↓Q ⇔ ¬(P∨Q)——对应计算机硬件里的与非门、或非门。{↑} 和 {↓} 各自单独都是完备集。
「只有 Q 才 P」是 Q→P，不是 P→Q。必要条件和充分条件方向相反，符号化前先判断谁是条件。
自然语言「或」的相斥义不能写成 ∨，要写异或 (P∧¬Q)∨(¬P∧Q)。
条件 → 不满足结合律：(P→Q)→R ≢ P→(Q→R)。改括号必须按优先级或加括号，不能想当然。
命题的真值必须唯一。「x+1=2」在 x 未定时不是命题；「宇宙中有类似地球的生命体」虽然不知道答案，但真值唯一，是命题。
联结词优先级 ¬ > ∧ > ∨ > → > ↔，最外层括号可省。写公式、判括号要不要保留，全靠它。
含 n 个变元的公式有 2ⁿ 组指派——填空、判断选择常考；真值表列赋值时从 FF…F 按二进制递增，别漏行。
先自己算，再展开对答案。做错的对回上面对应知识点。
「我是中国人」「角马是非洲数量最多的动物」是命题(陈述句 + 唯一真值)。「我正在说谎」是悖论不是命题；「禁止喧哗」是祈使句不是命题。
P→Q。「仅当 Q」＝Q 是 P 的必要条件，「P 仅当 Q」符号化为 P→Q，不要把方向写反。
¬(P∧Q)。用德摩根展开就是 ¬P∨¬Q。注意不是 ¬(P∨Q)——「既…又…」是合取，否定它。
重言式。它就是假言推理 P∧(P→Q)⇒Q 的「⇒ 变 →」形式，等价于说「前提成立则结论必真」。
等值。德摩根律：¬(P∨Q) ⇔ ¬P∧¬Q。记忆口诀：「∨ 变 ∧，¬ 进括号，逐个否」。反之 ¬(P∧Q) ⇔ ¬P∨¬Q。
Q→P。先用吸收律：P∨(P∧Q) ⇔ P，于是原式变成 Q→P。答案一步就出来了。
「2 不是偶数且 -3 不是负数」。设 P：2 是偶数，Q：-3 是负数，原式为 P∨Q，否定为 ¬(P∨Q) ⇔ ¬P∧¬Q。注意「或」的否定是「且」(德摩根)。
2³ = 8 组。赋值从 FFF 递增到 TTT：FFF, FFT, FTF, FTT, TFF, TFT, TTF, TTT。
{∧, ∨} 不是——没有否定，表示不出 ¬P 这种真值函数。{¬, ∧} 是——它是最小完备集之一(德摩根律可推出 ∨)。
条件 →。P→Q 与 Q→P 含义不同；合取、析取、双条件都对称，否定只有一元。