4第四章-一阶谓词逻辑

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章,一阶谓词逻辑,有些推理的有效性不能用命题逻辑和词项逻辑所讲的方法判定：,(1),白马是马（,p,）,所以，骑白马是骑马（,q,）,p,q,（不是重言式，在,p=1,，,q=0,的赋值值为假）,(2) 2,是小于,3,的,3,是小于,4,的,所以，,2,是小于,4,的,没有相同的中项（小于,3,的；,3,），前提和结论之间建立不起任何的关系,但实际上,(1),和,(2),的推理都是有效的。命题逻辑和词项逻辑有局限性。,命题逻辑和词项逻辑的局限性：,1.,都不能处理关系命题及其推理；,2.,都不能处理量词内部含联结词结构的命题及其推理。,需要用另外的逻辑理论,谓词逻辑,。,一阶谓词逻辑语言,一阶谓词逻辑公式,公式赋值,/,语义,普遍有效式,逻辑推论,形式推演,前束范式,专名、,常项及其指称,专名是用来指称、指向或命名某个东西的表达式。“长江”“黄河”“美国的首都,常项就是有所指的专名。,变项：,x y z ,变项的作用在于它在某个范围内可以取不同的值。,例如：,我们令下列城市为,x,的取值范围：,西安、南京、荆州、襄阳、平遥,x,的城墙,论域，有时也称个体域，是讨论中涉及的所有个体对象的集合。,函数和函数符号,函数是一种映射或指派关系。,设,A,是前面列出的所有城市的集合，,B,是所有这些城市的现有的城墙的集合。,那么,f,可以是这样一个函数，它把,A,中的每一个城市映射到,B,中该城市的城墙。,于是，,f(,西安）西安的城墙,.,在我们的讨论中，也可以有函数符号，用,f, g, h,来表示。函数符号的定义域和值域都是论域。,项,项类似于自然语言中的名词或名词词组，包括所有的个体常项和个体变项，并且包括用函数符号加上适当的常项或变项序列组成的符号串。,例如：,fx: x,的父亲,a:,张山,fa:,张三的父亲,这里的函数符号可以叠加，例如,gx: x,的母亲,张三的祖母？,gfa,第一节,一阶谓词逻辑语言,个体词,个体词就是表示对象域中的个体的符号，包括个体变项和个体常项。,个体变项：某个特定的范围内的某个不确定的对象，用,x,，,y,，,z,个体常项：某个特定的范围内的某个确定的对象，用,a,，,b,，,c,来表示,论域：由一定对象所组成的类或者集合，规定了个体变项的取值范围，也叫做个体变项的“值域”。,论域一般是全域。,谓词：,F,、,G,、,H,、,R,1.,一元谓词（表示性质）,F(x),：自然数是整数,F(a),：,3,是整数,G(b) ,春江花月夜,是中国古代名曲,2. n,元谓词（表示,n,元关系）,H(c,d),：牛郎爱织女,F(y,e),：张三比李四跑的快。,谓词：,F,、,G,、,H,、,R,词典,我们可以用下面方式直观表明：形式语言中的个体常项、函数符号和谓词等表示个体、函数、性质及关系,论域： 自然数集合,Px,：,x,是素数,a:0 Rxy: xy,fx:x+1,当我们对汉语的句子做符号化或形式翻译时候，类似上述表格被称为“词典”,量词,全称量词：,(,所有、任何、一切,),x,F(x),：对于所有的,x,，,x,是,F,特称量词：,(,存在、有些、有一个,),x,F(x),：存在,x,使得,x,是,F,联结词：,，,辅助符号,:,(),，,，,量词的辖域,量词的辖域是它后面第一个完整的公式。,个体变项的自由出现和约束出现,设,x,为一个个体变项，,是任意公式，,x,在,中的一个出现是约束的（,bound),，当且仅当这一出现或是在,中的某个使用,x,的量词中，或者在这样的量词的辖域内。,x,在,中的一个出现是自由的,(free),当且仅当这一出现既不是在,中出现的任何量词中，也不是在他们的辖域内。,开公式,一个含有至少一个自由变项的公式，叫做“开公式”。,闭公式,如果一个公式中所有个体变项的出现是约束出现，那么我们就把该公示称为闭公式或句子。,特别的，没有任何个体变项出现的公式都是闭公式。,G(a),在给定论域之后，闭公式有确定的意义。,直言句及其符号化,无量词的句子,例：用给出的词典将下列句子符号化：,论域：,现有的人,a:,张三,Px,：,x,是成年人,b:,李四,Rxy,: x,比,y,年长,c:,王五,如果李四是成年人并且没有王五年长，那么王五也是成年人。,虽然张三不是成年人，但他还是比李四和王五年长。,2.,自然语言中性质命题的符号化,1. SAP,符号化为：,x,(S(x),P(x),2. SEP,符号化为：,x,(,S,(x),P(x),x(S,(x),P(x),x,(,S,(x),P(x),3. SIP,符号化为：,x(,S(x),P(x),4. SOP,符号化为：,x(,S(x), ,P(x),5.,单称直言命题符号化： 原子公式,“,春江花月夜,是一只中国古典名曲”,F(a),所有的鱼都生活在水中,没有猫生活在水中,有些生活在水中的是鱼,有些生活在水中的不是鱼,论域：所有生物,Gx: x,生活在水里,Fx: x,是鱼,Hx: x,是猫,自然语言中关系命题符号化,论域：所有生物,Lxy: x,帮助,y,Px: x,是人,b:,张三,所有人都帮助张三。,没有人帮助张三。,有些人帮助张三。,有些人没有帮助张三。,张三帮助每一个人。,张三没帮助任何人。,论域：所有的人,Px:,x,是学生,b:,张三,Lxy: x,帮助,y,Rxy:,与,y,住同一个宿舍,与张三同宿舍的学生都帮助张三,与张三同宿舍的学生没人帮助张三。,张三帮助他同宿舍的每一个学生。,与张三同宿舍的某些学生没有帮助张三。,更进一步,论域：所有的人,Px: x,是学生,b:,张三,Lxy: x,帮助,y,Rxy: x,与,y,住同一个宿舍,1.,与张三同宿舍的学生都帮助张三,。,2,.,与张三同宿舍的学生中没人帮助张三。,3.,与张三同宿舍的某些学生帮助张三。,4.,与张三同宿舍的某些学生没帮助张三。,5.,张三帮助他同宿舍的每一个学生。,6.,张三帮助他同宿舍的某些学生。,更进一步,论域： 所有人,Qx: x,是文科专业的,Sx: x,是学生,Fx: x,学理科知识,Px: x,聪明,Gx: x,学文科知识,1.,聪明的文科生都既学文又学理。,2.,有些聪明的文科生既学文又学理。,3.,没有哪个聪明的文科生是既学文又学理。,4.,有些聪明的文科生没有既学文又学理。,关于“和”的处理,论域： 所有动物,Cx: x,是猪,Ax: x,是哺乳动物,Dx: x,是狗,Bx:,是鸟,Fx:x,是鱼,猫和狗都是哺乳动物。,鸟和鱼都不是哺乳动物。,嵌入量词的句子的形式化,嵌入量词是指出现在某个量词辖域中的量词。,论域：所有的动物,Px: x,是人,Lxy:x,爱,y,1.,每个人都爱所有的人,2.,没有人爱所有的人。,3.,有些人爱所有的人。,4.,每个人都爱某些人。,论域： 所有的动物,Dx: x,是狗,Px: x,是人,Rxy: x,见过,y,Qx: x,是家养动物,Lxy: x,喜欢,y,Sx: x,是流浪动物,Bxy: x,咬过,y,1.,见过流浪狗的人喜欢所有家养的狗。,2.,有些见过家养狗的人不喜欢任何流浪狗。,3.,每个被狗咬过的人都不喜欢任何流浪狗。,函数符号和等词的运用,“,是”至少有两种意思，一种是属于某类或有某性质，二是等于或相等。,“,张三是男人”。,“,张小三的父亲是张三”。,用给出的词典将下列句子符号化,论域：所有的人,gx: x,的母亲,a:,张三,Px:x,是女人,b:,李四,Lxy: x,喜欢,y,fx: x,的父亲,Tx:x,是教师,张三的祖母是教师。,张三的祖母是李四的外祖母。,张三的祖父不是李四的外祖父。,每个人的母亲都是女人。,有些女士不喜欢自己的父亲。,二元关系的逻辑性质,1.,自返性 ： 一关系,R,是自返的，当且仅当， 对任一,x,而言，,x,与它自身有,R,关系。即,x R(x,x).,2.,对称性：,一关系,R,是对称的，当且仅当，对任一,x,和,y,而言，如果,R(x,y),则,R(y,x),3.,传递性：,一关系,R,是传递的，当且仅当，对任一,x,y,和,z,而言，如果,R(x,y),且,R(y,z),， 则,R(x,z),符号系统,个体变项：,x,，,y,，,z,（自由,/,约束变元）,个体常项：,a,，,b,，,c,谓词：,F,、,G,、,H,、,R,一元谓词（表示性质）,二元谓词（表示关系）,量词,全称量词：,特称量词：,联结词：,，,辅助符号,:,(),，,，,真假值： “,1,”,（或,T,）， “,0,”,（或,F,）,项的形成规则,形式语言,L,的项是如下递归定义的,1.,常项符号是项；,2.,变元符号是项；,3.,如果,t,1,，,t,2, t,n,是项，,f,是任意,n,元函数符号， 则,f(t,1,，,t,2, t,n,也是项,;,4.,只有这些是项。,第二节,一阶谓词逻辑公式,公式形成规则,对于任意,n,元谓词,P,和任意序列,t,1,，,t,2, t,n,，,P(t,1,，,t,2, t,n,）,是公式,，,也称为原子公式；,如果,A,是公式，则,A,是公式；,如果,A,和,B,都是公式，则,A,B,，,A,B,，,A,B,，,A,B,是公式；,如果,A,是公式，则,x,A,，,xA,是公式；,只有按以上方式形成的符号串才是公式。,x,A,为全称公式,xA,为存在公式,辖域：如果,x,A,或,xA,是,B,的段，则称,A,为在它左边的,x,或,x,在,B,中的辖域。,量词的辖域不是公式,公式,xyzF(x,y,z),，,x,的辖域是,y zF(x,y,z),， ,y,的辖域是,zF(x,y,z),，,z,的辖域是,F(x,y,z),约束变元：如果处于量词,x,或,x,的辖域之内并且与量词所含变项相同，或作为与该量词一起出现的变项。否则称为自由变元。,x,(F(x),H(x),，,x,为约束变元,G(y),y,(F(x),G(y),， 第一个,G(y),中的,y,是自由变元，,y,(F(x),G(y),中的,x,是自由变元，,y,是约束变元,闭公式：不含自由变元符号的公式,F(a,b),，,y,F(a,y),，,xyF(x,y),是闭公式,开公式：含至少一个自由变元符号的公式,F(u,v),， ,y,F(u,y),，,xyF(x,y,w),闭公式意义确定，有确定的真值,开公式的意义不确定，没有确定的真值,F,xF(x),y,H(y),此公式是不是一阶谓词中的公式？,不是，一阶谓词逻辑的变元指论域中的对象，而不是谓词变元。只有在高阶逻辑中才允许使用谓词变元。,高阶逻辑的引入是为了解决一阶逻辑不能表达,/,处理的命题。,模型和赋值,1.,一阶语言的一个模型,M,（解释）包括一下要素：,（,1,）一个个体域,D,即由具有一定性质的个体所有构成的集合。,（,2,）个体常项在个体域,D,中的值， 即个体常项表示该个体域中的某个特定个体。,（,3,）谓词符号在个体域,D,上的解释，即表示该个体域中个体的性质和个体之间的关系。,D,：自然数集合,a,：,1,F(x),：,x,是偶数,R(x,y),：,x,小于,y,S(x,y,z),：,x,乘,y,等于,z,F(a),：,1,是偶数,xyR(x,y),：对于任一自然数，都可以找到另一个自然数，使得前者小于后者,xS(x,a,x),：任一自然数与,1,相乘都等于该自然数本身,yR(y,x),：有的自然数小于,10(,给,x,指派,10,的值,),yR(y,z),：有的自然数小于,5(,给,z,指派,5,的值,),一个模型,M,和模型,M,上的一个指派称为一个赋值，记为,=,。 从而一个公式,A,在赋值,下的的值,(A),可以递归定义如下,：,1. (F(t,1,t,n,)= T, iff, F,2. (,B)=T, iff, (,B,)=T,3. (B,C)=T, iff, (,B,)=T,且,(C)=T,4. (B,C)=T, iff, (,B,)=T,或,(C)=T,5. (B,C)=T, iff, (,B,)=F,或,(C)=T,6. (B,C)=T, iff, (,B)=,(C)=T,或,(,B)=,(C)=F,7. (,x,B(x)=T,，,iff,8. . (,x,B(x)=T,Iff,如果由,B(x),构作,B(u)(,取,u,不在,B(x),中出现并且,u,取代,A(x),中的,x),且对任何,aD,，,A(u),(u/a),=1,如果由,B(x),构作,B(u)(,取,u,不在,B(x),中出现并且,u,取代,A(x),中的,x),且存在,aD,，,A(u),(u/a),=1,A=F(g(a),g(b),g(c),D,：自然数集合,F(x,y,z),：,x,加,y,等于,z,g(x),：,x,的平方,a=3,b=4,c=5,A,为,3,2,+4,2,=5,2,A,在此赋值下为真,a=3,b=6,c=5,A,为,3,2,+6,2,=5,2,A,在此赋值下为假,存在赋值可使,A,为真和为假,B=F(u),F(u),任何赋值都使,B,为真,第四节,普遍有效式,（普遍）有效性,A,是有效的，当且仅当对于（以任何不空集为论域的）任何赋值,A=1,有效公式是永真式,可满足性,A,是可满足的，当且仅当存在（以某个不空集为论域的）赋值，使得,A=1,当,A=1,时，称此赋值满足,A,不可满足性,A,是非有效的，当且仅当对于（以任何不空集为论域的）任何赋值,A=0,不可满足公式是永假式,注意,有效公式相当于命题逻辑中的重言式，但它们之间有区别。可用算法（真值表法）判定命题逻辑中的公式是不是重言式。但若要判断谓词逻辑中的公式是否有效，须考虑所有不同大小的集合以及以它们为论域的所有指派。在无限论域,D,的情形，这个过程一般不是有限的。如我们没有方法在有限步内求出,x,A(x),或,x,A(x),的值，因为这要求先给出对应无限多个,aD,的,A(x),的值,普遍有效式 ：书,P186,普遍有效式的判定问题：书,P187,判定问题,机器判定公式,A,是不是,Theorem,中的定理。存在一个算法,T,（机械可实现的）,可判定：,If A Theorem,机器回答,=YES,else,机器回答,= NO,半可判定：,If A Theorem,机器回答,=YES,else,机器回答,=,？,不可判定：,If A Theorem,机器回答,=,？,else,机器回答,=,？,“停机问题”：一个任给的图灵机对于一个任给的输入而言，是否停机不可判定,一阶谓词逻辑的半可判定性,可判定：存在算法判定公式的真值,不可判定：不存在算法判定公式的真值,半可判定：,公式可满足，有算法可验证,公式不可满足，无算法可验证,命题逻辑是可判定的，判定算法的基本原理：穷尽每个命题变元的一切取值，分别计算各种取值下命题的真值,这一原理不适合一阶谓词逻辑，因为对公式,A,来说，由于结构、指派是不能穷尽的，从而,A,所涉及的取值也是不可穷尽的。丘奇首先指出：“任何至少含有一个二元谓词的一阶谓词演算系统都是不可判定的。”,一阶谓词逻辑是半可判定的，即存在一个可机械实现的过程，能对其定理做出肯定的判定，但对非定理的公式却未必能做出否定的判定,例子：书,P193-194,例,12,、,13,、,14,、,15,练习：书,可满足公式是相对于以特定的不空集为论域的特定赋值而是真的。公式在给以赋值之后就有了具体内容，可满足性刻划了由,内容确定,的命题的真的概念。,有效公式的真是由它的,形式结构,确定的，与其中的各种符号在赋值下产生的涵义没有关系，而注重命题的内容抽象出的逻辑形式,第五节,逻辑推论,是命题逻辑的公式集，,A,是公式集中一公式，,A,是的,逻辑推论,（即A是 中公式的,逻辑推论,），,记作,A，（,读作逻辑蕴涵,）,当且仅当对于任何赋值， ,=1,蕴涵,A=1,。,注意：,“,”不是形式语言中的符号,，,A不是形式语言中的公式,，而是关于,和,A的元语言中的命题。,A表示,A不成立，即存在真假赋值使,=1,并且,A=0,。,是公式集，当是空集时，是,A，且A的真是无条件的，即A是有效公式。,例,x,A(x),x,A(x),用反证法，设,x,A(x),x,A(x),，即存在以,D,为论域的赋值使得,(1),x,A(x)=1,(2),x,A(x)=0,由,A(x),构作,A(u),，取,u,不在,A(x),中出现。由,(1),得，存在,aD,，使得,(,A(u),(u/a),=1,，因此有,(3),存在,aD,，使得,A(u),(u/a),=0,由,(2),得,x,A(x)=1,，和,(3),矛盾,证,x,A(x),x,A(x),例,x,A(x),B(x),x,A(x), x,B(x),设,x,A(x),B(x),x,A(x), x,B(x),，即有以,D,为论域的赋值，使得,(1),x,A(x),B(x)=1,(2),x,A(x),x,B(x)=0,由,(2),得,(3),x,A(x) =1,(4),x,B(x)=0,由,A(x),和,B(x),分别构作,A(u),和,B(u),，取不在,A(x),和,B(x),中出现。得,(5),对于任何,aD,，,A(u),B(u),(u/a),=1,由,(1),(6),对于任何,aD,，,A(u),(u/a),=1,由 由,(3),(7),任何,a D,，,B(u),(u/a),=0,由,(5)(6),得,对于任何,aD,，,B(u),(u/a),=1,与,(7),矛盾,上面的两个例子都是证明逻辑推论，在证明中并不要构作赋值；若要否证逻辑推论，要在否证中构作赋值,例,x,F(x), x,G(x),x,F(x),G(x),令,D=a,b,，由,F(x),和,G(x),分别构作,F(u),和,G(u)(u,不在,F(x),和,G(x),中出现,),，,F(x)=a,，,G(x)=b,或,(1),F(u),(u/a),=1,(2) F(u),(u/b),=0,(3) G(u),(u/a),=0,(4) G(u),(u/b),=1,或,0,(5),x,F(x) =0,由,(2),(6),x,F(x), x,G(x)=1,由,(5),(7) F(u),G(u),(u/a),=0,由,(1)(3),(8),x,F(x),G(x)=0,由,(7),由,(6)(8),得,x,F(x), x,G(x),x,F(x),G(x),x,F(x), x,G(x),x,F(x),G(x),则有,x,F(x),x,G(x)=1,，,x,F(x),G(x)=0,。此时若令,D=a,，,(1) F(u),(u/a),=1,(2) G(u),(u/a),=0,(3),x,F(x) =1,由,(1),(4),x,G(x)=0,由,(2),(5) F(u),G(u),(u/a),=0,由,(1)(2),(6),x,F(x), x,G(x)=0,由,(3)(4),(7),x,F(x),G(x)=0,由,(5),(6),与前提矛盾，不能令,D=a,来证明,x,F(x), x,G(x),x,F(x),G(x),第六节,形式推演,一阶谓词逻辑推演规则包括了命题逻辑中的,13,条形式推演规则，增加量词规则,（其中,A,，,B,，,C,为任何公式）,(,-,),如果,x,A(x),，,则,A(t) (,消去,),(,+,),如果,A(u),，,u,不在中出现，,则,x,A(x),(,引入,),(,-),如果,A(u), B,u,不在或B中出现，,则,x,A(x), B,（,消去）,(,+),如果,A(t),则,x,A(x),，其中,A(x),是在,A(t),中把,t,的某些（不一定全部）出现替换为,x,而得 （,引入,）,形式可推演性,A,是在一阶谓词逻辑中由,形式可推演,（或,形式证明,）的，记作,A,，,当且仅当,A,能由（有限次使用）,一阶谓词,逻辑的形式推演规则生成。,定理,1,x,1,x,n,A(x,1,x,n,),A(t,1,t,n,), A(t,1,t,n,),x,1,x,n,A(x,1,x,n,),，其中,A(x,1,x,n,),是在,A(t,1,t,n,),中把,t,i,的某些（不一定是全部）出现替换为,x,i,而得,(1in),x,A(x),y,A(y),x,A(x),y,A(y),xy,A(x,y),yx,A(x,y),xy,A(x,y),yx,A(x,y),x,A(x),x,A(x),xy,A(x,y),yx,A(x,y),证,x,A(x),y,A(y),A(u),A(u) (,取,u,不在,A(y),中出现,),A(u),y,A(y) ,(,+),x,A(x),y,A(y) ,(,-),同上,定理,2,x,A(x),x,A(x), x,A(x),x,A(x),选证,x,A(x),x,A(x),A(u),x,A(x),(,取,u,不在,A(x),中出现,),x,A(x),A(u),x,A(x),(+)(ref),x,A(x), A(u) ,(, ,),x,A(x),x,A(x),(,+,),x,A(x) ,x,A(x),x,A(x),(+)(ref),x,A(x) ,x,A(x), ,(, ,),x,A(x) A(u),(,取,u,不在,A(x),中出现,),A(u),x,A(x),(,如果,AB,则,B,A),x,A(x),x,A(x),(,-),定理,3,x,A(x),B(x),x,A(x), x,B(x),x,A(x),B(x),x,A(x),x,B(x),x,A(x),B(x) ,x,B(x),C(x),x,A(x), x,C(x),A,x,B(x),x,A,B(x) x,不在,A,中出现,A,x,B(x),x,A,B(x) x,不在,A,中出现,x,A(x),B,x,A(x),B x,不在,B,中出现,x,A(x),B,x,A(x),B x,不在,B,中出现,定理,4,A,x,B(x),x,A,B(x) x,不在,A,中出现,A,x,B(x),x,A,B(x) x,不在,A,中出现,x,A(x),x,B(x),x,A(x),B(x),x,A(x),B(x),x,A(x),x,B(x),Q,1,xA(x),Q,2,y,B(y),Q,1,xQ,2,y ,A(x),B(y) x,不在,B(y),中出现，,y,不在,A(x),中出现,定理,5,A,x,B(x),x,A,B(x) x,不在,A,中出现,A,x,B(x),x,A,B(x) x,不在,A,中出现,x,A(x),x,B(x),x,A(x),B(x),x,A(x),x,B(x),x,A(x),B(x),Q,1,xA(x),Q,2,y,B(y),Q,1,xQ,2,y ,A(x),B(y) x,不在,B(y),中出现，,y,不在,A(x),中出现,定理,6,x,A(x),B(x),x,A(x),x,B(x),x,A(x),B(x),x,A(x),x,B(x),x,A(x),B(x) ,x,B(x),C(x),x,A(x),x,C(x),x,A(x),B(x),x,A(x),B(x),x,A(x),B(x),x,B(x),A(x),x,A(x),B(x),，,x,B(x),A(x),x,A(x),B(x),可靠性定理,A,A,每个可证明的一阶逻辑句子是普遍有效的，就是在所有域上有效,完备性定理,A, A,),每个普遍有效的一阶公式是可证明的,一阶逻辑是可靠和完备的,例子,书,P199,例,17,、,P203,例,18,苏格拉底三段论：所有人都会死，苏格拉底是人，所以苏格拉底会死。,H(x): x,是人,M(x):x,会死,a,：苏格拉底,x,H(x),M(x),H(a),M(a),x,H(x),M(x),，,H(a),x,H(x),M(x) (ref),x,H(x),M(x),，,H(a),H(a),M(a) ,(,-,),x,H(x),M(x),，,H(a),H(a) (ref),x,H(x),M(x),，,H(a),M(a) ,(,),任何人违反交通规则，则要受到罚款，因此，如果没有罚款，则没有人违反交通规则。,S(x,y):x,违反,y,M(y):y,是交通规则,P(z):z,是罚款,R(x,z):x,受到,z,x,y(S(x,y),M(y),),z(,P(z)R(x,z),),z,P(z)xy(S(x,y),M(y),x,y(S(x,y),M(y),),z(,P(z)R(x,z),),z,P(z)xy(S(x,y),M(y),x,y(S(x,y),M(y),),z(,P(z)R(x,z),),y(S(b,y),M(y),),z(,P(z)R(b,z),),x,y(S(x,y),M(y),),z(,P(z)R(x,z),), z(,P(z),z(,P(z) (+)(ref),x,y(S(x,y),M(y),),z(,P(z)R(x,z),), z(,P(z),z(,P(z),定理,2,x,y(S(x,y),M(y),),z(,P(z)R(x,z),), z(,P(z),(,P(a),x,y(S(x,y),M(y),),z(,P(z)R(x,z),), z(,P(z),(,P(a), ,R(b,a),( ,+),x,y(S(x,y),M(y),),z(,P(z)R(x,z),), z(,P(z),z,(,(,P(z), ,R(b,z) ),(,+),x,y(S(x,y),M(y),),z(,P(z)R(x,z),), z(,P(z),z (,P(z), ,R(b,z) ) ,定理,2,x,y(S(x,y),M(y),),z(,P(z)R(x,z),),， ,z(,P(z),z(,P(z)R(b,z),),y(S(b,y),M(y),),(,如果,AB,则,B,A),x,y(S(x,y),M(y),),z(,P(z)R(x,z),) , z(,P(z),y(S(b,y),M(y),),(,-,),x,y(S(x,y),M(y),),z(,P(z)R(x,z),) , z(,P(z),y(S(b,y),M(y),),定理,2,x,y(S(x,y),M(y),),z(,P(z)R(x,z),) , z(,P(z),y(S(b,y),M(y),),x,y(S(x,y),M(y),),z(,P(z)R(x,z),) , z(,P(z),x,y(S(x,y),M(y),),( ,+), xy(S(x,y)M(y) z(P(z)R(x,z),zP(z)xy(S(x,y)M(y),(,+,),课堂练习：书,第七节,前束范式,前束范式是一阶逻辑中的范式，在一阶逻辑中，公式可以变换为与它等值的前束范式,称公式,A,为,前束范式,，当且仅当它有下面的形式,Q,1,x,1,Q,n,x,n,B,其中的,Q,1,，,，,Q,n,是,或,，并且,B,不含量词。,称,Q,1,x,1,Q,n,x,n,为前束词；称,B,为母式,xA(x) xB(x),xA(x) B(x),xA(x) ,xB(x),xA(x) B(x),xA(x),x,A(x), ,xA(x),x,A(x),步骤：,把公式中的,和,替换为,、,、，并且使,的辖域中不出现,、,、，再根据等值公式，逐步把量词移到,、,、的辖域之外，从而使量词放在公式的最前面。,例,x,yF(u,x,y),x,yG(y,w)H(x),x,yF(u,x,y) ,x,yG(y,w) H(x),x,yF(u,x,y) ,xyG(y,w) H(x),x,yF(u,x,y) ,xyG(y,w) H(x),x,yF(u,x,y) x,y,G(y,w) H(x),x,yF(u,x,y) ,y,G(y,w) ,H(x),x,yF(u,x,y) ,z,G(z,w) ,H(x),x,y,zF(u,x,y) ,G(z,w) ,H(x),