第二章 谓词逻辑1

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,/44,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,/44,2/44,离散数学,第二章 谓词逻辑,瞻钧宣声满吵音笋歇爵两媳诊劝韧铁傣枉挑汤墙渴繁目统怕拆熔勘丙教浸第二章 谓词逻辑1第二章 谓词逻辑1,3/44,谓词逻辑的引入,在命题逻辑中，试进行下列推理:,“苏格拉底三段论”：,凡人都是要死的，P,苏格拉底是人，Q,所以苏格拉底是要死的。R,(PQ)R,命题逻辑中，命题被当作一个基本的，不可分割的单位，只研究由原子命题和联接词所组成的复合命题，没有研究命题内部的内部结构以及 命题之间的内在关系。,宫雏惰调浚籍粤扮郊燎章庸猾庞焰撰啄弗吃伏糙郑盼踏坊丧摈搀癸圣岗侈第二章 谓词逻辑1第二章 谓词逻辑1,4/44,类似的还有很多，例如：,所有软件学院的学生在毕业之前都要通过离散数学考试，王思奇是软件学院的学生，所以王思奇在毕业之前需要通过离散数学考试。,所有的正整数都大于0，3是正整数，所以3大于0。,本章介绍的谓词逻辑，对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。引入了个体词、谓词、量词、谓词公式等概念，在此基础上研究谓词公式间的等值关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充和进行谓词演绎。,辈缎碟赎刺究框添啃菊殆肠娇逊迎嗡沤桌即佣瑞罩奇寐瘩抒貉譬唱俄瓷札第二章 谓词逻辑1第二章 谓词逻辑1,4,/9,本章内容,谓词、个体、量词,合式谓词公式,自由变元和约束变元,含有量词的等价式和永真蕴含式,谓词逻辑中的推理理论,前束范式、斯柯林范式,迢溪衣貌拳止耙馁淹矗氓发亡旱暴幢怔逸帜描咎船萍持侵洲俭倪涕钧春笛第二章 谓词逻辑1第二章 谓词逻辑1,5/44,2.1谓词演算,原子命题被分解为谓词和个体两部分。,个体：可以独立存在的事物。,老师，计算机，证书，道德，智商等。,谓词：用来刻划个体的性质或个体之间关系的词称为谓词，刻划一个个体性质的词称为一元谓词；刻划n个个体之间关系的词称为n元谓词。,本质上是把数学中的逻辑论证加以符号化。,遍鸡蜀赏琢盛炸绿厌赏邓姚脸詹币施甲酬症藻障竖赶誊减慈舌孔怨韧运撂第二章 谓词逻辑1第二章 谓词逻辑1,6/44,谓词和个体,例：,（1）李明是学生；,（2）张亮比陈华高；,（3）陈华坐在张亮与李明之间。,个体：李明，张亮，陈华,谓词：是学生；比高；坐在 和之间,一元谓词：是学生,二元谓词：比高,三元谓词：坐在 和之间,俗寺总妙硝跑削漾陆迎婪赁沸鱼可型贝管忻奢澜社电旋类佰凭菜丹段想亮第二章 谓词逻辑1第二章 谓词逻辑1,7/44,谓词和个体,（1）李明是学生；,（2）张亮比陈华高；,（3）陈华坐在张亮与李明之间。,一般用大写的英文字母表示谓词，而用小写的英文字母表示个体。,上述命题可分别表示为Q(a),P(b,c),R(c,b,a),一般地，由n个个体和n元谓词所组成的命题可表示为F（a1,a2,an）,其中F表示n元谓词,a1,a2,an 分别表示n个个体。,注意：a1,a2,an的排列次序是重要的。,厂侵实但史酮肉纳条讳敛藻峨描钒亿蛹师抖汲捧掷躯沂腻萧你怎恶荔棠晕第二章 谓词逻辑1第二章 谓词逻辑1,8/44,谓词和个体,对于F（a1,a2,an），如果括号内的个体是抽象的可变化的，那么F（a1,a2,an）称为n元原子谓词公式或n元命题函数。,注意：命题的n元谓词表示形式和n元命题函数不同?,a:张明。,命题函数：P(x)x是学生。,谓词表示形式:P(a)张明是学生。,揩附碧和签酚钢党榨固奎窗块咏猩茂姿痔驮捆戮蝗呐速痰者邓辞唉崭泣石第二章 谓词逻辑1第二章 谓词逻辑1,9/44,个体域,个体域可以是有限的，也可以是无限的。所有个体域的总和叫作全总个体域。以某个个体域为变化范围的变元叫个体变元。,个体域的变换范围影响到谓词公式的真假,R(x)：x是大连理工大学软件学院的学生,如果x的讨论范围是大工软件学院某个班级的学生,如果x的讨论范围是某个幼儿园里的小朋友,如果x的讨论范围是大连的所有市民,任何个体的变化都有一个范围，这个变化范围称为个体域(或论域)。,永真,永假,可满足,趣奇柔屡刹哀殊绳辰秦妙耙吭锣砂孟十形样祝握冰陇徒励豆睛赎埃睛戈瓮第二章 谓词逻辑1第二章 谓词逻辑1,10/44,谓词的阶,在谓词 中，如果个体变元是一些简单的事物，那么P为一阶谓词；,若个体变元中有一些是一阶谓词，那么P为二阶谓词；二阶以上递推。,本门课程仅研究一阶谓词,诵酪影动贾养惜忱携衡胺促陇蚂区旋险葫却练巍朱瑰柞眨骇摩滤宽拆搪悄第二章 谓词逻辑1第二章 谓词逻辑1,11/44,量词,使用前面介绍的谓词和个体变元，还不足以描述自然界的所有命题。,例：,描述命题“所有的正整数都大于0”以及命题“有些正整数是素数”。,量词的引入：量词指在命题里表示数量的词。,勿刀协藤亭政痪炬毖艺随缅踌彭蹲牌磷迸氰淀嫁酵低定辆胁模耍厩耽酋怜第二章 谓词逻辑1第二章 谓词逻辑1,12/44,全称量词,符号“”表示命题：“对于个体域中所有个体x，谓词P(x)均为T”。其中“”叫作全称量词，读作“对于所有的x”。谓词P(x)称为全称量词的辖域或作用范围。,例如：,所有的人都是要死的,令D(x)：x 是要死的。,则命题可表示为 x D(x),取个体域为全体人的集合，是真命题。,所有的正整数都是素数；,令 P(x)：x 是素数,则命题可表示成 x P(x),取个体域为正整数集，是假命题。,靡柒糊痘骏工俊熔赏攫温云英安全盖赋字酝刑兑纤限陕醒楷炮凯砂泄蛀驶第二章 谓词逻辑1第二章 谓词逻辑1,13/44,存在量词,符号“”表示命题：“在个体域中存在某些个体使谓词P(x)为T”其中“”叫作存在量词，读作“存在x”。谓词P(x)称为存在量词的辖域或作用范围。,例如：,有些正整数是素数；,令 P(x)：x 是素数,则命题可表示成 x P(x),取个体域为正整数集，是真命题。,佯殉薄贪述烁扑煞具开酮屹叙宙试某已声咽诫械论窄票胖蛹钦其侄坎饼毛第二章 谓词逻辑1第二章 谓词逻辑1,13/44,存在唯一量词!,符号“”表示命题：“在个体域中存在一个且只存在一个个体使谓词P(x)为T”其中“”叫作存在唯一量词，读作“恰有一个x”。谓词P(x)称为存在量词的辖域或作用范围。,例如：,恰有一个正整数是素偶数；,令 P(x)：x 是素偶数,则命题可表示成 !x P(x),取个体域为正整数集，是真命题。,牢喀嗅砾截夹筛枢浑珐实染嘱仲伯晤搪故窝攫儿铸亥充沏愿锨敛缨橱天映第二章 谓词逻辑1第二章 谓词逻辑1,14/44,量词,量词本身不是一个独立的逻辑概念，可以用 联结词取代。,设个体域 ，谓词可以表示成以下形式：,由量词确定的命题真值与个体域有关。,令 P(x)：x 是素数,则 x P(x)，如果取个体域为素数集，为真；如果个体域为整数集，为假。,盐霞胺蚤亮凿痕谗迅绷瓜本预漆郎德茶甸宏丝檄猩娩怨氨惩卧至镣魁硕尽第二章 谓词逻辑1第二章 谓词逻辑1,15/44,量词,为了方便起见，个体域一律用全总个体域，每个个体变元的真正变化范围则用一个特性谓词来刻划。,注意：对于全称量词应使用单条件逻辑联结词；对于存在量词应使用逻辑联结词合取。,R(x):x是自然数；P(x):x大于0.,以后不加强调个体域均指全总个体域,刚市眉圣其篇粟胁唇朔睫茄徐疥夸稍享给踩香膜豫嘴暑沙颐奴收织锑煮娠第二章 谓词逻辑1第二章 谓词逻辑1,16/44,量词,全称量词和存在量词不仅可以单独出现，还可以组合形式出现。,对于二元谓词P(x,y)，可能有以下几种量化的可能：,病简栗碘狞探驮批敌荡液班遁嘱酞屋咯作烹犁舶阎苛讶如潘褪诅稗惕斩灼第二章 谓词逻辑1第二章 谓词逻辑1,17/44,组合量词的含义,设A(x,y)表示x,y同姓，x的个体域是1班同学，y的个体域是2班同学。,：1班任何一个同学与2班的所有同学同姓；,：2班任何一个同学与1班的所有同学同姓；,：对1班的任意一个同学，2班都有人跟他同姓；,：存在一个2班同学和1班的所有同学同姓。,翻译时从左向右,辅赞普亮撑滇潦豁杏机萍赠床煮侈酗渡浇帘咬讲韭患局爵掌栅银伏拍窃荷第二章 谓词逻辑1第二章 谓词逻辑1,18/44,合式谓词公式,若P为不能再分解的n元谓词变元，x1,x2,xn是个体变元，则称P(x1,x2,xn)为原子公式或原子谓词公式。当n=0时，P表示命题变元即原子命题公式。所以，命题逻辑实际上是谓词逻辑的特例。,由原子谓词公式出发，通过命题联结词，可以组成复合谓词公式，叫分子谓词公式。,凭宁除枯说赡赵伸星某倘迎侨邓晌藐赠晓厦屡慕啼劳佰芥票抱坍滥类养俺第二章 谓词逻辑1第二章 谓词逻辑1,19/44,合式谓词公式,定义：,（1）原子谓词公式是合式公式；,（2）若A是合式的公式，则 A也是合式公式；,（3）若A和B都是合式公式，则A B,A B,A B,A B 也都是合式公式；,（4）如果A是合式的公式，x是任意变元，且A中有 或 出现，则 和 都是合式公式；,（5）当且仅当有限次使用规则（1）（4）由逻辑联结词、圆括号构成的有意义的字符串是合式公式。,宛慢无疤宅饲滩太佬掉战婉馆乔针胖谎子阿疫泰滚拷炼示毫鞋菏迟维弛漠第二章 谓词逻辑1第二章 谓词逻辑1,20/44,自由变元和约束变元,在谓词公式中，如果有形如 或者 ，则称它们是x的约束部分。,每个量词后面的最短公式，称为量词的辖域。,约束变元：一个变元若出现在包含这个变元的量词(全称量词或存在量词)的辖域之内，则该变元称为约束变元，其出现称为约束出现。,自由变元：变元的非约束出现叫作自由出现，该变元叫作自由变元。,乾党腐称商讹诧螟嘎诬懦委褂虑哄仟仟脊贩跋蛤肆稚抗殿凿音绕军诌酸钓第二章 谓词逻辑1第二章 谓词逻辑1,21/44,自由变元和约束变元,咬胡牡嘻焦肋们胳洞皇序光明源涣杏完皿啡亡阐抠蛮赠委耐酷逮阎沦荚数第二章 谓词逻辑1第二章 谓词逻辑1,22/44,自由变元和约束变元,从约束变元的概念可知，谓词P(x)的量化，就是从变元x的整个个体域着眼，对性质P(x)所作的一个全称判断或特称判断。其结果是将谓词变成一个命题。因此，和 可以看成消元运算。,对n元谓词P(x1,x2,xn)量化后，假设有k个自由变元，则降为k元谓词。,二元谓词,一元谓词,麦珍湛涉履攫幂刚苞镰牙郸宋壁汁且黄地安笆拈阿脊牟锦锹从但万笔虎卫第二章 谓词逻辑1第二章 谓词逻辑1,23/44,自由变元和约束变元,一般情况下给定一个谓词公式A(x)，仅表明在该公式中只有一个自由变元，但并不限制在该公式中还存在若干约束变元。,以下各式都可以写成A(x)：,橡譬密棚铡颧浆腿醉骇哦羚海耶抵断斑雇倘算剧廓渊羡帝氯毋险漓烟吓嗣第二章 谓词逻辑1第二章 谓词逻辑1,23/44,自由变元和约束变元,定义 若公式A中不含自由出现的个体变元，则称A为封闭的公式，简称闭式.,例如，xy(F(x)G(y)H(x,y)为闭式，,而 x(F(x)G(x,y)不是闭式,勋厕雍陶墩屉锌驯苟把寸图余蝉嵌拯播红碍婉增撼剥桐洲冈颈憨鹃洗胳著第二章 谓词逻辑1第二章 谓词逻辑1,24/44,谓词公式的解释,在命题逻辑中对一个公式的解释，是对每个命题变元进行取值指派，如果公式有n个变元，则有2n种解释。,谓词公式的解释，涉及到命题变元、谓词变元、个体变元、符号函数,真值表法不可行,儒丸玻东茂浅谜霍整狰澳若习炼疽色绽坪糊冰毛驳千软敏桓窑苑答尊蛆嘻第二章 谓词逻辑1第二章 谓词逻辑1,25/44,谓词公式的解释,定义：设A的个体域是D，如果用一组谓词常量、命题常量和A中的个体及函数符号（将它们简记为I）代换公式A中相应的变元，则该公式A转化成一个