第章经典逻辑推理第章经典逻辑推理、基本概念、基本概念、自然演绎推理、自然演绎推理、归结演绎推理、归结演绎推理、与或形演绎推理、与或形演绎推理2021/8/21基本概念基本概念l何为推理？何为推理？l从已知的事实出发，不断运用已掌握的从已知的事实出发，不断运用已掌握的（知识库中的）知识推出或归纳出新的（知识库中的）知识推出或归纳出新的事实（包括目标结论）的过程称为推理。事实（包括目标结论）的过程称为推理。人工智能中推理是由程序实现的，称这人工智能中推理是由程序实现的，称这个程序为推理机。个程序为推理机。2021/8/22推理方式及其分类推理方式及其分类l人工智能作为对人类智能的模拟，有多人工智能作为对人类智能的模拟，有多种推理方式。它们是：种推理方式。它们是：l、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l、确定性推理、不确定性推理、确定性推理、不确定性推理l、单调推理、非单调推理、单调推理、非单调推理l、启发式推理、非启发式推理、启发式推理、非启发式推理l、基于知识的推理、统计推理、直觉、基于知识的推理、统计推理、直觉推理。推理。l分别解释如下：分别解释如下：2021/8/23、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l所谓演绎推理是从全称判断推导出特称所谓演绎推理是从全称判断推导出特称判断的过程，是从一般到个别的推理。判断的过程，是从一般到个别的推理。经常用的是三段论式，它包括：经常用的是三段论式，它包括： 大前提：已知的一般性知识或假设；大前提：已知的一般性知识或假设；小前提：具体情况或个别事实；小前提：具体情况或个别事实；结论：由大前提推出的适合小前提所示情结论：由大前提推出的适合小前提所示情况的新判断。况的新判断。2021/8/24、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l例如有如下三个判断：例如有如下三个判断：l（）足球运动员的身体都是强壮的；（）足球运动员的身体都是强壮的；l（）高波是一名足球运动员；（）高波是一名足球运动员；l（）所以，高波的身体是强壮的。（）所以，高波的身体是强壮的。l其中（）是大前提，（）是小前提其中（）是大前提，（）是小前提l（）是经演绎推出的结论。（）是经演绎推出的结论。l只要大前提和小前提是正确的，那麽由只要大前提和小前提是正确的，那麽由它们推出的结论就是正确的。它们推出的结论就是正确的。2021/8/25、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l演绎推理是人工智能中的一种重要推理演绎推理是人工智能中的一种重要推理方式，目前研制成功的各类智能系统中，方式，目前研制成功的各类智能系统中，大多是用演绎推理实现的。大多是用演绎推理实现的。2021/8/26、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l归纳推理是从足够多的事例中归纳出一归纳推理是从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到般性结论的推理过程，是一种从个别到一般的推理。例如，某厂进行产品质量一般的推理。例如，某厂进行产品质量检查，如果对每一件产品都进行了检查，检查，如果对每一件产品都进行了检查，并且都是合格的，则推导出结论：该厂并且都是合格的，则推导出结论：该厂生产的产品是合格的。并称这种推理为生产的产品是合格的。并称这种推理为完全归纳推理。完全归纳推理。2021/8/27、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理如果是随机地抽查部分产品，并且它们如果是随机地抽查部分产品，并且它们是合格的，则得出结论该厂的产品是是合格的，则得出结论该厂的产品是合格的，这种推理称为不完全归纳推合格的，这种推理称为不完全归纳推理。理。默认推理又称为缺省推理，它是在知识默认推理又称为缺省推理，它是在知识不完全的情况下假设某些条件已经具不完全的情况下假设某些条件已经具备所进行的推理。例如，在条件已备所进行的推理。例如，在条件已成立的情况下，如果没有足够的证据成立的情况下，如果没有足够的证据能证明条件不成立，则默认成立，能证明条件不成立，则默认成立，并在默认前提下进行推理，推导并在默认前提下进行推理，推导2021/8/28、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理 出出某某个个结结论论来来。由由于于这这种种推推理理允允许许默默认认某某些些条条件件是是成成立立的的，这这就就摆摆脱脱了了需需要要知知道道全全部部有有关关事事实实才才能能进进行行推推理理的的要要求求，使使得得在在知知识识不不完完全全的的情情况况下下也也能能进进行行推推理理。在在默默认认推推理理过过程程中中，如如果果到到某某一一时时刻刻发发现现原原先先所所做做的的默默认认不不正正确确，则则可可以以撤撤消消默默认认推推理理和和所所推推出出的的结结论论，并重新按新情况进行推理。并重新按新情况进行推理。 2021/8/29、确定性推理、不确定性推理、确定性推理、不确定性推理l所谓确定性推理是指推理时所用的所谓确定性推理是指推理时所用的知识都是精确的，推出的结论也是知识都是精确的，推出的结论也是确定的，是真或者是假。经典逻辑确定的，是真或者是假。经典逻辑推理就属于这一种。推理就属于这一种。l不确定性推理是指推理时所用的知不确定性推理是指推理时所用的知识不都是精确的，推出的结论也不识不都是精确的，推出的结论也不完全是肯定的，其真值位于真与假完全是肯定的，其真值位于真与假之间，命题的外延模糊不清。之间，命题的外延模糊不清。2021/8/210、确定性推理、不确定性推理、确定性推理、不确定性推理 这这里里，我我们们特特别别强强调调的的是是不不确确定定性性推推理理。因因为为，人人类类思思维维活活动动的的特特征征经经常常是是在在知知识识不不完完全全的的情情况况下下进进行行多多方方位位的的思思考考及及推推理理的的。因因此此，要要使使计计算算机机模模拟拟人人类类的的思思维维活活动动，就就必必须须使使它它具具有有不确定性推理的能力。不确定性推理的能力。2021/8/211、单调推理、非单调推理、单调推理、非单调推理l所谓单调推理是指在推理的过程中随着所谓单调推理是指在推理的过程中随着推理的向前推进及新知识的加入，推出推理的向前推进及新知识的加入，推出的结论是单调递增的趋势，并且越来越的结论是单调递增的趋势，并且越来越接近目标，推理过程不会出现反复的情接近目标，推理过程不会出现反复的情况，即不会因新知识的加入否定了前面况，即不会因新知识的加入否定了前面推出的结论，从而使推理又退回到前面推出的结论，从而使推理又退回到前面的某一步。经典逻辑演绎推理属于这一的某一步。经典逻辑演绎推理属于这一种。种。2021/8/212、启发式推理、非启发式推理、启发式推理、非启发式推理l若按推理中是否使用与问题有关的启发若按推理中是否使用与问题有关的启发性知识，推理可分为启发式推理和非启性知识，推理可分为启发式推理和非启发式推理。发式推理。l所谓启发性知识是指与问题有关并且能所谓启发性知识是指与问题有关并且能加快推理进程、求得问题最优解的知识。加快推理进程、求得问题最优解的知识。2021/8/213、基于知识的推理、统计推理、直觉推、基于知识的推理、统计推理、直觉推理理l如果从方法论的角度来划分，推理可分如果从方法论的角度来划分，推理可分为基于知识的推理、统计推理和直觉推为基于知识的推理、统计推理和直觉推理。理。l顾名思义，所谓基于知识的推理就是根顾名思义，所谓基于知识的推理就是根据已掌握的事实，通过运用知识进行推据已掌握的事实，通过运用知识进行推理。理。l统计推理是根据对某事物的数据统计进统计推理是根据对某事物的数据统计进行推理。例如，对农作物的产量进行统行推理。例如，对农作物的产量进行统计，从而得出是否增产的结论，从而找计，从而得出是否增产的结论，从而找2021/8/214、基于知识的推理、统计推理、直觉推理、基于知识的推理、统计推理、直觉推理l出出增增产产和和减减产产的的原原因因。就就是是运运用用了了统统计计推理。推理。l直直觉觉推推理理又又称称常常识识性性推推理理，是是根根据据常常识识进进行行的的推推理理。例例如如，当当你你从从某某建建筑筑物物下下走走过过时时，猛猛然然发发现现有有一一物物体体坠坠落落，这这时时你你立立即即就就会会意意识识到到这这有有危危险险，并并立立即即躲躲开开，这这就就是是使使用用了了直直觉觉推推理理。目目前前直直觉觉推推理理在在计计算算机机上上的的实实现现还还是是一一件件很很困困难难的工作。的工作。2021/8/215推理的控制策略推理的控制策略l推理的控制策略主要包括推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。l推理方向用于确定推理的驱动方式，分为正向推理、逆乡向推理、混合推理及双向推理四种。2021/8/216正向推理正向推理l正正向向推推理理也也称称数数据据驱驱动动推推理理，前前向向链链推推理、模式制导推理及前件推理等。理、模式制导推理及前件推理等。l正向推理过程的算法描述如下：正向推理过程的算法描述如下：l、将将用用户户提提供供的的初初始始已已知知事事实实送送入入数数据库据库DB;l2、检检查查数数据据库库DB中中是是否否包包含含问问题题的的解解，若若有有则则求求解解结结束束，成成功功退退出出；否否则则执执行行下一步；下一步；2021/8/217正向推理正向推理根据数据库DB中的已知事实，扫描知识库KB，检查KB中是否有可适用的知识，若有则转，否则转；把KB中所有的适用知识都选出来，构成可适用的知识集KS；若KS不空，则按某种冲突消解策略从中选出一条知识进行推理，并将推出的新事实加入DB中，然后转；若KS空，转；2021/8/218正向推理正向推理询问用户是否可以进一步补充新的事实，若可补充，则将补充的事实加入DB中，转，否则表示求不出解，失败退出算法的流程示意图如115的图所示为了实现正向推理，还有很多实际问题需要解决，后面将陆续介绍2021/8/219逆向推理逆向推理l逆逆向向推推理理的的思思想想是是首首先先假假设设一一个个目目标标，然然后后寻寻找找支支持持该该假假设设的的证证据据，若若所所需需的的证证据据都都能能找找到到，则则说说明明假假设设是是成成立立的的；若若实实在在找找不不到到证证据据时时，说说明明原原假假设设不不成成立立，此此时时需需另另做做假假设设推推理理过过程程的的算算法法如下所示如下所示2021/8/220逆向推理逆向推理l提出要求证的目标（假设目标）；提出要求证的目标（假设目标）；l检查该目标是否已在数据库中，若在，检查该目标是否已在数据库中，若在，则该目标成立，成功退出或者对下一目则该目标成立，成功退出或者对下一目标进行检验；否则，转下一步；标进行检验；否则，转下一步；l判断该目标是否是证据，即它是否是判断该目标是否是证据，即它是否是由用户证实的原始事实，若是，则询问由用户证实的原始事实，若是，则询问用户；否则转下一步用户；否则转下一步l在知识库中找出所有能导出该目标的在知识库中找出所有能导出该目标的知识，形成适用知识集知识，形成适用知识集KS，转下一步；，转下一步；2021/8/221逆向推理逆向推理l从从KS中选出一条知识，并将该知识的中选出一条知识，并将该知识的运用条件作为新的假设目标，然后转运用条件作为新的假设目标，然后转l算法的示意图如算法的示意图如116的图所示的图所示l2021/8/222双向推理双向推理l混合推理就是在推理过程中合理地使用正混合推理就是在推理过程中合理地使用正向推理和逆向推理向推理和逆向推理l混合推理的算法示意图如混合推理的算法示意图如P11的图的图所示所示l2021/8/223求解策略和限制策略求解策略和限制策略 所所谓谓推推理理的的求求解解策策略略是是指指只只求求一一个个解解还还是是求求所所有解和最优解等有解和最优解等为为了了防防止止无无穷穷的的推推理理过过程程, ,以以及及由由于于推推理理过过程程太太长长增增加加时时间间及及空空间间的的复复杂杂性性，可可在在控控制制策策略略中中指指定定推推理理的的限限制制条条件件，以以对对推推理理的的深深度度、宽宽度度、时间、空间等限制。时间、空间等限制。 2021/8/224模式匹配模式匹配l模式匹配是推理中必须进行的一项重要工作，模式匹配是推理中必须进行的一项重要工作，因为只有经过模式匹配才能从知识库中选出当因为只有经过模式匹配才能从知识库中选出当前适用的知识，才能进行推理。前适用的知识，才能进行推理。l模式匹配可以有确定性匹配和不确定性匹配良模式匹配可以有确定性匹配和不确定性匹配良种。种。l所谓确定性匹配是指两个模式完全一样，或者所谓确定性匹配是指两个模式完全一样，或者通过代换后变得完全一致。所谓不确定性匹配通过代换后变得完全一致。所谓不确定性匹配是指两个知识模式不完全一样，但从总体上看是指两个知识模式不完全一样，但从总体上看它们的相似程度又落在规定的限度内。它们的相似程度又落在规定的限度内。l无论是确定性匹配无论是确定性匹配 还是不确定性匹配都需要进还是不确定性匹配都需要进行变量的代换。行变量的代换。2021/8/225模式匹配模式匹配l例如设有如下两个知识模式：例如设有如下两个知识模式：l1:father(李李四四，李李小小四四）and man(李李小小四四)l2:father(x,y)and man (y)l若用李四代换若用李四代换x,用李小四代换用李小四代换y，则，则1与与l就就变变得得完完全全一一样样若若用用这这两两个个知知识识模模式式进进行行匹匹配配，则则是是确确定定性性匹匹配配，也也称称完完全匹配或精确匹配全匹配或精确匹配2021/8/226模式匹配模式匹配l下面我们给出代换的概念：下面我们给出代换的概念：l代换是形如代换是形如lt1/x1,t2/x2,tn/xn的有限集合。其中，的有限集合。其中，l t1， t2， ,tn是项，是项，lx1. ，x2, xn是互不相同的变元；是互不相同的变元；lti/xi表示用项表示用项ti代换变量代换变量xi，不允许，不允许ti 和和xi相同，也不允许相同，也不允许xi循环的出现在另一个循环的出现在另一个tj中。中。2021/8/227模式匹配模式匹配什麽是项呢？什麽是项呢？常可以作项，变量也可以作项，函数常可以作项，变量也可以作项，函数表达式可以作项。表达式可以作项。2021/8/228模式匹配模式匹配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/8/229模式匹配模式匹配l如果把它改为如果把它改为g(a)/x,f(x)/y就可就可以了，它将把公式中的以了，它将把公式中的x代换成代换成g(a),y代换成代换成f(g(a),从而消去了从而消去了变量变量x和和y。 2021/8/230模式匹配模式匹配l下面给出一个公式的代换例式的概念：下面给出一个公式的代换例式的概念：l设设F是一个公式，是一个公式， 是一个代换，记是一个代换，记F 为为公式公式F在在 下的代换例式，它是将公式下的代换例式，它是将公式F中中的变量用的变量用 中的项作代换的结果。例如有中的项作代换的结果。例如有公式（公式（x,y,f(y)和代换和代换 =a/x,b/yl于是于是F =（a,b,f(b)2021/8/231模式匹配模式匹配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/8/232模式匹配模式匹配l例如设有如下代换：例如设有如下代换：l =f(y)/x,z/yl =a/x,b/y,y/zl求求 和和 l解：我们先来求解：我们先来求 2021/8/233模式匹配模式匹配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/8/234模式匹配模式匹配l再来求再来求 ，同样先求，同样先求 l a /x, b /y, y /z, f(y)/x,z/yl =a /x, b /y,z/z, f(y)/x,z/yl去掉不合法的元素去掉不合法的元素z/z,f(y)/x,z/y得得l =a /x, b /yl显然代换的复合运算是不可交换的。并显然代换的复合运算是不可交换的。并且对任何代换且对任何代换 存在空代换存在空代换 ，并且，并且l 2021/8/235模式匹配模式匹配l下面我们给出合一的概念：下面我们给出合一的概念：l设有公式集设有公式集F=F1，F2，,Fn,若存在一若存在一个代换个代换 使得使得F1 = F2 = Fn l则称则称 为公式集为公式集F的一个合一，且称的一个合一，且称lF1，F2，,Fn是可合一的。是可合一的。2021/8/236模式匹配模式匹配l例如例如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/8/237模式匹配模式匹配l一个公式的合一一般是不唯一的。但如一个公式的合一一般是不唯一的。但如果果l 是公式集是公式集F的一个合一，若对任一个合的一个合一，若对任一个合一一 都存在一个代换都存在一个代换 使得：使得： = 则称则称 是一个最一般合一。是一个最一般合一。2021/8/238模式匹配模式匹配l最一般合一是唯一的。若用最一般合一最一般合一是唯一的。若用最一般合一去代换那些可合一的谓词公式，可使它去代换那些可合一的谓词公式，可使它们变成完全一致的公式。由此可知，为们变成完全一致的公式。由此可知，为了使两个知识模式匹配，可用其最一般了使两个知识模式匹配，可用其最一般合一对它们进行代换。合一对它们进行代换。2021/8/239模式匹配模式匹配l为了求最一般合一要用到一个差异集为了求最一般合一要用到一个差异集（也有叫分歧集的）的概念。设有如下（也有叫分歧集的）的概念。设有如下两个谓词公式两个谓词公式lF1：P(x,y,z)lF2: P(x,f(a),h(b)l分别从分别从F1 与与F2的第一个符号开始，逐个的第一个符号开始，逐个向右比较，此时发现向右比较，此时发现F1中的中的y与与F2中的中的f(a)不同，它们构成了一个差异集：不同，它们构成了一个差异集：D1=y,f(a),2021/8/240模式匹配模式匹配l当继续向右比较时，又发现当继续向右比较时，又发现F1中与中与F2中中的的h(b)不同，于是又得到一个差异集：不同，于是又得到一个差异集：lD2=z,h(b)。下面给出求最一般合一的。下面给出求最一般合一的算法：算法：l（1）令）令K=0， Fk=F, k= 这里，这里，F是欲是欲求其最一般合一的公式集，求其最一般合一的公式集， 是空代换，是空代换，它表示不做代换。它表示不做代换。l（2）若）若Fk只含一个表达式，则算法停，只含一个表达式，则算法停， k就是所求最一般合一。就是所求最一般合一。2021/8/241模式匹配模式匹配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/8/242模式匹配模式匹配l例如，设例如，设lF = P(a,x,f(g(y),P(z,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/8/243模式匹配模式匹配(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, g(y)/u。2021/8/244模式匹配模式匹配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/8/245冲突消解策略冲突消解策略l接下来我们学习冲突消解方面的概念：接下来我们学习冲突消解方面的概念：l在推理的过程中，系统不断的用以知的在推理的过程中，系统不断的用以知的事实与知识库中的知识进行匹配，此时事实与知识库中的知识进行匹配，此时可能发生如下三种情况：可能发生如下三种情况：l（1）已知事实不能与知识库中的任何知）已知事实不能与知识库中的任何知识匹配成功。识匹配成功。l（2）已知事实恰好与知识库中的一条知）已知事实恰好与知识库中的一条知识匹配成功。识匹配成功。2021/8/246冲突消解策略冲突消解策略l（3）已知事实可与知识库中的多条知识）已知事实可与知识库中的多条知识匹配成功。匹配成功。l以上三种情况中，第一种情况使得推理以上三种情况中，第一种情况使得推理无法进行下去，第三种情况则出现冲突，无法进行下去，第三种情况则出现冲突，需要按一定的策略解决冲突。需要按一定的策略解决冲突。 2021/8/247冲突消解策略冲突消解策略l目前解决冲突的策略有多种，其基本思目前解决冲突的策略有多种，其基本思想都是对知识进行排序，常用的有以下想都是对知识进行排序，常用的有以下几种：几种：l1、按针对性排序、按针对性排序l设有如下两条产生式规则：设有如下两条产生式规则：lr1:IF A1 and A2 and An THEN H1lr2:IF B1 and B2 and Bm THEN H22021/8/248冲突消解策略冲突消解策略l如果存在最一般合一，使得如果存在最一般合一，使得r1中每一个中每一个Ai都可变成相应的都可变成相应的Bi ，即，即r2中除了包含中除了包含r1的的全部条件全部条件A1,A2, , An外，还包含其它条外，还包含其它条件，则称件，则称r2 比比 r1有更大的针对性，有更大的针对性， r1 比比r2 有更大的通用性。有更大的通用性。l一般选用针对性较强的产生式规则。一般选用针对性较强的产生式规则。(即即应选用应选用r2)因为它要求的条件较多，其结因为它要求的条件较多，其结论一般更论一般更 接近目标，一旦得到满足，可接近目标，一旦得到满足，可缩短推理过程。缩短推理过程。2021/8/249冲突消解策略冲突消解策略l2、按已知事实的新鲜性排序、按已知事实的新鲜性排序l在产生式系统推理过程中，每应用一条在产生式系统推理过程中，每应用一条产生式规则就会得到一个或多个结论，产生式规则就会得到一个或多个结论，数据库就会增加新的事实。把数据库后数据库就会增加新的事实。把数据库后生成的事实称为生成的事实称为 新鲜的事实，即后生成新鲜的事实，即后生成的事实比先生成的事实具有较大的新鲜的事实比先生成的事实具有较大的新鲜性。设规则性。设规则r1可与事实组可与事实组A匹配成功，规匹配成功，规则则r2可与事实组可与事实组B匹配成功，则匹配成功，则A与与B中哪中哪一组新鲜与它匹配的产生式规则就先被一组新鲜与它匹配的产生式规则就先被应用。应用。2021/8/250冲突消解策略冲突消解策略l3、按匹配排序、按匹配排序l在不确定性匹配中，为了确定两个知识在不确定性匹配中，为了确定两个知识模式是否可以匹配，需要计算这两个模模式是否可以匹配，需要计算这两个模式的相似程度，当其相似程度达到某个式的相似程度，当其相似程度达到某个预定的值时，就认为它们是可匹配的。预定的值时，就认为它们是可匹配的。若两条规则均按匹配度匹配成功，则匹若两条规则均按匹配度匹配成功，则匹配度大的那条规则优先启用。配度大的那条规则优先启用。2021/8/251冲突消解策略冲突消解策略l4、根据领域问题的特点排序、根据领域问题的特点排序l某些领域问题可事先知道它的某些特性，某些领域问题可事先知道它的某些特性，可根据这些特性把知识排成固定的顺序。可根据这些特性把知识排成固定的顺序。先匹配成功的优先启用的原则。先匹配成功的优先启用的原则。2021/8/252冲突消解策略冲突消解策略l5、按上下文限制排序、按上下文限制排序l把产生式规则按它们所描述的上下文分把产生式规则按它们所描述的上下文分成若干组，在不同的条件下，只能从相成若干组，在不同的条件下，只能从相应的组中选取有关的产生式规则。这样应的组中选取有关的产生式规则。这样可以减少冲突的发生可以减少冲突的发生2021/8/253冲突消解策略冲突消解策略l6、按冗余限制排序、按冗余限制排序l若哪一条产生式规则被应用后产生冗余若哪一条产生式规则被应用后产生冗余知识，则就降低它被应用的优先级。知识，则就降低它被应用的优先级。l7、按条件个数排序、按条件个数排序l如果有多条产生式规则生成的结论相同，如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用。则要求条件少的产生式规则被优先应用。2021/8/254 4.2自然演绎推理自然演绎推理l从一组已知的事实出发，直接运用经典从一组已知的事实出发，直接运用经典逻辑推理规则推出结论的过程称为自然逻辑推理规则推出结论的过程称为自然演绎推理。其中，基本的推理规则是演绎推理。其中，基本的推理规则是P规规则、则、T规则、假言推理、拒取式推理等。规则、假言推理、拒取式推理等。假言推理的一般形式是假言推理的一般形式是lP，PQ Ql拒取式的一般形式是拒取式的一般形式是lPQ， Q P2021/8/2554.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/8/2564.2自然演绎推理自然演绎推理 6、 B C D P规则规则l7、 D T规则规则5和和6l8、D Q P规则规则l9、 Q T规则规则7和和8l问题得证问题得证2021/8/2574.2自然演绎推理自然演绎推理l例例2设已知如下事实；设已知如下事实；l（1）凡是容易的课程小王（）凡是容易的课程小王（Wang)都喜都喜欢。欢。l（2）C班的课程都是容易的。班的课程都是容易的。l（3）ds是是C班的一门课程班的一门课程l求证小王喜欢求证小王喜欢ds这门课程。这门课程。2021/8/2584.2自然演绎推理自然演绎推理l证明：首先定义谓词如下：证明：首先定义谓词如下：lEasy（x): x是容易的是容易的lLike（x,y): x喜欢喜欢ylC（x): x是是C班的一门课程班的一门课程l于是问题可以表示成：于是问题可以表示成：2021/8/2594.2自然演绎推理自然演绎推理l x(Easy(x) Like(Wang,x) l x(C(x) Easy(x) lC(ds) Like（Wang,ds).2021/8/2604.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/8/2614.2自然演绎推理自然演绎推理l自然演绎推理的优点是表达定理证明过自然演绎推理的优点是表达定理证明过程自然，容易理解，拥有丰富的推理规程自然，容易理解，拥有丰富的推理规则，推理过程灵活，便于在推理过程中则，推理过程灵活，便于在推理过程中嵌入领域启发知识。缺点是容易产生组嵌入领域启发知识。缺点是容易产生组合爆炸，推理过程中得到的中间结论一合爆炸，推理过程中得到的中间结论一般呈指数形式递增，这对于一个大型推般呈指数形式递增，这对于一个大型推理问题是十分不利的，甚至是不可能实理问题是十分不利的，甚至是不可能实现的。现的。2021/8/2624.3归结演绎推理归结演绎推理l定理证明是人工智能的一个重要研究领域，这定理证明是人工智能的一个重要研究领域，这不仅仅是因为许多数学问题要通过定理证明得不仅仅是因为许多数学问题要通过定理证明得以解决，很多非数学问题（如医疗诊断、机器以解决，很多非数学问题（如医疗诊断、机器人规划及难题求解等）也都归结为一个定理证人规划及难题求解等）也都归结为一个定理证明问题。定理证明的实质是对前提明问题。定理证明的实质是对前提P和结论和结论Q证证明明P Q的永真性。但是证明一个谓词公式的的永真性。但是证明一个谓词公式的永真性不像证明一个命题公式的永真性那麽简永真性不像证明一个命题公式的永真性那麽简单，（它牵涉到谓词变量、客体变量及函数符单，（它牵涉到谓词变量、客体变量及函数符号）在某些情况下甚至是行不通的。号）在某些情况下甚至是行不通的。2021/8/2634.3归结演绎推理归结演绎推理l在这种情况下，人们提出了用反证法来在这种情况下，人们提出了用反证法来解决问题的思路。在这方面，海伯伦和解决问题的思路。在这方面，海伯伦和鲁宾逊都作出了杰出的贡献。鲁宾逊都作出了杰出的贡献。l两人的研究都是以子句集为背景展开的。两人的研究都是以子句集为背景展开的。接下来，我们介绍这些概念。接下来，我们介绍这些概念。2021/8/2644.3归结演绎推理归结演绎推理l子句：在谓词逻辑中，称原子谓词公式子句：在谓词逻辑中，称原子谓词公式及其否定为文字；任何文字的析取式为及其否定为文字；任何文字的析取式为子句。子句。l例如，例如，P(x) Q(x), P(x,f(x) Q(x,g(x)都是子句。而都是子句。而P(x) 、 Q(x,g(x)、 P(x,f(x)等都是文字。并把不包含任何等都是文字。并把不包含任何文字的子句称为空子句。文字的子句称为空子句。2021/8/2654.3归结演绎推理归结演绎推理l由于空子句不包含任何文字，它不能被由于空子句不包含任何文字，它不能被任何解释所满足，所以空子句是永假的，任何解释所满足，所以空子句是永假的，不可满足的。不可满足的。l由子句构成的集合称为子句集。在谓词由子句构成的集合称为子句集。在谓词逻辑中任何一个谓词公式均可通过等价逻辑中任何一个谓词公式均可通过等价变换化为相应的子句集。变换化为相应的子句集。2021/8/2664.3归结演绎推理归结演绎推理l化子句集的步骤如下：化子句集的步骤如下：l1、利用等价公式消去公式中的逻辑连接、利用等价公式消去公式中的逻辑连接词词“”l和和“”：lP QP QlP Q （P Q） （ P Q）2021/8/2674.3归结演绎推理归结演绎推理l2、利用下列公式将否定符号、利用下列公式将否定符号“ ”深入到深入到单个变元前单个变元前l P Pl （P Q） P Ql （P Q） P Ql ( x)P ( x) Pl ( x)P ( x) P2021/8/2684.3归结演绎推理归结演绎推理l3、重新命名变元名，使不同量词约束的变元、重新命名变元名，使不同量词约束的变元有不同的名字有不同的名字 l4、消去存在量词。分两种情况处理：一种情、消去存在量词。分两种情况处理：一种情况是存在量词不出现在全称量词的辖域内，此况是存在量词不出现在全称量词的辖域内，此时只要用一个新的个体常量替换受该存在量词时只要用一个新的个体常量替换受该存在量词约束的变元就可消去存在量词；另一种情况是约束的变元就可消去存在量词；另一种情况是存在量词位于一个或多个全称量词的辖域内，存在量词位于一个或多个全称量词的辖域内，例如例如l（ x1) （ x2)( xn)( y)P(x1,x2,xn,y)l此时需要用此时需要用Skolem函数函数f(x1,x2,xn)替换受该替换受该存在量词约束的变元，然后才能消去存在量词。存在量词约束的变元，然后才能消去存在量词。2021/8/2694.3归结演绎推理归结演绎推理l5、把全称量词全部移到公式的左边。、把全称量词全部移到公式的左边。l6、利用等价关系、利用等价关系lP (Q R) =( P Q) ( P R)把公式化把公式化为为 Skolem标准型。标准型。2021/8/270 4.3归结演绎推理归结演绎推理lSkolem标准型的一般形式是：标准型的一般形式是：l（ x1) （ x2)( xn)Ml其中，其中，M是子句的合取式，称为是子句的合取式，称为Skolem标准型的母式。标准型的母式。l7、消去全称量词、消去全称量词l8、对变元更名，使不同子句中的变元不、对变元更名，使不同子句中的变元不同名。同名。2021/8/2714.3归结演绎推理归结演绎推理l9、消去合取连接词，变为子句集。子句、消去合取连接词，变为子句集。子句集中各子句之间是合取关系。谓词公式集中各子句之间是合取关系。谓词公式是不可满足的，则其子句集合是不可满是不可满足的，则其子句集合是不可满足的，反之亦然。足的，反之亦然。 2021/8/272 海伯伦理论海伯伦理论l如何证明一个子句集是不可满足的呢？如何证明一个子句集是不可满足的呢？下面就海伯伦理论和鲁宾逊的归结原理下面就海伯伦理论和鲁宾逊的归结原理进行讨论。进行讨论。l一、海伯伦理论一、海伯伦理论l要判定一个子句集是否是不可满足的，要判定一个子句集是否是不可满足的，需要对子句集中的谓词公式进行判定，需要对子句集中的谓词公式进行判定，而谓词公式的判定需要对个体域上的任而谓词公式的判定需要对个体域上的任何解释进行判定，这是很困难的。何解释进行判定，这是很困难的。2021/8/273 海伯伦理论海伯伦理论l海伯伦定义了一个特殊的域称为海伯伦海伯伦定义了一个特殊的域称为海伯伦域，在任何域上的判定，只要在海伯伦域，在任何域上的判定，只要在海伯伦域上域上 进行即可。进行即可。l*设设S是子句集，则按下述方法构造的域是子句集，则按下述方法构造的域H 称为是海伯伦域：称为是海伯伦域：2021/8/274 海伯伦理论海伯伦理论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/8/275海伯伦理论海伯伦理论l例例1求子句集求子句集S=P(x) Q(x),R(f(y)的的H域。域。l解：因为解：因为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/8/276海伯伦理论海伯伦理论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) l 2021/8/277海伯伦理论海伯伦理论l例例3：求子句集：求子句集S=P(x),Q(y) R(y)的的H域。域。l解：由于该子句集中既无个体常量，又无函数，解：由于该子句集中既无个体常量，又无函数，所以可任意指定一个常量所以可任意指定一个常量a作为个体常量，从作为个体常量，从而得到而得到H0 = H1= H = al有定理说：子句集有定理说：子句集S是不可满足的充要条件是是不可满足的充要条件是S对对H域上的一切解释都为假。并且海伯伦证明域上的一切解释都为假。并且海伯伦证明了若子句集了若子句集S在任何域在任何域D上的解释能满足上的解释能满足S，则，则在在H域上相应的解释也能满足域上相应的解释也能满足S。下面我们说明，。下面我们说明，S在在H域上解释的定义：域上解释的定义：2021/8/278海伯伦理论海伯伦理论l子句集子句集S在在H域上的一个解释满足下列域上的一个解释满足下列条件：条件：l1、在解释、在解释I下，常量映射到自身；下，常量映射到自身；l2、S中的任一个中的任一个n元函数是元函数是HnH的映的映射。即，设射。即，设h1,h2,hn H,则则f(h1,h2,hn) H;2021/8/279海伯伦理论海伯伦理论l3、S中的任一中的任一n元谓词是元谓词是HnT，F的映的映射。即谓词的真值可以指派射。即谓词的真值可以指派T也可指派也可指派F。l海伯伦在理论上证明了子句集不可满足海伯伦在理论上证明了子句集不可满足性的可行性及方法，但要在计算机上实性的可行性及方法，但要在计算机上实现其证明过程还是很困难的。现其证明过程还是很困难的。1965年鲁年鲁宾逊提出了归结原理，使机器证明成为宾逊提出了归结原理，使机器证明成为现实现实2021/8/280鲁宾逊归结原理鲁宾逊归结原理l归结原理也称消解原理，是鲁宾逊提出的一种归结原理也称消解原理，是鲁宾逊提出的一种证明子句不可满足性，从而实现定理证明的一证明子句不可满足性，从而实现定理证明的一种理论及方法。种理论及方法。l由谓词公式转化为子句集的过程可以看出，在由谓词公式转化为子句集的过程可以看出，在子句集中子句之间的关系是合取关系，其中只子句集中子句之间的关系是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。要有一个子句不可满足，则子句集就不可满足。前面，我们曾经说过空子句是不可满足的，即前面，我们曾经说过空子句是不可满足的，即一个子句集中若含空子句，则它是不可满足的。一个子句集中若含空子句，则它是不可满足的。2021/8/281鲁宾逊归结原理鲁宾逊归结原理l归结原理的基本思想就是检查子句集中归结原理的基本思想就是检查子句集中是否含空子句，若含，则子句集是否含空子句，若含，则子句集S不可满不可满足，或说证明一个谓词公式是永假的过足，或说证明一个谓词公式是永假的过程，就是归结由此公式转换成的子句集程，就是归结由此公式转换成的子句集包含空子句的过程。包含空子句的过程。2021/8/282鲁宾逊归结原理鲁宾逊归结原理l下面我们先来说明命题逻辑中的归结原下面我们先来说明命题逻辑中的归结原理理l定义定义P是原子谓词公式，则称是原子谓词公式，则称P与与 P为互为互补文字。我们知道在命题逻辑中有公式：补文字。我们知道在命题逻辑中有公式：lPQ,Q R P R即即l P Q， Q R P R l c1 c2 c122021/8/283鲁宾逊归结原理鲁宾逊归结原理l显然上述公式向我们展示的是在子句显然上述公式向我们展示的是在子句c1 中存在文字中存在文字Q，在子句，在子句c2中存在中存在Q的补文的补文字字 Q，把这一对互补文字消去，剩下的，把这一对互补文字消去，剩下的文字析取起来就是子句文字析取起来就是子句 c1 和和c2的逻辑结的逻辑结果果c12。并称。并称c12是是c1 和和c2的归结式，的归结式， c1 和和c2则称为则称为c12的亲本子句。的亲本子句。2021/8/284鲁宾逊归结原理鲁宾逊归结原理l例如：例如：l1、C1= P Q Rl C2= Q Sl它们的归结式它们的归结式c12为为 P R Sl2、C1= Pl C2=Pl它们的归结式它们的归结式c12为为NIL即空子句。即空子句。2021/8/285鲁宾逊归结原理鲁宾逊归结原理l3、C1= P Q l C2= Q Rl C3=Pl它们的归结式它们的归结式c123为为R。其归结过程可以。其归结过程可以用下面的一个树形结构很清楚的表现出用下面的一个树形结构很清楚的表现出来。来。2021/8/286鲁宾逊归结原理鲁宾逊归结原理 l P Q Q Rl P R Pl Rl 归结过程的树形表示图归结过程的树形表示图 2021/8/287鲁宾逊归结原理鲁宾逊归结原理l由命题逻辑中的归结原理可以得出如下由命题逻辑中的归结原理可以得出如下的推论：的推论：l设设c1与与c2是子句集是子句集S中的两个子句，中的两个子句，c12是是它们的归结式它们的归结式,若用若用c12代替代替c1和和c2后得到后得到新子句集新子句集S1，则由，则由S1的不可满足性可以推的不可满足性可以推出出S的不可满足性。这个定理告诉我们，的不可满足性。这个定理告诉我们，证明子句集证明子句集S的不可的不可 满足性问题，可以转满足性问题，可以转化成证子句集化成证子句集S1的不可满足性问，的不可满足性问，直直到从子句集到从子句集Sn 中推出一个空子句来。中推出一个空子句来。2021/8/288鲁宾逊归结原理鲁宾逊归结原理l在谓词逻辑中，由于子句中含有变元，在谓词逻辑中，由于子句中含有变元，所以不象命题逻辑中那样可以直接消去所以不象命题逻辑中那样可以直接消去互补文字，而先要用最一般合一对变元互补文字，而先要用最一般合一对变元进行代换。然后才能进行归结。前面我进行代换。然后才能进行归结。前面我们已经介绍过最一般合一的概念，下面们已经介绍过最一般合一的概念，下面给出谓词逻辑中二元归结式的概念。给出谓词逻辑中二元归结式的概念。2021/8/289鲁宾逊归结原理鲁宾逊归结原理l设设C1与与C2是两个没有公共变量的子句，是两个没有公共变量的子句，L1和和L2 分别是分别是C1与与C2中的文字，若中的文字，若 是是L1和和 L2的最一般合一，则称的最一般合一，则称lC12= （ C1 -L1 ） （ C2 - L2 ）为为C1与与C2的二元归结式，的二元归结式， L1和和L2称为归称为归结式上的文字。例子见结式上的文字。例子见P132页的例页的例4.10和例和例4.11。2021/8/290鲁宾逊归结原理鲁宾逊归结原理 例如设例如设C1=P(a) Q(x) R(x) C2= P(y) Q(b) 若选若选L1= P(a), L2= P(y),则则 =a/y是是L1 与与 L2的最一般合一的最一般合一于是有于是有C12=(C1 -L1 ) (C2 -L2 ) = Q(x) R(x) Q(b) = Q(x),R(x), Q(b) . 2021/8/291鲁宾逊归结原理鲁宾逊归结原理 若选若选L1= Q(x), L2= Q(b),则则 =b/x是是L1 与与 L2的最一般合一的最一般合一于是有于是有C12=(C1 -L1 ) (C2 -L2 ) = Q(x) R(x) Q(b) =P(a),R(b), P(y) .2021/8/292鲁宾逊归结原理鲁宾逊归结原理再例如设有如下子句：再例如设有如下子句：1=P(x) Q(a),2= P(b) R(x)由由于于1和和2 有有相相同同的的变变元元不不符符合合二二元元归归结结式式中中定定义义中中对对子子句句1和和2的的要求为了归结的需要，要修改要求为了归结的需要，要修改2中变元的名字中变元的名字 2021/8/293鲁宾逊归结原理鲁宾逊归结原理l令令2= P(b) R(y),此时，此时，1=P(x),l2= P(b),它它们们的的最最一一般般合合一一为为 b/x.于是有于是有lC12=(P(b),Q(a)P(b),)l ( P(b) R(y),- P(b)l=Q(a), R(y).l如如果果在在参参加加归归结结的的子子句句内内部部有有可可合合一一的的文文字字，则则在在归归结结之之前前应应先先对对这这些些文文字字合合一，见下例：一，见下例：2021/8/294鲁宾逊归结原理鲁宾逊归结原理l设有子句：设有子句：C1=P(x) P(f(a) Q(x)lC2= P(y) R(b)由于在由于在C1中有可合一文字中有可合一文字P(x) 和和P(f(a)，若用它们的最一般合一，若用它们的最一般合一l f(a)/x进行代换，得到进行代换，得到l C1 = P(f(a) Q(f(a)l此时可对此时可对C1 和和C2进行归结，从而的到进行归结，从而的到C1和和C2的二元归结式对的二元归结式对C1 和和C2分别选分别选l1=P(f(a),l2= P(y),它们的最一般合一是它们的最一般合一是2021/8/295鲁宾逊归结原理鲁宾逊归结原理 f(a)/y于是可得它们的归结式为：于是可得它们的归结式为：C12(b) Q(f(a)上例中称上例中称C1 为为C1因子，如果因子，如果C1 是一个单是一个单文字，则称它为文字，则称它为C1的单元因子的单元因子应用因子的概念，可对谓词逻辑中的归结原应用因子的概念，可对谓词逻辑中的归结原理给出如下的定义理给出如下的定义2021/8/296鲁宾逊归结原理鲁宾逊归结原理l定定义义；子子句句1和和的的归归结结式式是是下下列列二二元元归结式之一：归结式之一：l(1)1和和的二元归结式；的二元归结式；l(2)1和和的因子的因子 2的二元归结式；的二元归结式；l(3)的因子的因子1 1和和的二元归结式；的二元归结式；l(4)1的的因因子子1 1和和的的因因子子 2的的 二元归结式；二元归结式；2021/8/297鲁宾逊归结原理鲁宾逊归结原理l在在谓谓词词逻逻辑辑中中仍仍然然有有，归归结结式式是是它它的的亲亲本本子子句句的的逻逻辑辑结结果果，用用归归结结式式代代替替子子句句集集中中的的亲亲本本子子句句所所得得到到的的新新子子句句集集 仍然保持子句集的不可满足性仍然保持子句集的不可满足性2021/8/298归结反演归结反演l归结反演原理：欲证归结反演原理：欲证lP1,P2, PnQ (1)lP1P2, PnQT (2)l (P1P2, Pn) QT (3)l(P1P2, Pn) QF (4)l我们的工作过程是从后向前进行的，即我们的工作过程是从后向前进行的，即证证(4)就是证明了就是证明了(3),证证(3)就是证明了就是证明了(2),证证(2)就是证明了就是证明了(1) 2021/8/299归结反演归结反演l在在使使用用消消解解过过程程之之前前，我我们们必必须须把把任任一一谓谓词词公公式式转转换换成成子子句句，下下面面给给出出转转化化过过程的步骤：程的步骤：l（1）消去单条件运算符号）消去单条件运算符号“”，l应用公式应用公式 AB = A Bl（2） 将将否否定定符符号号深深入入到到单单个个谓谓词词变变元元的的前面，利用公式前面，利用公式l （A B）= ABl （A B）= ABl ( x)A(x) = ( x) A(x)l ( ( x) A(x) = ( x) A(x)l 2021/8/2100归结反演归结反演l(3) 对变量标准化对变量标准化l在在任任一一量量词词辖辖域域内内，受受该该量量词词约约束束的的变变量量为为一一哑哑元元（虚虚构构变变量量），它它可可以以在在该该辖辖域域内内处处处处统统一一地地被被另另一一个个没没有有出出现现过过的的任任一一变变量量所所代代替替，而而不不改改变变公公式式的的真真值值。合合适适公公式式中中变变量量的的标标准准化化意意味味着着对对哑哑元元改改名名以以保保证证每每个个量量词词有有其其自自己己唯一的哑元。唯一的哑元。l例如把例如把 ( x)（A(x) ( x)（B（x）l标准化为标准化为 ( x)（A(x) ( y)（B（y）2021/8/2101归结反演归结反演l(4) 消去存在量词消去存在量词l在在公公式式 ( x)( ( y)P(x,y)中中，存存在在量量词词是是在在全全称称量量词词的的辖辖域域内内，我我们们允允许许所所存存在在的的x可可能能依依赖赖于于y值值。令令这这种种依依赖赖关关系系明明显显地地由由函函数数g（y）所所定定义义，它它把把每每个个y值值映映射射到到存存在在的的那那个个x。这这种种函函数数叫叫做做skolem函函数数。如如果果用用skolem函函数数代代替替存存在在的的x，我我们们就就可可以以消消去去全全部部存存在在量量词词，并写成并写成( y)(P(g(y),y)2021/8/2102归结反演归结反演l在在公公式式 ( x)( ( y)P(x,y)中中，存存在在量量词词是是在在全全称称量量词词的的辖辖域域内内，我我们们允允许许所所存存在在的的x可可能能依依赖赖于于y值值。令令这这种种依依赖赖关关系系明明显显地地由由函函数数g（y）所所定定义义，它它把把每每个个y值值映映射射到到存存在在的的那那个个x。这这种种函函数数叫叫做做skolem函函数数。如如果果用用skolem函函数数代代替替存存在在的的x，我我们们就就可可以以消消去去全全部部存存在在量量词词，并写成并写成( y)(P(g(y),y)2021/8/2103归结反演归结反演l从从一一个个公公式式消消去去存存在在量量词词的的一一般般规规则则是是以以一一个个skolem函函数数代代替替每每个个出出现现的的存存在在量量词词的的量量化化变变量量，而而这这个个skolem函函数数的的变变量量就就是是由由那那些些全全称称量量词词所所约约束束的的全全称称量量词词量量化化变变量量，这这些些全全称称量量词词的的辖辖域域包包括括要要被被消消去去的的存存在在量量词词的的辖辖域域在在内内。skolem函函数数所所使使用用的的函函数数符符号号必必须须是是新新的的，即即不允许是公式中已经出现过的函数符号。例如：不允许是公式中已经出现过的函数符号。例如：l( y) ( x) P(x,y)被被( y)(P(g(y),y)代代替替，其其中中g(y)为一为一skolem函数。函数。2021/8/2104归结反演归结反演l如如果果要要消消去去的的存存在在量量词词不不在在任任何何一一个个全全称称量量词词的的辖辖域域内内，那那麽麽我我们们就就用用不不含含变变量量的的skolem函函数数即即常常量量。例例如如，( x) P(x)化化为为P(A)，其其中中常常量量符符号号A用用来来表表示示我我们们知知道道的的存存在在实实体体。A必必须须是是个个新新的的常常量量符符号号，它它未未曾曾在在公公式式中中其其它它地地方方使使用用过。过。2021/8/2105归结反演归结反演l（5）化为前束形）化为前束形l到到这这一一步步已已不不留留下下任任何何存存在在量量词词，而而且且，每每个个全全称称量量词词都都有有自自己己的的变变量量。把把所所有有全全称称量量词词移移到到公公式式的的左左边边，并并使使每每个个量量词词的的辖辖域域包包括括这这个个量量词词后后面面公公式式的的整整个个部分。所得公式称为前束形。部分。所得公式称为前束形。2021/8/2106归结反演归结反演l前前束束形形公公式式由由前前缀缀和和母母式式组组成成，前前缀缀由由全全称称量量词词组组成成，母母式式由由没没有有量量词词的的公公式式组成，即组成，即l 前束形前束形=（前缀）（前缀） （母式）（母式）l 全称量词串全称量词串 无量词公式无量词公式2021/8/2107归结反演归结反演l（6）把母式化为合取范式）把母式化为合取范式l 任任何何母母式式都都可可写写成成由由一一些些谓谓词词公公式式和和（或或）谓谓词词公公式式的的否否定定的的析析取取的的有有限限集集组组成成的的合合取取。这这种种母母式式叫叫做做合合取取范范式式。我我们们可可以以反反复复应应用用 对对 的的分分配配律律，把把任任一母式化成合取范式。例如，一母式化成合取范式。例如，lA （B C）=（A B） （ A C）2021/8/2108归结反演归结反演l（7）消去全称量词）消去全称量词l到到了了这这一一步步，所所有有余余下下的的量量词词均均被被全全称称量量词词量量化化了了。同同时时，全全称称量量词词的的次次序序已已经经不不重重要要了了。于于是是我我们们可可以以消消去去全全称称量量词。词。2021/8/2109归结反演归结反演l（8）消消去去连连接接词词符符号号 ，用用A，B代代替替A B。这这样样反反复复代代替替的的结结果果，最最后后得得到到一一个个有有限限集集，其其中中每每个个公公式式是是文文字字的的析析取取。任任一一个个只只由由文文字字的的析析取取构构成成的的合合式式公式叫做一个子句。公式叫做一个子句。l（9）更换变量名称）更换变量名称l可可以以更更换换变变量量符符号号的的名名称称，使使一一个个变变量量符符号号不不出出现现在在一一个个以以上上的的子子句句中中。下下面面我我们们用用例例子子来来说说明明化化子子句句并并进进行行消消解解的的过程：过程：2021/8/2110归结反演归结反演l例例1试证：试证：G是是F1和和F2的逻辑结论，其中的逻辑结论，其中lF1：( x)( P(x) ( y)(Q(y) L(x,y)lF2：( x)( P(x) ( y)(R(y) L(x,y)lG： ( x) (R(x) Q(x)l( x)(P(x)( y)(Q(y)L(x,y),l( x)( P(x) ( y)(R(y) L(x,y)l( x) (R(x) Q(x)2021/8/2111归结反演归结反演l证明：首先把证明：首先把F1 ，F2 和和 G转化成子句形：转化成子句形：lF1=( x)(P(x)( y)(Q(y)L(x,y)l=( x)( P(x) ( y)( Q(y) L(x,y)l=( x) ( y) ( P(x) Q(y) L(x,y)l= P(x) Q(y) L(x,y).2021/8/2112归结反演归结反演lF2=( x)( P(x) ( y)(R(y) L(x,y)l=( x)( P(x) ( y)( R(y) L(x,y)l=( P(a) ( y)( R(y) L(a,y)l=( y) ( P(a) ( R(y) L(a,y)lP(a), R(z) L(a,z) 2021/8/2113归结反演归结反演l G= ( x) (R(x) Q(x)l=( x) ( R(x) Q(x)l= (R(x) Q(x)lR(b), Q(b)l得到子句集合如下：得到子句集合如下：l1. P(x) Q(y) L(x,y)l2. P(a)l3. R(z) L(a,z) Sl4. R(b) l5. Q(b)2021/8/2114归结反演归结反演l6. Q(y) L(a,y) 1和和2及及 a/x l7. L(a,b) 5和和6及及 b/y l8. R(b) 3和和7及及 b/z l9. 4和和8及及 = l即即S是是不不可可满满足足的的，G是是F1和和F2的的逻逻辑辑结结论。论。2021/8/2115归结反演归结反演l例例2 2、已已知知：任任何何人人的的兄兄弟弟不不是是女女性性，任任何何人人的的姐姐妹妹必必是是女女性性，MaryMary是是BillBill的的姐姐妹妹，试试用用归归结结推推理理的的方方法法证证明明MaryMary不不是是TomTom的兄弟。的兄弟。l解：为了求解此问题首先定义如下谓词：解：为了求解此问题首先定义如下谓词：lbrother(x,y):xbrother(x,y):x是是y y的兄弟；的兄弟；lsister(x,y): xsister(x,y): x是是y y的姐妹；的姐妹；lwoman(x): xwoman(x): x是女性。是女性。2021/8/2116归结反演归结反演l于是问题可以描述成：于是问题可以描述成：l( ( x)(x)( y)(brother(x,y)y)(brother(x,y)woman(x)woman(x),),l( ( x)(x)( y)(sister(x,y)y)(sister(x,y) woman(x), woman(x),lsister(Mary,Bill) sister(Mary,Bill) l brother(Mary ,Tom)brother(Mary ,Tom)2021/8/2117归结反演归结反演l首先将前提和结论的否定转换成子句形首先将前提和结论的否定转换成子句形: :l( ( x)(x)( y)(brother(x,y)y)(brother(x,y) woman(x) = woman(x) = brother(x,y)brother(x,y) woman(x);woman(x);l( ( x)(x)( y)(sister(x,y)y)(sister(x,y)woman(x)=woman(x)=l sister(x,y) sister(x,y) woman(x); woman(x);lbrother(Mary,Tom)= brother(Mary,Tom)= brother(Mary,Tom);brother(Mary,Tom);lsister(Mary,Bill).sister(Mary,Bill).2021/8/2118归结反演归结反演l整理得子句集合整理得子句集合S S如下：如下：l1 1、sister(Mary,Bill)sister(Mary,Bill)l2 2、brother(Mary ,Tom) Sbrother(Mary ,Tom) Sl3 3、 brother(x,y)brother(x,y)woman(x) woman(x) l4 4、 sister(z,w) sister(z,w) woman(z) woman(z)2021/8/2119归结反演归结反演l5 5、 woman(Mary)woman(Mary)和和3 3及及 Mary/x,Tom/yMary/x,Tom/y l6 6、woman(Mary)1woman(Mary)1和和4 4及及 Mary/z,Bill/wMary/z,Bill/w l7 7、 5 5和和6 6及空代换及空代换 l问题得证问题得证. .2021/8/2120归结反演归结反演l例例 3、 已已 知知 ， JohnJohn是是 贼贼 。 PaulPaul喜喜 欢欢 酒酒（winewine）, PaulPaul也也喜喜欢欢奶奶酪酪（cheesecheese）。如如果果PaulPaul喜喜欢欢某某物物则则JohnJohn也也喜喜欢欢某某物物。如如果果某某人人是是贼贼，并并且且他他喜喜欢欢某某物物，则则他他很很可可能能会会偷偷窃窃该该物物。试试用用归归结结推推理理的的方方法证明法证明JohnJohn可能偷窃了什麽？可能偷窃了什麽？2021/8/2121归结反演归结反演l解：为了求解该问题定义如下谓词：解：为了求解该问题定义如下谓词：lthief(x): xthief(x): x是贼是贼llike(x,y): like(x,y): 某人某人x x喜欢某物喜欢某物y ylmay-steal(x,y):may-steal(x,y):某人某人x x可能偷窃了某物可能偷窃了某物y y2021/8/2122归结反演归结反演l于是问题可以描述成：于是问题可以描述成：lthief(John)thief(John)，llike(Paullike(Paul，wine)wine)，llike(Paullike(Paul，cheese )cheese )，l( ( y)(like(Paul,y)y)(like(Paul,y)like(John,y),like(John,y),l( ( x)(thief(x)x)(thief(x) ( ( y)(like(x,y)y)(like(x,y)mamay-steal(x,y) y-steal(x,y) may-may-steal(John,Z).steal(John,Z).2021/8/2123归结反演归结反演l首先把前提和结论的否定转换成子句形：首先把前提和结论的否定转换成子句形：l( y)(like(Paul,y)y)(like(Paul,y)like(Johnlike(John，y)=y)=l like(Paullike(Paul，y)y) like(Johnlike(John，y );y );l( ( x)(thief(x)x)(thief(x) ( ( y)(like(x,y)y)(like(x,y)may-may-steal(x,y)= steal(x,y)= thief(John)thief(John) ( ( y)(like(John,y)y)(like(John,y)l may-teal(John ,y)=may-teal(John ,y)=l( ( y)(thief(John)y)(thief(John) ( ( like(John,y)like(John,y) lmay-steal(John ,y)may-steal(John ,y)）= =lthief(John)thief(John) ( ( like(John,y)like(John,y) may-may-steal(John,y).steal(John,y).2021/8/2124l may-steal(John,Z). may-steal(John,Z). l整理得子句集合整理得子句集合S S为：为：l1 1、 thief(John ) thief(John ) l2 2、 like(John ,y)like(John ,y) may-steal(John ,y) may-steal(John ,y)l3 3、like(Paul, wine ) like(Paul, wine ) l4 4、like(Paul, cheese )like(Paul, cheese )l5 5、 may-steal(John,Z) may-steal(John,Z) l6 6、 like(Paullike(Paul，X)X) like(Johnlike(John，X)X)l7 7、like(John,wine) 3like(John,wine) 3和和6 6及及 wine/xwine/x l8 8、may-steal(John,wine) 2may-steal(John,wine) 2和和7 7及及 wine/ywine/y l9 9、 5 5和和8 8及及 l问题得证。问题得证。2021/8/2125应用归结原理求取问题的答案应用归结原理求取问题的答案l利用归结原理还可以来求取问题的答案，利用归结原理还可以来求取问题的答案，思想与定理证明类似其求解步骤如下：思想与定理证明类似其求解步骤如下：l、把已知前提用谓词公式表示出来，、把已知前提用谓词公式表示出来，并且化为相应的子句集；并且化为相应的子句集；l、把待求解的问题也用谓词公式表示、把待求解的问题也用谓词公式表示出来，然后把它否定并与谓词出来，然后把它否定并与谓词ANSWER构成析取式，构成析取式， ANSWER是一个为了求解是一个为了求解问题而专设的谓词，其变元必须与待求问题而专设的谓词，其变元必须与待求解问题公式的变元完全一致；解问题公式的变元完全一致；2021/8/2126应用归结原理求取问题的答案应用归结原理求取问题的答案l、把把析析取取式式化化为为子子句句集集，并并且且把把该该子子句并入到子句集中，得到子句集合句并入到子句集中，得到子句集合l ；l、对、对 应用归结原理进行归结；应用归结原理进行归结；l、若若得得到到归归结结式式ANSWER，则则答答案案就在就在ANSWER中。中。2021/8/2127应用归结原理求取问题的答案应用归结原理求取问题的答案l例：例：l1:已知王（已知王（wang)先生是小李先生是小李(li)的老师的老师 .l2:小李与小张小李与小张(zhang)是同班同学是同班同学l3:如果如果x与与y是同班同学，则是同班同学，则x的老师也的老师也是是y的老师的老师l求小张的老师是谁？求小张的老师是谁？2021/8/2128应用归结原理求取问题的答案应用归结原理求取问题的答案l解：首先定义谓词：解：首先定义谓词：lT(x,y):x是是y的老师的老师lC(x,y):x与与y是同班同学是同班同学l把已知前提和待求解的问题表示成谓词把已知前提和待求解的问题表示成谓词公式：公式：lF1: T(wang ,li)lF2: C(li,zhang)lF3: ( x) ( y) ( z)(C(x,y) T(z,x) T(z,y). 2021/8/2129应用归结原理求取问题的答案应用归结原理求取问题的答案lG: ( x)T(x,zhang) ANSWER(x)l把上述公式化为子句集：把上述公式化为子句集：l（1）T(wang ,li)l（2） C(li,zhang) S l（3） C(x,y) T(z,x) T(z,y). l (4) T(u,zhang) ANSWER(u)2021/8/2130应用归结原理求取问题的答案应用归结原理求取问题的答案l应用归结原理进行归结：应用归结原理进行归结：l(5) C(li,y) T(z,y). (1)和和(3)归结归结l(6) C(li,zhang) ANSWER(wang) (4),(5)l(7) ANSWER(wang) (2)与与(6)归结归结l其归结树如其归结树如137的图的图-9所示所示l 2021/8/2131应用归结原理求取问题的答案应用归结原理求取问题的答案例例：设设,B,C三三人人中中有有人人从从不不说说真真话话，也也有有人人从从不不说说假假话话，某某人人向向这这三三人人分分别别提提出出同同一一个个问问题题：谁谁是是说说谎谎者者？答答：“和和是是说说谎谎者者”；答答：“和和是是说说谎谎者者”；答答：“和和中中至至少少有有一一个个说说谎谎者者”求谁是诚实的人，谁是说谎者？求谁是诚实的人，谁是说谎者？2021/8/2132应用归结原理求取问题的答案应用归结原理求取问题的答案l解：令解：令T(x):表示表示x说真话说真话l如果说的是真话，则有如果说的是真话，则有lT(A)T(B)T(C) l如果说的是假话，则有如果说的是假话，则有l T(A)(T(B) T(C)l对和说的话做相同的处理得：对和说的话做相同的处理得：l T()T()T(C)l T()(T() T(C)2021/8/2133应用归结原理求取问题的答案应用归结原理求取问题的答案lT()( T() T(B)l T(C)(T() T(B)l把上面的公式化为子句集得：把上面的公式化为子句集得：l(1) T() T(B)l(2) T() T(C )l(3) T(B) T(C )l(4) T() T() T(C)l(5) T() T() T(B)l(6) T() T(C )l2021/8/2134应用归结原理求取问题的答案应用归结原理求取问题的答案l(7) T(B) T(C )l下面首先求谁是老实人下面首先求谁是老实人l把把 T(x) ANSWER(x)并入得并入得1l(8) T(x) ANSWER(x)l在在1上进行归结得上进行归结得l(9) T(A) T(C ) (1)和和(7)l l2021/8/2135应用归结原理求取问题的答案应用归结原理求取问题的答案l(10)T(C) (6)和和(9)l(11) ANSWER(C) (8)和和(10)及及C/xl即是老实人即是老实人l由于对由于对1进行归结得不出进行归结得不出ANSWER()l和和ANSWER() 所所以以下下面面来来证证明明和和不是老实人不是老实人l设设不不是是老老实实人人，则则有有 T()把把它它的的否否定并入中得定并入中得2 2021/8/2136应用归结原理求取问题的答案应用归结原理求取问题的答案l即即2只比多了一个子句只比多了一个子句l(8) ( T()l(9) T() T(C ) (1)和和(7)l(10) T() (2)和和(9)l(11)NIL (8)和和(10) l所所以以不不是是老老实实人人，同同理理可可证证不不是是老老实人实人2021/8/2137归结策略归结策略l实实际际用用计计算算机机进进行行归归结结时时使使用用的的是是水水平平浸浸透透法法，即即对对中中的的每每一一对对子子句句进进行行比比较较，有有归归结结式式即即产产生生直直到到推推出出一一个个空空子子句句从从上上面面的的例例子子我我们们可可以以看看出出影影响响归归结结效效率率的的重重要要因因素素是是子子句句的的数数量量和和子子句句中中文文字字的的数数量量下下面面我我们们给给出出一一些些提提高归结效率的方法高归结效率的方法2021/8/2138归结策略归结策略l要想提高消解效率，当然是希望子句集要想提高消解效率，当然是希望子句集合合S中的子句越少越好，子句中的文字越中的子句越少越好，子句中的文字越少越好。为了提高消解效率，人们提出少越好。为了提高消解效率，人们提出了很多控制策略，例如：删除策略，线了很多控制策略，例如：删除策略，线性归结，单元归结，输入归结等。性归结，单元归结，输入归结等。 2021/8/2139删除策略删除策略所所谓谓删删除除策策略略是是指指，若若子子句句集集合合S中中有有永永真真式式则则直直接接可可以以删删除除，因因为为它它不不影影响响子子句句集集合合S的的不不可可满满足足性性，此此外外被被前前面面子子句句归归类的子句也可以被删除。下面给出归类类的子句也可以被删除。下面给出归类的概念：的概念：设设有有两两个个子子句句C和和D，若若有有置置换换（或或代代换换） ，使使得得C D 成成立立，便便说说子子句句C把把子子句句D归类，或说归类，或说D被被C归类，于归类，于是子句是子句D可以从可以从S中删除。中删除。2021/8/2140删除策略删除策略其其中中：C 表表示示子子句句C在在代代换换 下下的的例例式式，即即将将子子句句C中中的的变变元元用用 中中的的项项代代换换所所得得的结果。的结果。例例如如 C=p(x) D=p(a) Q(a) 取取 = a/x 于于是是有有C = p(a)于是有于是有 p(a) p(a)，Q(a) 其中逗号代表的其中逗号代表的是析取。是析取。2021/8/2141删除策略删除策略l设子句序列设子句序列C1，C2，Ck是从是从S推出推出Ck的演绎，若在演绎的过程中随时删除的演绎，若在演绎的过程中随时删除永真公式和被前面归类的子句，就称在永真公式和被前面归类的子句，就称在这个演绎的过程中实行了删除策略。删这个演绎的过程中实行了删除策略。删除策略是完备的，即对于不可满足的子除策略是完备的，即对于不可满足的子句集合句集合S来说，如果在水平浸透法中使用来说，如果在水平浸透法中使用删除策略，那麽一定存在一个空子句删除策略，那麽一定存在一个空子句Sn n 。 2021/8/2142删除策略删除策略下面给出下面给出归类算法归类算法（Subsumption AlgorithmSubsumption Algorithm）设设D=LD=L1 1 L L2 2 L Lm m, ,有有 = a1/x1 , a2/x2, ,an/xn ,其其中中x1 ，x2， xn是是D中中所所有有变变元元的的符符号号, a1 ,a2, ,an是是C和和D中都没有的互不相同的常量符号。中都没有的互不相同的常量符号。步步1 令令W = L L1 1 ， , L Lm m ,K = 0,U0 = C C ;步步2 若若 Uk则算法停，则算法停，C归类归类D。步步3 令令Uk+1= R(C1,C2) C1 Uk , C2 W ;步步4 若若Uk+1= ，则算法停，则算法停，C不归类不归类D。步步5 令令K=K+1,转步转步22021/8/2143删除策略删除策略由于由于U0 ，U1， , Uk，序列中，后一个序列中，后一个子句集中的每一个子句一定比前一个子子句集中的每一个子句一定比前一个子句集中的亲本子句少一个文字，而子句句集中的亲本子句少一个文字，而子句中的文字是有限的，所以，最后一定存中的文字是有限的，所以，最后一定存在一个在一个n n使使Uk= 或或 Un n即算法是可停的即算法是可停的.本算法是完备的，即子句本算法是完备的，即子句C归类子句归类子句D，当且仅当归类算法停在步当且仅当归类算法停在步2。 2021/8/2144删除策略删除策略例如给定例如给定 C= P（x） Q(f(x),a)Q(f(x),a) D= D= P（h(y)） Q (f(h(y),a) Q (f(h(y),a) P(z)试判定试判定C是否可归类是否可归类D？解：令解：令 = b/y,c/z W = P（h(b)）, Q (f(h(b),a),Q (f(h(b),a), P(c) ,K = 0U0 = P（x） Q (f(x),a)Q (f(x),a) K=0:因因 U02021/8/2145删除策略删除策略U1= Q(f(h(b),a),Q(f(h(b),a), P(h(b), Q(f(c),a) Q(f(c),a) 因因U1，K=K+1,K=1: 因因 U1, 求求U2=,因因U2，K=K+1,K=2: U2 算法停，算法停，C归类归类D。D可以被删可以被删除。除。 2021/8/2146删除策略删除策略例 设设C = P（x,x）,D = P(f(x),y) P(y,f(x)试判定试判定C是否归类是否归类D?解:令令 = a/x,b/y a/x,b/y W = P(f(a),b), P(f(a),b), P(b), f(a)P(b), f(a) K = 0 U0 = P(x,x)P(x,x) K = 0:因因 U0，求，求U1= , 因因U1 = ，算法停，算法停，C不归类不归类D。2021/8/2147线性输入策略线性输入策略线线性性归归结结是是这这样样一一种种归归结结，首首先先从从子子句句集集合合S中中选选取取一一个个称称作作顶顶子子句句的的子子句句C0开开始始作作归归结结，其其次次是是归归结结过过程程中中所所得得到到的的归归结结式式Ci立立即即同同另另一一子子句句Bi进进行行归归结结得得归归结结式式Ci+1而而Bi属属于于S或或是是已已出出现现过过的的归归结结式式Cj(j i)2021/8/2148线性输入策略线性输入策略例例 S= P Q， P Q，P Q， P Q 选取顶子句选取顶子句C0 = P Q线性归结过程线性归结过程1、 P Q2、 P Q3、P Q4、 P Q5、Q 1和和26、P 5和和37、 Q 6和和48、 7和和5 2021/8/2149 PQ PQ Q P Q P Q P Q Q 2021/8/2150线性输入策略线性输入策略顶顶子子句句的的选选择择直直接接影影响响着着归归结结的的效效率率。最最好好选得选得C0使使S- C0 是可满足的。是可满足的。线线性性输输入入策策略略具具有有简简单单和和高高效效的的优优点点，但但它它是是不不完完备备的的也也就就是是说说，即即使使子子句句集集是是不不可可满满足足的的，用用线线性性归归结结时时也也不不一一定定能能归归结结出空子句例如对子句集出空子句例如对子句集S =P(x) Q(x), P(y) Q(y),P(u) Q(u), P(t) Q(t) 用用线线性性输输入入策策略略却却归归结结不不出出空空子句子句2021/8/2151单文字子句策略单文字子句策略l如果一个子句只包含一个文字，则称它为如果一个子句只包含一个文字，则称它为单文字子句单文字子句l单文字子句策略要求参加归结的两个子句单文字子句策略要求参加归结的两个子句中必须有一个子句是单文字子句中必须有一个子句是单文字子句l例如：设有子句集：例如：设有子句集：l= I(x) R(x),I(a), R(y) L(y),L(a)l其中其中 I(x) R(x)是目标公式经否定后得到是目标公式经否定后得到的子句用单文字子句策略归结过程如下的子句用单文字子句策略归结过程如下 2021/8/2152单文字子句策略单文字子句策略构构 (1) I(x) R(x) (2) I(a) SS1 (3) R(y) L(y) (4) L(a) (5) R(a) (1)和和(2)及代换及代换a/x (6) R(a) (3)和和(4)及代换及代换a/yS2 (7) I(a) (1)和和(6)及代换及代换a/x (8) L(a) (3)和和(5)及代换及代换a/y S3 (9)NIL2021/8/2153单文字子句策略单文字子句策略单文字子句策略归结的效率显然是很高单文字子句策略归结的效率显然是很高的，但是它不是完备的，因为如果没的，但是它不是完备的，因为如果没有单文字子句则不能使用单文字子句有单文字子句则不能使用单文字子句策略策略2021/8/2154祖先过滤策略祖先过滤策略l当两个子句进行归结时只要满足下列两个当两个子句进行归结时只要满足下列两个条件：条件：l(1)C1与与C2中至少有一个是初始子句集中中至少有一个是初始子句集中的子句的子句l(2)如果两个子句都不是初始子句集中的如果两个子句都不是初始子句集中的子句，则一个应是另一个的祖先所谓一子句，则一个应是另一个的祖先所谓一个子句个子句(例如例如C1)是另一个子句是另一个子句(例如例如C2 )l的祖先是指的祖先是指C2 是由是由C1与别的子句归结后与别的子句归结后得到的归结式得到的归结式2021/8/2155祖先过滤策略祖先过滤策略l祖先过滤发是完备的祖先过滤发是完备的例设有子句集例设有子句集SP(x) Q(x), P(y)Q(y),P(u) Q(u), P(t) Q(t) 2021/8/2156祖先过滤策略祖先过滤策略用祖先过滤法求解过程如下：用祖先过滤法求解过程如下：1. P(x) Q(x)2. P(y)Q(y) S3. P(u) Q(u) 4.P(t) Q(t) 5. P(x) 1和及代换和及代换x/y6.Q(x) 3和及代换和及代换x/u7.P(t) 4和及代换和及代换x/t8.NIL 5和及空代换和及空代换 2021/8/2157与或形演绎推理与或形演绎推理l针针对对归归结结演演绎绎中中存存在在的的问问题题，人人们们提提出出了了多多种种非非子子句句集集定定理理证证明明的的方方法法，其其中中尼尼尔尔逊逊提提出出的的与与或或形形的的演演绎绎推推理理就就是是其其中中的的一一种种它它不不再再把把有有关关知知识识转转化化成成子子句句形形，而而是是把把领领域域知知识识及及已已知知事事实实分分别别用用蕴蕴含含式式及及与与或或形形表表示示出出来来，然然后后通通过过运运用用蕴蕴含含式式进进行行演演绎绎推推理理，从从而而证证明某个目标公式明某个目标公式2021/8/2158与或形演绎推理与或形演绎推理l与或形的演绎推理分为正向演绎、逆与或形的演绎推理分为正向演绎、逆向演绎和双向演绎，分别介绍如下：向演绎和双向演绎，分别介绍如下：l、与或形正向演绎推理、与或形正向演绎推理l它从某个已知事实出发，正向地使用蕴它从某个已知事实出发，正向地使用蕴含式（规则）进行演绎推理，直到目含式（规则）进行演绎推理，直到目标公式的某个终止条件为止。标公式的某个终止条件为止。l推理过程中需要对已知的事实、规则推理过程中需要对已知的事实、规则及目标公式的表示形式变化成要求的形及目标公式的表示形式变化成要求的形式。式。2021/8/2159与或形正向演绎推理与或形正向演绎推理l、事事实实表表达达式式的的与与或或形形变变换换及及其其树树形表示形表示l事事实实表表达达式式的的与与或或形形表表示示和和化化子子句句的的过过程程类类似似，只只是是最最后后不不必必化化成成子子句句的的合合取形式，也不必消去合取词。取形式，也不必消去合取词。2021/8/2160与或形正向演绎推理与或形正向演绎推理l例如对下述事实表达式化成与或形例如对下述事实表达式化成与或形: :l( ( x)(x)( y)Q(y,x)y)Q(y,x) (R(y)(R(y) P(y)P(y)l S(x,y)S(x,y)l解上式解上式=)(=)( y)Q(y,a)y)Q(y,a) (R(y)(R(y) P(y)P(y)l S(a,y) /*S(a,y) /*消去存在量词消去存在量词*/*/l Q(z,a) Q(z,a) ( R(y)R(y)P(y)P(y)l S(a,y) S(a,y) /*/*消消去去全全称称量量词词，使使主主要要合合取取式中的变元不重名式中的变元不重名*/ */ 2021/8/2161与或形正向演绎推理与或形正向演绎推理l事实表达式的与或树表示事实表达式的与或树表示l Q(z,a)Q(z,a) ( R(y)R(y)P(y)P(y) S(a,y) S(a,y)l Q(z,a) Q(z,a) R(y)R(y)P(y)P(y) S(a,y) S(a,y)l R(y)R(y)P(y) P(y) S(a,y) S(a,y)l R(y) R(y) P(y) P(y) 2021/8/2162与或形正向演绎推理与或形正向演绎推理l上上图图中中每每个个节节点点表表示示相相应应事事实实表表达达式式的的一一个个子子表表达达式式，叶叶节节点点为为谓谓词词公公式式中中的的文文字字，圆圆弧弧表表示示的的或或节节点点，不不带带圆圆弧弧表表示与节点示与节点2021/8/2163与或形正向演绎推理与或形正向演绎推理l如果把与或树中圆弧连接的节点视为如果把与或树中圆弧连接的节点视为具有与关系，把不用圆弧连接的节点视具有与关系，把不用圆弧连接的节点视为或关系，那麽由叶节点所组成的公式：为或关系，那麽由叶节点所组成的公式：lQ(z,a)l R(y)R(y) S(a,y) S(a,y)l P(y)P(y) S(a,y) S(a,y)l恰好是由原表达式化成的子句集恰好是由原表达式化成的子句集 l l 2021/8/2164与或形正向演绎推理与或形正向演绎推理l、规则的表示形式、规则的表示形式l在与或形正向演绎推理中，通常要求在与或形正向演绎推理中，通常要求规则具有以下形式：规则具有以下形式：lLWl其中，为单文字，为与或形其中，为单文字，为与或形l限制规则左部为单文字，是因为在进限制规则左部为单文字，是因为在进行演绎推理时，要用规则作用于表示行演绎推理时，要用规则作用于表示事实的与或树，而该与或树的叶节事实的与或树，而该与或树的叶节点都是单文字，这样可与规则的左部点都是单文字，这样可与规则的左部2021/8/2165与或形正向演绎推理与或形正向演绎推理l进行简单匹配（合一）如果领域知识进行简单匹配（合一）如果领域知识的表示形式不是所要求的形式，就要通的表示形式不是所要求的形式，就要通过变换使其满足这种形式，变换步骤为：过变换使其满足这种形式，变换步骤为：l)暂时消去蕴含符号暂时消去蕴含符号“”l2)将否定符号将否定符号“ ”伸入到单个谓词变元前伸入到单个谓词变元前l3)引入引入skolem函数消去存在量词函数消去存在量词l4)消去全称量词消去全称量词l5)恢复蕴含式：利用恢复蕴含式：利用 P Q=PQ2021/8/2166与或形正向演绎推理与或形正向演绎推理l3、目标公式的表示形式、目标公式的表示形式l在在与与或或形形正正向向演演绎绎推推理理中中要要求求目目标标公公式用子句表示。式用子句表示。l、推理过程、推理过程l应应用用规规则则进进行行推推理理的的目目的的在在于于证证明明某某个个目目标标公公式式。如如果果从从已已知知事事实实的的与与或或树树出出发发，通通过过运运用用规规则则最最终终推推出出了了欲欲证明的目标公式，则推理结束。证明的目标公式，则推理结束。2021/8/2167与或形正向演绎推理与或形正向演绎推理1)首先用与或树把已知事实表示出来；首先用与或树把已知事实表示出来；2)用规则的左部和与或树的叶节点用规则的左部和与或树的叶节点进行匹配，并将匹配成功的规则加进行匹配，并将匹配成功的规则加入到与或树中；入到与或树中；3)重复第步，直到产生一个含有目标重复第步，直到产生一个含有目标节点作为终止节点的解图为止节点作为终止节点的解图为止2021/8/2168与或形正向演绎推理与或形正向演绎推理l例设已知事实为例设已知事实为lA A B BlF F规则为规则为lr r1 1:A:AC C D Dlr r2 2:B:BE E G Gl目标公式为：目标公式为：l l证明过程如下所示：证明过程如下所示：2021/8/2169与或形正向演绎推理与或形正向演绎推理lC GC GlC D D GC D D Gl A B A Bl A B A Bl A A B B 2021/8/2170与或形正向演绎推理与或形正向演绎推理l在在上上面面的的演演绎绎树树中中双双箭箭头头代代表表的的是是匹匹配配，为为了了和和一一般般的的与与或或树树有有所所区区别别，这这里里用用它它的的倒倒置置形形式式对对于于用用谓谓词词逻逻辑辑表表示示的的已已知知事事实实和和规规则则，推推理理需需要要用用最最一一般合一进行变元的代换般合一进行变元的代换2021/8/2171与或形正向演绎推理与或形正向演绎推理l例已知的事实为例已知的事实为l P(a)P(a) Q(a)Q(a) R(a) R(a) lF F规则为：规则为：lR R1 1: : P(x)P(x)S(x)S(x)lR R2 2: Q(y): Q(y)N(y)N(y)l欲证明的目标为：欲证明的目标为：l S(z)S(z) N(z)N(z)l推理过程如下：推理过程如下：2021/8/2172 S(z) N(z) S(z) N(z) N(a) N(a) S(a) Q(y) S(a) Q(y) P(x) Q(a) R(a)P(x) Q(a) R(a) P(a) Q(a)P(a) Q(a) R(a)R(a) P(a)P(a) Q(a)Q(a) R(a)R(a)2021/8/2173与或形逆向演绎推理与或形逆向演绎推理与或形逆向演绎推理是从待证明的问与或形逆向演绎推理是从待证明的问题（目标）出发，通过逆向地使用蕴题（目标）出发，通过逆向地使用蕴含式含式( (规则规则) )进行演绎推理，直到得进行演绎推理，直到得到包含已知事实的终止条件为止到包含已知事实的终止条件为止同正向演绎推理一样，逆向演绎推理对同正向演绎推理一样，逆向演绎推理对目标、已知事实和规则也有一定要目标、已知事实和规则也有一定要求。求。2021/8/2174与或形逆向演绎推理与或形逆向演绎推理、目标公式的与或形变换、目标公式的与或形变换变换过程与正向推理相似，只是将去存变换过程与正向推理相似，只是将去存在量词的规则变成去全称量词的规则在量词的规则变成去全称量词的规则即可即可例如对如下的目标公式：例如对如下的目标公式：( y)( x)P(x)Q(x,y)(R(y) S(y)转换过程如下：转换过程如下：2021/8/2175与或形逆向演绎推理与或形逆向演绎推理( y)( x)P(x)Q(x,y)(R(y) S(y)( y) P(f(y) Q(f(y),y) ( R(y) S(y)= P(f(y) Q(f(y),y) R(y)S(y)= P(f(z) Q(f(y),y) R(f(y)S(y)2021/8/2176与或形逆向演绎推理与或形逆向演绎推理l注意变换时应使各主要的析取式变元不注意变换时应使各主要的析取式变元不重名（采用改名原则）重名（采用改名原则）l目标公式的与或树和正向推理形式的目标公式的与或树和正向推理形式的事实与或树略有不同，在这里带弧的事实与或树略有不同，在这里带弧的表示与节点，不带弧的表示或节点表示与节点，不带弧的表示或节点l该例的与或树如下所示该例的与或树如下所示2021/8/2177l P(f(z) Q(f(y),y) R(f(y)S(y)l P(f(z)Q(f(y),y) R(f(y)S(y)l Q(f(y),y) R(f(y)S(y)l R(f(y) S(y)2021/8/2178与或形逆向演绎推理与或形逆向演绎推理l把上图中的叶节点用它们的合取及析取把上图中的叶节点用它们的合取及析取关系连接起来，就可得到目标公式的三关系连接起来，就可得到目标公式的三个子目标个子目标l P(f(z)l Q(f(y),y) R(f(y) l Q(f(y),y) S(y) l它们之间是或的关系它们之间是或的关系2021/8/2179与或形逆向演绎推理与或形逆向演绎推理l、规则的表示、规则的表示l规则的表示形式为规则的表示形式为ll其中为任一与或形公式；为文字。其中为任一与或形公式；为文字。l如果已知的规则不符合所要求的形式，如果已知的规则不符合所要求的形式，可用与转换规则类似的方法去转换，可用与转换规则类似的方法去转换，特别对特别对l1 22021/8/2180与或形逆向演绎推理与或形逆向演绎推理l这样的蕴含式可化为两个规则：这样的蕴含式可化为两个规则：l1l2l、事实的表示形式、事实的表示形式l要求事实是文字的合取式，即形如要求事实是文字的合取式，即形如lF1 F2 Fnl在问题求解中，每个在问题求解中，每个Fi都可单独起作用，都可单独起作用，因此可把上述公式表示为事实的集合因此可把上述公式表示为事实的集合lF1,F2, , Fn2021/8/2181与或形逆向演绎推理与或形逆向演绎推理l4、推理过程、推理过程l1)首先用与或树把目标公式表示出来；首先用与或树把目标公式表示出来；l2)用规则的右部和与或的叶节点进行匹配，用规则的右部和与或的叶节点进行匹配，并将匹配成功的规则加入到与或树中；并将匹配成功的规则加入到与或树中；l3)重复进行第步，直到产生某个终止的事实重复进行第步，直到产生某个终止的事实节点上的一致解图为止这里所说的一致解图节点上的一致解图为止这里所说的一致解图是指在推理过程中所用的代换是一致的是指在推理过程中所用的代换是一致的2021/8/2182与或形逆向演绎推理与或形逆向演绎推理l例设有如下事实及规则例设有如下事实及规则l事实：事实：lf1:DOG(fido) fido是狗是狗lf2: BARKS(fido) fido不吠叫不吠叫lf3:WAGS-TAIL(fido) fido摇尾巴摇尾巴lf4:MEOWS(myrtle) myrtle咪咪叫咪咪叫2021/8/2183与或形逆向演绎推理与或形逆向演绎推理l规则：规则：lr1: (WAGS-TAIL(x1) DOG(x1)lFRENDLY(x1) /*狗以摇尾巴表示友好狗以摇尾巴表示友好*/lr2: (FRENDLY(x2) BARKS(x2) l AFRAID(y2,x2) *友好且不吠叫的狗友好且不吠叫的狗不可怕不可怕*/lr3: DOG(x3) ANIMAL(x3)2021/8/2184与或形逆向演绎推理与或形逆向演绎推理lr4: CAT(x4) ANIMAL(x4)lr5: MEOWS(x5)CAT(x5)l现在的问题是：是否有这样的一条猫和现在的问题是：是否有这样的一条猫和一条狗，而且这只猫不怕这条狗？一条狗，而且这只猫不怕这条狗？l该问题的目标公式为：该问题的目标公式为：l( x)( y)CAT(x) DOG(y) AFRAID(x,y) 2021/8/2185lCAT(x) DOG(y) AFRAID(x,y)l lCAT(x) DOG(y) AFRAID(x,y) lCAT(x5) DOG(fido) AFRAID(y2,x2) lMEOWS(x) BARKS(y) FRENDLY(y)lMEOWS(myrtle) BARKS(fido) FRENDLY(x1)l WAGS-TAIL(y) DOG(y)l WAGS-TAIL(fido) DOG(fido)2021/8/2186与或形逆向演绎推理与或形逆向演绎推理l推理过程得到的是一致解图图中有八推理过程得到的是一致解图图中有八条匹配弧，每条弧上都应该有一个代换条匹配弧，每条弧上都应该有一个代换l终止在事实节点上的代换为终止在事实节点上的代换为lmyrtle/x和和fido/y 把它们应用到目标把它们应用到目标公式，就得到了该问题的解：公式，就得到了该问题的解：lCAT(myrtle) DOG(fido) lAFRAID(myrtle, fido)l即有一只名叫即有一只名叫myrtle的猫和一条名叫的猫和一条名叫fido的狗并且这只猫不怕这只狗的狗并且这只猫不怕这只狗2021/8/2187代换的一致性及剪枝策略代换的一致性及剪枝策略l、代换的一致性、代换的一致性l无无论论是是正正向向推推理理还还是是逆逆向向推推理理都都要要求求推推理理过过程程中中所所使使用用的的代代换换具具有有一一致致性性。代代换一致性的定义如下：换一致性的定义如下：l设有代换集合设有代换集合l = 1 , 2, n中第中第i个代换个代换 i为为l i=ti1/xi1, ti2/xi2, , tim(i)/xim(i)l其中其中tij是项是项xij是变元是变元(j=1,2 , , m(i)2021/8/2188代换的一致性及剪枝策略代换的一致性及剪枝策略l则代换集则代换集 是一致的充要条件是如下两个是一致的充要条件是如下两个元组元组lT=t11,t12,t1m(1),t21, t22,t2m(2),tnm(n)lX=x11,x12,x1m(1),x21,x22,x2m(2),xnm(n)l可合一可合一2021/8/2189代换的一致性及剪枝策略代换的一致性及剪枝策略l)设设 1x/y, 2y/z,则则 1和和 2是是一致的一致的l2)设设 1f(g(x1)/x3 ,f(x2)/x4,l 2x4/x3,g(x1)/x2 ,则则 1和和 2是一致是一致的的2021/8/2190代换的一致性及剪枝策略代换的一致性及剪枝策略l3)设设 1a/x, 2b/x,则则 1和和 2是不一是不一致的致的l4)设设 1g(y)/x, 2f(x)/y,则则 1和和 2是是不一致的不一致的l通过例子我们可以看出，只要构造出两通过例子我们可以看出，只要构造出两个代换的项集和变元集，项集和变元集个代换的项集和变元集，项集和变元集中有相同元素，则是一致的，否则就是中有相同元素，则是一致的，否则就是不一致的不一致的2021/8/2191代换的一致性及剪枝策略代换的一致性及剪枝策略l、剪枝策略、剪枝策略l在与或形的演绎推理中要不断地用在与或形的演绎推理中要不断地用规则的左部（正向推理）或规则的右规则的左部（正向推理）或规则的右部（逆向推理）和与或树的叶节点进部（逆向推理）和与或树的叶节点进行匹配（合一），在每一步上可匹配的行匹配（合一），在每一步上可匹配的规则可能不止一条，为了得到一致解图，规则可能不止一条，为了得到一致解图，应该选哪一条，以逆向推理来说明控制应该选哪一条，以逆向推理来说明控制策略，即剪枝策略策略，即剪枝策略2021/8/2192代换的一致性及剪枝策略代换的一致性及剪枝策略l剪枝策略的基本思想是：每当选一条规剪枝策略的基本思想是：每当选一条规则时就进行一次一致性检查，如果当前则时就进行一次一致性检查，如果当前的部分解图是一致的，则继续向下扩展，的部分解图是一致的，则继续向下扩展，否则就放弃该规则的而选用其它的候选否则就放弃该规则的而选用其它的候选规则由于应用该方法在使用每一条规规则由于应用该方法在使用每一条规则时都进行了一致性检查，所以最终得则时都进行了一致性检查，所以最终得到的解图必然是一致的由于该方法尽到的解图必然是一致的由于该方法尽早地发现并剪除了不一致的分支，从而早地发现并剪除了不一致的分支，从而避免了大的返工避免了大的返工2021/8/2193代换的一致性及剪枝策略代换的一致性及剪枝策略l例如，设当前的与或树如图例如，设当前的与或树如图a所示，可所示，可用的规则有用的规则有lr1:S(z)P(b)lr2:R(y)P(y)l若首先选用若首先选用r1则得到代换集则得到代换集a/x,b/yl显然它是不一致的因而必须放弃这一显然它是不一致的因而必须放弃这一选择接着选选择接着选r2得到代换集得到代换集a/x,x/y,这是这是一致的，所以把一致的，所以把r2用于推理，并把它加入用于推理，并把它加入到目标与或树中如图到目标与或树中如图b所示所示2021/8/2194代换的一致性及剪枝策略代换的一致性及剪枝策略l P(x) Q(x) P(x) Q(x)l P(x) Q(x) P(x) Q(x) l Q(a) P(y) Q(a) l a图图 R(x)llb图图 2021/8/2195代换的一致性及剪枝策略代换的一致性及剪枝策略l与或形演绎推理的优点是不必把公式与或形演绎推理的优点是不必把公式化为子句集，保留了连接词化为子句集，保留了连接词，这就可，这就可直观地表达出因果关系，比较自然直观地表达出因果关系，比较自然l但它在使用正向推理时要求把目标表达但它在使用正向推理时要求把目标表达式限制为文字的析取，而在逆向推理时式限制为文字的析取，而在逆向推理时又限制事实表达式为文字的合取式又限制事实表达式为文字的合取式2021/8/2196l作业：作业：153 4.14lP154 4.15,4.16,4.172021/8/2197部分资料从网络收集整理而来，供大家参考，感谢您的关注！