归结演绎推理课件.ppt

1、1人工智能 1.什么是推理什么是推理 推理是按照某种策略从已知事实出发去推推理是按照某种策略从已知事实出发去推出结论的过程。出结论的过程。推理所用事实可分为两种：推理所用事实可分为两种：u与求解问题有关的初始证据。与求解问题有关的初始证据。u推理过程中所得到的中间结论。推理过程中所得到的中间结论。2人工智能 通常智能系统的推理过程是通过推理机来完成的。通常智能系统的推理过程是通过推理机来完成的。推理机就是用来实现推理的那些程序。推理机就是用来实现推理的那些程序。智能系统的推理包括两个基本问题：智能系统的推理包括两个基本问题：u推理的方法。推理的方法。u推理的控制策略。推理的控制策略。3人工智能

2、 2.推理方法及其分类推理方法及其分类 推理方法主要解决在推理过程中前提与结论之间推理方法主要解决在推理过程中前提与结论之间的逻辑关系，以及在非精确性推理中不确定性的传递的逻辑关系，以及在非精确性推理中不确定性的传递问题。问题。(1)按推理的逻辑基础分类按推理的逻辑基础分类 演绎推理（一般到个别）演绎推理（一般到个别）是从已知的一般性知识出发，去推出蕴涵在这些是从已知的一般性知识出发，去推出蕴涵在这些已知知识中的适合与某种个别情况的结论。其核心是已知知识中的适合与某种个别情况的结论。其核心是三段论：假言推理、拒取式和假言三段论。三段论：假言推理、拒取式和假言三段论。4人工智能 常用的三段论是由

3、一个大前提、一个小前提和一常用的三段论是由一个大前提、一个小前提和一个结论三部分组成。个结论三部分组成。其中其中:大前提是已知的一般性知识或推理过程得到的判断；大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。结论是由大前提推出的，并且适合于小前提的判断。5人工智能 例如：例如：摔跤运动员的身体都是强壮的；摔跤运动员的身体都是强壮的；（大前提）（大前提）李名是一名摔跤运动员；李名是一名摔跤运动员；（小前提）（小前提）所以，李名的身体是强壮的。所以，李名的身体是强

4、壮的。（结论）（结论）6人工智能 归纳推理（个别到一般）归纳推理（个别到一般）是从一类事物的大量特殊实例出发，去推出该类是从一类事物的大量特殊实例出发，去推出该类事物的一般性结论。事物的一般性结论。按所选事例的广泛性可分为完全归纳推理和不完按所选事例的广泛性可分为完全归纳推理和不完全归纳推理。全归纳推理。按所选的方法可分为枚举归纳推理、类比归纳推按所选的方法可分为枚举归纳推理、类比归纳推理和差异归纳推理等。理和差异归纳推理等。默认推理默认推理 是在知识不完全的情况假设某些条件已经具备所是在知识不完全的情况假设某些条件已经具备所进行的推理，也称为缺省推理。进行的推理，也称为缺省推理。7人工智能

5、(2)按所用知识的确定性分类按所用知识的确定性分类 分为确定性推理与不确定性推理。分为确定性推理与不确定性推理。确定性推理是指推理所使用的知识和推出的结论确定性推理是指推理所使用的知识和推出的结论都是可以精确表示的，其值要么为真，要么为假。都是可以精确表示的，其值要么为真，要么为假。不确定性推理是指推理所使用的知识不都是精确不确定性推理是指推理所使用的知识不都是精确的，推出的结论也不完全是确定的，其值会位于真与的，推出的结论也不完全是确定的，其值会位于真与假之间。假之间。8人工智能(3)按推理过程的单调性按推理过程的单调性 单调推理与非单调推理。单调推理与非单调推理。单调推理是指在推理过程中每

6、当使用新的知识后，单调推理是指在推理过程中每当使用新的知识后，所得到的结论会愈来愈接近于目标，而不会出现反复所得到的结论会愈来愈接近于目标，而不会出现反复情况。情况。非单调推理是指在推理过程中当某些新知识加入非单调推理是指在推理过程中当某些新知识加入后，会否定原来推出的结论，使推理过程回到先前的后，会否定原来推出的结论，使推理过程回到先前的某一步。某一步。9人工智能 3.推理的控制策略及其分类推理的控制策略及其分类 推理的控制策略是指如何使用领域知识使推理过推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。程尽快达到目标的策略。由于智能系统的推理过程一般表现为一种搜索过由于智能系

7、统的推理过程一般表现为一种搜索过程，因此推理的控制策略分为程，因此推理的控制策略分为:F推理策略：主要解决推理方向、冲突消解等问题。推理策略：主要解决推理方向、冲突消解等问题。F搜索策略：主要解决推理路线、推理效果、推理效率搜索策略：主要解决推理路线、推理效果、推理效率等问题。等问题。10人工智能 推理方向用来确定推理的控制方式，即推理过程推理方向用来确定推理的控制方式，即推理过程是从初始证据开始到目标，还是从目标开始到初始证是从初始证据开始到目标，还是从目标开始到初始证据。按照对推理方向的控制，推理又分为：据。按照对推理方向的控制，推理又分为：F正向推理正向推理F逆向推理逆向推理F混合推理混

8、合推理F双向推理双向推理 无论哪一种推理方式，系统都需要有一个存放知无论哪一种推理方式，系统都需要有一个存放知识的知识库，一个存放初始证据及中间结果的综合数识的知识库，一个存放初始证据及中间结果的综合数据库和一个用于推理的推理机。据库和一个用于推理的推理机。11人工智能 4.正向推理（数据驱动推理、前向链推理）正向推理（数据驱动推理、前向链推理）是从已知事实出发、正向使用推理规则的推理方式。是从已知事实出发、正向使用推理规则的推理方式。正向推理算法描述：正向推理算法描述：（1）把用户提供的初始证据放入综合数据库。）把用户提供的初始证据放入综合数据库。（2）检查综合数据库中是否包含了问题的解，若

9、已包含，）检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功退出；否则执行下一步。则求解结束，并成功退出；否则执行下一步。（3）检查知识库中是否有可用知识，若有，形成当前可）检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转（用知识集，执行下一步；否则转（5）。）。12人工智能 (4）按照某种冲突消解策略，从当前可用知识集中选出）按照某种冲突消解策略，从当前可用知识集中选出一条知识进行推理，并将推出的新事实加入综合数据一条知识进行推理，并将推出的新事实加入综合数据库中，然后转（库中，然后转（2）。）。（5）询问用户是否可以进一步补充新的事实，如若可以，）询问

10、用户是否可以进一步补充新的事实，如若可以，则将补充的新事实加入综合数据库中，然后转（则将补充的新事实加入综合数据库中，然后转（3）；）；否则表示无解，失败退出。否则表示无解，失败退出。正向推理的优点：正向推理的优点：直观，允许用户主动提供有用的事实直观，允许用户主动提供有用的事实信息，适合于诊断、设计、监控等领域的问题求解。信息，适合于诊断、设计、监控等领域的问题求解。正向推理的缺点正向推理的缺点：推理无明确目标，求解问题可能执行推理无明确目标，求解问题可能执行许多与解无关的操作，导致推理效率低许多与解无关的操作，导致推理效率低13人工智能 5.逆向推理（目标驱动推理、逆向链推理）逆向推理（目

11、标驱动推理、逆向链推理）是一种以某个假设目标作为出发点的推理方法。是一种以某个假设目标作为出发点的推理方法。逆向推理算法描述：逆向推理算法描述：（1）把要求求证的目标（称为假设）构成一个假设集；）把要求求证的目标（称为假设）构成一个假设集；（2）从假设集中选出一个假设，检查该假设是否在综合）从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出；否则仍执行（空，则成功退出；否则仍执行（2）；若不在综合数据）；若不在综合数据库中，则执行下一步。库中，则执行下一步。14人工智能（3）检查该假设是否可由知

12、识库的某个知识导出。若不）检查该假设是否可由知识库的某个知识导出。若不能由某个知识导出，则询问用户该假设是否为可由用能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转综合数据库，再重新寻找新的假设，若不是，则转（5）；若能由某个知识导出，则执行下一步；）；若能由某个知识导出，则执行下一步；（4）将知识库中可以导出该假设的所有知识构成一个可）将知识库中可以导出该假设的所有知识构成一个可用知识集；用知识集；（5）检查知识集是否为空，若空，失败退出；否则执行）检查知识集

13、是否为空，若空，失败退出；否则执行下一步；下一步；（6）按冲突消解策略从可用知识集中取出一个知识，继）按冲突消解策略从可用知识集中取出一个知识，继续执行下一步；续执行下一步；（7）将该知识的前提中的每个子条件都作为新的假设放）将该知识的前提中的每个子条件都作为新的假设放入假设集，转（入假设集，转（2）。）。15人工智能 例例3.1 设推理开始时，知识库中的规则和综合数据库中的设推理开始时，知识库中的规则和综合数据库中的事实如下：事实如下：规则规则1：IF 你丢了自行车钥匙，并且车胎没气你丢了自行车钥匙，并且车胎没气 THEN 自行车不能骑自行车不能骑 规则规则2：IF 自行车不能骑，并且你只能

14、走路去自行车不能骑，并且你只能走路去 THEN 你你听功课会迟到听功课会迟到 事实事实1：你丢了自行车：你丢了自行车 事实事实2：车胎没气：车胎没气 16人工智能 如果利用逆向推理求证如果利用逆向推理求证“你听课会迟到你听课会迟到”这一假这一假设，其推理过程如下：设，其推理过程如下：（1）从假设集中取出该假设，查找综合数据库，直该假）从假设集中取出该假设，查找综合数据库，直该假设不是综合数据库中的事实。设不是综合数据库中的事实。（2）查找知识库，发现该假设可由规则）查找知识库，发现该假设可由规则2导出，于是规导出，于是规则则2被放入可用知识集被放入可用知识集（3）由于只有这一条规则可用，故可用

15、知识集中只有规）由于只有这一条规则可用，故可用知识集中只有规则则2。从可用知识集中取出规则。从可用知识集中取出规则2，将其与两个前提条，将其与两个前提条件件“自行车不能骑自行车不能骑”和和“你只有走路去你只有走路去”都作为新的都作为新的假设放入假设集。假设放入假设集。17人工智能（4）从假设集中取出一个假设）从假设集中取出一个假设“自行车不能骑自行车不能骑”，它不，它不是综合数据库中的事实，但可由规则是综合数据库中的事实，但可由规则1导出，于是规则导出，于是规则1被放入可用知识集，此时可用知识集中仍然是只有一被放入可用知识集，此时可用知识集中仍然是只有一条规则。条规则。（5）从可用知识集中提出

16、规则）从可用知识集中提出规则1，将其两个前提条件，将其两个前提条件“你丢了自行车钥匙你丢了自行车钥匙”和和“车胎没气车胎没气”也作为新的假也作为新的假设放入假设集。设放入假设集。18人工智能（6）再从假设集中取出一个假设）再从假设集中取出一个假设“你只有走路去你只有走路去”，检，检查发现此假设既不在综合数据库中也不能被任何一条查发现此假设既不在综合数据库中也不能被任何一条规则所导出，询问用户规则所导出，询问用户“你只有走路去吗？你只有走路去吗？”若用户若用户回答回答“是是”，则该假设成立，并被放入综合数据库中。，则该假设成立，并被放入综合数据库中。此时，假设集中还有两个假设此时，假设集中还有两

17、个假设“你丢了自行车钥匙你丢了自行车钥匙”和和“车胎没气车胎没气”（7）继续推理，显然它们都是综合数据库中的事实，均）继续推理，显然它们都是综合数据库中的事实，均为真。为真。（8）继续推理，假设库也为空，推理过程结束，）继续推理，假设库也为空，推理过程结束，“你听你听课会迟到课会迟到”得证。得证。19人工智能 逆向推理的优点：逆向推理的优点：不必寻找和使用那些与假设目标无关的信息和知不必寻找和使用那些与假设目标无关的信息和知识，推理过程的目标明确，同时有利于向用户提供解识，推理过程的目标明确，同时有利于向用户提供解释，在诊断性专家系统中较为有效。释，在诊断性专家系统中较为有效。逆向推理的缺点：

18、逆向推理的缺点：当用户对解的情况不清时，由系统自主选择假设当用户对解的情况不清时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。出假设，会影响系统效率。20人工智能 6.混合推理混合推理(1).混合推理的方法混合推理的方法 先正向后逆向的混合推理先正向后逆向的混合推理 先逆向后正向的混合推理先逆向后正向的混合推理 双向混合推理双向混合推理21人工智能(2).混合推理的适用场合混合推理的适用场合 已知事实不够充分已知事实不够充分 由正向推理推出的结论不可靠由正向推理推出的结论不可靠 希望得出更多的结论希望得出

19、更多的结论 希望从正反两方向同时进行推理希望从正反两方向同时进行推理22人工智能 7.推理的冲突消解策略推理的冲突消解策略 在推理的某一步，如果知识库中有多条知识可用，在推理的某一步，如果知识库中有多条知识可用，则称发生了冲突，此时需要按照某种策略从这多条知则称发生了冲突，此时需要按照某种策略从这多条知识中选择一条最佳知识用于推理，称这种解决冲突的识中选择一条最佳知识用于推理，称这种解决冲突的过程为冲突消解。冲突消解所用的策略则称为冲突消过程为冲突消解。冲突消解所用的策略则称为冲突消解策略。解策略。冲突消解的基本思想是对可用知识库进行排序。冲突消解的基本思想是对可用知识库进行排序。23人工智能

20、 目前，常用的冲突消解策略有：目前，常用的冲突消解策略有：.特殊知识优先特殊知识优先 新鲜知识优先新鲜知识优先 差异性大的知识优先差异性大的知识优先 领域特点优先领域特点优先 上下文关系优先上下文关系优先 前提条件少者优先前提条件少者优先24人工智能 1.谓词公式的解释谓词公式的解释 定义定义3.1 3.1 设设D D是谓词公式是谓词公式P P的非空个体域，若对的非空个体域，若对P P中的个中的个体常量、函数和谓词按如下规定赋值：体常量、函数和谓词按如下规定赋值：（1 1）为每个个体常量指派）为每个个体常量指派D D中的一个元素；中的一个元素；（2 2）为每个）为每个n n元函数指派一个从元函

21、数指派一个从DnDn到到D D的一个映射，的一个映射，其中其中 DnDn=(x1,x2,=(x1,x2,xn,xn)|x1,x2,)|x1,x2,xn,xn DD （3 3）为每个）为每个n n元谓词指派一个从元谓词指派一个从DnDn到到FF、TT的映的映射。射。则称这些指派为则称这些指派为P P在在D D上的一个解释。上的一个解释。25人工智能 例例3.2 3.2 设个体域设个体域D=1,2D=1,2，求公式，求公式A=(A=(x x)()(y)P(x,y)y)P(x,y)在在D D上的解释，并指出在每一种解释下公式的真值。上的解释，并指出在每一种解释下公式的真值。解：由于公式解：由于公式A

22、 A中没有包含个体域和函数，因此可以直接中没有包含个体域和函数，因此可以直接为谓词指派真值，设有：为谓词指派真值，设有：P(1,1)P(1,2)P(2,1)P(2,2)T F T F26人工智能 这就是公式这就是公式A A在在D D上的一个解释。从这个解释可以看上的一个解释。从这个解释可以看出：出：当当x=1x=1、y=1y=1时，有时，有P(x,y)P(x,y)的真值为的真值为T;T;当当x=2x=2、y=1y=1时，有时，有P(x,y)P(x,y)的真值为的真值为T;T;即对即对x x在在D D上的任意取值，都存在上的任意取值，都存在y=1y=1使使P(x,y)P(x,y)的真值的真值为为

23、T T。因此，在此解释下公式。因此，在此解释下公式A A的真值为的真值为T T。需要注意，一个谓词公式在其个体域上的解释不是需要注意，一个谓词公式在其个体域上的解释不是唯一的。例如，对公式唯一的。例如，对公式A A，若给出另一组真值指派，若给出另一组真值指派 P(1,1)P(1,2)P(2,1)P(2,2)T T F F27人工智能 这也是公式这也是公式A A在在D D上的一个解释。从这个解释可以看出：上的一个解释。从这个解释可以看出：当当x=1x=1、y=1y=1时，有时，有P(x,y)P(x,y)的真值为的真值为T;T;当当x=2x=2、y=1y=1时，有时，有P(x,y)P(x,y)的真

24、值为的真值为F;F;同样同样 当当x=1x=1、y=2y=2时，有时，有P(x,y)P(x,y)的真值为的真值为T;T;当当x=2x=2、y=2y=2时，有时，有P(x,y)P(x,y)的真值为的真值为F;F;即对即对x x在在D D上的任意取值，不存在一个上的任意取值，不存在一个y y使使P(x,y)P(x,y)的真的真值为值为T T。因此，在此解释下公式。因此，在此解释下公式A A的真值为的真值为F F。实际上实际上,A,A在在D D上上共有共有1616种种(2(2的四次方的四次方,即即P(1,1),P(1,1),P(1,2),P(2,1),P(2,2)P(1,2),P(2,1),P(2,

25、2)每个均有每个均有T T、F F两种两种)解释。解释。28人工智能 例例3.3 3.3 设个体域设个体域D=1,2D=1,2，求公式，求公式A=(A=(x x)P(f(x),a)P(f(x),a)在在D D上上的解释，并指出在该解释下公式的解释，并指出在该解释下公式B B的真值。的真值。解：设个体常量解：设个体常量a a和函数和函数f(x)f(x)的真值指派为：的真值指派为：a f(1)f(2)1 1 229人工智能 对谓词的真值指派为对谓词的真值指派为 P(1,1)P(1,2)P(2,1)P(2,2)T T 当当x=1时，时，a=1使使P(1,1)=T 当当x=2时，时，a=1使使P(2,

26、1)=T即对即对x在在D上的任意上的任意取值，都存在取值，都存在a=1使使P(f(x),a)P(f(x),a)的真的真值为值为T。因此在此解释下公式。因此在此解释下公式B的真值为的真值为T。30人工智能 2.谓词公式的永真性与可满足性谓词公式的永真性与可满足性 下面定义谓词公式的永真性、永假性、可满足性下面定义谓词公式的永真性、永假性、可满足性与不可满足性。与不可满足性。定义定义3.2 如果谓词公式如果谓词公式P对非空个体域对非空个体域D上的任一解释上的任一解释都取得真值都取得真值T，则称，则称P在在D上是永真的；上是永真的；如果如果P在任何非在任何非空个体域空个体域D上均是上均是永真的，永真

27、的，则称则称P永真。永真。要判定一个谓词公式为要判定一个谓词公式为永真，永真，必须对每个非空个必须对每个非空个体域上的每个解释逐一判断。当解释个数无限时，其体域上的每个解释逐一判断。当解释个数无限时，其永真永真性就很难判定了。性就很难判定了。31人工智能 定义定义3.3 对于谓词公式对于谓词公式P，如果至少存在，如果至少存在D上的一个解释，上的一个解释，使公式使公式P在此解释下在此解释下的真的真值为值为T，则称公式，则称公式P在在D上是可上是可满足的。满足的。谓词公式的谓词公式的满足性也称为相容性。满足性也称为相容性。定义定义3.4 如果谓词公式如果谓词公式P对非空个体域对非空个体域D上的任一

28、解释都上的任一解释都取得真值取得真值F，则称，则称P在在D上是永假上是永假的；如果的；如果P在任何非空在任何非空个体域个体域D上均是上均是永永假的，则称假的，则称P永永假。假。谓词公式的谓词公式的永永假性也称为不可假性也称为不可满足性也称为不相容性。满足性也称为不相容性。32人工智能 3.谓词公式的等价性与永真蕴含性谓词公式的等价性与永真蕴含性 谓词公式的等价性和永真蕴含性可分别用相应的谓词公式的等价性和永真蕴含性可分别用相应的等价式和永真蕴含式来表示，这些等价式和永真蕴含等价式和永真蕴含式来表示，这些等价式和永真蕴含式都是演绎推理的主要依据，因此也称它们为推理规式都是演绎推理的主要依据，因此

29、也称它们为推理规则。则。(1).等价式等价式定义定义3.5 设设P与与Q是是D上上的两个谓词公式，若对的两个谓词公式，若对D上的任意上的任意解释，解释，P与与Q都有相同的真值，则称都有相同的真值，则称P与与Q在在D上上是等是等价的。如果价的。如果D是任意非空个体域，是任意非空个体域，则称则称P与与Q是等价的，是等价的，记作记作P Q。33人工智能 常用的等价公式：常用的等价公式：（1）双重否定率：）双重否定率：P P（2）交换率：）交换率：PQ QP,PQ QP（3）结合率：）结合率：（PQ）R P(Q R),(P Q)R P(Q R)（4）分配率：）分配率：P (Q R)(P Q)(P R)

30、,P(Q R)(P Q)(P R)（5）狄）狄.摩根定律：摩根定律：(P Q)P Q,(P Q)P Q（6）吸收率：）吸收率：P (P Q)P,P(P Q)P34人工智能（7）补余率：）补余率：PP T,P P F（8）连词化归率：）连词化归率：PQ P Q,PQ (P Q)(Q P)PQ (P Q)(Q P)（9）量词转换率：）量词转换率：(x)P (x)(P),(x)P (x)(P),（10）量词分配率：）量词分配率：(x)(P Q)(x)P (x)Q,(x)(P Q)(x)P (x)Q35人工智能(2).永真蕴含式永真蕴含式定义定义3.6 对谓词公式对谓词公式P和和Q，如果，如果P Q永

31、真，则称永真，则称P永真永真蕴含蕴含Q，且称，且称Q为为P的逻辑结论，的逻辑结论，P为为Q的逻辑的逻辑前提，前提，记作记作P Q。常用的永真蕴含式如下：常用的永真蕴含式如下：（1）化简式：）化简式：PQ P，P Q Q（2）附加式：）附加式：P P Q，Q P Q（3）析取三段论：）析取三段论：P，P Q Q 36人工智能（4）假言图理：）假言图理：P，P Q Q（5）抽取式：）抽取式：Q，PQ P（6）假言三段论：）假言三段论：P Q，Q R P R（7）二难推理：）二难推理：PQ，P R，Q R R（8）全称固化：）全称固化：(x)P(x)P(y)y是个体域是个体域中的任一个体，利用此中的

32、任一个体，利用此永真蕴含式可消去谓词公式中永真蕴含式可消去谓词公式中的全程量词。的全程量词。（9）存在固化：存在固化：(x)P(x)P(y)y是个体域是个体域中某一个可以使中某一个可以使P(x)为真的个体。利用此为真的个体。利用此永真蕴含式永真蕴含式可消去谓词公式中的存在量词。可消去谓词公式中的存在量词。37人工智能 4.谓词公式的范式谓词公式的范式 范式是公式的标准形式，公式往往需要变换为同它范式是公式的标准形式，公式往往需要变换为同它等价的范式，以便对它们做一般性的处理。在谓词公式等价的范式，以便对它们做一般性的处理。在谓词公式出现的情况可将谓词公式的范式分为两种：出现的情况可将谓词公式的

33、范式分为两种：(1).前束范式：前束范式：定义定义3.7 设设F为一谓词公式，如果其中的所有量词均非否定为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，而它们的下域为整个公式，则地出现在公式的最前面，而它们的下域为整个公式，则称称F为前述范式。一般地，前述范式可写为：为前述范式。一般地，前述范式可写为：（Q1x1)(Qnxn)M(x1,x2,xn)其中其中Qi（i=1,2,n)为前为前缀，它是一个由全程量词或存在量词组成的量词串；缀，它是一个由全程量词或存在量词组成的量词串；M(x1,x2,xn)为母式，它是一个不含任何量词的谓词公为母式，它是一个不含任何量词的谓词公式。式。38

34、人工智能 例如，例如，(x)(y)(z)(P(x)Q(y,z)R(x,z)是前束是前束范式范式 任一谓词公式均可化为与其对应的前述范式，其简化任一谓词公式均可化为与其对应的前述范式，其简化方法将在后面子句集的化简中讨论。方法将在后面子句集的化简中讨论。39人工智能(2).Skolem范式：范式：定义定义3.8 如果前束范式中所有的存在量词都在全称量词之前，如果前束范式中所有的存在量词都在全称量词之前，则称这种形式的谓词公式为则称这种形式的谓词公式为Skolem范式。范式。例如，例如，(x)(z)(y)(P(x)Q(y,z)R(x,z)是是Skolem范式范式 任一谓词公式均可化为与其对应的任一

35、谓词公式均可化为与其对应的Skolem范式，其范式，其简化方法将在后面子句集的化简中讨论。简化方法将在后面子句集的化简中讨论。40人工智能 5.置换与合一置换与合一 在不同谓词公式中，往往会出现谓词名相同但其在不同谓词公式中，往往会出现谓词名相同但其个体不同的情况，此时推理过程是不能直接进行匹配，个体不同的情况，此时推理过程是不能直接进行匹配，需要先进行置换。需要先进行置换。例如：可根据全称固化推理和假言推理由谓词公式例如：可根据全称固化推理和假言推理由谓词公式 W1(A)和和(x)(W1(x)W2(x)推出推出W2(A)。对谓词。对谓词W1(A)可看作可看作由全称固化推理由全称固化推理（即（

36、即(x)(W1(x)W2(x)）)推出的，推出的，其中其中A是任意是任意个体常量。个体常量。41人工智能(1).置换（置换（substitution）定义定义3.9 置换是形如置换是形如t1/x2,t2/x2,tn/xn的有限集合。其的有限集合。其中，中，t1,t2,tn是项；是项；x1,x2,xn是互不相同的变元；是互不相同的变元；ti/xi表示用表示用ti置换置换xi。并且要求。并且要求ti与与xi不能相同，不能相同，xi不能不能循环地出现在另一个循环地出现在另一个ti中。中。例如：例如：a/x,c/y,f(b)/z是一个置换是一个置换 g(y)/x,f(x)/y不是一个置换不是一个置换

37、g(a)/x,f(x)/y是一个置换是一个置换42人工智能 定义定义3.10 设设=(t1/a1,t2/a2,tn/an是一个是一个置换，置换，F是一个是一个谓词公式，把公式谓词公式，把公式F中的所有中的所有ai换成换成ti（I=1,2,n），），得到一个新的公式得到一个新的公式G，称，称G为为F在置换在置换下的例示，记作下的例示，记作G=F。一个谓词公式的任何示例都是该公式的逻辑结论。一个谓词公式的任何示例都是该公式的逻辑结论。43人工智能 定义定义3.11 设设=t1/a1,t2/a2,tn/an，=u1/y1,u2/y2,um/ym是两个是两个置换。则置换。则与与的合成的合成也是一个置换

38、，记作也是一个置换，记作.。它是从集合它是从集合 t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,um/ym 中删去以下两种元素中删去以下两种元素（1）当）当ti=xi时，删去时，删去ti/xi（i=1,2,n);（2）当当yi (x1,x2,xi)时，删去时，删去ui/yi（i=1,2,m)。最后剩下的新元素所构成的集合。最后剩下的新元素所构成的集合。44人工智能 例例3.4：设：设=f(y)/x,z/y,=a/x,b/y,y/z,求求与与的合的合成。成。解：先求出集合解：先求出集合发发f(b/y)/x,(y/z)/y,a/x,b/y,y/z=f(b)/x,y/y,a/x,b/y

39、,y/z其中，其中，f(b)/x中的中的f(b)是置换是置换作用于作用于f(y)的结果；的结果；y/y中的中的y是置换是置换作用于作用于z的结果。在该集合中，的结果。在该集合中，y/y满足定义中的条件（满足定义中的条件（1），需要删除；），需要删除；a/x,b/y满足定义中的条件（满足定义中的条件（2），需要删除。最后得：），需要删除。最后得：.=f(b)/x,y/z45人工智能(2).合一（合一（Unifier）合一可以简单地理解为寻找项对变量的置换，使两个谓合一可以简单地理解为寻找项对变量的置换，使两个谓词公式一致。词公式一致。定义定义3.12 设有公式集设有公式集F=F1,F2,Fn,若

40、存在一个置若存在一个置，可使，可使F1=F2=Fn,则称则称是是F的一个合一。称的一个合一。称F1,F2,Fn是是可以合一的。可以合一的。例如：是有公式集例如：是有公式集F=P(x,y,f(y),P(a,g(x),z),则则 =a/x,g(a)/y,f(g(a)/z是它的一个合一。是它的一个合一。46人工智能 一般来说，一个公式集的合一不是唯一的。一般来说，一个公式集的合一不是唯一的。定义定义3.13 设设是公式集是公式集F的一个合一，如果队的一个合一，如果队F的的任意个任意个合一合一 都存在一个置换都存在一个置换，使得，使得=.，则称，则称是一个最是一个最一般合一（一般合一（Most Gen

41、eral Unifier,简记简记MGU)。一个公式集的最一般合一是唯一的。一个公式集的最一般合一是唯一的。47人工智能(3).合一算法合一算法定义定义3.14 设设F=F1,F2,Fn是一个非空有限的公式集，是一个非空有限的公式集，从从F中每个公式的第一个中每个公式的第一个符号同时向右比较，知道发现符号同时向右比较，知道发现第一个不相同的符号为止，从第一个不相同的符号为止，从F的的各个公式中取出那些各个公式中取出那些以第一个不一致符号开始的最大子表达式，并以这些以第一个不一致符号开始的最大子表达式，并以这些子表达式为元素组成一个集合子表达式为元素组成一个集合D,则称则称D为为F的分歧集的分歧

42、集（Disagreement Set)。48人工智能 例例3.5：求：求F=P(x,y,z),P(x,f(a),h(b)的分歧集。的分歧集。解：这里解：这里F1=P(x,y,z),F1=P(x,f(a),h(b)，分别从，分别从F1和和F2的的第一个符号开始，逐个向后比较，会发现第一个符号开始，逐个向后比较，会发现F1 中的中的y与与F2中的中的f(a)不同，它们构成了一个分歧集：不同，它们构成了一个分歧集：D1=y,f(a)再继续向后比较，又会发现再继续向后比较，又会发现F1中的中的z与与F2中的中的h(b)不同，不同，它们又构成了一个分歧集：它们又构成了一个分歧集：D2=z,h(b)49人

43、工智能 合一算法：设合一算法：设F为非空有限公式集合，求为非空有限公式集合，求F的最一般合一的合的最一般合一的合一算法如下：一算法如下：（1）令）令k=0,Fk=F,k=(空置换空置换,即不含任何元素的置换即不含任何元素的置换)；（2）若）若Fk只含有一个表达式，则算法停止只含有一个表达式，则算法停止,k就是最一般合一；就是最一般合一；（3）找出找出Fk 的分歧集的分歧集 Dk;（4）若）若Dk 中存在元素中存在元素xk和和tk，其中，其中xk是变元，是变元，tk是项，是项，且且xk不在不在tk中出现，中出现，则置则置 k+1=k.tk/xk,Fk+1=Fk.tk/xk,k=k+1,然后转（然

44、后转（2）；）；（5）算法停止，）算法停止，F的的最一般合一不存在。最一般合一不存在。50人工智能 例例3.6：求公式集：求公式集F=P(a,x,f(g(y),P(z,h(z,u),f(u)的的最一最一般合一。般合一。解：根据上述解：根据上述合一算法，首先置合一算法，首先置 k=0:F0=F,0=F0不是单一表达式，有不是单一表达式，有D0=a,z,其中其中z为变元，且为变元，且z不在不在a中出现，从而中出现，从而 1=0.a/z F1=F0a/z=P(a,x,f(g(y),P(z,h(z,u),f(u)51人工智能 k=1:F1也不是单一表达式，有也不是单一表达式，有D1=x,h(a,u),

45、其中其中x为变元，从而为变元，从而 2=1.h(a,u)/x=a/z,h(a,u)/x F2=F1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)k=2:F2也不是单一表达式，有也不是单一表达式，有D2=g(y),u,其中其中u为变元，为变元，从而从而 3=2.g(y)/u=a/z,h(a,g(y)/x,g(y)/u52人工智能 F3=F2g(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:F3已不是单一表达式，因此已不是单一表达式，因此3=a/z,h(a,g(y)/x,

46、g(y)/u是是F的最一般合一。的最一般合一。53人工智能 从一组以知为真的事实出发，直接运用经典逻辑从一组以知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。中的推理规则推出结论的过程称为自然演绎推理。在这种推理中，最基本的推理规则是三段论推理，在这种推理中，最基本的推理规则是三段论推理，包括：假言推理、拒取式推理、假言三段论等。包括：假言推理、拒取式推理、假言三段论等。54人工智能 两类错误：两类错误：（1 1）肯定后件的错误：当）肯定后件的错误：当P P 为真时，希望通过肯定后件为真时，希望通过肯定后件Q Q为真来推出前件为真来推出前件P P为真，这是不允许的

47、。为真，这是不允许的。（2 2）否定前件的错误：当）否定前件的错误：当P P 为真时，希望通过否定前件为真时，希望通过否定前件P P来推出后件来推出后件Q Q为假，这也是不允许的。为假，这也是不允许的。55人工智能 例例3.7：设已知如下事实：设已知如下事实：A,B,A C,BCD,DQ求证：求证：Q为真为真证明：证明：A,AC C 假言推理假言推理 B,C BC 引入合取词引入合取词 BC,BCD D 假言推理假言推理 D,DQ Q 假言推理假言推理 所以所以Q为真。为真。56人工智能 例例3.8：设已知如下事实：设已知如下事实：（1）只要是编程序的课王成都喜欢。）只要是编程序的课王成都喜欢

48、。（2）所有的程序设计语言课都是需要编程序的课。）所有的程序设计语言课都是需要编程序的课。（3）C是一门程序设计语言课。是一门程序设计语言课。求证：王成喜欢求证：王成喜欢C这门课。这门课。57人工智能 证明：首先定义谓词证明：首先定义谓词 Prog(x)x是需要编程序的课。是需要编程序的课。Like(x,y)x喜欢喜欢y。Lang(x)x是一门程序设计语言课。是一门程序设计语言课。把上述已知事实及待求解问题用谓词公式表示把上述已知事实及待求解问题用谓词公式表示如下：如下：Prog(x)Like(Wang,x)(x)(Lang(x)Prog(x)58人工智能 应用推理规则进行推理：应用推理规则进

49、行推理：Lang(y)Prog(y)全称固化全称固化Lang(C),Lang(y)Prog(y)Prog(C)假言推理假言推理 Prog(C),Prog(x)Like(Wang,x)Like(Wang,C)假言推理假言推理 因此因此王成喜欢王成喜欢C这门课。这门课。59人工智能 1.子句集及其简化子句集及其简化(1).子句及子句集子句及子句集定义定义3.15 原子谓词公式及其否定统称为文字。原子谓词公式及其否定统称为文字。例如例如P(x)、Q(x)、P(x)、Q(x)等都是文字。等都是文字。定义定义3.16 任何文字的析取式称为子句。任何文字的析取式称为子句。例如例如P(x)Q(x)、P(x,

50、f(x)Q(x,g(x)都是子句。都是子句。定义定义3.17 不包含任何文字的子句称为空子句。一般记为不包含任何文字的子句称为空子句。一般记为或或NIL。定义定义3.18 由子句或空子句所构成的集合称为子句集。由子句或空子句所构成的集合称为子句集。60人工智能(2).子句集的化简子句集的化简化简步骤如下化简步骤如下：v 消去连接词消去连接词“”“”v 减少否定符号的辖域减少否定符号的辖域v 对变元标准化对变元标准化v 化为前束范式化为前束范式v 消去存在量词消去存在量词v 化为化为Skolem标准形标准形61人工智能 v 消去全称量词消去全称量词v 消去合取词消去合取词v 更换变元名称更换变元