本科数学 · 数理逻辑

四

模块四：离散数学

Discrete Math · 程序员的底层逻辑

微积分研究连续的东西，离散数学研究一个个分立的对象：逻辑、集合、图、整数。计算机电路是与或非门、数据库是集合运算、导航是图论、HTTPS 加密是数论。这一层，是程序员的数学身份证。本模块 4 节。

这一模块在整条线里的位置：前面三块都是"连续/数值"的世界观，这一块换个操作系统——计算机只认 0 和 1、只处理一个一个的对象，所以它需要的是逻辑、集合、图、整数这套"离散语言"。学完能看懂算法为什么这么设计、加密怎么来的；到了研究生你会学可计算性、范畴论、密码学。这个知识在算法里直接用来做图算法（导航/社交网络）、在工程里用来做电路设计与数据库查询优化。

本模块要学什么 · 一张小图

推理：㉒数理逻辑 → 容器：㉓集合论 → 结构：㉔图论 → 密码：㉕数论基础
依赖链：逻辑是推理的语法 → 集合是数据的容器 → 图把"关系"画出来 → 数论给互联网加密。

数理逻辑

Logic · 把"如果…就…"严格化

【章首引子】你写代码 if (下雨 && 没带伞) 就打车——这里的 && 就是逻辑与。几亿个与或非门拼起来，就是你手里的电脑。数理逻辑把日常"如果…就…"掰扯成铁律，让你写 if-else 不写 bug。

卡必背公式 / 记忆口诀

集合运算：交并补差/幂集

关系：等价/偏序/函数

递归关系求解

口诀：离散是计算机科学的根

① 是什么：命题与联结词

啥¬∧∨→↔

命题：能判断真假的陈述句。联结词：¬ 非（不）、∧ 与（并且）、∨ 或（或者）、→ 蕴含（如果…就）、↔ 等价（当且仅当）。真值表：列出所有真假组合，看复杂命题最终真假。

蕴含 p→q 最反直觉：只有"p 真 q 假"时才为假。前提为假时整个命题自动为真（"善意推定"）。

② 怎么想到的

思解题心法

列真值表：n 个命题变元有 2ⁿ 行，逐行算。

背德摩根律：¬(p∧q)=¬p∨¬q，¬(p∨q)=¬p∧¬q——就是 !(a&&b)=!a||!b。

推理规则：假言推理（p→q 且 p 真，则 q 真）、拒取式（p→q 且 q 假，则 p 假）。

③ 完整解法：三个例题

证数理逻辑的核心定理与公式

核心定理：①德摩根律：$\neg(P\wedge Q)\iff\neg P\vee\neg Q$，$\neg(P\vee Q)\iff\neg P\wedge\neg Q$。②蕴含的等价形式：$P\to Q\iff\neg P\vee Q$，逆否命题 $P\to Q\iff\neg Q\to\neg P$（逆命题不等价）。③量词否定：$\neg\forall x\,P(x)\iff\exists x\,\neg P(x)$，$\neg\exists x\,P(x)\iff\forall x\,\neg P(x)$。④任一命题公式都能化成析取范式（DNF）与合取范式（CNF）。⑤命题逻辑的可靠性与完备性：语法可推演 $\iff$ 语义上为永真式。

推导思路：①先考察左边 $\neg(P\wedge Q)$：合取 $P\wedge Q$ 为真，当且仅当 $P$、$Q$ 同时为真。②取反后，$\neg(P\wedge Q)$ 为真当且仅当"$P$、$Q$ 不同时为真"，也就是"$P$ 为假，或者 $Q$ 为假"。③而"$P$ 为假或 $Q$ 为假"写作符号正是 $\neg P\vee\neg Q$，所以两个公式的真值条件完全一致。④逐行列出 $P$、$Q$ 的四种指派验证，两列真值完全相同，故 $\neg(P\wedge Q)\iff\neg P\vee\neg Q$ 成立；把式中的 $\wedge$ 与 $\vee$ 全部互换，同理得到另一条。

直觉把握：逻辑就是"把人话翻译成机器能执行的规则"。德摩根律的白话是："并非两样都满足"等价于"至少一样不满足"——你在搜索框里打「非(苹果且手机)」，搜出来的就是「非苹果或非手机」。AI/工程里，知识图谱的规则推理、程序合成、SAT 约束求解、SQL 里 WHERE 条件的等价改写，全在吃这套；而" $\neg\forall$ 变 $\exists$ "是写反例类断言（"不存在反例"怎么证伪）时的看家本领。

例题1：德摩根律化简 ¬(p∨q)

【审题】套定律。

思路：!(a||b) = !a&&!b。

逐步解法：¬(p∨q) = ¬p ∧ ¬q。"不是（p 或 q）"等于"既不是 p 也不是 q"。

例题2：p→q 什么时候为假

【审题】"如果下雨我就带伞"。

思路：找食言情形。

逐步解法：只有"下雨了却没带伞"（p 真 q 假）为假。其余都算没食言。

例题3：谓词逻辑与量词

【审题】"所有人都要喝水"。

思路：∀（对所有）和 ∃（存在）。

逐步解法：∀x (人(x)→喝水(x))。否定时 ∀↔∃："不是所有人都…"= "存在一个人不…"。

逻辑核心定律德摩根：$¬(p∧q)=¬p∨¬q$ | $¬(p∨q)=¬p∧¬q$
蕴含：$p\rightarrow q ≡ ¬p∨q$ | 量词否定：$¬∀x P(x) ≡ ∃x ¬P(x)$

④ 用途与案例

CPU 逻辑门

高电平=1、低电平=0，与或非门就是 ∧∨¬。几亿个门拼起一台电脑。

程序 if-else

条件判断、短路求值、布尔代数——写 bug 少全靠把逻辑想清楚。

法律条文分析

"如果…就…"的法条翻译成逻辑式，能检验是否矛盾、有无漏洞。

AI 推理

专家系统、规则引擎、自动定理证明，底层都是数理逻辑。

⑤ 延展

展知识衔接地图

往研究生走：命题逻辑 → 数理逻辑/可计算性（哥德尔不完备、图灵机、停机问题）。往算法走：布尔可满足性 SAT 是 NP 完全问题的祖师爷。

思维陷阱

把"蕴含 p→q"和"因果"划等号。逻辑里它只是真假函数，不要求 p 真的"导致"q。

"或"∨ 是可兼或。"A 或 B"是至少一个成立（可兼），不是二选一的异或。程序里 || 是可兼或，^ 才是异或。

练习

【基础】"今天周一 ∧ 今天下雨"何时为真？

查看思路与解答

与（∧）要求两个都真：既是周一又下雨才真。

【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到本页"是什么"和例题区，把卡住的那步再推一遍。

【进阶】¬∀x P(x) 等价于？

查看思路与解答

量词否定：∃x ¬P(x)。"不是所有 x 都满足 P"= "存在 x 不满足 P"。

【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到本页"是什么"和例题区，把卡住的那步再推一遍。

费曼学习法：讲给别人听

① 用自己的话讲：命题逻辑是真假值的代数，谓词逻辑再加上"任意∀/存在∃"两个量词，是写程序和证定理的语言。

② 举个反例（什么条件下不成立）："任意 x，存在 y" 和 "存在 y，任意 x" 顺序一换意思天差地别；逆命题和否命题绝不等价。

③ 哪里还说不清：德摩根律怎么把一串与/或一口气翻成对面？

记

小结卡

① ¬∧∨→ 就是 if-else 的祖宗；德摩根律 !(a||b)=!a&&!b。

② p→q 只有"p 真 q 假"时才假；∨ 是可兼或。