Sherfiter's wiki for fun第 2 章 · 命题逻辑
逻辑是「可靠推理的形式化」:给定前提,什么样的结论必然成立。命题逻辑处理最小单位(命题:非真即假的陈述句),它是数字电路的数学(计组课第 3 章的与或非门)、SQL 的 WHERE 条件、编程语言的布尔类型的共同祖先。本章的目标:会算真值表、会判等价、会判断推理有效——并且知道这些技能在硅片里怎么物理实现。
2.1 命题与联结词
命题 = 可判定真假的陈述句(「3 是素数」是;「2 大于 3」是,虽然假;「这题好难啊」不是)。五个联结词把命题组合成复合命题:
| 记号 | 读法 | 真值规则 | 编程对应 |
|---|---|---|---|
| ¬p | 非 p | 取反 | !p |
| p ∧ q | p 且 q | 全真才真 | && |
| p ∨ q | p 或 q | 有真即真 | || |
| p → q | p 蕴含 q | 前真后假才假 | 无直接对应!(见 2.2) |
| p ↔ q | 当且仅当 | 同真同假 | == |
真值表是命题逻辑的「一切裁决工具」:n 个变元的公式有 2ⁿ 行。三个变元 8 行,画熟三元的就够用了。
2.2 蕴含的真值表:最反直觉的联结词
p → q 只在「p 真而 q 假」时为假。三个推论值得单独想通:
- p 假时,p → q 恒真(无论 q)。「如果 2 是偶数,则月亮是奶酪做的」——在形式逻辑里这句话为真,因为前提为假。日常语言不会这么说,但形式逻辑要求蕴含对一切前提取值有定义,「假前提下不保证假结论」(vacuously true)是约定俗成的合理化。
- p → q 等价于 ¬p ∨ q。真值表一画便知;这是蕴含化简的万能公式。
- p → q 与 q → p 是两回事(逆命题),与 ¬q → ¬p 等价(逆否命题)。「下雨则地湿」推不出「地湿则下雨」,但能推出「地不干则没下雨」。考试爱考逆否,生活里爱犯逆推,同一件事。
2.3 逻辑等价与德摩根律
两个公式在一切赋值下同真值 = 等价(p ≡ q)。常用等价式(全部可用真值表验证):
- 德摩根:¬(p∧q) ≡ ¬p∨¬q;¬(p∨q) ≡ ¬p∧¬q;
- 分配:p∧(q∨r) ≡ (p∧q)∨(p∧r)(和集合运算(第 1 章)、算术乘法对加法同构);
- 吸收:p∧(p∨q) ≡ p;
- 双重否定:¬¬p ≡ p。
德摩根律的实际杀伤力:写条件的否定时人脑最爱犯的错。!(a && b) 不是 !a && !b 而是 !a || !b;「不是(男且老)」=「女或年轻」。SQL 优化、if 条件化简、电路化简,全靠它。
永真式(tautology):一切赋值下为真。推理的核心定理 p→q、p ⊢ q(假言推理)的合法性,验证方式就是检查 (p∧q)→q 是永真式。可满足性(SAT):是否存在使其为真的赋值——SAT 求解器是工业界的重炮(芯片验证、软件测试),P vs NP 的主角,知道它的重要性即可。
2.4 推理规则:合法的「一步走」
推理规则 = 从真前提保真地推出结论的模式:
| 规则 | 形式 | 名字 |
|---|---|---|
| p, p→q ⊢ q | 肯定前件 | 假言推理(MP) |
| ¬q, p→q ⊢ ¬p | 否定后件 | 拒取式(MT) |
| p→q, q→r ⊢ p→r | 传递 | 假言三段论 |
| p∨q, ¬p ⊢ q | 析取三段论 | —— |
两个著名谬误(考试和争论都爱出):肯定后件(q 真,p→q,推 p——「他发烧了,发烧则感冒,所以他感冒」?发烧原因多了)与否定前件(¬p,p→q,推 ¬q——「不发烧,发烧则感冒,所以没感冒」?不吃退烧药也能感冒)。识别这两类错误,是逻辑学给你的第一件防身武器。
2.5 布尔代数:逻辑的电路形态
把 {真, 假} 换成 {1, 0},∧∨¬ 换成 AND/OR/NOT 门,命题逻辑就变成了布尔代数:数字电路(计组课第 3 章的全加器、第 5 章的控制器译码)就是命题公式的物理实现。一组真值表 → 卡诺图化简 → 门电路,这条流水线在数字电路课练,数学基础全在本章。范式(析取范式 DNF:与项的或;合取范式 CNF:或项的与)是「任意布尔函数都能标准写出」的证明:每个使公式为真的赋值对应一个最小项,DNF 就是把它们或起来——「真值表和公式一一对应」,这就是电路综合的第一原理。
常见错误
- 蕴含当等价用。「if 用户是 VIP 则打折」推不出「打折的都是 VIP」;2.2 的逆命题陷阱在需求评审里天天出现。
- 德摩根展开漏变号。¬(p∧q) 写成 ¬p∧¬q;写代码时对长条件的取反,先列真值表再写,别脑补。
- 真值表行数漏行。n 元公式 2ⁿ 行,n=3 时 8 行一行不能少;考试扣分重灾区。
- 把「有效推理」当「结论为真」。推理有效 = 前提真则结论真;前提本身假时,有效推理可以推出假结论(垃圾进垃圾出,和编程一样)。
练习
- 手算:画 p→q、¬p∨q、¬(p∧¬q) 三个公式的真值表(2 元 4 行),验证前两者等价、后者与 p→q 等价。
- 手算:用德摩根与分配律,把 ¬((p∨q)∧¬r) 化成只含 ¬ 和 ∧ 的等价式(逐步写依据)。
- 动手:写一个程序枚举 3 变元公式的 8 种赋值,自动判断给定公式是否永真式(把公式建成表达式树,递归求值)。这就是你的第一个「定理验证器」。
- 思考:SQL 的 WHERE 条件、Java 课第 3 章的短路求值(短路与布尔代数的「运算顺序」差异),各自在逻辑上等价、在行为上不等价(短路影响副作用)。举一个「逻辑等价但不可替换」的代码例子,思考「形式等价」与「行为等价」的边界。