1、第章经典逻辑推理第章经典逻辑推理、基本概念、基本概念、自然演绎推理、自然演绎推理、归结演绎推理、归结演绎推理、与或形演绎推理、与或形演绎推理1基本概念基本概念l何为推理？何为推理？l从已知的事实出发，不断运用已掌握的从已知的事实出发，不断运用已掌握的（知识库中的）知识推出或归纳出新的（知识库中的）知识推出或归纳出新的事实（包括目标结论）的过程称为推理。事实（包括目标结论）的过程称为推理。人工智能中推理是由程序实现的，称这人工智能中推理是由程序实现的，称这个程序为推理机。个程序为推理机。2推理方式及其分类推理方式及其分类l人工智能作为对人类智能的模拟，有多人工智能作为对人类智能的模拟，有多种推理
2、方式。它们是：种推理方式。它们是：l、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l、确定性推理、不确定性推理、确定性推理、不确定性推理l、单调推理、非单调推理、单调推理、非单调推理l、启发式推理、非启发式推理、启发式推理、非启发式推理l、基于知识的推理、统计推理、直觉、基于知识的推理、统计推理、直觉推理。推理。l分别解释如下：分别解释如下：3、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l所谓演绎推理是从全称判断推导出特称所谓演绎推理是从全称判断推导出特称判断的过程，是从一般到个别的推理。判断的过程，是从一般到个别的推理。经常用的是三段论式，它包括：经常用的是三段
3、论式，它包括：大前提：已知的一般性知识或假设；大前提：已知的一般性知识或假设；小前提：具体情况或个别事实；小前提：具体情况或个别事实；结论：由大前提推出的适合小前提所示情结论：由大前提推出的适合小前提所示情况的新判断。况的新判断。4、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l例如有如下三个判断：例如有如下三个判断：l（）足球运动员的身体都是强壮的；（）足球运动员的身体都是强壮的；l（）高波是一名足球运动员；（）高波是一名足球运动员；l（）所以，高波的身体是强壮的。（）所以，高波的身体是强壮的。l其中（）是大前提，（）是小前提其中（）是大前提，（）是小前提l（）是经演绎推出的结
4、论。（）是经演绎推出的结论。l只要大前提和小前提是正确的，那麽由只要大前提和小前提是正确的，那麽由它们推出的结论就是正确的。它们推出的结论就是正确的。5、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l演绎推理是人工智能中的一种重要推理演绎推理是人工智能中的一种重要推理方式，目前研制成功的各类智能系统中，方式，目前研制成功的各类智能系统中，大多是用演绎推理实现的。大多是用演绎推理实现的。6、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理l归纳推理是从足够多的事例中归纳出一归纳推理是从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到般性结论的推理过程，是一种从个别
5、到一般的推理。例如，某厂进行产品质量一般的推理。例如，某厂进行产品质量检查，如果对每一件产品都进行了检查，检查，如果对每一件产品都进行了检查，并且都是合格的，则推导出结论：该厂并且都是合格的，则推导出结论：该厂生产的产品是合格的。并称这种推理为生产的产品是合格的。并称这种推理为完全归纳推理。完全归纳推理。7、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理如果是随机地抽查部分产品，并且它们如果是随机地抽查部分产品，并且它们是合格的，则得出结论该厂的产品是是合格的，则得出结论该厂的产品是合格的，这种推理称为不完全归纳推合格的，这种推理称为不完全归纳推理。理。默认推理又称为缺省推理，它是
6、在知识默认推理又称为缺省推理，它是在知识不完全的情况下假设某些条件已经具不完全的情况下假设某些条件已经具备所进行的推理。例如，在条件已备所进行的推理。例如，在条件已成立的情况下，如果没有足够的证据成立的情况下，如果没有足够的证据能证明条件不成立，则默认成立，能证明条件不成立，则默认成立，并在默认前提下进行推理，推导并在默认前提下进行推理，推导8、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理 出某个结论来。由于这种推理允许默认某些条件是成立出某个结论来。由于这种推理允许默认某些条件是成立的，这就摆脱了需要知道全部有关事实才能进行推理的，这就摆脱了需要知道全部有关事实才能进行推理的要
7、求，使得在知识不完全的情况下也能进行推理。的要求，使得在知识不完全的情况下也能进行推理。在默认推理过程中，如果到某一时刻发现原先所做的在默认推理过程中，如果到某一时刻发现原先所做的默认不正确，则可以撤消默认推理和所推出的结论，默认不正确，则可以撤消默认推理和所推出的结论，并重新按新情况进行推理。并重新按新情况进行推理。9、确定性推理、不确定性推理、确定性推理、不确定性推理l所谓确定性推理是指推理时所用的所谓确定性推理是指推理时所用的知识都是精确的，推出的结论也是知识都是精确的，推出的结论也是确定的，是真或者是假。经典逻辑确定的，是真或者是假。经典逻辑推理就属于这一种。推理就属于这一种。l不确定
8、性推理是指推理时所用的知不确定性推理是指推理时所用的知识不都是精确的，推出的结论也不识不都是精确的，推出的结论也不完全是肯定的，其真值位于真与假完全是肯定的，其真值位于真与假之间，命题的外延模糊不清。之间，命题的外延模糊不清。10、确定性推理、不确定性推理、确定性推理、不确定性推理 这里，我们特别强调的是不确定性推理。因为，这里，我们特别强调的是不确定性推理。因为，人类思维活动的特征经常是在知识不完全的情人类思维活动的特征经常是在知识不完全的情况下进行多方位的思考及推理的。因此，要使况下进行多方位的思考及推理的。因此，要使计算机模拟人类的思维活动，就必须使它具有计算机模拟人类的思维活动，就必须
9、使它具有不确定性推理的能力。不确定性推理的能力。11、单调推理、非单调推理、单调推理、非单调推理l所谓单调推理是指在推理的过程中随着所谓单调推理是指在推理的过程中随着推理的向前推进及新知识的加入，推出推理的向前推进及新知识的加入，推出的结论是单调递增的趋势，并且越来越的结论是单调递增的趋势，并且越来越接近目标，推理过程不会出现反复的情接近目标，推理过程不会出现反复的情况，即不会因新知识的加入否定了前面况，即不会因新知识的加入否定了前面推出的结论，从而使推理又退回到前面推出的结论，从而使推理又退回到前面的某一步。经典逻辑演绎推理属于这一的某一步。经典逻辑演绎推理属于这一种。种。12、启发式推理、
10、非启发式推理、启发式推理、非启发式推理l若按推理中是否使用与问题有关的启发若按推理中是否使用与问题有关的启发性知识，推理可分为启发式推理和非启性知识，推理可分为启发式推理和非启发式推理。发式推理。l所谓启发性知识是指与问题有关并且能所谓启发性知识是指与问题有关并且能加快推理进程、求得问题最优解的知识。加快推理进程、求得问题最优解的知识。13、基于知识的推理、统计推理、直觉推、基于知识的推理、统计推理、直觉推理理l如果从方法论的角度来划分，推理可分如果从方法论的角度来划分，推理可分为基于知识的推理、统计推理和直觉推为基于知识的推理、统计推理和直觉推理。理。l顾名思义，所谓基于知识的推理就是根顾名
11、思义，所谓基于知识的推理就是根据已掌握的事实，通过运用知识进行推据已掌握的事实，通过运用知识进行推理。理。l统计推理是根据对某事物的数据统计进统计推理是根据对某事物的数据统计进行推理。例如，对农作物的产量进行统行推理。例如，对农作物的产量进行统计，从而得出是否增产的结论，从而找计，从而得出是否增产的结论，从而找14、基于知识的推理、统计推理、直觉推理、基于知识的推理、统计推理、直觉推理l出增产和减产的原因。就是运用了统计出增产和减产的原因。就是运用了统计推理。推理。l直觉推理又称常识性推理，是根据常识直觉推理又称常识性推理，是根据常识进行的推理。例如，当你从某建筑物下进行的推理。例如，当你从某
12、建筑物下走过时，猛然发现有一物体坠落，这时走过时，猛然发现有一物体坠落，这时你立即就会意识到这有危险，并立即躲你立即就会意识到这有危险，并立即躲开，这就是使用了直觉推理。目前直觉开，这就是使用了直觉推理。目前直觉推理在计算机上的实现还是一件很困难推理在计算机上的实现还是一件很困难的工作。的工作。15推理的控制策略推理的控制策略l推理的控制策略主要包括推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。l推理方向用于确定推理的驱动方式，分为正向推理、逆乡向推理、混合推理及双向推理四种。16正向推理正向推理l正向推理也称数据驱动推理，前向链推正向推理也称数据驱动推理，前向链推理、模式制导推理及
13、前件推理等。理、模式制导推理及前件推理等。l正向推理过程的算法描述如下：正向推理过程的算法描述如下：l、将用户提供的初始已知事实送入数、将用户提供的初始已知事实送入数据库据库DB;DB;l2 2、检查数据库、检查数据库DBDB中是否包含问题的解，中是否包含问题的解，若有则求解结束，成功退出；否则执行若有则求解结束，成功退出；否则执行下一步；下一步；17正向推理正向推理根据数据库DB中的已知事实，扫描知识库KB，检查KB中是否有可适用的知识，若有则转，否则转；把KB中所有的适用知识都选出来，构成可适用的知识集KS；若KS不空，则按某种冲突消解策略从中选出一条知识进行推理，并将推出的新事实加入DB
14、中，然后转；若KS空，转；18正向推理正向推理询问用户是否可以进一步补充新的事实，若可补充，则将补充的事实加入DB中，转，否则表示求不出解，失败退出算法的流程示意图如115的图所示为了实现正向推理，还有很多实际问题需要解决，后面将陆续介绍19逆向推理逆向推理l逆向推理的思想是首先假设一个目标，逆向推理的思想是首先假设一个目标，然后寻找支持该假设的证据，若所需的然后寻找支持该假设的证据，若所需的证据都能找到，则说明假设是成立的；证据都能找到，则说明假设是成立的；若实在找不到证据时，说明原假设不成若实在找不到证据时，说明原假设不成立，此时需另做假设推理过程的算法立，此时需另做假设推理过程的算法如下
15、所示如下所示20逆向推理逆向推理l提出要求证的目标（假设目标）；提出要求证的目标（假设目标）；l检查该目标是否已在数据库中，若在，检查该目标是否已在数据库中，若在，则该目标成立，成功退出或者对下一目则该目标成立，成功退出或者对下一目标进行检验；否则，转下一步；标进行检验；否则，转下一步；l判断该目标是否是证据，即它是否是判断该目标是否是证据，即它是否是由用户证实的原始事实，若是，则询问由用户证实的原始事实，若是，则询问用户；否则转下一步用户；否则转下一步l在知识库中找出所有能导出该目标的在知识库中找出所有能导出该目标的知识，形成适用知识集知识，形成适用知识集KSKS，转下一步；，转下一步；21
16、逆向推理逆向推理l从从KSKS中选出一条知识，并将该知识的中选出一条知识，并将该知识的运用条件作为新的假设目标，然后转运用条件作为新的假设目标，然后转l算法的示意图如算法的示意图如116116的图所示的图所示l22双向推理双向推理l混合推理就是在推理过程中合理地使用正混合推理就是在推理过程中合理地使用正向推理和逆向推理向推理和逆向推理l混合推理的算法示意图如混合推理的算法示意图如P11P11的图的图所示所示l23求解策略和限制策略求解策略和限制策略 所谓推理的求解策略是指只求一个解还是求所有所谓推理的求解策略是指只求一个解还是求所有解和最优解等解和最优解等为了防止无穷的推理过程为了防止无穷的推
17、理过程,以及由于推理过程太长以及由于推理过程太长增加时间及空间的复杂性，可在控制策略中指增加时间及空间的复杂性，可在控制策略中指定推理的限制条件，以对推理的深度、宽度、定推理的限制条件，以对推理的深度、宽度、时间、空间等限制。时间、空间等限制。24模式匹配模式匹配l模式匹配是推理中必须进行的一项重要工作，模式匹配是推理中必须进行的一项重要工作，因为只有经过模式匹配才能从知识库中选出当因为只有经过模式匹配才能从知识库中选出当前适用的知识，才能进行推理。前适用的知识，才能进行推理。l模式匹配可以有确定性匹配和不确定性匹配良模式匹配可以有确定性匹配和不确定性匹配良种。种。l所谓确定性匹配是指两个模式
18、完全一样，或者所谓确定性匹配是指两个模式完全一样，或者通过代换后变得完全一致。所谓不确定性匹配通过代换后变得完全一致。所谓不确定性匹配是指两个知识模式不完全一样，但从总体上看是指两个知识模式不完全一样，但从总体上看它们的相似程度又落在规定的限度内。它们的相似程度又落在规定的限度内。l无论是确定性匹配无论是确定性匹配 还是不确定性匹配都需要进还是不确定性匹配都需要进行变量的代换。行变量的代换。25模式匹配模式匹配l例如设有如下两个知识模式：例如设有如下两个知识模式：l1 1:father(:father(李四，李小四）李四，李小四）and man(and man(李小四李小四)l2 2:fath
19、er(x,y)and man(y):father(x,y)and man(y)l若用李四代换若用李四代换x,x,用李小四代换用李小四代换y y，则，则1 1与与l就变得完全一样若用这两个知识模就变得完全一样若用这两个知识模式进行匹配，则是确定性匹配，也称完式进行匹配，则是确定性匹配，也称完全匹配或精确匹配全匹配或精确匹配26模式匹配模式匹配l下面我们给出代换的概念：下面我们给出代换的概念：l代换是形如代换是形如lt t1 1/x/x1 1,t,t2 2/x/x2 2,t,tn n/x/xn n 的有限集合。其中，的有限集合。其中，l t t1 1，t t2 2，,t,tn n是项，是项，lx
20、x1.1.，x x2 2,x,xn n是互不相同的变元；是互不相同的变元；lt ti i/x/xi i表示用项表示用项t ti i代换变量代换变量x xi i，不允许，不允许t ti i 和和x xi i相同，也不允许相同，也不允许x xi i循环的出现在另一个循环的出现在另一个t tj j中。中。27模式匹配模式匹配什麽是项呢？什麽是项呢？常可以作项，变量也可以作项，函数常可以作项，变量也可以作项，函数表达式可以作项。表达式可以作项。28模式匹配模式匹配l例如例如a/x,f(b)/y,w/za/x,f(b)/y,w/z就是一个代换，但是就是一个代换，但是lg(y)/x,f(x)/yg(y)/
21、x,f(x)/y则不是一个代换，因为代则不是一个代换，因为代换的目的是使某些变元被另外的变元、换的目的是使某些变元被另外的变元、常量、或函数表达式取代，使之不再在常量、或函数表达式取代，使之不再在公式中出现，而公式中出现，而g(y)/x,f(x)/yg(y)/x,f(x)/y在在x x与与y y之间之间出现了循环代换的情况，它既没有消去出现了循环代换的情况，它既没有消去x,x,也没有消去也没有消去y y。29模式匹配模式匹配l如果把它改为如果把它改为g(a)/x,f(x)/yg(a)/x,f(x)/y就可就可以了，它将把公式中的以了，它将把公式中的x x代换成代换成g(a),yg(a),y代换
22、成代换成f(g(a),f(g(a),从而消去了变从而消去了变量量x x和和y y。30模式匹配模式匹配l下面给出一个公式的代换例式的概念：下面给出一个公式的代换例式的概念：l设设F F是一个公式，是一个公式，是一个代换，记是一个代换，记F F 为为公式公式F F在在 下的代换例式，它是将公式下的代换例式，它是将公式F F中中的变量用的变量用 中的项作代换的结果。例如有中的项作代换的结果。例如有公式（公式（x,y,f(y)x,y,f(y)和代换和代换=a/x,b/y=a/x,b/yl于是于是F F =（a,b,f(b)a,b,f(b)31模式匹配模式匹配l下面给出复合代换的定义下面给出复合代换的
23、定义l设有两个代换设有两个代换 和和，其中，其中l =t t1 1/x/x1 1,t,t2 2/x/x2 2,t,tn n/x/xn n l =u=u1 1/y/y1 1,u,u2 2/y/y2 2,u,um m/y/ym m 则则 此两个代换的复合此两个代换的复合也是一个代换，它是从也是一个代换，它是从 l t t1 1 /x/x1 1,t,t2 2 /x/x2 2,t,tn n /x/xn n，u u1 1/y/y1 1,u,u2 2/y/y2 2,u,um m/y/ym m l中删去如下两种元素：中删去如下两种元素：lt ti i /x/xi i 当当t ti i =x=xi i 时时l
24、u ui i/y/yi i 当当y yi i x x1.1.，x x2 2,x,xn n 时，后剩下的元素时，后剩下的元素构成的集合，记为构成的集合，记为 。32模式匹配模式匹配l例如设有如下代换：例如设有如下代换：l =f(y)/x,z/y=f(y)/x,z/yl=a/x,b/y,y/z=a/x,b/y,y/zl求求 和和 l解：我们先来求解：我们先来求 33模式匹配模式匹配l =f(y)=f(y)/x,z /x,z /y,a/x,b/y,y/z/y,a/x,b/y,y/zl=f(b)/x,y/y,a/x,b/y,y/z=f(b)/x,y/y,a/x,b/y,y/z去掉不合法的去掉不合法的元
25、素：元素：ly/yy/y（条件）（条件）l a/x,b/ya/x,b/y（条件）（条件）l于是于是 f(b)/x,y/zf(b)/x,y/z34模式匹配模式匹配l再来求再来求 ，同样先求，同样先求 l a a /x,b/x,b /y,y/y,y /z,f(y)/x,z/y/z,f(y)/x,z/yl=a/x,b/y,z/z,f(y)/x,z/y=a/x,b/y,z/z,f(y)/x,z/yl去掉不合法的元素去掉不合法的元素z/z,f(y)/x,z/yz/z,f(y)/x,z/y得得l =a/x,b/y=a/x,b/yl显然代换的复合运算是不可交换的。并显然代换的复合运算是不可交换的。并且对任何
26、代换且对任何代换 存在空代换存在空代换，并且，并且l 35模式匹配模式匹配l下面我们给出合一的概念：下面我们给出合一的概念：l设有公式集设有公式集F=FF=F1 1，F F2 2，,F,Fn n,若存在一若存在一个代换个代换 使得使得F F1 1 =F=F2 2 =F=Fn n l则称则称 为公式集为公式集F F的一个合一，且称的一个合一，且称lF F1 1，F F2 2，,F,Fn n是可合一的。是可合一的。36模式匹配模式匹配l例如例如F=PF=P（x,y),x,y),=a/x,g(a)/y=a/x,g(a)/yl求公式求公式F F在在 下的例式为下的例式为lF F =P=P（a,g(a)
27、a,g(a)l对于公式集对于公式集F=PF=P（x,yx,y，f(y),P(a,g(x),z)f(y),P(a,g(x),z)则则l=a/x,g(a)/y=a/x,g(a)/y，f(g(a)/zf(g(a)/z是公式是公式F F的一个的一个合一。合一。37模式匹配模式匹配l一个公式的合一一般是不唯一的。但如一个公式的合一一般是不唯一的。但如果果l 是公式集是公式集F F的一个合一，若对任一个合的一个合一，若对任一个合一一 都存在一个代换都存在一个代换 使得：使得：=则称则称 是一个最一般合一。是一个最一般合一。38模式匹配模式匹配l最一般合一是唯一的。若用最一般合一最一般合一是唯一的。若用最一
28、般合一去代换那些可合一的谓词公式，可使它去代换那些可合一的谓词公式，可使它们变成完全一致的公式。由此可知，为们变成完全一致的公式。由此可知，为了使两个知识模式匹配，可用其最一般了使两个知识模式匹配，可用其最一般合一对它们进行代换。合一对它们进行代换。39模式匹配模式匹配l为了求最一般合一要用到一个差异集为了求最一般合一要用到一个差异集（也有叫分歧集的）的概念。设有如下（也有叫分歧集的）的概念。设有如下两个谓词公式两个谓词公式lF F1 1：P(x,y,z)P(x,y,z)lF F2 2:P(x,f(a),h(b):P(x,f(a),h(b)l分别从分别从F F1 1 与与F F2 2的第一个符
29、号开始，逐个的第一个符号开始，逐个向右比较，此时发现向右比较，此时发现F F1 1中的中的y y与与F F2 2中的中的f(a)f(a)不同，它们构成了一个差异集：不同，它们构成了一个差异集：D D1 1=y,f(a),=y,f(a),40模式匹配模式匹配l当继续向右比较时，又发现当继续向右比较时，又发现F F1 1中与中与F F2 2中的中的h(b)h(b)不同，于是又得到一个差异集：不同，于是又得到一个差异集：lD D2 2=z,h(b)=z,h(b)。下面给出求最一般合一的。下面给出求最一般合一的算法：算法：l（1 1）令）令K=0K=0，F Fk k=F,=F,k k=这里，这里，F
30、F是欲求是欲求其最一般合一的公式集，其最一般合一的公式集，是空代换，它是空代换，它表示不做代换。表示不做代换。l（2 2）若）若F Fk k只含一个表达式，则算法停，只含一个表达式，则算法停，k k就是所求最一般合一。就是所求最一般合一。41模式匹配模式匹配l（3 3）找出）找出F Fk k的差异集的差异集D Dk k。l（4 4）若）若D Dk k中存在元素中存在元素x xk k和和t tk k,其中其中x xk k是变是变元，元，t tk k是项是项,且且x xk k不在不在t tk k中出现，则置：中出现，则置：l k+1k+1=kk t tk k/x xk k lF Fk+1k+1=F
31、=Fk k t tk k/x xk k lK=k+1K=k+1转（转（2 2）l（5 5）算法停，）算法停，F F的最一般合一不存在。的最一般合一不存在。42模式匹配模式匹配l例如，设例如，设lF=P(a,x,f(g(y),P(z,f(z),f(u)F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般求其最一般合一合一l(1)(1)令令 0 0=,F,F0 0=F,=F,因因F F0 0中含有两个表达式，中含有两个表达式，所以所以 0 0不是最一般合一。不是最一般合一。l(2)(2)差异集差异集D D0 0=a,z,=a,z,l(3)(3)1 1=0 0 a/z,a/z,lF F
32、1 1=P(a,x,f(g(y),P(a,f(a),f(u)P(a,x,f(g(y),P(a,f(a),f(u)43模式匹配模式匹配(4)D(4)D1 1=x,f(a)=x,f(a)(5)(5)2 2=1 1 f(a)/x=a/z,f(a)/x,f(a)/x=a/z,f(a)/x,lF F2 2=F=F1 1 f(a)/x f(a)/xl=P(a,P(a,f(a)f(a),f(g(y),P(a,f(a),f(u),f(g(y),P(a,f(a),f(u)。l(6)(6)D D2 2=g(y)g(y),u,u。l(7)(7)3 3=2 2 g(y)g(y)/u/u=a/z,f(a)/x,=a/z
33、,f(a)/x,g(y)g(y)/u/u。44模式匹配模式匹配l(8)(8)F F3 3=F=F2 2 g(y)g(y)/u/ul =P(a,P(a,f(a)f(a),f(g(y),P(a,f(a),f(g(y),f(g(y),P(a,f(a),f(g(y)/u/u)l =P(a,P(a,f(a)f(a),f(g(y),f(g(y)l因为因为F F3 3只含一个表达式了，所以只含一个表达式了，所以 3 3就是最就是最一般合一，即一般合一，即la/z,f(a)/x,a/z,f(a)/x,g(y)g(y)/u/u 是最一般合一。是最一般合一。45冲突消解策略冲突消解策略l接下来我们学习冲突消解方面
34、的概念：接下来我们学习冲突消解方面的概念：l在推理的过程中，系统不断的用以知的在推理的过程中，系统不断的用以知的事实与知识库中的知识进行匹配，此时事实与知识库中的知识进行匹配，此时可能发生如下三种情况：可能发生如下三种情况：l（1 1）已知事实不能与知识库中的任何知）已知事实不能与知识库中的任何知识匹配成功。识匹配成功。l（2 2）已知事实恰好与知识库中的一条知）已知事实恰好与知识库中的一条知识匹配成功。识匹配成功。46冲突消解策略冲突消解策略l（3 3）已知事实可与知识库中的多条知识）已知事实可与知识库中的多条知识匹配成功。匹配成功。l以上三种情况中，第一种情况使得推理以上三种情况中，第一种
35、情况使得推理无法进行下去，第三种情况则出现冲突，无法进行下去，第三种情况则出现冲突，需要按一定的策略解决冲突。需要按一定的策略解决冲突。47冲突消解策略冲突消解策略l目前解决冲突的策略有多种，其基本思目前解决冲突的策略有多种，其基本思想都是对知识进行排序，常用的有以下想都是对知识进行排序，常用的有以下几种：几种：l1 1、按针对性排序、按针对性排序l设有如下两条产生式规则：设有如下两条产生式规则：lr r1:1:IF AIF A1 1 and A and A2 2 and A and An n THEN H THEN H1 1lr r2:2:IF BIF B1 1 and B and B2 2
36、 and B and Bm m THEN H THEN H2 248冲突消解策略冲突消解策略l如果存在最一般合一，使得如果存在最一般合一，使得r r1 1中每一个中每一个A Ai i都可变成相应的都可变成相应的B Bi i ，即，即r r2 2中除了包含中除了包含r r1 1的的全部条件全部条件A A1 1,A,A2 2,A,An n外，还包含其它条外，还包含其它条件，则称件，则称r r2 2 比比 r r1 1有更大的针对性，有更大的针对性，r r1 1 比比r r2 2 有更大的通用性。有更大的通用性。l一般选用针对性较强的产生式规则。一般选用针对性较强的产生式规则。(即即应选用应选用r
37、r2 2)因为它要求的条件较多，其结因为它要求的条件较多，其结论一般更论一般更 接近目标，一旦得到满足，可接近目标，一旦得到满足，可缩短推理过程。缩短推理过程。49冲突消解策略冲突消解策略l2 2、按已知事实的新鲜性排序、按已知事实的新鲜性排序l在产生式系统推理过程中，每应用一条在产生式系统推理过程中，每应用一条产生式规则就会得到一个或多个结论，产生式规则就会得到一个或多个结论，数据库就会增加新的事实。把数据库后数据库就会增加新的事实。把数据库后生成的事实称为生成的事实称为 新鲜的事实，即后生成新鲜的事实，即后生成的事实比先生成的事实具有较大的新鲜的事实比先生成的事实具有较大的新鲜性。设规则性
38、。设规则r r1 1可与事实组可与事实组A A匹配成功，规匹配成功，规则则r r2 2可与事实组可与事实组B B匹配成功，则匹配成功，则A A与与B B中哪中哪一组新鲜与它匹配的产生式规则就先被一组新鲜与它匹配的产生式规则就先被应用。应用。50冲突消解策略冲突消解策略l3 3、按匹配排序、按匹配排序l在不确定性匹配中，为了确定两个知识在不确定性匹配中，为了确定两个知识模式是否可以匹配，需要计算这两个模模式是否可以匹配，需要计算这两个模式的相似程度，当其相似程度达到某个式的相似程度，当其相似程度达到某个预定的值时，就认为它们是可匹配的。预定的值时，就认为它们是可匹配的。若两条规则均按匹配度匹配成
39、功，则匹若两条规则均按匹配度匹配成功，则匹配度大的那条规则优先启用。配度大的那条规则优先启用。51冲突消解策略冲突消解策略l4 4、根据领域问题的特点排序、根据领域问题的特点排序l某些领域问题可事先知道它的某些特性，某些领域问题可事先知道它的某些特性，可根据这些特性把知识排成固定的顺序。可根据这些特性把知识排成固定的顺序。先匹配成功的优先启用的原则。先匹配成功的优先启用的原则。52冲突消解策略冲突消解策略l5 5、按上下文限制排序、按上下文限制排序l把产生式规则按它们所描述的上下文分把产生式规则按它们所描述的上下文分成若干组，在不同的条件下，只能从相成若干组，在不同的条件下，只能从相应的组中选
40、取有关的产生式规则。这样应的组中选取有关的产生式规则。这样可以减少冲突的发生可以减少冲突的发生53冲突消解策略冲突消解策略l6 6、按冗余限制排序、按冗余限制排序l若哪一条产生式规则被应用后产生冗余若哪一条产生式规则被应用后产生冗余知识，则就降低它被应用的优先级。知识，则就降低它被应用的优先级。l7 7、按条件个数排序、按条件个数排序l如果有多条产生式规则生成的结论相同，如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用。则要求条件少的产生式规则被优先应用。54 4.2 4.2自然演绎推理自然演绎推理l从一组已知的事实出发，直接运用经典从一组已知的事实出发，直接运用经典逻辑
41、推理规则推出结论的过程称为自然逻辑推理规则推出结论的过程称为自然演绎推理。其中，基本的推理规则是演绎推理。其中，基本的推理规则是P P规规则、则、T T规则、假言推理、拒取式推理等。规则、假言推理、拒取式推理等。假言推理的一般形式是假言推理的一般形式是lP P，P PQ Q Q Ql拒取式的一般形式是拒取式的一般形式是lP PQ Q，Q Q P P554.24.2自然演绎推理自然演绎推理l以下是自然演绎推理的例子：以下是自然演绎推理的例子：l例例1 1：A A，B B，A AC C，B B C C D D，D D Q QlQ Ql1 1、A PA P规则规则l2 2、A AC PC P规则规则
42、l3 3、C TC T规则规则1 1和和2 2l4 4、B PB P规则规则l5 5、B B C TC T规则规则3 3和和4 4564.24.2自然演绎推理自然演绎推理 6 6、B B C C D PD P规则规则l7 7、D TD T规则规则5 5和和6 6l8 8、D D Q PQ P规则规则l9 9、Q TQ T规则规则7 7和和8 8l问题得证问题得证574.24.2自然演绎推理自然演绎推理l例例2 2设已知如下事实；设已知如下事实；l（1 1）凡是容易的课程小王（）凡是容易的课程小王（Wang)Wang)都喜都喜欢。欢。l（2 2）C C班的课程都是容易的。班的课程都是容易的。l（
43、3 3）dsds是是C C班的一门课程班的一门课程l求证小王喜欢求证小王喜欢dsds这门课程。这门课程。584.24.2自然演绎推理自然演绎推理l证明：首先定义谓词如下：证明：首先定义谓词如下：lEasyEasy（x):xx):x是容易的是容易的lLikeLike（x,y):xx,y):x喜欢喜欢y ylC C（x):xx):x是是C C班的一门课程班的一门课程l于是问题可以表示成：于是问题可以表示成：594.24.2自然演绎推理自然演绎推理l x(Easy(x)x(Easy(x)Like(Wang,x)Like(Wang,x)l x(C(x)x(C(x)Easy(x)Easy(x)lC(ds
44、)C(ds)Like Like（Wang,ds).Wang,ds).604.24.2自然演绎推理自然演绎推理l1 1、x(Easyx(Easy（x)x)Like Like（Wang,x)PWang,x)P规则规则l2 2、EasyEasy（ds)ds)Like Like（Wang,ds)USWang,ds)US规则和规则和1 1l3 3、x(Cx(C（x)x)Easy Easy（x)Px)P规则规则l4 4、C C（ds)ds)Easy Easy（ds)USds)US规则和规则和3 3l5 5、C C（ds)ds)Like Like（Wang,ds)TWang,ds)T规则规则2 2和和4 4
45、l6 6、C C（ds)Pds)P规则规则l7 7、LikeLike（Wang,ds)TWang,ds)T规则规则5 5和和6 6l即小王喜欢即小王喜欢dsds这门课程这门课程614.24.2自然演绎推理自然演绎推理l自然演绎推理的优点是表达定理证明过自然演绎推理的优点是表达定理证明过程自然，容易理解，拥有丰富的推理规程自然，容易理解，拥有丰富的推理规则，推理过程灵活，便于在推理过程中则，推理过程灵活，便于在推理过程中嵌入领域启发知识。缺点是容易产生组嵌入领域启发知识。缺点是容易产生组合爆炸，推理过程中得到的中间结论一合爆炸，推理过程中得到的中间结论一般呈指数形式递增，这对于一个大型推般呈指数
46、形式递增，这对于一个大型推理问题是十分不利的，甚至是不可能实理问题是十分不利的，甚至是不可能实现的。现的。624.34.3归结演绎推理归结演绎推理l定理证明是人工智能的一个重要研究领域，这定理证明是人工智能的一个重要研究领域，这不仅仅是因为许多数学问题要通过定理证明得不仅仅是因为许多数学问题要通过定理证明得以解决，很多非数学问题（如医疗诊断、机器以解决，很多非数学问题（如医疗诊断、机器人规划及难题求解等）也都归结为一个定理证人规划及难题求解等）也都归结为一个定理证明问题。定理证明的实质是对前提明问题。定理证明的实质是对前提P P和结论和结论Q Q证证明明P P Q Q的永真性。但是证明一个谓词
47、公式的的永真性。但是证明一个谓词公式的永真性不像证明一个命题公式的永真性那麽简永真性不像证明一个命题公式的永真性那麽简单，（它牵涉到谓词变量、客体变量及函数符单，（它牵涉到谓词变量、客体变量及函数符号）在某些情况下甚至是行不通的。号）在某些情况下甚至是行不通的。634.34.3归结演绎推理归结演绎推理l在这种情况下，人们提出了用反证法来在这种情况下，人们提出了用反证法来解决问题的思路。在这方面，海伯伦和解决问题的思路。在这方面，海伯伦和鲁宾逊都作出了杰出的贡献。鲁宾逊都作出了杰出的贡献。l两人的研究都是以子句集为背景展开的。两人的研究都是以子句集为背景展开的。接下来，我们介绍这些概念。接下来，
48、我们介绍这些概念。644.34.3归结演绎推理归结演绎推理l子句：在谓词逻辑中，称原子谓词公式子句：在谓词逻辑中，称原子谓词公式及其否定为文字；任何文字的析取式为及其否定为文字；任何文字的析取式为子句。子句。l例如，例如，P(x)P(x)Q(x),Q(x),P(x,f(x)P(x,f(x)Q(x,g(x)Q(x,g(x)都都是子句。而是子句。而P(x)P(x)、Q(x,g(x)Q(x,g(x)、P(x,f(x)P(x,f(x)等等都是文字。并把不包含任何文字的子句都是文字。并把不包含任何文字的子句称为空子句。称为空子句。654.34.3归结演绎推理归结演绎推理l由于空子句不包含任何文字，它不能
49、被由于空子句不包含任何文字，它不能被任何解释所满足，所以空子句是永假的，任何解释所满足，所以空子句是永假的，不可满足的。不可满足的。l由子句构成的集合称为子句集。在谓词由子句构成的集合称为子句集。在谓词逻辑中任何一个谓词公式均可通过等价逻辑中任何一个谓词公式均可通过等价变换化为相应的子句集。变换化为相应的子句集。664.34.3归结演绎推理归结演绎推理l化子句集的步骤如下：化子句集的步骤如下：l1 1、利用等价公式消去公式中的逻辑连接、利用等价公式消去公式中的逻辑连接词词“”l和和“”：lP P Q QP P Q QlP P Q Q（P P Q Q）（P P Q Q）674.34.3归结演绎推
50、理归结演绎推理l2 2、利用下列公式将否定符号、利用下列公式将否定符号“”深入深入到单个变元前到单个变元前l P P P Pl （P P Q Q）P P Q Ql （P P Q Q）P P Q Ql (x)P x)P(x)x)P Pl(x)P x)P (x)x)P P684.34.3归结演绎推理归结演绎推理l3 3、重新命名变元名，使不同量词约束的变元、重新命名变元名，使不同量词约束的变元有不同的名字有不同的名字 l4 4、消去存在量词。分两种情况处理：一种情、消去存在量词。分两种情况处理：一种情况是存在量词不出现在全称量词的辖域内，此况是存在量词不出现在全称量词的辖域内，此时只要用一个新的个
