人工智能 第3章 推理技术1分析

2018/10/12 《人工智能》 8
7.一些重要的永真蕴含式
化简式：P Q P, P Q Q 附加式：P P Q,Q P Q 析取三段论：P,P Q Q 假言推理：P,P Q Q 拒取式：Q,P Q P 假言三段论：P Q,Q R P R 二难推论：P Q,P R,Q R R 全称固化：(x)P(x) P(y) 存在固化：(x)P(x) P(a)
2018/10/12 《人工智能》 11
令θ= {t1/x1,t2/x2,…,tn/xn}为一个代换，F为表达 式，则Fθ表示对F用ti代换xi后得到的表达式。 Fθ称为F的特例。 规则: 事实: IF father(x,y) and man(y) THEN son(y,x) father(李四，李小四) and man(李小四)
《人工智能》
5
4. 连接词 非：¬ ；析取：∨；合取：∧；蕴含：→； 双向蕴含：
谓词逻辑真值表
P T T F F
2018/10/12
Q T F T F
¬ P
F F T T
P∨Q T T T F
P∧Q T F F F
P→Q T F T T
P Q T F F T
6
《人工智能》
5. 谓词公式 (well formed formulas) 定义： 按下述规则得到的合式公式： (1) 单个谓词是合式公式，称为原子公式； (2) 若A是合式公式，则 A 也是合式公式； (3) 若A，B是合式公式，则 A B, A B, A B, A B 都是合式公式； (4) 若A是合式公式，x是任一个体变元，则 (x) A,(x) A 都是合式公式； (5) 运用有限步上述规则得到的公式是合式公式。
2018/10/12 《人工智能》 20
3.1.1 化为子句集（2）
(3)对变量标准化 ：使不同量词约束的变元有不同的名字， 通过变量更名来完成。例如，上式经变换后
(x)((y)P(x, y)(z)(Q(x, z) R(x, z)))
(4)消去存在量词：分两种情况
a）存在量词不出现在全称量词的辖域内，则只要用一个新 的个体常量替换受该量词约束的变元。 b）存在量词位于一个或者多个全称量词的辖域内，此时要用 Skolem函数f(x1,x2,…,xn)替换受该存在量词约束的变元。 上式中存在量词(y)及(z)都位于(x)的辖域内，所以需要 用Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和 g(x)，则替换后得到
《人工智能》 19
2018/10/12
3.1.1 化为子句集
在进行消解过程之前, 首先需要将谓词演算公式化为一 个子句集。其变换过程由下列几个步骤组成： (1)消去蕴涵符号： 等价关系P Q P Q 例如： (x)((y)P(x, y) (y)(Q(x, y) R(x, y)))
F=father(x,y) ∧ man(y) θ= {李四/X,李小四/Y} Fθ= father(李四，李小四) ∧ man(李小四) 结论: son(李小四,李四)
2018/10/12 《人工智能》 12
代换的复合
定义 设
θ= {t1/x1,t2/x2,…,tn/xn} λ= {u1/y1,u2/y2,…,um/ym} 是两个代换，则这两个代换的复合也是一个代换，它是从 {t1λ/x1,t2λ/x2,…,tnλ/xn,u1/y1,u2/y2,…,um/ym} 中删去如下两种元素： tiλ/xi 当tiλ=xi ui/yi 当yi∈{x1,x2,…,xn} 后剩下的元素所构成的集合，记为θ°λ 。 tiλ表示对ti运用λ进行代换。 θ°λ就是对一个公式F先运用θ进行代换，然后再运用 λ进行代换：F（ θ°λ ）=（F θ）λ
2018/10/12
《人工智能》
7
6.一些重要的等价式
交换律：P Q Q P 结合律：(P Q) R P (Q R) 分配律：P (Q R) (P Q)(P R) 德.摩根律： (P Q) P Q 双重否定律：P P 吸收律：P (P Q) P 补余律：P P T,P P F 连接词化归律：P Q P Q, P Q (P Q)(Q P)

不确定性匹配是指两个知识模式不完全一致，但是 它们的相似程度又在规定的限度内。
2018/10/12
《人工智能》
10
变量代换
定义 代换是一个有限集合 {t1/x1,t2/x2,…,tn/xn} 其中t1,t2,…,tn是项，项可以是常量、变量、函数； x1,x2,…,xn是互不相同的变元; ti/xi表示用ti代换 xi ; 一个合法的代换不允许ti与xi相同，也不允许变元xi 循环地出现在另一个tj中。例如： {a/x,f(b)/y,w/z}是一个代换 {g(y)/x,f(x)/y}不是代换
2018/10/12 《人工智能》 13
代换复合的例子
设有代换
θ= {f(y)/x,z/y} λ= {a/x,b/y,y/z} 则 θ°λ={f(y)λ/x, zλ/y, a/x, b/y, y/z} ={f(b)/x, y/y, a/x, b/y, y/z} ={f(b)/x,y/z}
Biblioteka Baidu
2018/10/12
《人工智能》
14
公式集的合一
定义 设有公式集F={F1,F2,…,Fn}，若存在一个代换λ使 得 F1λ=F2λ=…=Fnλ 则称λ为公式集F的一个合一，且称F1,F2,…,Fn是可 合一的。 设有公式集 F={P(x,y,f(y)),P(a,g(x),z)} 则下式是它的一个合一： λ={a/x,g(a)/y,f(g(a))/z} 一个公式集的合一一般不唯一。
2018/10/12 《人工智能》 18
3.1 消解原理
消解原理也叫做归结原理。主要内容包括子句集的求取、 消解推理的规则和消解反演问题求解方法。
消解原理的基础知识：




在谓词逻辑中，把原子谓词公式及其否定统称为 文字。 例如： P(x), ¬P(x,f(x)) 任何文字的析取式称为子句（clause）。 例如： P(x)∨Q(x), ¬ P(x,f(x))∨Q(x,g(x)) 不包含任何文字的子句称为空子句。 合取范式：若干子句的合取（and） 例如： C1 ∧C2 ∧C3… ∧Cn 子句集： S= {C1 ,C2 ,C3… ,Cn}
(x)((y)P(x, y) (y)(Q(x, y) R(x, y))) (x)((y)P(x, y) (y)(Q(x, y) R(x, y)))
(2)减少否定符号的辖域：每个否定符号“¬”最多只用到 一个谓词符号上，即利用等价关系把“¬”移到紧靠谓 词的位置上。上式经等价变换后 (x)((y)P(x, y) (y)(Q(x, y) R(x, y))) (x)((y)P(x, y) (y)(Q(x, y) R(x, y)))
2018/10/12 《人工智能》 9
模式匹配


所谓模式匹配是指对两个知识模式(例如两个谓词公 式)进行比较，以检查这两个知识模式是否完全一致 或者近似一致。 模式匹配可分为确定性匹配与不确定性匹配。 确定性匹配是指两个知识模式完全一致，或者经过 变量代换后变得完全一致。例如：
规则: IF father(x,y) and man(y) THEN son(y,x) 事实: father(李四，李小四) and man(李小四) 代换：θ= {李四/X,李小四/Y} 结论：son(李小四,李四)
2018/10/12
《人工智能》
3
谓词逻辑基本概念
1. 一个谓词分为谓词名与个体两个部分。 谓词名刻画个体的性质、状态或个体间的关系。 个体表示独立存在的事物或者概念。 例如： Teacher(zhang)，Greater(5,3) 谓词的一般形式 P (x1, x2,…,xn) 其中，P是谓词名，x1, x2,…,xn是个体。谓词名通常用大 写的英文字母表示，个体通常用小写的英文字母表示。该 谓词是一个原子谓词公式。
最一般合一是唯一的。
2018/10/12 《人工智能》 16
求取最一般合一
差异集：两个公式中相同位置处不同符号的集合。 例如：F1:P(x,y,z), F2:P(x,f(a),h(b)) 则D1={y,f(a)}, D2={z,h(b)} 求取最一般合一的算法： 1. 令k=0,Fk=F, σk=ε。 ε是空代换。 2. 若Fk只含一个表达式，则算法停止，σk就是最一般合一。 3. 找出Fk的差异集Dk。 4. 若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk中出 现，则置： Fk+1=Fk{tk/xk} σK+1=σk°{tk/xk} k=k+1 然后转(2)。若不存在这样的xk和tk则算法停止。 5. 算法终止，F的最一般合一不存在。
2018/10/12 《人工智能》 15
最一般的合一
定义 设σ是公式集F的一个合一，如果对任一个合一θ都 存在一个代换λ，使得θ=σ°λ，则称σ是一个最一般的 合一。 代换过程是一个用项（常数，函数，变量）代替变元 的过程，因此是一个从一般到特殊的过程。
F= P(x,y) ∧ Q(y) θ= {a/x,f(z)/y} Fθ=P(a,f(z)) ∧ Q(f(z))
(x)(P(x, f (x))(Q(x, g(x)) R(x, g(x)))
2018/10/12 《人工智能》 21
3.1.1 化为子句集（3）
(5)化为前束形 ：把所有全称量词移到公式的左边，并使 每个量词的辖域包括这个量词后面公式的整个部分。
所得公式称为前束形。
(x)(P(x, f (x))(Q(x, g(x)) R(x, g(x)))
第3章 推理技术
本章主要内容：




3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8
消解原理 规则演绎系统 产生式系统 基于概率的推理 可信度方法 证据理论 模糊推理(cut) 非单调推理
2018/10/12
《人工智能》
2
推理方式及其分类
1. 演绎推理、归纳推理、默认推理 演绎推理：从一般到特殊。例如三段论。 归纳推理：从个体到一般。 默认推理：缺省推理，在知识不完全的情况下假设某 些条件已经具备所进行的推理。 2. 确定性、不确定性推理 3. 单调性、非单调推理 推出的结论是否单调增加。 4. 基于知识的推理、统计推理、直觉推理

2018/10/12 《人工智能》 17
求取最一般合一的例子
例如，设 F={P(a,x,f(g(y))),P(z,f(z),f(u))} 求其最一般合一。 令F0=F, σ0=ε。F0中有两个表达式，所以σ0不是最一般合一。 差异集：D0={a,z}。代换： {a/z} F1= F0 {a/z}={P(a,x,f(g(y))),P(a,f(a),f(u))} 。 σ1=σ0°{a/z}={a/z} 差异集： D1={x,f(a)} 。代换： {f(a)/x} F2=F1{f(a)/x}={P(a,f(a),f(g(y))),P(a,f(a),f(u))} 。 σ2=σ1°{f(a)/x}={a/z,f(a)/x} 差异集： D2={g(y),u} 。代换： {g(y)/u} F3=F2{g(y)/u}={P(a,f(a),f(g(y))),P(a,f(a),f(g(y)))} 。 σ3=σ2°{g(y)/u}={a/z,f(a)/x,g(y)/u} F3=Fσ3
2018/10/12
《人工智能》
4
2. 个体可以是常量、变元或者函数。 例如： Less(x,5),x是一个变元。 Teacher(father(wang)),其中father(wang)是一 个函数。 3.谓词的语义由人指定。 例如： S(x)可以表示x是一个人；也可以表示x是一朵花
2018/10/12