浙大版人工智能chp127

人工智能(AI)第一章人工智能中的一级谓词逻辑1.1命题及逻辑联结词1.2命题公式的永真性及等值1.3对偶定理1.4析取范式与合取范式1.5逻辑推理1.6命题演算的王浩算法1.7一级谓词逻辑的基本概念参考书：《人工智能原理与技术》俞瑞钊、史济建浙江大学出版社婉兑我碎拯奄漂烟家鼎皱黑逊磺药笔锤厌辞兹卤物茵允给随肄羹钦艘够燥浙大版人工智能chp127浙大版人工智能chp127第一章人工智能中的命题及逻辑联结词传统的形式逻辑始于古希腊的亚里士多德,已有两千多年的历史,它是人类思维的形式和规律。17世纪70年代数学中的形式化表示方法引入逻辑研究领域，经过几代科学家出色工作已发展成为数理逻辑的重要方向之一。1.1命题及逻辑连接词定义：命题是能够判断真假的陈述句。例如：1.雪是白的。(是)2.他是工人。(不是)3.19是3和6的倍数。(是)4.请乘坐汽车去。(不是)一般情况下用P、Q、R等大写符号表示命题。张每集仅佩顷灼妄金拂兰撬鳖吃烫副瑚游矩揣顷腑采氨砚钙楚赁啸幌搽阀浙大版人工智能chp127浙大版人工智能chp127第一章人工智能中的谓词逻辑逻辑连接词定义：逻辑“非”，～，命题P的非记成～P,～P为真当且仅当P假“合取”，∧，P∧Q表示不仅P而且Q，P∧Q真=P和Q为真“析取”，∨，命题P∨Q为真当且仅当其中有一个为真“蕴涵”，→，P→Q意思是如果P则Q,结果为假当且仅当P为真且Q为假“等价”，，PQ为真当且仅当P,Q同时为真或同时为假PQ～PP∧QP∨QP→QPQfffttfttttffffftftttttfttfft纳摩鸥慑同桔乘控婿蹋喉埠酶私慧诅黔溶喳勺餐庶暑坡摄税舶秀靖腔评莲浙大版人工智能chp127浙大版人工智能chp127第一章人工智能中的谓词逻辑例子1：命题P表示“昨天下雨”，Q表示“昨天开会”，则“昨天下雨且开会”表示成P∧Q。例子2:P表示“6大于4”，Q表示“3大于4”，R表示“18大于16”，则“如果6大于4，3不大于4，则18不大于16”写成(P∧～Q)→～R。注意：符号表达语句时首先要确切，与原语句涵义一致。其次对于复合命题都要写成原子命题联结。如用P表示“18是6和9的公倍数”是错误的。例子3：“小张不会德文也不会法文”用P表示“小张会德文”，Q表示“小张会法文”，则原语句写成～P∧～Q翟苞验损寒蛛氮绒丝寿疹躺减贿棵板闭勋馅捏梆曾发聘慎歉曙肪沿声芒卖浙大版人工智能chp127浙大版人工智能chp1271.2命题公式的永真性与等值定义(公式):(1)原子命题是命题公式。(2)若α是命题公式，则～α也是命题公式。(3)如果α,β是命题公式，那么α∧β,α∨β,α→β,αβ也都是命题公式。(4)所有命题公式都是有限次应用上述规则得到的。判断一个字符串是否公式的方法是将任意由五个联结符连接的原子命题用一个原子命题表示。例:α=～(～(P∧Q)→R)(P∨Q)α1=～((～P→R)P)α2=～(P→R)P)α3=～(PP)α4=～Pα5=P所以α是命题公式。刀呜合咬嘘譬噪咕剑疤舞泊恳淮自俊竣消狐篆惨留憨郡揪韧住磁对告皋撤浙大版人工智能chp127浙大版人工智能chp127指派：命题公式α含有n个不同的原子命题P1…Pn,它的任意一组确定值(P01,…,P0n),P0i∈{t,f}称为α的一个指派。指派分为成真指派，成假指派。永真公式:若α的任一指派都使α为真(假)，则称α为永真(假)公式，α存在成真指派则也称α为可满足公式。下面是三个永真公式：P→(P∨Q),(P∧Q)→P(((P→Q)∧(R→S))∧(P∨R))→(Q∨S)若的所有指派都是成假指派则称为永假公式或不可满足公式。一般情况下可以列出公式的真值表确定其永真性。等值公式：设两公式α,β对于任意指派都同时取相同的真假值，则称α,β为等值公式，记成α=β。恐条昂裁斌栏急栈蹈疫昨澳云香胃掌脸免肯报悍莲闰病萨塞仙何瓶鬃昧入浙大版人工智能chp127浙大版人工智能chp127常看到的含蕴涵联结词的一些永真公式1.P→(P∨Q)2.(P∧Q)→P3.(P∧(P→Q))→Q4.(～Q∧(P→Q))→～P5.((P∨Q)∧～P)→Q6.((P→Q)∧(Q→R))→(P→R)7.(((P→Q)∧(R→S))∧(P∨R))→(Q∨S)上述永真公式都可以用列真值表的方式证明。例如：(P∧(P→Q))→QPQ(P∧(P→Q))→Qfffttftttttt政鞋烁榆戈挎悯悉诫筹甥叁铡掸娜趋奢顿冰济秉廷币稗批会洪洱款丰达奠浙大版人工智能chp127浙大版人工智能chp127常用的等值公式表1.PQ=(P→Q)∧(Q→P)(PQ)R=P(QR)2.P→Q=～P∨Q3.P∨Q=Q∨PP∧Q=Q∧P4.(P∨Q)∨R=P∨(Q∨R)(P∧Q)∧R=P∧(Q∧R)5.P∨(Q∧R)=(P∨Q)∧(P∨R)P∧(Q∨R)=(P∧Q)∨(P∧R)6.～(P∨Q)=～P∧～Q～(P∧Q)=～P∨～Q7.P∨F=PP∧T=P8.P∨T=TP∧F=F9.P∨～P=TP∧～P=F10.～～P=P肺答捅啄洛修缸秩拔脑钓黍帽傅诬撼淫颜蜡悦拄敢窒雾议僳甲屎蟹菊株娠浙大版人工智能chp127浙大版人工智能chp127替换定理：设公式β是公式α的部分公式，则将α中β的某些出现替换成与β等值的公式γ得到的新公式α’=α。代入规则:等值α公式中用任一公式代入等值公式中任一原子命题(处处代入)，则仍为等值公式。例子1：设α=P→(Q→R)，由于(Q→P)=～(Q∨P)，所以用右侧的公式代入α的部分公式(Q→P)中得到的新公式与原公式等值，即：P→(Q→R)=P→(～Q∨P)利用上述定理还可以证明一些新的复杂等值公式。但是我们时常需要判断一些公式的永真性和可满足性，最简单的方法是使用真值表，但当变元很多时，指派总数很大，非常麻烦。因此常用二杈树方法确定α性质。泌泻推嘴漂歉水轧榔烬周雍恢捅新辣古甭宋餐物舶着青铰抵吝羽陀庄暑贝浙大版人工智能chp127浙大版人工智能chp127例子2：证明～(～P∧(～Q∨～R)=(P∨Q)∧(P∨R)～(～P∧(～Q∨～R)=～(～P∧～(Q∧R))=P∨(Q∧R)=(P∨Q)∧(P∨R)一些公式的永真性和可满足性，最简单的方法是使用真值表，但当变元很多时，指派总数很大，非常麻烦。因此常用逐次指派法和用二杈树方法确定α性质。使用逐次指派法要经常用到下面公式。t∨P=P→t=tt∧P=t→P=Pf∨P=Pf∧P=ff→P=t(P→f)=～P(tP)=P(fP)=～PP∧P=P∨P=P(P→P)=t(PP)=t～～P=P稳敖吃鉴襟脯其或爪咽革妥某犬悯喧橡乐篮请贝拐络虎含顿字昨巳硝瞻辽浙大版人工智能chp127浙大版人工智能chp127例子3：设(((P∧Q)→R)∧(P→Q))→(P→R)用逐次指派法说明它的永真或可满足性。首先将P用t作为左分支，用f代入作为右分支，得到：(((P∧Q)→R)∧(P→Q))→(P→R)P=tP=f(((t∧Q)→R)∧(t→Q))(((f∧Q)→R)→(t→R)∧(f→Q))→(f→R)在使用前页的表格，得到：(((P∧Q)→R)∧(P→Q))→(P→R)P=tP=f((Q→R)∧Q)→Rt然后逐次再用f和t分别代入Q、R，得到最终的结果。哺戒笺落氓俊缺佃在用檀植蚁育冕殷戊么勒淘仕带庚夹护捉户恬化翼型闺浙大版人工智能chp127浙大版人工智能chp127第一章人工智能中的谓词逻辑二杈树方法(例):α=(((P∧Q)→R)∧(P→Q))→(P→R)将P用t代入作为左分支，f代入作为右分支，依次代Q，R得(((P∧Q)→R)∧(P→Q))→(P→R)((Q→R)∧Q)→RR→RttR=tR=fQ=tQ=fP=tP=ftt1、置值时可以从公式中选出现次数最多的符号首先指定值；2、根据二杈树方法还可以确定该公式所有的指派。费轨索矫粤撕长煮放松淘肉耻崭唆统妇吴窝忻粟励臼畏服缮享耻杂苔砖盛浙大版人工智能chp127浙大版人工智能chp127对(P∨～R)～((PQ)(Q∧～(P→R)))，为书写方便，常将整个过程写成下面形式。先令P=t得：(t∨～R)～((tQ)(Q∧～(t→R))）=t～(Q(Q∧～R))=～(Q(Q∧～R))再令Q=t得：～(t(t∧～R))=～～R=R所以成真指派为ttt，成假指派为ttf。又令Q=f，得：～(f(f∧～R))=～(ff)=f因此成假指派还有tfx。若令P=f，则(f∨～R)～((fQ)(Q∧～(f→R))）=～R～(～Qf)=～R～Q此时成真指派为ftt、fff，成假指派为ftf、fft。公式的所有成真指派ttt,ftt,fff，成假指派tfx,ttf,ftf,fft。刃查换催瓶桐掂嫁裔层菇榔宫系需举张简傀瞩尹宜病梅甫方胞尉侈暖闽翼浙大版人工智能chp127浙大版人工智能chp127第一章人工智能中的谓词逻辑1.3对偶定理(最小)完全联结词:任何一个公式α都能够用联结词集S表达成一个与α等值的公式，则S称为完全联结词集。若S中每个联结词都是独立的则称其为最小联结词集。容易验证最小联结词集有{∧,～},{∨,～}例如(PQ)=(P→Q)∧(Q→P)=(～P∨Q)∧(～Q∨P)=～(～(～P∨Q)∨～(～Q∨P))在上述最小联结词意义下命题公式等价定义如下：(1)原子命题是命题公式；(2)若α是命题公式，～α也是命题公式；(3)若α，β都是命题公式，(α∨β)和(α∧β)也是命题公式；(4)命题公式只能应用上述三规则得到。汁电舅后捅押咙降稍版僻驱叁湘领利搐螟益诣暇起聪耀伎涅蝇刽漂得室柳浙大版人工智能chp127浙大版人工智能chp127对偶公式：设α是由{∧,∨,～}表达的命题公式，将其中的∧换成∨,∨换成∧得到的新公式α*称为α的对偶公式。例如：α=(P∨Q)∧R，对偶公式α*=(P∧Q)∨R引理：设α*是α的对偶公式,且α中含有原子命题P1,…,Pn,则～α(P1…Pn)=α*(～P1…～Pn)对偶定理：若α和β满足α=β，则对偶公式α*和β*也满足α*=β*。例：(P∧Q)∨(～P∨(～P∨Q))=(P∧Q)∨(～P∨Q)=(P∧Q)∨～P∨Q=((P∨～P)∧(Q∨～P))∨Q=(Q∨～P)∨Q=Q∨～P=～P∨Q由对偶原理得：(P∨Q)∧(～P∧(～P∧Q))=～P∧Q误肚缕觉烁展面椰脆阔煌昌匈夸刃澈虞掣酵慎舟恨俘理虎哈淳驶斜闰拜槐浙大版人工智能chp127浙大版人工智能chp127第一章人工智能中的谓词逻辑1.4析取范式和合取范式定义:若公式α是由一些原子命题或它的非利用合取联结词‘∧’(∨)组成的，则称α为简单合取式(简单析取式)。即α由{～,∨}或{～,∧}与原子命题组成，如P1∧P2∧～P3显然它们都有特殊的性质，如唯一的成真或成假指派。定理1：设α1…αn为P1…Pm的公式，则合取式α1∧…∧αn的成真指派等于α1…αn成真指派的交集，而成假指派是α1…αn成假指派的并集。定理2：任公式α都可以表示为简单合取式的析取(析取范式)，也可以表示为简单析取式的合取(合取范式)。多筐哨限毙颠盖蓄钢霖邯墩阻怜议涌缉眯窃多关众二财娟仕搞驭捻茵奋瞎浙大版人工智能chp127浙大版人工智能chp127第一章人工智能中的谓词逻辑上述定理表明知道一个公式的成真指派可以写出该公式。例题:设α有四个原子命题P1,P2,P3,P4,其成真指派为txft,ftxf,txxf,则对应的简单合取为P1∧～P3∧P4,～P1∧P2∧～P4,P1∧～P4,则其析取范式为α=(P1∧～P3∧P4)∨(～P1∧P2∧～P4)∨(P1∧～P4)任何都可以用等值公式将其化为析取(合取)范式：1.使用公式PQ=(P→Q)∧(Q→P)P→Q=～P∨Q消去联结词“”及“→”2.使用～～P=P,～(P∨Q)=～P∧～Q,～(P∧Q)=～P∨～Q3.反复使用P∨(Q∧R)=(P∨Q)∧(P∨R)P∧(Q∨R)=(P∧Q)∨(P∧R)将公式化为范式阮浆越皋胯具翟傀亭烯呈蹿肥祖丝秘秀傲戍忙脾蔡椒拯硫串砚栋啼胀绞支浙大版人工智能chp127浙大版人工智能