人工智能第三章

人工智能第三章第一页，共八十页，编辑于2023年，星期六3.1.1命题命题：能判断真假（不是既真又假）的陈述句。 简单陈述句描述事实、事物的状态、关系等性质。例如：1．

1+1=22．

雪是黑色的。3．

北京是中国的首都。4．

到冥王星去渡假。命题通常用字母p,q,a,b表示；

判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第4句的真值现在是假，随着人类科学的发展，有可能变成真，但不管怎样，真值是唯一的。因此，以上4个例子都是命题。而例如：

1．

快点走吧！

2．

到那去？

3．

x+y>10

等等句子，都不是命题。第二页，共八十页，编辑于2023年，星期六3.1.2命题逻辑公式

定义：

原子命题：不能再分解的命题称为原子命题。合式公式：原子命题是合式公式，连接词联结的合式公式的组合也是合式公式（命题公式）。常用的联结词：合取式：p与q，记做pΛ

q析取式：

p或q，记做p∨

q蕴含式：如果p则q，记做p→

q等价式：p当且仅当q，记做p<=>

q否定：～p

、

～最优先，其次为Λ、∨，再次为→，<=>第三页，共八十页，编辑于2023年，星期六命题表示公式（1）将陈述句转化成命题公式。如：设“下雨”为p，“骑车上班”为q，，1．“只要不下雨，我骑自行车上班”。～p

是q的充分条件， 因而，可得命题公式：～p→q2．“只有不下雨，我才骑自行车上班”。～p

是q的必要条件， 因而，可得命题公式：q→～p第四页，共八十页，编辑于2023年，星期六命题表示公式（2）事件化为命题公式的步骤：（１）分析简单命题，将其符号化；（２）使用适当的联结词把简单命题连接起来。例如：1．

“如果我进城我就去看你，除非我很累。” 设：p，我进城，q，去看你，r，我很累。 则有命题公式：～r→(p→q)。2．“应届高中生，得过数学或物理竞赛的一等奖， 保送上北京大学。” 设：p，应届高中生，q，保送上北京大学上学，

r，是得过数学一等奖。t，是得过物理一等奖。 则有命题公式公式：p

∧(r∨t)→

q。

第五页，共八十页，编辑于2023年，星期六２命题公式的解释定义：设Ａ为一个命题公式，p1,p2,…,pn是出现在Ａ中的全部原子命题，给原子命题各指定一个真值（０或者１），称为对Ａ的一个赋值或解释。若Ａ的值为真，则称为成真赋值。若Ａ的值为假，则称为成假赋值。第六页，共八十页，编辑于2023年，星期六公式逻辑真值表ＰＱ～ＰＰ∨ＱＰ∧ＱＰ→ＱＰＱＴＴＦＴＴＴＴＴＦＦＴＦＦＦＦＴＴＴＦＴＦＦＦＴＦＦＴＴ第七页，共八十页，编辑于2023年，星期六命题逻辑基础基本等值式交换率：p∨q<=>q

∨p

；

pΛq<=>qΛp

结合率：(p∨q)∨

r<=>p∨(q∨r); (pΛq)Λ

r<=>pΛ(qΛr)分配率：p∨(qΛ

r)<=>(p∨q)Λ(p∨r)

；

pΛ(q∨

r)<=>(pΛq)∨(pΛr)

双重否定率：～～p<=>p

等幂率：p<=>p∨p

，p<=>pΛp

等价等值式：p

q

<=> (p→

q)Λ(q→

p)等价否定式：p

q

<=> ~p~q

第八页，共八十页，编辑于2023年，星期六命题逻辑基础摩根率:～

(p∨q)

<=>～

pΛ

～

q

；

～

(pΛq)

<=>～

p∨

～

q

吸收率:p∨(pΛq)<=>p

；

pΛ(p∨q)<=>p

同一律:p∨0

<=>p

；

pΛ1

<=>p

蕴含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

归谬式:(p→

q)Λ(p→~q

)<=>～p排中律：p∨～p

<=>１；矛盾律：pΛ～p

<=>０

零率：p∨１

<=>１；

pΛ０

<=>０

第九页，共八十页，编辑于2023年，星期六范式：公式的标准型式。定义：设A为一个公式若A无成假赋值，则称A为重言式或永真式；若A无成真赋值，则称A为矛盾式或永假式；若A至少有一个成真赋值，则称A为可满足的；简单合取式：有限个原子命题或其否定构成合取式。简单析取式：有限个原子命题或其否定构成析取式。析取范式：仅由有限个简单合取式组成的析取式。合取范式：仅由有限个简单析取式组成的合取式。范式的性质：析取范式是矛盾式，当且仅当每个简单合取式是矛盾式。合取范式是永真式，当且仅当每个简单析取式是永真式。第十页，共八十页，编辑于2023年，星期六范式的转化存在定理：任何命题公式都存在着与之等值的析取范式和合取范式。求合取范式的步骤：（１）消去多余的｛∨，∧｝以及→联结词（２）去掉否定～符号（３）利用分配率例：3.1,3.23.1.3命题逻辑的意义

把自然语言转化为形式语言，以利于计算机能够处理。第十一页，共八十页，编辑于2023年，星期六例3.2：求的（（Ｐ∨Ｑ）→Ｒ）→Ｐ合取范式解：（（Ｐ∨Ｑ）→Ｒ）→Ｐ＝（～（Ｐ∨Ｑ）∨Ｒ）→Ｐ＝～（～（Ｐ∨Ｑ）∨Ｒ）∨Ｐ＝（（Ｐ∨Ｑ）∧～Ｒ）∨Ｐ＝（Ｐ∨Ｑ∨Ｐ）∧（～Ｒ∨Ｐ）＝（Ｐ∨Ｑ）∧（～Ｒ∨Ｐ）第十二页，共八十页，编辑于2023年，星期六3.1.4命题逻辑的推理规则（自然演绎推理）逻辑结论：对于Ａ→Ｂ，如果永真，则称Ｂ是Ａ的逻辑结论，即Ａ推出Ｂ的结论正确，Ａ为真则Ｂ为真，记为Ａ=>Ｂ。常用的推理定律（永真式）：，∧

附加：Ａ=>（Ａ∨Ｂ）简化：（Ａ∧Ｂ）=>Ａ

假言推理：（Ａ→Ｂ）∧Ａ）=>Ｂ拒取式：（（Ａ→Ｂ）∧～Ｂ）=>～Ａ析取三段论：（（Ａ∨Ｂ）∧～Ａ）=>Ｂ假言三段论：（（Ａ→Ｂ）∧（Ｂ→Ｃ））=>（Ａ→Ｃ）等价三段论：（（ＡＢ）∧（ＢＣ））=>（ＡＣ）构造性二难：（（Ａ→Ｂ）∧（Ｃ→Ｄ）∧（Ａ∨Ｃ））=>（Ｂ∨Ｄ）第十三页，共八十页，编辑于2023年，星期六常用的推理规则：（１）前提引入规则（２）结论引入规则（３）置换规则：等价的可以置换例３.4：证明：如果今天是下雨天，则要带伞或带雨衣。如果走路上班，则不带雨衣。今天下雨，走路上班，所以带雨伞。解：把题目用命题公式表示：今天下雨p，带伞q，带雨衣r，走路上班s前提：p→（q∨r），s→～r，p，s要证的结论：q证明：①p→（q∨r）②

p前提引入

③（q∨r）假言推理

④

s

⑤s→～r前提引入

⑥～r假言推理⑦q析取三段论第十四页，共八十页，编辑于2023年，星期六3.1.5命题逻辑的归结法归谬法：命题：A1、A2、A3

和B求证：A1ΛA2ΛA3成立，则B成立，即：A1ΛA2ΛA3→B为永真

A1ΛA2ΛA3→B

等价于~(A1ΛA2ΛA3)∨B

等价于~(~~(A1ΛA2ΛA3)∧~B)

等价于~((A1ΛA2ΛA3)∧~B)永真即证明((A1ΛA2ΛA3)∧~B)永假反证法：证明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

第十五页，共八十页，编辑于2023年，星期六例：前提：p→（~（r∨s）→q)，p，~s要证的结论：q证明：①p→（~（r∨s）→q)

②p前提引入

③~（r∨s）→q

假言推理

④

~q引入否定结论

⑤（r∨s）拒取式

⑥～s前提引入⑦s简化⑤⑧～s∧s⑥

⑦合取永假矛盾。第十六页，共八十页，编辑于2023年，星期六归结原理由J.A.Robinson由1965年提出。与演绎法(deductiveinference)完全不同，新的逻辑演算(inductiveinference)算法。一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）第十七页，共八十页，编辑于2023年，星期六命题逻辑的归结法子句集子句：子句是文字的集合，各个文字之间被析取分隔。文字：原子命题或否定被称为文字。合取范式：命题、命题或的与，如：

PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命题（元素）的集合例：命题公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

第十八页，共八十页，编辑于2023年，星期六归结式设C1,C2是子句集中的两个子句，如果C1中的文字L1与C2中文字L2互补，则可以从C1和

C2中分别消去文字L1和文字L2，并将中余下的部分按析取关系构成一个新子句C12，这个过程就叫归结。如子句：C1=P∨Q,C2=~P∨W

，归结式：C12

=W∨Q

性质：归结式C12

是亲本子句C1和

C2逻辑结论。

C1ΛC2→C12

，注意：反之不一定成立。第十九页，共八十页，编辑于2023年，星期六命题逻辑的归结法归结过程

将命题写成合取范式求出子句集对子句集使用归结推理规则归结式作为新子句参加归结归结式为空子句□，S是不可满足的（矛盾），原命题成立。（证明完毕）谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。第二十页，共八十页，编辑于2023年，星期六命题逻辑归结例题（1）例题，已知：(P→Q)求证：(～Q→～P)证明：（1）根据归结原理，将待证明公式转化成待归结命题公式：

(P→Q)∧～(～Q→～P)（2）分别将公式前项化为合取范式：

P→Q＝～P∨Q

结论求～后的后项化为合取范式： ～(～Q→～P)＝～(Q∨～P)＝～Q∧P

两项合并后化为合取范式： （～P∨Q）∧～Q∧P

（3）则子句集为：

{～P∨Q，～Q，P}第二十一页，共八十页，编辑于2023年，星期六命题逻辑归结例题（2）子句集为： {～P∨Q，～Q，P}（4）对子句集中的子句进行归结可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3归结）5.

， （2，4归结）

由上可得原公式成立。第二十二页，共八十页，编辑于2023年，星期六3.2谓词归结原理基础一阶逻辑3.2.1基本概念个体词：表示主语的词(客体、具体事物或抽象的概念）谓词：刻画个体性质或个体之间关系的词量词：表示数量的词第二十三页，共八十页，编辑于2023年，星期六谓词归结原理基础 小王是个工程师。

8是个自然数。 我去买花。 小丽和小华是朋友。其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。第二十四页，共八十页，编辑于2023年，星期六谓词归结原理基础个体常量：a,b,c个体变量：x,y,z谓词符号：P,Q,R谓词：由谓词符号和个体（项）组成。例P(x,y)一阶谓词：谓词中不含有谓词。n元谓词：就是有n个项。量词符号：

,第二十五页，共八十页，编辑于2023年，星期六例如：（1）所有的人都是要死的。（2）

有的人活到一百岁以上。在个体域D为人类集合时，可符号化为：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(x),其中Q(x)表示x活到一百岁以上。在个体域D是全总个体域时，引入特殊谓词R(x)表示x是人，可符号化为：（1）x（R(x)→P(x)）,

其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百岁以上。

第二十六页，共八十页，编辑于2023年，星期六3.2.2一阶谓词逻辑1谓词公式原子公式：单个谓词就是原子公式。谓词公式：简单说就是由原子公式、连接词、否定符号以及量词构成的式子。指导变量：量词后面的变量称为指导变量。x、y辖域：就是量词管辖的区域。约束出现：在辖域内，受量词约束的变量是约束出现。自由出现：在辖域内，不受量词约束的变量是约束出现。换名规则：将量词辖域中某个约束出现的个体变量改成在此辖域中未出现过的个体变量符号。xP(x,y)∧R(x,y)

第二十七页，共八十页，编辑于2023年，星期六替换规则：对某个自由变量用与原公式中所有个体变量符号不同的变量去替代，且处处替代。xP(x,y)∧R(x,y)替换xP(x,z)∧R(x,z)2.谓词公式的解释对谓词公式的各变量常量去替代，就构成了一个谓词公式的解释。当存在解释能使谓词公式为真时，则称这个解释满足谓词公式。这个解释就是这个谓词公式的模型。两个谓词公式等价，当且仅当所有的解释下两个谓词公式的值是相同的。永真式不可满足式归结原理就是对谓词公式的正确性证明转化为不可满足性证明。第二十八页，共八十页，编辑于2023年，星期六3.2.3谓词演算与推理1.谓词演算公式量词否定等值式：～(x

）

M（x）<=>（

y

）～

M（y）～(x

）

M（x）<=>（

y

）～

M（y）量词分配等值式：(x

）(

P（x）ΛQ（x）)<=>(x

）

P（x）Λ(x

）

Q（x）(x

）(

P（x）∨

Q（x）)<=>(x

）

P（x）∨

(x

）

Q（x）消去量词等值式：设个体域为有穷集合（a1,a2,…an）(x

）

P（x）<=>P（a1

）ΛP（a2

）Λ…ΛP（an

）(x

）P（x）<=>P（a1

）∨

P（a2

）∨

…

∨

P（an

）第二十九页，共八十页，编辑于2023年，星期六约束变量换名规则：

(Qx)P(x)<=>(Qy)P(y)

(Qx)P(x,z)<=>(Qy)P(y,z)量词辖域收缩与扩张等值式：(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）ΛQ)<=>(x

）

P（x）ΛQ

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）ΛQ)<=>(x

）

P（x）ΛQ

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）第三十页，共八十页，编辑于2023年，星期六前束范式

定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。第三十一页，共八十页，编辑于2023年，星期六即：把所有的量词都提到前面去，然后消掉所有量词

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)例９第三十二页，共八十页，编辑于2023年，星期六２谓词推理要运用与命题逻辑相同的推理规则和量词的消去和引入。任意量词可以消去，用变量或常量表示，存在量词可以用常量表示。对于任意量词，ｘ为自由变量，ｙ为不在Ｐ中约束出现的个体变量时：

ｘＰ（ｘ）=>Ｐ（ｙ）ｃ为常量

ｘＰ（ｘ）=>Ｐ（ｃ）对于存在量词，

ｘＰ（ｘ）=>Ｐ（ｃ）对于变量引入量词：

Ｐ（ｙ）=>ｘＰ（ｙ）要求ｙ在Ｐ（ｙ）中自由出现，且为真，ｘ不在Ｐ（ｙ）中约束出现。

Ｐ（ｃ）=>ｘＰ（ｘ）要求ｃ是特定常量，取代ｃ的ｘ不能在Ｐ（ｃ）中出现。第三十三页，共八十页，编辑于2023年，星期六例3.1020世纪７０年代的漫画都是日本漫画家创作的，这幅漫画是２０世纪７０年代的作品，因此这幅漫画是日本漫画家的作品。解：设Ｐ(x)：ｘ是20世纪７０年代的漫画Q(ｙ):ｙ日本漫画家的作品a:一幅漫画前提x(Ｐ(x)

→Q(x)),P(a)结论Q(a)证明①x(Ｐ(x)

→Q(x))②P(a)③Ｐ(a)

→Q(a)④Q(a)第三十四页，共八十页，编辑于2023年，星期六3.2.4谓词知识表示知识：是人们在认识、改造世界中经验的总结或者实事的描述。使用逻辑法表示知识，将自然语言描述的知识，通过谓词、函数加以描述，获得逻辑谓词公式，进而利用计算机进行处理。例：校长与小李打网球。可以表示为：定义：Play(x,y,z)表示，ｘ和ｙ打ｚ这种球

Play(zhang,li,tennis)

清华是个大学定义：Univ(x)表示ｘ是大学

Univ(qinghua)第三十五页，共八十页，编辑于2023年，星期六常用的可以用蕴含代表规则：人人都受法律管制：

Human(x)→Lawed(x)

如果ｘ犯罪则被惩罚

Commit(x)→Punished(x)（Human(x)→Lawed(x)）→（Commit(x)→Punished(x)）应用谓词表示知识应用广泛：（１）易于用数据库存贮知识（２）谓词具有完备逻辑推理方法（３）表达的知识具有科学严密性（４）逻辑推理具有知识的一致性第三十六页，共八十页，编辑于2023年，星期六３.3谓词逻辑归结原理3.3.1归结原理命题：A1、A2、A3

和B求证：A1ΛA2ΛA3成立，则B成立，反证法：证明A1ΛA2ΛA3Λ～B是矛盾式（永假式）3.3.2Skolem标准形1.前束范式2.Skolem标准形消去前束范式中的所有量词的公式第三十七页，共八十页，编辑于2023年，星期六量词消去原则： 消去存在量词“”，略去全程量词“”。 注意：左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。第三十八页，共八十页，编辑于2023年，星期六谓词归结子句形(Skolem标准形)Skolem定理： 谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。SKOLEM标准形定义： 消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。第三十九页，共八十页，编辑于2023年，星期六谓词归结子句形(Skolem标准形)例:将下式化为Skolem标准形： ～(x)(y)P(a,x,y)→(x)(～(y)Q(y,b)→R(x))解：第一步，消去→号，得： ～(～(x)(y)P(a,x,y))∨(x)(～～(y)Q(y,b)∨R(x))第二步，～深入到量词内部，得：

(x)(y)P(a,x,y)∨(x)((y)Q(y,b)∨R(x))第三步，变元易名，得

(x)((y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))第四步，存在量词左移，直至所有的量词移到前面，得：

(x)(y)(u)(v)P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式第四十页，共八十页，编辑于2023年，星期六谓词归结子句形(Skolem标准形)

第五步，消去“”（存在量词），略去“”全称量词 消去(y)，因为它左边只有(x)，所以使用x的函数f(x)代替之，这样得到：

(x)(z)(P(a,x,f(x))∧～Q(z,b)∧～R(x))

消去(z)，同理使用g(x)代替之，这样得到：

(x)(P(a,x,f(x))∧～Q(g(x),b)∧～R(x))

则，略去全称变量，原式的Skolem标准形为：

P(a,x,f(x))∧～Q(g(x),b)∧～R(x)

第四十一页，共八十页，编辑于2023年，星期六3.3.3子句集子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S的求取：

G→SKOLEM标准形 →消去存在变量 →以“，”取代“Λ”，并表示为集合形式。第四十二页，共八十页，编辑于2023年，星期六谓词归结子句形

G是不可满足的<=>S是不可满足的G与S不等价，但在不可满足得意义下是一致的。

定理： 若G是给定的公式，而S是相应的子句集，则G是不可满足的<=>S是不可满足的。

注意：G真不一定S真，而S真必有G真。 即：S=>G第四十三页，共八十页，编辑于2023年，星期六谓词归结子句形G=G1ΛG2ΛG3Λ…ΛGn

的子句形G的字句集可以分解成几个单独处理。

有SG=S1US2US3U…USn

则SG

与S1US2US3U…USn在不可满足得意义上是一致的。 即SG

不可满足<=>S1US2US3U…USn不可满足第四十四页，共八十页，编辑于2023年，星期六求取子句集例(1)例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：

P(x,y)表示x是y的父亲

Q(x,y)表示x是y的祖父

ANS(x)表示问题的解答第四十五页，共八十页，编辑于2023年，星期六求取子句集例(2)对于第一个条件，“如果x是y的父亲，y又是z的父亲，则x是z的祖父”，一阶逻辑表达式如下：

A1：(x)(y)(z)(P(x,y)∧P(y,z)→Q(x,z)) SA1：～P(x,y)∨～P(y,z)∨Q(x,z)对于第二个条件：“每个人都有父亲”，一阶逻辑表达式：

A2：(y)(x)P(x,y) SA2：P(f(y),y)对于结论：某个人是它的祖父

B：(x)(y)Q(x,y)

否定后得到子句：～（(x)(y)Q(x,y)）∨ANS(x) S～B：～Q(x,y)∨ANS(x)则得到的相应的子句集为：{SA1，SA2，S～B}第四十六页，共八十页，编辑于2023年，星期六归结原理归结原理正确性的根本在于，找到矛盾可以肯定不真。方法：和命题逻辑一样。但由于有函数，所以要考虑合一和置换。

第四十七页，共八十页，编辑于2023年，星期六3.3.4置换与合一置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义： 置换是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，x1,x2,…,xn是互不相同的变量，t1,t2,…,tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。例如

{a/x，c/y，f(b)/z}是一个置换。

{g(y)/x，f(x)/y}不是一个置换，

第四十八页，共八十页，编辑于2023年，星期六置换的合成设＝{t1/x1,t2/x2,…,tn/xn}， ＝{u1/y1,u2/y2,…,un/yn}，是两个置换。 则与的合成也是一个置换，记作·。它是从集合

{t1·/x1,t2·/x2,…,tn·/xn,u1/y1,u2/y2,…,un/yn}

中删去以下两种元素：当ti=xi时，删去ti/xi(i=1,2,…,n);

当yi{x1,x2,…,xn}时，删去uj/yj(j=1,2,…,m)

最后剩下的元素所构成的集合。合成即是对ti先做置换然后再做置换，置换xi第四十九页，共八十页，编辑于2023年，星期六置换的合成例：设：＝{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,y/z}

其中，f(b)/x中的f(b)是置换作用于f(y)的结果；y/y中的y是置换作用于z的结果。在该集合中，y/y满足定义中的条件i，需要删除；a/x，b/y满足定义中的条件ii，也需要删除。最后得

·＝{f(b)/x，y/z}第五十页，共八十页，编辑于2023年，星期六合一合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。定义：设有公式集F＝{F1，F2，…，Fn}，若存在一个置换，可使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}是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。

第五十一页，共八十页，编辑于2023年，星期六最一般合一：设δ是谓词公式集F，如果对F的任意一个合一θ都存在一个置换λ使得θ=δ·λ，则称δ是一个最一般的合一mgu.最一般合一求取方法：逐一比较找出不一致，并做合一置换算法：对于F1和F2①令W={F1,F2}②令k=0，W0=W,δ0=ε③如果Wk已合一，停止,δk=mgu,，否则找不一致集Dk④若Dk中存在元素vk和tk，其中vk不出现于tk中，转⑤，否则不可合一⑤令δk+1=δk·{tk/vk},Wk+1=Wk·{tk/tk}=Wδk+1⑥k=k+1转③。可证明若F1和F2可合一，算法必停于③第五十二页，共八十页，编辑于2023年，星期六例3.16：W={P(a,x,f(g(y))),P(z,f(a),f(u))},F1=P(a,x,f(g(y))),F2=P(z,f(a),f(u)),求：F1和F2的最一般合一第五十三页，共八十页，编辑于2023年，星期六3.3.5归结式要考虑变量的置换和合一归结式：对两个无公共变量的字句对于子句C1‘∨L1和C2’∨L2，如果L1与～L2可合一，且s是其合一者，则(C1‘∨C2’)s是其归结式。其中L1、L2是单文字。事实上L1、L2中有一个含有否定符，所以对另一个加上否定符后，才能判断它们是否可合一。

例（1）P(x)∨Q(x,y)与~P(a)∨R(b,z)（2）P(x,y)∨Q(x)∨R(x)与~P(a,z)∨~Q(b)第五十四页，共八十页，编辑于2023年，星期六3.3.5归结式归结的注意事项：谓词的一致性，P()与Q()，不可以常量的一致性，P(a,…)与P(b,….)，不可以 变量，P(a,….)与P(x,…)，可以变量与函数，P(a,x,….)与P(x,f(x),…)，不可以；是不能同时消去两个互补对，P∨Q与～P∨～Q的空，不可以先进行内部简化（置换、合并）

第五十五页，共八十页，编辑于2023年，星期六3.3.6归结的过程写出谓词关系公式→用反演法写出谓词表达式→SKOLEM标准形→子句集S→对S中可归结的子句做归结→归结式仍放入S中，反复归结过程→得到空子句

▯得证第五十六页，共八十页，编辑于2023年，星期六

子句集的化简

在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集。其化简步骤如下：

(1)消去连接词“→”和“↔”反复使用如下等价公式：

P→Q⇔﹁P∨QP↔Q⇔(P∧Q)∨(﹁P∧﹁Q)即可消去谓词公式中的连接词“→”和“↔”。例如公式

(∀x)((∀y)P(x,y)→﹁(∀y)(Q(x,y)→R(x,y)))经等价变化后为

(∀x)(﹁(∀y)P(x,y)∨﹁(∀y)(﹁Q(x,y)∨R(x,y)))第五十七页，共八十页，编辑于2023年，星期六2.子句集的化简(2)减少否定符号的辖域反复使用双重否定率

﹁(﹁P)⇔P摩根定律

﹁(P∧Q)⇔﹁P∨﹁Q﹁(P∨Q)⇔﹁P∧﹁Q量词转换率

﹁(∀x)P(x)⇔(∃x)﹁P(x)﹁(∃x)P(x)⇔(∀x)￢P(x)将每个否定符号“﹁”移到仅靠谓词的位置，使得每个否定符号最多只作用于一个谓词上。例如，上式经等价变换后为

(∀x)((∃y)﹁P(x，y)∨(∃y)(Q(x，y)∧﹁R(x，y)))第五十八页，共八十页，编辑于2023年，星期六子句集的化简

(3)对变元标准化在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字。例如，上式经变换后为

(∀x)((∃y)﹁P(x，y)∨(∃z)(Q(x，z)∧﹁R(x，z)))(4)化为前束范式化为前束范式的方法:把所有量词都移到公式的左边，并且在移动时不能改变其相对顺序。由于第(3)步已对变元进行了标准化，每个量词都有自己的变元，这就消除了任何由变元引起冲突的可能，因此这种移动是可行的。例如，上式化为前束范式后为

(∀x)(∃y)(∃z)(﹁P(x，y)∨(Q(x，z)∧﹁R(x，z)))第五十九页，共八十页，编辑于2023年，星期六2.子句集的化简

(5)消去存在量词消去存在量词时，需要区分以下两种情况：

若存在量词不出现在全称量词的辖域内（即它的左边没有全称量词），只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。

若存在量词位于一个或多个全称量词的辖域内，例如

(∀x1)…(∀xn)(∃y)P(x1，x2,…,xn,y)则需要用Skolem函数f(x1，x2,…,xn)替换受该存在量词约束的变元y，然后再消去该存在量词。例如，上步所得公式中存在量词(∃y)和(∃z)都位于(∀x)的辖域内，因此都需要用Skolem函数来替换。设替换y和z的Skolem函数分别是f(x)和g(x)，则替换后的式子为

(∀x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))第六十页，共八十页，编辑于2023年，星期六2.子句集的化简

(6)化为Skolem标准形

Skolem标准形的一般形式为

(∀x1)…(∀xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem标准形的母式，它由子句的合取所构成。把谓词公式化为Skolem标准形需要使用以下等价关系

P∨(Q∧R)⇔(P∨Q)∧(P∨R)例如，前面的公式化为Skolem标准形后为

(∀x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x))))(7)消去全称量词由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。但剩下的母式，仍假设其变元是被全称量词量化的。例如，上式消去全称量词后为

(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))第六十一页，共八十页，编辑于2023年，星期六2.子句集的化简

(8)消去合取词在母式中消去所有合取词，把母式用子句集的形式表示出来。其中，子句集中的每一个元素都是一个子句。例如，上式的子句集中包含以下两个子句

﹁P(x,f(x))∨Q(x,g(x))﹁P(x,f(x))∨﹁R(x,g(x))(9)更换变量名称对子句集中的某些变量重新命名，使任意两个子句中不出现相同的变量名。由于每一个子句都对应着母式中的一个合取元，并且所有变元都是由全称量词量化的，因此任意两个不同子句的变量之间实际上不存在任何关系。这样，更换变量名是不会影响公式的真值的。例如，对前面的公式，可把第二个子句集中的变元名x更换为y，得到如下子句集

﹁P(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))第六十二页，共八十页，编辑于2023年，星期六对于证明问题设F为前提的公式集，Q为目标公式集，用归结反演证明的步骤：（1）否定Q，得到~Q

（2）把~Q加入到公式集F，得到{F，~Q}称为S

（3）对S进行归结，归结到空子句为止。第六十三页，共八十页，编辑于2023年，星期六例：求证:G是F1和F2的逻辑推论

F1：F2:

G:

证明：化为子句集{P(a)(1)~R(y)∨L(a,y)(2)~P(x)∨~Q(y)∨~L(x,y)(3)R(b)(4)Q(b)(5)(2)(4)归结L(a,b)(6)(1)(3)归结~Q(y)∨~L(a,y)(7)(5)(7)~L(a,b)(8)(6)(8)NIL证毕。第六十四页，共八十页，编辑于2023年，星期六例题“快乐学生”问题假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。

解：先将问题用谓词表示如下：R1:“任何通过计算机考试并获奖的人都是快乐的”

(x)((Pass(x,computer)∧Win(x,prize))→Happy(x))R2:“任何肯学习或幸运的人都可以通过所有考试”

(x)(y)(Study(x)∨Lucky(x)→Pass(x,y))R3:“张不肯学习但他是幸运的” ～Study(zhang)∧Lucky(zhang)R4:“任何幸运的人都能获奖”

(x)(Luck(x)→Win(x,prize))结论：“张是快乐的”的否定～Happy(zhang)第六十五页，共八十页，编辑于2023年，星期六例题“快乐学生”问题由R1及逻辑转换公式:P∧W→H=～（P∧W）∨H，可得

(1)～Pass(x,computer)∨～Win(x,prize)∨Happy(x)由R2：(2)～Study(y)∨Pass(y,z)(3)～Lucky(u)∨Pass(u,v)由R3：(4)～Study(zhang)(5)Lucky(zhang)由R4：(6)～Lucky(w)∨Win(w，prize)由结论：(7)～Happy(zhang) （结论的否定）(8)～Pass(w,computer)∨Happy(w)∨～Luck(w)(1)(6)，{w/x}(9)～Pass(zhang,computer)∨～Lucky(zhang)(8)(7)，{zhang/w}(10)

～Pass(zhang,computer) (9)(5)(11)

～Lucky(zhang) (10)(3)，{zhang/u,computer/v}(12)

ɓ

(11)(5)

第六十六页，共八十页，编辑于2023年，星期六对于用归结原理求取问题答案步骤：（1）把已知化为谓词公式并转化成子句集S(2)把待求解的问题用谓词公式表示，并否定之，然后和谓词ANSWER(x)构成析取式，x代表问题的答案。（3）把第二步的析取式和S合并，构成S’(4)对S’进行归结（5）若归结出ANSWER(x)，并且在x已经被替代，被替代就是答案。第六十七页，共八十页，编辑于2023年，星期六已知：F1:李(li)先生是小赵(zhao)的老师；

F2:小赵(zhao)与小刘(liu)是同班同学；

F3:如果x与y是同班同学，则x的老师也是y的老师。定义的谓词如下：

T(x，y)：表示x是y的老师；

C(x，y)：表示x与y是同班同学；求：小刘的老师是谁？解：把已知前提及待求解的问题表示成谓词公式：

第六十八页，共八十页，编辑于2023年，星期六把上述公式化为子句集：（1）（2）（3）（4）应用归结原理进行归结：（5）（1）和（3）归结（4）和（5）归结（2）和（6）归结得知小刘的老师是李老师。第六十九页，共八十页，编辑于2023年，星期六第七十页，共八十页，编辑于2023年，星期六归结原理归结法的实质：归结法是仅有一条推理规则的推理方法。