谓词逻辑与归结原理

谓词逻辑与归结原理第一页，共五十二页，2022年，8月28日1归结推理命题逻辑谓词逻辑Skolem标准形、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理第二页，共五十二页，2022年，8月28日2命题与联结词称能判断真假而不是可真可假的陈述句为命题

（proposition）。作为命题的陈述句所表达得的判断结果称为命题的真值。真值只取两个：真与假。真值为真的命题称为真命题。真值为假的命题称为假命题。感叹句、疑问句、祈使句都不能称为命题。判断结果不唯一确定的陈述句不是命题。陈述句中的悖论不是命题。说明第三页，共五十二页，2022年，8月28日34是素数。

x大于y。充分大的偶数等于两个素数之和。今天是星期二。

请不要吸烟！这朵花真美丽啊！我正在说假话。例1.1

判断下列句子是否为命题。

是，假命题是，真命题不是，无确定的真值是，真值客观存在是，真值根据具体情况而定。不是，疑问句不是，祈使句不是，感叹句不是，悖论第四页，共五十二页，2022年，8月28日4命题和真值的符号化用小写英文字母p,q,r…,pi,qi

,ri

…表示命题用“1”表示真，用“0”表示假

r：充分大的偶数等于两个素数之和。s：今天是星期二。p：4是素数。q：不能被分解成更简单的陈述句，称这样的命题为简单命题或原子命题。由简单陈述句通过联结词而成的陈述句，称这样的命题为复合命题。

第五页，共五十二页，2022年，8月28日5例将下面这段陈述中所出现的原子命题符号化，并指出它们的真值，然后再写出这段陈述。

是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。

p：是有理数q：2是素数；r：2是偶数s：3是素数；t：4是素数01110非p；q并且(与)r；q或t；如果q，则s；q当且仅当s。第六页，共五十二页，2022年，8月28日6半形式化形式数理逻辑研究方法的主要特征是将论述或推理中的各种要素都符号化。即构造各种符号语言来代替自然语言。形式化语言：完全由符号所构成的语言。将联结词（connective）符号化，消除其二义性，对其进行严格定义。例如： 他是100米或400米赛跑的冠军。

鱼香肉丝或锅包肉，加一碗汤。第七页，共五十二页，2022年，8月28日7定义1.1 否定(negation)设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式,记作┐p，符号┐称作否定联结词，并规定┐p为真当且仅当p为假。

例如：p： 哈尔滨是一个大城市。

┐p：哈尔滨是一个不大城市。

┐p：哈尔滨不是一个大城市。p┐p1001第八页，共五十二页，2022年，8月28日8定义1.2 合取(conjunction)设p,q为二命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q，∧称作合取联结词，并规定p∧q为真当且仅当p与q同时为真。使用合取联结词时要注意的两点：描述合取式的灵活性与多样性。

自然语言中的“既……又……”、“不但……而且……”、“虽然……但是……”、“一面……一面……”等联结词都可以符号化为∧。分清简单命题与复合命题。

不要见到“与”或“和”就使用联结词∧。

pqp∧q1

11100010000第九页，共五十二页，2022年，8月28日9例将下列命题符号化吴颖既用功又聪明。吴颖不仅用功而且聪明。吴颖虽然聪明，但不用功。张辉与王丽都是三好学生。张辉与王丽是同学。

p:吴颖用功。q:吴颖聪明。r:张辉是三好学生。s:王丽是三好学生。t:张辉与王丽是同学。

(1)p∧q(2)p∧q(3)q∧┐p(4)r∧s(5)t第十页，共五十二页，2022年，8月28日10合取举例p：我们去看电影。

q：房间里有十张桌子。

p∧q：我们去看电影并且房间里有十张桌子。在数理逻辑中，关心的只是复合命题与构成复合命题的各原子命题之间的真值关系，即抽象的逻辑关系，并不关心各语句的具体内容。说明第十一页，共五十二页，2022年，8月28日11定义1.3 析取(disjunction)设p，q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假。

自然语言中的“或”具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或(排异或)。

说明pqp∨q1

11101011000第十二页，共五十二页，2022年，8月28日12例将下列命题符号化

张晓静爱唱歌或爱听音乐。张晓静只能挑选202或203房间。张晓静是江西人或安徽人。他昨天做了二十或三十道习题。设p：张晓静爱唱歌，q：张晓静爱听音乐。

相容或，符号化为

p∨q设t：张晓静挑选202房间，

u：张晓静挑选203房间。

排斥或，符号化为：(t∧┐u)∨(┐t∧u)设r：张晓静是江西人，

s：张晓静是安徽人。

排斥或，符号化为：r∨s。

(排斥或联结的两个命题事实上不可能同时为真)

或符号化为：(r∧┐s)∨(┐r∧s)原子命题，因为“或”只表示了习题的近似数目。第十三页，共五十二页，2022年，8月28日13定义1.4 蕴涵(implication)设p，q为二命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作p→q，并称p是蕴涵式的前件，q为蕴涵式的后件，→称作蕴涵联结词,并规定p→q为假当且仅当p为真q为假。

说明p→q的逻辑关系表示q是p的必要条件。

q是p的必要条件有许多不同的叙述方式

只要p，就q

因为p，所以qp仅当q只有q才p除非q才p除非q，否则非p

pqp→q1

11100011001第十四页，共五十二页，2022年，8月28日14例将下列命题符号化，并指出其真值

如果3+3＝6，则雪是白的。如果3+3≠6，则雪是白的。如果3+3＝6，则雪不是白的。如果3+3≠6，则雪不是白的。解：令p：3+3＝6，p的真值为1。

q：雪是白色的，q的真值也为1。

p→q┐p→q p→┐q ┐p→┐q 1101第十五页，共五十二页，2022年，8月28日15例将下列命题符号化，并指出其真值

以下命题中出现的a是一个给定的正整数：(5)只要a能被4整除，则a一定能被2整除。(6)a能被4整除，仅当a能被2整除。(7)除非a能被2整除，a才能被4整除。(8)除非a能被2整除，否则a不能被4整除。(9)

只有a能被2整除，a才能被4整除。(10)只有a能被4整除，a才能被2整除。解：令r：a能被4整除

s：a能被2整除(5)至(9)五个命题均叙述的是a能被2整除是a能被4整除的必要条件，因而都符号化为r→s。其真值为1在(10)中，将a能被4整除看成了a能被2整除的必要条件，因而应符号化为s→r。a值不定时，真值未知。第十六页，共五十二页，2022年，8月28日16关于蕴含的进一步说明作为一种规定，当p为假时，无论q是真是假，p→q均为真。也就是说，只有p为真q为假这一种情况使得复合命题p→q为假。称为实质蕴含。例：如果x>5，则x>2。

(1)x=6 如果6>5，则6>2。

(2)

x=3

如果3>5，则3>2。

(3)x=1 如果1>5，则1>2。

例：如果我有车，那么我去接你常出现的错误，没有分清充分条件与必要条件。第十七页，共五十二页，2022年，8月28日17定义1.5 等价(two-way-implication)设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词，并规定pq为真当且仅当p与q同时为真或同时为假。说明“当且仅当”（ifandonlyif）pq的逻辑关系为p与q互为充分必要条件。

(p→q)∧(q→p)与pq的逻辑关系完全一致。pqpq1

11100010001第十八页，共五十二页，2022年，8月28日18关于基本联结词的说明{┐,∧,∨,→,}，称为一个联结词集。由联结词集{┐,∧,∨,→,}中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以称它们为基本的复合命题。基本复合命题的真值见下表：第十九页，共五十二页，2022年，8月28日19关于基本联结词的说明多次使用联结词集中的联结词，可以组成更为复杂的复合命题。求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。本书规定的联结词优先顺序为：()，┐，∧，∨，→，，对于同一优先级的联结词，先出现者先运算。第二十页，共五十二页，2022年，8月28日20例令 p：北京比天津人口多。

q：2+2＝4.

r：乌鸦是白色的。求下列复合命题的真值：

(1)((┐p∧q)∨(p∧┐q))→r

(2)(q∨r)→(p→┐r)

(3)(┐p∨r)(p∧┐r)解：p、q、r的真值分别为

1、1、0

(1)1

(2)1

(3)0我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。说明第二十一页，共五十二页，2022年，8月28日21关于合式公式(┐A)、(A∧B)等公式单独出现时，外层括号可以省去，写成┐A、A∧B等。公式中不影响运算次序的括号可以省去，

如公式(p∨q)∨(┐r)可以写成p∨q∨┐r。合式公式的例子：

(p→q)∧(qr)

(p∧q)∧┐r

p∧(q∧┐r)不是合式公式的例子

pq→r

(p→(r→q)第二十二页，共五十二页，2022年，8月28日22赋值举例在公式(┐p1∧┐p2∧┐p3)∨(p1∧p2)中，

000(p1＝0，p2＝0，p3＝0)，

110(p1＝1，p2＝1，p3＝0)都是成真赋值，

001(p1＝0，p2＝0，p3＝1)，

011(p1＝0，p2＝1，p3＝1)都是成假赋值。在(p∧┐q)→r中，

011(p1＝0，p2＝1，p3＝1)为成真赋值，

100(p1＝1，p2＝0，p3＝0)为成假赋值。重要结论：

含n(n≥1)个命题变项的公式共有2n个不同的赋值。

第二十三页，共五十二页，2022年，8月28日23真值表求下列公式的真值表，并求成真赋值和成假赋值。(1)(┐p∧q)→┐r(2)(p∧┐p)(q∧┐q)(3)┐(p→q)∧q∧r

第二十四页，共五十二页，2022年，8月28日24定义1.10重言式、永真式、可满足式设A为任一命题公式(1)若A在它的各种赋值下取值均为真,则称A是重言式(tautology)或永真式。(2)若A在它的各种赋值下取值均为假,则称A是矛盾式(contradiction)或永假式。(3)若A不是矛盾式,则称A是可满足式（satisfactableformula）。第二十五页，共五十二页，2022年，8月28日25例题下列各公式均含两个命题变项p与q，它们中哪些具有相同的真值表?

(1)p→q (4)(p→q)∧(q→p)

(2)pq (5)┐q∨p

(3)┐(p∧┐q)第二十六页，共五十二页，2022年，8月28日26哑元设公式A,B中共含有命题变项p1,p2,…,pn，，而A或B不全含有这些命题变项，比如A中不含pi,pi+1,…,pn,称这些命题变项为A的哑元，A的取值与哑元的变化无关，因而在讨论A与B是否有相等的真值表时，将A,B都看成p1,p2,…,pn的命题公式。第二十七页，共五十二页，2022年，8月28日27例题

例1.10

下列公式中,哪些具有相同的真值表?

(1)p→q

(2)┐q∨r

(3)(┐p∨q)∧((p∧r)→p)

(4)(q→r)∧(p→p)第二十八页，共五十二页，2022年，8月28日28自动推理第二十九页，共五十二页，2022年，8月28日29Resolution归结方法是一种机械化的,可在计算机上加以实现的推理方法可认为是一种反向推理形式提供了一种自动定理证明的方法第三十页，共五十二页，2022年，8月28日30ResolutionRefutations（1）定理证明的任务:由前提A1A2...An推出结论B即证明:A1A2...AnB永真转化为证明:A1A2...An~B为永假式归结推理就是:从A1A2...An~B出发,使用归结推理规则来找出矛盾,最后证明定理A1A2...AnB的成立第三十一页，共五十二页，2022年，8月28日31ResolutionRefutations（2）定理证明的任务:由前提A1A2...An推出结论B即证明:A1A2...AnB永真转化为证明:A1A2...An~B为永假式归结推理就是:从A1A2...An~B出发,使用归结推理规则来找出矛盾,最后证明定理A1A2...AnB的成立第三十二页，共五十二页，2022年，8月28日32ResolutionRefutations（3）一般过程:建立子句集S从子句集S出发,仅对S的子句间使用归结推理规则如果得出空子句,则结束;否则转下一步将所得归结式仍放入S中对新的子句集使用归结推理规则转(3)空子句不含有文字,它不能被任何解释满足,所以空子句是永假的,不可满足的归结过程出现空子句,说明出现互补子句对,说明S中有矛盾,因此S是不可满足的.第三十三页，共五十二页，2022年，8月28日33SoundnessandCompleteness归结原理是合理的归结原理是完备的第三十四页，共五十二页，2022年，8月28日34归结原理概述归结原理由由1965年提出。与演绎法(deductiveinference)完全不同，新的逻辑演算(inductiveinference)算法。一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。

第三十五页，共五十二页，2022年，8月28日35命题逻辑的归结法命题逻辑基础：定义：合取式：p与q，记做pΛ

q析取式：

p或q，记做p∨

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

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

q

。。。。。。第三十六页，共五十二页，2022年，8月28日36命题逻辑基础定义：若A无成假赋值，则称A为重言式或永真式；若A无成真赋值，则称A为矛盾式或永假式；若A至少有一个成真赋值，则称A为可满足的；析取范式：仅由有限个简单合取式组成的析取式。合取范式：仅由有限个简单析取式组成的合取式。第三十七页，共五十二页，2022年，8月28日37命题逻辑基础基本等值式24个(1)交换率：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)

第三十八页，共五十二页，2022年，8月28日38命题逻辑基础基本等值式（1）摩根率:～

(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

第三十九页，共五十二页，2022年，8月28日39命题表示公式例如：1．

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

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

∧(r∨t)→

q。

第四十页，共五十二页，2022年，8月28日40命题逻辑的归结法基本单元：简单命题（陈述句）例：命题：A1、A2、A3

和B求证：A1ΛA2ΛA3成立，则B成立，即：A1ΛA2ΛA3→B反证法：证明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

第四十一页，共五十二页，2022年，8月28日41命题逻辑的归结法建立子句集合取范式：命题、命题和的与，如：

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

第四十二页，共五十二页，2022年，8月28日42命题逻辑的归结法归结过程

将命题写成合取范式求出子句集对子句集使用归结推理规则归结式作为新子句参加归结归结式为空子句□，S是不可满足的（矛盾），原命题成立。（证明完毕）谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。第四十三页，共五十二页，2022年，8月28日43命题逻辑归结例题（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}第四十四页，共五十二页，2022年，8月28日44命题逻辑归结例题（2）子句集为： {～P∨Q，～Q，P}（4）对子句集中的子句进行归结可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3归结）5.

， （2，4归结）

由上可得原公式成立。第四十五页，共五十二页，2022年，8月28日45证明：化成子句集

S={P,┐P∨┐Q∨R，┐S∨Q，┐T∨Q，T，┐R}归结可用图的演绎树表示，由于根部出现空子句，因此命题R得证。

例：设已知前提集为

P……………

…(1)(P∧Q)→R………(2)(S∨T)→Q………(3)T…………(4)求证R。第四十六页，共五十二页，2022年，8月28日46命题逻辑在计算机科学中的应用

逻辑难题

可以用逻辑推理解决的难题称为逻辑难题。求解逻辑难题是实践逻辑规则的一种好方法 涉及用于执行逻辑推理的计算机程序通常也使用著名的逻辑难题来演示它们的能力第四十七页，共五十二页，2022年，8月28日471.7命题逻辑在计算机科学中的应用

爱因斯坦的一道题。一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘。这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快地说出自己头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉，然后三人都