人工智能7课题

第三局部学问和推理

命题规律

谓词规律

学问表示方法第七章规律智能体7.1基于学问的智能体7.2wumpus世界7.3规律7.4命题规律7.5命题规律的推理模式7.6基于命题规律的智能体基于学问的智能体学问库(Knowledgebase，KB)：语句的集合TELL：将新语句添加到学问库，告知学问库感知的信息记录选择的行动ASK：查询学问库，以获得应当执行的行动Wumpus世界性能度量：金子+1000，死亡-1000每次行动-1，用掉箭-10环境：4*4网格，金子、陷阱、wumpus传感器：Stench,Breeze,Glitter,Bump,Scream执行器：向前移动，左、右转90度，Grab，shoot，局部可观看、确定性的、连续式的、静态的、离散的、单智能体环境。[None,None,None,None,None][None,Breeze,None,None,None][Stench,None,None,None,None][None,None,None,None,None][Stench,Breeze,Glitter,None,None]规律规律的历史Aristotle：规律学Leibnitz：数理规律Gottlobfrege:一阶谓词演算系统，《符号论》(19世纪)20世纪30年月，数理规律广泛进展规律系统一个规律系统是定义语言和它的含义的方法。规律符号集合：在全部该规律的规律理论中均消失的符号非规律符号集合：不同的规律理论中消失的不同的符号语句规章：定义什么样的符号串是有意义的语义规章：定义符号串的语义推理规章、公理和证明规律和程序语言的比照逻辑系统程序语言逻辑符号保留字或符号非逻辑符号用户自定义的符号(变量名，函数名等)语句规则构造一个程序的语句规则语义规则定义程序做什么的规则推理规则、公理和证明无语义x+2≥y在x=7,y=1的世界中为真x+2≥y在x=0,y=6的世界中为假可能世界—模型m是α的一个模型，表示语句α在模型m中为真规律推理--蕴含关系〔entailment〕α╞β，当且仅当在α为真的模型中，β也为真〔当α为真，β必定为真〕 即β的真值包含于α的真值中例如：x+y=4蕴含4=x+yKB╞α一个语句规律上跟随另一个语句而消失模型检验3个方格中的每个可能包含或不包含陷阱，则存在8个可能的模型与智能体所知内容相冲突的模型中，KB为假。α1：[1,2]无陷阱，α2：[2,2]无陷阱模型检验依据[1,1]无微风，则在任意[1,2]有陷阱的模型中，KB为假仅3个模型使得KB为真。α1：[1,2]无陷阱KB╞α1模型检验KB╞α2α2：[2,2]无陷阱模型检验模型检验:枚举出全部可能的模型用于检验在KB中为真的全部模型中α为真。推理的牢靠性和完备性KB├iα：α通过推理算法i从KB中导出，推理算法i从KB中导出α推理算法i是牢靠的：假设KB├iα，则KB╞α推理算法i是完备的：假设KB╞α，则KB├iα命题规律命题：能够区分真假的陈述句。 例如：1+1=2雪是绿色的昆明是云南的省会快点走吧!到哪去？一个原子命题可以用字母表示(命题符号)。命题规律是由命题符号和规律连接符组成。原子命题：一个命题，且是不能再进一步分解成更简洁语句。是命题的根本单位。规律连接符合取式：p与q，记为p∧q析取式：p或q，记为pq蕴含式：假设p则q，记为pq等价式：p当且仅当q，记为pq否认式：非，p优先级：，∧，，，命题表示将陈述句转化为命题公式：例如：设“下雨”为p，“骑车上班”为q1.“只要不下雨，我就骑自行车上班”。p是q的充分条件，可得命题公式：p

q2.“只有不下雨，我才骑自行车上班”。p是q的必要条件，可得命题公式：q

p3.“应届毕业生，得过国家级竞赛一等奖或全班排名第一，保送争论生”设：p“应届毕业生”，q“保送争论生”，r“得过国家级竞赛一等奖”，t“全班排名第一”则有命题公式：p∧〔rt〕qTrue永真命题，False永假命题析取范式：仅由有限个简洁合取式组成的析取式p〔pq〕〔pq〕合取范式：仅由有限个简洁析取式组成的合取式p〔pq〕〔pq〕语义例如：某模型下，P1,2 P2,2 P3,1

假 真

假语义定义了用于判定关于特定模型的语句真值的规章规律连接符的真值表：指定了复合句在其组成局部的真值的每种可能赋值状况下的真值。

P1,2

(P2,2

P3,1)=true

(true

false)=true

true=trueWumpus世界的学问库Pi,j

：在[i,j]有陷阱Bi,j

：在[i,j]有微风

P1,1

B1,1B2,1陷阱使得其邻域方格有微风B1,1

(P1,2

P2,1)B2,1

(P1,1

P2,2

P3,1)推理的根本概念推理：从事实动身，运用已把握的学问，推导出其中蕴含的事实性结论或归纳出某些新的结论的过程。推理所用的事实：初始证据；中间结论。初始证据推理机结论学问库目标是推断某些语句x，kB|=x是否成立。模型检验：枚举出模型，验证x在KB为真的每个模型中为真推理真值表α1：

P1,2α2：

P2,2真值表枚举算法真值表枚举算法，是牢靠的、完备的n个符号，存在2n个模型，时间简单度O(2n)用于命题规律的有效模型检验推理算法包括回溯(DPLL算法)和局部搜寻方法〔WALKSAT算法〕。推理方法演绎推理：从的一般性学问动身，推理出适合于某些个别状况的结论的过程。归纳推理：从大量的特殊事例动身，归纳出一般性结论的推理过程。默认推理：在学问不完全的状况下假设某些条件已经具备所进展的推理。推理的不确定性及其单调性确定性推理：推理所用的证据、学问及结论都是可以准确表示的，其真值不为真就为假，不会有第三种状况消失。不确定性推理：推理所用的证据、学问及结论都是不确定的，都是不行以准确表示的，其真值位于真和假之间。单调性推理：由于新学问的参加和使用，使推理所得到的结论会越来越接近目标。非单调性推理：推理过程中某些新学问的参加和使用，不但没有加强已经推出的结论，反而会否认原来已推出的结论。交换律：p∧q≡q∧pp∨q≡q∨p结合律：(p∨q)∨r≡p∨(q∨r)(p∧q)∧r≡p∧(q∧r)安排率：p∨(q∧r)≡(p∨q)∧(p∨r)p∧(q∨r)≡(p∧q)∨(p∧r)根本等值式：α≡ß

，当且仅当α╞β

且β╞α摩根律：(p∧q)≡p∨q(p∨q)≡p∧q吸取律：p∨(p∧q)≡pp∧(p∨q)≡p同一律：p∨0≡pp∧1≡p蕴含等值式：pq≡p∨q〔蕴含消去〕假言易位式：pq≡qp〔逆否命题〕双向蕴含消去：pq≡(pq)∧(qp)根本等值式：合法性和可满足性例如：True，AA, AA, (A(AB))B假设α至少有一个成真赋值，则称α为可满足的e.g.,AB, C假设α无成真赋值，则称α为不行满足的，称冲突式或永假式，例如：AA假设语句α无成假赋值，则称α是合法的，称重言式或永真式，α是合法的，当且仅当α是不行满足的α是可满足的，当且仅当α是不合法的反证法〔归谬〕：KB╞α当且仅当(KBα)是不行满足的推理规章规律等价分别规章：αβ,αβ例如，〔WumpusAheadWumpusAlive)shoot和〔WumpusAheadWumpusAlive)，可推导出shoot与消去〔合取式推导出任何合取子句〕：αβα例如：WumpusAheadWumpusAlive可推导出WumpusAlive推理规章的应用序列--证明1.双向蕴含消去：αβ代换为(αβ)(βα).由语句(4)得：(B1,1(P1,2P2,1))((P1,2P2,1)B1,1)--(6)

2.语句〔6〕与消去：((P1,2P2,1)B1,1)--(7)语句(7)再依据αβ≡βα〔逆否命题〕得：(B1,1((P1,2P2,1))--〔8〕3.由语句〔8〕和〔2〕依据分别规章得：((P1,2P2,1))--(9)

4.依据摩根律：P1,2P2,1---〔10〕〔1〕P1,1〔2〕B1,1〔3〕B2,1〔4〕B1,1(P1,2P2,1)〔5〕B2,1(P1,1P2,2P3,1)归结AB反证法：证明AB是冲突式〔永假式〕建立子句集合取范式：命题、命题或的与例如：p〔pq〕〔pq〕子句集S：合取范式形式下得子命题〔元素〕的集合例如：上述命题公式的子句集S={p,pq,pq}合取范式B1,1(P1,2P2,1)1.消去：αβ替换为(αβ)(βα).(B1,1(P1,2P2,1))((P1,2P2,1)B1,1)2.消去：αβ替换为αβ.(B1,1P1,2P2,1)((P1,2P2,1)B1,1)3.依据摩根律移入：(B1,1P1,2P2,1)((P1,2P2,1)B1,1)4.依据安排率:(B1,1P1,2P2,1)(P1,2B1,1)(P2,1B1,1)单元归结规章l1…lk, ml1…li-1li+1…lk其中liandm是互补文字(一个文字是另一个文字的否认式).全归结规章l1…lk, m1…mnl1…li-1li+1…lkm1…mj-1mj+1...mn其中li和mj是互补文字归结规章：P1,3P2,2, P2,2P1,3归并：〔AB〕和〔AB〕归结得到AA，最终简化为Ali

真，則mj

假

(m1

…

mj-1

mj+1

...

mn)真li

假，l1

…

li-1

li+1

…

lk真归结规章的完备性：任何完备的搜寻算法，只使用归结规章，就可以生成命题规律中被任何学问库蕴涵的任何结论。l1

…

lk, m1

…

mnl1

…

li-1

li+1

…

lk

m1

…

mj-1

mj+1

...

mn

归结规章的牢靠性：A为真，无法用归结自动生成结论AB，但可以用归结推断AB是否为真。将命题写成合取范式求出子句集S对子句集使用归结推理规章归结式作为新子句参与归结归结式为空子句，S是不行满足的〔冲突〕，原命题成立归结过程例如：证明公式〔pq〕〔qp〕证：将待证明公式转化为归结命题公式：〔pq〕(qp)将该公式转化为合取范式pq≡p∨q(qp)≡(q∨p)≡qp〔pq〕(qp)≡(p∨q)qp则子句集：p∨q，q，p对子句集中的子句进展归结：〔1〕p∨q〔2〕q〔3〕p〔4〕q〔1,3归结〕〔5〕空〔2,4归结〕KB=(B1,1

(P1,2

P2,1))

B1,1α=

P1,2Wumpus世界的归结推理(B1,1

(P1,2

P2,1))

B1,1

P1,2

≡(

B1,1

P1,2

P2,1)

(

P1,2

B1,1)

(

P2,1

B1,1)

B1,1

P1,2

前向和反向链接霍恩子句：至多只有一个正文字的文字析取式(P1,2B1,1)P2,1P1,2P2,1(B1,1P1,2P2,1)每个霍恩子句都可写成一个蕴涵式：(P1,2B1,1)≡P1,2B1,1没有正文字的霍恩子句：可写成结论为False的蕴涵式例如：P1,2P2,1≡〔P1,2P2,1)False确定子句：只有一个正文字，例如：P2,1，断言一个事实

使用霍恩子句的推理可在前向链接和反向链接中进展使用霍恩子句判定蕴涵需要的时间和数据库大小成线性关系前向链接判定单个命题符号q是否被霍恩子句的学问库所蕴涵：从学问库的事实(正文字)开头，假设蕴涵的全部前提，则将其结论添加到事实集。直到查询q被添加或无法进展更进一步的推理前向链接前向链接前向链接前向链接前向链接前向链接前向链接前向链接牢靠的完备的前向链接中每个推理本质上是分别规章的一个应用。从查询q反向进展：查询q是否是事实，否则查找学问库中能以q为结论的蕴涵，假设其中某个蕴涵的全部前提都能证明为真，则q为真。反向链接反向链接反向链接反向链接反向链接反向链接反向链