谓词逻辑与归结原理2.ppt

人工智能基础归结
推理谓词逻辑苏格拉底三段论:“所有的人都是要死的,苏格拉底是人,所以苏格拉底是要死的”。论证应该是成立的,但是不能用命题逻辑来论证。若设P:所有的人都是要死的,Q:苏格拉底是人,R:苏格拉底是要死的。但是(PQ)R不是永真式。P:张三是大学生,Q:李四是大学生都是原子命题,只能用不同的符号来表示,这样就不能揭示出这两个命题的共同特性。谓词的概念和表示命题是一个陈述句，它一般可分成主语和谓语两部分。有时还需要用到量词。主语一般是可以独立存在的物体,称为个体(客体),用来刻划个体的性质或关系的词称为谓语(谓词)。通常用大写字母表示谓词，而用小写字母表示客体。例.设有下列命题:(1)张三是大学生;李四是大学生;(2)地球绕着太阳转;(3)上海在北京与广州之间。用谓词表示之。(1)设P:张三是大学生,Q:李四是大学生。这是两个不同的命题,但有相同的谓语____…是大学生。若设A:…是大学生，a:张三,b:李四,则A(a)(或A(张三)):张三是大学生,A(b)(或A(李四)):李四是大学生。(2)地球绕着太阳转;若设B:绕着转,x:地球,y:太阳,则B(x,y):地球绕着太阳转#注意:B(y,x):太阳绕着地球转。B(y,x)与B(x,y)是不同的命题。(3)上海在北京与广州之间。若设Z:…在…与…之间,s:上海,b:北京,g:广州,则Z(s,b,g):上海在北京与广州之间。刻划一个个体的性质的谓词A(c)称为一元谓词，刻划二个个体间关系的谓词A(a,b)称为二元谓词,…,刻划n个个体间关系的谓词A(a1,a2,…,an,)称为n元谓词。通常，一元谓词表示客体的性质，而多元谓词表示客体之间的关系。n元谓词中个体出现的次序一经约定，就是完全确定的,不可以随意改变。谓词也分谓词常量和谓词变元,这里仅讨论谓词常量。当谓词A(a1,a2,…,an,)中的个体名称用具体的n个个体替代得到的式子称为谓词填式。引入符号“”称为全称量词,“”称为存在量词,统称为量词(Quantifier),全称量词表示“凡是”,“一切”,“所有”,“任一个”等意义;存在量词表示“至少有一个”等意义;现在用量词来表达上面几个命题。(a)若设M(x):x是人,H(x):x要呼吸,则原命题可写成:(x)(M(x)H(x))(b)若设P(x):x是学生,Q(x):x要参加考试,则原命题可写成:(x)(P(x)Q(x))(c)若设Z(x):x是整数,R(x):x是正数,N(x):x是负数,则原命题可写成:(x)(Z(x)(R(x)N(x)))#例.不管黑猫白猫,抓住老鼠就是好猫。解:设C(x):x是猫,B(x):x黑的,W(x):x是白的,G(x):x是好的,M(x):x是老鼠,K(x,y):x抓住y,则原命题可表示为:(x)(y)(C(x)M(y)((B(x)W(x))K(x,y)G(x))).谓词归结原理基础谓词归结原理基础谓词归结原理基础谓词归结原理基础谓词归结子句形(Skolem标准形)谓词归结子句形(Skolem标准形)字句集的求解：共9步(2)减少否定符号的辖域
每个否定符号～最多只用到一个谓词符号上，并反复应用狄·摩根定律。

(3)对变量标准化
对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。(4)消去存在量词
以Skolem函数代替存在量词内的约束变量，然后消去存在量词
化为前束形
把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。
前束形={前缀}{母式}
全称量词串无量词公式把母式化为合取范式
任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。

(7)消去全称量词
所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。
(8)消去连词符号∧
用{A,B}代替(A∧B)，消去符号∧。最后得到一个有限集，其中每个公式是文字的析取。
(9)更换变量名称
可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。谓词归结子句形(Skolem标准形)谓词归结子句形(Skolem标准形)谓词归结子句形谓词归结子句形谓词归结子句形求取子句集例(1)求取子句集例(2)归结原理谓词逻辑的归结原理归结原理置换例如表达式P[x,f(y)，B]，对应于不同的变换si，可得到不同的例:
置换置换的例
sl={z/x,w/y}，P[x,f(y)，B]s1=P[z,f(w),B]
s2={A/y}，P[x,f(y)，B]s2=P[x,f(A),B]
s3={g(z)/x,A/y}，P[x,f(y)，B]s3=P[g(z),f(A),B]
s4={C/x,A/y}，P[x,f(y)，B]s4=P[C,f(A),B]
置换的合成置换