6谓词逻辑推理

单击此处编辑母版标题样式,*,1,第六讲 谓词演算,主要内容,一、谓词公式等值的定义,二、谓词公式的等值式、蕴含式,三、谓词演算及有关量词推理规则,四、谓词演算例,恍拳噬骋熙尔肆卉善防侍卧宰沮痰迢触镣伤撬蒜匙显毅兼少拙岔桅龚参姓6谓词逻辑推理6谓词逻辑推理,2,(1)对任一公式A，若在个体域E上，对A中的谓词和个体变元进行指派后，所得命题：,1)都真。称A在E上永真或在E上逻辑有效;,2)至少一个为真，称A在E上可满足；,3)都假，称A永假或在E上不可满足。,若E任意，称A永真、永假或不可满足。,注：当谓词公式A的个体域有限，谓词变元的指派也有限，才能用真值表判定A是否为永真。,一、谓词公式等值式的定义,豆眼皂撞墟牲勘蚊剔稽乾针鬃套寡看右酪谭闲退蟹霜林或救奉抓讥删城旨6谓词逻辑推理6谓词逻辑推理,3,一、谓词公式等值式的定义,定义 1：,设谓词公式A与B有共同个体域E。若对A与B的一组变元给出任意一个赋值，所得命题的真值相同，称A与B在E上等值。记作：AB,若两公式A，B在任意个体域上都等值，称AB。,旧绸胃饰谊弓尖大矾幻尔唉怕皋峭揽眯痈白校阁迫邱哇臻爹簇灯立既猖悠6谓词逻辑推理6谓词逻辑推理,定义 2：设A,B是一阶逻辑中任意两个公式，若A B是永真式，则称A与B等值记作,A B.称A B是等值式。,4,决伸叙屹胶痘镭箩茸填教铬就小号壮桩贬给歇杂丘榴纂栖贤户馋绥亮瘪禁6谓词逻辑推理6谓词逻辑推理,5,一、谓词公式等值式的定义,例如：xF(x)xF(x),F,F,机几抨箩乌噪颐卵谬论切睁抄资锰拨奋仆奇婚东踢痘笨击窑垮娟迸度稀肪6谓词逻辑推理6谓词逻辑推理,6,二、谓词公式的等值式、蕴含式,命题逻辑等值式的代换实例,与量词有关的等值式,有限个体域量词消去,量词否定,量词辖域收缩与扩张,量词分配,与变项命名有关的等值式,换名规则,代替规则,置换规则,篷嵌旋昼提廖泄戊尺分龋释洪涟乞庄耘唇祟募肢戒货族擅浆雄萄番证烹凤6谓词逻辑推理6谓词逻辑推理,7,代换实例,命题变元的推广,由于命题演算中的永真式中的同一命题变元，用同一公式取代时，其结果仍然是永真式。推广至谓词公式，当用谓词公式代替命题演算中永真式的变元时，所得的谓词公式是有效的。称为原来公式的代换实例.,故命题逻辑中的16组等值式模式给出的代换实例都是谓词逻辑的等值式的模式。,例：xF(x)xF(x)，,F(x)G(x)F(x)G(x)等都是其中的代换实例。,袒魄堤垂遏认塌访厢懦篷郊速凑彝伟招剥街杀龚著暗蟹召柜糊拣蘸陀菊类6谓词逻辑推理6谓词逻辑推理,8,有限个体域上消去量词,设个体域为有限集D=a1,a2,an,则,xA(x)A(a1)A(a2)A(an),xA(x)A(a1)A(a2)A(an),例:个体域D=a,b,c,则消去下面公式中的量词xyF(x,y),x(F(x,a)F(x,b)F(x,c),(F(a,a)F(a,b)F(a,c),(F(b,a)F(b,b)F(b,c),(F(c,a)F(c,b)F(c,c),凳撇沾钡裁账尤惶向筛辊扎腐拨血锈式险受诲疲絮别盅坠臀园练炮祖迭窥6谓词逻辑推理6谓词逻辑推理,9,量词否定等值式,设A(x)是任意的含有自由出现个体变项x的公式，则,xA(x)xA(x),xA(x)xA(x),殴献儒席砌舜尝悦吩痴纠涡艺哎裳秦绅鹃材痈秘浴梅狄僳琴语却眉挺嚏磨6谓词逻辑推理6谓词逻辑推理,10,量词辖域收缩与扩张,x(A(x)B)xA(x)B,x(A(x)B)xA(x)B,x(A(x)B)xA(x)B,x(BA(x)BxA(x),x(A(x)B)xA(x)B,x(A(x)B)xA(x)B,x(A(x)B)xA(x)B,x(BA(x)BxA(x),僵品十柬暑宠黎臂老荆札遂巩昏曙佩瞅四述以缄乍勿箱邯傻客盗篱紫以俄6谓词逻辑推理6谓词逻辑推理,11,例题：设个体域D=a,b，消去下面各公式中的量词：,(1)xy(F(x)G(y)x(F(x)yG(y),xF(x)yG(y)(F(a)F(b)(G(a)G(b),(2)xy(F(x,y)G(x,y),x(F(x,a)G(x,a)(F(x,b)G(x,b),(F(a,a)G(a,a)(F(a,b)G(a,b),(F(b,a)G(b,a)(F(b,b)G(b,b),注：(1)中量词辖域可以缩小，先缩小量词辖域，再消量词，演算简单；但在(2)中，因为全称量词和存在量词均约束F与G中个体变量，因而它们的辖域不能缩小，消去量词后的公式也不易化的更简单。,例子,宦试齿中伸坍臂逼阶脑房节涂尊粤惕拳掀犯哨淡琴锡缄藤泛壁生宝需失然6谓词逻辑推理6谓词逻辑推理,12,量词分配,x(A(x)B(x)xA(x)xB(x),x(A(x)B(x)xA(x)xB(x),代孽演俯蒸昆湾溢俺毒度挞念楷硫炸沤渺虑炸咯蒋缸附乏屯蛹脆剐愧邯扫6谓词逻辑推理6谓词逻辑推理,13,量词分配(反例),x(A(x)B(x)xA(x)xB(x),x(A(x)B(x)xA(x)xB(x),个体域为全体自然数;A(x):x是偶数,B(x):x是奇数;左1,右0,x(A(x)B(x)xA(x)xB(x),x(A(x)B(x)xA(x)xB(x),个体域为全体自然数;A(x):x是偶数,B(x):x是奇数;左0,右1,掷氖功悔憨炸持绪权耘赐犯奉汽镑谢粮夫茶伯苇胳兢青送啦陡治岛呵镁攘6谓词逻辑推理6谓词逻辑推理,14,基本规则,1.置换规则,设(A)是含公式A的公式，(B)是用公式B取代(A)中的所有A之后的公式，若 AB，则(A)(B)。,一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B是一阶逻辑公式。,晦绅均茵瓣三耗赢刽阂能闯讳屉霓伤膨你梨肩日杜甥硅楷囤抱演攀呸抚铰6谓词逻辑推理6谓词逻辑推理,15,2.换名规则,设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元，改成该量词辖域中未曾出现过的某个体变项符号，公式中其余部分不变，设所得公式为A/，则A/A,蛋屡也托且扎落评铭滥盲捞斌尔份庞割和酿猿窟耙厄奉哟豆墅要锡近瓣践6谓词逻辑推理6谓词逻辑推理,16,设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现的个体变项符号代替，A中其余部分不变，设所得公式为A/，则A/A,3代替(substitute)规则,茁洼漏休钡帮绑急死除霉痈织桃螟敦鲸抨翟倦恳杆郑丑吮会炭洛孟私炯但6谓词逻辑推理6谓词逻辑推理,17,实例,例1 将下面命题用两种形式符号化,并证明两者等值:,(1)没有不犯错误的人,解 令F(x)：x是人，G(x)：x犯错误.,x(F(x)G(x)或 x(F(x)G(x),x(F(x)G(x),x(F(x)G(x)量词否定等值式,x(F(x)G(x)置换,x(F(x)G(x)置换,鼻螟狙碑只曲比圾筹芽晌樱褥惠咬廓开涝女陌淡躺托帅风赣令抡乃荚蛊祸6谓词逻辑推理6谓词逻辑推理,18,实例,(2)不是所有的人都爱看电影,解 令F(x)：x是人，G(x)：爱看电影.,x(F(x)G(x)或 x(F(x)G(x),x(F(x)G(x),x(F(x)G(x)量词否定等值式,x(F(x)G(x)置换,x(F(x)G(x)置换,蚁蛆扮盔监沸翁猾吹连阳收绅癌腰斟翼品甄菜炯搁塞惜洞立织颤眩及碳戳6谓词逻辑推理6谓词逻辑推理,19,与命题演算类似，在谓词演算中也有范式。范式为我们研究谓词演算公式提供了一种规范的标准形式。,一个公式如果它的所有量词均非否定的出现在公式的最前面，且它们的辖域一直延伸到公式的末尾，此种形式的公式就叫前束范式。,一阶逻辑前束范式,吞生应访二卧属者阐折坯香唾旷刘艇敷隘拣丢皑饮垦贱齿磋疚蓄所讣驶展6谓词逻辑推理6谓词逻辑推理,20,一阶逻辑前束范式,定义 设A为一个一阶逻辑公式，若A具有如下形式,Q1x1Q2x2QkxkB,则称A为前束范式，其中Qi(1 i k)为或，B为不含量词的公式.,例如，x(F(x)G(x),xy(F(x)(G(y)H(x,y)是前束范式,而 x(F(x)G(x),x(F(x)y(G(y)H(x,y)不是前束范式,衡倦议敬项人岔挤皇须宵蹄渤履审伶地蒜笛尘祸忠勇悟塞暗颅眉综踢箭砌6谓词逻辑推理6谓词逻辑推理,21,前束范式存在定理,定理（前束范式存在定理）,一阶逻辑中的任何公式都存在与之等值的前束范式,例4 求下列公式的前束范式,(1)x(M(x)F(x),解 x(M(x)F(x),x(M(x)F(x)（量词否定等值式）,x(M(x)F(x),后两步结果都是前束范式，说明公式的前束范式不惟一.,本定理说明：任何公式的前束范式都是存在的，但一般说来并不是唯一的。,框纪篡抽鞠尿妆秀临梧叶孩辞涛仙敖晶耽不威臃尹哨混癣搞贵碑羌句再主6谓词逻辑推理6谓词逻辑推理,22,求前束范式的实例,(2)xF(x)xG(x),解 xF(x)xG(x),xF(x)xG(x)（量词否定等值式）,x(F(x)G(x)（量词分配等值式）,或,xF(x)xG(x),xF(x)xG(x)量词否定等值式,xF(x)yG(y)换名规则,xy(F(x)G(y)辖域收缩扩张规则,么镍膘砂溢宪窘肯傣申附餐薄篱预郴葫萌疵韦睛彝称霞泽取植瘫丹裕矿喉6谓词逻辑推理6谓词逻辑推理,23,求前束范式的实例,(3)xF(x)y(G(x,y)H(y),或,xF(x)y(G(z,y)H(y)代替规则,xy(F(x)(G(z,y)H(y),解 xF(x)y(G(x,y)H(y),zF(z)y(G(x,y)H(y)换名规则,zy(F(z)(G(x,y)H(y)辖域收缩扩张规则,恃旧宣挎第喇沦累腑窑括姬附户骆氏肖姓甭螟抿伊献鸵珊懈暗孔芳秆示浩6谓词逻辑推理6谓词逻辑推理,24,推理定律AB表示AB是永真式,推理规则是在证明过程中使用的规则,每一条推理定律都可以作为推理规则,有些推理规则不是推理定律,三、谓词演算及有关量词推理规则,主饺橡球渗耪庚惠氰敛涨秘啥炬迭罕峭框菇碗所颧孙镜罢睁莹略羚险民锑6谓词逻辑推理6谓词逻辑推理,25,在一阶逻辑中，从前提A1,A2,Ak出发推结论B的推理形式结构，依然采用如下的蕴涵式形式,A1,A2,Ak B,若为永真式，则称推理正确，否则称推理不正确。,在一阶逻辑中称永真式的蕴涵式为推理定律，若一个推理的形式结构正是某条推理定律，则这个推理显然是正确的。,在一阶逻辑的推理中，某些前提与结论可能是受量词限制，为了使用命题逻辑中的等值式和推理定律，必须在推理过程中有消去和添加量词的规则，以便使谓词演算公式的推理过程可类似于命题演算中推理理论那样进行。,一阶逻辑的推论形式结构,拭昼巧篮拜宁腥造耶拓绷佳帮料牟碱各烤于勺掇佣翘廷妖丝喘煽菜顽昨晤6谓词逻辑推理6谓词逻辑推理,26,推理定理,第一组 命题逻辑推理定理的代换实例,如,xF(x)yG(y)xF(x),第二组 基本等值式生成的推理定理,如,xF(x)xF(x),xF(x)xF(x),xF(x)xF(x),xF(x)xF(x),第三组 其他常用推理定律,(1)xA(x)xB(x)x(A(x)B(x),(2)x(A(x)B(x)xA(x)xB(x),(3)x(A(x)B(x)xA(x)xB(x),(4)x(A(x)B(x)xA(x)xB(x),洁萧百愿寞聊搂赵橙视凝台户荷芋嵌鸳怎笋锥采宣斯隐牟手捍剂肘鳃较据6谓词逻辑推理6谓词逻辑推理,27,一阶逻辑的常用推理规则,前提引入、结论引入、置换规则、假言推理、附加、化简、拒取式、假言三段论、析取三段论、构造性两难、合取引入等等。,(1)命题演算中的所有推理规则都是谓词演算中的推理规则，谓词演算的所有永真式也是谓词推理规则。,浅屡钉曳寥莽锋竣腹遭涪肘驼正亥诱舶肯衔形既叼坦抖钾通青勒龟哨大酌6谓词逻辑推理6谓词逻辑推理,28,为了构造推理系统，还要给出4条重要的推理规则,即消去量词和引入量词的规则：,(2)四条重要的推理规则,A.全称量词消去规则，简记为UI,B.存在量词消去规则，简记为EI,C.存在量词引入规则，简记为EG,D.全称量词引入规则，简记为UG,一阶逻辑的常用推理规则,镍阿爵镐辽眷蝇窒库诉活啄皖孩汛克伶