《湘潭大学-人工智能幻灯片-确定性推理-part5》由会员分享，可在线阅读，更多相关《湘潭大学-人工智能幻灯片-确定性推理-part5（38页珍藏版）》请在金锄头文库上搜索。
1、Artificial Intelligence (AI) 人工智能,第二章：知识表示与推理,内容提要,第二章：知识表示与推理,1.推理的基本概念,2.搜索策略,3.自然演绎推理,4.消解演绎推理,5.基于规则的演绎推理,自然演绎推理,自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。 自然演绎推理最基本的推理规则是三段论推理，它包括： 假言推理 拒取式 假言三段论,自然演绎推理,假言推理 ： P, PQ Q 表示：由PQ 以及P为真，可以推出Q为真 例如：由“如果x是金属，则x能导电”，以及“铜是金属”，可以推出“铜能导电”。 拒取式：PQ,
2、Q P 表示：由PQ 为真以及Q为假，可以推出P为假 例如：由“如果下雨，则地上会湿”，以及“地上不湿”，可以推出“没有下雨”。 假言三段论：PQ, QR PR,自然演绎推理,注意避免以下两类错误： 肯定后件的错误：当PQ为真时，希望通过肯定后件Q为真来推出前件P为真，这是不允许的。 例如：伽利略在论证哥白尼的日心说时，曾使用了如下推理： (1)如果行星系统是以太阳为中心的，则金星会显示出位相变化； (2)金星显示出位相变化； (3)所有，行星系统是以太阳为中心的 这就是使用了肯定后件的推理，违反了经典逻辑的逻辑规则。,自然演绎推理,注意避免以下两类错误： 否定前件的错误：当PQ为真时，希望通
3、过否定前件P来推出后件Q为假，这也是不允许的。 例如： (1)如果下雨，则地上会湿 (2)没有下雨 (3)所有，地上不湿 事实上，如果向地上洒水，地上也是会湿的。这就是使用了否定前件的推理，违反了经典逻辑的逻辑规则。,自然演绎推理,自然演绎推理的例子 设已知如下事实：A, B, AC, BCD, DQ 求证：Q为真。 证明： 因为 A, AC C 假言推理 B, C BC 引入合取词 BC，BCD D 假言推理 D, DQ Q 假言推理 因此，Q为真,自然演绎推理,自然演绎推理的例子 设已知如下事实： (1) 只要是需要编程序的课，王程都喜欢。 (2) 所有的程序设计语言课都是需要编程序的课。
4、 (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
5、 , C) 假言推理 C/x 因此，王程喜欢C这门课。,自然演绎推理,自然演绎推理的优缺点 优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。 缺点：是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。,内容提要,第二章：知识表示与推理,1.推理的基本概念,2.搜索策略,3.自然演绎推理,4.消解演绎推理,5.基于规则的演绎推理,消解演绎推理,消解演绎推理：是一种基于鲁滨逊（Robinson）消解原理的机器推理技术。 鲁滨逊消解原理亦称为消解原理，是鲁滨逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法
6、”。 在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明PQ永真。 要证明PQ永真，就是要证明PQ在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。,消解演绎推理,消解演绎推理： 鲁滨逊消解原理把永真性的证明转化为关于不可满足性的证明。 要证明PQ永真，只需证明PQ不可满足 因为： (PQ) ( PQ) P Q 海伯伦(Herbrand)定理为自动定理证明奠定了理论基础。 鲁滨逊(Robinson)提出的消解原理使机器定理证明成为现实。,消解演绎推理,消解演绎推理 子句集及其化简 鲁滨逊消解原理 消解反演推理的消解策略
7、用消解反演求取问题的答案,消解演绎推理,消解演绎推理 子句集及其化简 鲁滨逊消解原理 消解反演推理的消解策略 用消解反演求取问题的答案,子句集及其化简,鲁滨逊消解原理是在子句集的基础上讨论问题的。因此，讨论消解演绎推理之前，需要先讨论子句集的有关概念。 子句和子句集 原子谓词公式及其否定统称为文字。 例如: P(x)、Q(x)、 P(x)、 Q(x)等都是文字。 任何文字的析取式称为子句。 例如，P(x)Q(x)，P(x，f(x)Q(x，g(x)都是子句。,子句集及其化简,子句和子句集 不含任何文字的子句称为空子句。 由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可
8、满足的。 空子句一般被记为NIL。 由子句或空子句所构成的集合称为子句集。 在子句集中，子句之间是合取关系 子句集中的变元受全称量词的约束 任何谓词公式都可通过等价关系及推理规则化为相应的子句集,子句集及其化简,把谓词公式化成子句集的步骤 Step 1： 利用等价关系消去“”和“” 反复使用如下等价公式： PQ PQ PQ (PQ)(PQ) 即可消去谓词公式中的连接词“”和“”。 例如： (x)(y)P(x,y) (y)(Q(x,y)R(x,y) 经等价变化后为： (x)(y)P(x,y) (y)(Q(x,y)R(x,y),子句集及其化简,Step 2：利用等价关系把“”移到紧靠谓词的位置上
9、反复使用 双重否定率：(P) P 摩根定律： (PQ) PQ (PQ) PQ 量词转换率： (x)P(x) (x) P(x) (x)P(x) (x) P(x) 使得每个否定符号最多只作用于一个谓词上。 例如：上式(x)(y)P(x,y) (y)(Q(x,y)R(x,y) 经等价变换后为 (x)(y)P(x，y)(y)( Q(x，y) R(x，y),子句集及其化简,Step 3：重新命名变元，使不同量词约束的变元有不同的名字 例如：上式经重新命名变换后为 (x)(y)P(x，y)(z)( Q(x，z) R(x，z) Step 4：消去存在量词。消去存在量词时，需要区分以下两种情况： 1）存在量词
10、不出现在全称量词的辖域内，只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。例如： (x)P(x) 可化为P(A) 2）存在量词位于一个或者多个全称量词的辖域内,子句集及其化简,如下面的谓词公式： (x1)(xn) (y)P(x1，x2 , xn ,y) 则需要用Skolem函数f(x1，x2 , xn)替换受该存在量词约束的变元y，然后再消去该存在量词。 例如：继续上面的例子 (x)(y)P(x，y)(z)( Q(x，z) R(x，z) 式子中存在量词(y)及(z)都位于(x)的辖域内，所以需要用Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和g(x)
11、，则替换后得到： (x)(P(x , f(x)(Q(x , g(x)R(x , g(x),子句集及其化简,Step 5：把全称量词全部移到公式的左边 上式中由于只有一个全称量词，而且它位于公式的最左边，所以这里不需要做任何工作。 如果在公式内部有全称量词，就需要把它们都移到公式的左边。 Step 6：利用等价关系 P (QR) (PQ) (PR) 把公式化为Skolem标准形 Skolem标准形的一般形式为 (x1)(xn) M(x1,x2,xn) 其中， M(x1,x2,xn)是Skolem标准形的母式，它由子句的合取所构成。,子句集及其化简,例如：前面的公式化为Skolem标准形后为 (x
12、)( (P(x , f(x)Q(x , g(x) (P(x , f(x) R(x , g(x) ) Step 7：消去全称量词。由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。 例如：上式消去全称量词后为 (P(x , f(x)Q(x , g(x) (P(x , f(x)R(x , g(x) Step 8：对变元更名，使不同子句中的变元不同名 例如：上式经更名后得到 (P(x , f(x)Q(x , g(x) (P(y , f(y)R(y , g(y),子句集及其化简,Step 9：消去合取词，就得到子句集。 例如：消去合取词后，上式 (P(x ,
13、f(x)Q(x , g(x) (P(y , f(y)R(y , g(y) 就变为下述子句集 P(x , f(x)Q(x , g(x) P(y , f(y)R(y , g(y),子句集及其化简,子句集的意义 在上述化简过程中，由于在消去存在量词时所用的Skolem函数可以不同，因此化简后的标准子句集是不唯一的。 因此，当原谓词公式为非永假时，它与其标准子句集并不等价。但当原谓词公式为永假（或不可满足）时，其标准子句集则一定是永假的，即Skolem化并不影响原谓词公式的永假性。 子句集S的不可满足性：对于任意论域中的任意一个解释，S中的子句不能同时取得真值T。,子句集及其化简,定理：设有谓词公式F
14、，其子句集为S，则F不可满足的充要条件是S不可满足。 由此定理可知，要证明一个谓词公式是不可满足的，只要证明其相应的标准子句集是不可满足的就可以了。 由于子句集中的子句之间是合取关系，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的。 空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。 这个结论是鲁滨逊消解原理的主要依据。,消解演绎推理,消解演绎推理 子句集及其化简 鲁滨逊消解原理 消解反演推理的消解策略 用消解反演求取问题的答案,鲁滨逊消解原理,鲁滨逊消解原理的基本思想 首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S； 然后设
15、法检验子句集S是否含有空子句，若含有空子句，则表明S是不可满足的；若不含有空子句，则继续使用消解法，在子句集中选择合适的子句进行消解，直至导出空子句或不能继续消解为止。 鲁滨逊消解原理包括 命题逻辑的消解 谓词逻辑的消解,命题逻辑的消解,消解推理的核心是求两个子句的消解式 消解式的定义及性质 若P是原子谓词公式，则称P与P为互补文字 设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新的子句C12，则称这一过程为消解，称C12为C1和C2的消解式，称C1和C2为C12的亲本子句。,命题逻辑的消解,例如：设C1=PQR，C2=PS，求C1和C2的消解式C12。 解：这里L1=P，L2=P，通过消解可以得到 C12= QRS 例如：设C1=Q，C2=Q，求C1和C2的消解式C12。 解：这里L1=Q，L2=Q，通过消解可以得到 C12= NIL,命题逻辑的消解,例如：设设C1 =P Q ，C2=Q，C3=P，求C
