人工智能(19)

第三部分知识和推理命题逻辑谓词逻辑知识表示方法,第七章逻辑智能体,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+2y在x=7,y=1的世界中为真x+2y在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无陷阱KB1,模型检验,KB2,2：2,2无陷阱,模型检验,模型检验:枚举出所有可能的模型用于检验在KB中为真的所有模型中为真。,推理的可靠性和完备性,KBi：通过推理算法i从KB中导出，推理算法i从KB中导出推理算法i是可靠的：如果KBi，则KB推理算法i是完备的：如果KB，则KBi,命题逻辑,命题：能够分辨真假的陈述句。例如：1+1=2雪是绿色的昆明是云南的省会快点走吧!到哪去？,一个原子命题可以用字母表示(命题符号)。命题逻辑是由命题符号和逻辑连接符组成。,原子命题：一个命题，且是不能再进一步分解成更简单语句。是命题的基本单位。,逻辑连接符,合取式：p与q，记为pq析取式：p或q，记为pq蕴含式：如果p则q，记为pq等价式：p当且仅当q，记为pq否定式：非，p优先级：，,命题表示,将陈述句转化为命题公式：例如：设“下雨”为p，“骑车上班”为q1.“只要不下雨，我就骑自行车上班”。p是q的充分条件，可得命题公式：pq2.“只有不下雨，我才骑自行车上班”。p是q的必要条件，可得命题公式：qp,3.“应届毕业生，得过国家级竞赛一等奖或全班排名第一，保送研究生”设：p“应届毕业生”，q“保送研究生”，r“得过国家级竞赛一等奖”，t“全班排名第一”则有命题公式：p（rt）q,True永真命题，False永假命题析取范式：仅由有限个简单合取式组成的析取式p（pq）（pq）合取范式：仅由有限个简单析取式组成的合取式,p（pq）（pq）,语义,例如：某模型下，P1,2P2,2P3,1假真假,语义定义了用于判定关于特定模型的语句真值的规则,逻辑连接符的真值表：指定了复合句在其组成部分的真值的每种可能赋值情况下的真值。,P1,2(P2,2P3,1)=true(truefalse)=truetrue=true,Wumpus世界的知识库,Pi,j：在i,j有陷阱Bi,j：在i,j有微风P1,1B1,1B2,1陷阱使得其邻域方格有微风B1,1(P1,2P2,1)B2,1(P1,1P2,2P3,1),推理的基本概念,推理：从已知事实出发，运用已掌握的知识，推导出其中蕴含的事实性结论或归纳出某些新的结论的过程。,推理所用的事实：初始证据；中间结论。,初始证据,推理机,结论,知识库,目标是判断某些语句x，kB|=x是否成立。模型检验：枚举出模型，验证x在KB为真的每个模型中为真,推理真值表,1：P1,2,2：P2,2,真值表枚举算法,真值表枚举算法，是可靠的、完备的n个符号，存在2n个模型，时间复杂度O(2n)用于命题逻辑的有效模型检验推理算法包括回溯(DPLL算法)和局部搜索方法（WALKSAT算法）。,推理方法,演绎推理：从已知的一般性知识出发，推理出适合于某些个别情况的结论的过程。归纳推理：从大量的特殊事例出发，归纳出一般性结论的推理过程。默认推理：在知识不完全的情况下假设某些条件已经具备所进行的推理。,推理的不确定性及其单调性,确定性推理：推理所用的证据、知识及结论都是可以精确表示的，其真值不为真就为假，不会有第三种情况出现。不确定性推理：推理所用的证据、知识及结论都是不确定的，都是不可以精确表示的，其真值位于真和假之间。单调性推理：由于新知识的加入和使用，使推理所得到的结论会越来越接近目标。非单调性推理：推理过程中某些新知识的加入和使用，不但没有加强已经推出的结论，反而会否定原来已推出的结论。,交换律：pqqppqqp结合律：(pq)rp(qr)(pq)rp(qr)分配率：p(qr)(pq)(pr)p(qr)(pq)(pr),基本等值式：,，当且仅当且,摩根律：(pq)pq(pq)pq吸收律：p(pq)pp(pq)p同一律：p0pp1p蕴含等值式：pqpq（蕴含消去）假言易位式：pqqp（逆否命题）双向蕴含消去：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),单元归结规则l1lk,ml1li-1li+1lk其中liandm是互补文字(一个文字是另一个文字的否定式).全归结规则l1lk,m1mnl1li-1li+1lkm1mj-1mj+1.mn其中li和mj是互补文字,归结规则：,P1,3P2,2,P2,2P1,3归并：（AB）和（AB）归结得到AA，最终简化为A,li真，則mj假(m1mj-1mj+1.mn)真li假，l1li-1li+1lk真,归结规则的完备性：任何完备的搜索算法，只使用归结规则，就可以生成命题逻辑中被任何知识库蕴涵的任何结论。,l1lk,m1mnl1li-1li+1lkm1mj-1mj+1.mn,归结规则的可靠性：,已知A为真，无法用归结自动生成结论AB，但可以用归结判断AB是否为真。,将命题写成合取范式求出子句集S对子句集使用归结推理规则归结式作为新子句参加归结归结式为空子句，S是不可满足的（矛盾），原命题成立,归结过程,例如：证明公式（pq）（qp）证：将待证明公式转化为归结命题公式：（pq）(qp)将该公式转化为合取范式pqpq(qp)(qp)qp（pq）(qp)(pq)qp则子句集：pq，q，p,对子句集中的子句进行归结：（1）pq（2）q（3）p（4）q（1,3归结）（5）空（2,4归结）,KB=(B1,1(P1,2P2,1)B1,1=P1,2,Wumpus世界的归结推理,(B1,1(P1,2P2,1)B1,1P1,2(B1,1P1,2P2,1)(P1,2B1,1)(P2,1B1,1)B1,1P1,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为真。,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,前向链接和反向链接的比较,前向链接是数据驱动的推理，由感知信息自动推理，无意识多用于目标识别，路线决策可能产生和目标无关的中间结果反向链接是目标指导的推理，适用于求解：“现在该做什么”，“钥匙在哪里”一类问题耗散远小于知识库大小的线性值常将前向推理限制在生成与要用反向链接求解的查询相关的事实上。,基于命题逻辑的智能体,采用推理算法和知识库的智能体以电路形式直接计算逻辑表达式的智能体,采用推理算法和知识库的智能体,P1,1W1,1Bx,y(Px,y+1Px,y-1Px+1,yPx-1,y)Sx,y(Wx,y+1Wx,y-1Wx+1,yWx-1,y)W1,1W1,2W4,4W1,1W1,2W1,1W1,34*