人工智能导论课件(李俊丽)ch4-推理

《人工智能导论课件(李俊丽)ch4-推理》由会员分享，可在线阅读，更多相关《人工智能导论课件(李俊丽)ch4-推理（134页珍藏版）》请在装配图网上搜索。

1、信息工程与自动化学院信息工程与自动化学院第第4 章章 确定性推确定性推 理理1第4 章 确定性推 理1信息工程与自动化学院信息工程与自动化学院本章学习要点本章学习要点l掌握谓词公式的概念及可满足性的定义、置换与合掌握谓词公式的概念及可满足性的定义、置换与合一的概念，掌握求取最一般合一置换的方法。一的概念，掌握求取最一般合一置换的方法。l掌握归结原理及归结推理方法。掌握归结原理及归结推理方法。（重点在谓词逻辑中）重点在谓词逻辑中）l掌握掌握利用归结原理进行定理证明的方法利用归结原理进行定理证明的方法。l掌握掌握利用归结原理进行问题求解的方法。利用归结原理进行问题求解的方法。l了解归结过程中的控制

2、策略了解归结过程中的控制策略。2本章学习要点掌握谓词公式的概念及可满足性的定义、置换与合一的信息工程与自动化学院信息工程与自动化学院4.1 概述概述4.2 确定性推理确定性推理主主 要要 内内 容容34.1 概述4.2 确定性推理主 要 内 容3信息工程与自动化学院信息工程与自动化学院人工智能学科人工智能学科知识获取知识获取知识表示知识表示知识推理知识推理确定性推理确定性推理不确定性推理不确定性推理4人工智能学科知识获取知识表示知识推理确定性推理不确定性推理4信息工程与自动化学院信息工程与自动化学院 4.1.1 4.1.1 推理的基本概念推理的基本概念 推理的定义推理的定义 推理就是推理就是按

3、照某种策略从已有事实和知识推出按照某种策略从已有事实和知识推出结论的过程结论的过程。一般来说，人工智能系统中的智能推理过程是一般来说，人工智能系统中的智能推理过程是由一些程序来完成的，这些程序在人工智能系统中由一些程序来完成的，这些程序在人工智能系统中称为称为推理机推理机。4.1 4.1 推理概述推理概述5 4.1.1 推理的基本概念4.1 推理概述5信息工程与自动化学院信息工程与自动化学院4.1.2 4.1.2 推理的分类推理的分类 按推理的逻辑基础分类按推理的逻辑基础分类 1 1）演绎推理：）演绎推理：从已知的一般性知识出发，推理出适合于某种从已知的一般性知识出发，推理出适合于某种个别情况

4、的结论过程。个别情况的结论过程。即从即从一般到个别一般到个别的推理。的推理。常用形式：三段论法常用形式：三段论法(大前提、小前提、结论大前提、小前提、结论)64.1.2 推理的分类 按推理的逻辑基础分类 6信息工程与自动化学院信息工程与自动化学院【演绎推理实例】【演绎推理实例】音乐系的学生至少会演奏一种乐器；（大前提）音乐系的学生至少会演奏一种乐器；（大前提）李聪是音乐系的一名学生；（小前提）李聪是音乐系的一名学生；（小前提）李聪至少会演奏一种乐器。（结论）李聪至少会演奏一种乐器。（结论）7【演绎推理实例】音乐系的学生至少会演奏一种乐器；（大前提）7信息工程与自动化学院信息工程与自动化学院2

5、2）归纳推理：）归纳推理：从大量特殊事例出发，归纳出一般性结论从大量特殊事例出发，归纳出一般性结论的推理过程。的推理过程。即从即从个别到一般个别到一般的推理过程。的推理过程。归纳推理归纳推理完全完全归纳推理归纳推理不完全不完全归纳推理归纳推理枚举枚举归纳推理归纳推理类比类比归纳推理归纳推理特殊事例考察范围特殊事例考察范围推理使用方法推理使用方法82）归纳推理：从大量特殊事例出发，归纳出一般性结信息工程与自动化学院信息工程与自动化学院 3 3）默认推理：）默认推理：在知识不完全的情况下，假设某些条件已经在知识不完全的情况下，假设某些条件已经具备所进行的推理。具备所进行的推理。默认推理过程中可能会

6、出现一些无效推理，默认推理过程中可能会出现一些无效推理，但默认推理解决了在一个不完备知识集中进行推但默认推理解决了在一个不完备知识集中进行推理的问题。理的问题。9 3）默认推理：在知识不完全的情况下，假设某些条信息工程与自动化学院信息工程与自动化学院 1)1)确定性推理确定性推理 推理时所有用的知识和证据都是确定的，推理时所有用的知识和证据都是确定的，推出的结论也是确定的，其真值或者为真或者推出的结论也是确定的，其真值或者为真或者为假，没有第三种情况出现。为假，没有第三种情况出现。2)2)不确定性推理不确定性推理 推理时所用的知识和证据不都是确定的，推理时所用的知识和证据不都是确定的，推出的结

7、论也不确定的。推出的结论也不确定的。按所用知识的确定性分类按所用知识的确定性分类10 1)确定性推理 按所用知识的确定性分类10信息工程与自动化学院信息工程与自动化学院 1)1)单调推理单调推理 在推理过程中随着推理的向前推进及新知识的在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标。接近最终目标。2)2)非单调推理非单调推理 在推理过程中随着推理的向前推进及新知识的在推理过程中随着推理的向前推进及新知识的加入，不仅没有加强已推出的结论，反而要否定它加入，不仅没有加强已推出的结论，反而要否定它，使得推理

8、退回到前面的某一步，重新开始。，使得推理退回到前面的某一步，重新开始。按推理过程的单调性分类按推理过程的单调性分类11 1)单调推理 按推理过程的单调性分类11信息工程与自动化学院信息工程与自动化学院 1)1)启发式推理启发式推理 推理过程中应用与问题有关的启发性知识，推理过程中应用与问题有关的启发性知识，即解决问题的的策略、技巧及经验，以加快推即解决问题的的策略、技巧及经验，以加快推理过程，提高搜索效率。理过程，提高搜索效率。2)2)非启发式推理非启发式推理 在推理过程中，不运用启发性知识，只按在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理。这种方法缺乏对照一般的控制逻辑进行推

9、理。这种方法缺乏对求解问题的针对性，所以推理效率较低，容易求解问题的针对性，所以推理效率较低，容易出现出现“组合爆炸组合爆炸”问题。问题。按推理中所用知识是否具有启发性分类按推理中所用知识是否具有启发性分类12 1)启发式推理 按推理中所用知识是否具有启发性分信息工程与自动化学院信息工程与自动化学院4.1 概述概述4.2 确定性推理确定性推理主主 要要 内内 容容134.1 概述4.2 确定性推理主 要 内 容13信息工程与自动化学院信息工程与自动化学院确定性推理确定性推理归结推理归结推理演绎推理演绎推理命题命题逻辑逻辑谓词谓词逻辑逻辑海伯伦定理海伯伦定理数理数理逻辑逻辑基础基础命题命题逻辑逻

10、辑归结归结基本基本概念概念谓词逻辑谓词逻辑归结原理归结原理Skolem标准形，标准形，子句集子句集合一和置换，合一和置换，控制策略控制策略4.2 4.2 确定性推理确定性推理14确定性推理归结推理演绎推理命题逻辑谓词逻辑海伯伦定理数理逻辑信息工程与自动化学院信息工程与自动化学院【推理的逻辑基础】【推理的逻辑基础】逻辑是推理科学的研究。逻辑研究主要逻辑是推理科学的研究。逻辑研究主要是研究推理的过程是否正确，推理过程中是研究推理的过程是否正确，推理过程中各个语句之间的关系，而不考虑某一个语各个语句之间的关系，而不考虑某一个语句是否正确。句是否正确。命题逻辑命题逻辑和和谓词逻辑谓词逻辑属于经典逻辑，

11、是属于经典逻辑，是最先应用于人工智能的两种逻辑。其中谓最先应用于人工智能的两种逻辑。其中谓词逻辑是在命题逻辑的基础上发展起来的，词逻辑是在命题逻辑的基础上发展起来的，是一种表达能力很强的形式语言。是一种表达能力很强的形式语言。15【推理的逻辑基础】逻辑是推理科学的研究。逻辑信息工程与自动化学院信息工程与自动化学院1.命题命题 能够分辨真假的语句称为能够分辨真假的语句称为命题命题。一个语句如果不能再进一步分解成更简单的语句，一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为并且又是一个命题，则称此命题为原子命题原子命题。原子命题是命题中最基本的单位，常用大写原子命题是命题

12、中最基本的单位，常用大写字母字母P,Q,R等表示。等表示。4.2.1 4.2.1 命题逻辑基础命题逻辑基础16命题4.2.1 命题逻辑基础16信息工程与自动化学院信息工程与自动化学院判断以下句子，哪些是命题哪些不是？判断以下句子，哪些是命题哪些不是？1+1=10。快点走吧！快点走吧！雪是黑色的。雪是黑色的。西安是个古老的城市。西安是个古老的城市。明天是否开大会？明天是否开大会？如果天气好，那么我去散步。如果天气好，那么我去散步。是是不是不是是是是是不是不是是是17判断以下句子，哪些是命题哪些不是？是17信息工程与自动化学院信息工程与自动化学院：合取合取(与与),：析取析取(或或),：等价：等价

13、(当且仅当当且仅当)。：蕴含蕴含(IF THEN),：否定否定(非非)，P Q PQPQPQPTTTTTFFTTFTTTFTFFFFFFFTT命题逻辑真值表命题逻辑真值表2.连接词连接词18：合取(与),：析取(或),：等价(当且仅当)。：蕴信息工程与自动化学院信息工程与自动化学院连接词的优先级别连接词的优先级别19连接词的优先级别19信息工程与自动化学院信息工程与自动化学院原子命题是命题公式。原子命题是命题公式。A A是命题公式，则是命题公式，则A A也是命题公式。也是命题公式。若若A A 和和B B都是命题公式，则都是命题公式，则ABAB、ABAB、A AB B、A BA B也都是命题公式

14、。也都是命题公式。按照上述规则由原子命题、连接词及圆括按照上述规则由原子命题、连接词及圆括号所组成的字符串称为号所组成的字符串称为命题公式命题公式。3.命题公式命题公式20原子命题是命题公式。3.命题公式20信息工程与自动化学院信息工程与自动化学院 他既聪明又用功。他既聪明又用功。应届高中生，得过数学或物理竞赛的一等奖，应届高中生，得过数学或物理竞赛的一等奖，保送上大学。保送上大学。设设P：他聪明。：他聪明。Q：他用功。转换为：他用功。转换为：P Q。设设P：应届高中生。：应届高中生。Q：保送上大学。：保送上大学。A：得过：得过数学竞赛一等奖。数学竞赛一等奖。B：得过物理竞赛一等奖。表：得过物

15、理竞赛一等奖。表示为：示为：P (AB)Q例：将陈述句转化为命题公式。例：将陈述句转化为命题公式。【命题公式实例】【命题公式实例】21 他既聪明又用功。设P：他聪明。Q：他用功。转换为：P信息工程与自动化学院信息工程与自动化学院1.1.基本概念基本概念4.2.2 4.2.2 一阶谓词逻辑基础一阶谓词逻辑基础个体：独立存在的物体（抽象或具体）个体：独立存在的物体（抽象或具体）个体：个体：独立存在的物体（抽象或具体）独立存在的物体（抽象或具体）谓词：谓词：用于刻画个体性质、状态或个体间关系。用于刻画个体性质、状态或个体间关系。53 Greater(5,3)李白是诗人李白是诗人 Poet(LiBai

16、)一元谓词一元谓词二元谓词二元谓词一阶谓词一阶谓词221.基本概念4.2.2 一阶谓词逻辑基础个体：独立存在的物体信息工程与自动化学院信息工程与自动化学院3.谓词公式谓词公式2.连接词：连接词：，单个谓词是谓词公式，称为原子谓词公式。单个谓词是谓词公式，称为原子谓词公式。若若A是谓词公式，则是谓词公式，则 A也是谓词公式。也是谓词公式。若若A，B都都是谓词公式，则是谓词公式，则(AB)，(AB)，(AB)，(A B)也是谓词公式也是谓词公式。若若A是谓词公式，则是谓词公式，则 也是谓词公也是谓词公式。式。只有有限次的应用上述只有有限次的应用上述4 4条规则构成的符号串条规则构成的符号串才是谓词

17、公式。才是谓词公式。233.谓词公式2.连接词：，单个谓词是谓词信息工程与自动化学院信息工程与自动化学院 位于量词后面的单个谓词或者用括弧括起来位于量词后面的单个谓词或者用括弧括起来的的合式公式称为的的合式公式称为量词的辖域量词的辖域。在辖域内与量词同名的变元称为在辖域内与量词同名的变元称为约束变元约束变元，不受约束的变元称为不受约束的变元称为自由变元自由变元。4.4.量词辖域与约束变元量词辖域与约束变元全称量词全称量词全称量词的辖域全称量词的辖域存在量词存在量词存在量词的辖域存在量词的辖域约束变元约束变元自由变元自由变元24 位于量词后面的单个谓词或者用括弧括起来的的合式公式称信息工程与自动

18、化学院信息工程与自动化学院永真式永真式:如果谓词公式如果谓词公式P P在每个非空个体域上均取得真值在每个非空个体域上均取得真值T T，则称则称P P永真永真。永假式永假式:如果谓词公式如果谓词公式P P在每个非空个体域上均取得真值在每个非空个体域上均取得真值F F，则，则称称P P永假永假。可满足式可满足式:对于谓词公式对于谓词公式P P，如果至少存在一个值使得，如果至少存在一个值使得P P的真的真值为值为T T，则称公式，则称公式P P是可满足的是可满足的。不可满足式不可满足式:对于谓词公式对于谓词公式P P，如果不存在任何值使得，如果不存在任何值使得P P的真的真值为值为T T，则称公式，

19、则称公式P P是不可满足的是不可满足的。5.5.谓词公式的永真性谓词公式的永真性25永真式:如果谓词公式P在每个非空个体域上均取得真值T，则称信息工程与自动化学院信息工程与自动化学院 交换律：交换律：PQPQTTTTFTFTTFFFPQPQTTTTFFFTFFFF6.谓词公式的等价性谓词公式的等价性26 交换律：PQPQ信息工程与自动化学院信息工程与自动化学院 结合律：结合律：PQRPQ(PQ)R(Q R)P(Q R)TTTTTTTTTFTTTTTFTTTTTTFFTTFTFTTTTTTFTFTTTTFFTFTTTFFFFFFF步骤123427 结合律：PQRPQ(PQ)R(Q R)P(信息工

20、程与自动化学院信息工程与自动化学院 结合律：结合律：PQRPQ(PQ)R(Q R)P(Q R)TTTTTTTTTFTFFFTFTFFFFTFFFFFFFTTFFTFFTFFFFFFFTFFFFFFFFFFF步骤123428 结合律：PQRPQ(PQ)R(Q R)P(信息工程与自动化学院信息工程与自动化学院 分配律：分配律：PQR(QR)P(QR)(PQ)(PR)(PQ)(PR)TTTTTTTTTTFFTTTTTFTFTTTTTFFFTTTTFTTTTTTTFTFFFTFFFFTFFFTFFFFFFFFF步骤1234529 分配律：PQR(QR)P(QR)(PQ)(P信息工程与自动化学院信息工程

21、与自动化学院 分配律：分配律：PQR(QR)P(QR)(PQ)(PR)(PQ)(PR)TTTTTTTTTTFTTTFTTFTTTFTTTFFFFFFFFTTTFFFFFTFTFFFFFFTTFFFFFFFFFFFF步骤1234530 分配律：PQR(QR)P(QR)(PQ)(信息工程与自动化学院信息工程与自动化学院 狄狄 摩根律：摩根律：PQPQ(PQ)PQPQTTTFFFFTFTFFTFFTTFTFFFFFTTTT步骤1234531 狄 摩根律：PQPQ(PQ)PQPQ信息工程与自动化学院信息工程与自动化学院 狄狄 摩根律：摩根律：PQPQ(PQ)PQPQTTTFFFFTFFTFTTFTFT

22、TFTFFFTTTT步骤1234532 狄 摩根律：PQPQ(PQ)PQPQ信息工程与自动化学院信息工程与自动化学院 吸收律：吸收律：PQPQP(PQ)TTTFTFFTFTFFFFFF步骤1233 吸收律：PQPQP(PQ)TTTFTFFTFTF信息工程与自动化学院信息工程与自动化学院 吸收律：吸收律：PQPQ P(PQ)TTTTTFTTFTTFFFFF步骤1234 吸收律：PQPQ P(PQ)TTT信息工程与自动化学院信息工程与自动化学院 同一律：同一律：P0P0TFTTFTFFFFFF步骤1P1P1TTTTTTFTFFTF步骤1 零律：零律：35 同一律：P0P0TFTTFTFFFFFF步

23、骤1P1P信息工程与自动化学院信息工程与自动化学院 双重否定律：双重否定律：排中律：排中律：矛盾律：矛盾律：36 双重否定律：排中律：矛盾律：36信息工程与自动化学院信息工程与自动化学院 蕴涵等值式：蕴涵等值式：PQPQ P PQTTTFTTFFFFFTTTTFFTTT步骤12337 蕴涵等值式：PQPQPPQTTTFTTFFFF信息工程与自动化学院信息工程与自动化学院PQPQQP(PQ)(PQ)TTTTTTTFFFTFFTFTFFFFTTTT 等价等值式：等价等值式：38PQPQQP(PQ)(PQ)TTTTTTTFF信息工程与自动化学院信息工程与自动化学院 逆反律：逆反律：PQPQP Q Q

24、PTTTFFTTFFFTFFTTTFTFFTTTT39 逆反律：PQPQP Q QPTTTFFTT信息工程与自动化学院信息工程与自动化学院 归谬论：归谬论：PQPQ QP Q(PQ)(P Q)PTTTFFFFTFFTTFFFTTFTTTFFTTTTT40 归谬论：PQPQ QP Q(PQ)(P信息工程与自动化学院信息工程与自动化学院合取式：合取式：P与与Q，记做，记做 PQ析取式：析取式：P或或Q，记做，记做 PQ蕴含式：蕴含式：如果如果P则则Q，记做，记做 PQ等价式：等价式：P当且仅当当且仅当Q，记做，记做 P Q7.谓词公式型式：谓词公式型式：41合取式：P与Q，记做 PQ7.谓词公式型

25、式：41信息工程与自动化学院信息工程与自动化学院简单合取式简单合取式：仅由有限个命题变量或其否定构成的仅由有限个命题变量或其否定构成的合取式。合取式。简单析取式简单析取式：仅由有限个命题变量或其否定构成的仅由有限个命题变量或其否定构成的析取式。析取式。合取范式合取范式：仅由有限个简单析取式组成的合取式。仅由有限个简单析取式组成的合取式。如：如：P(P Q)(P Q)析取范式析取范式：仅由有限个简单合取式组成的析取式。仅由有限个简单合取式组成的析取式。如：如：P(P Q)(P Q)42简单合取式：仅由有限个命题变量或其否定构成的合取式。42信息工程与自动化学院信息工程与自动化学院例：求取例：求取

26、P(QR)S的合取范式。的合取范式。解：解：43例：求取P(QR)S的合取范式。解：43信息工程与自动化学院信息工程与自动化学院 把公式中量词辖域中的同名约束变元都统一改把公式中量词辖域中的同名约束变元都统一改成相同的名字，且不能与辖域内的自由变元同名，成相同的名字，且不能与辖域内的自由变元同名，公式的其余部分不变。公式的其余部分不变。例：例：更名为：更名为：5.5.换名规则换名规则44 把公式中量词辖域中的同名约束变元都统一改成相同的名字信息工程与自动化学院信息工程与自动化学院 约束变元换名规则约束变元换名规则:量词转换律量词转换律:量词分配律量词分配律:6.6.基本规则和等价式基本规则和等

27、价式45 约束变元换名规则:量词转换律:量词分配律:信息工程与自动化学院信息工程与自动化学院 消去量词等价式消去量词等价式:设个体域为有穷集合设个体域为有穷集合(a1,a2,an)量词辖域收缩与扩张等价式量词辖域收缩与扩张等价式:46 消去量词等价式:设个体域为有穷集合(a1,a2,信息工程与自动化学院信息工程与自动化学院 量词辖域收缩与扩张等价式量词辖域收缩与扩张等价式(续续):47 量词辖域收缩与扩张等价式(续):47信息工程与自动化学院信息工程与自动化学院4.2.3 4.2.3 自然演绎推理方法自然演绎推理方法 从一组已知为真的事实出发，直接运用命题逻从一组已知为真的事实出发，直接运用命

28、题逻辑或谓词逻辑中的推理规则推出结论的过程。辑或谓词逻辑中的推理规则推出结论的过程。最基本的推理规则有：最基本的推理规则有：假言三段论假言三段论 T规则规则 假言推理假言推理 P规规则则 拒取式拒取式 484.2.3 自然演绎推理方法 从一组已信息工程与自动化学院信息工程与自动化学院【演绎推理实例】【演绎推理实例】l如果一个人大学毕业，则他就具有独立生活的能如果一个人大学毕业，则他就具有独立生活的能力。力。l如果一个人具有独立生活的能力，则他就可以离如果一个人具有独立生活的能力，则他就可以离开父母。开父母。l如果一个人大学毕业，则他就可以离开父母。如果一个人大学毕业，则他就可以离开父母。假言三

29、段论假言三段论49【演绎推理实例】如果一个人大学毕业，则他就具有独立生活的能力信息工程与自动化学院信息工程与自动化学院【演绎推理实例】【演绎推理实例】l如果如果S是音乐系学生，则是音乐系学生，则S至少会演奏一样乐器。至少会演奏一样乐器。l张艺是音乐系学生。张艺是音乐系学生。l张艺至少会演奏一样乐器。张艺至少会演奏一样乐器。假言推理假言推理50【演绎推理实例】如果S是音乐系学生，则S至少会演奏一样乐器。信息工程与自动化学院信息工程与自动化学院【演绎推理实例】【演绎推理实例】l如果如果S是音乐系学生，则是音乐系学生，则S至少会演奏一样乐器。至少会演奏一样乐器。l张艺不会演奏任何乐器。张艺不会演奏任

30、何乐器。l张艺不是音乐系学生。张艺不是音乐系学生。拒取式推理拒取式推理51【演绎推理实例】如果S是音乐系学生，则S至少会演奏一样乐器。信息工程与自动化学院信息工程与自动化学院【演绎推理常见错误】【演绎推理常见错误】l如果如果S是音乐系学生，则是音乐系学生，则S至少会演奏一样乐器。至少会演奏一样乐器。l张艺会演奏电子琴。张艺会演奏电子琴。l张艺是音乐系学生。张艺是音乐系学生。肯定后件错误肯定后件错误52【演绎推理常见错误】如果S是音乐系学生，则S至少会演奏一样乐信息工程与自动化学院信息工程与自动化学院【演绎推理常见错误】【演绎推理常见错误】l如果如果S是音乐系学生，则是音乐系学生，则S至少会演奏

31、一样乐器。至少会演奏一样乐器。l张艺不是音乐系学生。张艺不是音乐系学生。l张艺不会演奏任何一样乐器。张艺不会演奏任何一样乐器。否定前件错误否定前件错误53【演绎推理常见错误】如果S是音乐系学生，则S至少会演奏一样乐信息工程与自动化学院信息工程与自动化学院【实例】【实例】设已知如下事实：设已知如下事实：R,S,RT,ST P,P Q求证：求证：Q为真。为真。证明：因为证明：因为 所以所以Q为真。为真。P规则及假言推理规则及假言推理引入合取词引入合取词T规则及假言推理规则及假言推理T规则及假言推理规则及假言推理54【实例】设已知如下事实：证明：因为P规则及假言推理54信息工程与自动化学院信息工程与

32、自动化学院【演绎推理的特点】【演绎推理的特点】l只是将蕴涵在一般性知识前提中的事实揭示出来，只是将蕴涵在一般性知识前提中的事实揭示出来，不能增殖新的知识；不能增殖新的知识；l由已知事实推出的结论可能有多个；由已知事实推出的结论可能有多个；l优点在于符合人的思维习惯，易于理解；优点在于符合人的思维习惯，易于理解；l缺点在于容易产生知识或规则爆炸，不利于对复缺点在于容易产生知识或规则爆炸，不利于对复杂问题的求解。杂问题的求解。55【演绎推理的特点】只是将蕴涵在一般性知识前提中的事实揭示出信息工程与自动化学院信息工程与自动化学院4.2.4 4.2.4 归结推理方法归结推理方法 归结法是与自然演绎法完

33、全不同的新的逻辑演归结法是与自然演绎法完全不同的新的逻辑演算算法。算算法。归结法的基本原理是采用归结法的基本原理是采用反证法反证法（也称为反演（也称为反演推理方法）：将待证明的表达式转换成为逻辑公式推理方法）：将待证明的表达式转换成为逻辑公式（谓词公式），然后再进行归结，归结能顺利完成，（谓词公式），然后再进行归结，归结能顺利完成，则证明原公式是正确的。则证明原公式是正确的。564.2.4 归结推理方法 归结法是与自信息工程与自动化学院信息工程与自动化学院1.1.范式范式谓词演算公式的标准型，即范式。一般有谓词演算公式的标准型，即范式。一般有2种范式：种范式：l 前束型范式前束型范式 一个谓词

34、公式，如果它的所有量词均非否定地一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且它的辖域一直延伸到公式出现在公式的最前面，且它的辖域一直延伸到公式之末，同时公式中不出现连接词之末，同时公式中不出现连接词、，这种形，这种形式的谓词公式称为前束型范式。式的谓词公式称为前束型范式。571.范式谓词演算公式的标准型，即范式。一般有2种范式：57信息工程与自动化学院信息工程与自动化学院公式的首标公式的首标命题演算公式命题演算公式优点：量词全部集中在公式的前面；优点：量词全部集中在公式的前面；缺点：其首标杂乱无章，量词排列没有一定的缺点：其首标杂乱无章，量词排列没有一定的规则。规则。58公式

35、的首标命题演算公式优点：量词全部集中在公式的前面；58信息工程与自动化学院信息工程与自动化学院例：求下式的前束范式例：求下式的前束范式解：解：59例：求下式的前束范式解：59信息工程与自动化学院信息工程与自动化学院 从前束型范式中消去全部存在量词所得到的从前束型范式中消去全部存在量词所得到的公式，称为公式，称为SkolemSkolem范式，或范式，或Skolem标准型。标准型。Skolem标准型的一般形式为：标准型的一般形式为：l Skolem范式范式60 从前束型范式中消去全部存在量词所得到的公式，称为Sk信息工程与自动化学院信息工程与自动化学院公式的首标公式的首标（不出现存在量词）（不出现

36、存在量词）命题演算公式命题演算公式f(x)代替代替y61公式的首标命题演算公式f(x)代替y61信息工程与自动化学院信息工程与自动化学院【Skolem范式的获取步骤】范式的获取步骤】1.1.消去谓词公式消去谓词公式G G中的蕴涵（中的蕴涵（）和双条件（）和双条件（）符号；符号；2.2.减少否定符号（减少否定符号（）的辖域，使否定符号最多只）的辖域，使否定符号最多只作用到一个谓词上；作用到一个谓词上；3.3.重新命名变元，使所有的变元的名字均不同，并重新命名变元，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。且自由变元及约束变元亦不同。62【Skolem范式的获取步骤】消去谓词公式G中

37、的蕴涵（）和信息工程与自动化学院信息工程与自动化学院4.4.消去存在量词（消去存在量词（）。将该量词约束的变量用任意）。将该量词约束的变量用任意常量常量(a,b等等)或任意变量的函数或任意变量的函数(f(x),g(y)等等)代代替。替。如果存在量词左边没有任何任意量词，则只将其如果存在量词左边没有任何任意量词，则只将其改写为个体常量；改写为个体常量；如果存在量词的左边有任意量词，消去时该变量如果存在量词的左边有任意量词，消去时该变量改写为任意量词的函数。改写为任意量词的函数。63消去存在量词（）。将该量词约束的变量用任意常量(a,b等信息工程与自动化学院信息工程与自动化学院5.5.把全称量词全

38、部移到公式的左边，并使每个量词把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分；的辖域包括这个量词后面公式的整个部分；6.6.母式化为合取范式。母式化为合取范式。7.7.至此所得的公式就是谓词公式至此所得的公式就是谓词公式G G的的skolemskolem标准型。标准型。64把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词信息工程与自动化学院信息工程与自动化学院例：将下式化为例：将下式化为Skolem标准形。标准形。解：解：消去消去符号符号 ，得：，得：深入到量词内部，得：深入到量词内部，得：【SkolemSkolem范式的获取实例】范式的获取实例】6

39、5例：将下式化为Skolem标准形。解：消去符号 信息工程与自动化学院信息工程与自动化学院 任意量词左移，利用分配律，得：任意量词左移，利用分配律，得：变量易名，存在量词左移，直至所有的量词移到变量易名，存在量词左移，直至所有的量词移到 前面，得：前面，得：66 任意量词左移，利用分配律，得：变量易名，存在量词左移信息工程与自动化学院信息工程与自动化学院 消去存在量词，略去任意量词，消去存在量词，略去任意量词，得得Skolem标准形标准形：67 消去存在量词，略去任意量词，67信息工程与自动化学院信息工程与自动化学院例：例：将下式化为将下式化为Skolem标准形。标准形。解：解：68例：将下式

40、化为Skolem标准形。解：68信息工程与自动化学院信息工程与自动化学院6969信息工程与自动化学院信息工程与自动化学院2.2.子句与子句集子句与子句集 原子公式：原子公式：不含任何连接词的谓词公式。不含任何连接词的谓词公式。文文 字：字：原子或原子的否定。原子或原子的否定。子子 句：句：由一些文字组成的析取式。由一些文字组成的析取式。空空 子子 句：句：不包含任何文字的子句，表示为不包含任何文字的子句，表示为NILNIL。空子句是永假的。空子句是永假的。子子 句句 集：集：由子句构成的集合。由子句构成的集合。702.子句与子句集 原子公式：不含任何连接词的谓词公式。70信息工程与自动化学院信

41、息工程与自动化学院【子句集【子句集S S的求取】的求取】由于由于Skolem 标准型的母式已为合取式，从而母标准型的母式已为合取式，从而母式的每一个合取项都是一个子句。式的每一个合取项都是一个子句。子句集的求取方法为：子句集的求取方法为：将谓词公式将谓词公式G化为化为 Skolem 标准型；标准型；消去消去Skolem 标准型前面的全称量词；标准型前面的全称量词；用用“，”取代取代“”，并表示为成集合形式。，并表示为成集合形式。71【子句集S的求取】由于Skolem 标准型信息工程与自动化学院信息工程与自动化学院【实例】【实例】72【实例】72信息工程与自动化学院信息工程与自动化学院定理定理1

42、 1：G G是不可满足的是不可满足的 S S是不可满足的是不可满足的【子句集【子句集S S与谓词公式与谓词公式G G的关系】的关系】证明一个公式的不可满足性，转化为证证明一个公式的不可满足性，转化为证明其子句集明其子句集S S的不可满足性。的不可满足性。73定理1：G是不可满足的 S是不可满足的【子句集S与谓信息工程与自动化学院信息工程与自动化学院3.Robinson3.Robinson归结原理（消解原理）归结原理（消解原理）检查子句集检查子句集S S中是否有空子句，若有，则中是否有空子句，若有，则表明表明S S是不可满足的；若没有，就在子句集是不可满足的；若没有，就在子句集中选择合适的子句对

43、其进行归结推理，如中选择合适的子句对其进行归结推理，如果能推出空子句，就说明子句集是果能推出空子句，就说明子句集是S S是不可是不可满足的。满足的。什么是归结？什么是归结？如何进行归结推理？如何进行归结推理？743.Robinson归结原理（消解原理）检查子句信息工程与自动化学院信息工程与自动化学院（1 1）命题逻辑中的归结原理）命题逻辑中的归结原理l若若P P是原子公式，则称是原子公式，则称P P与与 为为互补文字互补文字。l设设C C1 1,C,C2 2是命题逻辑中的两个子句，是命题逻辑中的两个子句，C C1 1中有文字中有文字L L1 1，C C2 2中有文字中有文字L L2 2，且，且

44、L L1 1与与L L2 2互补，从互补，从C C1 1,C,C2 2中分别删除中分别删除L L1 1,L,L2 2，再将剩余部分进行析取，构成一个新子句，再将剩余部分进行析取，构成一个新子句为为C C1212，这一过程称为，这一过程称为归结归结，所得到的子句，所得到的子句C C1212称为称为C C1 1,C,C2 2的的归结式归结式(或消解式或消解式)，C C1 1,C,C2 2称为其归结式称为其归结式C C1212的的亲本子句亲本子句，L L1 1,L,L2 2称为称为消解基消解基。75（1）命题逻辑中的归结原理若P是原子公式，则称P与 为信息工程与自动化学院信息工程与自动化学院 设：设

45、：C1=乛乛PQR C2=乛乛QS 求：求：C1,C2的归结式。的归结式。解：解：由于由于Q和乛和乛Q是互补文字，则消去互补文是互补文字，则消去互补文字后得：字后得：C12=乛乛PRS76 设：C1=乛PQR76信息工程与自动化学院信息工程与自动化学院 定理定理2 2：归结式：归结式C C1212是其亲本子句是其亲本子句C C1 1、C C2 2的逻辑的逻辑结论。结论。推推 论：论：设设C C1 1,C C2 2是子句集是子句集S S的两个子句，的两个子句，C C1212是它们是它们的归结式，则若用的归结式，则若用C C1212加入到子句集加入到子句集S S后得到新子句后得到新子句集集S S1

46、 1，则由，则由S S1 1和和S S在在不可满足的意义下是等价的。不可满足的意义下是等价的。即即S S不可满足不可满足 S S1 1不可满足不可满足77 定理2：归结式C12是其亲本子句C1、C2的逻辑结论。7信息工程与自动化学院信息工程与自动化学院【归结推理过程】【归结推理过程】对子句集对子句集S S中的各个子句间使用归结推理规则；中的各个子句间使用归结推理规则；将归结所得的归结式放入子句集将归结所得的归结式放入子句集S S中，得到新子句中，得到新子句集集SS；检查子句集检查子句集SS中是否有空子句（中是否有空子句（NILNIL），若有，），若有，则停止推理；否则，转步骤则停止推理；否则，

47、转步骤；置置S=SS=S，转步骤，转步骤。按照上述推理，在推理过程中，当子句集按照上述推理，在推理过程中，当子句集S S中中出现空子句，即证明出现空子句，即证明S S是不可满足的。是不可满足的。78【归结推理过程】对子句集S中的各个子句间使用归结推理规则；7信息工程与自动化学院信息工程与自动化学院【例题】【例题】证明子句集证明子句集PP乛乛Q,Q,乛乛P,QP,Q是不可满足的。是不可满足的。证：证：(1)P(1)P乛乛Q.Q.已知已知(2)(2)乛乛P .P .已知已知(3)Q .(3)Q .已知已知(4)(4)乛乛Q .Q .由由(1),(2)(1),(2)归结归结(5)NIL .(5)NI

48、L .由由(3),(4)(3),(4)归结归结由于由于S S中出现空子句，所以中出现空子句，所以S S是不可满足的。是不可满足的。79【例题】证明子句集P乛Q,乛P,Q是不可满足的信息工程与自动化学院信息工程与自动化学院【例题】【例题】用归结原理证明用归结原理证明R R是是P,(PQ)R,(SU)Q,UP,(PQ)R,(SU)Q,U的逻辑结果。的逻辑结果。【提示】【提示】要证明要证明PQPQ是永真的，考虑反证法，先否是永真的，考虑反证法，先否定逻辑结论定逻辑结论Q Q，再由否定后的逻辑结论，再由否定后的逻辑结论Q Q及前提及前提条件条件P P出发推出矛盾，即证明原问题。出发推出矛盾，即证明原问

49、题。为证明为证明PQPQ，实际实际上只需证明，实际实际上只需证明P P Q Q的的不可满足性。不可满足性。80【例题】用归结原理证明R是P,(PQ)R,(SU)信息工程与自动化学院信息工程与自动化学院证：证：由已知前提条件和否定逻辑结论可得到子句集由已知前提条件和否定逻辑结论可得到子句集S S：S=S=P,P,乛乛PP乛乛QR,QR,乛乛SQ,SQ,乛乛UQ,U,UQ,U,乛乛R R 然后对该子句集施行归结，归结过程用下面的然后对该子句集施行归结，归结过程用下面的归结演绎树表示。归结演绎树表示。由于最后推出了空子句，所以子句集由于最后推出了空子句，所以子句集S S不可满不可满足。足。即命题公式

50、即命题公式 P(P(乛乛PP乛乛R)(R)(乛乛SQ)SQ)(乛乛UQ)UUQ)U乛乛R R不可满足，从而不可满足，从而R R是题设前提的是题设前提的逻辑结果。逻辑结果。81证：81信息工程与自动化学院信息工程与自动化学院8282信息工程与自动化学院信息工程与自动化学院（2 2）一阶谓词逻辑中的归结原理）一阶谓词逻辑中的归结原理 在一阶谓词逻辑中，因为谓词逻辑中的子句含在一阶谓词逻辑中，因为谓词逻辑中的子句含有个体变元，所以不能直接消去互补文字进行子有个体变元，所以不能直接消去互补文字进行子句归结，而是要首先使用句归结，而是要首先使用置换和合一置换和合一的思想，对的思想，对子句中的某些变元进行

51、合一置换，对置换后的新子句中的某些变元进行合一置换，对置换后的新子句再次使用归结。子句再次使用归结。83（2）一阶谓词逻辑中的归结原理 在一阶谓词逻辑中，信息工程与自动化学院信息工程与自动化学院例如：例如：假设有如下两个子句：假设有如下两个子句：C1=P(x)Q(x)C2=乛乛P(a)R(y)直接比较，似乎两者中不含互补文字，但如果我们用直接比较，似乎两者中不含互补文字，但如果我们用a替替换换C1中的中的x，则得到，则得到 C1=P(a)Q(a)C2=乛乛P(a)R(y)于是根据命题逻辑中的消解原理，得于是根据命题逻辑中的消解原理，得C1和和C2的消解式的消解式 C3=Q(a)R(y)所以，要

52、在谓词逻辑中应用消解原理，则一般需要对所以，要在谓词逻辑中应用消解原理，则一般需要对个体变元作适当的替换。个体变元作适当的替换。84例如：假设有如下两个子句：84信息工程与自动化学院信息工程与自动化学院&置换与合一置换与合一 在基于知识进行推理时，模式匹配时必须要进在基于知识进行推理时，模式匹配时必须要进行的一项工作。为了使已知事实与知识库中的知行的一项工作。为了使已知事实与知识库中的知识完全匹配，需要进行某种变元置换，所以先介识完全匹配，需要进行某种变元置换，所以先介绍置换与合一的有关概念及方法。绍置换与合一的有关概念及方法。85 置换与合一 在基于知识进行推理时，模式信息工程与自动化学院信

53、息工程与自动化学院 置换可以简单理解为：在一个谓词公式中用置换可以简单理解为：在一个谓词公式中用置换项去置换变量。置换项去置换变量。定定义：形如形如 的有限集合。的有限集合。其中，其中，是互不相同的变量，即置换是互不相同的变量，即置换 变量；变量；是是不同于不同于 xi 的项（常量、变量、的项（常量、变量、函数），即置换项；函数），即置换项；1.1.置换置换86 置换可以简单理解为：在一个谓词公式中用置换项去置换变量。信息工程与自动化学院信息工程与自动化学院 ti/xi 表示用表示用 ti 置换置换 xi,并要求并要求 ti 与与 xi 不能不能相同，而且相同，而且 xi 不能循环地出现在另一

54、个不能循环地出现在另一个 ti 中。中。例如例如：是一个置换；是一个置换；那么置换结果为：那么置换结果为：87 ti/xi 表示用 ti 置换 xi,并要求 ti信息工程与自动化学院信息工程与自动化学院设设 是两个置换，则将集合是两个置换，则将集合中符合下列条件的元素删除：中符合下列条件的元素删除：(1)ti/xi 当当ti=xi (2)ui/yi 当当yix1,x2,xn如此得到的集合仍然是一个替换，该替换称为如此得到的集合仍然是一个替换，该替换称为与与的的复合复合(或乘积或乘积)，记作，记作。置换的复合置换的复合88设 置换的复合88信息工程与自动化学院信息工程与自动化学院例例：设：设 求

55、求与与的合的合成。成。解：先求出集合解：先求出集合满足定义中的条件需删除，得：满足定义中的条件需删除，得：时，删去时，删去 当当 时，删去时，删去 置换复合实例置换复合实例 89例：设 信息工程与自动化学院信息工程与自动化学院 置换合成的性质置换合成的性质置换合成满足结合律置换合成满足结合律,不满足交换律。不满足交换律。90 置换合成的性质置换合成满足结合律,不满足交换律。90信息工程与自动化学院信息工程与自动化学院合一可以简单理解为：寻找相对变量的置换，合一可以简单理解为：寻找相对变量的置换，使两个谓词公式一致。使两个谓词公式一致。一般情况下一般情况下,一个公式集的合一一个公式集的合一不是惟

56、一不是惟一的。的。2.2.合一合一2 合一置换：合一置换：设有公式集设有公式集 ，若存在一个置换，若存在一个置换 可使可使则称则称 是是E 的合一置换。同时称的合一置换。同时称E1,E2,En是可是可合一的。合一的。91合一可以简单理解为：寻找相对变量的置换，使两个谓词公式一致。信息工程与自动化学院信息工程与自动化学院2 最一般合一：最一般合一：设设 是谓词公式集是谓词公式集E 的一个合一置换，如果的一个合一置换，如果对对E 的任意一个合一置换的任意一个合一置换 都存在一个置换都存在一个置换 ，使得使得 ，则称，则称 是一个最一般是一个最一般(或最简或最简单单)合一合一(most genera

57、l unifier，简记为简记为mgu)。谓词公式集的最一般合一置换谓词公式集的最一般合一置换并不是唯一的。并不是唯一的。92 最一般合一：设 是谓词公式集E 的一个合一信息工程与自动化学院信息工程与自动化学院例例：设：设 S有一个最一般合一有一个最一般合一 对于对于S的任一合一，例如：的任一合一，例如：存在一个替换存在一个替换 使得使得 【合一实例】【合一实例】93例：设【合一实例】93信息工程与自动化学院信息工程与自动化学院2 最一般合一置换的求取算法：最一般合一置换的求取算法：l差异集差异集 在在对对两两个个谓谓词词公公式式中中的的项项从从左左到到右右进进行行比比较较时时，那些不相同的项

58、所构成的集合，称为差异集。那些不相同的项所构成的集合，称为差异集。设设S=S=P(x,y,z),P(x,f(a),h(b)P(x,y,z),P(x,f(a),h(b)，则则不不难难看看出出，S S有有两两个差异集个差异集 D D1 1=y,f(a)y,f(a)D D2 2=z,h(b)z,h(b)94 最一般合一置换的求取算法：差异集94信息工程与自动化学院信息工程与自动化学院置置k=0,Sk=0,Sk k=S=S，k k=;=;若若S Sk k只只含含有有一一个个谓谓词词公公式式，则则算算法法停停止止，k k就就是要求的最一般合一是要求的最一般合一;求求S Sk k的差异集的差异集D Dk

59、k;若若D Dk k中存在元素中存在元素x xk k和和t tk k，其中，其中x xk k是变元，是变元，t tk k是项是项且且x xk k不在不在t tk k中出现，则置中出现，则置S Sk+1k+1=S=Sk kt tk k/x/xk k,k+1k+1=k kt tk k/x/xk k，k=k+1k=k+1，然后转，然后转;算法停止，算法停止，S S的最一般合一不存在。的最一般合一不存在。95置k=0,Sk=S，k=;95信息工程与自动化学院信息工程与自动化学院【实例【实例1】1.求求公公式式集集S=P(a,x,f(g(y),P(z,h(z,u),f(u)的的最最一一般合一。般合一。解

60、：解：k=0：S0=S,0=,S0不不是是单单元元素素集集，求求得得D0=a,z，其其中中z是变元，且不在是变元，且不在a中出现，所以有中出现，所以有 1=0a/z=a/z=a/z S1=S0a/z=P(a,x,f(g(y),P(a,h(a,u),f(u)k=1:S1不是单元素集，求得不是单元素集，求得D1=x,h(a,u)，2=1h(a,u)/x=a/zh(a,u)/x=a/z,h(a,u)/x S2=S1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)96【实例1】1.求公式集S=P(a,x,f(g(y),信息工程与自动化学院信息工程与自动化学院k=2:

61、S2不是单元素集，不是单元素集，D2=g(y),u，3=2g(y)/u=a/z,h(a,g(y)/x,g(y)/uS3=S2g(y)/u=P(a,h(a,g(y),f(g(y),P(a,h(a,g(y),f(g(y)=P(a,h(a,g(y),f(g(y)k=3:S3已是单元素集，所以已是单元素集，所以3就是就是S的最一般合一。的最一般合一。97k=2:97信息工程与自动化学院信息工程与自动化学院【实例【实例2】2.判定判定S=P(x,x),P(y,f(y)是否可合一？是否可合一？解：解：k=0:S0=S,0=,S0不是单元素集，不是单元素集，D0=x,y1=0y/x=y/xS1=S0y/x=

62、P(y,y),P(y,f(y)k=1:S1不不是是单单元元素素集集，D1=y,f(y)，由由于于变变元元y在在项项f(y)中出现，所以算法停止，中出现，所以算法停止，S不存在最一般合一。不存在最一般合一。98【实例2】2.判定S=P(x,x),P(y,f(y)信息工程与自动化学院信息工程与自动化学院 定定理理3 3（合合一一定定理理）如如果果S S是是一一个个非非空空有有限限可可合合一一的的公公式式集集，则则合合一一算算法法总总是是在在步步停停止，且最后的止，且最后的k k即是即是S S的最一般合一。的最一般合一。本本定定理理说说明明任任一一非非空空有有限限可可合合一一的的公公式式集集，一一定

63、定存存在在最最一一般般合合一一，而而且且用用合合一一算算法法总总能能找找到到最最一一般般合合一一，这这个个最最一一般般合合一一也也就就是是当当算算法法终止在步终止在步 时，最后的合一时，最后的合一k k。99 定理3（合一定理）如果S是一个非空有限信息工程与自动化学院信息工程与自动化学院&谓词逻辑中的归结原理谓词逻辑中的归结原理 定定义义1212 设设C C1 1,C,C2 2是是两两个个无无相相同同变变元元的的子子句句，L L1 1,L,L2 2分分别别是是C C1 1,C,C2 2中中的的两两个个文文字字，如如果果L L1 1和和乛乛L L2 2有有最最一一般合一般合一，则子句，则子句 (

64、C(C1 1-L L1 1)(C)(C2 2-L L2 2)称称作作C C1 1和和C C2 2的的二二元元归归结结式式(二二元元消消解解式式)，C C1 1和和C C2 2称称作归结式的作归结式的亲本子句亲本子句，L L1 1和和L L2 2称作称作消解文字消解文字。100 谓词逻辑中的归结原理 定义12 设C1,C2信息工程与自动化学院信息工程与自动化学院【例题】【例题】设设C1=P(x)Q(x),C2=乛乛P(a)R(y)，求求C1,C2的的归归结式。结式。解解：取取L1=P(x),L2=乛乛P(a),则则L1与与乛乛L2的的最最一一般般合合一一=a/x，于是：，于是：(C1-L1)(C

65、2-L2)=(P(a),Q(a)-P(a)(乛乛P(a),R(y)-乛乛P(a)=Q(a),R(y)=Q(a)R(y)所以，所以，Q(a)R(y)是是C1和和C2的二元归结式。的二元归结式。101【例题】设C1=P(x)Q(x),C2=乛P(a)信息工程与自动化学院信息工程与自动化学院【例题】【例题】设设C1=P(x,y)乛乛Q(a),C2=Q(x)R(y),求求C1,C2的的归归结式。结式。解：取解：取L1=乛乛Q(a),L2=Q(x),则则L1与乛与乛L2的最一般合的最一般合一一=a/x，于是：，于是：(C1-L1)(C2-L2)=(P(a,y),乛乛Q(a)-乛乛Q(a)(Q(a),R(

66、y)-Q(a)=P(a,y),R(y)=P(a,y)R(y)所以，所以，P(a,y)R(y)是是C1和和C2的二元归结式的二元归结式。102【例题】设C1=P(x,y)乛Q(a),C2=Q(信息工程与自动化学院信息工程与自动化学院【补充说明】补充说明】如如果果在在参参加加归归结结的的子子句句内内部部含含有有可可合合一一的的文文字字，则则在在进进行行归归结结之之前前，也也应应对对这这些些文文字字进进行行合合一一，从从而而使使子子句句达达到最简。例如，设有两个子句：到最简。例如，设有两个子句：C1=P(x)P(f(a)Q(x)C2=P(y)R(b)可可见见,在在C1中中有有可可合合一一的的文文字字P(x)与与P(f(a)，那那么么，取取替替换换=f(a)/x(这这个个替替换换也也就就是是P(x)和和P(f(a)的的最最一一般般合合一一)，则得，则得 C1=P(f(a)Q(f(a)现现在在再再用用C1与与C2进进行行归归结结，从从而而得得到到C1与与C2的的归归结结式为：式为：(f(a)R(b)103【补充说明】如果在参加归结的子句内信息工程与自动化学院信息工程与自动化学院定义定义1414子