资源描述：
《基于谓词逻辑的机器课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3章基于谓词逻辑的机器推理3.1一阶谓词逻辑3.2归结演绎推理3.3应用归结原理求取问题答案3.4归结策略3.5归结反演程序举例3.6Horn子句归结与逻辑程序3.1一阶谓词逻辑3.1.1谓词、函数、量词谓词A(x1,x2,…,xn):个体域Di个体变元xi设i=1,2,…n个体常元ai∈Di论述域D1,×D2×…×Dn原子命题A(a1,a2,…,an)量词命题常元(0元原子命题）：表示基本事实例如A:AI是一门专业基础课程1元谓词：表示特定对象是否具有某种属性例如P(x):x是素数P(2)n元谓词：表
2、示n个对象之间是否具有某种关系例如F(x,y):x和y是朋友F(张三，李四)“凡是人都有名字”：x(M(x)→N(x))例3.1不存在最大的整数，我们可以把它翻译为乛x(G(x)∧y(G(y)→D(x,y))或x(G(x)→y(G(y)∧D(y,x))例3.2对于所有的自然数，均有x+y>xxy(N(x)∧N(y)→S(x+y,x))例3.3某些人对某些食物过敏xy(M(x)∧F(y)∧G(x,y))3.1.2谓词公式定义1(1)个体常元和个体变元都是项。(2)设f是n元函数符号，若t1,t2,…,tn
3、是项，则函词f(t1,t2,…,tn)是项。(3)只有有限次使用(1)，(2)得到的符号串才是项。定义2设P为n元谓词符号，t1,t2,…,tn为项，则P(t1,t2,…,tn)称为原子谓词公式，简称原子公式或者原子。定义3(1)原子公式是谓词公式。(2)若A,B是谓词公式，则也是谓词公式。则上式左端也是谓词公式。(3)只有有限步应用(1)，(2)生成的公式才是谓词公式。谓词公式亦称为谓词逻辑中的合适（式）公式，记为Wff。量词的辖域。(1)xP(x)(2)x(H(x)→G(x,y))(3)xA(x)∧B
4、(x)其中(1)中的P(x)为x的辖域，(2)中的H(x)→G(x,y)为x的辖域，(3)中的A(x)为x的辖域指导变元（或作用变元）约束变元自由变元变元公式中可约束出现，自由出现改名规则定义4设A为如下形式的谓词公式：B1∧B2∧…∧Bn其中Bi(i=1,2,…,n)形如L1∨L2∨…∨Lm，Lj(j=1,2,…,m)为原子公式或其否定，则A称为合取范式。例如：(P(x)∨Q(y))∧(乛P(x)∨Q(y)∨R(x,y))∧(乛Q(y)∨乛R(x,y))是一个合取范式。定义5设A为如下形式的命题公式
5、：B1∨B2∨…∨Bn其中Bi(i=1,2,…,n)形如L1∧L2∧…∧Lm，Lj(j=1,2,…,m)为原子公式或其否定，则A称为析取范式。例如：(P(x)∧乛Q(y)∧R(x,y))∨(乛P(x)∧Q(y))∨(乛P(x)∧R(x,y))是一个析取范式。定义6设P为谓词公式，D为其个体域，对于D中的任一解释I：(1)若P恒为真，则称P在D上永真（或有效）或是D上的永真式。(2)若P恒为假，则称P在D上永假（或不可满足）或是D上的永假式。(3)若至少有一个解释,可使P为真，则称P在D上可满足或是D上的可
6、满足式。定义7设P为谓词公式，对于任何个体域：(1)若P都永真，则称P为永真式。(2)若P都永假，则称P为永假式。(3)若P都可满足，则称P为可满足式。表3.1常用逻辑等价式3.1.3谓词逻辑中的形式演绎推理表3.2常用逻辑蕴含式例3.4设有前提：(1)凡是大学生都学过计算机；(2)小王是大学生。试问：小王学过计算机吗？解令S(x)：x是大学生;M(x)：x学过计算机;a：小王。则上面的两个命题可用谓词公式表示为(1)x(S(x)→M(x))(2)S(a)下面我们进行形式推理：(2)x(S(x)→M(x)
7、)［前提］(2)S(a)→M(a)［(1),US］(3)S(a)［前提］(4)M(a)［(2),(3),I3］得结果：M(a)，即“小王学过计算机”。例3.5证明P(a,b)是xy(P(x,y)→W(x,y))和W(a,b)的逻辑结果。证(1)xy(P(x,y)→W(x,y))［前提］(2)y(P(a,y)→W(a,y))［(1),US］(3)P(a,b)→W(a,b)［(2),US］(4)乛W(a,b)［前提］(5)乛P(a,b)［(3),(4),I4］例3.6证x(P(x)→Q(x))∧x(R(x)
8、乛Q(x))x(R(x)→乛P(x))。证(1)x(P(x)→Q(x))［前提］(2)P(y)→Q(y)［(1),US］(3)乛Q(y)→乛P(y)［(2),E24］(4)x(R(x)→Q(x))［前提］(5)R(y)→乛Q(y)［(3),US］(6)R(y)→乛P(y)［(3),(5),I6］(7)x(R(x)→乛P(x))［(6),UG］3.2归结演绎推理3.2.1子句集定义1原子谓词公式及其否定称为文字，若干个文字的一个
