交大数理逻辑课件4-1 谓词逻辑的基本概念

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,作业讲评,1,第,1,章习题,P12,：,2(2),用自然语言叙述,：,(,P,Q,),设,P,：今天很冷，,Q,：正在下雪,(,P,Q,),：今天,不是,既,很冷,又,下雪,P13,：,5(7),形式自然语言：,如果,水是清的，,那么,或者,张三能见到池底,或者,他是个近视眼,设,P,：水是清的，,Q,：张三能见到池底，,R,：张本是个近视眼,P,(,Q,R,),(,Q,R,),P,(,Q,R,),不可兼或,第,1,章习题,P13,：,6,将下公式写成,波兰式,和,逆波兰式,(1),P,Q,R,S,P,Q,R S,P Q R,S,P,(,W,R,),Q,P,W R,Q,或,P,W R,Q,P,W R,Q,第,4,章 谓词逻辑的基本概念,4.1,谓词和个体词,4.2,函数和谓词,4.3,合式公式,4.4,自然语句的形式化,4.5,有限域下公式,(,x)P(x,),、,(,x)P(x,),的表示法,4.6,公式的普遍有效性和判定问题,一阶逻辑,在命题逻辑中最基本的研究对象是命题,一个原子命题是不能再分割的,两个命题之间没有任何内在的联系,这种研究方法显然不足以刻划世界上事物间千变万化的逻辑关系,就连最古老、最简单的,苏格拉底,三段论,也无法从命题逻辑中推出,前提：凡人都是要死的,p,苏格拉底是人,q,结论：苏格拉底是要死的,r,p,q,r,谓词演算,谓词演算,(,一阶谓词演算）是命题演算的扩充和发展,一阶,谓词演算,是重要的符号逻辑系统,它是,程序设计理论,、,语义形式化,及,程序逻辑研究,的重要基础，是,程序验证,、,程序分析、综合及自动生成,、,定理证明,和,知识表示,的有力工具,。,4.1,谓词和个体词,在谓词演算中，将原子命题分解为,谓词,和,个体,两部分。,如：,张三,是,人,。,个体,可以独立存在的东西，,它可以是一个具体的事物，也可以是一个抽象的概念。,谓词,用于刻划个体的性质和个体之间的关系,个体,谓词,个体,考察下面的三个原子命题：,李玲,是优秀共青团员。,张华,比,李红,高。,小高,坐在,小王,和,小刘,的中间。,个体的分类,个体常项,：,表示具体或特定个体的标识符,如,a,：李玲，,b,：张华，,c,：李红，,d,：小高，,e,：小王，,f,：小刘,个体变项,：,表示任意个体或泛指某类个体的标识符,如：偶数、生物，,用,x,y,z,表示,个体域,D,个体变项的变化范围,有限个体域：,如,a,b,c,1,2,无限个体域：,如,N,Z,R,全总个体域,:,宇宙间一切事物组成（,默认的个体域,）,谓词,考察下面的三个原子命题：,李玲,是优秀共青团员,。,张华,比,李红,高,。,小高,坐在,小王,和,小刘,的中间,。,谓词,:,用于,刻划个体性质或各个个体的关系，常用大写英文字母表示。,谓词常项,：,如：,F,:,是人,，则,F,(,a,),：,a,是人,谓词变项,：,如：,F,:,具有性质,F,，则,F,(,x,),：,x,具有性质,F,如：可用,F,，,G,，,H,表示上面三个命题中谓词：,F,：,是优秀共青团员。,G,：,比,高。,H,：,坐在,和,的中间,。,谓词,考察下面的三个原子命题：,李玲,是优秀共青团员,。,张华,比,李红,高,。,小高,坐在,小王,和,小刘,的中间,。,如：可用,F,，,G,，,H,表示上面三个命题中谓词：,F,：,是优秀共青团员。,G,：,比,高。,H,：,坐在,和,的中间,。,谓词的分类,一元谓词,:,刻划一个个体的性质，如谓词,F(x,),多元谓词,:,刻划两个或以上个体间的关系，,如,L,(,x,y,),：,x,与,y,有关系,L,，,L,(,x,y,),：,x,y,，,如谓词,G(x,y,),、,H(x,y,z,),0,元谓词,:,不含个体变项的谓词,即命题常项或命题变项,F(a,),G(b,c,),H(d,e,f,),a,：李玲，,b,：张华，,c,：李红，,d,：小高，,e,：小王，,f,：小刘,函数,它是某个体域到另一个体域的映射，由一个谓词字母和,n,个个体变项组成的表达式：,F(,x,y,z,),注意：,F(,x,y,z,),不是命题，它的真值无法确定，要想使它成为命题，必须指定某一谓词常项代替,F,，,同时还要用,n,个个体常项代替,n,个个体变项。,如：,L(x,y),是一个二元谓词，它不是命题。,当令,L,表示“小于”之后，,L(x,y),还不是命题。,当令,a=2,，,b=3,时，,L(a,b),才是命题，并且是真命题。,当令,c=2,，,d=1,时，,L(c,d),为假命题。,4.2,函数和量词,将下列命题用谓词符号化,(1),如果,23,，则,33,，,q,：,3,y,，,G,(,x,y,),：,x,y,命题符号化为,F,(2,3),G,(3,4,),(2),2,是素数且是偶数。,在命题逻辑中,设,p,:2,是素数,q,:2,是偶数,命题符号化为：,p,q,这是真命题,在一阶逻辑中,设,F,(x,),：,x,是素数。,G,(x,),：,x,是偶数。,a,：,2,，,命题,符号化为：,F,(a,),G,(a,),将下列命题用谓词符号化,(3),如果张明比李民高，李民比李民高，则张明比赵亮高。,解：,在命题逻辑中，,设：,p,：,张明比李民高,，,q,：李民,比李民高,r,：,张明比赵亮高,则命题符号为,：,p,q,r,在一阶逻辑中，,设,H,(,x,y,),：,x,比,y,高。,a,：张明；,b,：李民；,c,：赵亮，,则命题符号化为：,H,(,a,b,),H,(,b,c,),H,(,a,c,),4.2.2,量词,引入量词表示个体域中所有个体或部分个体具有某种性质。,全称量词,:,表示任意的,所有的,一切的等,如,:,x,表示对个体域中所有的,x,xF(x,),表示个体域里的所有个体都有性质,F,存在量词,:,表示存在,有的,至少有一个等,如,:,x,表示在个体域中存在,x,xF(x,),表示存在着个体域中的个体具有性质,F,（,1,）每个人都有一双手。,（,2,）有的人很聪明。,（,1,）每个人都有一双手。,（,2,）有的人很聪明。,第一种情况,考虑个体域,D,为,人类集合。,(1),符号化为：,xF(x,),，,其中,F(x,),：,x,都有一双手,。,这个命题是真命题。,(2),符号化为,xF(x,),，,其中,F(x,),：,x,很聪明,。,这个命题也是真命题。,在一阶逻辑中将下面命题符号化,（,1,）每个人都有一双手。,（,2,）有的人很聪明。,第二种情况，考虑个体域,D,为,全总个体域。,引出一个新的谓词，将人分离出来,:,M(x,),：,x,是人。,称这个谓词为,特性谓词,。,在全总个体域的情况下，以上两命题可叙述如下,(1),对所有个体而言，如果它是人，则它有一双手,。,(2),存在着个体，它是人并且很聪明。,则（,1,）符号化为,x(,M(x)F(x,),（,2,）,符号化为,x(,M(x)F(x,),，,在一阶逻辑中将下面命题符号化,4.2.3,约束变元和自由变元,定义,在公式,(,x,),A,和,(,x,),A,中，称,x,为,指导变元,，称,A,为,辖域,.,在,x,和,x,的辖域中，,x,的所有出现都称为,约束出现，,A,中不是约束出现的其他变元均称为是,自由变元,。,如：在公式,(,x,),(,F,(,x,y,),G,(,x,z,),中,A,=(,F,(,x,y,),G,(,x,z,),为,x,的辖域，,x,是,约束变元,，,y,与,z,均为自由变元。,如,(,x,),P,(,x,),(,z,),Q,(,x,z,),(,y,),R,(,x,y,),Q,(,x,y,),在,x,中，,x,、,y,、,z,是约束变元，,Q,(,x,y,),中,x,，,y,是自由变元。,闭式,:,不含自由变元的公式,.,约束变元的换名规则,如：,(,x,),P,(,x,),R,(,x,y,),(,x,),的辖域为,P,(,x,),，,x,是约束变元,R,(,x,y,),中,x,y,都是自由变元,x,既可以是约束的、又可以是自由的，容易混淆。,换名规则,将量词辖域中的某个约束出现的个体变项及对应的指导变项改成公式中未曾出现的个体变项符号，公式中的其余部分不变。,注意：,改名时一定要更改为辖域中没有出现的变元名称,。,例如,：,(,x,),P,(,x,),R,(,x,y,),改名为：,(,z,),P,(z),R,(,x,y,),或,(,x,),P,(,x,),R,(,z,y,),自由变元的代入规则,代替规则,对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。,注意：,用以代入的变项与原公式中所有变项名不能相同,如：,(,x,),F,(,x,),G,(,x,y,),利用代替规则：,(,x,),F,(,x,),G,(,z,y,),(,x,),P,(,x,)(,z,),Q,(,x,z,)(,y,),R,(,x,y,),Q,(,x,y,),对,Q,(,x,y,),中自由出现的,x,用,t,代入，,y,用,s,代入则：,(,x,),P,(,x,)(,z,),Q,(,x,z,),(,y,),R,(,x,y,),Q,(,t,s,),4.3,合式公式,(,谓词公式,),量词的作用范围：,量词仅作用于个体变元，不允许作用于命题变项和谓词变项，不出现：,(,p,)(,F,(,x,y,),p,),(,F,)(,F,(,x,y,),G,(,x,z,),本课程中用到的符号说明：,命题变项：,p,q,r,p,i,q,i,r,i,i,1,个体变项：,x,y,z,x,i,y,i,z,i,i,1,个体常项：,a,b,c,a,i,b,i,c,i,i,1,谓词变项：,P,Q,R,P,i,Q,i,R,i,i,1,谓词常项：,GREAT,ON,函数符号：,f,g,h,f,i,g,i,h,i,i,1,量词符号：,联结词符号：,括号与逗号：,(,),，,合式公式,(,谓词公式,),合式公式,定义如下：,(1),命题常项、命题变项和原子谓词公式（不含联结词的谓词）是合式公式,.,(2),若,A,是合式公式，则,(,A,),也是合式公式,(3),若,A,B,是合式公式，则,(,A,B,),(,A,B,),(,A,B,),(,A,B,),也是合式公式,(4),若,A,是合式公式，而,x,在,A,中是自由变元，则,(,x,),A,(,x,),A,也是合式公式,(5),只有适合以上,4,条的才是,合式公式,.,如：,(,x)(,M(x,),F(x,),4.4,自然语句的形式,化,自然数集的形式描述,对每个数，有且仅有一个相继后元,解：,注意到题目中没给个体域,一律用,全总个体域,设：,谓词,E(x,y,),：,x=y,函数,f(x,)=x+1(,表示个体,x,的相继后元,),理解为：,对每个,x,都存在,y,y,是,x,的相继后元，且对任一,z,，若它也是,x,的相继后元，则必有,y=z,形式化为：,(,x)(,y),(,E(y,f(x,),(,z)(,E(z,f(x),E(y,z,),),自然语句的形式,化,自然数集的形式描述,没有这样的数，,0,是其相继后元,解：,注意到题目中没给个体域,一律用,全总个体域,设：,谓词,E(x,y,),：,x=y,函数,f(x,)=x+1(,表示个体,x,的相继后元,),理解为：,不存在,x,，它的相继后元为,0,形式化为：,(,x),(,E(0,f(x),),自然语句的形式,化,自然数集的形式描述,对除,0,外的数，有且仅有一个相继前元,解：,注意到题目中没给个体域,一律用,全总个体域,设：,谓词,E(x,y,),：,x=y,函数,g(x,)=x-1(,表示个体,x,的相继前元,),理解为：,对每个,x,若,x,0,都存在,y,y,是,x,的相继前元，且对任一,z,，若它也是,x,的相继前元，则必有,y=z,形式化为：,(,x)(,E