人工智能第四章经典逻辑推理1

1、第第4 4章章 经典逻辑推理经典逻辑推理经典逻辑推理经典逻辑推理的含义的含义: : 是根据经典逻辑（命题逻辑及一阶谓词逻辑）的逻是根据经典逻辑（命题逻辑及一阶谓词逻辑）的逻辑规则进行的一种推理，又称为机械一自动定理证明，辑规则进行的一种推理，又称为机械一自动定理证明，主要推理方法有自然演绎推理、归结演绎推理及与主要推理方法有自然演绎推理、归结演绎推理及与或形演绎推理等。或形演绎推理等。 由于这种推理是基于经典逻辑的，其真值只有由于这种推理是基于经典逻辑的，其真值只有“真真”和和“假假”两种，是一种精确推理，或称为确定性推理。两种，是一种精确推理，或称为确定性推理。第第4 4章章 经典逻辑推理经

2、典逻辑推理学习任务：学习任务：推理的基本概念及分类推理的基本概念及分类命题逻辑推理命题逻辑推理谓词逻辑推理谓词逻辑推理基于规则的演绎推理基于规则的演绎推理第第4 4章章 经典逻辑推理经典逻辑推理一、什么是推理一、什么是推理1 1、推理：按某种策略由已知判断推出另一判断的思维过程。、推理：按某种策略由已知判断推出另一判断的思维过程。2 2、一般来说，推理都包括两种判断：、一般来说，推理都包括两种判断：（A A）已知的判断，它包括已掌握的与求解问题有关的知识）已知的判断，它包括已掌握的与求解问题有关的知识及关于问题的已知事实；及关于问题的已知事实；（B B）由已知判断推出的新判断，即推理的结论。）

3、由已知判断推出的新判断，即推理的结论。3 3、在人工智能系统中，推理是由程序实现的，称为推理机。、在人工智能系统中，推理是由程序实现的，称为推理机。4.1 4.1 基本概念基本概念第第4 4章章 经典逻辑推理经典逻辑推理二、推理方式及其分类二、推理方式及其分类1 1、演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（从新判断（从新判断推出的途径来划分）推出的途径来划分）（A A）演绎推理：是从一般性知识推出适合于某一具体情演绎推理：是从一般性知识推出适合于某一具体情况的结论。况的结论。这是一种从一般到个别的推理。演绎推理这是一种从一般到个别的推理。演绎推理有多种形式，经常用的是三段论式

4、，它包括：有多种形式，经常用的是三段论式，它包括：(1(1）大）大前提，已知的一般性知识或假设；前提，已知的一般性知识或假设；(2(2）小前提，这是）小前提，这是关于所研究的具体情况或个别事实的判断；关于所研究的具体情况或个别事实的判断；(3(3）结论，）结论，这是由大前提推出的适合于小前提所示情况的新判断。这是由大前提推出的适合于小前提所示情况的新判断。第第4 4章章 经典逻辑推理经典逻辑推理例：设有如下三个判断：例：设有如下三个判断：(1(1）所有的推理系统都是智能）所有的推理系统都是智能系统；系统；(2(2）专家系统是推理系统；）专家系统是推理系统；(3(3）所以，专家系）所以，专家系统

5、是智能系统。这就是一个三段论推理。其中，统是智能系统。这就是一个三段论推理。其中，(l(l）是大前提；是大前提；(2(2）是小前提；）是小前提；(3(3）是经演绎推出的结论。）是经演绎推出的结论。 在任何情况下，由演绎推理导出的结论都是蕴含在大在任何情况下，由演绎推理导出的结论都是蕴含在大前提的一般性知识之中的。前提的一般性知识之中的。第第4 4章章 经典逻辑推理经典逻辑推理（B B）归纳推理：是从足够多的事例中归纳出一般性结归纳推理：是从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理。论的推理过程，是一种从个别到一般的推理。 若从归纳时所选事例的广泛性来划分，归纳推理又可

6、分为若从归纳时所选事例的广泛性来划分，归纳推理又可分为完全归纳推理与不完全归纳推理两种。完全归纳推理与不完全归纳推理两种。 完全归纳推理：是指在进行归纳时，考察了相应事物的完全归纳推理：是指在进行归纳时，考察了相应事物的全部对象，并根据这些对象是否都具有某种属性，从而推全部对象，并根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性。出这个事物是否具有这个属性。 例如，某厂进行产品质量检查，如果对每一件产品都进行例如，某厂进行产品质量检查，如果对每一件产品都进行了严格检查，并且都是合格的，则推导出结论了严格检查，并且都是合格的，则推导出结论“该厂生产该厂生产的产品是合格的的产品是合

7、格的”，这就是一个完全归纳推理。，这就是一个完全归纳推理。第第4 4章章 经典逻辑推理经典逻辑推理 不完全归纳推理：是指只考察了相应事物的部分对象，不完全归纳推理：是指只考察了相应事物的部分对象，就得出了结论。就得出了结论。 例如，检查产品质量时，只是随机地抽查了部分产品，例如，检查产品质量时，只是随机地抽查了部分产品，只要它们都合格，就得出了只要它们都合格，就得出了“该厂生产的产品是合格该厂生产的产品是合格的的”结论，这就是一个不完全归纳推理。结论，这就是一个不完全归纳推理。 不完全归纳推理推出的结论不具有必然性，属于非必不完全归纳推理推出的结论不具有必然性，属于非必然性推理，而完全归纳推理

8、是必然性推理。然性推理，而完全归纳推理是必然性推理。但由于要但由于要考察事物的所有对象通常都比较困难，因而大多数归考察事物的所有对象通常都比较困难，因而大多数归纳推理都是不完全归纳推理。纳推理都是不完全归纳推理。第第4 4章章 经典逻辑推理经典逻辑推理（C C）默认推理：又称为缺省推理，它是在知识不完全）默认推理：又称为缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。的情况下假设某些条件已经具备所进行的推理。 例如，在条件例如，在条件A A已成立的情况下，如果没有足够的证据已成立的情况下，如果没有足够的证据能证明条件能证明条件B B不成立，则就默认不成立，则就默认B B是成

9、立的，并在此默认是成立的，并在此默认的前提下进行推理，推导出某个结论。在默认推理过程的前提下进行推理，推导出某个结论。在默认推理过程中，如果到某一时刻发现原先所作的默认不正确，则要中，如果到某一时刻发现原先所作的默认不正确，则要撤消所作的默认以及由此默认推出的所有结论，重新按撤消所作的默认以及由此默认推出的所有结论，重新按新情况进行推理。新情况进行推理。第第4 4章章 经典逻辑推理经典逻辑推理2 2、确定性推理、不确定性推理：（按推理时所、确定性推理、不确定性推理：（按推理时所用知识的确定性来划分）用知识的确定性来划分）（A A）确定性推理：推理时所用的知识都是精确的，推）确定性推理：推理时所

10、用的知识都是精确的，推出的结论也是确定的，其真值或者为真，或者为假，出的结论也是确定的，其真值或者为真，或者为假，没有第三种情况出现。没有第三种情况出现。（B B）不确定性推理：推理时所用的知识不都是精确的，）不确定性推理：推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其真值位于真与假之推出的结论也不完全是肯定的，其真值位于真与假之间，命题的外延模糊不清。间，命题的外延模糊不清。第第4 4章章 经典逻辑推理经典逻辑推理 3 3、单调推理、非单调推理：（按推理过程中推、单调推理、非单调推理：（按推理过程中推出的结论是否单调地增加，或者说推出的结论是出的结论是否单调地增加，或者说推出的

11、结论是否越来越接近最终目标来划分）否越来越接近最终目标来划分）（A A）单调推理：在推理过程中随着推理的向前推进及新知）单调推理：在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不会出现反复的情况，即接近最终目标，在推理过程中不会出现反复的情况，即不会由于新知识的加入否定了前面推出的结论，从而使不会由于新知识的加入否定了前面推出的结论，从而使推理又退回到前面的某一步。推理又退回到前面的某一步。第第4 4章章 经典逻辑推理经典逻辑推理（B B）非单调推理）非单调推理: :是指在推理过程中

12、由于新知识的加入，是指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。退回到前面的某一步，重新开始。 第第4 4章章 经典逻辑推理经典逻辑推理4 4、启发式推理、非启发式推理：（按推理中、启发式推理、非启发式推理：（按推理中是否运用与问题有关的启发性知识）是否运用与问题有关的启发性知识） 启发性知识：是指与问题有关且能加快推理进程、启发性知识：是指与问题有关且能加快推理进程、求得问题最优解的知识。求得问题最优解的知识。 启发式推理：在推理过程中，运用启发性知识。启发式推理：在推理过程中，

13、运用启发性知识。 非启发式推理：在推理过程中，不运用启发性知识。非启发式推理：在推理过程中，不运用启发性知识。第第4 4章章 经典逻辑推理经典逻辑推理5 5、基于知识的推理、统计推理、直觉推理、基于知识的推理、统计推理、直觉推理（A A）基于知识的推理：根据已掌握的事实，通过运用）基于知识的推理：根据已掌握的事实，通过运用知识进行的推理。知识进行的推理。 例如医生诊断疾病时，他根据病人的症状及检验结果，例如医生诊断疾病时，他根据病人的症状及检验结果，运用自己的医学知识进行推理，最后给出诊断结论及运用自己的医学知识进行推理，最后给出诊断结论及治疗方案，这就是基于知识的推理。治疗方案，这就是基于知

14、识的推理。第第4 4章章 经典逻辑推理经典逻辑推理（B B）统计推理：根据对某事物的数据统计进行的推理。）统计推理：根据对某事物的数据统计进行的推理。 例如农民根据对农作物的产量统计，得出是否增产的结例如农民根据对农作物的产量统计，得出是否增产的结论，从而可找出增产或者减产的原因，这就是运用了统论，从而可找出增产或者减产的原因，这就是运用了统计推理。计推理。（C C）直觉推理：又称为常识性推理，是根据常识进行的推）直觉推理：又称为常识性推理，是根据常识进行的推理。理。 例如，当你从某建筑物下面走过时，猛然发现有一物体例如，当你从某建筑物下面走过时，猛然发现有一物体从建筑物上掉落下来，这时你立即

15、就会意识到从建筑物上掉落下来，这时你立即就会意识到“这有危这有危险险”，并立即躲开，这就是使用了直觉推理。，并立即躲开，这就是使用了直觉推理。第第4 4章章 经典逻辑推理经典逻辑推理 三、三、推理的控制策略推理的控制策略 推理的控制策略主要包括推理方向、搜索策略、冲突消解策略、推理的控制策略主要包括推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。求解策略及限制策略等。 1 1、推理方向推理方向用于确定推理的驱动方式，分为正向推理、逆向推理、混合推理用于确定推理的驱动方式，分为正向推理、逆向推理、混合推理及双向推理四种。无论按哪种方向进行推理，一般都要求系统具及双向推理四种。无论按哪种方

16、向进行推理，一般都要求系统具有一个存放知识的有一个存放知识的，一个存放初始已知事实及问题状态的，一个存放初始已知事实及问题状态的和一个用于推理的和一个用于推理的。第第4 4章章 经典逻辑推理经典逻辑推理（A）正向推理：正向推理：是以已知事实作为出发点，通过不断的匹配知识库是以已知事实作为出发点，通过不断的匹配知识库中的知识，最终找到一个解或无解退出的一种推理，又称为数据中的知识，最终找到一个解或无解退出的一种推理，又称为数据驱动推理、前向链推理、模式制导推理及前件推理等。驱动推理、前向链推理、模式制导推理及前件推理等。 基本思想是：基本思想是： 从用户提供的初始已知事实出发，在知识库从用户提供

17、的初始已知事实出发，在知识库KB中找出当前可适中找出当前可适用的知识，构成可适用知识集用的知识，构成可适用知识集KS。 按某种冲突消解策略从按某种冲突消解策略从KS中选出一条知识进行推理，并将推出中选出一条知识进行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实。的新事实加入到数据库中作为下一步推理的已知事实。 再在知识库中选取可适用知识进行推理，如此重复进行这一过再在知识库中选取可适用知识进行推理，如此重复进行这一过程，直到求得了所要求的解或者知识库中再无可适用的知识为止。程，直到求得了所要求的解或者知识库中再无可适用的知识为止。第第4 4章章 经典逻辑推理经典逻辑推理其推理过程

18、的算法描述：其推理过程的算法描述：将用户提供的初始已知事实送入数据库将用户提供的初始已知事实送入数据库DB中；中；检查数据库检查数据库DB中是否已经包含了问题的解，若有，则求解结束，中是否已经包含了问题的解，若有，则求解结束，并成功退出；否则执行下一步；并成功退出；否则执行下一步；根据数据库根据数据库DB中的已知事实，扫描知识库中的已知事实，扫描知识库KB，检查，检查KB中是否中是否有可适用（即可与有可适用（即可与DB中已知事实匹配）的知识，若有，则转中已知事实匹配）的知识，若有，则转，否则转否则转；把把KB中所有的适用知识都选出来，构成可适用的知识集中所有的适用知识都选出来，构成可适用的知识

19、集KS；若若KS不空，则按某种冲突消解策略从中选出一条知识进行推理，不空，则按某种冲突消解策略从中选出一条知识进行推理，并将推出的新事实加入并将推出的新事实加入DB中，然后转中，然后转；若；若KS空，则转空，则转；询问用户是否可进一步补充新的事实，若可补充，则将补充的询问用户是否可进一步补充新的事实，若可补充，则将补充的新事实加入新事实加入DB中，然后转中，然后转；否则表示求不出解，失败退出。；否则表示求不出解，失败退出。第第4 4章章 经典逻辑推理经典逻辑推理算法和基本思想：算法和基本思想：算法是推理的控制策略的整个过程的描述，算法是推理的控制策略的整个过程的描述，而基本思想是算法的核心部分

20、。而基本思想是算法的核心部分。第第4 4章章 经典逻辑推理经典逻辑推理正向推理过程第第4 4章章 经典逻辑推理经典逻辑推理（B B）是以某个假设目标作为出发点，然后去寻找证据，直是以某个假设目标作为出发点，然后去寻找证据，直至最终所有的证据都能寻找到使其成立的已知证据的至最终所有的证据都能寻找到使其成立的已知证据的一种推理，又称为目标驱动推理、逆向链推理、目标一种推理，又称为目标驱动推理、逆向链推理、目标制导推理及后件推理等。制导推理及后件推理等。第第4 4章章 经典逻辑推理经典逻辑推理基本思想：基本思想：选定一个假设目标选定一个假设目标在知识库中寻找其结论部分导致这个假设目标的知识集在知识库

21、中寻找其结论部分导致这个假设目标的知识集检查知识集中每条知识的条件部分，如果某条知识的条检查知识集中每条知识的条件部分，如果某条知识的条件中所含的条件项均能被当前数据库的内容所匹配，则件中所含的条件项均能被当前数据库的内容所匹配，则把该条知识的结论加到当前数据库中，从而该目标被证把该条知识的结论加到当前数据库中，从而该目标被证明；否则把该知识的条件项作为新的子目标明；否则把该知识的条件项作为新的子目标第第4 4章章 经典逻辑推理经典逻辑推理递归执行上述过程，直到各递归执行上述过程，直到各“与与”关系的子目标关系的子目标全部或者全部或者“或或”关系的子目标有一个出现在数据关系的子目标有一个出现在

22、数据库中，此时目标被求解，或者直到子目标不能进库中，此时目标被求解，或者直到子目标不能进一步分解而且数据库不能实现上述匹配时，这个一步分解而且数据库不能实现上述匹配时，这个假设目标为假，系统重新提出新的假设目标。假设目标为假，系统重新提出新的假设目标。第第4 4章章 经典逻辑推理经典逻辑推理其推理过程的算法描述：其推理过程的算法描述：提出要求证的目标（假设）；提出要求证的目标（假设）；检查该目标是否已在数据库中，若在，则该目标成立，检查该目标是否已在数据库中，若在，则该目标成立，成功地退出推理或者对下一个假设目标进行验证；否则，成功地退出推理或者对下一个假设目标进行验证；否则，转下一步；转下一

23、步；判断该目标是否是证据，即它是否为应由用户证实的判断该目标是否是证据，即它是否为应由用户证实的原始事实，若是，则询问用户；否则转下一步；原始事实，若是，则询问用户；否则转下一步；在知识库中找出所有能导出该目标的知识，形成适用在知识库中找出所有能导出该目标的知识，形成适用知识集知识集KS，然后转下一步；，然后转下一步；从从KS中选出一条知识，并将该知识的运用条件作为新中选出一条知识，并将该知识的运用条件作为新的假设目标，然后转的假设目标，然后转。第第4 4章章 经典逻辑推理经典逻辑推理逆向推理过程第第4 4章章 经典逻辑推理经典逻辑推理 与正向推理相比，逆向推理更复杂一些，上述算法只是描述了它

24、与正向推理相比，逆向推理更复杂一些，上述算法只是描述了它的大致过程，许多细节没有反映出来。例如，如何判断一个假设是的大致过程，许多细节没有反映出来。例如，如何判断一个假设是否是证据？当导出假设的知识有多条时，如何确定先选哪一条？另否是证据？当导出假设的知识有多条时，如何确定先选哪一条？另外，一条知识的运用条件一般都有多个，当其中的一个经验证成立外，一条知识的运用条件一般都有多个，当其中的一个经验证成立后，如何自动地换为对另一个的验证？其次，在验证一个运用条件后，如何自动地换为对另一个的验证？其次，在验证一个运用条件时，需要把它当作新的假设，并查找可导出该假设的知识，这样就时，需要把它当作新的假

25、设，并查找可导出该假设的知识，这样就又会产生一组新的运用条件，如此不断地向纵深方向发展，就会产又会产生一组新的运用条件，如此不断地向纵深方向发展，就会产生处于不同层次上的多组运用条件，形成一个树状结构，当到达叶生处于不同层次上的多组运用条件，形成一个树状结构，当到达叶节点（即数据库中有相应的事实或者用户可肯定相应事实存在等）节点（即数据库中有相应的事实或者用户可肯定相应事实存在等）时，又需逐层向上返回，返回过程中有可能又要下到下一层，这样时，又需逐层向上返回，返回过程中有可能又要下到下一层，这样上上下下重复多次，才会导出原假设是否成立的结论。上上下下重复多次，才会导出原假设是否成立的结论。 第

26、第4 4章章 经典逻辑推理经典逻辑推理 逆向推理的主要优点：是不必使用与目标逆向推理的主要优点：是不必使用与目标无关的知识，目的性强，同时它还有利于向无关的知识，目的性强，同时它还有利于向用户提供解释。用户提供解释。 其主要缺点：是初始目标的选择有盲目性，其主要缺点：是初始目标的选择有盲目性，若不符合实际，就要多次提出假设，影响到若不符合实际，就要多次提出假设，影响到系统的效率，也不能通过用户自愿提供的有系统的效率，也不能通过用户自愿提供的有用信息来操作。用信息来操作。第第4 4章章 经典逻辑推理经典逻辑推理 正向推理具有盲目、效率低等缺点，推理过程中可正向推理具有盲目、效率低等缺点，推理过程

27、中可能会推出许多与问题求解无关的子目标；逆向推理中，能会推出许多与问题求解无关的子目标；逆向推理中，若提出的假设目标不符合实际，也会降低系统的效率。若提出的假设目标不符合实际，也会降低系统的效率。为解决这些问题，可把正向推理与逆向推理结合起来，为解决这些问题，可把正向推理与逆向推理结合起来，使其各自发挥自己的优势，取长补短。使其各自发挥自己的优势，取长补短。 像这样既有正向又有逆向的推理称为混合推理。像这样既有正向又有逆向的推理称为混合推理。第第4 4章章 经典逻辑推理经典逻辑推理混合推理分为两种情况：混合推理分为两种情况：一种是先进行正向推理，帮助选择某个目标，即从已知事一种是先进行正向推理

28、，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度；其可信度；另一种情况是先假设一个目标进行逆向推理，然后再利用另一种情况是先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。逆向推理中得到的信息进行正向推理，以推出更多的结论。第第4 4章章 经典逻辑推理经典逻辑推理（先正向后逆向）（先正向后逆向） （先逆向后正向）（先逆向后正向）第第4 4章章 经典逻辑推理经典逻辑推理 另外，在下述几种情况下，通常也需要进行混合推理。另外，在下述几种情况下，通常也需要进行混合推理。已

29、知的事实不充分。当数据库中的已知事实不够充分时，已知的事实不充分。当数据库中的已知事实不够充分时，进行正向推理，可能连一条适用知识都选不出来，这就使推进行正向推理，可能连一条适用知识都选不出来，这就使推理无法进行下去。此时，可通过正向推理先把其运用条件不理无法进行下去。此时，可通过正向推理先把其运用条件不能完全匹配的知识都找出来，并把这些知识可导出的结论作能完全匹配的知识都找出来，并把这些知识可导出的结论作为假设，然后分别对这些假设进行逆向推理。由于在逆向推为假设，然后分别对这些假设进行逆向推理。由于在逆向推理中可以向用户询问有关证据，这就有可能使推理进行下去。理中可以向用户询问有关证据，这就

30、有可能使推理进行下去。第第4 4章章 经典逻辑推理经典逻辑推理 由正向推理推出的结论可信度不高。此时为了得到由正向推理推出的结论可信度不高。此时为了得到一个可信度符合要求的结论，可用这些结论作为假一个可信度符合要求的结论，可用这些结论作为假设，然后进行逆向推理，通过向用户询问进一步的设，然后进行逆向推理，通过向用户询问进一步的信息，有可能会得到可信度较高的结论。信息，有可能会得到可信度较高的结论。 希望得到更多的结论。在逆向推理过程中，由于要希望得到更多的结论。在逆向推理过程中，由于要与用户进行对话，有针对性地向用户提出询问，这与用户进行对话，有针对性地向用户提出询问，这就有可能获得一些原来不

31、掌握的有用信息，这些信就有可能获得一些原来不掌握的有用信息，这些信息不仅可用于证实要证明的假设，同时还可能有助息不仅可用于证实要证明的假设，同时还可能有助于推出一些其它结论。于推出一些其它结论。第第4 4章章 经典逻辑推理经典逻辑推理（D）双向推理：双向推理：指正向推理与逆向推理同时进行，且在推理指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上过程中的某一步骤上“碰头碰头”的一种推理。的一种推理。 基本思想：基本思想：一方面根据已知事实进行正向推理，但并不推到最终目标；一方面根据已知事实进行正向推理，但并不推到最终目标；另一方面从某假设目标出发进行逆向推理，但并不推至原另一方面从某假设

32、目标出发进行逆向推理，但并不推至原始事实，而是让它们在中途相遇，即由正向推理所得的中始事实，而是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所要求的证据，这时推理就可间结论恰好是逆向推理此时所要求的证据，这时推理就可结束，逆向推理时所做的假设就是推理的最终结论。双向结束，逆向推理时所做的假设就是推理的最终结论。双向推理的困难在于推理的困难在于“碰头碰头”的判断。的判断。第第4 4章章 经典逻辑推理经典逻辑推理是指推理是只求一个解，还是求所有是指推理是只求一个解，还是求所有解以及最优解等。解以及最优解等。为了防止无穷的推理过程，以及由于为了防止无穷的推理过程，以及由于推理过程太

33、长增加时间及空间的复杂性，可在控制策推理过程太长增加时间及空间的复杂性，可在控制策略中指定推理的限制条件，以对推理的深度、宽度、略中指定推理的限制条件，以对推理的深度、宽度、时间、空间等进行限制，满足问题求解的实际要求。时间、空间等进行限制，满足问题求解的实际要求。第第4 4章章 经典逻辑推理经典逻辑推理(4)、模式匹配模式匹配 （a a）模式匹配：是指对两个知识模式（如两个谓词模式匹配：是指对两个知识模式（如两个谓词公式、两个框架片断或两个语义网络片断等）的比公式、两个框架片断或两个语义网络片断等）的比较与藕合，即检查这两个知识模式是否完全一致或较与藕合，即检查这两个知识模式是否完全一致或近

34、似一致。如果两者完全一致，或者虽不完全一致近似一致。如果两者完全一致，或者虽不完全一致但其相似程度落在指定的限度内，就称它们是可匹但其相似程度落在指定的限度内，就称它们是可匹配的，否则为不可匹配。配的，否则为不可匹配。 第第4 4章章 经典逻辑推理经典逻辑推理按匹配时两个知识模式的相似程度划分，模式匹按匹配时两个知识模式的相似程度划分，模式匹配可分为配可分为确定性匹配与不确定性匹配确定性匹配与不确定性匹配两种。两种。（b b）确定性匹配：是指两个知识模式完全一致，或者）确定性匹配：是指两个知识模式完全一致，或者经过变量代换后变得完全一致。经过变量代换后变得完全一致。（c c）不确定性匹配：是指

35、两个知识模式不完全一致，不确定性匹配：是指两个知识模式不完全一致，但从总体上看，它们的相似程度又落在规定的限度内。但从总体上看，它们的相似程度又落在规定的限度内。第第4 4章章 经典逻辑推理经典逻辑推理(5)、冲突消解策略：、冲突消解策略： 冲突：已知事实可与知识库中的多个知识匹配成功。冲突：已知事实可与知识库中的多个知识匹配成功。第第4 4章章 经典逻辑推理经典逻辑推理下面我们就产生式系统运行过程中的冲突及其消解策略做进一步的讨论。下面我们就产生式系统运行过程中的冲突及其消解策略做进一步的讨论。目前已有多种消解冲突的策略，其基本思想都是对知识进行排序，常用的目前已有多种消解冲突的策略，其基本

36、思想都是对知识进行排序，常用的有以下几种：有以下几种：本策略是优先选用针对性较强的知识（产生式规本策略是优先选用针对性较强的知识（产生式规则）。因为它要求的条件较多，其结论一般更接近于目标，一旦得到满足，则）。因为它要求的条件较多，其结论一般更接近于目标，一旦得到满足，可缩短推理过程。可缩短推理过程。 如：有如下规则：如：有如下规则： 规则规则1 1：IF A AND B AND C THEN E;IF A AND B AND C THEN E; 规则规则2 2：IF A AND B AND C AND D THEN F;IF A AND B AND C AND D THEN F; 数据库中数

37、据库中A A，B B，C C，D D均为真，这时规则均为真，这时规则1 1和规则和规则2 2都与数据库相匹配，都与数据库相匹配，但因规则但因规则2 2的条件更有针对性，更多，所以具有较高的优先级。的条件更有针对性，更多，所以具有较高的优先级。第第4 4章章 经典逻辑推理经典逻辑推理在产生式系统的推理过程中，每应用一条产生式规则就会在产生式系统的推理过程中，每应用一条产生式规则就会得到一个或多个结论或者执行某个操作，数据库就会增加得到一个或多个结论或者执行某个操作，数据库就会增加新的事实。另外，在推理时还会向用户询问有关的信息，新的事实。另外，在推理时还会向用户询问有关的信息，也使数据库的内容发

38、生变化。也使数据库的内容发生变化。我们把数据库中后生成的事实称为新鲜的事实，即后生我们把数据库中后生成的事实称为新鲜的事实，即后生成的事实比先生成的事实具有较大的新鲜性。成的事实比先生成的事实具有较大的新鲜性。若一条规则被应用后生成了多个结论，则既可以认为这若一条规则被应用后生成了多个结论，则既可以认为这些结论有相同的新鲜性，也可认为排在前面（或后面）的些结论有相同的新鲜性，也可认为排在前面（或后面）的结论有较大的新鲜性，根据情况决定。结论有较大的新鲜性，根据情况决定。第第4 4章章 经典逻辑推理经典逻辑推理 设规则设规则R1R1可与事实组可与事实组A A匹配成功，规则匹配成功，规则R2R2可

39、与事实组可与事实组B B匹配成功，则匹配成功，则A A与与B B中哪一组新鲜，与它匹配的产生式中哪一组新鲜，与它匹配的产生式规则就先被应用。如何衡量规则就先被应用。如何衡量A A与与B B中哪一组事实更新鲜中哪一组事实更新鲜呢？呢？ 常用的方法有以下三种：常用的方法有以下三种：把把A A与与B B中的事实逐个地比中的事实逐个地比较其新鲜性，若较其新鲜性，若A A中包含的更新鲜的事实比中包含的更新鲜的事实比B B多，就认多，就认为为A A比比B B新鲜。新鲜。以以A A中最新鲜的事实与中最新鲜的事实与B B中最新鲜的事中最新鲜的事实相比较，哪一个更新鲜，就认为相应的事实组更新实相比较，哪一个更新

40、鲜，就认为相应的事实组更新鲜。鲜。以以A A中最不新鲜的事实与中最不新鲜的事实与B B中最不新鲜的事实相中最不新鲜的事实相比较，哪一个更不新鲜，就认为相应的事实组有较小比较，哪一个更不新鲜，就认为相应的事实组有较小的新鲜性。的新鲜性。第第4 4章章 经典逻辑推理经典逻辑推理 在不确定性匹配中，为了确定两个知识模式是否可在不确定性匹配中，为了确定两个知识模式是否可以匹配，需要计算这两个模式的相似程度，当其相以匹配，需要计算这两个模式的相似程度，当其相似度达到某个预先规定的值时，就认为它们是可匹似度达到某个预先规定的值时，就认为它们是可匹配的。相似度又称为匹配度，它除了可用来确定两配的。相似度又称

41、为匹配度，它除了可用来确定两个知识模式是否可匹配外，还可用于冲突消解。若个知识模式是否可匹配外，还可用于冲突消解。若产生式规则产生式规则R1R1与与R2R2都可匹配成功，则可根据它们的都可匹配成功，则可根据它们的匹配度来决定哪一个产生式规则可优先被应用。匹配度来决定哪一个产生式规则可优先被应用。第第4 4章章 经典逻辑推理经典逻辑推理 某些领域问题，事先可知道它的某些特点，此时可某些领域问题，事先可知道它的某些特点，此时可根据这些特点把知识排成固定的顺序。例如：根据这些特点把知识排成固定的顺序。例如：当当领域问题有固定的解题次序时，可按该次序排列相领域问题有固定的解题次序时，可按该次序排列相应

42、的知识，排在前面的知识优先被应用。应的知识，排在前面的知识优先被应用。当已知当已知某些产生式规则被应用后会明显地有利于问题的求某些产生式规则被应用后会明显地有利于问题的求解时，就使这些产生式规则优先被应用。解时，就使这些产生式规则优先被应用。第第4 4章章 经典逻辑推理经典逻辑推理把产生式规则按它们所描把产生式规则按它们所描述的上下文分成若干组，在不同的条件下，只能从相述的上下文分成若干组，在不同的条件下，只能从相应的组中选取有关的产生式规则。应的组中选取有关的产生式规则。如果一条产生式规则被应用如果一条产生式规则被应用后将产生冗余知识，则就降低它被应用的优先级，产后将产生冗余知识，则就降低它

43、被应用的优先级，产生的冗余知识越多，优先级愈低。生的冗余知识越多，优先级愈低。如果有多条产生式规则生成如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用，的结论相同，则要求条件少的产生式规则被优先应用，因为要求条件少的规则匹配时花费的时间较少。因为要求条件少的规则匹配时花费的时间较少。第第4 4章章 经典逻辑推理经典逻辑推理 从一组已知为真的事实出发，直接运用从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论的过程称为经典逻辑的推理规则推出结论的过程称为。其中，基本的推理规则是其中，基本的推理规则是P规则、规则、T规则、假言推理、拒取式推理规则、假言推理、拒取式推

44、理等。等。4.2 4.2 命题逻辑推理命题逻辑推理一、命题的自然演绎一、命题的自然演绎第第4 4章章 经典逻辑推理经典逻辑推理 P P规则：在推理的任何步骤上都可引入前提。规则：在推理的任何步骤上都可引入前提。 T T规则：推理时，如果前面步骤中有一个或多个公式永真蕴含公式规则：推理时，如果前面步骤中有一个或多个公式永真蕴含公式S S，则可把，则可把S S引入推理过程中。引入推理过程中。第第4 4章章 经典逻辑推理经典逻辑推理例例4.1 4.1 设已知下述事实：设已知下述事实：第第4 4章章 经典逻辑推理经典逻辑推理一般来说，由已知事实推出的结论可能有多个，只一般来说，由已知事实推出的结论可能

45、有多个，只要其中包含了待证明的结论，就认为问题得到了解决。要其中包含了待证明的结论，就认为问题得到了解决。第第4 4章章 经典逻辑推理经典逻辑推理二、命题推理规则二、命题推理规则1 1、子句与子句集、子句与子句集子句：一组文字的析取。子句：一组文字的析取。文字：一个原子或者是一个原子的否定。文字：一个原子或者是一个原子的否定。子句集：由子句构成的集合称为子句集。子句集：由子句构成的集合称为子句集。空子句：不包含任何文字的子句称为空子句。由于空子空子句：不包含任何文字的子句称为空子句。由于空子句不含有文字，它不能被任何解释满足，所以空子句是句不含有文字，它不能被任何解释满足，所以空子句是永假的，

46、不可满足的。永假的，不可满足的。 第第4 4章章 经典逻辑推理经典逻辑推理 2 2、基于子句的归结、基于子句的归结定义定义1 1：若：若P P是原子谓词公式，则是原子谓词公式，则P P与与P P是互补文字。是互补文字。定义定义2 2：第第4 4章章 经典逻辑推理经典逻辑推理例：例：定理定理 子句子句C C1 1和和 C C2 2的归结是的归结是C C1 1和和 C C2 2的逻辑推论。的逻辑推论。所以在定理证明中可用其代替所以在定理证明中可用其代替C C1 1和和 C C2 2。第第4 4章章 经典逻辑推理经典逻辑推理3 3、命题的归结反演、命题的归结反演若两个若两个单位子句单位子句C C1

47、1和和C C2 2存在归结式，则该归结式为空子句存在归结式，则该归结式为空子句NILNIL，并且，并且C C1 1C C2 2等价于等价于NILNIL。若子句集。若子句集S S是不可满足的，则是不可满足的，则可以使用归结规则由可以使用归结规则由S S产生产生NILNIL。第第4 4章章 经典逻辑推理经典逻辑推理归结原理（又称消解原理）的基本思想是：归结原理（又称消解原理）的基本思想是：设法检验子句集设法检验子句集S S是否含有空子句，若有空子句则子句是否含有空子句，若有空子句则子句集是不可满足的，否则就进一步用集是不可满足的，否则就进一步用归结法归结法从从S S导出导出S S1 1, ,然然后

48、再检验后再检验S S1 1是否有空子句，如此可以一直进行下去，直是否有空子句，如此可以一直进行下去，直到导出空子句或不能继续归结为止。归结原理的实质就到导出空子句或不能继续归结为止。归结原理的实质就是通过归结过程演绎出是通过归结过程演绎出S S的不可满足性。鲁宾逊归结原的不可满足性。鲁宾逊归结原理可分为命题逻辑的归结原理和谓词逻辑的归结原理。理可分为命题逻辑的归结原理和谓词逻辑的归结原理。第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理4 4、命题归结反演的合理性与完备性、命题归结反演的合理性与完备性合理性：是指证明过程的正确性。合理性：是指证明过程的正确性。完

49、备性：说明使用方法可以得到所有可能的推断。完备性：说明使用方法可以得到所有可能的推断。归结反演是合理的。归结反演是合理的。归结反演是完备的。归结反演是完备的。第第4 4章章 经典逻辑推理经典逻辑推理一、一、子句子句 在谓词逻辑中，把在谓词逻辑中，把原子谓词公式原子谓词公式及其否定统称为及其否定统称为文字文字。 任何文字的析取式称为子句。任何文字的析取式称为子句。如：如：P(x)VQ(x) 不包含任何文字的子句称为空子句。由于空子句不含有不包含任何文字的子句称为空子句。由于空子句不含有文字，它不能被任何解释满足，所以空子句是永假的，文字，它不能被任何解释满足，所以空子句是永假的，不可满足的。不可

50、满足的。 由子句构成的集合称为子句集。由子句构成的集合称为子句集。 4.3 4.3 谓词逻辑推理谓词逻辑推理P(xP(x) ) 是原子谓词公式，是原子谓词公式，复合谓词公式是由原子复合谓词公式是由原子谓词公式通过连接词构谓词公式通过连接词构成的成的第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理说明：说明：1、前束范式（书、前束范式（书P165定义及例子）定义及例子）把谓词公式中的所有量词均非否定地移到公式的最前面，它把谓词公式中的所有量词均非

51、否定地移到公式的最前面，它们的辖域为整个公式，此时称公式为前束范式。们的辖域为整个公式，此时称公式为前束范式。 2、Skolem标准型，也称标准型，也称S范式（书范式（书P166定义及例子）定义及例子） ：消去存在量词后，把所有全称量词都依次移到整个式子的最消去存在量词后，把所有全称量词都依次移到整个式子的最左边（或者先把所有量词都依次移到整个式子的最左边，再左边（或者先把所有量词都依次移到整个式子的最左边，再消去存在量词），再将右部的式子化为合取范式，这时所得消去存在量词），再将右部的式子化为合取范式，这时所得的式子称为原公式的的式子称为原公式的Skolem标准型，也称标准型，也称S范式。范

52、式。第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理二、置换和合一二、置换和合一置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。在谓词逻辑中，一个表达式的项是常量符号、变量符号或函数式。第第4 4章章 经典逻辑推理经典逻辑推理u置换的合成置换的合成 第第4 4章章 经典逻辑推理经典逻辑推理例：例：设：设： f(y)/x, z/yf(y)/x, z/y， a/x, b/y, y/za/x, b/y, y/z，求，求 与与 的合成。的合成。解：先求出集合解：先求出集合f(b/y)/x, (y/z)/y, a/x,

53、b/y, y/zf(b/y)/x, (y/z)/y, a/x, b/y, y/zf(b)/x, y/y, a/x, b/y, f(b)/x, y/y, a/x, b/y, y/zy/z其中，其中，f(b)/xf(b)/x中的中的f(b)f(b)是置换是置换 作用于作用于f(y)f(y)的结果；的结果；y/yy/y中中的的y y是置换是置换 作用于作用于z z的结果。在该集合中，的结果。在该集合中，y/yy/y满足定义满足定义中的条件中的条件i i，需要删除；，需要删除；a/xa/x，b/yb/y满足定义中的条件满足定义中的条件ii ii，也需要删除。最后得也需要删除。最后得 f(b)/xf(b

54、)/x，y/zy/z 第第4 4章章 经典逻辑推理经典逻辑推理合一合一:寻找一个合适的置换项来置换某一谓词公式中的变量，寻找一个合适的置换项来置换某一谓词公式中的变量，以使得两个表达式一致。以使得两个表达式一致。第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理三、合一算法：三、合一算法：第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理四、四、归结原理归结原理： 又称为消解原理，是鲁宾逊提出的一种证明子句集不可满足

55、性，又称为消解原理，是鲁宾逊提出的一种证明子句集不可满足性，从而实现定理证明的一种理论及方法。从而实现定理证明的一种理论及方法。 由谓词公式转化子句集的过程可以看出，在子句集中子句之间是由谓词公式转化子句集的过程可以看出，在子句集中子句之间是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。合取关系，其中只要有一个子句不可满足，则子句集就不可满足。另另外，空外，空子句是不可满足的。因此，若一个子句集中包含空子句，子句是不可满足的。因此，若一个子句集中包含空子句，则这个子句集一定是不可满足的。鲁宾逊归结原理就是基于这一认则这个子句集一定是不可满足的。鲁宾逊归结原理就是基于这一认识提出来的

56、。识提出来的。 其基本思想是：检查子句集其基本思想是：检查子句集S 中是否包含空子句，若包含，则中是否包含空子句，若包含，则S 不可满足；若不包含，就在子句集中选择合适的子句进行归结，一不可满足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结能推出空子句，就说明子句集旦通过归结能推出空子句，就说明子句集S 是不可满足的。是不可满足的。第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章

57、章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理五、归结反演五、归结反演第第4 4章章 经典逻辑推理经典逻辑推理例：例：已知已知第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理六、六、应用归结原理求取问题的答案应用归结原理求取问题的答案第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理例例 设设A,B,CA,B,C三

58、人中有人从不说真话，也有人从不说假话，某人三人中有人从不说真话，也有人从不说假话，某人向这三人分别提出同一个问题：谁是说谎者？向这三人分别提出同一个问题：谁是说谎者？A A答：答：BB和和C C都是说都是说谎者谎者” ” ;B;B答：答： AA和和C C都是说谎者都是说谎者” ” ;C;C答：答：AA和和B B中至少有一个是中至少有一个是说谎者说谎者”。求谁是老实人，谁是说谎者？。求谁是老实人，谁是说谎者？第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理第第4 4章章 经典逻辑推理经典逻辑推理七、七、归结策略归结策略对子句集进行归结时，关键的一步是从子句集中找出

59、可进行对子句集进行归结时，关键的一步是从子句集中找出可进行归结的一对子句。由于事先不知道哪两个子句可以进行归结，归结的一对子句。由于事先不知道哪两个子句可以进行归结，更不知道通过对哪些子句对的归结可以尽快地得到空子句，更不知道通过对哪些子句对的归结可以尽快地得到空子句，因而必须对子句集中的所有子句逐对地进行比较，对任何一因而必须对子句集中的所有子句逐对地进行比较，对任何一对可归结的子句对都进行归结，这样不仅要耗费许多时间，对可归结的子句对都进行归结，这样不仅要耗费许多时间，而且还会因为归结出了许多无用的归结式而多占用了许多存而且还会因为归结出了许多无用的归结式而多占用了许多存储空间，造成了时空

60、的浪费，降低了效率。为解决这些问题，储空间，造成了时空的浪费，降低了效率。为解决这些问题，人们研究出了多种归结策略。人们研究出了多种归结策略。这些归结策略大致可分为两大这些归结策略大致可分为两大类：一类是删除策略，另一类是限制策略。前一类通过删除类：一类是删除策略，另一类是限制策略。前一类通过删除某些无用的子句来缩小归结的范围，后一类通过对参加归结某些无用的子句来缩小归结的范围，后一类通过对参加归结的子句进行种种限制，尽可能地减小归结的盲目性，使其尽的子句进行种种限制，尽可能地减小归结的盲目性，使其尽快地归结出空子句。快地归结出空子句。第第4 4章章 经典逻辑推理经典逻辑推理 归结的一般过程归