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

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

2、.1 概述概述4.2 确定性推理确定性推理信息工程与自动化学院信息工程与自动化学院4人工智能学科人工智能学科知识获取知识获取知识表示知识表示知识推理知识推理确定性推理确定性推理不确定性推理不确定性推理信息工程与自动化学院信息工程与自动化学院5 4.1.1 4.1.1 推理的基本概念推理的基本概念 推理的定义推理的定义 推理就是推理就是按照某种策略从已有事实和知识推按照某种策略从已有事实和知识推出结论的过程出结论的过程。 一般来说，人工智能系统中的智能推理过程一般来说，人工智能系统中的智能推理过程是由一些程序来完成的，这些程序在人工智能系是由一些程序来完成的，这些程序在人工智能系统中称为统中称为

3、推理机推理机。 信息工程与自动化学院信息工程与自动化学院64.1.2 4.1.2 推理的分类推理的分类v 按推理的逻辑基础分类按推理的逻辑基础分类 1 1）演绎推理：）演绎推理： 从已知的一般性知识出发，推理出适合于某种从已知的一般性知识出发，推理出适合于某种个别情况的结论过程。个别情况的结论过程。 即从即从一般到个别一般到个别的推理。的推理。 常用形式：三段论法常用形式：三段论法( (大前提、小前提、结论大前提、小前提、结论) )信息工程与自动化学院信息工程与自动化学院7【演绎推理实例【演绎推理实例】音乐系的学生至少会演奏一种乐器；（大前提）音乐系的学生至少会演奏一种乐器；（大前提）李聪是音

4、乐系的一名学生；（小前提）李聪是音乐系的一名学生；（小前提）李聪至少会演奏一种乐器。（结论）李聪至少会演奏一种乐器。（结论）信息工程与自动化学院信息工程与自动化学院82 2）归纳推理：）归纳推理： 从大量特殊事例出发，归纳出一般性结论从大量特殊事例出发，归纳出一般性结论的推理过程。的推理过程。 即从即从个别到一般个别到一般的推理过程。的推理过程。归纳推理归纳推理完全完全归纳推理归纳推理不完全不完全归纳推理归纳推理枚举枚举归纳推理归纳推理类比类比归纳推理归纳推理特殊事例考察范围特殊事例考察范围推理使用方法推理使用方法信息工程与自动化学院信息工程与自动化学院9 3 3）默认推理：）默认推理： 在知

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

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

7、而要否定加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。它，使得推理退回到前面的某一步，重新开始。v 按推理过程的单调性分类按推理过程的单调性分类信息工程与自动化学院信息工程与自动化学院12 1) 1) 启发式推理启发式推理 推理过程中应用与问题有关的启发性知识，推理过程中应用与问题有关的启发性知识，即解决问题的的策略、技巧及经验，以加快推即解决问题的的策略、技巧及经验，以加快推理过程，提高搜索效率。理过程，提高搜索效率。 2) 2) 非启发式推理非启发式推理 在推理过程中，不运用启发性知识，只按在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理。

8、这种方法缺乏对照一般的控制逻辑进行推理。这种方法缺乏对求解问题的针对性，所以推理效率较低，容易求解问题的针对性，所以推理效率较低，容易出现出现“组合爆炸组合爆炸”问题。问题。v 按推理中所用知识是否具有启发性分类按推理中所用知识是否具有启发性分类信息工程与自动化学院信息工程与自动化学院134.1 概述概述4.2 确定性推理确定性推理信息工程与自动化学院信息工程与自动化学院14确定性推理确定性推理归结推理归结推理演绎推理演绎推理命题命题逻辑逻辑谓词谓词逻辑逻辑海伯伦定理海伯伦定理数理数理逻辑逻辑基础基础命题命题逻辑逻辑归结归结基本基本概念概念谓词逻辑谓词逻辑归结原理归结原理Skolem标准形，标

9、准形，子句集子句集合一和置换，合一和置换，控制策略控制策略信息工程与自动化学院信息工程与自动化学院15【推理的逻辑基础【推理的逻辑基础】 逻辑是推理科学的研究。逻辑研究主要逻辑是推理科学的研究。逻辑研究主要是研究推理的过程是否正确，推理过程中是研究推理的过程是否正确，推理过程中各个语句之间的关系，而不考虑某一个语各个语句之间的关系，而不考虑某一个语句是否正确。句是否正确。 命题逻辑命题逻辑和和谓词逻辑谓词逻辑属于经典逻辑，是属于经典逻辑，是最先应用于人工智能的两种逻辑。其中谓最先应用于人工智能的两种逻辑。其中谓词逻辑是在命题逻辑的基础上发展起来的，词逻辑是在命题逻辑的基础上发展起来的，是一种表

10、达能力很强的形式语言。是一种表达能力很强的形式语言。信息工程与自动化学院信息工程与自动化学院161.命题命题 能够分辨真假的语句称为能够分辨真假的语句称为命题命题。 一个语句如果不能再进一步分解成更简单的语句，一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为并且又是一个命题，则称此命题为原子命题原子命题。 原子命题是命题中最基本的单位，常用大写原子命题是命题中最基本的单位，常用大写字母字母P,Q,R等表示。等表示。4.2.1 4.2.1 命题逻辑基础命题逻辑基础信息工程与自动化学院信息工程与自动化学院17判断以下句子，哪些是命题哪些不是？判断以下句子，哪些是命题哪些不

11、是？ 1+1=10。 快点走吧！快点走吧！ 雪是黑色的。雪是黑色的。 西安是个古老的城市。西安是个古老的城市。 明天是否开大会？明天是否开大会？ 如果天气好，那么我去散步。如果天气好，那么我去散步。是是不是不是是是是是不是不是是是信息工程与自动化学院信息工程与自动化学院18 ：合取合取(与与), ：析取析取(或或),：等价：等价(当且仅当当且仅当)。：蕴含蕴含(IF THEN),：否定否定(非非)， P Q PQPQPQPTTTTTFFTTFTTTFTFFFFFFFTT 命题逻辑真值表命题逻辑真值表2. 连接词连接词信息工程与自动化学院信息工程与自动化学院19连接词的优先级别连接词的优先级别

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

13、奖，保送上大学。保送上大学。 设设P：他聪明。：他聪明。Q：他用功。转换为：他用功。转换为：P Q。 设设P：应届高中生。：应届高中生。Q：保送上大学。：保送上大学。A：得过：得过数学竞赛一等奖。数学竞赛一等奖。B：得过物理竞赛一等奖。表：得过物理竞赛一等奖。表示为：示为： P (AB)Q例：将陈述句转化为命题公式。例：将陈述句转化为命题公式。【命题公式实例【命题公式实例】信息工程与自动化学院信息工程与自动化学院221.1.基本概念基本概念4.2.2 4.2.2 一阶谓词逻辑基础一阶谓词逻辑基础个体：独立存在的物体（抽象或具体）个体：独立存在的物体（抽象或具体）个体：个体：独立存在的物体（抽象

14、或具体）独立存在的物体（抽象或具体）谓词：谓词：用于刻画个体性质、状态或个体间关系。用于刻画个体性质、状态或个体间关系。53 Greater (5,3)李白是诗人李白是诗人 Poet (LiBai)一元谓词一元谓词二元谓词二元谓词一阶谓词一阶谓词信息工程与自动化学院信息工程与自动化学院233. 谓词公式谓词公式2. 连接词：连接词：，单个谓词是谓词公式，称为原子谓词公式。单个谓词是谓词公式，称为原子谓词公式。若若A是谓词公式，则是谓词公式，则 A也是谓词公式。也是谓词公式。若若A，B都都是谓词公式，则是谓词公式，则(AB)，(AB)， (AB)，(AB)也是谓词公式也是谓词公式 。若若A是谓词

15、公式，则是谓词公式，则 也是谓词公也是谓词公式。式。只有有限次的应用上述只有有限次的应用上述4 4条规则构成的符号串条规则构成的符号串才是谓词公式。才是谓词公式。,)(Ax Ax)( 信息工程与自动化学院信息工程与自动化学院24 位于量词后面的单个谓词或者用括弧括起来位于量词后面的单个谓词或者用括弧括起来的的合式公式称为的的合式公式称为量词的辖域量词的辖域。 在辖域内与量词同名的变元称为在辖域内与量词同名的变元称为约束变元约束变元，不受约束的变元称为不受约束的变元称为自由变元自由变元。4.4.量词辖域与约束变元量词辖域与约束变元),()()()(zyxRyxPx全称量词全称量词全称量词的辖域全

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

17、足式: : 对于谓词公式对于谓词公式P P，如果不存在任何值使得，如果不存在任何值使得P P的真的真值为值为T T，则称公式，则称公式P P是不可满足的是不可满足的。5. 5. 谓词公式的永真性谓词公式的永真性信息工程与自动化学院信息工程与自动化学院26PQQPPQQP ; 交换律：交换律： PQPQTTTTFTFTTFFFPQPQTTTTFFFTFFFF6. 谓词公式的等价性谓词公式的等价性信息工程与自动化学院信息工程与自动化学院27)()();()(RQPRQPRQPRQP 结合律：结合律：PQRPQ(PQ) R(Q R)P(Q R)TTTTTTTTTFTTTTTFTTTTTTFFTTFT

18、FTTTTTTFTFTTTTFFTFTTTFFFFFFF步骤1234信息工程与自动化学院信息工程与自动化学院28)()();()(RQPRQPRQPRQP 结合律：结合律：PQRPQ(PQ) R(Q R)P(Q R)TTTTTTTTTFTFFFTFTFFFFTFFFFFFFTTFFTFFTFFFFFFFTFFFFFFFFFFF步骤1234信息工程与自动化学院信息工程与自动化学院29 分配律：分配律：)()()();()()(RPQPRQPRPQPRQP PQR(QR)P(QR)(PQ)( PR)(PQ) ( PR)TTTTTTTTTTFFTTTTTFTFTTTTTFFFTTTTFTTTTTTT

19、FTFFFTFFFFTFFFTFFFFFFFFF步骤12345信息工程与自动化学院信息工程与自动化学院30 分配律：分配律：)()()();()()(RPQPRQPRPQPRQP PQR(QR)P (QR)(PQ)( PR)(PQ) ( PR)TTTTTTTTTTFTTTFTTFTTTFTTTFFFFFFFFTTTFFFFFTFTFFFFFFTTFFFFFFFFFFFF步骤12345信息工程与自动化学院信息工程与自动化学院31QPQPQPQP )(;)( 狄狄 摩根律：摩根律：PQPQ(PQ)PQPQTTTFFFFTFTFFTFFTTFTFFFFFTTTT步骤12345信息工程与自动化学院信息

20、工程与自动化学院32QPQPQPQP )(;)( 狄狄 摩根律：摩根律：PQPQ(PQ)PQPQTTTFFFFTFFTFTTFTFTTFTFFFTTTT步骤12345信息工程与自动化学院信息工程与自动化学院33PQPPPQPP )(;)( 吸收律：吸收律：PQPQP(PQ)TTTFTFFTFTFFFFFF步骤12信息工程与自动化学院信息工程与自动化学院34PQPPPQPP )(;)( 吸收律：吸收律：PQPQ P (PQ)TTTTTFTTFTTFFFFF步骤12信息工程与自动化学院信息工程与自动化学院35PPPP 1;0 同一律：同一律：P0P0TFTTFTFFFFFF步骤1P1P1TTTTT

21、TFTFFTF步骤100; 11 PP 零律：零律：信息工程与自动化学院信息工程与自动化学院36PP )( 双重否定律：双重否定律：1 PP 排中律：排中律：0 PP 矛盾律：矛盾律：信息工程与自动化学院信息工程与自动化学院37QPQP 蕴涵等值式：蕴涵等值式：PQPQ P PQTTTFTTFFFFFTTTTFFTTT步骤123信息工程与自动化学院信息工程与自动化学院38PQPQQP (PQ) (PQ)TTTTTTTFFFTFFTFTFFFFTTTT)()(PQQPQP 等价等值式：等价等值式：QP 信息工程与自动化学院信息工程与自动化学院39PQQP 逆反律：逆反律：PQPQP Q QPTT

22、TFFTTFFFTFFTTTFTFFTTTT信息工程与自动化学院信息工程与自动化学院40PQPQP )()( 归谬论：归谬论：PQPQ QP Q(PQ) (P Q)PTTTFFFFTFFTTFFFTTFTTTFFTTTTT信息工程与自动化学院信息工程与自动化学院41合取式：合取式：P与与Q，记做，记做 PQ析取式：析取式：P或或Q，记做，记做 PQ蕴含式：蕴含式：如果如果P则则Q，记做，记做 PQ等价式：等价式：P当且仅当当且仅当Q，记做，记做 PQ7. 谓词公式型式：谓词公式型式：信息工程与自动化学院信息工程与自动化学院42简单合取式简单合取式： 仅由有限个命题变量或其否定构成的仅由有限个命

23、题变量或其否定构成的合取式。合取式。简单析取式简单析取式： 仅由有限个命题变量或其否定构成的仅由有限个命题变量或其否定构成的析取式。析取式。合取范式合取范式： 仅由有限个简单析取式组成的合取式。仅由有限个简单析取式组成的合取式。如：如：P (P Q) ( P Q)析取范式析取范式： 仅由有限个简单合取式组成的析取式。仅由有限个简单合取式组成的析取式。如：如：P (P Q) ( P Q)信息工程与自动化学院信息工程与自动化学院43例：求取例：求取P(QR)S的合取范式。的合取范式。解：解：QPQP QPQP QPQP )(QPQP )(PP )(PQQP )()()(RPQPRQP )()()(

24、)()()()()()(RSPQSPRQSPSRQPSRQPSRQPSRQPSRQPSRQP 信息工程与自动化学院信息工程与自动化学院44 把公式中量词辖域中的同名约束变元都统一改把公式中量词辖域中的同名约束变元都统一改成相同的名字，且不能与辖域内的自由变元同名，成相同的名字，且不能与辖域内的自由变元同名，公式的其余部分不变。公式的其余部分不变。 例：例： 更名为：更名为：),(),()(yxQzyxpy ),(),()(yxQzwxpw 5.5.换名规则换名规则信息工程与自动化学院信息工程与自动化学院45)()()()()()()()(xPxxPxxPxxPx 约束变元换名规则约束变元换名规

25、则:)()()()()()()()(yPyxPxyPyxPx )()()()()()()()()()()()()()(xQxxPxxQxPxxQxxPxxQxPx 量词转换律量词转换律: 量词分配律量词分配律:6.6.基本规则和等价式基本规则和等价式信息工程与自动化学院信息工程与自动化学院46 消去量词等价式消去量词等价式: 设个体域为有穷集合设个体域为有穷集合(a1,a2,an)()()()()()()()()()(2121nnaPaPaPxPxaPaPaPxPx )()()()()()()()()()()()()()()()(xPxQxPQxQxPxQxPxQxPxQxPxQxPxQxPx

26、 量词辖域收缩与扩张等价式量词辖域收缩与扩张等价式:信息工程与自动化学院信息工程与自动化学院47)()()()()()()()()()()()()()()()(xPxQxPQxQxPxQxPxQxPxQxPxQxPxQxPx 量词辖域收缩与扩张等价式量词辖域收缩与扩张等价式(续续):信息工程与自动化学院信息工程与自动化学院484.2.3 4.2.3 自然演绎推理方法自然演绎推理方法 从一组已知为真的事实出发，直接运用命题逻从一组已知为真的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程。辑或谓词逻辑中的推理规则推出结论的过程。 最基本的推理规则有：最基本的推理规则有： 假言三段论

27、假言三段论 T规则规则 假言推理假言推理 P规则规则 拒取式拒取式 信息工程与自动化学院信息工程与自动化学院49【演绎推理实例【演绎推理实例】l 如果一个人大学毕业，则他就具有独立生活的能如果一个人大学毕业，则他就具有独立生活的能力。力。l 如果一个人具有独立生活的能力，则他就可以离如果一个人具有独立生活的能力，则他就可以离开父母。开父母。l 如果一个人大学毕业，则他就可以离开父母。如果一个人大学毕业，则他就可以离开父母。RPRQQP,假言三段论假言三段论信息工程与自动化学院信息工程与自动化学院50【演绎推理实例【演绎推理实例】l 如果如果S是音乐系学生，则是音乐系学生，则S至少会演奏一样乐器

28、。至少会演奏一样乐器。l 张艺是音乐系学生。张艺是音乐系学生。l 张艺至少会演奏一样乐器。张艺至少会演奏一样乐器。为真为真QQPP,假言推理假言推理信息工程与自动化学院信息工程与自动化学院51【演绎推理实例【演绎推理实例】l 如果如果S是音乐系学生，则是音乐系学生，则S至少会演奏一样乐器。至少会演奏一样乐器。l 张艺不会演奏任何乐器。张艺不会演奏任何乐器。l 张艺不是音乐系学生。张艺不是音乐系学生。PQ，QP拒取式推理拒取式推理信息工程与自动化学院信息工程与自动化学院52【演绎推理常见错误【演绎推理常见错误】l 如果如果S是音乐系学生，则是音乐系学生，则S至少会演奏一样乐器。至少会演奏一样乐器

29、。l 张艺会演奏电子琴。张艺会演奏电子琴。l 张艺是音乐系学生。张艺是音乐系学生。PQ ，QP肯定后件错误肯定后件错误信息工程与自动化学院信息工程与自动化学院53【演绎推理常见错误【演绎推理常见错误】l 如果如果S是音乐系学生，则是音乐系学生，则S至少会演奏一样乐器。至少会演奏一样乐器。l 张艺不是音乐系学生。张艺不是音乐系学生。l 张艺不会演奏任何一样乐器。张艺不会演奏任何一样乐器。QPQP，否定前件错误否定前件错误信息工程与自动化学院信息工程与自动化学院54【实例【实例】设已知如下事实：设已知如下事实： R, S, RT, ST P, P Q求证：求证：Q为真。为真。证明：因为证明：因为

30、所以所以Q为真。为真。QQPPPPTSTSTSTSTTRR,P规则及假言推理规则及假言推理引入合取词引入合取词T规则及假言推理规则及假言推理T规则及假言推理规则及假言推理信息工程与自动化学院信息工程与自动化学院55 【演绎推理的特点【演绎推理的特点】l 只是将蕴涵在一般性知识前提中的事实揭示出来，只是将蕴涵在一般性知识前提中的事实揭示出来，不能增殖新的知识；不能增殖新的知识；l 由已知事实推出的结论可能有多个；由已知事实推出的结论可能有多个；l 优点在于符合人的思维习惯，易于理解；优点在于符合人的思维习惯，易于理解；l 缺点在于容易产生知识或规则爆炸，不利于对复缺点在于容易产生知识或规则爆炸，

31、不利于对复杂问题的求解。杂问题的求解。信息工程与自动化学院信息工程与自动化学院564.2.4 4.2.4 归结推理方法归结推理方法 归结法是与自然演绎法完全不同的新的逻辑演归结法是与自然演绎法完全不同的新的逻辑演算算法。算算法。 归结法的基本原理是采用归结法的基本原理是采用反证法反证法（也称为反演（也称为反演推理方法）：将待证明的表达式转换成为逻辑公式推理方法）：将待证明的表达式转换成为逻辑公式（谓词公式），然后再进行归结，归结能顺利完成，（谓词公式），然后再进行归结，归结能顺利完成，则证明原公式是正确的。则证明原公式是正确的。信息工程与自动化学院信息工程与自动化学院571. 1. 范式范式谓

32、词演算公式的标准型，即范式。一般有谓词演算公式的标准型，即范式。一般有2种范式：种范式：l 前束型范式前束型范式 一个谓词公式，如果它的所有量词均非否定地一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且它的辖域一直延伸到公式出现在公式的最前面，且它的辖域一直延伸到公式之末，同时公式中不出现连接词之末，同时公式中不出现连接词、，这种形，这种形式的谓词公式称为前束型范式。式的谓词公式称为前束型范式。信息工程与自动化学院信息工程与自动化学院58),(),()()()()(zyQzyFxPzyx公式的首标公式的首标命题演算公式命题演算公式优点：量词全部集中在公式的前面；优点：量词全部集中

33、在公式的前面；缺点：其首标杂乱无章，量词排列没有一定缺点：其首标杂乱无章，量词排列没有一定的规则。的规则。信息工程与自动化学院信息工程与自动化学院59QxPxQxPx )()()()(例：求下式的前束范式例：求下式的前束范式),()(),(yxxRyyQyxxP 解：解：),()(),(),()(),(),()(),(),()(),(),()(),(),()(),(),()(),(wtRyQzxPtyxwttRyQzxPyxwttRyQzxPyxwttRyyQzxPxwttRyyQzxxPwxxRyyQzxxPyxxRyyQyxxP)()()()(xPxQxPQx QxPxQxPx )()()

34、()()()()()(xPxQxPQx 信息工程与自动化学院信息工程与自动化学院60 从前束型范式中消去全部存在量词所得到的从前束型范式中消去全部存在量词所得到的公式，称为公式，称为SkolemSkolem范式，或范式，或Skolem标准型。标准型。 Skolem标准型的一般形式为：标准型的一般形式为：l Skolem范式范式),.,()()(2121nnxxxMxxx 信息工程与自动化学院信息工程与自动化学院61),(),()()()(zxfQzxfFxPzx公式的首标公式的首标（不出现存在量词）（不出现存在量词）命题演算公式命题演算公式),(),()()()()(zyQzyFxPzyxf(

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

36、该量词约束的变量用任意）。将该量词约束的变量用任意常量常量( (a, b等等) )或任意变量的函数或任意变量的函数( (f(x), g(y)等等)代替。代替。 如果存在量词左边没有任何任意量词，则只将其如果存在量词左边没有任何任意量词，则只将其改写为个体常量；改写为个体常量； 如果存在量词的如果存在量词的左边有任意量词左边有任意量词，消去时该变量，消去时该变量改写为任意量词的函数。改写为任意量词的函数。),.,()()(2121yxxxPyxxxnn ),.,(,.,()()(212121nnnxxxfxxxPxxx 信息工程与自动化学院信息工程与自动化学院645.5.把全称量词全部移到公式的

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

38、部，得：深入到量词内部，得：)(),()(),()()(),()()(),()()(),()(),()(xRbyQyxyxaPyxxRbyQyxyxaPyxxRbyQyxyxaPyx QPQP )()()()(xPxxPx 【SkolemSkolem范式的获取实例范式的获取实例】信息工程与自动化学院信息工程与自动化学院66 任意量词左移，利用分配律，得：任意量词左移，利用分配律，得： 变量易名，存在量词左移，直至所有的量词移到变量易名，存在量词左移，直至所有的量词移到 前面，得：前面，得：)(),(),()()()()(),()(),()()(),()(),()(xRbzQyxaPzyxxRb

39、zQzyxaPyxxRbyQyyxaPyx)(),()(),()(xRbyQyyxaPyx )(),()(),()(xRbyQyxyxaPyx )()()()()()()(xQxxPxxQxPx QxPxQxPx )()()()(信息工程与自动化学院信息工程与自动化学院67 消去存在量词，略去任意量词，消去存在量词，略去任意量词， 得得Skolem标准形标准形 ：)(),()(,()(),()(,()()(),()(,()()(xRbxgQxfxaPxRbxgQxfxaPxxRbzQxfxaPzx)(),(),()()()(xRbzQyxaPzyx 信息工程与自动化学院信息工程与自动化学院68

40、例：例：将下式化为将下式化为Skolem标准形。标准形。)()()()(),()()()()(xBxPxxQyxSyxQxPx 解：解：信息工程与自动化学院信息工程与自动化学院69)()()(,()()()()()(,()()()()()()(,()()()()()()()()(,()()()()()()()()(,()()()()()()()(),()()()()()()()(),()()()()()()()()(),()()()()()()()()(),()()()()()()()()(),()()()()(wBwPxfxSxPxQwBwPxfxSxPxQwxwBwPxfxSxQxPxQw

41、xwBwPxQxfxSxQxPwxwBwPwxQxfxSxQxPxwBwPwxQyxSxQxPyxwBwPwxQyxSyxQxPxxBxPxxQyxSyxQxPxxBxPxxQyxSyxQxPxxBxPxxQyxSyxQxPx )()()(RQPRPQP ：QxPxQxPx )()()()(：)()()()()()()(xQxxPxxQxPx ：信息工程与自动化学院信息工程与自动化学院702.2.子句与子句集子句与子句集 原子公式原子公式：不含任何连接词的谓词公式。不含任何连接词的谓词公式。 文文 字：字：原子或原子的否定。原子或原子的否定。 子子 句：句：由一些文字组成的析取式。由一些文字组

42、成的析取式。 空空 子子 句：句：不包含任何文字的子句，表示为不包含任何文字的子句，表示为NILNIL。空子句是永假的。空子句是永假的。 子子 句句 集：集：由子句构成的集合。由子句构成的集合。子句原子公式)(,(),(),()(P),(),(),(xfyxRcxPyxQxyxRcxPxP信息工程与自动化学院信息工程与自动化学院71 【子句集【子句集S S的求取的求取】 由于由于Skolem 标准型的母式已为合取式，从而母标准型的母式已为合取式，从而母式的每一个合取项都是一个子句。式的每一个合取项都是一个子句。子句集的求取方法为：子句集的求取方法为： 将谓词公式将谓词公式G化为化为 Skole

43、m 标准型；标准型； 消去消去Skolem 标准型前面的全称量词；标准型前面的全称量词； 用用“，”取代取代“”，并表示为成集合形式。，并表示为成集合形式。信息工程与自动化学院信息工程与自动化学院72【实例【实例】),(),()(),()(yxRyxQyyxPyxG)(,()(,()(,()(,()(xgxRxfxPxgxQxfxPxGs)(,()(,(),(,()(,(xgxRxfxPxgxQxfxPS信息工程与自动化学院信息工程与自动化学院73定理定理1 1： G G是不可满足的是不可满足的 S S是不可满足的是不可满足的【子句集【子句集S S与谓词公式与谓词公式G G的关系的关系】 证明

44、一个公式的不可满足性，转化为证明一个公式的不可满足性，转化为证明其子句集证明其子句集S S的不可满足性。的不可满足性。信息工程与自动化学院信息工程与自动化学院743. Robinson3. Robinson归结原理（消解原理）归结原理（消解原理） 检查子句集检查子句集S S中是否有空子句，若有，则中是否有空子句，若有，则表明表明S S是不可满足的；若没有，就在子句集是不可满足的；若没有，就在子句集中选择合适的子句对其进行归结推理，如中选择合适的子句对其进行归结推理，如果能推出空子句，就说明子句集是果能推出空子句，就说明子句集是S S是不可是不可满足的。满足的。什么是归结？什么是归结？如何进行归

45、结推理？如何进行归结推理？信息工程与自动化学院信息工程与自动化学院75（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，且，且L L1 1与与L L2 2互补，从互补，从C C1 1,C,C2 2中分别删除中分别删除L L1 1,L,L2 2，再将剩余部分进行析取，构成一个新子句，再将剩余部分进行析取，构成一个新子句为为C C1212，这一过程称为，

46、这一过程称为归结归结，所得到的子句，所得到的子句C C1212称为称为C C1 1,C,C2 2的的归结式归结式( (或消解式或消解式) )，C C1 1,C,C2 2称为其归结式称为其归结式C C1212的的亲本子句亲本子句， L L1 1,L,L2 2称为称为消解基消解基。P信息工程与自动化学院信息工程与自动化学院76 设：设： C1=乛乛PQR C2=乛乛QS 求：求： C1,C2的归结式。的归结式。 解：解： 由于由于Q和乛和乛Q是互补文字，则消去互补文是互补文字，则消去互补文字后得：字后得： C12=乛乛PRS信息工程与自动化学院信息工程与自动化学院77 定理定理2 2：归结式：归结

47、式C C1212是其亲本子句是其亲本子句C C1 1、C C2 2的逻的逻辑结论。辑结论。 推推 论：论：设设C C1 1, ,C C2 2是子句集是子句集S S的两个子句，的两个子句，C C1212是它们是它们的归结式，则若用的归结式，则若用C C1212加入到子句集加入到子句集S S后得到新子句后得到新子句集集S S1 1，则由，则由S S1 1和和S S在在不可满足的意义下是等价的。不可满足的意义下是等价的。即即S S不可满足不可满足 S S1 1不可满足不可满足信息工程与自动化学院信息工程与自动化学院78【归结推理过程【归结推理过程】对子句集对子句集S S中的各个子句间使用归结推理规则

48、；中的各个子句间使用归结推理规则；将归结所得的归结式放入子句集将归结所得的归结式放入子句集S S中，得到新子中，得到新子句集句集SS；检查子句集检查子句集SS中是否有空子句（中是否有空子句（NILNIL），若有，），若有，则停止推理；否则，转步骤则停止推理；否则，转步骤；置置S=SS=S，转步骤，转步骤。 按照上述推理，在推理过程中，当子句集按照上述推理，在推理过程中，当子句集S S中出现空子句，即证明中出现空子句，即证明S S是不可满足的。是不可满足的。信息工程与自动化学院信息工程与自动化学院79【例题【例题】 证明子句集证明子句集PP乛乛Q,Q,乛乛P,QP,Q是不可满足的。是不可满足的。

49、证：证：(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)NIL .由由(3),(4)(3),(4)归结归结由于由于S S中出现空子句，所以中出现空子句，所以S S是不可满足的。是不可满足的。信息工程与自动化学院信息工程与自动化学院80【例题【例题】 用归结原理证明用归结原理证明R R是是P,(PQ)R,(SU)Q,UP,(PQ)R,(SU)Q,U的逻辑结果。的逻辑结果。【提示【提示】 要证明要证明PQPQ是永真的，考虑反证法，先否是永真的，考虑反证法，先否

50、定逻辑结论定逻辑结论Q Q，再由否定后的逻辑结论，再由否定后的逻辑结论Q Q及前及前提条件提条件P P出发推出矛盾，即证明原问题。出发推出矛盾，即证明原问题。 为证明为证明PQPQ，实际实际上只需证明，实际实际上只需证明P P Q Q的不可满足性。的不可满足性。信息工程与自动化学院信息工程与自动化学院81证：证： 由已知前提条件和否定逻辑结论可得到子句集由已知前提条件和否定逻辑结论可得到子句集S S： S=S=P,P,乛乛PP乛乛QR,QR,乛乛SQ,SQ,乛乛UQ,U,UQ,U,乛乛R R 然后对该子句集施行归结，归结过程用下面的然后对该子句集施行归结，归结过程用下面的归结演绎树表示。归结演