经典逻辑推理学习

1、2021/6/161第章经典逻辑推理第章经典逻辑推理、基本概念、基本概念、自然演绎推理、自然演绎推理、归结演绎推理、归结演绎推理、与或形演绎推理、与或形演绎推理2021/6/162基本概念基本概念l何为推理？何为推理？l从已知的事实出发，不断运用已掌握的从已知的事实出发，不断运用已掌握的（知识库中的）知识推出或归纳出新的（知识库中的）知识推出或归纳出新的事实（包括目标结论）的过程称为推理。事实（包括目标结论）的过程称为推理。人工智能中推理是由程序实现的，称这人工智能中推理是由程序实现的，称这个程序为推理机。个程序为推理机。2021/6/163推理方式及其分类推理方式及其分类l人工智能作为对人类

2、智能的模拟，有多人工智能作为对人类智能的模拟，有多种推理方式。它们是：种推理方式。它们是：l、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l、确定性推理、不确定性推理、确定性推理、不确定性推理l、单调推理、非单调推理、单调推理、非单调推理l、启发式推理、非启发式推理、启发式推理、非启发式推理l、基于知识的推理、统计推理、直觉、基于知识的推理、统计推理、直觉推理。推理。l分别解释如下：分别解释如下：2021/6/164、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l所谓演绎推理是从全称判断推导出特称所谓演绎推理是从全称判断推导出特称判断的过程，是从一般到个别的推理。判

3、断的过程，是从一般到个别的推理。经常用的是三段论式，它包括：经常用的是三段论式，它包括： 大前提：已知的一般性知识或假设；大前提：已知的一般性知识或假设；小前提：具体情况或个别事实；小前提：具体情况或个别事实；结论：由大前提推出的适合小前提所示情结论：由大前提推出的适合小前提所示情况的新判断。况的新判断。2021/6/165、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l例如有如下三个判断：例如有如下三个判断：l（）足球运动员的身体都是强壮的；（）足球运动员的身体都是强壮的；l（）高波是一名足球运动员；（）高波是一名足球运动员；l（）所以，高波的身体是强壮的。（）所以，高波的身体

4、是强壮的。l其中（）是大前提，（）是小前提其中（）是大前提，（）是小前提l（）是经演绎推出的结论。（）是经演绎推出的结论。l只要大前提和小前提是正确的，那麽由只要大前提和小前提是正确的，那麽由它们推出的结论就是正确的。它们推出的结论就是正确的。2021/6/166、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l演绎推理是人工智能中的一种重要推理演绎推理是人工智能中的一种重要推理方式，目前研制成功的各类智能系统中，方式，目前研制成功的各类智能系统中，大多是用演绎推理实现的。大多是用演绎推理实现的。2021/6/167、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l归纳

5、推理是从足够多的事例中归纳出一归纳推理是从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到般性结论的推理过程，是一种从个别到一般的推理。例如，某厂进行产品质量一般的推理。例如，某厂进行产品质量检查，如果对每一件产品都进行了检查，检查，如果对每一件产品都进行了检查，并且都是合格的，则推导出结论：该厂并且都是合格的，则推导出结论：该厂生产的产品是合格的。并称这种推理为生产的产品是合格的。并称这种推理为完全归纳推理。完全归纳推理。2021/6/168、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理如果是随机地抽查部分产品，并且它们如果是随机地抽查部分产品，并且它们是合格的，则得出

6、结论该厂的产品是是合格的，则得出结论该厂的产品是合格的，这种推理称为不完全归纳推合格的，这种推理称为不完全归纳推理。理。默认推理又称为缺省推理，它是在知识默认推理又称为缺省推理，它是在知识不完全的情况下假设某些条件已经具不完全的情况下假设某些条件已经具备所进行的推理。例如，在条件已备所进行的推理。例如，在条件已成立的情况下，如果没有足够的证据成立的情况下，如果没有足够的证据能证明条件不成立，则默认成立，能证明条件不成立，则默认成立，并在默认前提下进行推理，推导并在默认前提下进行推理，推导2021/6/169、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理 出某个结论来。由于这种推理

7、允许默认某些条件是成立出某个结论来。由于这种推理允许默认某些条件是成立的，这就摆脱了需要知道全部有关事实才能进行推理的，这就摆脱了需要知道全部有关事实才能进行推理的要求，使得在知识不完全的情况下也能进行推理。的要求，使得在知识不完全的情况下也能进行推理。在默认推理过程中，如果到某一时刻发现原先所做的在默认推理过程中，如果到某一时刻发现原先所做的默认不正确，则可以撤消默认推理和所推出的结论，默认不正确，则可以撤消默认推理和所推出的结论，并重新按新情况进行推理。并重新按新情况进行推理。 2021/6/1610、确定性推理、不确定性推理、确定性推理、不确定性推理l所谓确定性推理是指推理时所用的所谓确

8、定性推理是指推理时所用的知识都是精确的，推出的结论也是知识都是精确的，推出的结论也是确定的，是真或者是假。经典逻辑确定的，是真或者是假。经典逻辑推理就属于这一种。推理就属于这一种。l不确定性推理是指推理时所用的知不确定性推理是指推理时所用的知识不都是精确的，推出的结论也不识不都是精确的，推出的结论也不完全是肯定的，其真值位于真与假完全是肯定的，其真值位于真与假之间，命题的外延模糊不清。之间，命题的外延模糊不清。2021/6/1611、确定性推理、不确定性推理、确定性推理、不确定性推理 这里，我们特别强调的是不确定性推理。因为，这里，我们特别强调的是不确定性推理。因为，人类思维活动的特征经常是在

9、知识不完全的情人类思维活动的特征经常是在知识不完全的情况下进行多方位的思考及推理的。因此，要使况下进行多方位的思考及推理的。因此，要使计算机模拟人类的思维活动，就必须使它具有计算机模拟人类的思维活动，就必须使它具有不确定性推理的能力。不确定性推理的能力。2021/6/1612、单调推理、非单调推理、单调推理、非单调推理l所谓单调推理是指在推理的过程中随着所谓单调推理是指在推理的过程中随着推理的向前推进及新知识的加入，推出推理的向前推进及新知识的加入，推出的结论是单调递增的趋势，并且越来越的结论是单调递增的趋势，并且越来越接近目标，推理过程不会出现反复的情接近目标，推理过程不会出现反复的情况，即

10、不会因新知识的加入否定了前面况，即不会因新知识的加入否定了前面推出的结论，从而使推理又退回到前面推出的结论，从而使推理又退回到前面的某一步。经典逻辑演绎推理属于这一的某一步。经典逻辑演绎推理属于这一种。种。2021/6/1613、启发式推理、非启发式推理、启发式推理、非启发式推理l若按推理中是否使用与问题有关的启发若按推理中是否使用与问题有关的启发性知识，推理可分为启发式推理和非启性知识，推理可分为启发式推理和非启发式推理。发式推理。l所谓启发性知识是指与问题有关并且能所谓启发性知识是指与问题有关并且能加快推理进程、求得问题最优解的知识。加快推理进程、求得问题最优解的知识。2021/6/161

11、4、基于知识的推理、统计推理、直觉推、基于知识的推理、统计推理、直觉推理理l如果从方法论的角度来划分，推理可分如果从方法论的角度来划分，推理可分为基于知识的推理、统计推理和直觉推为基于知识的推理、统计推理和直觉推理。理。l顾名思义，所谓基于知识的推理就是根顾名思义，所谓基于知识的推理就是根据已掌握的事实，通过运用知识进行推据已掌握的事实，通过运用知识进行推理。理。l统计推理是根据对某事物的数据统计进统计推理是根据对某事物的数据统计进行推理。例如，对农作物的产量进行统行推理。例如，对农作物的产量进行统计，从而得出是否增产的结论，从而找计，从而得出是否增产的结论，从而找2021/6/1615、基于

12、知识的推理、统计推理、直觉推理、基于知识的推理、统计推理、直觉推理l出增产和减产的原因。就是运用了统计出增产和减产的原因。就是运用了统计推理。推理。l直觉推理又称常识性推理，是根据常识直觉推理又称常识性推理，是根据常识进行的推理。例如，当你从某建筑物下进行的推理。例如，当你从某建筑物下走过时，猛然发现有一物体坠落，这时走过时，猛然发现有一物体坠落，这时你立即就会意识到这有危险，并立即躲你立即就会意识到这有危险，并立即躲开，这就是使用了直觉推理。目前直觉开，这就是使用了直觉推理。目前直觉推理在计算机上的实现还是一件很困难推理在计算机上的实现还是一件很困难的工作。的工作。2021/6/1616推理

13、的控制策略推理的控制策略l推理的控制策略主要包括推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。l推理方向用于确定推理的驱动方式，分为正向推理、逆乡向推理、混合推理及双向推理四种。2021/6/1617正向推理正向推理l正向推理也称数据驱动推理，前向链推正向推理也称数据驱动推理，前向链推理、模式制导推理及前件推理等。理、模式制导推理及前件推理等。l正向推理过程的算法描述如下：正向推理过程的算法描述如下：l、将用户提供的初始已知事实送入数、将用户提供的初始已知事实送入数据库据库DB;l2、检查数据库、检查数据库DB中是否包含问题的解，中是否包含问题的解，若有则求解结束，成功退出；否则执行

14、若有则求解结束，成功退出；否则执行下一步；下一步；2021/6/1618正向推理正向推理根据数据库DB中的已知事实，扫描知识库KB，检查KB中是否有可适用的知识，若有则转，否则转；把KB中所有的适用知识都选出来，构成可适用的知识集KS；若KS不空，则按某种冲突消解策略从中选出一条知识进行推理，并将推出的新事实加入DB中，然后转；若KS空，转；2021/6/1619正向推理正向推理询问用户是否可以进一步补充新的事实，若可补充，则将补充的事实加入DB中，转，否则表示求不出解，失败退出算法的流程示意图如115的图所示为了实现正向推理，还有很多实际问题需要解决，后面将陆续介绍2021/6/1620逆向

15、推理逆向推理l逆向推理的思想是首先假设一个目标，逆向推理的思想是首先假设一个目标，然后寻找支持该假设的证据，若所需的然后寻找支持该假设的证据，若所需的证据都能找到，则说明假设是成立的；证据都能找到，则说明假设是成立的；若实在找不到证据时，说明原假设不成若实在找不到证据时，说明原假设不成立，此时需另做假设推理过程的算法立，此时需另做假设推理过程的算法如下所示如下所示2021/6/1621逆向推理逆向推理l提出要求证的目标（假设目标）；提出要求证的目标（假设目标）；l检查该目标是否已在数据库中，若在，检查该目标是否已在数据库中，若在，则该目标成立，成功退出或者对下一目则该目标成立，成功退出或者对下

16、一目标进行检验；否则，转下一步；标进行检验；否则，转下一步；l判断该目标是否是证据，即它是否是判断该目标是否是证据，即它是否是由用户证实的原始事实，若是，则询问由用户证实的原始事实，若是，则询问用户；否则转下一步用户；否则转下一步l在知识库中找出所有能导出该目标的在知识库中找出所有能导出该目标的知识，形成适用知识集知识，形成适用知识集KS，转下一步；，转下一步；2021/6/1622逆向推理逆向推理l从从KS中选出一条知识，并将该知识的中选出一条知识，并将该知识的运用条件作为新的假设目标，然后转运用条件作为新的假设目标，然后转l算法的示意图如算法的示意图如116的图所示的图所示l2021/6/

17、1623双向推理双向推理l混合推理就是在推理过程中合理地使用正混合推理就是在推理过程中合理地使用正向推理和逆向推理向推理和逆向推理l混合推理的算法示意图如混合推理的算法示意图如P11的图的图所示所示l2021/6/1624求解策略和限制策略求解策略和限制策略 所谓推理的求解策略是指只求一个解还是求所所谓推理的求解策略是指只求一个解还是求所有解和最优解等有解和最优解等为了防止无穷的推理过程为了防止无穷的推理过程, ,以及由于推理过程太以及由于推理过程太长增加时间及空间的复杂性，可在控制策略中长增加时间及空间的复杂性，可在控制策略中指定推理的限制条件，以对推理的深度、宽度、指定推理的限制条件，以对

18、推理的深度、宽度、时间、空间等限制。时间、空间等限制。 2021/6/1625模式匹配模式匹配l模式匹配是推理中必须进行的一项重要工作，模式匹配是推理中必须进行的一项重要工作，因为只有经过模式匹配才能从知识库中选出当因为只有经过模式匹配才能从知识库中选出当前适用的知识，才能进行推理。前适用的知识，才能进行推理。l模式匹配可以有确定性匹配和不确定性匹配良模式匹配可以有确定性匹配和不确定性匹配良种。种。l所谓确定性匹配是指两个模式完全一样，或者所谓确定性匹配是指两个模式完全一样，或者通过代换后变得完全一致。所谓不确定性匹配通过代换后变得完全一致。所谓不确定性匹配是指两个知识模式不完全一样，但从总体

19、上看是指两个知识模式不完全一样，但从总体上看它们的相似程度又落在规定的限度内。它们的相似程度又落在规定的限度内。l无论是确定性匹配无论是确定性匹配 还是不确定性匹配都需要进还是不确定性匹配都需要进行变量的代换。行变量的代换。2021/6/1626模式匹配模式匹配l例如设有如下两个知识模式：例如设有如下两个知识模式：l1:father(李四，李小四）李四，李小四）and man(李小李小四四)l2:father(x,y)and man (y)l若用李四代换若用李四代换x,用李小四代换用李小四代换y，则，则1与与l就变得完全一样若用这两个知识模就变得完全一样若用这两个知识模式进行匹配，则是确定性匹

20、配，也称完式进行匹配，则是确定性匹配，也称完全匹配或精确匹配全匹配或精确匹配2021/6/1627模式匹配模式匹配l下面我们给出代换的概念：下面我们给出代换的概念：l代换是形如代换是形如lt1/x1,t2/x2,tn/xn的有限集合。其中，的有限集合。其中，l t1， t2， ,tn是项，是项，lx1. ，x2, xn是互不相同的变元；是互不相同的变元；lti/xi表示用项表示用项ti代换变量代换变量xi，不允许，不允许ti 和和xi相同，也不允许相同，也不允许xi循环的出现在另一个循环的出现在另一个tj中。中。2021/6/1628模式匹配模式匹配什麽是项呢？什麽是项呢？常可以作项，变量也可

21、以作项，函数常可以作项，变量也可以作项，函数表达式可以作项。表达式可以作项。2021/6/1629模式匹配模式匹配l例如例如a/x,f(b)/y,w/z就是一个代换，但是就是一个代换，但是lg(y)/x,f(x)/y则不是一个代换，因为代换则不是一个代换，因为代换的目的是使某些变元被另外的变元、常的目的是使某些变元被另外的变元、常量、或函数表达式取代，使之不再在公量、或函数表达式取代，使之不再在公式中出现，而式中出现，而g(y)/x,f(x)/y在在x与与y之间出之间出现了循环代换的情况，它既没有消去现了循环代换的情况，它既没有消去x,也也没有消去没有消去y。2021/6/1630模式匹配模式

22、匹配l如果把它改为如果把它改为g(a)/x,f(x)/y就可就可以了，它将把公式中的以了，它将把公式中的x代换成代换成g(a),y代换成代换成f(g(a),从而消去了从而消去了变量变量x和和y。 2021/6/1631模式匹配模式匹配l下面给出一个公式的代换例式的概念：下面给出一个公式的代换例式的概念：l设设F是一个公式，是一个公式， 是一个代换，记是一个代换，记F 为为公式公式F在在 下的代换例式，它是将公式下的代换例式，它是将公式F中中的变量用的变量用 中的项作代换的结果。例如有中的项作代换的结果。例如有公式（公式（x,y,f(y)和代换和代换 =a/x,b/yl于是于是F =（a,b,f

23、(b)2021/6/1632模式匹配模式匹配l下面给出复合代换的定义下面给出复合代换的定义l设有两个代换设有两个代换 和和 ，其中，其中l = t1/x1,t2/x2,tn/xnl = u1/y1,u2/y2,um/ym则则 此两个代换的复合此两个代换的复合也是一个代换，它是从也是一个代换，它是从 lt1 /x1,t2 /x2,tn /xn， u1/y1,u2/y2,um/yml中删去如下两种元素：中删去如下两种元素：lti /xi 当当ti = xi 时时lui/yi 当当yi x1. ，x2, xn时，后剩下的元素时，后剩下的元素构成的集合，记为构成的集合，记为 。2021/6/1633模

24、式匹配模式匹配l例如设有如下代换：例如设有如下代换：l =f(y)/x,z/yl =a/x,b/y,y/zl求求 和和 l解：我们先来求解：我们先来求 2021/6/1634模式匹配模式匹配l =f(y) /x, z /y, a/x,b/y,y/zl=f(b) /x, y /y, a/x,b/y,y/z去掉不合法的元去掉不合法的元素：素：ly /y（条件）（条件）l a/x,b/y（条件）（条件）l于是于是 f(b) /x,y/z2021/6/1635模式匹配模式匹配l再来求再来求 ，同样先求，同样先求 l a /x, b /y, y /z, f(y)/x,z/yl =a /x, b /y,z

25、/z, f(y)/x,z/yl去掉不合法的元素去掉不合法的元素z/z,f(y)/x,z/y得得l =a /x, b /yl显然代换的复合运算是不可交换的。并显然代换的复合运算是不可交换的。并且对任何代换且对任何代换 存在空代换存在空代换 ，并且，并且l 2021/6/1636模式匹配模式匹配l下面我们给出合一的概念：下面我们给出合一的概念：l设有公式集设有公式集F=F1，F2，,Fn,若存在一若存在一个代换个代换 使得使得F1 = F2 = Fn l则称则称 为公式集为公式集F的一个合一，且称的一个合一，且称lF1，F2，,Fn是可合一的。是可合一的。2021/6/1637模式匹配模式匹配l例

26、如例如F=P（x,y), =a/x,g(a)/yl求公式求公式F在在 下的例式为下的例式为lF = P（a,g(a)l对于公式集对于公式集F=P（x,y，f(y),P(a,g(x),z)则则l =a/x,g(a)/y，f(g(a)/z是公式是公式F的一个的一个合一。合一。2021/6/1638模式匹配模式匹配l一个公式的合一一般是不唯一的。但如一个公式的合一一般是不唯一的。但如果果l 是公式集是公式集F的一个合一，若对任一个合的一个合一，若对任一个合一一 都存在一个代换都存在一个代换 使得：使得： = 则称则称 是一个最一般合一。是一个最一般合一。2021/6/1639模式匹配模式匹配l最一般

27、合一是唯一的。若用最一般合一最一般合一是唯一的。若用最一般合一去代换那些可合一的谓词公式，可使它去代换那些可合一的谓词公式，可使它们变成完全一致的公式。由此可知，为们变成完全一致的公式。由此可知，为了使两个知识模式匹配，可用其最一般了使两个知识模式匹配，可用其最一般合一对它们进行代换。合一对它们进行代换。2021/6/1640模式匹配模式匹配l为了求最一般合一要用到一个差异集为了求最一般合一要用到一个差异集（也有叫分歧集的）的概念。设有如下（也有叫分歧集的）的概念。设有如下两个谓词公式两个谓词公式lF1：P(x,y,z)lF2: P(x,f(a),h(b)l分别从分别从F1 与与F2的第一个符

28、号开始，逐个的第一个符号开始，逐个向右比较，此时发现向右比较，此时发现F1中的中的y与与F2中的中的f(a)不同，它们构成了一个差异集：不同，它们构成了一个差异集：D1=y,f(a),2021/6/1641模式匹配模式匹配l当继续向右比较时，又发现当继续向右比较时，又发现F1中与中与F2中中的的h(b)不同，于是又得到一个差异集：不同，于是又得到一个差异集：lD2=z,h(b)。下面给出求最一般合一的。下面给出求最一般合一的算法：算法：l（1）令）令K=0， Fk=F, k= 这里，这里，F是欲求是欲求其最一般合一的公式集，其最一般合一的公式集， 是空代换，它是空代换，它表示不做代换。表示不做

29、代换。l（2）若）若Fk只含一个表达式，则算法停，只含一个表达式，则算法停， k就是所求最一般合一。就是所求最一般合一。2021/6/1642模式匹配模式匹配l（3）找出）找出Fk的差异集的差异集Dk。l（4）若）若Dk中存在元素中存在元素xk和和tk,其中其中xk是变是变元，元，tk是项是项,且且xk不在不在tk中出现，则置：中出现，则置：l k+1= ktk/ xklFk+1= Fktk/ xklK = k + 1转（转（2）l（5）算法停，）算法停，F的最一般合一不存在。的最一般合一不存在。2021/6/1643模式匹配模式匹配l例如，设例如，设lF = P(a,x,f(g(y),P(z

30、,f(z),f(u)求其最一求其最一般合一般合一l(1)令令 0= , F0=F,因因F0中含有两个表达式，中含有两个表达式，所以所以 0不是最一般合一。不是最一般合一。l(2)差异集差异集D0= a,z,l(3) 1= 0 a/z,lF1 = P(a,x,f(g(y),P(a,f(a),f(u)2021/6/1644模式匹配模式匹配(4) D1=x,f(a)(5) 2= 1 f(a)/x=a/z, f(a)/x,lF2=F1 f(a)/xl= P(a, f(a),f(g(y),P(a,f(a),f(u)。l(6) D2=g(y),u。l(7) 3= 2 g(y)/u=a/z, f(a)/x,

31、 g(y)/u。2021/6/1645模式匹配模式匹配l(8) F3=F2 g(y)/ul = P(a, f(a),f(g(y),P(a,f(a),f(g(y)/u)l = P(a, f(a),f(g(y)l因为因为F3只含一个表达式了，所以只含一个表达式了，所以 3就是就是最一般合一，即最一般合一，即la/z, f(a)/x, g(y)/u是最一般合一。是最一般合一。2021/6/1646冲突消解策略冲突消解策略l接下来我们学习冲突消解方面的概念：接下来我们学习冲突消解方面的概念：l在推理的过程中，系统不断的用以知的在推理的过程中，系统不断的用以知的事实与知识库中的知识进行匹配，此时事实与知

32、识库中的知识进行匹配，此时可能发生如下三种情况：可能发生如下三种情况：l（1）已知事实不能与知识库中的任何知）已知事实不能与知识库中的任何知识匹配成功。识匹配成功。l（2）已知事实恰好与知识库中的一条知）已知事实恰好与知识库中的一条知识匹配成功。识匹配成功。2021/6/1647冲突消解策略冲突消解策略l（3）已知事实可与知识库中的多条知识）已知事实可与知识库中的多条知识匹配成功。匹配成功。l以上三种情况中，第一种情况使得推理以上三种情况中，第一种情况使得推理无法进行下去，第三种情况则出现冲突，无法进行下去，第三种情况则出现冲突，需要按一定的策略解决冲突。需要按一定的策略解决冲突。 2021/

33、6/1648冲突消解策略冲突消解策略l目前解决冲突的策略有多种，其基本思目前解决冲突的策略有多种，其基本思想都是对知识进行排序，常用的有以下想都是对知识进行排序，常用的有以下几种：几种：l1、按针对性排序、按针对性排序l设有如下两条产生式规则：设有如下两条产生式规则：lr1:IF A1 and A2 and An THEN H1lr2:IF B1 and B2 and Bm THEN H22021/6/1649冲突消解策略冲突消解策略l如果存在最一般合一，使得如果存在最一般合一，使得r1中每一个中每一个Ai都可变成相应的都可变成相应的Bi ，即，即r2中除了包含中除了包含r1的的全部条件全部条

34、件A1,A2, , An外，还包含其它条外，还包含其它条件，则称件，则称r2 比比 r1有更大的针对性，有更大的针对性， r1 比比r2 有更大的通用性。有更大的通用性。l一般选用针对性较强的产生式规则。一般选用针对性较强的产生式规则。(即即应选用应选用r2)因为它要求的条件较多，其结因为它要求的条件较多，其结论一般更论一般更 接近目标，一旦得到满足，可接近目标，一旦得到满足，可缩短推理过程。缩短推理过程。2021/6/1650冲突消解策略冲突消解策略l2、按已知事实的新鲜性排序、按已知事实的新鲜性排序l在产生式系统推理过程中，每应用一条在产生式系统推理过程中，每应用一条产生式规则就会得到一个

35、或多个结论，产生式规则就会得到一个或多个结论，数据库就会增加新的事实。把数据库后数据库就会增加新的事实。把数据库后生成的事实称为生成的事实称为 新鲜的事实，即后生成新鲜的事实，即后生成的事实比先生成的事实具有较大的新鲜的事实比先生成的事实具有较大的新鲜性。设规则性。设规则r1可与事实组可与事实组A匹配成功，规匹配成功，规则则r2可与事实组可与事实组B匹配成功，则匹配成功，则A与与B中中哪一组新鲜与它匹配的产生式规则就先哪一组新鲜与它匹配的产生式规则就先被应用。被应用。2021/6/1651冲突消解策略冲突消解策略l3、按匹配排序、按匹配排序l在不确定性匹配中，为了确定两个知识在不确定性匹配中，

36、为了确定两个知识模式是否可以匹配，需要计算这两个模模式是否可以匹配，需要计算这两个模式的相似程度，当其相似程度达到某个式的相似程度，当其相似程度达到某个预定的值时，就认为它们是可匹配的。预定的值时，就认为它们是可匹配的。若两条规则均按匹配度匹配成功，则匹若两条规则均按匹配度匹配成功，则匹配度大的那条规则优先启用。配度大的那条规则优先启用。2021/6/1652冲突消解策略冲突消解策略l4、根据领域问题的特点排序、根据领域问题的特点排序l某些领域问题可事先知道它的某些特性，某些领域问题可事先知道它的某些特性，可根据这些特性把知识排成固定的顺序。可根据这些特性把知识排成固定的顺序。先匹配成功的优先

37、启用的原则。先匹配成功的优先启用的原则。2021/6/1653冲突消解策略冲突消解策略l5、按上下文限制排序、按上下文限制排序l把产生式规则按它们所描述的上下文分把产生式规则按它们所描述的上下文分成若干组，在不同的条件下，只能从相成若干组，在不同的条件下，只能从相应的组中选取有关的产生式规则。这样应的组中选取有关的产生式规则。这样可以减少冲突的发生可以减少冲突的发生2021/6/1654冲突消解策略冲突消解策略l6、按冗余限制排序、按冗余限制排序l若哪一条产生式规则被应用后产生冗余若哪一条产生式规则被应用后产生冗余知识，则就降低它被应用的优先级。知识，则就降低它被应用的优先级。l7、按条件个数

38、排序、按条件个数排序l如果有多条产生式规则生成的结论相同，如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用。则要求条件少的产生式规则被优先应用。2021/6/1655 4.2自然演绎推理自然演绎推理l从一组已知的事实出发，直接运用经典从一组已知的事实出发，直接运用经典逻辑推理规则推出结论的过程称为自然逻辑推理规则推出结论的过程称为自然演绎推理。其中，基本的推理规则是演绎推理。其中，基本的推理规则是P规规则、则、T规则、假言推理、拒取式推理等。规则、假言推理、拒取式推理等。假言推理的一般形式是假言推理的一般形式是lP，PQ Ql拒取式的一般形式是拒取式的一般形式是lPQ，

39、Q P2021/6/16564.2自然演绎推理自然演绎推理l以下是自然演绎推理的例子：以下是自然演绎推理的例子：l例例1：A，B，AC，B C D，D QlQl1、A P规则规则l2、 AC P规则规则l3、 C T规则规则1和和2l4、B P规则规则l5、 B C T规则规则3和和42021/6/16574.2自然演绎推理自然演绎推理 6、 B C D P规则规则l7、 D T规则规则5和和6l8、D Q P规则规则l9、 Q T规则规则7和和8l问题得证问题得证2021/6/16584.2自然演绎推理自然演绎推理l例例2设已知如下事实；设已知如下事实；l（1）凡是容易的课程小王（）凡是容易

40、的课程小王（Wang)都喜都喜欢。欢。l（2）C班的课程都是容易的。班的课程都是容易的。l（3）ds是是C班的一门课程班的一门课程l求证小王喜欢求证小王喜欢ds这门课程。这门课程。2021/6/16594.2自然演绎推理自然演绎推理l证明：首先定义谓词如下：证明：首先定义谓词如下：lEasy（x): x是容易的是容易的lLike（x,y): x喜欢喜欢ylC（x): x是是C班的一门课程班的一门课程l于是问题可以表示成：于是问题可以表示成：2021/6/16604.2自然演绎推理自然演绎推理l x(Easy(x) Like(Wang,x) l x(C(x) Easy(x) lC(ds) Lik

41、e（Wang,ds).2021/6/16614.2自然演绎推理自然演绎推理l1、 x(Easy（x) Like（Wang,x) P规则规则l2、 Easy（ds) Like（Wang,ds) US规则和规则和1l3、 x(C（x) Easy（x) P规则规则l4、 C（ds) Easy（ds) US规则和规则和3l5、 C（ds) Like（Wang,ds) T规则规则2和和4l6、 C（ds) P规则规则l7、 Like（Wang,ds) T规则规则5和和6l即小王喜欢即小王喜欢ds这门课程这门课程2021/6/16624.2自然演绎推理自然演绎推理l自然演绎推理的优点是表达定理证明过自然演

42、绎推理的优点是表达定理证明过程自然，容易理解，拥有丰富的推理规程自然，容易理解，拥有丰富的推理规则，推理过程灵活，便于在推理过程中则，推理过程灵活，便于在推理过程中嵌入领域启发知识。缺点是容易产生组嵌入领域启发知识。缺点是容易产生组合爆炸，推理过程中得到的中间结论一合爆炸，推理过程中得到的中间结论一般呈指数形式递增，这对于一个大型推般呈指数形式递增，这对于一个大型推理问题是十分不利的，甚至是不可能实理问题是十分不利的，甚至是不可能实现的。现的。2021/6/16634.3归结演绎推理归结演绎推理l定理证明是人工智能的一个重要研究领域，这定理证明是人工智能的一个重要研究领域，这不仅仅是因为许多数

43、学问题要通过定理证明得不仅仅是因为许多数学问题要通过定理证明得以解决，很多非数学问题（如医疗诊断、机器以解决，很多非数学问题（如医疗诊断、机器人规划及难题求解等）也都归结为一个定理证人规划及难题求解等）也都归结为一个定理证明问题。定理证明的实质是对前提明问题。定理证明的实质是对前提P和结论和结论Q证明证明P Q的永真性。但是证明一个谓词公式的永真性。但是证明一个谓词公式的永真性不像证明一个命题公式的永真性那麽的永真性不像证明一个命题公式的永真性那麽简单，（它牵涉到谓词变量、客体变量及函数简单，（它牵涉到谓词变量、客体变量及函数符号）在某些情况下甚至是行不通的。符号）在某些情况下甚至是行不通的。

44、2021/6/16644.3归结演绎推理归结演绎推理l在这种情况下，人们提出了用反证法来在这种情况下，人们提出了用反证法来解决问题的思路。在这方面，海伯伦和解决问题的思路。在这方面，海伯伦和鲁宾逊都作出了杰出的贡献。鲁宾逊都作出了杰出的贡献。l两人的研究都是以子句集为背景展开的。两人的研究都是以子句集为背景展开的。接下来，我们介绍这些概念。接下来，我们介绍这些概念。2021/6/16654.3归结演绎推理归结演绎推理l子句：在谓词逻辑中，称原子谓词公式子句：在谓词逻辑中，称原子谓词公式及其否定为文字；任何文字的析取式为及其否定为文字；任何文字的析取式为子句。子句。l例如，例如，P(x) Q(x

45、), P(x,f(x) Q(x,g(x)都是子句。而都是子句。而P(x) 、 Q(x,g(x)、 P(x,f(x)等都是文字。并把不包含任何等都是文字。并把不包含任何文字的子句称为空子句。文字的子句称为空子句。2021/6/16664.3归结演绎推理归结演绎推理l由于空子句不包含任何文字，它不能被由于空子句不包含任何文字，它不能被任何解释所满足，所以空子句是永假的，任何解释所满足，所以空子句是永假的，不可满足的。不可满足的。l由子句构成的集合称为子句集。在谓词由子句构成的集合称为子句集。在谓词逻辑中任何一个谓词公式均可通过等价逻辑中任何一个谓词公式均可通过等价变换化为相应的子句集。变换化为相应

46、的子句集。2021/6/16674.3归结演绎推理归结演绎推理l化子句集的步骤如下：化子句集的步骤如下：l1、利用等价公式消去公式中的逻辑连接、利用等价公式消去公式中的逻辑连接词词“”l和和“”：lP QP QlP Q （P Q） （ P Q）2021/6/16684.3归结演绎推理归结演绎推理l2、利用下列公式将否定符号、利用下列公式将否定符号“ ”深入到深入到单个变元前单个变元前l P Pl （P Q） P Ql （P Q） P Ql ( x)P ( x) Pl ( x)P ( x) P2021/6/16694.3归结演绎推理归结演绎推理l3、重新命名变元名，使不同量词约束的变元、重新命名

47、变元名，使不同量词约束的变元有不同的名字有不同的名字 l4、消去存在量词。分两种情况处理：一种情、消去存在量词。分两种情况处理：一种情况是存在量词不出现在全称量词的辖域内，此况是存在量词不出现在全称量词的辖域内，此时只要用一个新的个体常量替换受该存在量词时只要用一个新的个体常量替换受该存在量词约束的变元就可消去存在量词；另一种情况是约束的变元就可消去存在量词；另一种情况是存在量词位于一个或多个全称量词的辖域内，存在量词位于一个或多个全称量词的辖域内，例如例如l（ x1) （ x2)( xn)( y)P(x1,x2,xn,y)l此时需要用此时需要用Skolem函数函数f(x1,x2,xn)替换受

48、该替换受该存在量词约束的变元，然后才能消去存在量词。存在量词约束的变元，然后才能消去存在量词。2021/6/16704.3归结演绎推理归结演绎推理l5、把全称量词全部移到公式的左边。、把全称量词全部移到公式的左边。l6、利用等价关系、利用等价关系lP (Q R) =( P Q) ( P R)把公式化为把公式化为 Skolem标准型。标准型。2021/6/1671 4.3归结演绎推理归结演绎推理lSkolem标准型的一般形式是：标准型的一般形式是：l（ x1) （ x2)( xn)Ml其中，其中，M是子句的合取式，称为是子句的合取式，称为Skolem标准型的母式。标准型的母式。l7、消去全称量词

49、、消去全称量词l8、对变元更名，使不同子句中的变元不、对变元更名，使不同子句中的变元不同名。同名。2021/6/16724.3归结演绎推理归结演绎推理l9、消去合取连接词，变为子句集。子句、消去合取连接词，变为子句集。子句集中各子句之间是合取关系。谓词公式集中各子句之间是合取关系。谓词公式是不可满足的，则其子句集合是不可满是不可满足的，则其子句集合是不可满足的，反之亦然。足的，反之亦然。 2021/6/1673 海伯伦理论海伯伦理论l如何证明一个子句集是不可满足的呢？如何证明一个子句集是不可满足的呢？下面就海伯伦理论和鲁宾逊的归结原理下面就海伯伦理论和鲁宾逊的归结原理进行讨论。进行讨论。l一、

50、海伯伦理论一、海伯伦理论l要判定一个子句集是否是不可满足的，要判定一个子句集是否是不可满足的，需要对子句集中的谓词公式进行判定，需要对子句集中的谓词公式进行判定，而谓词公式的判定需要对个体域上的任而谓词公式的判定需要对个体域上的任何解释进行判定，这是很困难的。何解释进行判定，这是很困难的。2021/6/1674 海伯伦理论海伯伦理论l海伯伦定义了一个特殊的域称为海伯伦海伯伦定义了一个特殊的域称为海伯伦域，在任何域上的判定，只要在海伯伦域，在任何域上的判定，只要在海伯伦域上域上 进行即可。进行即可。l*设设S是子句集，则按下述方法构造的域是子句集，则按下述方法构造的域H 称为是海伯伦域：称为是海

51、伯伦域：2021/6/1675 海伯伦理论海伯伦理论l1、令、令H0是是S中所有个体常量的集合，若中所有个体常量的集合，若S中不包含个体常量，则令中不包含个体常量，则令H0 =a，其中，其中a为任意指定的一个个体常量。为任意指定的一个个体常量。l2、令、令Hi+1 = Hi S中所有中所有n元函数元函数f(x1,x2,xn) | xj(j=1,2,n)是是Hi中的元中的元素素，其中，其中，li = 0,1,。下面通过例子来解释这个定。下面通过例子来解释这个定义。义。 2021/6/1676海伯伦理论海伯伦理论l例例1求子句集求子句集S=P(x) Q(x),R(f(y)的的H域。域。l解：因为解

52、：因为S中没有个体常量，所以指定中没有个体常量，所以指定a作为个体常量，于是得到：作为个体常量，于是得到：lH0 = a, lH1 = a, f(a),lH2 = a, f(a),f( f(a), lH = a, f(a),f( f(a)， f(f( f(a), llH = a, f(a),f( f(a),2021/6/1677海伯伦理论海伯伦理论l例例2 求子句集求子句集S=P(a),Q(b),R(f(x)的的H域域l解：根据解：根据H域的定义得到：域的定义得到：lH0 =a,blH1=a,b,f(a),f(b)lH2=a,b,f(a),f(b), f(f(a), f(f(b) l2021/

53、6/1678海伯伦理论海伯伦理论l例例3：求子句集：求子句集S=P(x),Q(y) R(y)的的H域。域。l解：由于该子句集中既无个体常量，又无函数，解：由于该子句集中既无个体常量，又无函数，所以可任意指定一个常量所以可任意指定一个常量a作为个体常量，从作为个体常量，从而得到而得到H0 = H1= H = al有定理说：子句集有定理说：子句集S是不可满足的充要条件是是不可满足的充要条件是S对对H域上的一切解释都为假。并且海伯伦证明域上的一切解释都为假。并且海伯伦证明了若子句集了若子句集S在任何域在任何域D上的解释能满足上的解释能满足S，则，则在在H域上相应的解释也能满足域上相应的解释也能满足S

54、。下面我们说。下面我们说明，明，S在在H域上解释的定义：域上解释的定义：2021/6/1679海伯伦理论海伯伦理论l子句集子句集S在在H域上的一个解释满足下列域上的一个解释满足下列条件：条件：l1、在解释、在解释I下，常量映射到自身；下，常量映射到自身；l2、S中的任一个中的任一个n元函数是元函数是HnH的映的映射。即，设射。即，设h1,h2,hn H,则则f(h1,h2,hn) H;2021/6/1680海伯伦理论海伯伦理论l3、S中的任一中的任一n元谓词是元谓词是HnT，F的的映射。即谓词的真值可以指派映射。即谓词的真值可以指派T也可指派也可指派F。l海伯伦在理论上证明了子句集不可满足海伯

55、伦在理论上证明了子句集不可满足性的可行性及方法，但要在计算机上实性的可行性及方法，但要在计算机上实现其证明过程还是很困难的。现其证明过程还是很困难的。1965年鲁年鲁宾逊提出了归结原理，使机器证明成为宾逊提出了归结原理，使机器证明成为现实现实2021/6/1681鲁宾逊归结原理鲁宾逊归结原理l归结原理也称消解原理，是鲁宾逊提出的一种归结原理也称消解原理，是鲁宾逊提出的一种证明子句不可满足性，从而实现定理证明的一证明子句不可满足性，从而实现定理证明的一种理论及方法。种理论及方法。l由谓词公式转化为子句集的过程可以看出，在由谓词公式转化为子句集的过程可以看出，在子句集中子句之间的关系是合取关系，其

56、中只子句集中子句之间的关系是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。要有一个子句不可满足，则子句集就不可满足。前面，我们曾经说过空子句是不可满足的，即前面，我们曾经说过空子句是不可满足的，即一个子句集中若含空子句，则它是不可满足的。一个子句集中若含空子句，则它是不可满足的。2021/6/1682鲁宾逊归结原理鲁宾逊归结原理l归结原理的基本思想就是检查子句集中归结原理的基本思想就是检查子句集中是否含空子句，若含，则子句集是否含空子句，若含，则子句集S不可满不可满足，或说证明一个谓词公式是永假的过足，或说证明一个谓词公式是永假的过程，就是归结由此公式转换成的子句集程，就是归结由此

57、公式转换成的子句集包含空子句的过程。包含空子句的过程。2021/6/1683鲁宾逊归结原理鲁宾逊归结原理l下面我们先来说明命题逻辑中的归结原下面我们先来说明命题逻辑中的归结原理理l定义定义P是原子谓词公式，则称是原子谓词公式，则称P与与 P为互为互补文字。我们知道在命题逻辑中有公式：补文字。我们知道在命题逻辑中有公式：lPQ,Q R P R即即l P Q， Q R P R l c1 c2 c122021/6/1684鲁宾逊归结原理鲁宾逊归结原理l显然上述公式向我们展示的是在子句显然上述公式向我们展示的是在子句c1 中存在文字中存在文字Q，在子句，在子句c2中存在中存在Q的补文的补文字字 Q，把

58、这一对互补文字消去，剩下的，把这一对互补文字消去，剩下的文字析取起来就是子句文字析取起来就是子句 c1 和和c2的逻辑结的逻辑结果果c12。并称。并称c12是是c1 和和c2的归结式，的归结式， c1 和和c2则称为则称为c12的亲本子句。的亲本子句。2021/6/1685鲁宾逊归结原理鲁宾逊归结原理l例如：例如：l1、C1= P Q Rl C2= Q Sl它们的归结式它们的归结式c12为为 P R Sl2、C1= Pl C2=Pl它们的归结式它们的归结式c12为为NIL即空子句。即空子句。2021/6/1686鲁宾逊归结原理鲁宾逊归结原理l3、C1= P Q l C2= Q Rl C3=Pl

59、它们的归结式它们的归结式c123为为R。其归结过程可以。其归结过程可以用下面的一个树形结构很清楚的表现出用下面的一个树形结构很清楚的表现出来。来。2021/6/1687鲁宾逊归结原理鲁宾逊归结原理 l P Q Q Rl P R Pl Rl 归结过程的树形表示图归结过程的树形表示图 2021/6/1688鲁宾逊归结原理鲁宾逊归结原理l由命题逻辑中的归结原理可以得出如下由命题逻辑中的归结原理可以得出如下的推论：的推论：l设设c1与与c2是子句集是子句集S中的两个子句，中的两个子句，c12是是它们的归结式它们的归结式,若用若用c12代替代替c1和和c2后得到后得到新子句集新子句集S1，则由，则由S1

60、的不可满足性可以的不可满足性可以推出推出S的不可满足性。这个定理告诉我们，的不可满足性。这个定理告诉我们，证明子句集证明子句集S的不可的不可 满足性问题，可以满足性问题，可以转化成证子句集转化成证子句集S1的不可满足性问，的不可满足性问，直到从子句集直到从子句集Sn 中推出一个空子句来。中推出一个空子句来。2021/6/1689鲁宾逊归结原理鲁宾逊归结原理l在谓词逻辑中，由于子句中含有变元，在谓词逻辑中，由于子句中含有变元，所以不象命题逻辑中那样可以直接消去所以不象命题逻辑中那样可以直接消去互补文字，而先要用最一般合一对变元互补文字，而先要用最一般合一对变元进行代换。然后才能进行归结。前面我进