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

第4章确定性推理1第4章确定性推理1本章学习要点掌握谓词公式的概念及可满足性的定义、置换与合一的概念，掌握求取最一般合一置换的方法。掌握归结原理及归结推理方法。（重点在谓词逻辑中）掌握利用归结原理进行定理证明的方法。掌握利用归结原理进行问题求解的方法。了解归结过程中的控制策略。2本章学习要点掌握谓词公式的概念及可满足性的定义、置换与合一的4.1概述4.2确定性推理主要内容34.1概述4.2确定性推理主要内容3人工智能学科知识获取知识表示知识推理确定性推理不确定性推理4人工智能学科知识获取知识表示知识推理确定性推理不确定性推理44.1.1推理的基本概念

推理的定义推理就是按照某种策略从已有事实和知识推出结论的过程。一般来说，人工智能系统中的智能推理过程是由一些程序来完成的，这些程序在人工智能系统中称为推理机。

4.1推理概述54.1.1推理的基本概念4.1推理概述54.1.2推理的分类按推理的逻辑基础分类

1）演绎推理：从已知的一般性知识出发，推理出适合于某种个别情况的结论过程。即从一般到个别的推理。常用形式：三段论法(大前提、小前提、结论)64.1.2推理的分类按推理的逻辑基础分类6【演绎推理实例】音乐系的学生至少会演奏一种乐器；（大前提）李聪是音乐系的一名学生；（小前提）李聪至少会演奏一种乐器。（结论）7【演绎推理实例】音乐系的学生至少会演奏一种乐器；（大前提）72）归纳推理：从大量特殊事例出发，归纳出一般性结论的推理过程。即从个别到一般的推理过程。归纳推理完全归纳推理不完全归纳推理枚举归纳推理类比归纳推理特殊事例考察范围推理使用方法82）归纳推理：从大量特殊事例出发，归纳出一般性结

3）默认推理：在知识不完全的情况下，假设某些条件已经具备所进行的推理。默认推理过程中可能会出现一些无效推理，但默认推理解决了在一个不完备知识集中进行推理的问题。93）默认推理：在知识不完全的情况下，假设某些条

1)确定性推理推理时所有用的知识和证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假，没有第三种情况出现。2)不确定性推理推理时所用的知识和证据不都是确定的，推出的结论也不确定的。按所用知识的确定性分类101)确定性推理按所用知识的确定性分类101)单调推理

在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标。

2)非单调推理

在推理过程中随着推理的向前推进及新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。按推理过程的单调性分类111)单调推理按推理过程的单调性分类111)启发式推理

推理过程中应用与问题有关的启发性知识，即解决问题的的策略、技巧及经验，以加快推理过程，提高搜索效率。2)非启发式推理在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理。这种方法缺乏对求解问题的针对性，所以推理效率较低，容易出现“组合爆炸”问题。按推理中所用知识是否具有启发性分类121)启发式推理按推理中所用知识是否具有启发性分4.1概述4.2确定性推理主要内容134.1概述4.2确定性推理主要内容13确定性推理归结推理演绎推理命题逻辑谓词逻辑海伯伦定理数理逻辑基础命题逻辑归结基本概念谓词逻辑归结原理Skolem标准形，子句集合一和置换，控制策略4.2确定性推理14确定性推理归结推理演绎推理命题逻辑谓词逻辑海伯伦定理数理逻辑【推理的逻辑基础】 逻辑是推理科学的研究。逻辑研究主要是研究推理的过程是否正确，推理过程中各个语句之间的关系，而不考虑某一个语句是否正确。

命题逻辑和谓词逻辑属于经典逻辑，是最先应用于人工智能的两种逻辑。其中谓词逻辑是在命题逻辑的基础上发展起来的，是一种表达能力很强的形式语言。15【推理的逻辑基础】 逻辑是推理科学的研究。逻辑命题

能够分辨真假的语句称为命题。一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为原子命题。原子命题是命题中最基本的单位，常用大写字母P,Q,R等表示。4.2.1命题逻辑基础16命题4.2.1命题逻辑基础16判断以下句子，哪些是命题哪些不是？

①1+1=10。②快点走吧！③雪是黑色的。④西安是个古老的城市。⑤明天是否开大会？⑥如果天气好，那么我去散步。是不是是是不是是17判断以下句子，哪些是命题哪些不是？是17∧

：合取(与),∨

：析取(或),：等价(当且仅当)。：蕴含(IF…THEN),：否定(非)，P

Q

P∨QP∧QP→Q~PTTTTTFFTTFTTTFTFFFFFFFTT命题逻辑真值表2.连接词18∧：合取(与),∨：析取(或),：等价(当且仅当)。：蕴连接词的优先级别∧∨19连接词的优先级别∧∨19原子命题是命题公式。A是命题公式，则﹁A也是命题公式。若A和B都是命题公式，则A∧B、A∨B、AB、AB也都是命题公式。按照上述规则由原子命题、连接词及圆括号所组成的字符串称为命题公式。3.命题公式20原子命题是命题公式。3.命题公式20①他既聪明又用功。②应届高中生，得过数学或物理竞赛的一等奖，保送上大学。①设P：他聪明。Q：他用功。转换为：P∧

Q。②设P：应届高中生。Q：保送上大学。A：得过数学竞赛一等奖。B：得过物理竞赛一等奖。表示为：P∧(A∨B)→Q例：将陈述句转化为命题公式。【命题公式实例】21①他既聪明又用功。①设P：他聪明。Q：他用功。转换为：P1.基本概念4.2.2一阶谓词逻辑基础个体：独立存在的物体（抽象或具体）个体：独立存在的物体（抽象或具体）谓词：用于刻画个体性质、状态或个体间关系。5>3Greater(5,3)李白是诗人Poet(LiBai)一元谓词二元谓词一阶谓词221.基本概念4.2.2一阶谓词逻辑基础个体：独立存在的物体3.谓词公式2.连接词：¬，∧，∨，→，单个谓词是谓词公式，称为原子谓词公式。若A是谓词公式，则¬A也是谓词公式。若A，B都是谓词公式，则(A∧B)，(A∨B)，(A→B)，(AB)也是谓词公式

。若A是谓词公式，则也是谓词公式。只有有限次的应用上述4条规则构成的符号串才是谓词公式。233.谓词公式2.连接词：¬，∧，∨，→，单个谓词是谓词位于量词后面的单个谓词或者用括弧括起来的的合式公式称为量词的辖域。在辖域内与量词同名的变元称为约束变元，不受约束的变元称为自由变元。4.量词辖域与约束变元全称量词全称量词的辖域存在量词存在量词的辖域约束变元自由变元24位于量词后面的单个谓词或者用括弧括起来的的合式公式称永真式:如果谓词公式P在每个非空个体域上均取得真值T，则称P永真。永假式:如果谓词公式P在每个非空个体域上均取得真值F，则称P永假。可满足式:对于谓词公式P，如果至少存在一个值使得P的真值为T，则称公式P是可满足的。不可满足式:对于谓词公式P，如果不存在任何值使得P的真值为T，则称公式P是不可满足的。5.谓词公式的永真性25永真式:如果谓词公式P在每个非空个体域上均取得真值T，则称交换律：

PQP∨QTTTTFTFTTFFFPQP∧QTTTTFFFTFFFF6.谓词公式的等价性26交换律：PQP∨Q

结合律：PQRP∨Q(P∨Q)∨R(Q∨R)P∨(Q∨R)TTTTTTTTTFTTTTTFTTTTTTFFTTFTFTTTTTTFTFTTTTFFTFTTTFFFFFFF步骤123427结合律：PQRP∨Q(P∨Q)∨R(Q∨R)P∨(

结合律：PQRP∧Q(P∧Q)∧R(Q∧R)P∧(Q∧R)TTTTTTTTTFTFFFTFTFFFFTFFFFFFFTTFFTFFTFFFFFFFTFFFFFFFFFFF步骤123428结合律：PQRP∧Q(P∧Q)∧R(Q∧R)P∧(分配律：PQR(Q∧R)P∨(Q∧R)(P∨Q)(P∨R)(P∨Q)∧(P∨R)TTTTTTTTTTFFTTTTTFTFTTTTTFFFTTTTFTTTTTTTFTFFFTFFFFTFFFTFFFFFFFFF步骤1234529分配律：PQR(Q∧R)P∨(Q∧R)(P∨Q)(P分配律：PQR(Q∨R)P∧(Q∨R)(P∧Q)(P∧R)(P∧Q)∨(P∧R)TTTTTTTTTTFTTTFTTFTTTFTTTFFFFFFFFTTTFFFFFTFTFFFFFFTTFFFFFFFFFFFF步骤1234530分配律：PQR(Q∨R)P∧(Q∨R)(P∧Q)(狄·

摩根律：PQP∨Q¬(P∨Q)¬P¬Q¬P∧¬QTTTFFFFTFTFFTFFTTFTFFFFFTTTT步骤1234531狄·摩根律：PQP∨Q¬(P∨Q)¬P¬Q¬P∧¬Q狄·

摩根律：PQP∧Q¬(P∧Q)¬P¬Q¬P∨¬QTTTFFFFTFFTFTTFTFTTFTFFFTTTT步骤1234532狄·摩根律：PQP∧Q¬(P∧Q)¬P¬Q¬P∨¬Q吸收律：PQP∧QP∨(P∧Q)TTTFTFFTFTFFFFFF步骤1233吸收律：PQP∧QP∨(P∧Q)TTTFTFFTFTF吸收律：PQP∨QP∧(P∨Q)TTTTTFTTFTTFFFFF步骤1234吸收律：PQP∨QP∧(P∨Q)TTT同一律：P0P∨0TFTTFTFFFFFF步骤1P1P∧1TTTTTTFTFFTF步骤1零律：35同一律：P0P∨0TFTTFTFFFFFF步骤1P1P双重否定律：排中律：矛盾律：36双重否定律：排中律：矛盾律：36蕴涵等值式：PQP→Q¬P¬P∨QTTTFTTFFFFFTTTTFFTTT步骤12337蕴涵等值式：PQP→Q¬P¬P∨QTTTFTTFFFFPQP→QQ→P(P→Q)∧(P→Q)TTTTTTTFFFTFFTFTFFFFTTTT等价等值式：38PQP→QQ→P(P→Q)∧(P→Q)TTTTTTTFF逆反律：PQP→Q¬P¬Q¬Q→¬PTTTFFTTFFFTFFTTTFTFFTTTT39逆反律：PQP→Q¬P¬Q¬Q→¬PTTTFFTT归谬论：PQP→Q¬QP→¬Q(P→Q)∧(P→¬Q)¬PTTTFFFFTFFTTFFFTTFTTTFFTTTTT40归谬论：PQP→Q¬QP→¬Q(P→Q)∧(P→合取式：P与Q，记做P∧Q析取式：P或Q，记做P∨Q蕴含式：如果P则Q，记做P→Q等价式：P当且仅当Q，记做PQ7.谓词公式型式：41合取式：P与Q，记做P∧Q7.谓词公式型式：41简单合取式：仅由有限个命题变量或其否定构成的合取式。简单析取式：仅由有限个命题变量或其否定构成的析取式。合取范式：仅由有限个简单析取式组成的合取式。如：P∧(P∨Q)∧(¬

P∨

Q)析取范式：仅由有限个简单合取式组成的析取式。如：P∨(P∧

Q)∨(¬

P∧

Q)42简单合取式：仅由有限个命题变量或其否定构成的合取式。42例：求取P∧(Q→R)→S的合取范式。解：43例：求取P∧(Q→R)→S的合取范式。解：43把公式中量词辖域中的同名约束变元都统一改成相同的名字，且不能与辖域内的自由变元同名，公式的其余部分不变。

例：

更名为：5.换名规则44把公式中量词辖域中的同名约束变元都统一改成相同的名字约束变元换名规则:量词转换律:量词分配律:6.基本规则和等价式45约束变元换名规则:量词转换律:量词分配律:消去量词等价式:设个体域为有穷集合(a1,a2,…,an)量词辖域收缩与扩张等价式:46消去量词等价式:设个体域为有穷集合(a1,a2,…,量词辖域收缩与扩张等价式(续):47量词辖域收缩与扩张等价式(续):474.2.3自然演绎推理方法从一组已知为真的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程。最基本的推理规则有：

◆假言三段论◆T规则

◆假言推理◆P规则

◆拒取式

484.2.3自然演绎推理方法从一组已【演绎推理实例】如果一个人大学毕业，则他就具有独立生活的能力。如果一个人具有独立生活的能力，则他就可以离开父母。如果一个人大学毕业，则他就可以离开父母。假言三段论49【演绎推理实例】如果一个人大学毕业，则他就具有独立生活的能力【演绎推理实例】如果S是音乐系学生，则S至少会演奏一样乐器。张艺是音乐系学生。张艺至少会演奏一样乐器。假言推理50【演绎推理实例】如果S是音乐系学生，则S至少会演奏一样乐器。【演绎推理实例】如果S是音乐系学生，则S至少会演奏一样乐器。张艺不会演奏任何乐器。张艺不是音乐系学生。拒取式推理51【演绎推理实例】如果S是音乐系学生，则S至少会演奏一样乐器。【演绎推理常见错误】如果S是音乐系学生，则S至少会演奏一样乐器。张艺会演奏电子琴。张艺是音乐系学生。肯定后件错误52【演绎推理常见错误】如果S是音乐系学生，则S至少会演奏一样乐【演绎推理常见错误】如果S是音乐系学生，则S至少会演奏一样乐器。张艺不是音乐系学生。张艺不会演奏任何一样乐器。否定前件错误53【演绎推理常见错误】如果S是音乐系学生，则S至少会演奏一样乐【实例】设已知如下事实：R,S,R→T,S∧T→P,P→Q求证：Q为真。证明：因为

所以Q为真。P规则及假言推理引入合取词T规则及假言推理T规则及假言推理54【实例】设已知如下事实：证明：因为P规则及假言推理54【演绎推理的特点】只是将蕴涵在一般性知识前提中的事实揭示出来，不能增殖新的知识；由已知事实推出的结论可能有多个；优点在于符合人的思维习惯，易于理解；缺点在于容易产生知识或规则爆炸，不利于对复杂问题的求解。55【演绎推理的特点】只是将蕴涵在一般性知识前提中的事实揭示出4.2.4归结推理方法归结法是与自然演绎法完全不同的新的逻辑演算算法。归结法的基本原理是采用反证法（也称为反演推理方法）：将待证明的表达式转换成为逻辑公式（谓词公式），然后再进行归结，归结能顺利完成，则证明原公式是正确的。564.2.4归结推理方法归结法是与自1.范式谓词演算公式的标准型，即范式。一般有2种范式：前束型范式

一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且它的辖域一直延伸到公式之末，同时公式中不出现连接词、，这种形式的谓词公式称为前束型范式。571.范式谓词演算公式的标准型，即范式。一般有2种范式：57公式的首标命题演算公式优点：量词全部集中在公式的前面；缺点：其首标杂乱无章，量词排列没有一定的规则。58公式的首标命题演算公式优点：量词全部集中在公式的前面；58例：求下式的前束范式解：59例：求下式的前束范式解：59从前束型范式中消去全部存在量词所得到的公式，称为Skolem范式，或Skolem标准型。Skolem标准型的一般形式为：Skolem范式60从前束型范式中消去全部存在量词所得到的公式，称为Sk公式的首标（不出现存在量词）命题演算公式f(x)代替y61公式的首标命题演算公式f(x)代替y61【Skolem范式的获取步骤】消去谓词公式G中的蕴涵（）和双条件（）符号；减少否定符号（）的辖域，使否定符号最多只作用到一个谓词上；重新命名变元，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。62【Skolem范式的获取步骤】消去谓词公式G中的蕴涵（）和消去存在量词（）。将该量词约束的变量用任意常量(a,b等)或任意变量的函数(f(x),g(y)等)代替。如果存在量词左边没有任何任意量词，则只将其改写为个体常量；如果存在量词的左边有任意量词，消去时该变量改写为任意量词的函数。63消去存在量词（）。将该量词约束的变量用任意常量(a,b等把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分；母式化为合取范式。至此所得的公式就是谓词公式G的skolem标准型。64把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词例：将下式化为Skolem标准形。解：①消去→符号，得：②¬深入到量词内部，得：【Skolem范式的获取实例】65例：将下式化为Skolem标准形。解：①消去→符号③任意量词左移，利用分配律，得：④变量易名，存在量词左移，直至所有的量词移到前面，得：66③任意量词左移，利用分配律，得：④变量易名，存在量词左移⑤消去存在量词，略去任意量词，得Skolem标准形

：67⑤消去存在量词，略去任意量词，67例：将下式化为Skolem标准形。解：68例：将下式化为Skolem标准形。解：68①②③69①②③692.子句与子句集

原子公式：不含任何连接词的谓词公式。

文字：原子或原子的否定。

子句：由一些文字组成的析取式。

空子句：不包含任何文字的子句，表示为NIL。空子句是永假的。

子句集：由子句构成的集合。702.子句与子句集原子公式：不含任何连接词的谓词公式。70

【子句集S的求取】由于Skolem标准型的母式已为合取式，从而母式的每一个合取项都是一个子句。子句集的求取方法为：①将谓词公式G化为Skolem标准型；②消去Skolem标准型前面的全称量词；③用“，”取代“∧”，并表示为成集合形式。71【子句集S的求取】由于Skolem标准型【实例】72【实例】72定理1：G是不可满足的S是不可满足的【子句集S与谓词公式G的关系】证明一个公式的不可满足性，转化为证明其子句集S的不可满足性。73定理1：G是不可满足的S是不可满足的【子句集S与谓3.Robinson归结原理（消解原理）

检查子句集S中是否有空子句，若有，则表明S是不可满足的；若没有，就在子句集中选择合适的子句对其进行归结推理，如果能推出空子句，就说明子句集是S是不可满足的。什么是归结？如何进行归结推理？743.Robinson归结原理（消解原理）检查子句（1）命题逻辑中的归结原理若P是原子公式，则称P与为互补文字。设C1,C2是命题逻辑中的两个子句，C1中有文字L1，C2中有文字L2，且L1与L2互补，从C1,C2中分别删除L1,L2，再将剩余部分进行析取，构成一个新子句为C12，这一过程称为归结，所得到的子句C12称为C1,C2的归结式(或消解式)，C1,C2称为其归结式C12的亲本子句，L1,L2称为消解基。75（1）命题逻辑中的归结原理若P是原子公式，则称P与为

设：C1=乛P∨Q∨RC2=乛Q∨S求：C1,C2的归结式。解：由于Q和乛Q是互补文字，则消去互补文字后得：C12=乛P∨R∨S76设：C1=乛P∨Q∨R76

定理2：归结式C12是其亲本子句C1、C2的逻辑结论。

推论：设C1,C2是子句集S的两个子句，C12是它们的归结式，则若用C12加入到子句集S后得到新子句集S1，则由S1和S在不可满足的意义下是等价的。即S不可满足S1不可满足77定理2：归结式C12是其亲本子句C1、C2的逻辑结论。7【归结推理过程】对子句集S中的各个子句间使用归结推理规则；将归结所得的归结式放入子句集S中，得到新子句集S’；检查子句集S’中是否有空子句（NIL），若有，则停止推理；否则，转步骤④；置S=S’，转步骤①。按照上述推理，在推理过程中，当子句集S中出现空子句，即证明S是不可满足的。78【归结推理过程】对子句集S中的各个子句间使用归结推理规则；7【例题】证明子句集{P∨乛Q,乛P,Q}是不可满足的。证：(1)P∨乛Q………..已知(2)乛P………..已知(3)Q………..已知(4)乛Q………..由(1),(2)归结(5)NIL………..由(3),(4)归结由于S中出现空子句，所以S是不可满足的。79【例题】证明子句集{P∨乛Q,乛P,Q}是不可满足的【例题】用归结原理证明R是P,(P∧Q)→R,(S∨U)→Q,U的逻辑结果。【提示】要证明P→Q是永真的，考虑反证法，先否定逻辑结论Q，再由否定后的逻辑结论﹁Q及前提条件P出发推出矛盾，即证明原问题。

为证明P→Q，实际实际上只需证明P∧﹁Q的不可满足性。80【例题】用归结原理证明R是P,(P∧Q)→R,(S∨U)证：

①由已知前提条件和否定逻辑结论可得到子句集S：S=｛P,乛P∨乛Q∨R,乛S∨Q,乛U∨Q,U,乛R｝

②然后对该子句集施行归结，归结过程用下面的归结演绎树表示。

③由于最后推出了空子句，所以子句集S不可满足。

④即命题公式P∧(乛P∨乛∨R)∧(乛S∨Q)∧(乛U∨Q)∧U∧乛R不可满足，从而R是题设前提的逻辑结果。81证：818282（2）一阶谓词逻辑中的归结原理

在一阶谓词逻辑中，因为谓词逻辑中的子句含有个体变元，所以不能直接消去互补文字进行子句归结，而是要首先使用置换和合一的思想，对子句中的某些变元进行合一置换，对置换后的新子句再次使用归结。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)所以，要在谓词逻辑中应用消解原理，则一般需要对个体变元作适当的替换。84例如：假设有如下两个子句：84置换与合一在基于知识进行推理时，模式匹配时必须要进行的一项工作。为了使已知事实与知识库中的知识完全匹配，需要进行某种变元置换，所以先介绍置换与合一的有关概念及方法。85置换与合一在基于知识进行推理时，模式

置换可以简单理解为：在一个谓词公式中用置换项去置换变量。定义：形如的有限集合。其中，是互不相同的变量，即置换变量；是不同于

xi的项（常量、变量、函数），即置换项；置换86置换可以简单理解为：在一个谓词公式中用置换项去置换变量。

ti/xi表示用ti置换xi,并要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。例如：是一个置换；那么置换结果为：87ti/xi表示用ti置换xi,并要求ti设

是两个置换，则将集合中符合下列条件的元素删除：(1)tiλ/xi当tiλ=xi(2)ui/yi当yi∈{x1,x2,…,xn}如此得到的集合仍然是一个替换，该替换称为θ与λ的复合(或乘积)，记作θ·λ。

置换的复合88设置换的复合88例：设求θ与λ的合成。解：先求出集合满足定义中的条件需删除，得：①时，删去②当时，删去[置换复合实例]89例：设置换合成的性质置换合成满足结合律,不满足交换律。90置换合成的性质置换合成满足结合律,不满足交换律。90合一可以简单理解为：寻找相对变量的置换，使两个谓词公式一致。一般情况下,一个公式集的合一不是惟一的。2.合一合一置换：设有公式集，若存在一个置换可使则称

是E的合一置换。同时称E1,E2,…,En是可合一的。91合一可以简单理解为：寻找相对变量的置换，使两个谓词公式一致。最一般合一：设是谓词公式集E的一个合一置换，如果对E的任意一个合一置换都存在一个置换，使得，则称是一个最一般(或最简单)合一(mostgeneralunifier，简记为mgu)。谓词公式集的最一般合一置换并不是唯一的。92最一般合一：设是谓词公式集E的一个合一例：设S有一个最一般合一对于S的任一合一，例如：存在一个替换使得

【合一实例】93例：设【合一实例】93最一般合一置换的求取算法：差异集在对两个谓词公式中的项从左到右进行比较时，那些不相同的项所构成的集合，称为差异集。设S=｛P(x,y,z),P(x,f(a),h(b))｝，则不难看出，S有两个差异集D1=｛y,f(a)｝D2=｛z,h(b)｝94最一般合一置换的求取算法：差异集94置k=0,Sk=S，σk=ε;若Sk只含有一个谓词公式，则算法停止，σk就是要求的最一般合一;求Sk的差异集Dk;若Dk中存在元素xk和tk，其中xk是变元，tk是项且xk不在tk中出现，则置Sk+1=Sk｛tk/xk｝,σk+1=σk·｛tk/xk｝，k=k+1，然后转②;算法停止，S的最一般合一不存在。95置k=0,Sk=S，σk=ε;95【实例1】1.求公式集S=｛P(a,x,f(g(y))),P(z,h(z,u),f(u))｝的最一般合一。解：k=0：S0=S,σ0=ε,S0不是单元素集，求得D0=｛a,z｝，其中z是变元，且不在a中出现，所以有σ1=σ0·｛a/z｝=ε·｛a/z｝=｛a/z｝S1=S0｛a/z｝=｛P(a,x,f(g(y))),P(a,h(a,u),f(u))｝

k=1:S1不是单元素集，求得D1=｛x,h(a,u)｝，σ2=σ1·{h(a,u)/x}={a/z}·{h(a,u)/x}={a/z,h(a,u)/x}S2=S1{h(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:S2不是单元素集，D2=｛g(y),u｝，σ3=σ2·｛g(y)/u｝=｛a/z,h(a,g(y))/x,g(y)/u｝S3=S2{g(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,y｝σ1=σ0·｛y/x｝=｛y/x｝S1=S0｛y/x｝=｛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（合一定理）如果S是一个非空有限可合一的公式集，则合一算法总是在步②停止，且最后的σk即是S的最一般合一。本定理说明任一非空有限可合一的公式集，一定存在最一般合一，而且用合一算法总能找到最一般合一，这个最一般合一也就是当算法终止在步②时，最后的合一σk。99定理3（合一定理）如果S是一个非空有限谓词逻辑中的归结原理

定义12

设C1,C2是两个无相同变元的子句，L1,L2分别是C1,C2中的两个文字，如果L1和乛L2有最一般合一σ，则子句

(C1σ-｛L1σ｝)∪(C2σ-｛L2σ｝)称作C1和C2的二元归结式(二元消解式)，C1和C2称作归结式的亲本子句，L1和L2称作消解文字。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σ｝)∪(C2σ-｛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(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【补充说明】如果在参加归结的子句内定义14子句C1,C2的消解式，是下列二元消解式之一：(1)C1和C2的二元消解式;(2)C1和C2的因子的二元消解式;(3)C1的因子和C2的二元消解式;(4)C1的因子和C2的因子的二元消解式。104定义14子句C1,C2的消解式，是下列二元消解式之一：104定理4

谓词逻辑中的消解式是它的亲本子句的逻辑结果。

由此定理我们即得谓词逻辑中的推理规则：C1∧C2(C1σ-｛L1σ｝)∪(C2σ-｛L2σ｝)其中C1,C2是两个无相同变元的子句，L1,L2分别是C1,C2中的文字，σ为L1与L2的最一般合一。此规则称为谓词逻辑中的消解原理（或归结原理）。105定理4谓词逻辑中的消解式是它的亲本子句的逻辑结果。4.利用归结原理进行定理证明归结原理指出了证明子句集不可满足性的方法。设要被证明的定理用谓词公式表示为应用归结原理进行定理证明的步骤如下：首先否定结论，并将否定后的结论谓词公式﹁B与前提条件公式集组成如下形式的谓词公式：求谓词公式G的子句集S；应用归结原理，证明子句集S的不可满足性，从而证明谓词公式G的不可满足性。反证法1064.利用归结原理进行定理证明归结原理指出了证明子句集不可满【实例】求证G是A1和A2的逻辑结果。A1:x(P(x)→(Q(x)∧R(x)))A2:x(P(x)∧S(x))G:x(S(x)∧R(x))

证：我们用反证法，即证明A1∧A2∧乛G不可满足。首先求得子句集S：

107【实例】求证G是A1和A2的逻辑结果。证：我们用反证法，即(1)乛P(x)∨Q(x)(2)乛P(y)∨R(y)(3)P(a)(4)S(a)(5)乛S(z)∨乛R(z)(乛G)然后应用消解原理得:(6)R(a)［(2),(3),σ1=｛a/y｝］(7)乛R(a)［(4),(5),σ2=｛a/z｝］(8)NIL［(6),(7)］所以S是不可满足的，从而G是A1和A2的逻辑结果。

(A1)(A2)S108(1)乛P(x)∨Q(x)(A1)(A2)S108【实例】设已知：(1)能阅读者是识字的；(2)海豚不识字；(3)有些海豚是很聪明的。试证明：有些聪明者并不能阅读。证：首先，定义如下谓词：R(x)：x能阅读。L(x)：x识字。I(x)：x是聪明的。D(x)：x是海豚。

109【实例】设已知：109然后把上述各语句翻译为谓词公式：(1)x(R(x)→L(x))(2)x(D(x)→乛L(x))已知条件(3)x(D(x)∧I(x))(4)x(I(x)∧乛R(x))需证结论求题设与结论的否定子句集，得(1)乛R(x)∨L(x)(2)乛D(y)∨乛L(y)(3)D(a)(4)I(a)(5)乛I(z)∨R(z)110然后把上述各语句翻译为谓词公式：求题设与结论的否定子句集，得归结得：(6)R(a)[(5)，(4)，{a/z}](7)L(a)[(6)，(1)，{a/x}](8)乛D(a)[(7),(2),{a/y}](9)NIL[(8),(3)]这个归结过程的演绎树如图。111归结得：111

由以上例子可以看出，谓词逻辑中的消解原理也可以代替其他推理规则。上面我们通过推导空子句，证明了子句集的不可满足性，于是存在问题：对于任一不可满足的子句集，是否都能通过归结原理推出空子句呢？回答是肯定的。

定理5（归结原理的完备性定理）如果子句集S是不可满足的，那么必存在一个由S推出空子句NIL的消解序列。112由以上例子可以看出，谓词逻5.利用归结原理进行问题求解

归结原理除了能用于对已知结果的证明外，还能用于对未知结果的求解，即能求出问题的答案来。

1135.利用归结原理进行问题求解归结原【问题求解的基本步骤】把已知条件用谓词公式表示，并化成相应的子句集S1；把待求解的问题也用谓词公式表示，然后将其否定，并与谓词ANSWER构成析取式G1；把G1化为子句集S2，并把子句集S2与S1合并构成新子句集S；对子句集S应用谓词归结原理进行归结，在归结过程中通过合一置换，改变ANSWER中的变元；如果得到归结式ANSWER，则问题的答案就在ANSWER谓词中。114【问题求解的基本步骤】114【实例1】已知:(1)如果x和y是同班同学，则x的老师也是y的老师。(2)王先生是小李的老师。(3)小李和小张是同班同学。问：小张的老师是谁？115【实例1】已知:115

解:设谓词T(x,y)表示x是y的老师，C(x,y)表示x与y是同班同学，则

①已知可表示成如下的谓词公式：F1:xyz(C(x,y)∧T(z,x)→T(z,y))F2:T(Wang,Li)F3:C(Li,Zhang)将它们化成子句集为S1={﹁C(x,y)∨﹁T(z,x)∨T(z,y)),T(Wang,Li),C(Li,Zhang）}116解:设谓词T(x,y)表示x是y的老师，C(x②把问题用谓词公式表示，并将其否定与谓词ANSWER作析取：

设小张的老师是u，则有T(u,Zhang)G1:﹁T(u,Zhang)∨ANSWER(u)③将析取式G1化成子句集S2,并将S1与S2合并为新子句集S：S2={﹁T(u,Zhang)∨ANSWER(u)}S=S1∪S2={﹁C(x,y)∨﹁T(z,x)∨T(z,y)),…….(a)T(Wang,Li),…….(b)C(Li,Zhang),…….(c)﹁T(u,Zhang)∨ANSWER(u)}…….(d)117②把问题用谓词公式表示，并将其否定与谓词ANSWER作析取：④应用归结原理进行归结：(e)﹁C(Li,y)∨T(Wang,y)[a与b归结，（Li/x,Wang/z)](f)﹁T(z,Li)∨ANSWER(u)[d与e归结，（Wang/u,Zhang/y)](g)ANSWER(Wang)[b与f归结]⑤得到归结式ANSWER（Wang），答案即在其中：

u=Wang，即小张的老师是王先生。118④应用归结原理进行归结：118【实例2】设有如下关系:(1)如果x是y的父亲，y又是z的父亲，则x是z的祖父。(2)老李是大李的父亲。(3)大李是小李的父亲。问：上述人员中谁和谁是祖孙关系？119【实例2】设有如下关系:119解：①先把上述前提中的三个命题符号化为谓词公式：F1:xyz(F(x,y)∧F(y,z)→G(x,z))F2:F(Lao,Da)F3:F(Da,Xiao)②求其子句集如下:S1={乛F(x,y)∨乛F(y,z)∨G(x,z),F(Lao,Da),F(Da,Xiao)}120解：①先把上述前提中的三个命题符号化为谓词公式：120②把问题用谓词公式表示，并将其否定与谓词ANSWER作析取：

设u,v为祖孙关系，则有G(u,v)G1:﹁G(u,v)∨ANSWER(u,v)③将析取式G1化成子句集S2,并将S1与S2合并为新子句集S：S2={﹁G(u,v)∨ANSWER(u,v)}S=S1∪S2={乛F(x,y)∨乛F(y,z)∨G(x,z),…….(a)F(Lao,Da),…….(b)F(Da,Xiao)…….(c)﹁G(u,v)∨ANSWER(u,v)}…….(d)121②把问题用谓词公式表示，并将其否定与谓词ANSWER作析取：④应用归结原理进行归结：(e)﹁F(Da,z)∨G(Lao,z)[a与b归结，（Lao/x,Da/y)](f)G(Lao,Xiao)[c与e归结，（Xiao/z)](g)ANSWER(Lao,Xiao)[d与f归结,Lao/u,Xiao/v]⑤得到归结式ANSWER（Lao,Xiao），答案即在其中：

u=Lao,v=Xiao，即老李是小李的祖父。122④应用归结原理进行归结：1226.归结策略

引入归结策略的原因：问题：如果采用盲目的归结策略，将产生大量无用的归结式，在计算机上实现时造成惊人的浪费！目的：选择合适的子句进行归结，以少量的归结尽快导出空子句。归结控制策略1236.归结策略引入归结策略的原因：问题：如果采用盲目的归归结策略的类型：归结策略删除策略限制策略通过删除某些无用的子句来缩小归结范围。通过对参加归结的子句进行种种限制，尽可能地减少归结的盲目性。124归结策略的类型：归结策略删除策略限制策略通过删除某些•如果文字L出现在子句集S中，而﹁L不出现在S中，则称L为S的纯文字。如果一个子句中同时包含互补文字时，则称该子句为重言式。对于子句C1和C2，如果存在一个置换σ使得C1σ∈C2，则称C1类含于C2。删除策略（完备）125•如果文字L出现在子句集S中，而﹁L不出现在S中，则称L为在归结过程中可随时删除以下子句：(1)含有纯文字的子句；(2)含有永真式的子句；(3)被子句集中别的子句类含的子句。126在归结过程中可随时删除以下子句：126【实例】S={T∨Q∨R,﹁R,Q,R∨﹁Q}S’={﹁R,Q,R∨﹁Q}T为纯文字S={P(x),P(y)∨Q(z),P(a)∨R(x)}S’={P(x)∨Q(z),P(a)∨R(x)}P(x)类含于P(y)∨Q(z),σ=y/x127【实例】S={T∨Q∨R,﹁R,Q,R∨﹁Q}S’=首先从子句集中选取一个称作顶子句的子句C0开始作归结。归结过程中所得到的归结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现的归结式Cj(j<i)。C0C1C2C3C4C5空线性归结策略示意图线性归结策略（完备）128首先从子句集中选取一个称作顶子句的子句C【实例】设有子句集S={乛I(x)∨R(x),I(a),乛R(y)∨乛L(y),L(a)}用线性归结策略归结。解：已知子句为：(1)乛I(x)∨R(x)(2)I(a)(3)乛R(y)∨乛L(y)(4)L(a)进行线性归结：(5)R(a)[由(1)(2),{a/x}](6)乛L(a)[由(5)(3),{a/y}](7)□[由(6)(4)]129【实例】设有子句集129在归结过程中，每次归结都有一个子句是单元子句（只含一个文字的子句）或单元因子。显而易见，此方法可以简单地削去另一个非单子句中的一个因子，使其长度减少，构成简单化，归结效率较高。【注】初始子句集中没有单元子句时，单元归结策略无效，即此问题不能采用单元归结策略。

单元归结策略（不完备）130在归结过程中，每次归结都有一个子句是单元子句（只含一

在归结过程中，每一次归结的两个子句中必须有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结，造成恶性循环。【注】原始子句集中没有单元子句的谓词公式一定不能采用输入归结策略。

输入归结策略（不完备）131在归结过程中，每一次归结的两个子句中必须有一个是S的•

支持集：

目标公式否定的子句集即为支持集。

支持集策略（完备）

每次归结时，参加归结的两个子句中至少应有一个是由目标公式的否定所得到的子句或其后裔。132•支持集：支持集策略（完备）每次归结时，参加归【实例】设有子句集S={乛I(x)∨R(x),I(a),乛R(y)∨乛L(y),L(a)}假设其中子句乛I(x)∨R(x)是目标公式否定的子句。用支持集策略进行归结。解：已知子句集S为：(1)乛I(x)∨R(x)(2)I(a)(3)乛R(y)∨乛L(y)(4)L(a)

133【实例】设有子句集133S1:(5)R(a)[由(1),(2),{a/x}](6)乛I(x)∨乛L(x)[由(1),(3),{x/y}]S2:(7)乛L(a)[由(5),(3),{a/y}](8)乛L(a)[由(6),(2),{a/x}](9)乛I(a)[由(6),(4),{a/x}](10)□[由(7),(4)]134S1:(5)R(a)[由(1),(2)第4章确定性推理135第4章确定性推理1本章学习要点掌握谓词公式的概念及可满足性的定义、置换与合一的概念，掌握求取最一般合一置换的方法。掌握归结原理及归结推理方法。（重点在谓词逻辑中）掌握利用归结原理进行定理证明的方法。掌握利用归结原理进行问题求解的方法。了解归结过程中的控制策略。136本章学习要点掌握谓词公式的概念及可满足性的定义、置换与合一的4.1概述4.2确定性推理主要内容1374.1概述4.2确定性推理主要内容3人工智能学科知识获取知识表示知识推理确定性推理不确定性推理138人工智能学科知识获取知识表示知识推理确定性推理不确定性推理44.1.1推理的基本概念

推理的定义推理就是按照某种策略从已有事实和知识推出结论的过程。一般来说，人工智能系统中的智能推理过程是由一些程序来完成的，这些程序在人工智能系统中称为推理机。

4.1推理概述1394.1.1推理的基本概念4.1推理概述54.1.2推理的分类按推理的逻辑基础分类

1）演绎推理：从已知的一般性知识出发，推理出适合于某种个别情况的结论过程。即从一般到个别的推理。常用形式：三段论法(大前提、小前提、结论)1404.1.2推理的分类按推理的逻辑基础分类6【演绎推理实例】音乐系的学生至少会演奏一种乐器；（大前提）李聪是音乐系的一名学生；（小前提）李聪至少会演奏一种乐器。（结论）141【演绎推理实例】音乐系的学生至少会演奏一种乐器；（大前提）72）归纳推理：从大量特殊事例出发，归纳出一般性结论的推理过程。即从个别到一般的推理过程。归纳推理完全归纳推理不完全归纳推理枚举归纳推理类比归纳推理特殊事例考察范围推理使用方法1422）归纳推理：从大量特殊事例出发，归纳出一般性结

3）默认推理：在知识不完全的情况下，假设某些条件已经具备所进行的推理。默认推理过程中可能会出现一些无效推理，但默认推理解决了在一个不完备知识集中进行推理的问题。1433）默认推理：在知识不完全的情况下，假设某些条

1)确定性推理推理时所有用的知识和证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假，没有第三种情况出现。2)不确定性推理推理时所用的知识和证据不都是确定的，推出的结论也不确定的。按所用知识的确定性分类1441)确定性推理按所用知识的确定性分类101)单调推理

在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标。

2)非单调推理

在推理过程中随着推理的向前推进及新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。按推理过程的单调性分类1451)单调推理按推理过程的单调性分类111)启发式推理

推理过程中应用与问题有关的启发性知识，即解决问题的的策略、技巧及经验，以加快推理过程，提高搜索效率。2)非启发式推理在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理。这种方法缺乏对求解问题的针对性，所以推理效率较低，容易出现“组合爆炸”问题。按推理中所用知识是否具有启发性分类1461)启发式推理按推理中所用知识是否具有启发性分4.1概述4.2确定性推理主要内容1474.1概述4.2确定性推理主要内容13确定性推理归结推理演绎推理命题逻辑谓词逻辑海伯伦定理数理逻辑基础命题逻辑归结基本概念谓词逻辑归结原理Skolem标准形，子句集合一和置换，控制策略4.2确定性推理148确定性推理归结推理演绎推理命题逻辑谓词逻辑海伯伦定理数理逻辑【推理的逻辑基础】 逻辑是推理科学的研究。逻辑研究主要是研究推理的过程是否正确，推理过程中各个语句之间的关系，而不考虑某一个语句是否正确。

命题逻辑和谓词逻辑属于经典逻辑，是最先应用于人工智能的两种逻辑。其中谓词逻辑是在命题逻辑的基础上发展起来的，是一种表达能力很强的形式语言。149【推理的逻辑基础】 逻辑是推理科学的研究。逻辑命题

能够分辨真假的语句称为命题。一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为原子命题。原子命题是命题中最基本的单位，常用大写字母P,Q,R等表示。4.2.1命题逻辑基础150命题4.2.1命题逻辑基础16判断以下句子，哪些是命题哪些不是？

①1+1=10。②快点走吧！③雪是黑色的。④西安是个古老的城市。⑤明天是否开大会？⑥如果天气好，那么我去散步。是不是是是不是是151判断以下句子，哪些是命题哪些不是？是17∧

：合取(与),∨

：析取(或),：等价(当且仅当)。：蕴含(IF…THEN),：否定(非)，P

Q

P∨QP∧QP→Q~PTTTTTFFTTFTTTFTFFFFFFFTT命题逻辑真值表2.连接词152∧：合取(与),∨：析取(或),：等价(当且仅当)。：蕴连接词的优先级别∧∨153连接词的优先级别∧∨19原子命题是命题公式。A是命题公式，则﹁A也是命题公式。若A和B都是命题公式，则A∧B、A∨B、AB、AB也都是命题公式。按照上述规则由原子命题、连接词及圆括号所组成的字符串称为命题公式。3.命题公式154原子命题是命题公式。3.命题公式20①他既聪明又用功。②应届高中生，得过数学或物理竞赛的一等奖，保送上大学。①设P：他聪明。Q：他用功。转换为：P∧

Q。②设P：应届高中生。Q：保送上大学。A：得过数学竞赛一等奖。B：得过物理竞赛一等奖。表示为：P∧(A∨B)→Q例：将陈述句转化为命题公式。【命题公式实例】155①他既聪明又用功。①设P：他聪明。Q：他用功。转换为：P1.基本概念4.2.2一阶谓词逻辑基础个体：独立存在的物体（抽象或具体）个体：独立存在的物体（抽象或具体）谓词：用于刻画个体性质、状态或个体间关系。5>3Greater(5,3)李白是诗人Poet(LiBai)一元谓词二元谓词一阶谓词1561.基本概念4.2.2一阶谓词逻辑基础个体：独立存在的物体3.谓词公式2.连接词：¬，∧，∨，→，单个谓词是谓词公式，称为原子谓词公式。若A是谓词公式，则¬A也是谓词公式。若A，B都是谓词公式，则(A∧B)，(A∨B)，(A→B)，(AB)也是谓词公式

。若A是谓词公式，则也是谓词公式。只有有限次的应用上述4条规则构成的符号串才是谓词公式。1573.谓词公式2.连接词：¬，∧，∨，→，单个谓词是谓词位于量词后面的单个谓词或者用括弧括起来的的合式公式称为量词的辖域。在辖域内与量词同名的变元称为约束变元，不受约束的变元称为自由变元。4.量词辖域与约束变元全称量词全称量词的辖域存在量词存在量词的辖域约束变元自由变元158位于量词后面的单个谓词或者用括弧括起来的的合式公式称永真式:如果谓词公式P在每个非空个体域上均取得真值T，则称P永真。永假式:如果谓词公式P在每个非空个体域上均取得真值F，则称P永假。可满足式:对于谓词公式P，如果至少存在一个值使得P的真值为T，则称公式P是可满足的。不可满足式:对于谓词公式P，如果不存在任何值使得P的真值为T，则称公式P是不可满足的。5.谓词公式的永真性159永真式:如果谓词公式P在每个非空个体域上均取得真值T，则称交换律：

PQP∨QTTTTFTFTTFFFPQP∧QTTTTFFFTFFFF6.谓词公式的等价性160交换律：PQP∨Q

结合律：PQRP∨Q(P∨Q)∨R(Q∨R)P∨(Q∨R)TTTTTTTTTFTTTTTFTTTTTTFFTTFTFTTTTTTFTFTTTTFFTFTTTFFFFFFF步骤1234161结合律：PQRP∨Q(P∨Q)∨R(Q∨R)P∨(

结合律：PQRP∧Q(P∧Q)∧R(Q∧R)P∧(Q∧R)TTTTTTTTTFTFFFTFTFFFFTFFFFFFFTTFFTFFTFFFFFFFTFFFFFFFFFFF步骤1234162结合律：PQRP∧Q(P∧Q)∧R(Q∧R)P∧(分配律：PQR(Q∧R)P∨(Q∧R)(P∨Q)(P∨R)(P∨Q)∧(P∨R)TTTTTTTTTTFFTTTTTFTFTTTTTFFFTTTTFTTTTTTTFTFFFTFFFFTFFFTFFFFFFFFF步骤12345163分配律：PQR(Q∧R)P∨(Q∧R)(P∨Q)(P分配律：PQR(Q∨R)P∧(Q∨R)(P∧Q)(P∧R)(P∧Q)∨(P∧R)TTTTTTTTTTFTTTFTTFTTTFTTTFFFFFFFFTTTFFFFFTFTFFFFFFTTFFFFFFFFFFFF步骤12345164分配律：PQR(Q∨R)P∧(Q∨R)(P∧Q)(狄·

摩根律：PQP∨Q¬(P∨Q)¬P¬Q¬P∧¬QTTTFFFFTFTFFTFFTTFTFFFFFTTTT步骤12345165狄·摩根律：PQP∨Q¬(P∨Q)¬P¬Q¬P∧¬Q狄·

摩根律：PQP∧Q¬(P∧Q)¬P¬Q¬P∨¬QTTTFFFFTFFTFTTFTFTTFTFFFTTTT步骤12345166狄·摩根律：PQP∧Q¬(P∧Q)¬P¬Q¬P∨¬Q吸收律：PQP∧QP∨(P∧Q)TTTFTFFTFTFFFFFF步骤12167吸收律：PQP∧QP∨(P∧Q)TTTFTFFTFTF吸收律：PQP∨QP∧(P∨Q)TTTTTFTTFTTFFFFF步骤12168吸收律：PQP∨QP∧(P∨Q)TTT同一律：P0P∨0TFTTFTFFFFFF步骤1P1P∧1TTTTTTFTFFTF步骤1零律：