速成 · 离散数学 | L.D.J 的私家工坊

这门课的名字叫“离散数学”，但现有课件的准确范围是离散数学（1）：数理逻辑。集合、函数和归纳法只在开头用来搭语言；考试真正反复出现的是四件事：

命题公式怎样取值、化范式、判断推论；
谓词公式怎样读、怎样解释、怎样把量词移到前面；
怎样只用公理和推理规则写形式证明；
怎样把“证明结论”改造成“推出空子句”的归结反驳。

先分清四种符号

符号	所在层次	人话
$A\Rightarrow B$	对公式关系的叙述	如果 $A$ ，那么 $B$ ；不是本课程固定使用的对象语言联结词
$A\to B$	公式内部	一个新的合式公式，真值按蕴涵表计算
$\Gamma\models B$	语义	每个满足前提集 $\Gamma$ 的赋值或模型也满足 $B$
$\Gamma\vdash B$	语法	能从 $\Gamma$ 出发，按公理和规则写出一个以 $B$ 结尾的证明序列

可靠性与完备性把后两种关系接起来：

\Gamma\vdash B\Longrightarrow\Gamma\models B \qquad\text{(soundness)},

\Gamma\models B\Longrightarrow\Gamma\vdash B \qquad\text{(completeness)}.

可靠性说“证出来的不能错”，完备性说“逻辑上必然正确的都能证出来”。二者不是同一句话。

第一条线：命题逻辑

真值只看结构，不看句子是否自然

$p\to q$ 只有在 $p=1,q=0$ 时为假。因而一个听起来荒诞的句子，只要前件为假，形式蕴涵仍为真。

常用等值式应当熟到能直接消元：

p\to q\equiv\neg p\lor q, \qquad p\leftrightarrow q\equiv(p\to q)\land(q\to p),

\neg(p\land q)\equiv\neg p\lor\neg q, \qquad \neg(p\lor q)\equiv\neg p\land\neg q.

判断公式类型

永真式：所有赋值下都为 $1$ ；
永假式：所有赋值下都为 $0$ ，因此不可满足；
可满足式：至少一个赋值下为 $1$ 。

永真式当然也可满足。“永真、永假、可满足”不是三个互斥盒子；真正互斥的是“不可满足”和“可满足”。

范式的固定路线

把任意公式化为合取范式或析取范式，按同一条流水线：

消去 $\to,\leftrightarrow,\oplus$ ；
用 De Morgan 律把 $\neg$ 推到命题变元前；
消去双重否定；
用分配律整理为“合取套析取”或“析取套合取”。

主析取范式由公式取值为 $1$ 的真值行生成极小项；主合取范式由公式取值为 $0$ 的行生成极大项。

例如 $p\to q$ 只在 $(p,q)=(1,0)$ 时为假，所以主合取范式就是这一行对应的极大项：

\neg p\lor q.

其余三行都为真，因此主析取范式为

(\neg p\land\neg q) \lor(\neg p\land q) \lor(p\land q).

语义推论怎样判

判断

A_1,\ldots,A_n\models B

有三条等价路线：

假设所有 $A_i$ 都真，直接推出 $B$ 真；
检查 $(A_1\land\cdots\land A_n)\to B$ 是否永真；
检查 $\{A_1,\ldots,A_n,\neg B\}$ 是否不可满足。

若推论不成立，只需给一个“前提全真、结论为假”的赋值。反例比长篇解释更有力。

第二条线：谓词逻辑

一句话先拆成对象、性质和量词

把“每个认真学习的人都取得好成绩”写成

\forall x\,(Study(x)\to Good(x)).

不能写成 $\forall x\,Study(x)\to\forall x\,Good(x)$ ：后者说的是“如果所有人都学习，那么所有人都有好成绩”，强弱完全不同。

量词顺序也不能随便换：

\exists x\forall y\,R(x,y)\models\forall y\exists x\,R(x,y),

但反向一般不成立。前者要求同一个 $x$ 对所有 $y$ 都奏效；后者允许每个 $y$ 使用不同的 $x$ 。

自由变元、约束变元和可代入

在 $\forall x\,Q(x,y)$ 中， $x$ 受量词约束， $y$ 自由。一个符号在同一公式的不同位置可以既有自由出现，也有约束出现。

代入时最危险的是变量捕获。若把含自由变元 $y$ 的项代入 $\forall y\,R(x,y)$ 中的 $x$ ，原本自由的 $y$ 会被量词抓住，因此不可直接代入。先把约束变元换成新名字，再代入。

模型求值

谓词公式的真值不是只靠符号决定，还要给出：

非空论域 $D$ ；
常元指向哪个对象；
函词解释成什么运算；
谓词解释成什么关系；
自由变元的赋值。

要否定一个所谓“永真式”，构造一个很小的反模型通常最快。论域 $\{a,b\}$ 、让 $P$ 只对 $a$ 真、 $Q$ 只对 $b$ 真，就能反驳很多错误的量词分配式，例如

\exists xP(x)\land\exists xQ(x) \not\models \exists x(P(x)\land Q(x)).

前束范式与 Skolem 化

前束范式把量词全部搬到公式最前：

Q_1x_1\cdots Q_nx_n\,M,

其中 $M$ 无量词。步骤是：

消去 $\to,\leftrightarrow$ ；
把否定推进量词，使用 $\neg\forall xA\equiv\exists x\neg A$ 、 $\neg\exists xA\equiv\forall x\neg A$ ；
先把不同量词绑定的变量换成互不冲突的新名字；
利用辖域等值式逐个把量词外提。

Skolem 化消去存在量词：

若 $\exists y$ 前没有全称量词，用新常元 $c$ 代替 $y$ ；
若其前已有 $\forall x_1,\ldots,\forall x_k$ ，用新函数 $f(x_1,\ldots,x_k)$ 代替 $y$ 。

Skolem 式与原式通常不逻辑等价，但二者同可满足或同不可满足。归结法需要的是这个可满足性关系。

第三条线：公理证明

命题逻辑的 Hilbert 系统只把 $\neg,\to$ 当基本联结词：

\mathrm{A1}\quad R\to(Q\to R),

\mathrm{A2}\quad (P\to(Q\to R))\to((P\to Q)\to(P\to R)),

\mathrm{A3}\quad (\neg Q\to\neg R)\to(R\to Q).

唯一基本规则是 MP：

Q,\quad Q\to R\quad\Longrightarrow\quad R.

谓词系统再加入：

\mathrm{A4}\quad \forall xQ(x)\to Q[x/t],

其中 $t$ 对 $x$ 可代入，以及

\mathrm{A5}\quad \forall x(Q\to R(x))\to(Q\to\forall xR(x)),

其中 $x$ 不在 $Q$ 中自由出现；再加入概括规则

Q\Longrightarrow\forall xQ.

写证明的机械套路

若目标是 $P\to R$ ，而手上有 $P\to Q$ 和 $Q\to R$ ，不要凭自然语言跳步。引用已经证明的传递定理：

(Q\to R)\to((P\to Q)\to(P\to R)),

再连续两次 MP。

每一行证据只能是：

前提；
某个公理模式的实例；
已证定理；
由前面两行 MP 得到；
谓词系统中由前行 UG 得到。

考试若明确“只能用公理与规则”，就不能把演绎定理当捷径。

第四条线：归结法

证明 $\Gamma\models R$ 时先反驳：

\Gamma\models R \quad\Longleftrightarrow\quad \operatorname{Unsat}(\Gamma\cup\{\neg R\}).

命题归结的计算流程：

把前提与否定结论合取；
化为合取范式；
每个简单析取式作为一个子句；
对互补文字归结；
推出空子句 $\square$ 。

例如证明

P\to Q,\quad P\models Q.

加入 $\neg Q$ 后的子句集为

\{\neg P\lor Q,\ P,\ \neg Q\}.

先由前两句归结得 $Q$ ，再与 $\neg Q$ 归结得 $\square$ 。

谓词归结多两步：

先前束化、Skolem 化并转为子句；
用代换统一两个文字后再归结。

归结时每次都要写清父子句、互补文字和代换。只写“显然推出空子句”通常拿不到过程分。

最后一天怎么复习

默写真值表、A1–A5、MP、UG、可靠性与完备性；
各做一题主范式、前束范式、Skolem 范式；
准备两个二元素反模型，专门对付错误的量词分配；
完整手写一次命题公理证明和一次谓词公理证明；
完整走一遍“否定结论—子句集—空子句”的归结流程。

最常见的失分不是不会算，而是混淆层次：把 $\models$ 当 $\vdash$ 、把模型中为真当永真、把 Skolem 化当等值变换、把自由变元在代入时意外绑定。每一步先问“我现在是在做语义、语法，还是可满足性变换”，路线就不容易乱。

速成 · 离散数学