logic1讲解.ppt

前向链接和反向链接的对比 前向链接：data-driven 反向链接：goal-driven 通常，反向链接的耗散远小于KB大小的线性值。 对于智能体来说，应该共享前向和反向推理的工作，将前向推理限制在生成与要用反向链接求解的查询有关的事实上。 有效的命题推理 基于模型检验的2个命题推理算法家族： 基于回溯搜素 DPLL 基于爬山法有哪些信誉好的足球投注网站 WalkSAT 主要内容 基于知识的智能体 总体的智能体设计 wumpus世界：一个基于知识的智能体运转的例子 逻辑 命题逻辑 命题逻辑的推理形式 基于命题逻辑的智能体 用逻辑推理寻找陷阱和wumpus 陈述“物理规则”的知识库 ?P1,1 ?W1,1 Bx,y ? (Px,y+1 ? Px,y-1 ? Px+1,y ? Px-1,y) （1） Sx,y ? (Wx,y+1 ? Wx,y-1 ? Wx+1,y ? Wx-1,y) （2） W1,1 ? W1,2 ? … ? W4,4 ?W1,1 ? ?W1,2 ?W1,1 ? ?W1,3 … ?64个符号和155个语句 用命题逻辑来辨别陷阱、wumpus和安全方格的智能体 命题逻辑的表达能力的局限性 KB包含以(1)和(2)（见再前页)中给出形式表示的每个方格的“物理规则”语句，环境规模越大，要求的初始KB就越大。 如果要记录位置与方向，KB需包含以下形式的语句： Lx,yt ? FacingRightt ? Forwardt ? Lx+1,yt＋1 需要表达能力更强的逻辑语言。 小结 智能化智能体需要关于世界的知识以达到良好的决策 逻辑智能体对知识库进行推理，以导出新的语句，并用它们来决策。 逻辑的基本概念 表示语言通过语法和语义来定义 语句之间的蕴涵关系 推理：可靠性和完备性 归结规则产生一个用于表示为合取范式的知识库的完备推理算法。 前向链接和反向链接都是用于以Horn Form表示的知识库的非常自然的推理算法。 命题逻辑缺乏表达能力。 * * 表示和学习 * 完备性：KB的有限性。 * figure 7.9 * * * * * 推理算法的可靠性与完备性 * Resolution yields a complete inference algorithm. * CNF in order to apply resolution. 逻辑等价关系（1） 逻辑等价关系（2） wumpus世界的推理 证明： 从R2开始 R6： (B1,1?(P1,2∨P2,1))∧((P1,2∨P2,1)?B1,1) R2双向蕴涵消去 R7： (P1,2∨P2,1)?B1,1 R6与消去 R8： ?B1,1??(P1,2∨P2,1) 逆否命题逻辑等价 R9： ?(P1,2∨P2,1) R4/R8分离规则 R10 ?P1,2∧?P2,1 迪摩根定律 证毕. 用R1~R5规则和推理模式证明： [1,2]和[2,1]中没有陷阱， 即?P1,2和?P2,1 证明、方法 模型检查 真值表枚举：时间复杂度为O(2n)。 推理规则的应用 寻找证明的过程与有哪些信誉好的足球投注网站问题中寻找解的过程非常类似：定义后继函数以便生成推理规则所有可能的应用。 从初始知识库正向出发，应用推理规则以生成目标语句； 从目标语句反向出发，试图找到由初始知识库引出的推理规则链。 命题逻辑的推理是NP完全的 逻辑系统的单调性 单调性：对于任意语句?和?，如果KB|= ?，那么KB? ? |= ?。 单调性意味着任何时刻只要在知识库中发现了合适的前提，就可以应用推理规则 规则的结论和KB中其它内容无关。 归结（Resolution） 归结： 单一推理规则，与完备的有哪些信誉好的足球投注网站算法相结合，得到完备的推理算法。 归结：单个归结 R11： ?B1,2 R12： B1,2? (P1,1?P2,2?P1,3) 事实 R13： ?P2,2 R14： ?P1,3 同R10的推导过程 R15： P1,1?P2,2?P3,1 对R3消去、R5分离 R16： P1,1 ? P3,1 R13/R15归结 R17： P3,1 R1/R16归结 例子：Agent从[2,1]返回[1,1]， 接着走到[1,2]并在此地闻到臭气， 但没有微风。 归结（Resolution） 全归结规则： 假设：l1 ?… ? lk and