人工智能7分析.ppt

人工智能　━━　一种现代方法 云南大学 施心陵讲授 第三部分 知识和推理  命题逻辑 谓词逻辑 知识表示方法 第七章 逻辑智能体 基于知识的智能体 Wumpus世界 逻辑 逻辑的历史 Aristotle：逻辑学 Leibnitz：数理逻辑 Gottlob frege:一阶谓词演算系统，《符号论》(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+y KB ╞ α 模型检验 模型检验 模型检验 模型检验 推理的可靠性和完备性 KB ├i α： α通过推理算法i从KB中导出， 推理算法i从KB中导出α 推理算法i是可靠的：如果KB ├i α， 则KB╞ α 推理算法i是完备的：如果 KB╞ α， 则KB ├i α 命题逻辑 逻辑连接符 合取式：p与q，记为p∧q 析取式：p或q，记为p ? q 蕴含式：如果p则q，记为p ? q 等价式： p当且仅当q，记为p ? q 否定式：非，?p 优先级： ?， ∧， ?， ?， ? 命题表示 将陈述句转化为命题公式： 例如：设“下雨”为p，“骑车上班”为q 1.“只要不下雨，我就骑自行车上班”。 ?p是q的充分条件，可得命题公式： ?p ? q 2. “只有不下雨，我才骑自行车上班”。 ?p是q的必要条件，可得命题公式： q ? ?p 语义 例如：某模型下，P1,2 P2,2 P3,1 假 真 假 Wumpus世界的知识库 Pi,j ：在[i, j]有陷阱 Bi,j ：在[i, j]有微风 ? P1,1 ?B1,1 B2,1 陷阱使得其邻域方格有微风 B1,1 ? (P1,2 ? P2,1) B2,1 ? (P1,1 ? P2,2 ? P3,1) 推理的基本概念 推理真值表 真值表枚举算法 推理方法 推理的不确定性及其单调性 交换律：p∧q ≡ q∧p p∨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) ≡ p p∧(p∨q) ≡ p 同一律： p∨ 0 ≡ p p∧1 ≡ p 蕴含等值式：p ? q ≡ ? p ∨ q （蕴含消去） 假言易位式： p ? q ≡ ? q ? ?p（逆否命题） 双向蕴含消去： p?q ≡( p? q) ∧ (q ? p) 合法性和可满足性 例如：True，A ??A, A ? A, (A ? (A ? B)) ? B 若α至少有一个成真赋值，则称α为可满足的 e.g., A? B, C 若α无成真赋值，则称α为不可满足的，称矛盾式或永假式， 例如： A??A α是合法的，当且仅当?α是不可满足的 α是可满足的，当且仅当?α是不合法的 反证法（归谬）： KB ╞ α当且仅当(KB ??α)是不可满足的 推理规则 逻辑等价 分离规则： α? β, α β 例如，已知（WumpusAhead ?WumpusAlive) ?shoot 和（WumpusAhead ?WumpusAlive)，可推导出shoot 与消去（合取式推导出任何合取子句）： α ? β