当前位置:文档之家› 人工智能第4章(推理技术)

人工智能第4章(推理技术)

(x) (y)( ($z)(A(x,z)∧A(y,z)) ($u)B(x,y,u))
=(x) (y)( ~(($z)(A(x,z)∧A(y,z)))∨($u)B(x,y,u))
=(x) (y)( (z)(~A(x,z)∨~A(y,z) )∨($u)B(x,y,u)) =(x) (y)( (z)(~A(x,z)∨~A(y,z) )∨B(x,y,f(x,y))
基本的出发点:要证明一个命题 为真都可以通过证明其否命题为 假来得到 将多样的推理规则简化为一个— 消解
鲁滨逊
什么叫消解
析取联接词,类似“或”
PQ
﹁P R 亲本子句
QR
消解式
消解式是亲本子 句的逻辑结论
消解只能在仅含否定和析取联接词的公式(子句) 间进行 必须先把公式化成规范的形式(范式,子句集)
( $ x)Q(x) ( $ y)Q(y) Skolemnizing),两种情况:
存在量词不在全称量词的辖域内 —— 用新的个 体常量替换受存在量词约束的变元 存在量词在全称量词的辖域内 Skolem函数,即具体化函数
( x ) P ( x ) ( $ y ) Q ( y ) ( x ) P( x ) Q ( a ) ( x 1 )( x 2 )...( x n )( $ y ) P ( x 1, x 2 ,..., x n , y ) ( x 1)( x 2 )...( x n ) P ( x 1, x 2 ,..., x n , f ( x 1, x 2 ,..., x n ))
什么叫消解
例 1:
小王说他下午或者去图书馆或者在家休息 小王没去图书馆 R—小王下午去图书馆 S—小王下午在家休息
RS 例 2: ﹁R

S
﹁ P→Q P Q ﹁P
如果今天不下雨,我就去你家 今天没有下雨
含变量的消解
例:苏格拉底论断
凡人都会死. x (Man (x) Mortal (x)) 苏格拉底是人. Man (Socrates) 如何得到结论:苏格拉底会死. Mortal(Socrates)
斯科伦函数 w = g ( x )
⑤ 化成前束范式
⑥ 化成前束合取范式 分配律: P∨(Q∧R) = (P∨Q)∧(P∨R)
注:使用分配律两次
⑦ 消去全称量词或者前束
⑧ 消去合取符号,得到子句
⑨ 变量改名,使得变量不相同,得到子句集
消解式的定义
命题逻辑的消解式
设C1与C2是子句集中的任意两个子句,如果C1中的文字L1与 C2中的文字L2互补,那么从C1和C2中分别消去L1和L2,并将 两个子句中余下的部分析取,构成一个新子句C12,则称这一 过程为消解,称C12为C1和C2的消解式,C1,C2为C12的亲 本子句 例:子句 C1=P∨C1' C2=~P∨C2' 消解式 C12=C1'∨C2'
= (x) (y) (z)(~A(x,z)∨~A(y,z) ∨B(x,y,f(x,y)))
子句
例3:
((x)P(x)∨($y)Q(y)) (x)R(x)
=~((x)P(x)∨($y)Q(y)) ∨ (x)R(x)
=(~(x)P(x)∧~($y)Q(y)) ∨ (x)R(x) =( ($x)(~P(x))∧(y)(~Q(y))) ∨ (x)R(x)




Artificial Intelligence (AI)
第4章 推理技术
4.1 消解原理
推理是如何进行的?
推理过程多种多样 例 1:
如果今天不下雨,我就去你家 今天没有下雨
例 2:
小王说他下午或者去图书馆或者在家休息 小王没去图书馆
计算机如何选择?
消解原理(归结原理)
美国数学家鲁滨逊 提出消解原理(1965年)
“快乐的人过着激动人心的生活”
(∀z) (Happy(z)→Exciting(z))
目标“李明过着激动人心的生活”的否定
~Exciting(Liming)
消解反演示例—“激动人心的生活”问题
将上述谓词公式转化为子句集如下: (1) Poor(x)∨~Smart(x)∨Happy(x) (2) ~Read(y)∨Smart(y) (3) Read(Liming) (4) ~Poor(Liming) (5) ~Happy(z)∨Exciting(z) (6) ~Exciting(Liming) (结论的否定)
F2的前束合取范式和子句集: ($x)(C(x)∧O(x)) = (C(a)∧O(a)) 子句集={ C(a), O(a) }
~L 的前束范式和子句集: ~($x)(O(x)∧R(x))
= (x)(~O(x)∨~R(x))
子句集={~O(x)∨~R(x)}
构成子句集(注意改名) { ~C(x)∨W(x), ~C(y)∨R(y),
例:求Skolem函数(斯柯伦范式)
$x y z $u v $w A(x,y,z,u,v,w)
(用a替代x,删除$x)
= y z $u v $w A(a,y,z,u,v,w) (用f(y,z)代替u,删除$u) = y z v $w A(a,y,z, f(y,z),v,w) (用h(y,z,v)代替w,删除$w) = y z v A(a,y,z, f(y,z),v,h(y,z,v))
L: ($x)(O(x)∧R(x)) 试证:L是F1,F2的逻辑结果,即F1∧F2L
证明:
利用消解原理来构造F1∧F2∧~L的一个反演
首先分别求出F1,F2和 ~L 的子句集
F1的前束合取范式与子句集: (x)(C(x)(W(x)∧R(x)) = (x)(~C(x)∨(W(x)∧R(x)) = (x)((~C(x)∨W(x) )∧(~C(x)∨R(x))) 子句集={ ~C(x)∨W(x) , ~C(x)∨R(x) }(未改名)
~Happy(z)∨Exciting(z)
消解原理的局限性
消解原理推进了用逻辑方法进行机器证明的研究,使得 自动定理证明领域发生了质的变化。 但是
要求把逻辑公式转化为某种范式,丧失了其固有的逻辑 蕴含语义y)(~Q(y))) ∨ (z)R(z) (改名)
=( ($x)(~P(x))∧(y)(~Q(y))) ∨ (z)R(z) = ( (~P(a))∧(y)(~Q(y))) ∨ (z)R(z) (消去存在量词) = (y) (z)(( ~P(a)∧ ~Q(y)) ∨ R(z) ) (化成前束范式)
{P(x), P(a)}的最一般的合一者为 {a/x} c’1= Q(x) c’2= R(y)
则c1, c2的消解式为 c=Q(a)∨R(y)
怎么利用消解原理进行证明?
消解反演 通俗的说就是“反证法”
要证命题A恒为真,等价于证﹁A恒为假
证明过程
否定结论R,得﹁R ; 把﹁R添加到已知前提集合F中去; 把新产生的集合{ ﹁R ,F}化成范式; 应用消解原理,不断求消解式,直到得到一个表示矛 盾的空子句
一阶谓词逻辑的消解式
设C1与C2是两个没有相同变元的子句,L1和L2分别是C1和C2 中的文字,若σ是L1和~L2的最一般合一者,则称 C12=(C1σ - {L1σ})∪(C2σ - {L2σ}) 为C1和C2的二元消解式,L1和L2为消解式上的文字
例:
设c1 = P(x) ∨ Q(x), c2 = ~P(a) ∨ R(y)
5) 化为前束形式 把全称量词提到最外层 前束形:= (前缀) {母式} ↑ ↑
全称量词串 无量词公式
6) 把母式化为合取范式 7) 消去全称量词 8) 消去连词符号∧,写成子句集 9) 变量分离标准化 改变变量名称,使一个变量符号不出现在一个 以上的子句中
例1: (x)A(x) ($x)B(x)

φ
⑥⑦
消解反演示例—“激动人心的生活”问题
假设:所有不贫穷并且聪明的人都是快乐的,那 些看书的人是聪明的。李明能看书且不贫穷,快 乐的人过着激动人心的生活。 求证:李明过着激动人心的生活。 解:先定义谓词: Poor(x) x是贫穷的 Smart(x) x是聪明的 Happy(x) x是快乐的 Read(x) x能看书 Exciting(x) x过着激动人心的生活
仔细分析量词的辖域
= ~(x)A(x)∨($x)B(x) (消去“蕴含”)
= ($x) (~A(x))∨($x)B(x) (“非”直接作用谓词符号)
= ($ x) (~A(x) ) ∨ ($z) B(z) (改名)
= ~A(a)∨B(b) (消去存在量词)
子句集= { ~A(a)∨B(b) }
例 2:
(1)子句定义 任何文字的析取式称为子句 不包含任何文字的子句称为空子句(空子句是永假的) 由子句构成的集合称为子句集 例:{P(x)∨Q(x) , ~P(x,f(x))∨Q(x,g(x)) }
(2)谓词演算公式化为子句式 任何一个谓词演算公式可以化为一个子句集合 步骤: 1) 消去蕴涵符号 用~A∨B代换A→B 2) 把非号~移入内层
要完成消解还面临几个问题
“”和“ ”必须消去
Man (x) Mortal (x) Man (x) Mortal “”怎么办?
化为子句集 置换与合一
如果能消去“”,Man (x) 和Man (Socrates)也不能构成互补对,形式不一样, 怎么办?
化子句集
相关概念
文字:原子公式及其否定统称为文字 子句集
~ (P Q) = ~ P ~ Q ~ (P Q) = ~ P ~ Q ~ ( x)P = ( $x) ~ P ~ ($ x)P = ( x) ~ P
3)对变量标准化 改变变量名,使不同的变量不同名
( x)P(x) ( x)P(x) 4)消去存在量词(具体化
1. 2.
从父子句求消解式的若干例子
相关主题