第10讲谓词逻辑等值式

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,一阶逻辑,*,一阶逻辑的字母表,个体常项:,a, b, c, , a,1, b,1, c,1,个体变项:,x, y, z, , x,1, y,1, z,1,函数符号:,f, g, h, , f,1, g,1, h,1,谓词符号:,F, G, H, , F,1, G,1, H,1, ,量词符号:,联结词符号: , , , , ,括号与逗号: (, ), ，,2024/10/1,1,一阶逻辑,一阶(,first order,),逻辑的合式公式,项,原子公式,合式公式,2024/10/1,2,一阶逻辑,合式公式中的变项,量词辖域:,在,xA, ,x,A,中,A,是量词的辖域. 例如:,x(F(x)y,(G(y)H(x,y),指导变项,: 紧跟在量词后面的个体变项.例如:,x,(F(x),y,(G(y)H(x,y),约束出现,: 在辖域中与指导变项同名的变项. 例如:,x(F(,x,)y(G(,y,)H(,x,y,),自由出现,: 既非指导变项又非约束出现. 例如:,y(G(y)H(,x,y),2024/10/1,3,一阶逻辑,解释(,interpret),对一个合式公式的,解释,包括给出,个体域,谓词,函数,个体常项,的具体含义,2024/10/1,4,一阶逻辑,赋值(举例),F(f(a,a),b),赋值1： 个体域是全体自然数;,a: 2,;,b: 4; f(x,y)=x+y,;,F(x,y): x=y,原公式赋值成: “2+2=4”。,赋值2： 个体域是全体实数;,a: 3,;,b: 5; f(x,y)=x-y,;,F(x,y): xy,原公式赋值成: “3-35”。,2024/10/1,5,一阶逻辑,一阶逻辑永真式(,tautology),永真式:在各种,解释,下取值均为真(逻辑有效式),命题逻辑永真式: 在各种,解释,下取值均为真(重言式),永假式:在各种,解释,下取值均为假(矛盾式),命题逻辑永假式: 在各种,解释,下取值均为假(矛盾式),可满足式：非永假式,2024/10/1,6,一阶逻辑,代换实例,在含命题变项,p,1,p,2,p,n,的命题公式中, 每个命题变项代换成一阶逻辑公式所得到的式子, 称为原来公式的,代换实例,.,例：,F(x,),G(y,),xF(x,),G(y),2024/10/1,7,一阶逻辑,一阶逻辑公式分类,例：,xF(x,),x,F(x,),xF(x,),(,G(y,),xF(x,) ),xF(x,),yG(y,),(,xF(x,),yG(y,) ) ,yG(y,),2024/10/1,8,一阶逻辑,命题符号化(举例,),例,: “,不存在最大的自然数”。,(,论域取全体自然数,),解: 设:,G(x,y): x,y,;,原命题符号化成:,xyG(y,x,),或:,x,y ,G(y,x,),2024/10/1,9,一阶逻辑,一阶逻辑等值式(定义,),等值：,A,B,读作：,A,等值于,B,含义：,A,与,B,在各种,赋值,下取值均相等,A,B,当且仅当,A,B,是永真式,例如：,xF(x,),x,F(x),F,F,2024/10/1,10,一阶逻辑,一阶逻辑等值式(来源),命题逻辑等值式的,代换实例,与,量词,有关的,有限个体域量词消去,量词否定,量词辖域收缩与扩张,量词分配,相同量词的交换,与,变项命名,有关的,换名规则,代替规则,2024/10/1,11,一阶逻辑,代换实例,在命题逻辑等值式中, 代入一阶逻辑公式所得到的式子, 称为原来公式的,代换实例,.,例1：,A,A,令,A=,xF(x,),得到,xF(x,),xF(x,),例2：,A,B,A,B,令,A=F(x),B=G(y),得到,F(x),G(y),F(x),G(y),2024/10/1,12,一阶逻辑,有限个体域上消去量词,设个体域为有限集,D=a,1, a,2, a,n,则,xA(x)A(,a,1,),A(,a,2,),A(,a,n,),xA(x)A(,a,1,),A(,a,2,),A(,a,n,),例: 个体域,D=a,b,c,则,x,yF(x,y,),x (F(x,a),F(x,b),F(x,c), (F(a,a),F(a,b),F(a,c),(F(b,a),F(b,b),F(b,c),(F(c,a),F(c,b),F(c,c),2024/10/1,13,一阶逻辑,量词否定等值式,xA(x,),x,A(x),xA(x,),x,A(x),A,A,2024/10/1,14,一阶逻辑,量词否定等值式(举例),N,n (,nN,|,a,n,-a|N, |,a,n,-a|N, |,a,n,-a|N, |,a,n,-a|N, |,a,n,-a|N,|,a,n,-a|N,|,a,n,-a|N,|,a,n,-a|, ),2024/10/1,16,一阶逻辑,量词辖域收缩与扩张(,),x,(,A(x),B),xA(x,),B,x,(,A(x),B),xA(x,),B,说明:,B,中不含,x,的出现,例1: ,x(F(x),G(y),) ,xF(x,),G(y),例2: ,x,y(F(x),G(y),) ,x(F(x),y,G(y,),xF(x,),y,G(y,),2024/10/1,17,一阶逻辑,量词辖域收缩与扩张(,、续,),x,(,A(x),B),x,(B,A(x,),),证明: ,x(A(x),B),x(,A(x),B) ,x,A(x),B,xA(x,),B ,xA(x,),B,证明: ,x(B,A(x),x(,B,A(x),) ,B,x,A(x,),B,x,A(x,), B,xA(x,),xA(x,),B, B,xA(x,),2024/10/1,18,一阶逻辑,量词辖域收缩与扩张(,),x,(,A(x),B),xA(x,),B,x,(,A(x),B),xA(x,),B,x,(,A(x),B),xA(x,),B,x,(B,A(x),),B,xA(x,),说明:,B,中不含,x,的出现,例1: ,x(F(x),G(y),) ,xF(x,),G(y),例2: ,x,y(F(x),G(y),) ,x(F(x),y,G(y,),xF(x,),y,G(y,),2024/10/1,19,一阶逻辑,量词辖域收缩与扩张(,、续,),x(A(x),B) ,xA(x,),B,证明: ,x(A(x),B),x(,A(x),B) ,x,A(x),B,xA(x,),B ,xA(x,),B,x(B,A(x) B,xA(x,),证明: ,x(B,A(x),x(,B,A(x),) ,B,x,A(x,),B,x,A(x,), B,xA(x,),2024/10/1,20,一阶逻辑,量词分配,x(A(x),B(x) ,xA(x,),xB(x,),x(A(x),B(x) ,xA(x,),xB(x,),2024/10/1,21,一阶逻辑,量词分配(反例),x(A(x),B(x),xA(x,),xB(x,),x(A(x),B(x),xA(x,),xB(x,),个体域为全体自然数;,A(x): x,是偶数,B(x): x,是奇数; 左,1,右,0,x(A(x),B(x),xA(x,),xB(x,),x(A(x),B(x),xA(x,),xB(x,),个体域为全体自然数;,A(x): x,是偶数,B(x): x,是奇数; 左,0,右,1,2024/10/1,22,一阶逻辑,相同量词的交换,x,y(x,y),y,x(x,y),x,y(x,y),y,x(x,y),2024/10/1,23,一阶逻辑,换名(,rename),规则,把某个,指导变项,和其量词辖域中所有同名的,约束出现, 都换成某个新的个体变项符号.,例如:,x(A(x),B(x) ,y(A(y),B(y),xA(x,),xB(x,) ,yA(y,),zB(z,),H(x,y),xF(x,),y(G(y)H(x,y), H(x,y),zF(z,),u(G(u)H(x,u),2024/10/1,24,一阶逻辑,代替(,substitute,),规则,把某个,自由变项,的所有出现, 都换成某个新的个体变项符号.,例如:,A(x),B(x) A(y),B(,y,),xA(x,),B(x) ,xA(x,),B(,y,),H(x,y),xF(x,),y(G(y)H(x,y), H(,s,t,),xF(x,),y(G(y)H(,s,y),2024/10/1,25,一阶逻辑,置换,(,permutation,),规则,设,(,A,),是含公式,A,的一阶谓词公式，,(,B,),是用公式,B,置换,(,A,),中所有出现的,A,后得到的公式。若,A,B,则,(,A,),(,B,),2024/10/1,26,一阶逻辑,例,5.5,2024/10/1,27,一阶逻辑,举例,xA(x,),xB(x,) ,x(A(x),B(x),xA(x,),xB(x,),y,A(y,),xB(x,),y,(,A(y,),xB(x,),y,x(A(y),B(x,),特点：所有量词都在最前面,2024/10/1,28,一阶逻辑,前束范式,设,为一谓词公式，如果,具有如下形式：,Q,1,x,1,Q,2,x,2,.,Q,n,x,n,其中,Q,i,(1in),为,或,，,为不含量词的公式，则称,为,前束范式,.,2024/10/1,29,一阶逻辑,前束范式存在定理,定理：任意一个谓词公式，都存在着一个等值的前束范式。,(注：利用换名规则或代替规则以及上述所提及的等值式可知，任意公式都有其前束范式(存在性)，但并不唯一.),2024/10/1,30,一阶逻辑,前束合取（析取）范式,设,为一谓词公式，如果,具有如下形式：,Q,1,x,1,Q,2,x,2,.,Q,n,x,n,其中,Q,i,(1in),为,或,，,为不含量词的,合取（析取）范式,公式，则称,为前束合取（析取）范式,合取范式形如：,(,A,11,A,12,A,1n,), (,A,21,A,22,A,2n,）, (,A,m1,A,m2,A,mn,）,其中,A,ij,是,原子公式或其否定。,2024/10/1,31,一阶逻辑,举例,xA(x,),xB(x,) ,x(A(x),B(x),xA(x,),xB(x,) ,y,A(y,),xB(x,),y,(,A(y),xB(x,),y,x(A(y),B(x),2024/10/1,32,一阶逻辑,习题,P78-80 2,，,6-12,2024/10/1,33,一阶逻辑,