离散完整ppt课件2.12

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,第,2,章 一阶逻辑,2.1,一阶逻辑基本概念,2.2,一阶逻辑合式公式及解释,2.3,一阶逻辑等值式,观点卜瓷徐肖韦伏妈柔港涂板支湍陷靴奉常哉娠些哉炉俱吃赌稼宇死护松离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,2,2.1,一阶逻辑基本概念,个体词,谓词,量词,一阶逻辑中命题符号化,隘镐涯邮学蹦修浪混胎环盟椭展阶黑杜茬炬件修泰进蟹栏参捷甸疏坠淋垂离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,3,基本概念,个体词、谓词、量词,个体词（个体）,:,所研究对象中可以独立存在的具,体或抽象的客体,个体常项,：具体的事物，用,a,b,c,表示,个体变项,：抽象的事物，用,x,y,z,表示,个体域,:,个体变项的取值范围,有限个体域,，如,a,b,c,1,2,无限个体域,，如,N,Z,R,全总个体域,:,宇宙间一切事物组成,仙溉沁吃勉管排挫吴穴烹恍辜迟停票潘货膛淑笛棕姥够刹逆悉汀朵坊窍贤离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,4,基本概念,(,续,),谓词,:,表示个体词性质或相互之间关系的词,谓词常项,：,F,(,a,),：,a,是人,谓词变项,：,F,(,x,),：,x,具有性质,F,一元谓词,:,表示事物的性质,多元谓词,(,n,元谓词,n,2),:,表示事物之间的关系,如,L,(,x,y,),：,x,与,y,有关系,L,，,L,(,x,y,),：,x,y,，,0,元谓词,:,不含个体变项的谓词,即命题常项或命,题变项,顶敞炒衬豹闸修充察终捻啃探威改掇绦侣涟飞抄提翠沸忍龟哦至守倦漏愤离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,5,基本概念,(,续,),量词,:,表示数量的词,全称量词,:,表示任意的,所有的,一切的等,如,x,表示对个体域中所有的,x,存在量词,:,表示存在,有的,至少有一个等,如,x,表示在个体域中存在,x,栈唤锋霍纫履翠傀捶挎蹬次努田吓帧芝晤留俭独叮巫郭纺说淌挠鹅桅碧扯离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,6,一阶逻辑中命题符号化,例,1,用,0,元谓词将命题符号化,要求：先将它们在命题逻辑中符号化，再在一阶,逻辑中符号化,(1),墨西哥位于南美洲,在命题逻辑中,设,p,:,墨西哥位于南美洲,符号化为,p,这是真命题,在一阶逻辑中,设,a,：墨西哥，,F,(,x,),：,x,位于南美洲,符号化为,F,(,a,),仆力种贫招庆辅厅娱扇嚏谎糯售蹈砚郭录恫棕刑淮毅缉酬饭朽彭扶溺赠赤离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,7,例,1(,续,),(2),是无理数仅当 是有理数,在命题逻辑中,设,p,：是无理数，,q,：是有理数,.,符号化为,p,q,这是假命题,在一阶逻辑中,设,F,(,x,):,x,是无理数,G,(,x,):,x,是有理数,符号化为,(3),如果,23,，则,33,，,q,：,3,y,，,G,(,x,y,),：,x,y,x,(,F,(,x,),y,(,G,(,y,),L,(,x,y,),或,x,y,(,F,(,x,),G,(,y,),L,(,x,y,),两者等值,(2),令,F,(,x,):,x,是无理数,G,(,y,):,y,是有理数,L,(,x,y,),：,x,y,x,(,F,(,x,),y,(,G,(,y,),L,(,x,y,),或 ,x,y,(,F,(,x,),G,(,y,),L,(,x,y,),两者等值,泣党瞥嚏律置躇浮膜汕窑信讨隘托姨尖智予拷宾询达伊彪培曰萄舵命对谤离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,10,一阶逻辑中命题符号化,(,续,),几点注意：,1,元谓词与多元谓词的区分,无特别要求，用全总个体域,量词顺序一般不能随便颠倒,否定式的使用,思考：,没有不呼吸的人,不是所有的人都喜欢吃糖,不是所有的火车都比所有的汽车快,以上命题应如何符号化？,葡财组磋柿均忿呼锑代妆疲炙汞磺迪吁芹纤径碎罢臻佳沦盒力峙眨酪汽梅离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,11,2.2,一阶逻辑公式及解释,字母表,合式公式,(,简称公式,),个体变项的自由出现和约束出现,解释,永真式（逻辑有效式）,矛盾式（永假式）,可满足式,格奔厕垂剪撼二吵靛酸盾拆沾绥别叔婚晶停马摸刚祥给盏筐弘匙写抉致顾离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,12,字母表,定义 字母表,包含下述符号：,(1),个体常项：,a,b,c,a,i,b,i,c,i,i,1,(2),个体变项：,x,y,z,x,i,y,i,z,i,i,1,(3),函数符号：,f,g,h,f,i,g,i,h,i,i,1,(4),谓词符号：,F,G,H,F,i,G,i,H,i,i,1,(5),量词符号：,(6),联结词符号：,(7),括号与逗号：,(,),，,褂耘桑芦候钒列舶卒许蚂孪碎阂寿噎午几翌祸位魄洒督冻页湃浊称腆矽锣离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,13,项,定义 项,的定义如下：,(1),个体常项和个体变项是项,.,(2),若,(,x,1,x,2,x,n,),是任意的,n,元函数，,t,1,t,2,t,n,是任意的,n,个项，则,(,t,1,t,2,t,n,),是项,.,(3),所有的项都是有限次使用,(1),(2),得到的,.,个体常项、变项是项，由它们构成的,n,元函数和复,合函数还是项,唉泪缝话悯脖攻予塞克娃橇汪短辞淀氧吭耐戳遭梯绢伐涅弘掐章忙占娠钵离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,14,原子公式,定义,设,R,(,x,1,x,2,x,n,),是任意的,n,元谓词，,t,1,t,2,t,n,是任意的,n,个项，则称,R,(,t,1,t,2,t,n,),是,原子公式,.,原子公式是由项组成的,n,元谓词,.,例如，,F,(,x,y,),F,(,f,(,x,1,x,2,),g,(,x,3,x,4,),等均为原子公式,畏娇事汞遥皮争左爽直德猴证蔡蓬苔赊蝇抿刊太沼刘酪场纫芋云淄沮魂龋离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,15,合式公式,定义 合式公式,（简称,公式,）定义如下：,(1),原子公式是合式公式,.,(2),若,A,是合式公式，则,(,A,),也是合式公式,(3),若,A,B,是合式公式，则,(,A,B,),(,A,B,),(,A,B,),(,A,B,),也是合式公式,(4),若,A,是合式公式，则,xA,xA,也是合式公式,(5),只有有限次地应用,(1)(4),形成的符号串是合,式公式,.,请举出几个合式公式的例子,.,枷炕柴令碗陇冷喀扔恳覆堕臀谍拈吟闽跟漠玫脐溪荔赘唇扮咯协价浦烫贱离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,16,个体变项的自由出现与约束出现,定义,在公式,xA,和,xA,中，称,x,为,指导变元,，,A,为相,应量词的,辖域,.,在,x,和,x,的,辖域,中，,x,的所有出现都,称为,约束出现,，,A,中不是约束出现的其他变项均称,为是,自由出现的,.,例如,在公式,x,(,F,(,x,y,),G,(,x,z,),中,A,=(,F,(,x,y,),G,(,x,z,),为,x,的辖域，,x,为指导变元,A,中,x,的两次出现均为约束出现，,y,与,z,均为自由出现,.,闭式,:,不含自由出现的个体变项的公式,.,栽畔乃仆舶质卡攫捏映维那川婶泅毛吗否较无我朔得透恒拆乾冯碑咳羞盈离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,17,公式的解释与分类,给定公式,A,=,x,(,F,(,x,),G,(,x,),成真解释,:,个体域,N,F,(,x,),:,x,2,G,(,x,):,x,1,代入得,A,=,x,(,x,2,x,1),真命题,成假解释,:,个体域,N,F,(,x,),:,x,1,G,(,x,):,x,2,代入得,A,=,x,(,x,1,x,2),假命题,问,:,xF,(,x,),x,F,(,x,),有成真解释吗？,xF,(,x,),x,F,(,x,),有成假解释吗？,署仔酉摹吹粮粱绘侥润艳趴逝巡戳雪捎坪看介乏吐锁炬肄呈雹饥嫁已士澡离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,18,解释,定义,解释,I,由下面,4,部分组成：,(a),非空个体域,D,I,(b),D,I,中一些特定元素 等,(c),D,I,上一些特定函数 等,(d),D,I,上一些特定谓词 等,说明：,被解释的公式,A,中的个体变项均取值于,D,I,若,A,中含个体常项,a,、函数,f,、谓词,F,就分别解释,成 、,苛撒獭粳瘪赎园涉暴剿号臂拐咒斤丑迭掷际瘪机莱揭朝艾米咨谩件睡曹洗离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,19,解释,(,续,),被解释的公式不一定全部包含解释中的,4,部分,.,闭式在任何解释下都是命题，,注意不是闭式的公式在某些解释下也可能是命题,.,坞声方镭餐毒醉汇蚂痰窖俞名笨误修洞猎盈帚条叛急彼厅烁罩曳扎路憨斜离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,20,公式的分类,永真式（逻辑有效式）,：无成假赋值,矛盾式（永假式）,：无成真赋值,可满足式,：至少有一个成真赋值,几点说明：,永真式为可满足式，但反之不真,谓词公式的可满足性（永真性,永假性,),是不可判,定的,利用代换实例可判某些公式的类型,氏甸厘薪隐乃琢拷肇入氛拓匠渗虽邻猜秧惫饼赌盔睬褂瓢会茫转握赖臭拳离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,21,代换实例,定义,设,A,0,是含命题变项,p,1,p,2,p,n,的命题公式，,A,1,A,2,A,n,是,n,个谓词公式，用,A,i,处处代替,A,0,中的,p,i,(1,i,n,),，所得公式,A,称为,A,0,的,代换实例,.,例如,:,F,(,x,),G,(,x,),xF,(,x,),yG,(,y,),等都是,p,q,的换实例，,x,(,F,(,x,),G,(,x,),等不是,p,q,的代换实例,.,定理,重言式的代换实例都是永真式，矛盾式的代,换实例都是矛盾式,.,契寇闹亨栖身鹅霹蜘居黎丹炬蓖秧庸喂堪辟啊盂叼堪整蔽骸抹屉卫宏碾焰离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,22,代换实例,(,续,),例,1,给定解释,I,如下,:,(,a,),个体域,D,=N,(,b,),(,c,),(,d,),谓词,说明下列公式在,I,下的涵义,并讨论真值,(1),xF,(,g,(,x,a,),x,),x,(2,x=x,),假命题,(2),x,y,(,F,(,f,(,x,a,),y,),F,(,f,(,y,a,),x,),x,y,(,x+,2=,y,y,+2=,x,),假命题,湍宾烂月裁呻苫蚀烯谅启外抛酷蕉茅吓储丹胚契寨流断甩浊疚否闪撅侄帮离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,23,例,1,(,续,),(3),x,y,zF,(,f,(,x,y,),z,),两点说明,:,5,个小题都是闭式,在,I,下全是命题,(3),与,(5),说明，量词顺序不能随意改变,(5),x,y,zF,(,f,(,y,z,),x,),x,y,z,(,y+z,=,x,),假命题,(4),xF,(,f,(,x,x,),g,(,x,x,),x,(2,x,=,x,2,),真命题,x,y,z,(,x+y,=,z,),真命题,釉案盾茬砰限肿很刘盎攻徒父侩蒜死萤惑增讥追幼艘鹰冲困稿蕊袖摈夯拆离散完整,ppt,课件,2.1-2,离散完整,ppt,课件,2.1-2,24,代换实例,(,