一阶谓词原理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,*,一阶谓词逻辑,CH4,一阶逻辑基本概念,CH5,一阶逻辑等值演算与推理,*,2,内容要点：,谓词和个体,量词,一阶逻辑公式,置换规则,一阶逻辑等值式,一阶逻辑前束范式,推理理论,CH4,CH4,CH4,CH5,CH5,CH5,CH5,*,3,1.,命题的表达,例,1.1,：凡偶数都能被,2,整除，,6,是偶数。,所以，,6,能被,2,整除,将它们命题符号化：,p,：凡偶数都能被,2,整除,q,：,6,是偶数,r,：,6,能被,2,整除,则推理的形式结构符号化为：,(,p,q,),r,由于上式不是重言式，所以不能由它判断推理的正确性。为了克服命题逻辑的局限性，就应该将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这就是谓词逻辑。,*,4,(1),是自然数。,(2),21,世纪末，人类将住在月球。,(3),x,+,y,=,y+x,(4),只有,x,能被,2,整除，,x,才能被,4,整除。,A.,个体词,x,y,的取值范围：复数域,a,的取值范围：整数域,是指所研究对象中可以独立存在的具体的或抽象的客体。,表示具体或特定的客体的个体词称作,个体常项,；常用,a,b,c,表示。,表示抽象或泛指的客体的个体词称作,个体变项,；常用,x,y,z,表示。,个体变项的取值范围为,个体域,，个体域可以是有穷集合，也可以是无穷集合。,全总个体域,：由宇宙间一切事物组成的域为,全总个体域,。,*,5,a.,小陈是大学生,b.,小张生于苏州,c.8=3*2,x,是大学生 小陈,-,个体；是大学生,-,谓词：,是大学生刻划了,x,的性质,x,生于,y,生于,-,谓词：刻划了,x,和,y,的关系,x=y*z,.=,.-,谓词：刻划了,x,，,y,，,z,三,元的关系,一、谓词和个体,B.,谓词,*,6,B.,谓词,(1),是自然数。,(2),21,世纪末，人类将住在月球。,(3),x,与,y,具有关系,L,(4),只有,x,能被,2,整除，,x,才能被,4,整除。,谓词：,用来刻划个体词性质及个体词之间相互关系的词,表示具体性质或关系的谓词称为,谓词常项,谓词变项,：表示,抽象的或泛指的,性质或关系的谓词,两者都用大写英文字母表示,*,7,一般的,用,F,(,a,),表示个体常项,a,具有性质,F,（,F,是谓词常项或谓词变项），,用,F,(,x,),表示个体变项,x,具有性质,F,。,而用,F(,a,b,),表示个体常项,a,b,具有关系,F,，,用,F,(,x,y,),表示个体变项,x,y,具有关系,F,。,定义,：,一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为,谓词,。如果括号内有,n,个客体变元,，称该谓词为,n,元谓词,。,*,8,例如,S(x):,表示,x,是大学生。,一元谓词,G(x,y),：表示,xy,。二元谓词,B(x,y,z),：表示,x,在,y,与,z,之间。三元谓词,一般地,P(x,1,x,2,x,n,),是,n,元谓词。,0,元谓词,：有时将不带个体变项的谓词称为,0,元谓词，例如上面提到的,F,(,a,),，,H(,a,b,),，,P,(,a,1,a,2,a,n,),等都是,0,元谓词，当,F,H,P,为谓词常项时，,0,元谓词为命题,。这样，,命题逻辑中的命题均可表示成,0,元谓词,，因而可以将命题看成是特殊的谓词。,*,9,(1)2,是素数且是偶数,2),如果,2,大于,3,，则,2,大于,4,解：,(1),设一元谓词,F,(,x,),：,x,是素数；一元谓词,G,(,x,),：,x,是偶数；,a,：,2,。,则,(1),中命题符号化为,0,元谓词的合取式：,F,(,a,),G,(,a,),。,(2),设二元谓词,L,(,x,y,),：,x,大于,y,；,a,：,2,；,b,：,3,；,c,：,4.,L,(,a,b,),L,(,a,c,),是两个,0,元谓词，把,(2),中命题符号化为,L,(,a,b,),L,(,a,c,),例题：将下列命题用,0,元谓词符号化，并讨论它们的真值。,*,10,x,读作,对任意,x,xP(x),表示,对一切,x,P(x),为真,xP(x),表示,并非对任意,x,P(x),是真,(1),全称量词,x,C.,量词,*,11,x,读作,至少有一,x,，,存在一,x,x P(x),表示,存在一,x,，使,P(x),为真,x P(x),表示,并非存在一个,x,，使,P(x),为真,(2),存在量词,x,C.,量词,*,12,在,P(x),，,P(x,y),前加上,x,或,x,，称变元,x,被存在量化或,全称量化。,将谓词,F(x),变成命题有两种方法。,a.,将,x,取定值,例：,F(x),表示,x,是质数,，那么,F(4),是命题（假）,b.,将谓词量化,例：,1).,xF(x)F(x),：任意的,x是质数,2).,y(yy+1),3).,y(y0,，存在,d,0,使得当,|x-x0|,d,时，均有,|f(x)-f(x0)|0,d,0(|x-x0|,d,|f(x)-f(x0)|,Z,),*,29,谓词公式的解释：,定义 一个,解释,I,由下面,4,部分组成：,（,1,）非空个体域,D,；,（,2,）,D,中一些特定元素的集合,（,3,）,D,上特定函数集合,（,4,）,D,上特定谓词的集合,在,I,下，下列哪些公式为真？哪些为假？哪些的真值还不能确定？,(1)F(f(x,y),g(x,y),在,I,下，被解释成“,x+y=x,y”,这不是命题,(2)F(f(x,a),y),F(,g(x,y),z),在,I,下，被解释成“,(x+0=y),(,x,y=z)”,这不是命题,(3),F(g(x,y),g(y,z),在,I,下，被解释成“,x,yy,z”,这不是命题,(4)xF(g(x,y),z),在,I,下，被解释成“,x,(,x,yz)”,这不是命题,(5)xF(g(x,a),x),F(x,y),在,I,下，被解释成“,x(,(x,0=x),(x=y),)”,由于蕴含式前件为假，所以被解释的公式为真。,(6)xF(g(x,a),x),在,I,下，被解释成“,x(,x,0=x,)”,这不是命题,(7)xy F(f(x,a),y),F(f(y,a),x),在,I,下，被解释成“,xyx+0=y),(y+0=x,),),”,这是真命题,(8)xy,z,F(f(x,y),z),在,I,下，被解释成“,xy,z,(,x+y=z,),”,这是真命题,(9),x,F(f(x,x),g(x,x),在,I,下，被解释成“,x,(x+x=x,x,),”,这是真命题,解 为方便起见，用,A,，,B,，,C,分别记,(1),，,(2),，,(3),中的公式。,(1),取解释,I,1,:,个体域为实数集合,R,，,F(x):x,是整数，,G(x):x,是有理数。在,I,1,下,A,为真，因而,A,不是矛盾式,。取解释,I,2,:,个体域仍然为,R,，,F(x):x,是无理数，,G(x):x,能表示成分数。在,I,2,下,A,为假，所以,A,不是永真式,。故,A,是非永真式的可满足式。,(2),易知,B,是命题公式,p(qp),的代换实例，而该命题公式是重言式，所以,B,是永真式。,(3)C,是命题公式,(p,q),q,的代换实例，而该命题公式是矛盾式，所以,C,是矛盾式。,*,32,注：,在证明一个谓词公式既不是永真式也不是矛盾式时，可以为公式分别找一个成真的解释和一个成假的解释。,当证明一个谓词公式是永真式或矛盾式时，可以使用相应的命题公式进行代换。若命题公式为永真式，则原谓词公式也是永真式；若命题公式为矛盾式，则原谓词公式也是矛盾式。,*,33,内容小结：,谓词和个体,量词,一阶逻辑公式,置换规则,一阶逻辑等值式,一阶逻辑前束范式,推理理论,CH4,CH4,CH4,CH5,CH5,CH5,CH5,*,34,CH4,基本要求,准确的将给定命题符号化,掌握永真式、矛盾式和可满足式的概念及判断方法,深刻理解闭式的概念及闭式的性质（闭式在任何解释下都是命题）,对于给定的解释会判断给定公式是否成为命题，对是命题的能够判断出真假,*,35,Ch,作业,P68,1,，,3,，,5,，,6(1)(2),，,7,，,8,，,10,，,11(1)(2)(3),12,