第3章确定性推理

第三章确定性推理人工智能原理与应用按照推理过程所用知识的确定性，推理可分为确定性推理和不确定性推理。自然演绎推理和归结推理是经典的确定性推理，它们以数理逻辑的有关理论、方法和技术为理论基础，是机械化的、可在计算机上加以实现的推理方法。本章在讨论有关推理的一般概念以及命题和谓词逻辑的基础上，介绍自然演绎推理方法和基于一阶谓词逻辑的归结推理方法。第三章确定性推理人工智能原理与应用3.1推理概述3.2命题逻辑3.3谓词逻辑3.4自然演绎推理方法3.5归结推理方法3.6归结过程的控制策略第三章确定性推理人工智能原理与应用3.1推理概述3.1.1推理的基本概念推理是指从已知事实出发，运用已掌握的知识，推导出其中蕴含的事实性结论或归纳出某些新的结论的过程。其中，推理所用的事实可分为两种情况，一种是与求解问题有关的初始证据；另一种是推理过程中所得到的中间结论，这些中间结论可以作为进一步推理的已知事实或证据。人工智能系统的构成：推理机－－－一些程序来完成的；综合数据库－－－存放有用于推理的事实或证据；知识库－－－存放有用于推理所必须的知识。第三章确定性推理人工智能原理与应用3.1.2推理的方法及其分类1.按照推理的逻辑基础分类可分为演绎推理、归纳推理和默认推理。（1）演绎推理演绎推理是从已知的一般性知识出发，推理出适合于某种个别情况的结论的过程。它是一种由一般到个别的推理方法。3.1推理概述第三章确定性推理人工智能原理与应用3.1推理概述（2）归纳推理归纳推理是从大量特殊事例出发，归纳出一般性结论的推理过程，是一种由个别到一般的推理方法。其基本思想是：首先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认，数学归纳法就是归纳推理的一种典型例子。归纳推理又可分为：从特殊事例考察范围看：完全归纳推理、不完全归纳推理；从使用的方法看：枚举归纳推理、类比归纳推理。第三章确定性推理人工智能原理与应用（3）默认推理默认推理又称缺省推理，是在知识不完全的情况下假设某些条件已经具备所进行的推理。也就是说，在进行推理时，如果对某些证据不能证明其不成立的情况下，先假设它是成立的，并将它作为推理的依据进行推理，但在推理过程中，当由于新知识的加入或由于所推出的中间结论与已有知识发生矛盾时，就说明前面的有关证据的假设是不正确，这时就要撤消原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理3.1推理概述第三章确定性推理人工智能原理与应用2.按所用知识的确定性分类按推理时所用知识的确定性来划分，推理可分为确定性推理、不确定性推理。3.按推理过程的单调性按照推理过程中所推出的结论是否单调地增加，或者说按照推理过程所得到的结论是否越来越接近最终目标来分类，推理可分为单调推理与非单调推理。3.1推理概述第三章确定性推理人工智能原理与应用3.1.3推理的控制策略推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制策略。控制策略包括推理方向、搜索策略、冲突消解策略等；而推理方法则是指在推理控制策略确定之后，在进行具体推理时所要采取的匹配方法或不确定性传递算法等方法。推理方向用来确定推理的驱动方式，即是数据（证据）驱动或是目标驱动。所谓数据驱动即指推理过程从初始证据开始直到目标结束，而目标驱动则是指推理过程从目标开始进行反向推理，直到出现与初始证据相吻合的结果。按照对推理方向的控制，推理可分为正向推理、反向推理、混合推理及双向推理四种情况。3.1推理概述第三章确定性推理人工智能原理与应用•正向推理是一种从已知事实出发、正向使用推理规则的推理方式，它是一种数据（或证据）驱动的推理方式，又称前项链推理或自底向上推理。•反向推理是一种以某个假设目标为出发点，反向运用推理规则的推理方式，它是一种目标驱动的推理方式，又称反向链推理或自顶向下推理。•混合推理是把正向推理和反向推理结合起来所进行的推理。•所谓双向混合推理是指正向推理和反向推理同时进行，使推理过程在中间的某一步骤相汇合而结束的一种推理方法。3.1推理概述第三章确定性推理人工智能原理与应用3.1.4推理的冲突消解策略推理过程中的冲突消解策略，就是确定如何从多条匹配规则中选出一条规则作为启用规则，将它用于当前的推理。目前已有的多种冲突消解策略的基本思想都是对匹配的知识或规则进行排序，以决定匹配规则的优先级别，优先级高的规则将作为启用规则。常用排序方法有如下几种:3.1推理概述第三章确定性推理人工智能原理与应用(1)按就近原则排序(2)按知识特殊性排序(3)按上下文限制排序(4)按知识的新鲜性排序(5)按知识的差异性排序(6)按领域问题的特点排序(7)按规则的次序排序(8)按前提条件的规模排序3.1推理概述第三章确定性推理人工智能原理与应用3.2命题逻辑3.2.1命题定义3.1能够分辨真假的语句称作命题。定义3.2一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为原子命题。原子命题是命题中最基本的单位。我们一般用P、Q、R、…大写拉丁字母表示命题，而命题的真与假分别用“T”与“F”表示。用大写英文字母表示的命题既可以是一个特定的命题，也可以是一个抽象的命题。前者称为命题常量，后者称为命题变量。对于命题变量而言，只有把确定的命题代入后，它才可能有明确的逻辑值（T或F）。第三章确定性推理人工智能原理与应用3.2.2命题公式1.连接词～：称为“非”或“否定”。∨：称为“析取”。∧：称为“合取”。→：称为“条件”或者“蕴含”。：称为“双条件”。PQ表示“P当且仅当Q”。表3.1命题逻辑真值表PQP∨QP∧QP→QPQ~PTTTTTTFTFTFFFFFTTFTFTFFFFTTT3.1推理概述第三章确定性推理人工智能原理与应用2.命题公式定义3.3以下面的递归形式给出命题公式的定义：•（1）原子命题是命题公式。•（2）A是命题公式，则～A也是命题公式。•（3）若A和B都是命题公式，则A∧B、A∨B、A→B、AB•（4）只有按（1）—（3）所得的公式才是命题公式。3.1推理概述第三章确定性推理人工智能原理与应用命题公式的缺点：•无法把所描述的客观事物的结构和逻辑特征反映出来•不能把不同事物的共同特征反映出来P:“张三是李四的老师”；仅用字母P看不出张三和李四之间的师生关系。为了克服命题逻辑的局限性，引入了下面的谓词逻辑3.1推理概述第三章确定性推理人工智能原理与应用3.3谓词逻辑3.3.1谓词与个体在谓词逻辑中，将原子命题分解为谓词与个体两部分。个体是指可以独立存在的物体，可以是抽象的或具体的。谓词则是用于刻画个体的性质、状态或个体间的关系的。例如：“李白是诗人”可表示为：poet(LiBai)poet称为谓词，用以刻画“是诗人”；LiBai称为个体第三章确定性推理人工智能原理与应用3.3谓词逻辑一个谓词可以与一个个体相关联，此种谓词称作一元谓词，它刻画了个体的性质。一个谓词也可以与多个个体相关联，此种谓词称为多元谓词，它刻画了个体间的“关系”。第三章确定性推理人工智能原理与应用谓词的一般形式：P(x1,x2,…,xn)其中P是谓词，而x1,x2,…,xn是个体。谓词通常用大写字母表示，个体通常用小写字母表示。项：在谓词中，个体可以是常量，也可以是变量，还可以是一个函数。例如，“小刘的哥哥是个工人”，可以表示为worker(brother(Liu))，其中brother(Liu)是一个函数。个体常数、变量和函数统称为项。谓词的语义：由使用者根据需要人为地定义.3.3谓词逻辑第三章确定性推理人工智能原理与应用谓词的元数：谓词中包含的个体数目称为谓词的元数。谓词的阶数：在谓词P(x1,x2,…,xn)中，若xi(i=1,2,…,n)都是个体常量、变元或函数，则称它为一阶谓词。如果某个xi本身又是一个一阶谓词，则称它为二阶谓词，依次类推。3.3谓词逻辑第三章确定性推理人工智能原理与应用3.3.2谓词公式1.连接词～，∨，∧，→，2.量词全称量词（x）,和存在量词（x）。3.谓词演算公式定义3.4谓词演算中，由单个谓词构成的不含任何连接词的公式，叫做原子谓词公式。3.3谓词逻辑第三章确定性推理人工智能原理与应用由原子公式的定义出发，可定义谓词演算的合式公式如下。定义3.5可按下述规则得到谓词演算的合式公式：（1）原子谓词公式是合式公式。（2）若A是合式公式，则～A也是合式公式。（3）若A和B都是合式公式，则A∧B、A∨B、A→B、AB也都是合式公式。（4）若A是合式公式，x是任一个体变元，则(x)A和(x)A也都是合式公式。（5）只有按（1）—（4）所得的公式才是合式公式。3.3谓词逻辑第三章确定性推理人工智能原理与应用4.量词辖域与约束变元在一个公式中，如果有量词出现，位于量词后面的单个谓词或者用括弧括起来的合式公式称为量词的辖域。在辖域内与量词中同名的变元称为约束变元。3.3谓词逻辑第三章确定性推理人工智能原理与应用3.3.3谓词公式的永真性和可满足性1．谓词公式的解释定义3.6设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按照如下规定赋值：（1）为每个个体常量指派D中的一个元素；（2）为每个n元函数指派一个从Dn到D的映射，其中Dn={(x1,x2,…,xn)|x1,x2,…,xnD}（3）为每个n元谓词指派一个从Dn到{F,T}的映射；则称这些指派为公式P在D上的一个解释。3.3谓词逻辑第三章确定性推理人工智能原理与应用例3.1设个体域D={1,2}，求公式A=(x)(P(x)→Q(f(x),b))在D上的某一个解释，并指出在此解释下公式A的真值。(详细的求解过程参见教材)3.3谓词逻辑第三章确定性推理人工智能原理与应用2．谓词公式的永真性定义3.7如果谓词公式P，对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P永真。定义3.8如果谓词公式P对于个体域D上的所有解释都取得假值F，则称P在D上是永假的；如果P在每个非空个体域上均永假，则称P永假。谓词公式的永假性又称为不可满足性或不相容性。3.3谓词逻辑第三章确定性推理人工智能原理与应用3．谓词公式的可满足性定义3.9对于谓词公式P，如果至少存在一个解释使得公式P在此解释下的真值为T，则称公式P是可满足的。按照定义3.9，对谓词公式P，如果不存在任何解释，使得P的取值为T，则称公式P是不可满足的。所以，谓词公式P永假与不可满足是等价的。若P永假，则也可称P是不可满足的。3.3谓词逻辑第三章确定性推理人工智能原理与应用3.3.4谓词公式的等价性与永真蕴含定义3.10设P与Q是两个谓词公式，D是它们共同的个体域。若对D上的任何一个解释，P与Q的取值都相同，则公式P和Q在域D上是等价的。如果D是任意个体域，则称P和Q是等价的，记作PQ。常用的一些等价式参见教材定义3.11对于谓词公式P和Q，如果P→Q永真，则称P永真蕴含Q，且称Q为P的逻辑结论，称P为Q的前提，记作P=Q。以后要用到的一些永真蕴含式参见教材3.3谓词逻辑第三章确定性推理人工智能原理与应用谓词逻辑中还有如下一些推理规则：（1）P规则：在推理的任何步骤上都可引入前提。（2）T规则：推理时，如果前面步骤中有一个或多个永真蕴含公式S，则可把S引入推理过程中。（3）CP规则：如果能从R和前提集合中推出S来，则可从前提集合推出R→S来。（4）反证法：P=Q，当且仅当P∧～QF，即Q为P的逻辑结论，当且仅当P∧～Q是不可满足的。推广之，可得如下定理。定理3.1Q为P1，P2，…，Pn的逻辑结论，当且仅当(P1∧P2∧…∧Pn)∧～Q是不可满足的。3.3谓词逻辑第三章确定性推理人工智能原理与应用3.3.5置换与合一1.置换置换的定义定义3.12置换是形如{t1/x1,t2/x2,…,tn/xn}的一个有限集。其中xi是变量，ti是不同于xi的项（常量，变量，函数），且xixj（Ij），i，j=1,2,…,n。3.3谓词逻辑第三章确定性推理人工智能原理与应用例如，{a/x,b/y,f(x)/z}，{