浙大版人工智能

人工智能(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∧～Q第四页，共二十八页。1.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及β均为命题公式，则α1…αn|=β当且仅当α1∧…∧αn∧～β

是永假的。证明：由上知β是逻辑结果当且仅当(α1∧…∧αn)→β是永真的，因此～((α1∧…∧αn)→β)是永假的，而～((α1∧…∧αn)→β)=～(～(α1∧…∧αn)∨β)=α1∧…∧αn∧～β

因此定理得证。第二十一页，共二十八页。总结为什么建立命题、谓词逻辑

基本思路：一个实际问题，有使用的定理和条件条件，有要证明的结论。首先将所有条件和结论转换成命题公式集合α1…αn及命题公式β。显然问题是，如果所有条件成立(α1…αn为真)，证明结论成立(β为真)，即按照定义β称为α1…αn的逻辑推论(逻辑结果)，记成：α1…αn|=β。

按照定理1，就是证明(α1∧…∧αn)→β

是永真的。

按照定理2，就是证明α1∧…∧αn∧～β

是永假的。但是要证明上述公式的永假性也是非常困难的，所以必须建立一套更为复杂的理论解决求证的问题。因此，下面建立了王浩演算体系和谓词逻辑的归结原理，他们都是用来证明α1∧…∧αn∧～β的永假性的。第二十二页，共二十八页。实际问题命题转换α1…αn|=β就是证明(α1∧…∧αn)→β

是永真的(定理1)就是证明α1∧…∧αn∧～β

是永假的(定理2)建立证明的理论体系王浩演算体系谓词逻辑归结原理第二十三页，共二十八页。第一章人工智能中的谓词逻辑1.6一级谓词逻辑的基本概念1.6.1谓词:谓词是指个体所具有的性质或若干个体之间的关系，如“数理逻辑是科学”分为两部分，主语“数理逻辑”与谓表语“是科学”。“3整除6”，表现3和6间的整除关系。其中“数理逻辑”、“3”、“6”也可以是抽象的x,y等称为个体变元。“是科学”、“整除”是谓词。一般用A、B、C等表示谓词，如x,y间的关系写成B(x,y),谓词中有n个体变元则称为n元谓词，0元谓词就是命题，记为P、Q、R等。为方便常用一些符号直接表示谓词，如“等于”直接用“=”表示，这样E(x,y)写成“x=y”。单独的谓词没有意义，必须赋予个体，通常把谓词填以个体后的式子称为谓词填式。如“张山高于李四，则张山高于王五”，用A表示“高于”，a,b,c分别表示“张山”、“李四”、“王五”，则上述谓词填式表示为A(a,b)→A(a,c)第二十四页，共二十八页。第一章人工智能中的谓词逻辑1.6.2量词:量词有全称量词和存在量词，分别记为“

x”和“ヨx”,意思为“对于所有的x”和“存在一个x”。当写xP(x)和ヨxQ(x,y)时称其为量词的作用域，x称为约束变元，y称为自由变元。变元的取值范围称为个体域。例：“任何整数是正的或负的”，用M(x)表x是整数，P(x)表x是正数，N(x)表x是负数，则整个语句表示为

x(M(x)→(P(x)∨N(x)))而如果事先约定个体域是全体整数，则可以表示为

x(P(x)∨N(x))注意在受量词约束的变元中，变元用什么记号