← COMP5511 全部讲次
T05 · 第 5 周

T05 命题逻辑三件基本功:真值表、链接法、归结反证

同一组规则、同一个目标,用三种方法各走一遍。真值表怎么按列头拆,or 前件为什么会拆成两条 Horn 子句,归结为什么要先假设结论不成立。

一句话版

三道题共用同一组规则、同一个目标(已知 C,证 A),差别只在推理方向。中间插的一道 CNF 转换练习是后两题的地基。

先认识这几个词

读之前最好先懂命题逻辑的基本概念,见 L03b-1。

词 全称 / 读法 一句人话
命题逻辑 propositional logic 用 A、B 这类只能取真或假的符号,加联结词做推理
¬ ∧ ∨ 读「非」「且」「或」 ¬A 是 A 的反面;A ∧ B 两个都真才真;A ∨ B 至少一个真就真
⟹(也写 ⇒)/ ⇔ 读「蕴含」/「当且仅当」 A ⟹ B 是「A 成立则 B 成立」;A ⇔ B 是两个方向都成立
文字 / 子句 literal / clause 文字是一个符号或它的否定;子句是几个文字用 ∨ 连起来
正文字 positive literal 前面没带 ¬ 的文字,比如 M
⊨ 读「推出」,蕴涵关系 左边全为真时,右边一定为真
空子句 empty clause 消到一个文字都不剩,代表推出了矛盾,记作 □
目标栈 goal stack 后向链接记「还没证的子目标」的清单,后放进去的先处理

题目地图

顺序 题目 考什么 主要失分点
1 Question 1:填 (A ⟹ B) and not (B ⟹ A) 的真值表 五条联结词语义,尤其蕴含 A 为假的两行按「空真」判成假
2 插入练习:把 P ⇔ (Q ∧ R) 转成 CNF 四步转换流程 ⇔ 只拆了一个方向,漏掉子句
3 Question 2:前向链接与后向链接各证一遍 A Horn 子句、两种搜索方向 第三条规则前件是 or,忘了拆成两条
4 Question 3:用归结反证证 A 取否定、逐对消解 要证的命题没先写成子句就取否

真值表是把每种真假组合列成一行的表。这四块是递进的:真值表管语义,CNF 管形式,链接法和归结管推理。前面一块没弄清,后面一块必卡。

概念卡

1. 蕴含的语义(Implication)

人话定义:蕴含回答「如果 S1 那么 S2」这句话什么时候算对。S1 ⇒ S2 为真,当且仅当 S1 为假或者 S2 为真,等价写法是 ¬S1 ∨ S2。

例子:课件把这条规则写了正反两遍。正向是「S1 假或 S2 真则为真」,反向是「S1 真且 S2 假则为假」。反向那句更好记,因为蕴含只有这一种情况为假。

常见误解

前件为假时以为要看后件 → 只要 S1 假就直接判真,后件不用看。这叫空真(vacuously true)。真值表里 A 为假的那两行就靠这一条填,是初学最集中的失分点。

回讲义:L03b-1 命题逻辑的语法与语义

2. 合取范式(CNF, Conjunctive Normal Form)

人话定义:链接法和归结只吃统一格式的输入,CNF 就是这个格式。整个公式写成若干子句用 ∧ 连起来,每个子句内部是若干文字用 ∨ 连起来,形如 (…∨…) ∧ (…∨…)。

例子:课件给的四步流程:消 ⇔(拆成两个方向的 ⟹),消 ⟹(换成 ¬前件 ∨ 后件),把 ¬ 用德摩根律往里推,用分配律把 ∨ 分进 ∧。德摩根律说 ¬(A ∧ B) 等于 ¬A ∨ ¬B;分配律说 A ∨ (B ∧ C) 等于 (A ∨ B) ∧ (A ∨ C)。

常见误解

把分配律和德摩根律用混 → 分配律用在 ∨ 遇到 ∧ 的时候,德摩根律用在 ¬ 遇到括号的时候。课件那道题前一半用分配律,后一半用德摩根律,两处不是同一条定律。

回讲义:L03b-5 归结法

3. Horn 子句(Horn Clause)

人话定义:链接法只能处理「条件凑齐就得出一个结论」的规则,Horn 子句就是这种规则的子句写法。它是至多含一个正文字的子句;恰好一个正文字的,可以读成「若干条件合取起来 ⟹ 一个结论」。

例子:¬C ∨ M 里只有 M 是正的,读回去就是 C ⟹ M,合格。课件做转换前写了一句 “Based on Horn clause format”,交代的就是链接法对输入形状的要求。

常见误解

以为这是可选的写法习惯 → 链接法每一步都是「前件满足则结论成立」,要求结论唯一确定。子句里有两个正文字(如 A ∨ B)时,只知道至少一个成立,不知道该把哪个加进已知集合。归结没有这个限制,这是它相对链接法的主要优势(补充)。

回讲义:L03b-3 前向链接

4. 前向链接与后向链接(Forward & Backward Chaining)

人话定义:两者都用规则库一步步推出目标,区别是从哪头开始。前向从已知事实出发,哪条规则的前件全被证出,就把它的结论加进已知。后向从目标出发,把目标换成「证它所需的子目标」,递归到所有子目标都落在已知上。

例子:本题前向的已知集合演化是 {C} → {C, M} → {C, M, B} → {C, M, B, A}。后向的目标栈演化是 [A] → [B ∧ C] → [B] → [M ∧ C] → [M] → 已知。

常见误解

以为两种方法路径不同,结论可能不同 → 两者都是可靠的推理方法,结论必然一致,差别在搜索顺序和做不做无用功。本题两条路径经过的规则完全一样((3) → (2) → (1)),因为规则集太小没有分支。规则一多,前向会把整个库扫很多遍,后向只沿一条链走。

回讲义:L03b-3 前向链接、L03b-4 后向链接

5. 归结与反证(Resolution & Proof by Contradiction)

人话定义:归结是一条机械规则,靠反复使用它就能证明结论。两个子句里一个含 P、另一个含 ¬P,就把这对文字消掉,剩下部分合并成新子句。要证「前提 ⊨ 目标」,就把目标的否定加进子句集,归结出空子句即证毕。

例子:要证 C ⟹ A,先写成子句 ¬C ∨ A,整体取否按德摩根得 C ∧ ¬A。也就是把 C 和 ¬A 两个子句扔进去。C 本来已知,实际新增的只有 ¬A。

常见误解

以为一步能消多对互补文字 → 归结每步只消一对。本题关键一步是 ¬B ∨ A 与 ¬M ∨ B 在 B 上归结,得 ¬M ∨ A。读回蕴含就是 M ⟹ B ⟹ A 的传递性,课件在这一步旁边专门用红框补了解释。

回讲义:L03b-5 归结法

逐题拆解

Question 1:真值表

列头本身就是解题步骤。把复合公式拆成从内到外的子公式,一列一列算,最后一列才是答案。四行结果是 F / F / T / F,只有 A 假、B 真那一行成立。翻译成自然语言就是「A 能推出 B,但 B 推不出 A」,也就是 A 严格蕴含 B 而不等价。有个捷径:not(B ⟹ A) 为真要求 B 真且 A 假,这一条直接把答案锁死在第三行。考场时间紧时管用,但填表是给分点,正式作答还是把表写全。

一步一步看

目标:一列一列填真值表,看蕴含什么时候为假,取反和 and 怎样逐行算,最后只剩第 3 行为真。

表头六列,前两列 A、B 是四种真假组合,题目已给。后面四列从左到右一列一列填。每帧青绿框是这一步填的那一列,问号是还没填的列。

  1. 先填 A ⟹ B。蕴含只有前件真、后件假才为假,四行里只有第 2 行(A 真、B 假)是这样,填 F。A 为假的第 3、4 行是空真,直接填 T。

    Question 1 真值表第 1 步:A、B 两列已给,第三列 A ⇒ B 用青绿框标出,四行从上到下填 T、F、T、T,右边三列还是问号,底部说明只有第 2 行前真后假为 F

  2. 再填 B ⟹ A。这回 B 是前件,只有第 3 行 B 真、A 假,填 F,其余三行填 T。

    Question 1 真值表第 2 步:第四列 B ⇒ A 用青绿框标出,四行从上到下填 T、T、F、T,只有第 3 行 B 真 A 假为 F,右边两列还是问号

  3. not (B ⟹ A) 是把上一列逐行取反,T 变 F、F 变 T,得 F、F、T、F。

    Question 1 真值表第 3 步:第五列 not (B ⇒ A) 用青绿框标出,把 B ⇒ A 列逐行取反,四行从上到下填 F、F、T、F,最后一列还是问号

  4. 最后一列是第三列和第五列取 and,同一行两格都为 T 才为 T。只有第 3 行两格都是 T,答案 F / F / T / F。

    Question 1 真值表第 4 步:最后一列 (A ⇒ B) and not (B ⇒ A) 用青绿框标出,四行从上到下填 F、F、T、F,只有第 3 行 A 假、B 真时整个公式为真

插入练习:P ⇔ (Q ∧ R) 转 CNF

一个 ⇔ 必须拆成两个方向,P ⟹ (Q ∧ R) 和 (Q ∧ R) ⟹ P 各走一遍,最后得三个子句。课件把 ∧ 省掉直接编号列出,编号本身就代表合取。转换完顺手把子句读回自然语言,是最快的自查方式:「P 真则 Q 真、P 真则 R 真、Q 和 R 都真则 P 真」。

Question 2:前向链接与后向链接

唯一的坑在第三条规则的前件是 or。C ∨ B ⟹ M 先换成 ¬(C ∨ B) ∨ M,按德摩根变成 (¬C ∧ ¬B) ∨ M。再用分配律拆成 (¬C ∨ M) ∧ (¬B ∨ M),也就是两条 Horn 子句 C ⟹ M 和 B ⟹ M。前两条规则前件是 and,转换后本身就是单个子句,不用拆。转换完的规则清单是 (1) B ∧ C ⟹ A、(2) M ∧ C ⟹ B、(3) C ⟹ M、(4) B ⟹ M、(5) C。前向沿 (3) → (2) → (1) 推出 A,规则 (4) 一次都没用上。这正是前向「能推的都推、不管目标」的典型特征。后向从 A 倒着拆子目标,目标栈是 [A] → [B ∧ C] → [B] → [M ∧ C] → [M] → 已知,同样落到 C 上。

一步一步看:前向链接

目标:从已知事实 C 出发反复扫规则,看哪条先触发、新命题怎样加进集合,直到得出 A。

下面每帧左边是转换后的规则清单 (1)–(5),旁边写这条规则此刻的状态。底下一行是已知集合。青绿是这一步触发的规则和新加进集合的命题。

  1. 开始:(5) 是题目给的事实,C 进已知集合。扫一遍:(1) 缺 B,(2) 缺 M,(4) 缺 B,只有 (3) 的前件 C 已经齐了。

    前向链接开始帧:规则清单 (1) B∧C⇒A、(2) M∧C⇒B、(3) C⇒M、(4) B⇒M、(5) C,(5) 行用青绿框标出,已知集合只有 C,(1)(2)(4) 旁注缺 B、缺 M、缺 B,(3) 旁注前件已知可以触发

  2. 触发 (3) C ⟹ M,M 进已知集合,变成 {C, M}。

    前向链接第 1 次触发帧:(3) C⇒M 一行用青绿框标出,旁注 C 已知触发、M 进已知集合,底部已知集合是 C、M,新加入的 M 用青绿标出

  3. 再扫一遍:(2) 要 M 和 C,现在都在了。触发 (2),B 进已知集合,变成 {C, M, B}。

    前向链接第 2 次触发帧:(2) M∧C⇒B 一行用青绿框标出,旁注 M、C 都已知触发,底部已知集合是 C、M、B,新加入的 B 用青绿标出

  4. 再扫:(1) 要 B 和 C,都在了。触发 (1),A 进已知集合,目标出现,停。(4) 的前件 B 这时也有了,但它的结论 M 早就在集合里,整个过程没用上它。

    前向链接第 3 次触发帧:(1) B∧C⇒A 一行用青绿框标出,旁注得到目标 A,(4) 旁注 B 已知但结论 M 早就有了没用上,底部已知集合是 C、M、B、A,新加入的 A 用青绿标出

一步一步看:后向链接

目标:从目标 A 倒着找结论是它的规则,看目标怎样拆成子目标直到栈空,以及为什么不选 (4)。

规则清单不变,底下换成两行:「换过的目标」是已经被拆开的目标,「目标栈」是还要证的子目标。青绿是这一步用到的规则和栈里的新内容。

  1. 要证 A。结论是 A 的规则只有 (1),于是把 A 换成 B ∧ C,目标栈变成 [B ∧ C]。

    后向链接第 1 步:(1) B∧C⇒A 一行用青绿框标出,旁注要 A 成立先证 B∧C,换过的目标是 A,目标栈里是 B∧C,用青绿标出

  2. C 是 (5) 给的已知事实,不用再证,栈里只剩 B。

    后向链接第 2 步:(5) 已知事实 C 一行用青绿框标出,旁注 C 已知不用再证只剩 B,换过的目标是 A,目标栈里只剩 B

  3. 要证 B。结论是 B 的规则只有 (2),把 B 换成 M ∧ C。

    后向链接第 3 步:(2) M∧C⇒B 一行用青绿框标出,旁注要 B 成立先证 M∧C,换过的目标是 A、B,目标栈里是 M∧C

  4. C 已知,栈里只剩 M。

    后向链接第 4 步:(5) 已知事实 C 一行用青绿框标出,旁注 C 已知只剩 M,换过的目标是 A、B,目标栈里只剩 M

  5. 要证 M。用 (3) C ⟹ M,前件 C 已知,M 成立,栈空了。再一路返回:M 成立让 B 成立,B 成立让 A 成立。(4) 的结论也是 M,可它要先证 B,而 B 正是上面还在等的目标,选它会绕回去。

    后向链接第 5 步:(3) C⇒M 一行用青绿框标出,旁注 C 已知 M 成立栈清空,(1)(2) 旁注 A、B 依次成立,(4) 旁注要先证 B 会绕回去不选,换过的目标是 A、B、M,目标栈已空,A 得证

Question 3:归结反证

归结过程分四步。先用已知的 C 消掉所有 ¬C,得到 ¬B ∨ A、¬M ∨ B、M。再把 ¬B ∨ A 与 ¬M ∨ B 在 B 上归结,得 ¬M ∨ A。再与 M 归结得 A。最后 A 与 ¬A 得空子句。课件在第二步写了 “omit other irrelevant terms”,说明归结允许挑着做。子句 ¬B ∨ M 从头到尾没参与,因为它推不向目标。这一点和前向链接的「能推的都推」正好相反。

一步一步看

目标:把要证的结论取否加进子句集再逐次归结,看怎样推出空子句,从而证明 A 成立。

顶行是初始子句集,标签写明每个子句的来路。往下每一层是归结出来的新子句,连线连着它的两个亲本。青绿是这一步新得到的子句和它的两条连线。

  1. 先把要证的 C ⟹ A 写成 ¬C ∨ A,整体取否得 C ∧ ¬A。三条规则展开成四个子句,加上 C 和 ¬A,一共六个。

    归结反证第 0 步:顶行六个子句依次是已知 C、来自规则 (1) 的 ¬B∨¬C∨A、来自 (2) 的 ¬M∨¬C∨B、来自 (3) 的 ¬C∨M、来自 (4) 的 ¬B∨M、否定目标 ¬A,¬A 用青绿标出

  2. 用 C 消掉所有 ¬C:三个含 ¬C 的子句各和 C 归结一次,得 ¬B ∨ A、¬M ∨ B、M。这是三次归结,每次只消一对。

    归结反证第 1 步:C 用虚线分别连到三个含 ¬C 的子句下方,归结出 ¬B∨A、¬M∨B、M 三个新子句,用青绿标出,底部说明每次只消一对 C 与 ¬C

  3. ¬B ∨ A 和 ¬M ∨ B 在 B 上归结,B 与 ¬B 消掉,得 ¬M ∨ A。

    归结反证第 2 步:¬B∨A 与 ¬M∨B 两条青绿连线汇到新子句 ¬M∨A,底部说明读回蕴含就是 M ⇒ B ⇒ A 的传递

  4. ¬M ∨ A 和第一层的 M 归结,M 与 ¬M 消掉,得 A。这时子句集里同时有 A 和 ¬A。

    归结反证第 3 步:¬M∨A 与 M 两条青绿连线汇到新子句 A,底部说明现在子句集里同时有 A 和 ¬A

  5. A 和顶行的 ¬A 归结,什么都不剩,得空子句 □。子句集自相矛盾,A 得证。灰掉的 ¬B ∨ M 全程没参与。

    归结反证第 4 步:A 与顶行的 ¬A 两条青绿连线汇到空子句 □,旁注空子句,顶行 ¬B∨M 变灰表示全程没用上,底部说明 □ 代表矛盾所以 A 得证

课件里的坑

  • [读图提醒] 从 p.4 起每页左上角那个加粗的 Exercise 标题框和正文 Question 压在了一起,p.4、p.5、p.8、p.9、p.10、p.11、p.12 都有。这是占位框位置没调好造成的排版重叠,不是内容出错,把压住的几个字按上下文补回来即可。
  • [读图提醒] p.5 答案表第 2、3、4 行最后一列偏右、和上一行列宽没对齐,容易看成第 1 行只有一格。按四行四值 F / F / T / F 读。
  • [读图提醒] p.9 左侧规则清单的 (1) 那行有两组字叠着(“C ∨ B ⟹ M” 的残影压在 “(1) B ∧ C ⟹ A” 上),是动画层没清干净。
  • [读图提醒] p.12 版面挤得最厉害,第二步那行有一道当堂手画的红色下划线划在 “¬B ∨ A; ¬M ∨ B;” 下面——那是在提示这两个子句是下一步要归结的一对,不是修改标记。右侧红框的五行推导是对第二步的补充说明,不属于主流程。
  • [读图提醒] 每页右下角都印了页码,但印的数字比实际页序多 1(第 4 页印 5、第 7 页印 8、第 12 页印 13)。
  • [课件留白] p.8 列出的三种方法里 deduction 没有单独演示,Question 3 的归结就是它的一种具体实现。
  • [补充] 归结对命题逻辑是反驳完备的:子句集不可满足时反复归结必能得到空子句。但它不能用来枚举所有可推出的结论,只能验证某一个结论,所以天然配反证法用。
  • [补充] 三种方法都得到同一结论不是巧合,它们都是可靠(sound)的推理方法。差别只在效率和适用范围。

课后 10 分钟:考点复习

这 10 分钟怎么用:前 3 分钟读必背 7 条,重点是第 3、4、5 条这串形式转换链;中间 4 分钟把完整例题的 CNF 转换默写一遍;最后 3 分钟做变式题,先自己算再展开对照。

必背

  1. 蕴含 S1 ⇒ S2 等价于 ¬S1 ∨ S2,只有前件真、后件假这一种情况为假
  2. (A ⟹ B) and not (B ⟹ A) 只在 A 假、B 真时为真,刻画的是 A 严格蕴含 B 而不等价
  3. CNF 转换四步:消 ⇔ 拆成两个方向、消 ⟹ 换成 ¬前件 ∨ 后件、¬ 用德摩根往里推、∨ 对 ∧ 用分配律
  4. 前件是 or 的规则转 CNF 后会拆成两条 Horn 子句,前件是 and 的规则不拆
  5. Horn 子句要求每个子句至多一个正文字,前向和后向链接只能处理这种形状,归结不要求
  6. 前向链接从已知事实出发、前件全满足就把结论加入已知,是数据驱动;后向链接从目标出发换成子目标,是目标驱动
  7. 归结法要证 C ⟹ A,先写成 ¬C ∨ A 再取否定得到 C ∧ ¬A 加进子句集,归结出空子句即证毕

完整例题

题面:把 P ⇔ (Q ∧ R) 转成 CNF,写出完整过程和最终子句。

解法:

  1. 消 ⇔:P ⇔ (Q ∧ R) ≡ (P ⟹ (Q ∧ R)) ∧ ((Q ∧ R) ⟹ P)。两个方向都要写,漏一个就漏子句。
  2. 前一半消 ⟹:P ⟹ (Q ∧ R) ≡ ¬P ∨ (Q ∧ R)。
  3. 前一半用分配律:¬P ∨ (Q ∧ R) ≡ (¬P ∨ Q) ∧ (¬P ∨ R)。这里是 ∨ 遇到 ∧,所以用分配律,得两个子句。
  4. 后一半消 ⟹:(Q ∧ R) ⟹ P ≡ ¬(Q ∧ R) ∨ P。
  5. 后一半用德摩根:¬(Q ∧ R) ∨ P ≡ (¬Q ∨ ¬R) ∨ P ≡ ¬Q ∨ ¬R ∨ P。这里是 ¬ 遇到括号,所以用德摩根律,∨ 满足结合律,括号可去。
  6. 合起来:三个子句 ¬P ∨ Q、¬P ∨ R、¬Q ∨ ¬R ∨ P,它们之间是 ∧。

自查:把三个子句读回自然语言——P 真则 Q 真、P 真则 R 真、Q 和 R 都真则 P 真,和原式含义完全对得上。

答题格式:每一步注明用的是哪条定律(消 ⇔ / 消 ⟹ / 德摩根 / 分配律)。只写最终三个子句不写过程,看不出你是推出来的还是背下来的。

变式题(先自己做)

改编自课件 p.6–12。

(a) 把题目换成 P ⇔ (Q ∨ R),照同样流程走一遍,写出最终子句。和课件那题比,分裂成两个子句的是哪一半?

(b) 把 Question 2 的已知从「C 为真」改成「B 为真」,前向、后向、归结三种方法各走一遍,各自会在哪一步卡住?

(c) 为什么规则 (4) B ⟹ M 在原题一次都没用上,在 (b) 里却成了唯一能用的规则?这说明前向链接的什么性质?

提示

(a) 前一半的 ∨ 遇不到 ∧ 了,后一半的 ¬ 遇到的括号里是 ∨。(b) 先列出哪些命题能出现在规则的结论位置。(c) 想一想前向链接每一步的判据里有没有出现「目标」这个词。

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

判分点:① (a) 有没有写出定律名;② (b) 三种方法都要指出卡在哪;③ (c) 要点出「前向不看目标」。

(a) 前一半 P ⟹ (Q ∨ R) ≡ ¬P ∨ Q ∨ R,这次 ∨ 遇不到 ∧,是单个子句。后一半 (Q ∨ R) ⟹ P ≡ ¬(Q ∨ R) ∨ P ≡ (¬Q ∧ ¬R) ∨ P ≡ (¬Q ∨ P) ∧ (¬R ∨ P),分裂成两个。最终三个子句:¬P ∨ Q ∨ R、¬Q ∨ P、¬R ∨ P。分裂从前一半对调到了后一半。

(b) 三种都证不出 A,卡点是同一个:C 从来不出现在任何规则的结论位置,没有规则能推出它。前向从 {B} 出发,用 (4) 得到 M,已知集合停在 {B, M};(1) 要 B ∧ C、(2) 要 M ∧ C、(3) 要 C,全都缺 C,再推不出新东西。后向从 [A] 展开到 [B ∧ C],B 已知、C 成了子目标,而没有规则的结论是 C,这个子目标无法展开也不是已知事实,分支失败。归结方面,取 C 为假、A 为假、B 为真、M 为真就是一个模型:(1) 和 (2) 因前件含 C 而空真,(3) 空真,(4) 后件 M 真。子句集可满足,归结不出空子句。

(c) 前向链接每一步的判据只有「这条规则的前件是否全部被证出」,判据里没有目标。原题 C 已知,(3) 先推出了 M,(4) 的结论 M 已在已知集合里,所以它没派上用场;变式里 C 缺失,(3) 用不了,反倒只剩 (4) 能触发。这就是前向「能推的都推、会产出与目标无关的中间结论」的性质,也是后向链接要改进的地方。

闪卡自测

1. 默写蕴含的两条判定规则,并解释「前件为假则整个蕴含为真」。

正向:S1 ⇒ S2 为真当且仅当 S1 为假或 S2 为真。反向:为假当且仅当 S1 真且 S2 假。前件为假时按正向规则第一个条件已满足,直接判真,不用看后件(p.4)。

2. 不查表,说出 (A ⟹ B) and not (B ⟹ A) 在哪一行为真,含义是什么。

只在 A 假、B 真时为真。合取要两边真,not(B ⟹ A) 为真要求 B ⟹ A 为假,即 B 真且 A 假。含义是 A 严格蕴含 B 而不等价(p.5)。

3. 写出 CNF 的定义,以及归结为什么必须先转 CNF。

若干子句用 ∧ 连接,每个子句内部是若干文字用 ∨ 连接。归结规则的形式是 (α ∨ P) 与 (β ∨ ¬P) 消去互补文字得 (α ∨ β),它只接受子句作为输入,所以 CNF 是硬性前置(p.6、p.11)。

4. 规则「C or B ⟹ M」转 CNF 后为什么变成两条?换成 and 会是几条?

前件取否后 ¬(C ∨ B) 按德摩根变成 ¬C ∧ ¬B,与 M 之间是 ∨,用分配律拆成 (¬C ∨ M) ∧ (¬B ∨ M),两条。换成 and 时 ¬(C ∧ B) 变成 ¬C ∨ ¬B,整体已是单个子句,一条(p.9)。

5. 什么是 Horn 子句?为什么链接法要求它、归结不要求?

至多含一个正文字的子句。链接法每步要求结论唯一确定,两个正文字时不知道该把哪个加进已知集合。归结只消互补文字,对任意 CNF 都适用(p.9、补充)。

6. 写出本题前向链接的已知集合演化,指出哪条规则没用上。

{C} → {C, M} → {C, M, B} → {C, M, B, A},沿 (3) → (2) → (1)。规则 (4) B ⟹ M 没用上,它的结论 M 已经先被 (3) 推出来了(p.9)。

7. 写出本题后向链接的目标栈演化。

[A] → [B ∧ C] → [B] → [M ∧ C] → [M] → 已知。每步把目标换成证它所需的子目标,C 是已知事实所以直接落地(p.10)。

8. 列表对比前向与后向:起点、每步动作、终止、是否做无用功。

前向起点是已知事实,每步把前件全满足的规则的结论加入已知,终止于目标出现在已知集合,会做无用功。后向起点是待证目标,每步把目标换成子目标,终止于所有子目标落到已知,只展开相关分支(p.9、p.10)。

9. 归结要证 C ⟹ A,加进子句集的否定形式是什么?为什么是它?

C ∧ ¬A。要证的命题写成子句是 ¬C ∨ A,整体取否按德摩根得 C ∧ ¬A,即把 C 和 ¬A 两个子句加进去。C 本来已知,实际新增的只有 ¬A(p.12)。

10. 复现归结第二步:¬B ∨ A 与 ¬M ∨ B 归结得什么?读回蕴含是什么意思?

在 B 上归结得 ¬M ∨ A。读回蕴含:¬M ∨ B 是 M ⟹ B,¬B ∨ A 是 B ⟹ A,于是 M ⟹ B ⟹ A,即 M ⟹ A。这就是传递性在归结里的样子(p.12)。

11. 归结出空子句为什么等于证明成功?

空子句无法被满足,归结出它说明「前提 ∧ 目标的否定」这个子句集不可满足,即前提成立时目标的否定不可能成立,所以目标成立(p.11–12)。

下一步

三道题共用同一组规则是这份材料的设计,不要分开做。找一张纸横着画三栏,把前向、后向、归结的每一步并排写下来,对照同一个事实(比如 M)在三种方法里分别是第几步出现的。CNF 转换是后两题的地基,把 P ⇔ (Q ∨ R) 的变式做完,再做一个带三层嵌套的(比如 (P ∧ Q) ⇔ (R ∨ S)),这一关就稳了。归结最容易在「取否定」那步出错,练法是把目标依次换成 M、B、¬A,每次先写要证命题的子句形式,再写它的否定,最后才归结——前两步分开写,错误率明显下降。这次三道题的规则里都没有变量,复习知识表示那一讲时注意区分命题逻辑和一阶逻辑:后者的归结还要多一步合一(unification),本次没涉及。

下一讲 →
L06a L06a 逻辑回归:一个 sigmoid 神经元

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