
10 分证明题保姆级教程——线性归结法,看一遍就会
这道题看起来符号很多很吓人,其实就干一件事:找矛盾。下面我一步一步带着你走,保证你看完就会做。
一、先看题目长什么样
题目给了 4 个公式,最后让你证明它们能推出结论 B。
这 4 个公式里有一堆符号:∀(所有)、∃(存在)、→(如果...那么)、∧(且)、∨(或)、¬(非)。
别慌!这些符号只是"包装纸",拆开看就是人话。
二、做题就两步
不管题目多复杂,归结法证明题就只有两步:
第一步:翻译——把题目里的公式翻译成"子句"(一种标准格式)
第二步:消消乐——像玩消消乐一样,两个子句里一正一反的配对消掉,直到消出"矛盾"
下面一步一步来。
三、第一步:翻译(写子句集)
翻译规则(记住这 3 条就够了)
规则 1:"如果 P 那么 Q" 变成 "非P 或 Q"
比如:"如果下雨那么地湿" 变成 "不下雨 或 地湿"
规则 2:"存在一个 x" 用一个具体的名字代替
比如题目说"存在某个 x",我们就用字母 a 来代表它。
规则 3:"存在一个 y,但 y 跟着 x 变" 用一个函数代替
比如用 f(x) 表示"跟着 x 变化的那个 y"。
开始翻译
翻译 A1
原公式:对所有 x,(D(x) 且 非E(x)) → 存在 y,(F(x,y) 且 H(y))
第 1 小步:消掉"如果...那么..."
→ 变成"非...或..."
得到:对所有 x,非(D(x) 且 非E(x)) 或 存在 y,(F(x,y) 且 H(y))
第 2 小步:把"非(A 且 B)"拆开
→ 变成"非A 或 B"
得到:对所有 x,(非D(x) 或 E(x)) 或 存在 y,(F(x,y) 且 H(y))
第 3 小步:处理"存在 y"
→ y 跟着 x 变,用 f(x) 代替 y
→ 把"且"拆开,变成两个独立句子
得到两个子句:
子句 1:非D(x) 或 E(x) 或 F(x, f(x))
子句 2:非D(x) 或 E(x) 或 H(f(x))
翻译 A2
原公式:存在 x,D(x) 且 G(x) 且 对所有 y,(F(x,y) → G(y))
第 1 小步:"存在 x"用 a 代替
第 2 小步:把"如果...那么..."消掉
→ F(x,y) → G(y) 变成 非F(x,y) 或 G(y)
第 3 小步:把"且"拆开
得到三个子句:
子句 3:D(a)
子句 4:G(a)
子句 5:非F(a, y) 或 G(y)
翻译 A3
原公式:对所有 x,非E(x) 或 非G(x)
→ 已经是子句了,不用翻译
子句 6:非E(x) 或 非G(x)
翻译结论的否定
结论 B:存在 x,H(x) 且 G(x)
我们要假设结论是错的,所以对 B 取反:
→ 对所有 x,不是(H(x) 且 G(x))
→ 用德摩根拆开:对所有 x,非H(x) 或 非G(x)
子句 7:非H(z) 或 非G(z)
7 个子句总览(写在这,后面要用)
编号 子句 哪里来的1 非D(x) 或 E(x) 或 F(x, f(x)) A1
2 非D(x) 或 E(x) 或 H(f(x)) A1
3 D(a) A2
4 G(a) A2
5 非F(a, y) 或 G(y) A2
6 非E(x) 或 非G(x) A3
7 非H(z) 或 非G(z) 结论取反
四、第二步:消消乐(归结推理)
消消乐的规则(超简单)
找两个子句:
一个里面有 P
另一个里面有 非P
把它们消掉,剩下的内容拼起来,就是一个新子句。
就像解方程:x + 3 = 5 和 -x + 2 = 1,把 x 和 -x 消掉。
开始消!
我们从子句 7(结论的反面)开始,一步步消:
第 1 步
子句 7: 非H(z) 或 非G(z)
子句 2: 非D(x) 或 E(x) 或 H(f(x))
找配对:子句 7 有"非H",子句 2 有"H"。消掉!
让 z = f(x),剩下的拼起来:
→ 得到:非D(x) 或 E(x) 或 非G(f(x))
第 2 步
上一步得到: 非D(x) 或 E(x) 或 非G(f(x))
子句 6: 非E(x) 或 非G(x)
找配对:一个有"E(x)",一个有"非E(x)"。消掉!
剩下的拼起来:
→ 得到:非D(x) 或 非G(f(x)) 或 非G(x)
第 3 步
上一步得到: 非D(x) 或 非G(f(x)) 或 非G(x)
子句 3: D(a)
找配对:一个有"非D",一个有"D"。消掉!
让 x = a,剩下的拼起来:
→ 得到:非G(f(a)) 或 非G(a)
第 4 步
上一步得到: 非G(f(a)) 或 非G(a)
子句 4: G(a)
找配对:一个有"非G(a)",一个有"G(a)"。消掉!
剩下的:
→ 得到:非G(f(a))
第 5 步
上一步得到: 非G(f(a))
子句 5: 非F(a, y) 或 G(y)
找配对:一个有"非G",一个有"G"。消掉!
让 y = f(a),剩下的:
→ 得到:非F(a, f(a))
第 6 步
上一步得到: 非F(a, f(a))
子句 1: 非D(x) 或 E(x) 或 F(x, f(x))
找配对:一个有"非F",一个有"F"。消掉!
让 x = a(此时 f(x) = f(a)),剩下的:
→ 得到:非D(a) 或 E(a)
第 7 步
上一步得到: 非D(a) 或 E(a)
子句 3: D(a)
找配对:一个有"非D(a)",一个有"D(a)"。消掉!
剩下的:
→ 得到:E(a)
第 8 步
上一步得到: E(a)
子句 6: 非E(x) 或 非G(x)
找配对:一个有"E(a)",一个有"非E"。消掉!
让 x = a,剩下的:
→ 得到:非G(a)
第 9 步
上一步得到: 非G(a)
子句 4: G(a)
找配对:一个有"非G(a)",一个有"G(a)"。消掉!
什么都没了 = 矛盾!
五、写答案(考试就这么写)
证明:
假设结论不成立,即 ¬B:对所有 z,非H(z) 或 非G(z)
将前提化为子句集:
(1) 非D(x)∨E(x)∨F(x,f(x))
(2) 非D(x)∨E(x)∨H(f(x))
(3) D(a)
(4) G(a)
(5) 非F(a,y)∨G(y)
(6) 非E(x)∨非G(x)
(7) 非H(z)∨非G(z) (¬B)
归结过程:
(8) 非D(x)∨E(x)∨非G(f(x)) ((7)(2) 归结,消 H)
(9) 非D(x)∨非G(f(x))∨非G(x) ((8)(6) 归结,消 E)
(10) 非G(f(a))∨非G(a) ((9)(3) 归结,消 D)
(11) 非G(f(a)) ((10)(4) 归结,消 G(a))
(12) 非F(a,f(a)) ((11)(5) 归结,消 G)
(13) 非D(a)∨E(a) ((12)(1) 归结,消 F)
(14) E(a) ((13)(3) 归结,消 D(a))
(15) 非G(a) ((14)(6) 归结,消 E)
(16) NIL(空子句) ((15)(4) 归结,消 G(a))
推出矛盾,假设不成立,原命题得证。证毕。
六、记住一句话
归结法 = 翻译 + 消消乐 + 推出矛盾 = 证完了。
考试时就写:先写 7 个子句,再写 9 步归结,最后写"推出矛盾,证毕"。10 分到手。
有不会的题直接发给我,我来给你拆解。
关注我,每天用大白话讲清楚 AI 的核心概念和考题。
中承配资提示:文章来自网络,不代表本站观点。