1、Artificial Intelligence (AI)人工智能人工智能第二章：知识第二章：知识表示与推理表示与推理内容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.消解演绎推理消解演绎推理5.5.基于规则的演绎推理基于规则的演绎推理基于规则的演绎推理v在消解演绎推理中，需要把谓词公式化为子句形，这在消解演绎推理中，需要把谓词公式化为子句形，这使得原来蕴含在谓词公式中的一些重要信息却会在求使得原来蕴含在谓词公式中的一些重要信息却会在求取子句形的过程中被丢失。取子句形的过程中被丢失。v在不少情况下人们多希望使用接近于问题原始描述的在不少情
2、况下人们多希望使用接近于问题原始描述的形式来进行求解，而不希望把问题描述化为子句集。形式来进行求解，而不希望把问题描述化为子句集。又称为与又称为与/ /或形演绎推理，不或形演绎推理，不再把有关知识转化为子句集，而是把领域知识及已知再把有关知识转化为子句集，而是把领域知识及已知事实分别用事实分别用蕴含式蕴含式及及与与/ /或形或形表示出来，然后通过表示出来，然后通过运运用蕴含式用蕴含式进行演绎推理，从而证明某个目标公式。进行演绎推理，从而证明某个目标公式。基于规则的演绎推理v规则规则是一种比较接近于人们习惯的问题描述方式，用是一种比较接近于人们习惯的问题描述方式，用蕴含式（蕴含式（“If The
3、n”规则）按照这种问题描述方式进规则）按照这种问题描述方式进行求解的系统称为行求解的系统称为基于规则的系统基于规则的系统，或者叫做，或者叫做规则演规则演绎系统绎系统。规则正向演绎系统规则正向演绎系统规则逆向演绎系统规则逆向演绎系统规则双向演绎系统规则双向演绎系统基于规则的演绎推理规则正向演绎系统规则正向演绎系统规则逆向演绎系统规则逆向演绎系统规则双向演绎系统规则双向演绎系统规则正向演绎系统v 规则正向演绎系统是从已知事实出发，正向使用规则（蕴规则正向演绎系统是从已知事实出发，正向使用规则（蕴含式）直接进行演绎，直至到达目标为止。含式）直接进行演绎，直至到达目标为止。v 在规则正向演绎系统中，对
4、已知在规则正向演绎系统中，对已知事实事实和和规则规则都有一定的要都有一定的要求，如果不是所要求的形式，需要进行变换。求，如果不是所要求的形式，需要进行变换。在基于规则的正向演绎系统中，把在基于规则的正向演绎系统中，把事实事实表示为表示为非蕴含非蕴含形式形式的的与或形与或形，作为系统的总数据库，作为系统的总数据库把一个公式化为与或形的步骤与化为子句集类似，把一个公式化为与或形的步骤与化为子句集类似，只只是不必把公式化为子句的合取形式，也不能消去公式是不必把公式化为子句的合取形式，也不能消去公式中的合取。中的合取。规则正向演绎系统(1) 利用利用 “PQPQ”，消去蕴含符号；，消去蕴含符号； (2
5、) 利用狄利用狄.摩根定律及量词转换率把摩根定律及量词转换率把“”移到紧靠谓移到紧靠谓词的位置，直到否定符号的辖域最多只含一个谓词为词的位置，直到否定符号的辖域最多只含一个谓词为止；止；(3)重新命名变元，使重新命名变元，使不同量词约束的变元有不同的名不同量词约束的变元有不同的名字字；(4)对存在量词量化的变量用对存在量词量化的变量用skolem函数代替；函数代替；(5) 消去全称量词，且消去全称量词，且使各主要使各主要合取式合取式中的变元具有不中的变元具有不同的变量名同的变量名。规则正向演绎系统有如下表达式有如下表达式 (x) (y)(Q(y, x)(R(y)P(y)S(x, y)可把它转化
6、为：可把它转化为： Q(z, a)( ( R(y)P(y) )S(a, y) )这就是这就是与与/或形表示或形表示。事实表达式的事实表达式的与与/或形或形可用一棵可用一棵与与/或图或图表示出表示出来。来。规则正向演绎系统vQ(z, a)(R(y)P(y)S(a, y)的与的与/或图表示或图表示如下：如下： Q(z, a)(R(y)P(y)S(a, y)Q(z, a)(R(y)P(y)S(a, y)R(y)P(y) S(a, y)R(y)P(y)规则正向演绎系统当某表达式为当某表达式为k个子表达式的析取：个子表达式的析取：E1E2Ek，其中每个子表达式其中每个子表达式Ei均被表示为均被表示为E1
7、E2Ek的的后继后继节点节点，并由一个，并由一个k线连接符线连接符（即图中的半圆弧）将这些（即图中的半圆弧）将这些后继节点都连接到其父节点，即后继节点都连接到其父节点，即表示成与的关系表示成与的关系。当某表达式为当某表达式为k个子表达式的合取：个子表达式的合取：E1E2Ek，其中的每个子表达式其中的每个子表达式Ei均被表示为均被表示为E1E2Ek的一的一个单一的后继节点，无需用连接符连接，即个单一的后继节点，无需用连接符连接，即表示成或表示成或的关系的关系。这样，与这样，与/或图的或图的根节点根节点就是整个事实表达式，就是整个事实表达式，叶节点叶节点均为事实表达式中的一个均为事实表达式中的一个
8、文字文字。规则正向演绎系统有了与有了与/或图的表示，就可以求出其或图的表示，就可以求出其解树（结束于文字解树（结束于文字节点上的子树）集节点上的子树）集。可以发现，事实表达式的子句集。可以发现，事实表达式的子句集与解树集之间存在着一一对应关系，即与解树集之间存在着一一对应关系，即解树集中的每解树集中的每个解树都对应着子句集中的一个子句个解树都对应着子句集中的一个子句。解树集中每个解树的端节点上的文字的析取就是子句解树集中每个解树的端节点上的文字的析取就是子句集中的一个子句。集中的一个子句。上图所示的与上图所示的与/或图有或图有3个解树，分别对应这以下个解树，分别对应这以下3个子句：个子句： Q
9、(z, a) R(y) S(a, y) P(y) S(a, y)规则正向演绎系统可以把与可以把与/或图看作是对子句集的简洁表示。或图看作是对子句集的简洁表示。不过，不过，表达式的与表达式的与/或图表示要比子句集表示的通用性或图表示要比子句集表示的通用性差一些，原因是与差一些，原因是与/或图中的合取元没有进一步展开，或图中的合取元没有进一步展开，因此因此不能象在子句形中那样对某些变量进行改名不能象在子句形中那样对某些变量进行改名，这，这就就限制了与限制了与/或图表示的灵活性或图表示的灵活性。上面的最后一个子句上面的最后一个子句“P(y) S(a, y)”：在：在子句集中，其变量子句集中，其变量y
10、可全部改名为可全部改名为x，但却无法在与，但却无法在与/或或图中加以表示，因而失去了通用性，并且可能带来一图中加以表示，因而失去了通用性，并且可能带来一些困难。些困难。规则正向演绎系统还需要指出，这里的与还需要指出，这里的与/或图是作为综合数据库的一种或图是作为综合数据库的一种表示，其中的表示，其中的变量受全称量词的约束变量受全称量词的约束。在第二章问题归约表示中所描述的在第二章问题归约表示中所描述的与与/或图表示方法或图表示方法与与这里这里与与/或形的与或形的与/或图表示或图表示有着有着不同的目的和含义不同的目的和含义，因，因此应用时应加以区分。此应用时应加以区分。 规则正向演绎系统为简化演
11、绎过程，通常要求规则具有如下形式：为简化演绎过程，通常要求规则具有如下形式： LW其中，其中，L为为单文字单文字，W为为与与/或形公式或形公式。假定出现在蕴含式中的任何变量全都受假定出现在蕴含式中的任何变量全都受全称量词的约全称量词的约束束，并且这些变量已经被换名，使得他们，并且这些变量已经被换名，使得他们与事实公式与事实公式和其他规则中的变量不同和其他规则中的变量不同。如果领域知识的规则表示形式与上述要求不同，则应如果领域知识的规则表示形式与上述要求不同，则应将它转换成要求的形式。将它转换成要求的形式。规则正向演绎系统(1) 暂时消去蕴含符号暂时消去蕴含符号“”。设有如下公式：。设有如下公式
12、： (x)(y) ( z)P(x, y,z)(u)Q(x, u) 运用等价关系运用等价关系“PQPQ”，可将上式变为：，可将上式变为： (x)( y) (z)P(x, y,z)(u)Q(x, u)(2) 把否定符号把否定符号“”移到紧靠谓词的位置上，使其作用移到紧靠谓词的位置上，使其作用域仅限于单个谓词。通过使用狄域仅限于单个谓词。通过使用狄.摩根定律及量词转换摩根定律及量词转换率可把上式转换为：率可把上式转换为： ( x)( (y) (z)P(x, y,z) (u)Q(x, u)规则正向演绎系统(3) 引入引入Skolem函数，消去存在量词。消去存在量词后，函数，消去存在量词。消去存在量词后
13、，上式可变为：上式可变为： ( x)( (y) (P(x, y,f(x,y)(u)Q(x, u)(4)把所有全称量词移至前面化成前束式，消去全部全把所有全称量词移至前面化成前束式，消去全部全称量词。消去全称量词后，上式变为：称量词。消去全称量词后，上式变为： P(x, y,f(x,y)Q(x, u) 此公式中的变元都被视为受全称量词约束的变元。此公式中的变元都被视为受全称量词约束的变元。(5) 恢复蕴含式表示。利用等价关系恢复蕴含式表示。利用等价关系“PQPQ”将上式变为：将上式变为： P(x, y,f(x,y)Q(x, u)规则正向演绎系统在上述对规则的要求中，在上述对规则的要求中，之所以限
14、制其前件为单文字，之所以限制其前件为单文字，是因为是因为在进行正向演绎推理时要用规则作用于表示事在进行正向演绎推理时要用规则作用于表示事实的与实的与/或树，而该与或树，而该与/或树的叶节点都是单文字，这样或树的叶节点都是单文字，这样就可用规则的前件与叶节点进行简单匹配。就可用规则的前件与叶节点进行简单匹配。对非单文字情况，若形式为对非单文字情况，若形式为L1L2W，则可将其转，则可将其转换成与之等价的两个规则换成与之等价的两个规则L1W与与 L2W进行处理。进行处理。与与/或树正向演绎系统要求目标公式用或树正向演绎系统要求目标公式用子句形子句形表示。表示。如果目标公式不是子句形，则需要化成子句
15、形。如果目标公式不是子句形，则需要化成子句形。规则正向演绎系统规则正向演绎推理过程是从已知事实出发，不断运用规则正向演绎推理过程是从已知事实出发，不断运用规则，推出欲证明目标公式的过程。规则，推出欲证明目标公式的过程。先用与先用与/或树把已知事实表示出来，然后再用规则的前或树把已知事实表示出来，然后再用规则的前件和与件和与/或树的或树的叶节点进行匹配叶节点进行匹配，并通过一个匹配弧把，并通过一个匹配弧把匹配成功的规则加入到与匹配成功的规则加入到与/或树中，依此使用规则，直或树中，依此使用规则，直到产生一个含有到产生一个含有以目标节点为终止节点以目标节点为终止节点的解树为止。的解树为止。下面分下
16、面分命题逻辑命题逻辑和和谓词逻辑谓词逻辑两种情况来讨论规则正向两种情况来讨论规则正向演绎过程。演绎过程。规则正向演绎系统已知事实：已知事实：AB规则：规则： r1: ACD r2: BEG目标公式：目标公式：CG证明：证明：1）先将已知事实用与）先将已知事实用与/或树表示出来；或树表示出来；2）然后）然后再用匹配弧把再用匹配弧把r1和和r2分别连接到事实与分别连接到事实与/或树中与或树中与r1和和r2 的前件匹配的两个不同端节点；的前件匹配的两个不同端节点；3 ) 由于出现了由于出现了以目以目标节点为终节点的解树标节点为终节点的解树，故推理过程结束。这一证明，故推理过程结束。这一证明过程可用下
17、图表示。过程可用下图表示。规则正向演绎系统在该图中，双箭头表示匹配弧，它相当于一个单线连在该图中，双箭头表示匹配弧，它相当于一个单线连接符。接符。 C GCDEGA B A BAB目标目标匹配匹配匹配匹配规则规则已知事实已知事实r1r2规则正向演绎系统已知事实的与已知事实的与/或形表示：或形表示：P(x, y)(Q(x)R(v, y)规则：规则： P(u, v)(S(u)N(v) 目标公式：目标公式： S(a)N(b)Q(c)证明：证明：p在谓词逻辑情况下，由于事实、规则及目标中均含在谓词逻辑情况下，由于事实、规则及目标中均含有有变元变元，因此，其规则演绎过程还，因此，其规则演绎过程还需要用最一般合需要用最一般合一对变进行置换一对变进行置换。p证明过程可用下图表示。证明过程可用下图表示。规则正向演绎系统S(a)N(b)Q(c)S(u)N(v)P(u, v)P(x, y)Q(x)R(v, y)Q(x)R(v, y)P(x, y)(Q(x)R(v, y)a/ub/vc/xu/x,v/y目标公式：目标公式： S(a)N(b)Q(c)
