人工智能基础及应用 课件 第2章 确定性推理

人工智能第2章确定性推理

国家级一流本科线上线下混合式课程“人工智能”人工智能第2章确定性推理

2.1

确定性推理与不确定推理确定性推理的基本内容*推理：是指从已知的事实出发，用已掌握的知识，推导出其中蕴含的

事实性结论或归纳出某些新结论的过程。---人工智能系统的推理过程实际上就是一种思维过程，即运用知识进行推理来求解问题的过程。依据知识的确定性

确定性推理不确定性推理确定性推理：就是指推理时所用的知识都是精确的，推出的结论也是确定的，其值或者为“真”或者为“假”没有第三种情况出现。

知识如何表示推理的依据是什么推理的过程又是怎样人工智能第2章确定性推理

2.2

谓词逻辑推理方法一阶谓词逻辑表示法谓词逻辑推理方法求解问题的一般步骤谓词逻辑推理方法的应用举例主要内容一阶谓词逻辑表示法命题逻辑命题：能够分辨真假的语句称为命题。原子命题：一个语句如果不能再进一步分解成更简单的语句，并且又

是一个命题，则称此命题为原子命题。原子命题是命题中的基本单位，一般用大写的P、Q、R、S…等表示。若命题的意义为真，称它的真值为真，记为T。若命题的意义为假，称它的真值为假，记为F。一个命题可在一种条件下为真，在另一种条件下为假。*谓词公式：就是用谓词联接符号将一些谓词联接起来所形成的公式。3<5

太阳从西边升起

1＋1＝2命题逻辑：研究命题及命题之间关系的符号逻辑系统。命题逻辑表示法的局限性：无法把它所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。P：李白是诗人Q：杜甫也是诗人R:老李是小李的父亲一阶谓词逻辑表示法谓词逻辑原子命题分为谓词和个体两部分。*谓词公式：就是用谓词联接符号将一些谓词联接起来所形成的公式。用于刻画个体的性质、状态或个体间的关系可以独立存在的物体，可以是抽象的、也可以是具体的

例如：李白是诗人PoetLiBai谓词表示Poet(LiBai)5>3X<6Greater(5,3)Less(x,6)谓词的一般形式为：

P(x1,x2,…,xn)个体谓词名谓词的元数例如：P(x),Q(x,y),R(x,y,z)个体域连接词有:（1）﹁：“否定”（negation）或“非”。（2）∨：“析取”（disjunction）——或。（3）∧：“合取”（conjunction）——与。（4）→：“蕴含”(implication)或“条件”(condition)。（5）

：“等价”（equivalence）或“双条件”（bicondition）。一阶谓词逻辑表示法对应的真值表为:连接词的优先级别从高到低排列：﹁，∧，∨，→，量词有:（1）全称量词（universalquantifier)：“对个体域中的所有（或任一个）个体x”。

（2）

存在量词（existentialquantifier)：“在个体域中存在个体x”。

一阶谓词逻辑表示法例如:可按下面的规则得到谓词公式：

一阶谓词逻辑表示法(4)若A是谓词公式，则

A，

A也是谓词公式。(1)单个谓词是谓词公式，称为原子谓词公式。(2)若A是谓词公式，则﹁A也是谓词公式。

(3)若A，B都是谓词公式，则A∧B，A∨B，A→B，A

B也都是谓词公式。有限步应用（1）－（4）生成的公式也是谓词公式。怎样应用谓词公式来表示知识呢？11一阶谓词逻辑表示法

*一般步骤：

首先定义谓词及个体，确定每个谓词及个体的确切含义。然后依据所要表达的事物或概念，为每个谓词中的变元赋予特定的值。最后根据所要表达的知识的语义，用适当的连接符号将各个谓词连接起来，形成谓词公式。例如：李是一名计算机系的学生，但他不喜欢编程序。解：按照知识表示的步骤，用谓词公式表示上述知识。首先：定义谓词如下：

COMPUTER(X)：x是计算机系的学生。LIKE(x,y)：x喜欢y。

涉及的个体有：

李(Li)，编程序(programming)然后：将这些个体代入到谓词中，得到

COMPUTER(Li)，~LIKE(Li,programming)最后：根据语义用连接词将它们连接起来，就

得到上述知识的谓词公式：

COMPUTER(Li)∧~LIKE(Li,programming)

案例分析系列谓词逻辑推理方法之机器人搬弄盒子问题

用谓词逻辑推理方法进行问题求解—案例机器人搬弄盒子问题：在房间的c处有一个机器人，在a和b处各有一张桌子，a桌子上有一个盒子，如图所示（初始状态）。现需要机器人将a桌子上的盒子移到b桌子上，然后回到c处，如图所示（目标状态）。初始状态目标状态如何用一阶谓词逻辑来表示这一问题，并对其进行求解呢？

acbacb用谓词逻辑推理方法进行问题求解—案例初始状态目标状态acbacb解：先定义谓词和确定个体：则定义谓词如下：TABLE(x)：x是桌子；EMPTY(y)：y手中是空的；AT(y,z)：y在z附近；HOLDS(y,w)：y拿起w；ON(w,x)：w在x上面。对应的个体分别为：

x：{a，b}；y：{robot}；z：{a，b，c}；w：{box}。AT(rabot,c)∧EMPTY(rabot)∧ON(box,a)∧TABLE(a)∧TABLE(b)AT(rabot,c)∧EMPTY(rabot)∧ON(box,b)∧TABLE(a)∧TABLE(b)用谓词逻辑推理方法进行问题求解—案例acb用谓词逻辑推理方法进行问题求解—案例acbGOTO(x,y)：从x处走到y处条件：AT(robot,x)动作：删除：AT(robot,x)

增加：AT(robot,y)PICK-UP(x)：在x处拿起盒子(box)条件：TABLE(x)∧ON(box,x)

∧AT(robot,x)∧EMPTY(robot)动作：删除：ON(box,x)∧EMPTY(robot)

增加：HOLDS(robot,box)SET-DOWN(x)：在x处放下盒子条件：TABLE(x)∧AT(robot,x)

∧HOLDS(robot,box)动作：删除：HOLDS(robot,box)

增加：ON(box,x)∧EMPTY(robot)用谓词逻辑推理方法进行问题求解—案例机器人搬弄盒子问题的具体过程：初始状态acb目标状态acbAT(rabot,c)∧EMPTY(rabot)∧ON(box,a)∧TABLE(a)∧TABLE(b)AT(rabot,a)∧EMPTY(rabot)∧ON(box,a)∧TABLE(a)∧TABLE(b)GOTO(c,a)GOTO(x,y)用c替换x，a替换yAT(rabot,a)∧HOLDS(robot,box)∧TABLE(a)∧TABLE(b)PICK-UP(x)用a代换xPICK-UP(a)AT(rabort,b)∧HOLDS(robort,box)∧TABLE(a)∧TABLE(b)AT(rabort,b)∧ON(box,b)∧EMPTY(robort)∧TABLE(a)∧TABLE(b)AT(rabort,c)

∧ON(box,b)∧EMPTY(rabort)∧TABLE(a)∧TABLE(b)GOTO(x,y)用a替换x，b替换yGOTO(x,y)GOTO(a,b)SET-DOWN(x)用b代换xGOTO(x,y)用b替换x，c替换yGOTO(b,c)SET-DOWN(b)一阶谓词逻辑表示法具有如下特点

自然性：其形式接近于自然语言，易于被人理解和接受。精确性：谓词公式非真即假，能够精确的表示知识，进行确定性推理。严密性：谓词逻辑具有严格的形式定义与推理规则。易实现：易于转换为计算机的内部形式，易于模块化。不足之处：不能表示不精确、不确定、模糊性的知识。作业：

总结课后请大家思考，在机器人搬积木的问题中，当某一状态可同时满足多个操作的条件时，应选用哪一个操作？在进行变量代换时，如果存在多种代换的可能性，如何确定用哪一个？课堂练习用谓词表示法求解农夫、狼、山羊、白菜问题。农夫、狼、山羊、白菜全部放在一条河的左岸，现在要把他们全部送到河的右岸去，农夫有一条船，过河时，除农夫外船上至多能载狼、山羊、白菜中的一种。狼要吃山羊，山羊要吃白菜，除非农夫在那里。似规划出一个确保全部安全过河的计划。请写出所用谓词的定义，并给出每个谓词的功能及变量的个体域。

人工智能第2章确定性推理

2.3

自然演绎推理方法自然演绎推理方法的基本内容自然演绎推理方法的推理规则自然演绎推理方法的应用举例主要内容自然演绎推理的基本内容*按照推理的逻辑基础推理分为：演绎推理、归纳推理和默认推理。演绎推理：就是从已知的一般知识出发，推理出适合于某种个别情况的结论的过程，是一种由一般到个别的推理方法。最常用的演绎推理形式是三段论式，包括：

大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；例如：有如下三个判断：

①

计算机系的学生都会编程序；

（一般性知识）

②

程强是计算机系的一位学生；

（具体情况）

③

程强会编程序。

（结论）结论是由大前提推出的，并且适合于小前提的判断。

自然演绎推理的基本内容自然演绎推理：就是从一组已知为真的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程。

谓词公式的永真性、可满足性、等价性和永真蕴涵

谓词公式的永真性：如果谓词公式P，对于个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P永真。

谓词公式的永假性：如果谓词公式P，对于个体域D上的任何一个解释都取得真值F，则称P在D上是永假的；如果P在每个非空个体域上均永假，则称P永假。谓词公式的可满足性：对于谓词公式P，如果至少存在一个解释使得公式P在此解释下的真值为T，则称公式P是可满足的。谓词公式的不可满足性：对于谓词公式P，如果不存在任何解释，使得公式P的真值为T，则称公式P是不可满足的。等价的自然演绎推理的基本内容谓词公式的永真性、可满足性、等价性和永真蕴涵

谓词公式的等价性：设Ｐ和Ｑ是两个谓词公式，Ｄ是它们公共的个体域。若对Ｄ上的任何一个解释，Ｐ与Ｑ的取值都相同，则称公式Ｐ和Ｑ在域Ｄ上式等价的。如果Ｄ是任意个体域，则称Ｐ和Ｑ是等价的，记为。谓词公式的永真蕴涵：对于谓词公式P和Q，如果永真，则称P永真蕴涵Q，且称Q为P的逻辑结论，称P为Q的前提，记为。常用等价式常用蕴涵式交换律结合律吸收律补余律逆否律

推理规则化简式附加式拒取式

自然演绎推理的推理规则常用等价式常用蕴涵式交换律结合律吸收律补余律逆否律

推理规则化简式附加式拒取式

案例分析系列自然演绎推理之问题证明

用自然演绎推理进行问题证明—案例例1:设已知如下事实：

A,B,A→C,B∧C→D,D→Q

求证：Q为真。证明：因为

A,A→C⇒C

假言推理及P规则

B,C⇒B∧C

引入合取词

B∧C，B∧C→D⇒D

假言推理及T规则

D,D→Q⇒Q

假言推理及T规则

因此，Q为真。用自然演绎推理进行问题证明—案例例2:设已知如下事实：(1)只要是需要室外活动的课，郝亮（Hao）都喜欢。(2)所有的公共体育课都是需要室外活动的课。(3)篮球（Ball）是一门公共体育课课。求证：郝亮喜欢篮球这门课。Outdoor(x)

x是需要室外活动的课。Like(x,y)x喜欢y。Sport(x)x是一门公共体育课证明：①依据已知事实定义如下谓词：②把已知事实及待求解问题用谓词公式表示如下：(1)Outdoor(x)→Like(Hao,x)(2)(∀x)(Sport(x)→Outdoor(x))(3)Sport(Ball)待求解的问题：Like(Hao,Ball)③应用推理规则进行推理：因为有(∀x)(Sport(x)→Outdoor(x))所以

Sport(y)→Outdoor(y)全称固化又Sport(Ball)，Sport(y)→Outdoor(y)⇒Outdoor(Ball)假言推理{Ball/y}又Outdoor(Ball),Outdoor(x)→Like(Hao,x)⇒Like(Hao,Ball)假言推理

{Ball/x}所以原题得证：郝亮喜欢篮球这门课。主要优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。

主要缺点：容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。

总结

所谓肯定后件的错误是指：当为真时，希望通过肯定后件Q为真来推出前件P为真。这是错误的推理逻辑，请问为什么？

所谓否定前件的错误是指：当为真时，希望通过否定前件P来推出后件Q为假，这也是不允许的，请问为什么？人工智能第2章确定性推理

2.4

归结演绎推理方法子句与子句集的基本概念归结原理的基本内容应用归结原理进行定理证明与问题求解

主要内容定理证明的实质*证明P→Q永真*应用反证法即证明﹁(P→Q)是永假的，也就是不可满足的。﹁(﹁P∨Q)所以，只要能够证明P∧﹁Q是不可满足的就可以了。P∧﹁Q

等价变换﹁(P→Q)那么，如何证明P∧﹁Q是不可满足的呢？子句与子句集定义1不含有任何连接词的谓词公式叫原子公式，简称原子。例如，P(x)、Q(x)、﹁P(x)、﹁Q(x)等都是文字。定义2原子或原子的否定统称为文字。定义3子句就是由一些文字组成的析取式。定义4不含任何文字的子句称为空子句。定义5由子句或空子句所构成的集合称为子句集。例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句。例如，{P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))，NIL}就是一个子句集。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，是不可满足的。空子句可表示为NIL.谓词公式到子句集的转换如果将谓词公式G的Skolem标准型前面的全称量词全部消去，并用逗号，代替合取符号∧，便可得到谓词公式G的子句集S。例如，有谓词公式G=(∀x)((∀y)P(x,y)→﹁(∀y)(Q(x,y)→R(x,y)))依据等价变化和谓词公式化为Skolem标准型的步骤有：

(∀x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x))))化为合取范式(∀x)((∀y)P(x,y)→﹁(∀y)(Q(x,y)→R(x,y)))(∀x)(﹁(∀y)P(x,y)∨﹁(∀y)(﹁Q(x,y)∨R(x,y)))消去蕴涵(∀x)((∃y)﹁P(x，y)∨(∃y)(Q(x，y)∧﹁R(x，y)))减少否定符号的辖域

(∀x)((∃y)﹁P(x，y)∨(∃z)(Q(x，z)∧﹁R(x，z)))变元重新命名，使所有变元的名字均不相同(∀x)(∃y)(∃z)(﹁P(x，y)∨(Q(x，z)∧﹁R(x，z)))量词前移(∀x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))应用Skolem函数消去存在量词则谓词公式G的子句集S为：S={(﹁P(x,f(x))∨Q(x,g(x))，(﹁P(x,f(x))∨﹁R(x,g(x)))}Skolem标准型

Robinson的归结原理定理1设有谓词公式G，而其相应的子句集为S，则G是不可满足的充分必要条件是S是不可满足的。

子句集中各子句之间是合取的关系，因此，其中只要有一个子句是不可满足的，则子句集就是不可满足的。

空子句是不可满足的。所以，只要子句集中包含一个空子句，则此子句集一定是不可满足的。

基本思想检查子句集S中是否有空子句，若有，则表明S是不可满足的；若没有，就在子句集中选择合适的子句对其进行归结推理，如果能推出空子句，就说明子句集是不可满足的。1965年，Robinson鲁滨逊提出了一种证明子句集不可满足性的方法，称为归结原理。

命题逻辑中的归结原理定义6若P是原子谓词公式或原子命题，即为文字，则称

P与﹁P为互补文字。例：

设C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的归结式C12。定义7归结与归结式：设C1和C2是子句集中的任意两个子句，

如果C1中的文字L1与C2中的文字L2互补，那么可从C1

和C2中分别消去L1和L2，并将C1和C2中余下的部分按

析取关系构成一个新的子句C12，则称这一过程为归结，

称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。解：这里L1=P，L2=﹁P，通过归结可以得到C12=Q∨R∨S命题逻辑中的归结原理例：设C1=﹁P∨Q，C2=﹁Q，C3=P，求C1、C2、C3的归结式C123。解：若先对C1、C2归结，可得到C12=﹁P

然后再对C12和C3归结，得到C123=NIL如果改变归结顺序，同样可以得到相同的结果，即其归结过程是不唯一的。其归结过程可用右图来表示，该树称为归结树。命题逻辑中的归结原理定理2归结式C12是其亲本子句C1和C2的逻辑结论。推论1：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若用C12代替C1和C2后得到新的子句集S1，则由S1的不可满足性可以推出原子句集S的不可满足性。即：S1的不可满足性⇒S的不可满足性推论2：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若把C12加入S中得到新的子句集S2，则S与S2的不可满足性是等价的。即：S2的不可满足性⇔S的不可满足性证明：设C1=L∨C1’，C2=﹁L∨C2’关于解释I为真，则只需证C12=C1’∨C2'

关于解释I也为真。

对于解释I，L和﹁L中必有一个为假。

若L为假，则必有C1'为真，不然就会使C1为假，这将与前提假设

C1为真矛盾，因此只能有C1'为真

同理，若﹁L为假，则必有C2'为真。

因此，必有C12=C1'∨C2'关于解释I也为真。即C12是C1和C2的逻辑结论。定理3子句集S是不可满足的，当且仅当存在一个从S到

空子句的归结过程。谓词逻辑中的归结原理定义8设C1和C2是两个没有公共变元的子句，L1和L2分别是

C1和C2中的文字。如果L1和L2存在最一般合一σ，则称

C12=({C1σ}-{L1σ})∪({C2σ}-{L2σ})

为C1和C2的二元归结式，而L1和L2为归结式上的文字。例：设C1=P(x)∨Q(a)，C2=﹁P(b)∨R(x)，求C12解：由于C1和C2有相同的变元x，不符合定义的要求。为了进行归结，需要修改C2中变元的名字，令C2=﹁P(b)∨R(y)。此时L1=P(x),L2=﹁P(b)，L1和L2的最一般合一是σ={b/x}。则有C12=({C1σ}-{L1σ})∪({C2σ}-{L2σ})=({P(b),Q(a)}-{P(b)})∪({﹁P(b),R(y)}-{﹁P(b)})=({Q(a)})∪({R(y)})={Q(a),R(y)}=Q(a)∨R(y)归结演绎推理方法*归结原理指出了证明子句集不可满足的方法*对于定理证明，即要证明谓词公式G=P→Q永真应用归结原理，只需证明P∧﹁Q所对应的子句集是不可满足的也就是通过归结，归结出一个空子句

应用反证法，即证明﹁(P→Q)是永假的，也就是不可满足的。欲证明﹁(P→Q)是不可满足的，只需证明P∧﹁Q是不可满足的

案例分析系列归结演绎推理之定理证明与问题求解

用归结演绎推理进行问题证明—步骤定理证明：通过上面的学习，应用归结原理进行定理证明的步骤

可归纳如下：设要被证明的定理可用谓词公式表示为：G=P→Q①否定结论Q，得﹁Q;②把﹁Q并入到公式集P中，得到G=P∧﹁Q；③把{G=P∧﹁Q}化为其对应的子句集S。④应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式并入S中。如此反复进行，若出现空子句，则停止归结，此时就证明了G为真。用归结演绎推理进行定理证明—案例例:已知：P=(∀x)((∃y)(A(x,y)∧B(y))→(∃y)(C(y)∧D(x,y)))Q=﹁(∃x)C(x)→(∀x)(∀y)(A(x,y)→﹁B(y))

证明:Q是P的逻辑结论，即证明P→Q永真。{(∀x)((∃y)(A(x,y)∧B(y))→(∃y)(C(y)∧D(x,y)))∧﹁(﹁(∃x)C(x)→(∀x)(∀y)(A(x,y)→﹁B(y)))}证明：①依据证明步骤：先把Q否定，并入

到公式集P中，得到G=P∧﹁Q如下：②再把G=P∧﹁Q化为其对应的子句集，得到如下5个子句：(1)﹁A(x,y)∨﹁B(y)∨C(f(x))(2)﹁A(u,v)∨﹁B(v)∨D(u,f(u))(3)﹁C(z)(4)A(m,n)(5)B(k)③最后应用谓词逻辑的归结原理对上述子句集进行归结，其过程为：由(1)和(3)归结，取置换：σ={f(x)/z}得：(6)﹁A(x,y)∨﹁B(y)由(4)和(6)归结，取置换：σ={m/x,n/y}得：(7)﹁B(n)由(5)和(7)归结，取置换：σ={n/k}得：(8)NIL因此，Q是P的逻辑结论。例:“快乐学生”问题假设：①任何通过计算机考试并获奖的人都是快乐的，

②任何肯学习或幸运的人都可以通过所有考试，

③张不肯学习但他是幸运的，

④任何幸运的人都能获奖。求证：张是快乐的。Pass(x,y)x可以通过y考试Win(x,prize)x能获得奖励Study(x)x肯学习Happy(x)x是快乐的Lucky(x)x是幸运的

解：①

对其进行求解时，先定义谓词：②再将问题用谓词表示如下：①(∀x)(Pass(x,computer)∧Win(x,prize)→Happy(x))②(∀x)(∀y)(Study(x)∨Lucky(x)→Pass(x,y))③﹁Study(zhang)∧Lucky(zhang)④(∀x)(Lucky(x)→Win(x,prize))

结论“张是快乐的”的否定

﹁Happy(zhang)③接下来按照推理步骤，将上述谓词公式转化为子句集如下：﹁Pass(x,computer)∨

﹁Win(x,prize)∨Happy(x)(2)﹁Study(y)∨Pass(y,z)(3)﹁Lucky(u)∨Pass(u,v)(4)﹁Study(zhang)(5)Lucky(zhang)(6)﹁Lucky(w)∨Win(w,prize)(7)﹁Happy(zhang)(结论的否定)用归结演绎推理进行问题求解—步骤问题求解：应用归结原理进行问题求解的步骤可归纳如下：①把已知前提用谓词公式表示出来，并且化为相应的子句集S；②把待求解的问题也用谓词公式表示出来，然后把它的否定式与谓词ANSWER构成一个析取式，ANSWER是一个为了求解问题而专设的谓词，其变元数量和变元名必须与问题公式的变元完全一致；③把此析取式化为子句集，并且把该子句集并入