← COMP5511 全部讲次
L03b-5 · 第 3 周

L03b-5 归结法:只有一条规则,先转 CNF,再推出矛盾

从零讲归结规则、CNF 和四步转换、反证法的归结算法,最后用 Tom/John 题逐轮做完整归结树,推出空子句。

一句话版

归结法只有一条规则:一个子句里有 X,另一个里有 ¬X,就把这一对消掉,剩下的用「或」连成新子句。想证 Q,就把 ¬Q 放进知识库,一直归结,直到推出什么都不剩的空子句,说明这组句子自相矛盾。

用这条规则前,所有句子都要先改写成 CNF。上一页 L03b-4 的两种链接法只能处理 Horn 子句,归结法去掉了这个限制。

先认识这几个词

词 全称 / 读法 一句人话
文字 literal 一个原子,或者它的否定,比如 p、¬p
子句 clause 若干文字用 ∨ 连起来,比如 ¬p ∨ s
互补文字 complementary literals 一对正好相反的文字,X 和 ¬X
CNF Conjunctive Normal Form,合取范式 若干子句用 ∧ 连起来
空子句 □ null clause,也写 NIL 一个文字都不剩的子句,恒为假
反证法 proof by contradiction 先假设结论不成立,推出矛盾

一个类比:两份说法对账,矛盾的一对互相抵掉

两个人各交来一份「至少有一条成立」的清单。张三写「要么下雨,要么刮风」,李四写「要么没下雨,要么停课」。

把两张清单放在一起,「下雨」和「没下雨」不可能同时成立。如果下雨,李四那张就只剩「停课」能成立;如果没下雨,张三那张就只剩「刮风」能成立。不管哪种情况,「刮风或停课」一定成立。矛盾的一对互相抵掉,剩下的合并成一张新清单。

要证一个结论,先假装它不成立,把这句「不成立」也写成一张清单丢进去。一路对账抵消,如果最后抵出一张什么都没写的空清单,说明这堆清单不可能同时成立,问题出在你假装的那一句上。

类比在哪里失效:

  • 真实对账可以一次划掉好几对,归结一次只能消一对互补文字。
  • 真实清单可以写「如果…就…」,归结只接受全是「或」的子句,所以要先改写成 CNF。

从零讲起

1. 归结规则:消掉一对互补文字

它解决什么问题

链接法只能处理「几个前提 ⇒ 一个结论」的 Horn 子句,碰到 p ∨ q 这种「至少一个成立,不知道是哪个」的句子就没办法。需要一条能直接在「或」形式的句子上做推理的规则。

直觉

归结规则说:已知两个子句 A1 ∨ A2 ∨ … ∨ An 和 B1 ∨ B2 ∨ … ∨ Bm,如果其中有一对互补文字 Ai = ¬Bj,就可以推出一个新子句,由两边去掉这一对之后剩下的所有文字析取而成。

它其实是三段论的一般化。A1 ∨ A2 可以读成 ¬A2 ⇒ A1,¬A1 ∨ A3 可以读成 A1 ⇒ A3。两条接起来是 ¬A2 ⇒ A3,也就是 A2 ∨ A3。

一步一步看

目标:拿 A1 ∨ A2 和 ¬A1 ∨ A3 做一次归结,看划掉互补文字后剩下的部分怎样拼成新子句。

用课件的例子 A1 ∨ A2 和 ¬A1 ∨ A3:

  1. 找互补文字:第一个子句有 A1,第二个有 ¬A1。

  2. 把这一对划掉。

  3. 剩下第一个子句的 A2、第二个子句的 A3。

  4. 用 ∨ 连起来,得到新子句 A2 ∨ A3。

    归结规则示意:子句 A1 ∨ A2 和 ¬A1 ∨ A3 并排,互补的 A1 与 ¬A1 用青绿划掉,剩下的 A2 和 A3 用或连起来得到 A2 ∨ A3,底部注明一次只能消一对

怎么算

两个子句各写一行,找出一对 X 和 ¬X,把两行剩下的文字全部抄到一行用 ∨ 连起来。

意思是:新子句里的东西都来自原来那两个子句,只少了那一对互补文字。两个单文字子句 s 和 ¬s 归结,什么都不剩,得到的就是空子句 □。

常见误解

以为一次可以消掉两对互补文字

p ∨ q 和 ¬p ∨ ¬q 有两对互补文字,但一次只能消一对。消 p 得到 q ∨ ¬q,消 q 得到 p ∨ ¬p,都是恒真句。同时消两对会得到空子句,那是错的,这两个子句明明可以同时为真。

以为归结可以直接用在带 ⇒ 的句子上

归结规则只对析取子句定义。带 ⇒、⇔ 或者 ¬ 套在括号外面的句子,都要先转成 CNF。

试一下

¬p ∨ s 和 p ∨ q 归结得到什么?

互补文字是 ¬p 和 p,划掉后剩 s 和 q,得到 q ∨ s。读成白话:John 是父亲则有儿子,John 和 Tom 至少一个是父亲,所以 Tom 是父亲或者 John 有儿子。

2. CNF:先把句子改写成一堆子句

它解决什么问题

归结规则只吃子句。知识库里的句子却可能带 ⇔、⇒、括号外的 ¬。需要一个机械的流程,把任何句子改写成等价的子句集合。

从哪来(补充)

每个命题公式都能转成等价的 CNF,但长度可能指数膨胀。例如 (X₁∧Y₁)∨(X₂∧Y₂)∨…∨(Xₙ∧Yₙ) 转成 CNF 后有 2ⁿ 个子句,每个子句要从每一对里挑一个。

出处:Wikipedia: Conjunctive normal form

直觉

CNF 是若干子句用 ∧ 连起来,每个子句内部只有 ∨ 和 ¬,比如 (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D)。最外层是合取,C 就是 Conjunctive。

关键定理:命题逻辑里每一个句子都逻辑等价于某个 CNF 句子。所以不管 KB 写得多复杂,都能化成一堆子句,然后只用归结这一条规则。

转换用的是第二页那张等价律表,按固定顺序用四次。口诀:先消双箭头,再消单箭头,然后把否定往里赶,最后把或往里分。

一步一步看

目标:把 α ⇔ (β ∨ γ) 按消 ⇔、消 ⇒、¬ 内推、分配四步改写,看它怎样变成三个子句的合取。

把 α ⇔ (β ∨ γ) 转成 CNF:

  1. 消 ⇔,用 biconditional elimination:(α ⇒ (β ∨ γ)) ∧ ((β ∨ γ) ⇒ α)。

  2. 消 ⇒,用 implication elimination:(¬α ∨ β ∨ γ) ∧ (¬(β ∨ γ) ∨ α)。

  3. ¬ 内推,用 de Morgan:(¬α ∨ β ∨ γ) ∧ ((¬β ∧ ¬γ) ∨ α)。

  4. 分配律展平,把 α 分配进 ¬β ∧ ¬γ:(¬α ∨ β ∨ γ) ∧ (¬β ∨ α) ∧ (¬γ ∨ α)。

    转 CNF 四步:α ⇔ (β ∨ γ) 依次消 ⇔、消 ⇒、用 de Morgan 把 ¬ 推进括号、用分配律展平,最后一行 (¬α ∨ β ∨ γ) ∧ (¬β ∨ α) ∧ (¬γ ∨ α) 共 3 个子句,用青绿标出

怎么算

第 4 步用的分配律是 (α ∧ β) ∨ γ ≡ (α ∨ γ) ∧ (β ∨ γ),把「或」分配进「且」。

意思是:每一步都换成等价式,所以最后的 CNF 和原句真值表完全相同。写完可以回读验算:三个子句还原成蕴含是 α ⇒ β ∨ γ、β ⇒ α、γ ⇒ α,合起来正是「α 成立当且仅当 β 或 γ 成立」。

常见误解

以为四步顺序可以随便换

不先消 ⇔ 和 ⇒,de Morgan 用不上;不先把 ¬ 推到原子上,分配律展开后得到的仍然不是子句。顺序是固定的。

把 CNF 和 DNF 记反

CNF 最外层是 ∧,括号里是 ∨;DNF(析取范式)反过来。转 CNF 用的是「∨ 对 ∧」的分配律,「∧ 对 ∨」那条是转 DNF 用的。

试一下

把 (P ∧ Q) ⇒ (R ∨ ¬S) 转成 CNF。

没有 ⇔,跳过第 1 步。消 ⇒:¬(P ∧ Q) ∨ R ∨ ¬S。de Morgan:¬P ∨ ¬Q ∨ R ∨ ¬S。已经是一个子句,不需要分配律。结果只有 1 个子句。

3. 归结算法:把目标取反,推出空子句

它解决什么问题

有了规则和 CNF,还要一个完整的流程:从 KB 和目标 Q 出发,怎么用归结判断 KB ⊨ Q。

从哪来(补充)

归结法可以追溯到 Davis 和 Putnam 1960 年的工作。John Alan Robinson 在 1965 年发表了 A Machine-Oriented Logic Based on the Resolution Principle,引入了合一(unification)。归结是可靠的,也是反驳完备的。

出处:Wikipedia: Resolution (logic)

直觉

第二页讲过:KB ⊨ Q 等价于 KB ∧ ¬Q 不可满足。归结法就走这条路,用反证法:

  • Step 1:构造集合 S,包含 KB 的全部句子,加上被否定的目标 ¬Q。
  • Step 2:把 S 的每个元素转成 CNF。
  • Step 3:对每一对含互补文字的子句做归结,产生的新子句若尚未出现则加入 S。

重复 Step 3,直到两种情况之一:归结出空子句,说明 S 不可满足,KB 为真时 Q 必为真;或者再也加不出新子句,说明 KB 推不出 Q。

一步一步看

目标:把 ¬Q 加进 KB 的子句集里连续归结,看两步之后怎样推出空子句,证明 KB 能推出 Q。

用一个最小的例子:KB 是 P ⇒ Q 和 P,要证 Q。

  1. 构造 S:把 ¬Q 放进去,P ⇒ Q 写成子句 ¬P ∨ Q。S = {¬P ∨ Q, ¬Q, P}。

    归结反证第 1 帧:知识库 P ⇒ Q 和 P,要证 Q,把否定的目标 ¬Q 放进集合,三个子句 ¬P ∨ Q、¬Q、P 排成一行,¬Q 用青绿标出

  2. ¬P ∨ Q 与 ¬Q 归结:Q 和 ¬Q 互补,划掉,得 ¬P。

    归结反证第 2 帧:¬P ∨ Q 与 ¬Q 连线归结,Q 和 ¬Q 互补被划掉,下方得到新子句 ¬P 并用青绿标出

  3. ¬P 与 P 归结:什么都不剩,得到空子句 □。

    归结反证第 3 帧:¬P 与 P 归结什么都不剩,得到空子句 □ 用青绿标出,底部注明推出空子句说明 KB ∧ ¬Q 不可满足,所以 KB ⊨ Q

怎么判断

推出空子句,就说明集合自相矛盾。矛盾只能来自加进去的 ¬Q,所以 Q 成立。

意思是:空子句恒为假,它的出现说明 S 里的子句不可能同时为真。KB 被假设为真,那么出错的只能是 ¬Q。这个例子三步就到底,因为它就是 modus ponens 的反证写法。

常见误解

忘了把 ¬Q 放进集合

这是归结法最常见的失分点。只拿 KB 去归结,KB 本身没有矛盾,永远推不出空子句。

以为算了几步没出空子句,就能断言 KB ⊭ Q

只有穷尽了全部可能的新子句仍然没有空子句,才能据归结的完备性断言不蕴含。提前停下来,什么都不能断言。

试一下

KB 只有 P ∨ Q,要证 P。归结能推出空子句吗?

S = {P ∨ Q, ¬P}。P ∨ Q 与 ¬P 归结得 Q。Q 和集合里任何子句都没有互补文字,加不出新子句了,没有空子句。所以 KB ⊭ P。

把它们串起来

归结法把整件事压缩成一条规则加一个反证套路。

规则本身很小:一对互补文字互相抵掉,剩下的用「或」连起来。它是三段论的一般化,所以可靠。限制是只能作用在子句上。

于是要先转 CNF。四步按顺序用第二页的等价律:消 ⇔,消 ⇒,把 ¬ 推到原子上,用分配律展平。每一步都是等价改写,意思不变。

套路来自第二页那条换法:KB ⊨ Q 等价于 KB ∧ ¬Q 不可满足。把 ¬Q 放进集合,反复归结,推出空子句就证完了。

这一套能处理 p ∨ q 这种链接法装不下的句子。Tom/John 那道题的第一句「至少一个是父亲」就是这种形状,所以只能用归结做。

课件里的坑

  • [课件没画] 最后 s 与 ¬s 归结出空子句的那条箭头课件没画,只用两个浅蓝圆圈标出;答题必须写出这一步(p.43)
  • [读图] 被方框圈住的 s 是普通单文字子句,空子句是它和 ¬s 再归结一次才出现的(p.43)
  • [易漏] 集合 S 是 KB 的 4 条加 ¬s 这 1 条,共 5 条,漏掉否定目标就推不出矛盾(p.41)
  • [代价] 分配律会让子句数量翻倍增长,最坏情况下 CNF 的长度是指数级(p.37)
  • [格式] 课件第一轮是穷举所有能归结的配对,画成一层层的树,考试按这个格式写(p.42)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写转 CNF 的四步口诀;再把 α ⇔ (β ∨ γ) 自己转一遍并回读验算;最后从翻译开始完整做一遍 Tom/John 题,画出归结树,确认最后一步 s 与 ¬s 写出来了。

必背

  1. 归结规则:两个子句含一对互补文字时,消掉这一对、其余全部析取;一次只消一对
  2. CNF = 合取套析取(最外层是 ∧);每个 PL 句子都等价于某个 CNF 句子
  3. 转 CNF 四步:消 ⇔ → 消 ⇒ → ¬ 内推(de Morgan + 双重否定)→ 分配律展平
  4. 归结算法用反证法:S = KB ∪ {¬Q},全转 CNF,反复归结;推出空子句 ⟹ Q 成立,推不出新子句 ⟹ Q 不成立
  5. Tom/John 题的 5 个子句是 p∨q、¬p∨s、¬q∨r、¬r、¬s;q∨s 与 ¬q 得 s,s 与 ¬s 归结出空子句
  6. p ∨ q 不是 Horn 子句,链接法装不下,这正是归结法存在的理由

课件例题

例 1(课件 p.35):A1 ∨ A2 和 ¬A1 ∨ A3 归结得到什么?

题面:写出归结结果,并用蕴含的读法解释它为什么成立。

提示

先找互补文字;解释时把两个子句各改写成一条蕴含。

解答

互补文字是 A1 和 ¬A1,结果是 A2 ∨ A3。A1 ∨ A2 读成 ¬A2 ⇒ A1,¬A1 ∨ A3 读成 A1 ⇒ A3,接起来是 ¬A2 ⇒ A3,即 A2 ∨ A3,三段论成立。

例 2(课件 p.38):把 α ⇔ (β ∨ γ) 转成 CNF

题面:写出四步中每一步的中间结果,并数出最终子句个数。

提示

消 ⇔ → 消 ⇒ → de Morgan → 分配律。

解答
  1. (α ⇒ (β ∨ γ)) ∧ ((β ∨ γ) ⇒ α)
  2. (¬α ∨ β ∨ γ) ∧ (¬(β ∨ γ) ∨ α)
  3. (¬α ∨ β ∨ γ) ∧ ((¬β ∧ ¬γ) ∨ α)
  4. (¬α ∨ β ∨ γ) ∧ (¬β ∨ α) ∧ (¬γ ∨ α)

共 3 个子句。回读:α ⇒ β ∨ γ,β ⇒ α,γ ⇒ α,合起来就是原式。

例 3(课件 p.40–43):Tom/John 题,证明 John 有一个儿子

见下方完整例题。

完整例题

题面(课件 p.40–43):Tom 和 John 之间至少有一个是父亲。如果 John 是父亲,他有一个儿子。如果 Tom 是父亲,他有一个女儿。Tom 没有女儿。证明 John 有一个儿子。

约定:p = John is a dad,q = Tom is a dad,r = Tom has a daughter,s = John has a son。

解法:

  1. 翻译 KB。p ∨ q,p ⇒ s,q ⇒ r,¬r。第一句是 p ∨ q,两个正文字,不是 Horn 子句,所以只能用归结。
  2. 否定目标。目标是 s,加入 ¬s。S 共 5 条。
  3. 转 CNF。只需消两个 ⇒:
原式 CNF
p ∨ q p ∨ q
p ⇒ s ¬p ∨ s
q ⇒ r ¬q ∨ r
¬r ¬r
¬s ¬s
  1. 第一轮归结,穷举所有含互补文字的配对:
参与归结的两个子句 消掉的互补文字 结果
p ∨ q 与 ¬p ∨ s p / ¬p q ∨ s
p ∨ q 与 ¬q ∨ r q / ¬q p ∨ r
¬p ∨ s 与 ¬s s / ¬s ¬p
¬q ∨ r 与 ¬r r / ¬r ¬q
  1. 第二轮归结。q ∨ s 与 ¬q,消掉 q / ¬q,得 s。

  2. 推出空子句。s 与集合里原有的 ¬s 归结,什么都不剩,得 □。

  3. 结论。S = KB ∧ ¬s 不可满足,所以 KB ⊨ s,John 有一个儿子。

  4. 语义验算。¬r 加 q ⇒ r 得 ¬q(Tom 不是父亲);再由 p ∨ q 得 p(John 是父亲);再由 p ⇒ s 得 s。这条 ¬q → p → s 和归结树走的是同一条路。

    Tom John 题的完整归结树:左列 5 个 CNF 子句,第一轮归结出 q ∨ s、p ∨ r、¬p、¬q,第二轮由 q ∨ s 与 ¬q 得 s,最后 s 与 ¬s 归结出空子句 □,注明课件没画这一步

要点:否定目标必须进集合;第一轮按课件格式穷举配对;最后一步 s 与 ¬s 必须写出来。

答题格式:符号表 → KB 与否定目标 → CNF 表 → 逐轮归结(每条写清哪两个子句、消哪对文字、得到什么)→ 空子句 → 结论一句话。

变式题(先自己做)

(1) 改编自课件 p.40–43:把「Tom 没有女儿」换成「John 没有儿子」(¬s),其余不变,用归结证明 Tom 有一个女儿(r)。 (2) 改编自课件 p.39、p.41–43:已知 a ∨ b、a ⇒ c、b ⇒ c,用归结证明 c。 (3) 改编自课件 p.37:把 ¬(P ⇒ Q) ∨ R 转成 CNF。

提示

(1) 否定目标是 ¬r,先用单文字子句去消。(2) 否定目标是 ¬c。(3) 消 ⇒ 后再用 de Morgan,最后分配。

判分点与答案(非官方评分标准)

判分点:① 否定目标进集合;② 每步写出两个父子句和消掉的文字;③ 最后一步推出 □ 并写结论;④ (3) 四步顺序正确、结果是子句的合取。

(1) S = {p ∨ q, ¬p ∨ s, ¬q ∨ r, ¬s, ¬r}。¬p ∨ s 与 ¬s 得 ¬p;p ∨ q 与 ¬p 得 q;¬q ∨ r 与 ¬r 得 ¬q;q 与 ¬q 得 □。所以 Tom 有一个女儿。

(2) S = {a ∨ b, ¬a ∨ c, ¬b ∨ c, ¬c}。¬a ∨ c 与 ¬c 得 ¬a;¬b ∨ c 与 ¬c 得 ¬b;a ∨ b 与 ¬a 得 b;b 与 ¬b 得 □。所以 c 成立。

(3) 消 ⇒:¬(¬P ∨ Q) ∨ R。de Morgan 加双重否定:(P ∧ ¬Q) ∨ R。分配律:(P ∨ R) ∧ (¬Q ∨ R),2 个子句。

闪卡自测

1. 为什么需要归结法?

前向和后向链接只能处理 Horn 子句,p ∨ q 这种两个正文字的句子它们装不下(p.21、p.35)。

2. 归结规则一次能消几对互补文字?

只能一对。同时消两对会推出过强的结论(p.35)。

3. CNF 的结构是什么?为什么归结前必须转 CNF?

若干子句的合取,子句是文字的析取;归结规则只对析取子句定义(p.36)。

4. 转 CNF 的四步是什么?

消 ⇔ → 消 ⇒ → ¬ 内推(de Morgan + 双重否定)→ 分配律展平(p.37)。

5. 归结算法的两种终止情况分别说明什么?

推出空子句:S 不可满足,Q 成立;再也加不出新子句:KB 推不出 Q(p.39)。

6. Tom/John 题为什么链接法做不了?最后一步是什么?

第一句是 p ∨ q,不是 Horn 子句。最后一步是 s 与 ¬s 归结出空子句(p.40、p.43)。

下一讲

逻辑这条路线讲完了,下一讲换到从数据里学规律的机器学习,从它的定义和监督学习讲起。见 L04a-1。

下一讲 →
L04a-1 L04a-1 机器学习是什么:从一张七行表格学会看 x 和 y

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。