《人工智能》（何泽奇）491-6教案 第6课 归结演绎推理

PAGE2PAGE2PAGE17PAGE17课题归结演绎推理课时2课时（90min）教学目标知识技能目标：掌握归结演绎推理的推理方法，并能够使用它们求解问题思政育人目标：弘扬精益求精、科学严谨、追求卓越的工匠精神熟悉确定性推理，探究技术原理，增加知识储备，培养钻研精神了解时代新科技，激发学习兴趣和创新思维，增强民族自信心教学重难点教学重点：归结演绎推理的概念教学难点：利用归结演绎推理解决问题教学方法讲授法、讨论法、问答法教学用具计算机、投影仪、多媒体课件、教材教学设计→→→传授新知（50min）→→课堂实训（20min）→课堂练习（7min）→课堂小结（3min）→作业布置（2min）教学过程主要教学内容及步骤设计意图课前任务【教师】布置课前任务，和学生负责人取得联系，让其提醒同学通过文旌课堂APP或其他学习软件，完成课前任务请各位同学回想一下以前数学所学过的反证法的证明过程，请写出反证法的一般步骤。【学生】完成课前任务通过课前任务，使学生了解本次课程的重点，增加学生的学习兴趣考勤

（2min）【教师】通过文旌课堂APP让学生签到【学生】签到，班干部交假条培养学生的组织纪律性，掌握学生的出勤情况问题导入（3min）【教师】提出以下问题，并邀请学生回答请各位同学回想一下以前数学所学过的反证法的证明过程，讨论一下如何使用人工智能的方法来进行描述。【学生】讨论、举手回答【教师】通过学生的回答引入要讲的知识，并板书：推理综合大家的讨论，咱们来看一下应该怎么使用人工智能的知识表示的方法来表示数学上常用的反证法的证明过程。本节课主要介绍归结演绎推理的相关知识。【学生】聆听通过问题导入的方法，引导学生主动思考，激发学生的学习兴趣传授新知

（50min）3.3归结演绎推理【教师】提问：什么是归结演绎推理？【学生】讨论、举手回答【教师】总结在人工智能中，几乎所有的问题都可以转化成一个定理证明问题。对于定理证明问题，如果用一阶谓词逻辑表示的话，该问题的实质就是要求对前提P和结论Q证明是永真的。然而，要证明谓词公式的永真性，必须对谓词公式中所含变元的所有个体域上的每一个解释进行验证，这是极其困难的。为了简化问题，在推理时常采用归结演绎推理。归结演绎推理是一种基于归结原理的机器推理技术。实际上，它是一种基于逻辑的“反证法”，把关于永真性的证明转化为关于不可满足性的证明，即要证明永真，只要能够证明是不可满足的就可以了。3.3.1子句集归结原理是在子句集的基础上讨论问题的，因此，讨论归结演绎推理之前需要先讨论子句集。1．基本定义原子谓词公式是一个不能再分解的命题。原子谓词公式及其否定，统称为文字。例如，、、、等都是文字。其中称为正文字，称为负文字，与为互补文字。任何文字的析取式称为子句，如、都是子句。任何文字本身也是子句，如、也是子句。不包含任何文字的子句称为空子句，记为NIL。【教师】重点强调由于空子句不含有文字，而且任何解释都不能满足它，所以，空子句是永假的、不可满足的。由子句构成的集合称为子句集。2．谓词公式化为子句集的基本步骤【教师】安排学生扫一扫教材上的二维码，了解“谓词公式化为子句集的基本步骤”。并结合教材和PPT内容讲解谓词公式在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集，从而能够比较容易地判断谓词公式的不可例如，现有谓词公式，请将其化为子句集。（1）通过谓词公式的等价性消去谓词公式中的“”和“”符号。使用谓词公式的等价式有（连接词化归律）上例可等价变换为【教师】重点强调谓词公式的等价式的推导过程如下。（2）通过谓词公式的等价性把否定符号（）移到紧靠谓词的位置上。使用谓词公式的等价式有（双重否定律）（德摩根定律）（德摩根定律）（量词转换律）（量词转换律）上例可等价变换为【教师】提醒：把否定符号移到紧靠谓词的位置上，减少了否定符号的辖域。（3）变元标准化。所谓变元标准化就是重新命名变元，是指在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字。例如，本例中量词约束的变元只有x、y，它们的名字已经不同，因此本例中不需要进行变元标准化操作。【教师】重点强调现有谓词公式，该公式中量词约束的变元有x、y、y，而和中的两个属于不同量词，对其变元进行标准化操作后可等价变换为。（4）化为前束形。前束形就是指把所有量词都移动到公式的前面，即前束形=（前缀）{母式}其中，（前缀）是量词串，{母式}是不含量词的谓词公式。化为前束形的方法是把所有量词都移到公式的左边，并且在移动时不能改变量词的相对顺序。【教师】提醒：由于在第（3）步已对变元进行了标准化，每个量词都有自己的变元，这就消除了任何由变元引起冲突的可能，因此这种移动是可行的。对于上面的例子，因为所有的量词已经位于公式的最左边，所以，不需要进行该步骤。（5）消去存在量词。消去存在量词时，需要区分以下两种情况。①存在量词不出现在全称量词的辖域内。此时只要用一个新的个体常量替换受该存在量词约束的变元，就可以消去存在量词。【教师】重点强调采用上述消去存在量词的方法是因为原谓词公式为真，则总能找到一个个体常量替换量词约束的变元后，仍然使谓词公式为真。这里的个体常量就是不含变元的Skolem函数。②若存在量词位于一个或多个全称量词的辖域内，例如，则需要用Skolem函数替换受该存在量词约束的变元y，即可见，Skolem函数把每个值，映射到存在的那个y。最后再消去该存在量词。【教师】重点强调用Skolem函数代替每个存在量词量化的变元的过程称为Skolem化。Skolem函数所使用的函数符号必须是新的。对于上面的例子，存在量词位于全称量词的辖域内，所以需要用Skolem函数来替换。设y的Skolem函数为，则替换后得到（6）化为Skolem标准形。其一般形式如下其中，M是子句的合取式，称为Skolem标准形的母式。一般利用谓词公式等价式的分配律或可把谓词公式化为Skolem标准形。对于上例，化为Skolem标准形后为（7）消去全称量词。由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此，谓词公式中可以省掉全称量词，但是剩下的母式，仍假设其变元是全称量词量化的。上例中消去全称量词后，为（8）消去合取词，把母式用子句集表示。对于上例有（9）子句变元标准化。对子句集中的某些变元重新命名，使任意两个子句中不出现相同的变元名。【教师】重点强调由于每一个子句都对应着母式中的一个合取元，并且所有变元都是由全称量词量化的，因此，任意两个不同子句的变元之间实际上不存在任何关系，故而，更换变元名是不会影响公式真值的。对于上例，可把子句集中第二个子句的变元名x更换为y，可得到显然，在子句集中各子句之间是合取关系。[教师】提问将下列谓词公式化为子句集。【学生】讨论、举手回答【教师】总结谓词公式可以化为相应的子句集，定理“谓词公式不可满足的重要条件是其子句集不可满足”表明了两者之间的不可满足性是等价的。由此定理可知，要证明一个谓词公式是不可满足的，只要证明相应的子句集是不可满足的就可以了。（1）消去蕴含符号“”，谓词公式可转换为（2）消去存在量词，谓词公式可转换为（3）化为Skolem标准形，谓词公式可转换为（4）消去全称量词，谓词公式可转换为（5）消去合取词，把母式用子句集表示，可得（6）子句变元标准化，把子句集中第二个子句的变元名x更换为y，可得3.3.2归结原理对谓词公式的不可满足性分析可以转化为对其子句集的不可满足性分析。为了判定子句集的不可满足性，就需要对子句集中的子句进行判定。对于不可满足性，子句与子句集之间具有以下联系。（1）由谓词公式化为子句集的过程可知，子句集中子句之间是合取关系。因此，子句集中只要有一个子句为不可满足的，则整个子句集就是不可满足的。（2）空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。基于以上叙述，鲁宾逊（J.A.Robinson）于1965年提出了归结原理。归结原理也称为消解原理，是一种通过证明子句集不可满足性，实现定理证明的理论及方法，它使机器定理证明进入了应用阶段。归结原理的基本思想是检查子句集S中是否含有空子句，如含有空子句，则表明S是不可满足的；若不含空子句，则使用归结法，在子句集S中选择合适的子句进行归结，一旦通过归结得到空子句，就说明子句集S是不可满足的。归结原理可分为命题逻辑归结原理和谓词逻辑归结原理。1．命题逻辑归结原理设与是子句集中的任意两个子句，如果中的文字与中的文字互补，称为归结。其中，称为和的归结式，和称为的亲本子句。例如，现有子句集设子句集中的子句分别为、、、，首先对和进行归结，得到然后再用和进行归结，得到最后用和进行归结，得到【教师】提问上例中，如果改变子句的归结顺序，是否可以得到相同的结果？请回答该问题，并给出归结过程。【学生】讨论、举手回答【教师】总结【教师】PPT展示“归结过程的树形表示”图片，讲解归结过程由上述推论可得到下列结论。（1）为证明子句集的不可满足性，只要对其中可进行归结的子句进行归结，并把归结式加入子句集中，或者用归结式代替它的亲本子句，然后证明新子句集的不可满足性就可以了。（2）如果归结过程中得到空子句，根据空子句的不可满足性，即可得到原子句集是不可满足的。2．谓词逻辑归结原理【教师】安排学生扫描二维码“谓词逻辑归结原理”，了解谓词逻辑归结原理【学生】扫码观看、了解原理在谓词逻辑中，由于子句集中的谓词一般都含有变元，因此不能像命题逻辑那样直接消去互补文字，而需要先用最一般合一对变元进行置换，然后才能进行归结。可见谓词逻辑的归结要比命题逻辑的归结更麻烦。例如，设有两个子句如下由于与不同，所以与不能直接进行归结，因此，使用最一般合一对两个子句分别进行置换，可得然后对它们进行归结，消去和，得到归结式如下【教师】讲授知识库中相关知识内容合一可以简单地理解为寻找相对变元的置换，从而使两个谓词公式一致。其中，置换是指在谓词公式中用置换项去置换变元。它们的相关定义及表示形式如下。（1）置换是形如的有限集合。其中，是互不相同的变元，是不同于的项（常量、变元或函数）。表示用置换，并且要求与不能相同，而且不能循环地出现在另一个中。例如，是一个置换，不是一个置换，因为x、y循环地出现在项、中。设是一个置换，是一个谓词逻辑表达式，对进行置换可记为。（2）设有公式集，若存在一个置换，可使，则称是F的一个合一。同时称、、…、是可合一的。设是公式集F的一个合一，如果对F的任意一个合一都存在一个置换，使得，则称是最一般合一。一个公式集的最一般合一是唯一的。用最一般合一去置换那些可合一的谓词公式，可使它们变成完全一致的谓词公式。谓词逻辑中关于归结的定义如下。设与是两个没有相同变元的子句，与分别是与中的文字，若是和的最一般合一，则称为与的二元归结式。[教师】提问现有子句和，求其二元归结式。【学生】讨论、举手回答【教师】总结、讲解答案选、，则与的最一般合一为。因此可得根据定义可得【教师】提醒：为了说明方便，此处的集合只是一种表示形式，不代表谓词公式的子句集。在谓词逻辑中，对子句进行归结推理时，要注意以下3个问题。（1）若归结的子句与中具有相同的变元时，需要更改其中一个变元的名字，否则可能无法做最一般合一，导致无法进行归结。[教师】提问设子句和，求其二元归结式。【学生】讨论、举手回答【教师】总结、讲解答案与中有相同的变元，不符合定义的要求，将中的变元名字x改为y，则。此时，、，与的最一般合一为。因此可得根据定义可得（2）在求归结式时，不能同时消去两个互补文字对，因为消去两个互补文字对所得的结果不是两个亲本子句的逻辑推论。（3）如果参加归结的子句内含有可合一的文字，则在进行归结之前，可对这些文字进行最一般合一，实现这些子句内部的化简。[教师】提问现有子句和，求其二元归结式。【学生】讨论、举手回答【教师】总结、讲解答案进行置换，可得。此时对和进行归结，以得到与的二元归结式。选、，则与的最一般合一为。因此可得根据定义可得【教师】重点强调在上例中，把称为的因子。一般来说，若子句中有两个或两个以上的文字具有最一般合一，则称为子句的因子。如果是一个单文字，则称它为的单元因子。应用因子的概念可对谓词逻辑中的归结原理给出如下定义。①与的二元归结式；②的因子与的二元归结式；③与的因子的二元归结式；④的因子与的因子的二元归结式。【教师】提醒：如果子句集没有归结出空子句，则既不能说S是不可满足的，也不能说S是可满足的。这是因为，有可能是没有找到合适的归结演绎步骤。但是如果确定不存在任何方法能将S归结出空子句，则可以确定S是可满足的。3.3.3归结反演要证明定理的不可满足性，只要证明其相应谓词公式子句集的不可满足性即可。归结原理指明了证明子句集不可满足性的方法，因此可用归结原理实现定理证明。【教师】重点强调根据定理“Q为的逻辑结论，当且仅当是不可满足的”可知，如欲证明定理的不可满足性，只需证明谓词公式是不可满足的。再根据定理“谓词公式不可满足的充要条件是其子句集不可满足”可知，要证明定理的不可满足性，只要证明其相应谓词公式子句集的不可满足性即可。应用归结原理证明定理的过程称为归结反演。其证明步骤如下。【教师】安排学生扫一扫教材上的二维码，了解“归结反演”。并结合教材和PPT内容讲解归结反演的步骤（1）将已知前提用谓词公式表示。设该谓词公式的形式为（2）将待证明的结论用谓词公式B表示，否定结论B，并将结论的否定与前提谓词公式组成新的谓词公式（3）求谓词公式G的子句集S。（4）应用归结原理，证明子句集S的不可满足性，从而证明谓词公式G的不可满足性。若谓词公式G不可满足，则说明对结论B的否定是错误的，从而证明了结论B为真，推断出定理成立。【教师】提出问题，假设任何通过计算机考试并获奖的人都是快乐的，任何勤奋学习或幸运的人都可以通过所有的考试。李不是幸运的人但他勤奋学习，任何勤奋学习的人都能获奖。求证：李是快乐的。【学生】举手回答老师提出的问题（1）用谓词公式表示待证明问题的前提。问题中涉及的谓词有表示x可以通过考试，表示x能获得奖励，表示x勤奋学习，表示x是幸运的，表示x是快乐的。将问题含有的前提条件用谓词公式表示如下。①“任何通过计算机考试并获奖的人都是快乐的”可表示为②“任何勤奋学习或幸运的人都可以通过所有的考试”可表示为③“李不是幸运的人但他勤奋学习”可表示为④“任何勤奋学习的人都能获奖”可表示为则待证明问题的前提可用谓词公式表示为（2）结论“李是快乐的”用谓词公式表示为否定结论，可表示为则含有否定结论的谓词公式G为（3）将上述谓词公式转化为子句集S为【教师】用PPT展示“归结过程”图片，进行过程讲解【学生】聆听、理解（4）应用归结原理进行归结，归结过程可用归结树表示归结过程中得到空子句，根据空子句的不可满足性，即可得到该子句集S是不可满足的，从而判定谓词公式G是不可满足的。因此，对于结论的否定是错误的，所以结论为真，即可证明“李是快乐的”。3.3.4应用归结原理求解问题【教师】安排学生扫一扫教材上的二维码，了解“应用归结原理求解问题”。并结合教材和PPT内容讲解应用归结原理求解问题的过程归结原理不仅可用于对已知结果的证明，还可用于对未知结果的求解。应用归结原理求解问题的步骤如下。（1）将已知前提F用谓词公式表示，并化为相应的子句集S。（2）把待求解的问题Q用谓词公式表示，并否定Q，再与答案谓词ANSWER构成析取式，即。【教师】提醒ANSWER是一个为了求解问题而专设的谓词，其变元必须与问题公式的变元完全一致。（3）把析取式化为子句集，并将其加入子句集S中，得到新的子句集。（4）应用归结原理对进行归结。（5）若得到归结式ANSWER，则答案就在ANSWER中。3.3.5案例：寻找新闻真相【教师】安排学生完成实践题，思考如何表示某记者到一个孤岛上采访，遇到一个难题，即岛上有许多人说假话，因而难以保证新闻报道的正确性。不过这个岛上的人有一特点，即说假话的人从来不说真话，说真话的人也从来不说假话。有一次，记者遇到了孤岛上的3个人，为了弄清楚谁说真话，谁说假话，他向3个人中的每一个人都提了一个同样的问题，即“谁是说谎者”。结果，A回答：“B和C都是说谎者”；B回答：“A和C都是说谎者”；C回答：“A和B中至少有一个是说谎者”。请问记者如何才能从这些回答中确定谁是说谎者，谁不是说谎者。【学生】讨论、思考【教师】总结（1）将已知前提用谓词公式表示。问题中涉及的谓词有表示x说真话。如果A说的是真话，则有如果A说的是假话，则有对B和C说的话做同样的处理，可得根据谓词公式的等价性将上述公式化为子句集S，可表示为（2）把待求解的问题用谓词公式表示，将其否定并与答案谓词ANSWER构成析取式。设u代表说真话的人，则有，将其否定与ANSWER作析取，可得（3）将析取式化为子句集并加入子句集S中，得到新的子句集，如下所示【教师】用PPT展示图片“对子句集进行归结的过程”，讲解归结的过程【学生】倾听、理解对子句集进行归结，其归结过程的归结树。由可知C是说真话的人，即C不是说谎者。【教师】重点强调通过分析可知，无论怎么对子句集进行归结，都推不出和。因此，A和B是说谎者，其证明过程如下。假设A说的不是真话，则有，把它的否定加入子句集S中，得到新的子句集，可得【教师】用PPT展示图片“对子句集的归结过程”，讲解对子句集的归结过程【学生】观看了解由此可知，假设“A说的不是真话”是正确的，可确定A是说谎者。同理，可证明B也是说谎者。【教师】提出问题，请写出证明B是说谎者的过程。【学生】回答老师提出的问题在归结过程中，子句集中的所有子句不一定会全部用到，只要在定理证明时能够归结出空子句，在求解问题答案时能够归结出ANSWER就可以了。【学生】聆听、记录、理解通过教师的讲解和课堂互动，使学生了解归结演绎推理的概念教师结合例子讲解谓词公式化为子句集的基本步骤讲完了基本的概念之后，通过例子的形式让学生加深对这些概念的理解。实训导入（3min）【教师】讲解动物识别系统案例实训报告要求（1）根据动物识别的专家知识，确定识别其余动物的产生式规则，建立规则库。（2）编写程序实现动物识别，并提交源代码。（3）总结实训的心得体会。【学生】聆听【教师】导入实训报告案例：动物识别系统案例通过导入环节，激发学生的学习兴趣课堂实训（20min）3.4动物识别系统【教师】讲解动物识别系统实训报告的编写1．实训目的（1）熟悉一阶谓词逻辑和产生式表示法。（2）掌握产生式系统的运行机制。（3）掌握基于确定性推理的基本方法。2．实训内容设计并编程实现一个能够识别鸵鸟、企鹅、信天翁、金钱豹、虎、长颈鹿和斑马这7种动物的识别系统。3．实训要求用一阶谓词逻辑和产生式规则表示知识，以动物识别系统的产生式规则为例，建立规则库和综合数据库，并能对它们进行添加、删除和修改操作。4．实训步骤（1）分析动物识别系统中的产生式规则。根据动物识别的专家知识，确定规则库中的产生式规则。例如，根据专家知识“如果该动物有羽毛，则该动物是鸟”“如果该动物会飞，而且会下蛋，则该动物是鸟”“如果该动物是鸟，有长脖子和长腿但是不会飞，则该动物是鸵鸟”等，可得到如下产生式规则。r1：IF该动物有羽毛THEN该动物是鸟r2：IF该动物会飞AND会下蛋THEN该动物是鸟r3：IF该动物是鸟AND有长腿AND有长脖子AND不会飞THEN该动物是鸵鸟（2）建立规则库。所有产生式规则组成规则库。【教师】提醒：上述产生式规则的表示形式直观易懂，但是不便于在计算机系统中存储与运算。因此，为了提高动物识别系统的性能，常用数字或字母表示已知事实。【教师】举例：例如，可用“1”表示“有羽毛”，用“2”表示“是鸟”，则有r1：IF1THEN2。（3）设计动物识别系统。在动物识别系统中，主要通过判断综合数据库中的前提条件与产生式规则的前提是否匹配实现动物识别。【教师】重点强调在动物识别系统中，用数字表示已知事实，则可用列表表示综合数据库。例如，综合数据库中的前提条件“该动物有羽毛，还有长腿和长脖子，但是不会飞”可表示为“list[i]=[1，3，4，5]”，其中“1”表示有羽毛，“3”表示有长腿，“4”表示有长脖子，“5”表示不会飞。遍历综合数据库中的前提条件“1”，发现它与规则r1的前提条件匹配，可得到结论“2”，并将“2”加入综合数据库中作为前提条件，可得“list[i]=[1，3，4，5，2]”，接着遍历综合数据库中的前提条件，依次可遍历到“2”“3”“4”和“5”与规则r3中的前提匹配，所以，可得出结论“6”（“6”表示是