12 确定性推理 part5.ppt

Artificial Intelligence (AI)人工智能 主讲：戚玉涛 内容提要 自然演绎推理 自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。 自然演绎推理最基本的推理规则是三段论推理，它包括： 假言推理 拒取式 假言三段论 自然演绎推理 假言推理 ： P, P→Q ? Q 表示：由P→Q 以及P为真，可以推出Q为真 例如：由“如果x是金属，则x能导电”，以及“铜是金属”，可以推出“铜能导电”。 拒取式：P→Q, ﹁ Q ? ﹁ P 表示：由P→Q 为真以及Q为假，可以推出P为假 例如：由“如果下雨，则地上会湿”，以及“地上不湿”，可以推出“没有下雨”。 假言三段论：P→Q, Q→R ? P→R 自然演绎推理 注意避免以下两类错误： 肯定后件的错误：当P→Q为真时，希望通过肯定后件Q为真来推出前件P为真，这是不允许的。 例如：伽利略在论证哥白尼的日心说时，曾使用了如下推理： (1)如果行星系统是以太阳为中心的，则金星会显示出位相变化； (2)金星显示出位相变化； (3)所有，行星系统是以太阳为中心的 这就是使用了肯定后件的推理，违反了经典逻辑的逻辑规则。 自然演绎推理 注意避免以下两类错误： 否定前件的错误：当P→Q为真时，希望通过否定前件P来推出后件Q为假，这也是不允许的。 例如： (1)如果下雨，则地上会湿 (2)没有下雨 (3)所有，地上不湿 事实上，如果向地上洒水，地上也是会湿的。这就是使用了否定前件的推理，违反了经典逻辑的逻辑规则。 自然演绎推理 自然演绎推理的例子 设已知如下事实：A, B, A→C, B∧C→D, D→Q 求证：Q为真。 证明： 因为 A, A→C? C 假言推理 B, C? B∧C 引入合取词 B∧C，B∧C→D ? D 假言推理 D, D→Q ? Q 假言推理 因此，Q为真 自然演绎推理 自然演绎推理的例子 设已知如下事实： (1) 只要是需要编程序的课，王程都喜欢。 (2) 所有的程序设计语言课都是需要编程序的课。 (3) C是一门程序设计语言课。 求证：王程喜欢C这门课。 证明：首先定义谓词 Prog(x)：x是需要编程序的课。 Like(x, y): x喜欢y。 Lang(x): x是一门程序设计语言课 自然演绎推理 自然演绎推理的例子 把已知事实及待求解问题用谓词公式表示如下： Prog(x)→Like(Wang , x) (?x)( Lang(x)→Prog(x)) Lang(C) 应用推理规则进行推理： Lang(y)→Prog(y) 全称固化 Lang(C)，Lang(y)→Prog(y) ? Prog(C) 假言推理 {C/y} Prog(C), Prog(x)→Like(Wang , x) ? Like(Wang , C) 假言推理 {C/x} 因此，王程喜欢C这门课。 自然演绎推理 自然演绎推理的优缺点 优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。 缺点：是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。 内容提要 归结演绎推理 归结演绎推理：是一种基于鲁滨逊（Robinson）归结原理的机器推理技术。 鲁滨逊归结原理亦称为消解原理，是鲁滨逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法”。 在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明P→Q永真。 要证明P→Q永真，就是要证明P→Q在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。 归结演绎推理 归结演绎推理： 鲁滨逊归结原理把永真性的证明转化为关于不可满足性的证明。 要证明P→Q永真，只需证明P∧﹁Q不可满足 因为：﹁ (P→Q) ? ﹁(﹁ P∨Q) ? P∧﹁ Q 海伯伦(Herbrand)定理为自动定理证明奠定了理论基础。 鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实。 归结演绎推理 归结演绎推理 子句集及其化简 鲁滨逊归结原理 归结反演推理的归结策略 用归结反演求取问题的答案 归结演绎推理 归结演绎推理 子句集及其化简 鲁滨逊归结原理 归结反演推理的归结策略 用归结反演求取问题的答案 子句集及其化简 无论是海伯伦理论，还是鲁滨逊归结原理是在子句集的基础上讨论问题的。因此，讨论归结演绎推理之前，需要先讨论子句集的有关概念。 子句和子句集 原子谓词公式及其否定统称为文字。 例如: P(x)、Q(x)、﹁