浙大版人工智能chp127

人工智能(AI)第一章人工智能中的一级谓词逻辑1.1命题及逻辑联结词1.2命题公式的永真性及等值1.3对偶定理1.4析取范式与合取范式1.5逻辑推理1.6命题演算的王浩算法1.7一级谓词逻辑的基本概念参考书：《人工智能原理与技术》俞瑞钊、史济建浙江大学出版社第一章人工智能中的命题及逻辑联结词传统的形式逻辑始于古希腊的亚里士多德,已有两千多年的历史,它是人类思维的形式和规律。17世纪70年代数学中的形式化表示方法引入逻辑研究领域，经过几代科学家出色工作已发展成为数理逻辑的重要方向之一。1.1命题及逻辑连接词定义：命题是能够判断真假的陈述句。例如：1.雪是白的。(是)2.他是工人。(不是)3.19是3和6的倍数。(是)4.请乘坐汽车去。(不是)一般情况下用P、Q、R等大写符号表示命题。第一章人工智能中的谓词逻辑逻辑连接词定义：逻辑“非”，～，命题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第一章人工智能中的谓词逻辑例子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∧～Q1.2命题公式的永真性与等值定义(公式):(1)原子命题是命题公式。(2)若α是命题公式，则～α也是命题公式。(3)如果α,β是命题公式，那么α∧β,α∨β,α→β,αβ也都是命题公式。(4)所有命题公式都是有限次应用上述规则得到的。判断一个字符串是否公式的方法是将任意由五个联结符连接的原子命题用一个原子命题表示。例:α=～(～(P∧Q)→R)(P∨Q)α1=～((～P→R)P)α2=～(P→R)P)α3=～(PP)α4=～Pα5=P所以α是命题公式。指派：命题公式α含有n个不同的原子命题P1…Pn,它的任意一组确定值(P01,…,P0n),P0i∈{t,f}称为α的一个指派。指派分为成真指派，成假指派。永真公式:若α的任一指派都使α为真(假)，则称α为永真(假)公式，α存在成真指派则也称α为可满足公式。下面是三个永真公式：P→(P∨Q),(P∧Q)→P(((P→Q)∧(R→S))∧(P∨R))→(Q∨S)若的所有指派都是成假指派则称为永假公式或不可满足公式。一般情况下可以列出公式的真值表确定其永真性。等值公式：设两公式α,β对于任意指派都同时取相同的真假值，则称α,β为等值公式，记成α=β。常看到的含蕴涵联结词的一些永真公式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常用的等值公式表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替换定理：设公式β是公式α的部分公式，则将α中β的某些出现替换成与β等值的公式γ得到的新公式α’=α。代入规则:等值α公式中用任一公式代入等值公式中任一原子命题(处处代入)，则仍为等值公式。例子1：设α=P→(Q→R)，由于(Q→P)=～(Q∨P)，所以用右侧的公式代入α的部分公式(Q→P)中得到的新公式与原公式等值，即：P→(Q→R)=P→(～Q∨P)利用上述定理还可以证明一些新的复杂等值公式。但是我们时常需要判断一些公式的永真性和可满足性，最简单的方法是使用真值表，但当变元很多时，指派总数很大，非常麻烦。因此常用二杈树方法确定α性质。例子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例子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，得到最终的结果。第一章人工智能中的谓词逻辑二杈树方法(例):α=(((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、根据二杈树方法还可以确定该公式所有的指派。对(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。第一章人工智能中的谓词逻辑1.3对偶定理(最小)完全联结词:任何一个公式α都能够用联结词集S表达成一个与α等值的公式，则S称为完全联结词集。若S中每个联结词都是独立的则称其为最小联结词集。容易验证最小联结词集有{∧,～},{∨,～}例如(PQ)=(P→Q)∧(Q→P)=(～P∨Q)∧(～Q∨P)=～(～(～P∨Q)∨～(～Q∨P))在上述最小联结词意义下命题公式等价定义如下：(1)原子命题是命题公式；(2)若α是命题公式，～α也是命题公式；(3)若α，β都是命题公式，(α∨β)和(α∧β)也是命题公式；(4)命题公式只能应用上述三规则得到。对偶公式：设α是由{∧,∨,～}表达的命题公式，将其中的∧换成∨,∨换成∧得到的新公式α*称为α的对偶公式。例如：α=(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第一章人工智能中的谓词逻辑1.4析取范式和合取范式定义:若公式α是由一些原子命题或它的非利用合取联结词‘∧’(∨)组成的，则称α为简单合取式(简单析取式)。即α由{～,∨}或{～,∧}与原子命题组成，如P1∧P2∧～P3显然它们都有特殊的性质，如唯一的成真或成假指派。定理1：设α1…αn为P1…Pm的公式，则合取式α1∧…∧αn的成真指派等于α1…αn成真指派的交集，而成假指派是α1…αn成假指派的并集。定理2：任公式α都可以表示为简单合取式的析取(析取范式)，也可以表示为简单析取式的合取(合取范式)。第一章人工智能中的谓词逻辑上述定理表明知道一个公式的成真指派可以写出该公式。例题:设α有四个原子命题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)将公式化为范式第一章人工智能中的谓词逻辑例题1:将(P∧(Q→R))→S化为合取范式(P∧(Q→R))→S=(P∧(～Q∨R))→S=～(P∧(～Q∨R))∨S=(～P∨～(～Q∨R))∨S=(～P∨(Q∧～R))∨S=((～P∨Q)∧(～P∨～R))∨S=(～P∨Q∨S)∧(～P∨～R∨S)例题2:将～P(Q∧～R)化为析取范式～P(Q∧～R)=(～P→(Q∧～R))∧((Q∧～R)→～P)=(P∨(Q∧～R))∧((～Q∨R)∨～P)=((P∨(Q∧～R))∧(～Q∨R))∨((P∨(Q∧～R))∧～P)=((P∧(～Q∨R))∨((Q∧～R)∧(～Q∨R))∨((Q∧～R)∧～P)=(P∧～Q)∨(P∧R)∨(Q∧～R∧～Q)∨(Q∧～R∧R)∨(Q∧～R∧～P)=(P∧～Q)(P∧R)(～P∧Q∧～R)第一章人工智能中的谓词逻辑1.5逻辑推理例题1:如果天气干旱则粮食歉收,又设当粮食歉收时大多数人是不幸的，再设天气干旱，那么可以指出大多数人是不幸的。设相应的陈述表示为：P表天气干旱，S表粮食丰收，U表大多数人是幸运的。例子中有四个陈述句：1.如果天气干旱，则粮食歉收；2.如果粮食歉收，则大多数人是不幸的；3.天气是干旱的；4.大多数人是不幸的。将其符号化：P→～S,～S→～U,P,～U。其实我们求证的任务是当上述表示均为真时，～U为真。第一章人工智能中的谓词逻辑将上述式子的合取化为范式：(P→～S)∧(～S→～U)∧P=P∧(～P∨～S)∧(S∨～U)=…=P∧～S∧～U如果(P→～S)∧(～S→～U)∧P为真，那么P∧～S∧～U为真，进而必须P、～S、～U均为真，所以得U为假，此时逻辑上称～U是(P→～S)、(～S→～U)和P的逻辑结果。上述推理过程的大致思想如下：1.将所有定理、条件命题和结果命题符号化，并将条件命题组成合取公式α；2.将结果命题与上述条件公式α合取成公式β；3.化β为简单合取式，令其为真，推出其中的结果命题为真。第一章人工智能中的谓词逻辑定义:设命题公式序列α1…αn及命题公式β，如果对任何使α1…αn成真的指派也使β成真，则β称为α1…αn的逻辑推论(逻辑结果)，记成：α1…αn|=β。定理1：设α1…αn及β均为命题公式，则α1…αn|=β当且仅当(α1∧…∧αn)→β是永真的。定理2：设α1…αn及β均为