离散数学 1 第 1 章：命题联结词——真值表与命题符号化
很多人把这一章当成"背五个符号"，结果是真值表画得出来，一见自然语言就翻错。这一章真正要建立的是翻译能力：拿到一句中文，能判断它是不是命题、该用哪个联结词、嵌套顺序是什么。五个联结词的真值定义是后面一切等值演算、范式、推理的底层规格——真值表里错一行，第 2 章到第 4 章都会跟着错，而且错得很隐蔽。
一、命题：真值唯一确定的陈述句
命题的定义只有一句话：能判断真假的陈述句。三个条件缺一不可——是陈述句（不是疑问句、祈使句、感叹句）、有真假可言、真假唯一。
- "3 是素数"：命题，真值为真。
- "x > 5"：不是命题。x 未指定，真值不确定。它是开句，是第 3 章谓词的原料。
- "请把门关上"：不是命题，祈使句没有真值。
- "这句话是假的"：不是命题。若它为真则它为假，若它为假则它为真，真值不唯一，这是悖论。
不含联结词的命题叫原子命题，习惯用 p、q、r 表示；由联结词组合出来的叫复合命题。所谓符号化，就是先用原子命题给每个简单分句"起名"，再用联结词把它们按原句的逻辑结构连起来。
二、五个联结词的真值定义
一张表看完，1 表示真，0 表示假：
| p | q | ¬p | p∧q | p∨q | p→q | p↔q |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
- 否定 ¬p：一元联结词，真值取反。¬ 的优先级最高。
- 合取 p∧q：仅当 p、q 都真时为真，对应"并且""不但…而且"。
- 析取 p∨q：仅当 p、q 都假时为假，对应可兼或——允许两者同时成立。
- 蕴含 p→q：仅当 p 真而 q 假时为假。p 叫前件，q 叫后件。
- 等价 p↔q：p、q 真值相同时为真，对应"当且仅当"。
五个联结词里，只有 → 的真值表不能靠日常语感直接记住，其余四个都能用"并且/或者/不是/相同"秒推。
三、蕴含：唯一需要专门适应的地方
p→q 只在"前件真、后件假"这一种情况下为假。由此得到三条必须接受的结论：
- 前件为假时，整个蕴含为真。 "如果太阳从西边出来，我就请你吃饭"——太阳没从西边出来，这句话没有被推翻，按定义为真。这叫空真（vacuously true），不是"无意义"。
- → 表达真值关系，不表达因果关系。 "1+1=2 → 雪是白的"是真命题，尽管两者毫无关联。考试里把两句无关的话用 → 连起来，只要不出现"真推出假"，它就是真的。
- p→q 与 q→p 不等值，与 ¬p→¬q 也不等值；唯一与它等值的是逆否式 ¬q→¬p。
四、自然语言到符号：翻译对照表
| 中文说法 | 符号化 | 说明 |
|---|---|---|
| 不但 p 而且 q | p∧q | 并列、递进都作合取 |
| p 或 q | p∨q | 默认可兼或 |
| 要么 p，要么 q | (p∨q)∧¬(p∧q) | 排斥或，二者恰一 |
| 如果 p，则 q | p→q | p 是前件 |
| 只有 p，才 q | q→p | "只有"引出的是必要条件 |
| p 仅当 q | p→q | 与上一行同义换序 |
| 除非 p，否则 q | ¬p→q，即 p∨q | p 是 q 不发生的条件 |
| p 当且仅当 q | p↔q | 充要条件 |
| p 是 q 的充分条件 | p→q | 有 p 必有 q |
| p 是 q 的必要条件 | q→p | 无 p 必无 q |
这张表的用法是先找逻辑主词：见到"只有…才…"，把"才"后面的句子当后件不行，要把"才"后面的当前件、"只有"后面的当后件。判断口诀："只有 p 才 q"读作"q 的必要条件是 p"，即 q→p。
一个完整的符号化例子："如果明天下雨或者我有课，我就不去爬山。"先切原子命题：p 表示"明天下雨"，q 表示"我有课"，r 表示"我去爬山"。前半句"下雨或者有课"是 p∨q，充当条件的前件；"不去爬山"是 ¬r。整句写成 (p∨q)→¬r。这里括号不能省，一旦句子嵌套超过两层，靠优先级读公式迟早出错。
五、合式公式与优先级
命题公式（合式公式）是递归定义的：原子命题是合式公式；若 A 是合式公式，则 ¬A 是；若 A、B 是，则 (A∧B)、(A∨B)、(A→B)、(A↔B) 都是；只有有限次应用上述规则得到的符号串才是合式公式。这条定义解释了为什么 p∧→q 不是公式——它无法由规则生成。
联结词的优先级从高到低为 ¬、∧、∨、→、↔，同级左结合。但考试和工程里都不要依赖优先级：凡有嵌套就加括号，是唯一不会产生歧义的写法。另外要记住，复合命题的真值完全由原子命题的真值决定，与原子命题的内容、语气、因果毫无关系——这叫真值函项性，是命题逻辑能做成"计算"的根本原因。
六、真值表与赋值
含 n 个命题变元的公式，每个变元取 0 或 1，共 2ⁿ 种赋值，真值表就是把这 2ⁿ 行全部列出。标准写法按二进制从 00…0 递增到 11…1，这样第 i 行（从 0 计）的行号正好是该行的二进制值，第 2 章编极小项时可以直接对应。
使公式为真的赋值叫成真赋值，使公式为假的叫成假赋值。按成真赋值的分布，公式分三类：
- 重言式（永真式）：所有赋值都成真，如 p∨¬p
- 矛盾式（永假式）：所有赋值都成假，如 p∧¬p
- 可满足式：至少存在一个成真赋值
画表的操作顺序是由内向外：先算括号最内层，每一列只引用它左边已经算好的列。3 个变元是 8 行，4 个变元 16 行——考场上变元超过 3 个，基本就该改用等值演算，硬画表既慢又容易抄错。
易错点
- "只有 p 才 q" 是 q→p，方向反了就是全错。判断时把它改写成"q 的必要条件是 p"再动笔。
- "p 或 q"默认是可兼或；题目强调"不能同时发生"时，必须写成 (p∨q)∧¬(p∧q)，不能只写 p∨q。
- 前件为假时蕴含为真，这是定义而非约定俗成的宽松处理，答题时要敢写"真"。
- 含自由变元的开句（如 x>5）不是命题，必须先量化才有真值；这一步的合法性来自第 3 章。
这一章在整门课里的位置
本章的五个真值表是第 2 章等值演算与范式的唯一依据；第 3 章把原子命题拆成"个体词 + 谓词"，但联结词部分原样搬过去，一个符号都不改；到第 5 章讲集合恒等式时，你会发现 ∪ 对应 ∨、∩ 对应 ∧、补集对应 ¬，结构完全同构。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 离散数学 1：数理逻辑与集合论 14 讲
- 离散数学 2：图论 10 讲