离散数学的谓词逻辑详解省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,谓 词 逻 辑,第1页,2025/3/31 周一,1,命题逻辑不足,苏格拉底三段论：,P,：全部人都是要死。,Q,：苏格拉底是人。,R,：所以苏格拉底要死。,凭直觉知道这个结论是真，推理是有效。不过，借助命题演算推理理论，却不能推导出这个结论（无法证实它正确性）。,Why?,第2页,2025/3/31 周一,2,此三段论论断显然正确。,不过，在命题逻辑中无法得到正确性反应,:PQ,R,不是重言式！,命题逻辑不能正确反应此三段论推理过程。这是命题逻辑不足,!,第3页,2025/3/31 周一,3,原 因,在命题逻辑中无法将简单命题之间内在联络反应出来。命题逻辑中描述上述三段论，即,PQR,，使,R,与命题,P,、,Q,无关独立命题。,不过，实际上,R,与命题,P,、,Q,是相关系，只是这种关系在命题逻辑中得不到反应。,要反应这种内在联络，需对简单命题作,深入分解,，分解出其中成份，包含：个体词，谓词，量词，函词等，研究它们形式结构及逻辑关系，总结出正确推理形式和规则，这就是一阶逻辑所研究内容,.,一阶逻辑也称谓词逻辑。谓词逻辑是一个表示能力更强逻辑。,第4页,2025/3/31 周一,4,谓词逻辑,我们将介绍谓词逻辑基本概念和符号。关于命题、命题真值、命题词、命题常量和命题变元以及逻辑五个联结词其含意和在命题逻辑中基本相同，,本章中只介绍谓词逻辑中新出现基本概念和符号，其中主要是,个体词，谓词，量词以及函词,。,第5页,2025/3/31 周一,5,1.,谓词与个体词,将简单命题分解成个体与谓词这么两个组成部分。谓词，通常是用来描述个体性质或特征，或者个体之间关系。,谓词逻辑，是命题逻辑扩充与发展,。,例,1,：下面两个命题,1.,张华是学生,2.,李明是学生,a:,张华,b:,李明,H,：是学生，则,H,（,x,）,:x,是学生,1,，,2,可分别表示成,H(a),，,H(b).,这么表示就揭示了两命题间有相同谓语这一特征。,第6页,2025/3/31 周一,6,例,2,：,张华比李明高,令,a:,张华,b:,李明,L(x,，,y):x,高于,y,该命题可表示为：,L(a,，,b),例,1,和例,2,中,H,、,L,称为谓词，,其中,H,是一元谓词，表示个体性质（是什么），,L,是二元谓词，表示个体之间关系。,注,：（,1,）,惯用大写拉丁字母表示谓词,.,（,2,）,谓词是用来刻划个体性质或者个体之间关系。,第7页,2025/3/31 周一,7,命题函数与命题,例,:,令,P(x),表示,x,为质数，则,P(x),为一元谓词。,令,H(x,，,y),表示“,x,高于,y”,则,H(x,，,y),为二元谓词。,则：,H(,张三，李四,),表示“张三高于李四”，是命题。,注意,：,P(x.y),H(x,，,y),为命题函数,.,P(2),与,H(,张三，李四,),才是命题。,谓词中假如有,n,个变元则称为,n,元谓词,.n,元谓词反应了个体之间,n,元关系,.,第8页,2025/3/31 周一,8,2.,个体词,个体是能够独立存在实体，它能够是一个详细,事物,-,个体常元，,惯用小写拉丁字母,a,，,b,，,c等表示。,也能够是一个抽象概念（即没指定哪一个个体）,-,个体变元,，惯用小写拉丁字母：,x,，,y,，,z,等表示,第9页,2025/3/31 周一,9,函词,例：,张华哥哥比李明高,a:,张华,b:,李明,L(x,，,y):x,高于,y,f(x):x,哥哥,则上述符号化为：,L(f(a),，,b),f,称为,函词,定义,：一个,n,元函词,即是一个论域上一个,n,元函数,第10页,2025/3/31 周一,10,变元在谓词中次序直接影响了谓词取值。,如,:,设谓词,P(x,，,y),为“,x,比,y,高”，,设张三为,170cm,，李四为,180cm.,则,:P(,李四，张三,),为真命题。,P(,张三，李四,),为假命题,.,概念讨论,第11页,2025/3/31 周一,11,命题符号化,例,1:,武汉位于重庆与上海之间,.,解,:,用个体词,a,，,b,，,c,分别表示武汉，重庆和上海，,谓词,P(x,，,y,，,z),表示,x,位于,y,与,z,之间，,则该命题表示为,:,P(a,，,b,，,c).,例,2,：假如王英坐在李红后面，则王英比李红高,.,解：令,a:,王英,;b:,李红,;P(x,，,y):x,坐在,y,后面,;,G(x,，,y):x,比,y,高,.,则该命题表示为：,P(a,，,b),G(a,，,b).,第12页,2025/3/31 周一,12,3.,量词,使用前面介绍概念，还不足以表示日常生活中各种命题。,比如：,“,全部正整数都是素数,”,“,有些正整数是素数,”,两种量词,:,全称量词和存在量词,.,第13页,2025/3/31 周一,13,全称量词,:,1.,全称量词：,（任意，全部）,x:,“,对一切,x,”,，,“,对全部,x,”,，,“,对任一,x,”,如：,x P(x),“,对一切,x,，,P(x),是真,”,x P(x),“,并非对一切,x,，,P(x),是真,”,x,P(x),“,对一切,x,，,P(x),是真,”,如,:“,全部些人都是要死”,设,x,个体域为全体人集合，则可表示为,x,D(x),第14页,2025/3/31 周一,14,存在量词,:,2.,存在量词：,（存在）,x:,“,存在,x,“,、,”,一些,x,“,、,”,最少有一,x,”,如：,x P(x),“,存在,x,，,P(x),是真,”,x,P(x),“,存在,x,，,P(x),是真，并非这么,”,x,P(x),“,存在,x,，,P(x),是真,”,如,:,“,有些有理数是整数。,”,令,(x,）：,x,是整数，,设,x,个体域为有理数集合，,则命题可表示为,：,x I,(x,）,第15页,2025/3/31 周一,15,4.,论 域,含有量词命题表示式形式，与论域相关。用量词量化后命题，其值也与,论域,相关,。,例,1,x,（,x=0),若论域为整数集，则此命题值为真，,若论域为正整数集，则命题值为假。,为了方便，引入全总个体域，记为：,U,，简称,全域,:,定义,:,宇宙间全部个体聚集在一起所组成集合称为,全域。,第16页,2025/3/31 周一,16,特征谓词,后面讨论中，除特殊说明外，均使用,全域,。而对个体改变真正取值范围，用特征谓词加以限制。,普通地，对全称量词，特征谓词作蕴含前件引入；而对存在量词，特征谓词常作为合取项引入。,第17页,2025/3/31 周一,17,例,(1)“,全部人都是要死。”,(2)“,有人不怕死。”,1.,当,x,个体域为,全体人,组成集合时，符号化上述命题。,解,:,令,D,（,x,）x,是要死，令,G,（,x,）：,x,怕死。,则（,1,）可表示为,:,x,D(x),。,（,2,）可表示为,:,x,G(x),。,第18页,2025/3/31 周一,18,论域为全域时,2.,当取,x,个体域为全域时，必须引入一个特征谓词将“人”从全域中分离出来。,（,1,）对全部个体而言，假如它是人，则它是要死。,（,2,）存在着个体，它是人而且它不怕死,于是令,M,（,x,）：,x,是人。,（,1,）,x,（,M(x)D(x),（,2,）,x,(M,（,x,）,G,（,x,）,第19页,2025/3/31 周一,19,命题符号化,(,翻译,),：,将汉语(或其它自然语言)语句翻译成逻辑表示式，这在数学、逻辑编程、人工智能、软件工程以及许多其它学科中都是一项主要任务。翻译目标是生成简单而有用逻辑表示式。,第20页,命题符号化,：,例：没有不犯错误人,令,H,（,x,）：,x,是人，,M,（,x,）：,x,犯错误,例：存在着偶质数,令,E(x),：,x,是偶数，,P(x),：,x,是质数,则有：,x(E(x)P(x),第21页,2025/3/31 周一,21,例,：,每个自然数都有后继数,若令：,N,（,x,）：,x,是自然数，,H,（,x,，,y,）：,y,是,x,后继数,例：对平面上任意两点，有且仅有一条直线经过这两点。,若令,P,（,x,）：,x,是一个点，,L,（,xx,是一条直线，,T,（,x,，,y,，,z,）：,z,经过,x,，,y,，,E,（,x,，,y,）：,x,等于,y,第22页,2025/3/31 周一,22,例,5,将以下命题符号化,(,使用全域,),。,(,1),发光并非都是金子,令：,P,（,x,）：,x,发光；,G,（,x,）：,x,是金子。,则该命题可表示为：,（,2,）全部运动员都钦佩一些教练。,令：,P,（,x,）：,x,是运动员；,T,（,x,）：,x,是教练；,Q,（,x,，,y,）：,x,钦佩,y,。,则该命题可表示为：,第23页,2025/3/31 周一,23,（,3,）凡是实数均能比较大小。,若令,R,（,x,x,是实数；,G,（,x,，,y),：,x,与,y,可比较大小,.,则该命题可表示为：,例,6,将苏格拉底三段论进行符号化：,令：,(x),：,x,是人,(x):x,要死,则,第24页,2025/3/31 周一,24,量化断言与命题关系,(,1),假如叙述域是有限，不妨设叙述域是,1,，,2,，,3,，则,x P(x),P(1)P(2)P(3),x P(x),P(1)P(2)P(3),(2),假如叙述域是可数无限，比如自然数集合，我们能够这么了解：,(,x)P(x),P(1)P(2)P(3),(,x)P(x),P(1)P(2)P(3),(3),假如叙述域不可数无限，则无法表示,。,第25页,2025/3/31 周一,25,练习,任何金属都能够溶解在某种液体中,.,令,J(x):x,是金属,;,E(x):x,是液体,;,S(x,，,y):x,能够溶解在,y,中，,第26页,2025/3/31 周一,26,原子与公式,设,P(x,1,，,x,n,),是,n,元谓词，则称其为为原子公式，或简称,原子,谓词公式，简称为,公式,，其递归定义为：,（,1,）原子是合式公式；,（,2,）若,A,是合式公式，则,(A),也是合式公式；,（,3,）若,A,，,B,是合式公式，则,(AB),，,(AB),，,(A,B),，,(A,B),也是合式公式；,（,4,）若,A,是合式公式，,x,是,A,中变量符号，,（,5,）只有有限次地使用（,1,）,（,4,）所生成符号串,才是合式公式。,第27页,2025/3/31 周一,27,前面各命题符号化结果都是合式公式。,对于一个谓词，假如其中每一个变量都在一个量词作用之下，则它就不再是命题函数而是一个命题了。,不过，这种命题和命题逻辑中命题还是有区分。因为这种命题中毕竟还有变量，尽管这种变量和命题函数中变量有所不一样。所以，有必要区分这些变量。,第28页,2025/3/31 周一,28,例,1,：令,P,（,x,，,y,）：“,xy.,则,A(y),是真命题,原因是,:,条件,2),不满足。,第58页,2025/3/31 周一,58,存在推广规则,EG,使用此规则时注意,:,(1),c,是个体域中某个确定个体。,(2),代替,cx,不能已在,A(c),中出现。,比如：设,A(x，y):xy,，考查下面推理过程,:,(1),A(x，c),(2),是错误！原因在于代替,cx,已在,A(x),中出现,第59页,2025/3/31 周一,59,存在指定规则,(ES,规则,):,成立条件：,1)c,是使,A(c),为真常量符号,3)A(x),中自由变元只有,x.,比如,：,设,D,为自然数集，,F(x),表示“,x,是奇数”，,G(x),表示“,x,是偶数”,.,注意：以上四条规则中,A(x),都是公式,第60页,2025/3/31 周一,60,但，若不注意使用条件，则有：,前提引入,化简，依据（,1,）,ES,规则，依据（,2,）,化简，依据（,1,）,ES,规则，依据（,4,）,合取，依据（,3,），（,5,）,EG,规则，依据（,6,）,于是得出：,（,）,违反了条件,2,）,第61页,2025/3/31 周一,61,例,1,证实：,证实以下：,前提引入,US,规则，依据（,1,）,前提引入,ES,规则，依据（,3,）,化简，依据（,4,）,化简，依据（,4,）,假言推理，依据（,2,），（,6,）,合取，依据（,5,），（,7,）,EG,规则，依据（,8,）,第62页,2025/3/31 周一,62,本例也可作以下证实：前提引入,ES,规则，依据（,1,）,化简，依据（,2,）,前提引入,US,规则，依据（,4,）,假言推理，依据,(3),，,(5),化简，依据（,2,）,合取，依据（,6,），（,7,）,EG,规则，依据（,8,）,第63页,2025/3/31 周一,63,例,2,证实,：,苏格拉底三段论“凡人都是要死，苏格拉底是人，,所以苏格拉底是要死”。,证实,:,结论,:D(a),首先将命题符号化：设,M(x):x,是人,.D(x):x,是要死,.a:,苏格拉底,.,前提,:,证实,:,规则,US,规则，（,1,）,规则,假言推理，（,2,），（,3,）,第64页,2025/3/31 周一,64,例3,有些病人相信全部医生，不过病人都不相信骗子。证实：医生都不是骗子。,证实：,命题符号化：设论域为全域,P(x):,x,是病人；,D(x):x,是医生；,Q(x):x,是骗子；,R(x,，,y):x,相信,y,。,前提：,x(,P(x),y(D(y)R,(x,，,y),，,x,y(,P(x),Q(y)R,(x,，,y),结论：,x(D(x),Q(x),证实：,第65页,2025/3/31 周一,65,x(,P(x),y(D(y)R,(x,，,y),前提引入,P(c),y(D(y)R,(c,，,y)ES,，,(1),x,y(,P(x),Q(y)R,(x,，,y),前提引入,y(,P(c),Qy)R,(c,，,y)US,，,(3),P(c),Q(z)R,(c,，,z)US,，,(4),(,P(c),Q(z),R,(c,，,z),蕴涵等值式，,(5),P(c),Q(z),R,(c,，,z)De Morgan,律，,(6),P(c)(,Q(z)R,(c,，,z),蕴涵等值式，,(7),P(c),化简，,(2),Q(z)R,(c,，,z),析取三段论，,(8),，,(9),R,(c,，,z),Q(z),等值演算，,(10),y(D(y)R,(c,，,y),化简，,(2),D(z)R,(c,，,z)US,，,(12),D(z)Q(z),假言三段论，,(11),，,(13),x(,D(x)Q(x)UG,，,(14),第66页,2025/3/31 周一,66,例,4,：指出下面推理错误,x(F(x)G(x),前提引入,F(y)G(y)US,，,(1),xF(x),前提引入,F(y)ES,，,(3),G(y),假言推理，,(2),，,(4),xG(x)UG,，,(5),没有满足,ES,规则条件,1,即：,xA(x)A(c),c,是使,A(c),为真,常量,符号。,F(c)ES,，,(3),G(c),假言推理，,(2),，,(4),xG(x)EG,，,(5),第67页,2025/3/31 周一,67,例,证实下述论证正确性,人会说话，猴子不会说话，所以猴子不是人。,解：设论域为全域。设,M(x):x,是人。,S(x):x,会说话。,B(x):x,是猴子。,则前提为：,x(M(x)S(x),和,x(B(x)S(x),结论为：,x(B(x)M(x),证实,:,1,x(M(x)S(x)P,规则，前提,2 M(x)S(x)T,，,1,，,US,3,x(B(x)S(x)P,规则，前提,4 B(x)S(x)T,，,3,，,US,5 S(x)B(x)T,，,4,，逆反律,6 M(x)B(x)T,，,2,，,5,，,I6,7 B(x)M(x)T,，,6,，逆反律,8,x(B(x)M(x)T,，,7,，,UG,第68页,2025/3/31 周一,68,练习：符号化以下命题，并论证其结论：,任何人假如他喜欢步行，他就不喜欢乘汽车，每一个人或 者喜欢乘汽车，或者喜欢骑自行车。有人不爱骑自行车，因而有人不爱步行。,命题符号化：设,P(x):x,喜欢步行。,Q(x):x,喜欢乘汽车,.R(x):x,喜欢骑自行车。,推理形式结构：,第69页,2025/3/31 周一,69,结构形式：,前提引入,ES,，,(1),前提引入,US,，,(3),(5)Q(c),析取三段论,(2),，,(4).,前提引入,(7)P(c),Q(c),US,，,(6),(8),Q(c),P(c),等值演算，,(7).,EG,，,(9).,证实：推理以下：,(9)P(c),假言推理,(5),，,(8).,10,第70页,2025/3/31 周一,70,谓词逻辑应用实例,-,逻辑程序设计,有一类主要程序设计语言使用谓词逻辑规则进行推理。,比如,:Prolog(Programming in Logic),Prolog,程序包含一组申明，有两类语句,:Prolog,事实和,Prolog,规则。,Prolog,事实经过指定那些满足谓词元素来定义谓词。,Prolog,规则使用,Prolog,事实定义好谓词来定义新谓词。,(,主要应用在人工智能方面,),第71页,例,1,考虑一个,Prolog,程序，它给出事实是每门课程教师和学生注册课程，程序使用这些事实往返答相关给特定学生上课教授查询。,此程序中,Prolog,事实可能包含,:,instructor(chan,math273),instructor(patel,ee222),instructor(grossman,cs301),enrolled(kevin,math273),enrolled(juana,ee222),enrolled(juana,cs301),enrolled(kiko,math273),enrolled(kikoi,cs301),则一个新谓词,teacher(p,s),表示教授,p,教学生,s,，能够用,prolog,规则来定义,:,teacher(P,S):-instructor(P,C),enrolled(S,C)(Prolog,中用逗号表示谓词合取,),Prolog,使用给定事实和规则回答查询。,如,:,？,Enrolled(kevin,math273),生成应答,yes,?Enrolled(x,math273),生成应答,kevin kiko,?teacher(x,jinna),返回,patel grossman,第72页,本章习题,:,1.6：1,，,3,，,9,，,10,，（,13,，,17,，,21,，,22）,1.7:2,，,6,，,7,1.8:3,，,4,，,5,，,7（8）,第73页,2025/3/31 周一,73,第74页,2025/3/31 周一,74,