谓词逻辑与归结原理精.ppt

谓词逻辑与归结原理1第1页，本讲稿共52页归结推理命题逻辑谓词逻辑Skolem标准形、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理2第2页，本讲稿共52页命题与联结词命题与联结词命题与联结词命题与联结词n称能判断真假而不是可真可假的陈述句为命题（proposition）。n作为命题的陈述句所表达得的判断结果称为命题的真值。n真值只取两个：真与假。n真值为真的命题称为真命题。n真值为假的命题称为假命题。q感叹句、疑问句、祈使句都不能称为命题。感叹句、疑问句、祈使句都不能称为命题。q判断结果不唯一确定的陈述句不是命题。判断结果不唯一确定的陈述句不是命题。q陈述句中的悖论不是命题陈述句中的悖论不是命题。说明说明3第3页，本讲稿共52页(1)4是素数。(2)(3)x大于y。(4)充分大的偶数等于两个素数之和。(5)今天是星期二。(6)(7)请不要吸烟！(8)这朵花真美丽啊！(9)我正在说假话。例例例例1.11.1 判断下列句子是否为命题。判断下列句子是否为命题。判断下列句子是否为命题。判断下列句子是否为命题。(1)(1)是，假命题是，假命题(2)(2)是，真命题是，真命题(3)(3)不是，无确定的真值不是，无确定的真值(4)(4)是，真值客观存在是，真值客观存在(5)(5)是，真值根据具体情况而定。是，真值根据具体情况而定。(6)(6)不是，疑问句不是，疑问句(7)(7)不是，祈使句不是，祈使句(8)(8)不是，感叹句不是，感叹句(9)(9)不是，悖论不是，悖论4第4页，本讲稿共52页命题和真值的符号化n用小写英文字母用小写英文字母p,q,r,pi,qi,ri 表示命题表示命题n用用“1”表示真，用表示真，用“0”表示假表示假r：充分大的偶数等于两个素数之充分大的偶数等于两个素数之和和。s：今天是星期二今天是星期二。p：4 4是素数。是素数。q：q不能被分解成更简单的陈述句，称这样的命题为不能被分解成更简单的陈述句，称这样的命题为简单命题简单命题或或原子命题原子命题。q由简单陈述句通过联结词而成的陈述句，称这样的命题为由简单陈述句通过联结词而成的陈述句，称这样的命题为复合命题复合命题。5第5页，本讲稿共52页例将下面这段陈述中所出现的原子命题符号化，并指出它们的将下面这段陈述中所出现的原子命题符号化，并指出它们的真值，然后再写出这段陈述。真值，然后再写出这段陈述。是是有有理理数数是是不不对对的的；2 2是是偶偶素素数数；2 2或或4 4是是素素数数；如如果果2 2是素数，则是素数，则3 3也是素数；也是素数；2 2是素数当且仅当是素数当且仅当3 3也是素数。也是素数。p：是有理数是有理数q：2 2是素数；是素数；r：2 2是偶数是偶数s s：3 3是素数；是素数；t：4 4是素数是素数0111 10非非p；q并且并且(与与)r；q或或t t；如果如果q，则则s；q当且仅当当且仅当s。6第6页，本讲稿共52页n半形式化形式n数理逻辑研究方法的主要特征是将论述或推理中的各种要素都符号化。即构造各种符号语言来代替自然语言。n形式化语言：完全由符号所构成的语言。n将联结词（connective）符号化，消除其二义性，对其进行严格定义。n例如：他是100米或400米赛跑的冠军。鱼香肉丝或锅包肉，加一碗汤。7第7页，本讲稿共52页定义定义1.1 否定(negation)n设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式,记作p，符号称作否定联结词，并规定p为真当且仅当p为假。例如例如：p：哈尔滨哈尔滨是一个大城市是一个大城市。p：哈尔滨是一个不大城市。：哈尔滨是一个不大城市。p：哈尔滨不是一个大城市。：哈尔滨不是一个大城市。pp10018第8页，本讲稿共52页定义定义定义定义1.21.2 合取合取(conjunctionconjunction)n设p,q为二命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作pq，称作合取联结词，并规定pq为真当且仅当p与q同时为真。使用合取联结词时要注意的两点：使用合取联结词时要注意的两点：1)1)描述合取式的灵活性与多样性。描述合取式的灵活性与多样性。自然语言中的自然语言中的“既既又又”、“不但不但而且而且”、“虽然虽然但是但是”、“一面一面一面一面”等联结词都可以符号化为等联结词都可以符号化为。2)2)分清简单命题与复合命题。分清简单命题与复合命题。不要见到不要见到“与与”或或“和和”就使用联结词就使用联结词。pqpq1 11 11 11 10 00 00 01 10 00 000 09第9页，本讲稿共52页例例 将下列命题符号化(1)吴颖既用功又聪明。(2)吴颖不仅用功而且聪明。(3)吴颖虽然聪明，但不用功。(4)张辉与王丽都是三好学生。(5)张辉与王丽是同学。p:p:吴颖用功。吴颖用功。q:q:吴颖聪明。吴颖聪明。r:r:张辉是三好学生。张辉是三好学生。s:s:王丽是三好学生。王丽是三好学生。t:t:张辉与王丽是同学。张辉与王丽是同学。(1)pq(1)pq(2)pq(2)pq(3)qp(3)qp(4)rs(4)rs(5)t(5)t10第10页，本讲稿共52页合取举例np：我们去看电影。q：房间里有十张桌子。pq：我们去看电影并且房间里有十张桌子。在数理逻辑中，关心的只是复合命题与构成复合命题在数理逻辑中，关心的只是复合命题与构成复合命题的各原子命题之间的真值关系，即抽象的逻辑关系，的各原子命题之间的真值关系，即抽象的逻辑关系，并不关心各语句的具体内容并不关心各语句的具体内容。说明说明11第11页，本讲稿共52页定义定义1.3 析取(disjunction)n设p，q为二命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词，并规定pq为假当且仅当p与q同时为假。自然语言中的自然语言中的“或或”具有二义性，用它联结的命题有具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别时具有相容性，有时具有排斥性，对应的联结词分别称为相容或称为相容或和排斥或排斥或(排异或排异或)。说明说明pqpq1 11 11 11 10 01 10 01 11 10 000 012第12页，本讲稿共52页例将下列命题符号化(1)张晓静爱唱歌或爱听音乐。(2)张晓静只能挑选202或203房间。(3)张晓静是江西人或安徽人。(4)他昨天做了二十或三十道习题。(1)(1)设设 p p：张晓静爱唱歌，：张晓静爱唱歌，q q：张晓静爱听音乐。：张晓静爱听音乐。相容或，符号化为相容或，符号化为 p pq q(2)(2)设设t t：张晓静挑选：张晓静挑选202202房间，房间，u u：张晓静挑选：张晓静挑选203203房间。房间。排斥或，符号化为：排斥或，符号化为：(t tu u)()(t tu u)(3)(3)设设r r：张晓静是江西人，：张晓静是江西人，s s：张晓静是安徽人。：张晓静是安徽人。排斥或，符号化为：排斥或，符号化为：r rs s。(排斥或排斥或联结的两个命题事实上不可能同时为真联结的两个命题事实上不可能同时为真)或符号化为：或符号化为：(rs)(rs)(rs)(rs)(4)(4)原子命题，因为原子命题，因为“或或”只表示了习题的近似数目。只表示了习题的近似数目。13第13页，本讲稿共52页定义定义定义定义1.41.4 蕴涵蕴涵(implicationimplication)n设p，q为二命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词,并规定pq为假当且仅当p为真q为假。说明说明qpq的的逻辑逻辑关系表示关系表示q是是p的必要条件。的必要条件。qq是是p的必要条件有的必要条件有许许多不同的叙述方式多不同的叙述方式只要只要p，就，就q因因为为p，所以，所以qp仅仅当当q只有只有q才才p除非除非q才才p除非除非q，否，否则则非非ppqp q1 11 11 11 10 00 00 01 11 10 001 114第14页，本讲稿共52页例例 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值 (1)如果3+36，则雪是白的。(2)如果3+36，则雪是白的。(3)如果3+36，则雪不是白的。(4)如果3+36，则雪不是白的。解：令解：令p p：3+33+36 6，p p的真值为的真值为1 1。q q：雪是白色的，：雪是白色的，q q的真值也为的真值也为1 1。(1)pq(2)(2)pq(3)pq(4)(4)pq110115第15页，本讲稿共52页例例 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值 以下命题中出现的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 r：a a能被能被4 4整除整除 s s：a a能被能被2 2整除整除 (5)(5)至至(9)(9)五个命题均叙述的是五个命题均叙述的是a a能被能被2 2整除是整除是a a能被能被4 4整除的必要条件整除的必要条件，因而都符号化为因而都符号化为r rs s。其真值为。其真值为1 1在在(10)(10)中，中，将将a a能被能被4 4整除看成了整除看成了a a能被能被2 2整除的必要条件整除的必要条件，因而应符号因而应符号化为化为s sr r。a a值不定时，真值未知。值不定时，真值未知。16第16页，本讲稿共52页关于蕴含的进一步说明n作为一种规定，当p为假时，无论q是真是假，pq均为真。也就是说，只有p为真q为假这一种情况使得复合命题pq为假。称为实质蕴含。n例：如果x5，则x2。(1)x=6如果65，则62。(2)x=3 如果35，则32。(3)x=1 如果15，则12。n例：如果我有车，那么我去接你n常出现的错误，没有分清充分条件与必要条件。17第17页，本讲稿共52页定义定义定义定义1.51.5 等价等价(two-way-implicationtwo-way-implication)n设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词，并规定pq为真当且仅当p与q同时为真或同时为假。说明说明q“当且仅当当且仅当”（if and only if）qp pq q的逻辑关系为的逻辑关系为p p与与q q互为充分必要条件。互为充分必要条件。q(pq)(qp)(pq)(qp)与与p pq q的逻辑关系完全一致。的逻辑关系完全一致。pqp q1 11 11 11 10 00 00 01 10 00 001 118第18页，本讲稿共52页关于基本联结词的说明n,，称为一个联结词集。n由联结词集,中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以称它们为基本的复合命题。n基本复合命题的真值见下表：19第19页，本讲稿共52页关于基本联结词的说明n多次使用联结词集中的联结词，可以组成更为复杂的复合命题。n求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。n本书规定的联结词优先顺序为：()，对于同一优先级的联结词，先出现者先运算。20第20页，本讲稿共52页例令p：北京比天津人口多。q：2+24.r：乌鸦是白色的。求下列复合命题的真值：(1)(pq)(pq)r(2)(qr)(pr)(3)(pr)(pr)解：解：p p、q q、r r的真值分别为的真值分别为1 1、1 1、0 0(1)1(1)1(2)1(2)1(3)0(3)0我们关心的是复合命题中命题之间的真值关系，我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。而不关心命题的内容。说明说明21第21页，本讲稿共52页关于合式公式n(A)、(AB)等公式单独出现时，外层括号可以省去，写成A、AB等。n公式中不影响运算次序的括号可以省去，如公式(pq)(r)可以写成pqr。n合式公式的例子：(pq)(qr)(pq)rp(qr)n不是合式公式的例子pqr(p(rq)22第22页，本讲稿共52页赋值举例n在公式(p1p2p3)(p1p2)中，000(p10，p20，p30)，110(p11，p21，p30)都是成真赋值，001(p10，p20，p31)，011(p10，p21，p31)都是成假赋值。n在(pq)r中，011(p10，p21，p31)为成真赋值，100(p11，p20，p30)为成假赋值。n重要结论：含n(n1)个命题变项的公式共有2n个不同的赋值。23第23页，本讲稿共52页真值表求下列公式的真值表，并求成真赋值和成假赋值。(1)(pq)r(2)(pp)(qq)(3)(pq)qr 24第24页，本讲稿共52页定义1.10 重言式、永真式、可满足式设A为任一命题公式(1)若A在它的各种赋值下取值均为真,则称A是重言式(tautology)或永真式。(2)若A在它的各种赋值下取值均为假,则称A是矛盾式(contradiction)或永假式。(3)若A不是矛盾式,则称A是可满足式（satisfactable formula）。25第25页，本讲稿共52页例题下列各公式均含两个命题变项p与q，它们中哪些具有相同的真值表?(1)pq(4)(pq)(qp)(2)pq(5)qp(3)(pq)26第26页，本讲稿共52页哑元n设公式设公式A,B中共含有命题变项中共含有命题变项p1,p2,pn，而A或B不全含有这些命题变项，比如A中不含pi,pi+1,pn,称这些命题变项为A的哑元，A的取值与哑元的变化无关，因而在讨论A与B是否有相等的真值表时，将A,B都看成p1,p2,pn的命题公式。27第27页，本讲稿共52页例题 例1.10下列公式中,哪些具有相同的真值表?(1)pq(2)qr(3)(pq)(pr)p)(4)(qr)(pp)28第28页，本讲稿共52页自动推理自动推理29第29页，本讲稿共52页Resolutionn归结方法是一种机械化的,可在计算机上加以实现的推理方法n可认为是一种反向推理形式n提供了一种自动定理证明的方法30第30页，本讲稿共52页Resolution Refutations（1）n定理证明的任务:由前提A1 A2.An推出结论B即证明:A1 A2.AnB 永真n转化为证明:A1 A2.An B为永假式n归结推理就是:从A1 A2.An B出发,使用归结推理规则来找出矛盾,最后证明定理A1 A2.AnB的成立31第31页，本讲稿共52页Resolution Refutations（2）n定理证明的任务:由前提A1 A2.An推出结论B即证明:A1 A2.AnB 永真n转化为证明:A1 A2.An B为永假式n归结推理就是:从A1 A2.An B出发,使用归结推理规则来找出矛盾,最后证明定理A1 A2.AnB的成立32第32页，本讲稿共52页Resolution Refutations（3）n一般过程:1)建立子句集S2)从子句集S出发,仅对S的子句间使用归结推理规则3)如果得出空子句,则结束;否则转下一步4)将所得归结式仍放入S中5)对新的子句集使用归结推理规则6)转(3)n空子句不含有文字,它不能被任何解释满足,所以空子句是永假的,不可满足的n归结过程出现空子句,说明出现互补子句对,说明S中有矛盾,因此S是不可满足的.33第33页，本讲稿共52页Soundness and Completenessn归结原理是合理的n归结原理是完备的34第34页，本讲稿共52页归结原理概述n归结原理由J.A.Robinson由1965年提出。q与演绎法(deductiveinference)完全不同，新的逻辑演算(inductiveinference)算法。q一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。q语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）n本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。35第35页，本讲稿共52页命题逻辑的归结法n命题逻辑基础：定义：q合取式：p与q，记做p qq析取式：p或q，记做p qq蕴含式：如果p则q，记做p qq等价式：p当且仅当q，记做p q。36第36页，本讲稿共52页命题逻辑基础n定义：q若A无成假赋值，则称A为重言式或永真式；q若A无成真赋值，则称A为矛盾式或永假式；q若A至少有一个成真赋值，则称A为可满足的；q析取范式：仅由有限个简单合取式组成的析取式。q合取范式：仅由有限个简单析取式组成的合取式。37第37页，本讲稿共52页命题逻辑基础n基本等值式24个(1)q交换率：pq qp；p q q p q结合率：(pq)r p(q r);(p q)r p(q r)q分配率：p(q r)(pq)(p r)；p(q r)(p q)(p r)38第38页，本讲稿共52页命题逻辑基础n基本等值式（1）q摩根率:(pq)p q；(p q)p q q吸收率:p(pq)p；p(pq)pq同一律:p0 p；p1 pq蕴含等值式:p q pqq假言易位式:p q p q39第39页，本讲稿共52页命题表示公式例如：n1“如果我进城我就去看你，除非我很累。”设：p，我进城，q，去看你，r，我很累。则有命题公式：r(pq)。n2“应届高中生，得过数学或物理竞赛的一等奖，保送上北京大学。”设：p，应届高中生，q，保送上北京大学上学，r，是得过数学一等奖。t，是得过物理一等奖。则有命题公式公式：p(r t)q。40第40页，本讲稿共52页命题逻辑的归结法n基本单元：简单命题（陈述句）例：命题：A1、A2、A3 和 B求证：A1A2A3成立，则B成立，即：A1A2A3 B反证法：证明A1A2A3B 是矛盾式 （永假式）41第41页，本讲稿共52页命题逻辑的归结法n建立子句集q合取范式：命题、命题和的与，如：P（PQ）（PQ）子句集S：合取范式形式下的子命题（元素）的集合例：命题公式：P（PQ）（PQ）子句集 S：S=P,PQ,PQ 42第42页，本讲稿共52页命题逻辑的归结法n归结过程q将命题写成合取范式q求出子句集q对子句集使用归结推理规则q归结式作为新子句参加归结q归结式为空子句，S是不可满足的（矛盾），原命题成立。（证明完毕）n谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。43第43页，本讲稿共52页命题逻辑归结例题（1）n例题，证明公式：(PQ)(QP)n证明：（1）根据归结原理，将待证明公式转化成待归结命题公式：(PQ)(QP)（2）分别将公式前项化为合取范式：PQPQ结论求后的后项化为合取范式：(QP)(QP)QP两项合并后化为合取范式：（PQ）QP（3）则子句集为：PQ，Q，P44第44页，本讲稿共52页命题逻辑归结例题（2）子句集为：PQ，Q，P（4）对子句集中的子句进行归结可得：n1.PQn2.Qn3.Pn4.Q，（1，3归结）n5.，（2，4归结）由上可得原公式成立。45第45页，本讲稿共52页n证明证明：化成子句集：化成子句集 S=P,P QRS=P,P QR，SQSQ，TQTQ，T T，R R n归结可用图的演绎树表示，由于归结可用图的演绎树表示，由于根部出现空子句，因此命题根部出现空子句，因此命题R R得得证。证。n例：设已知前提集为例：设已知前提集为n P P (1)(PQ)R(1)(PQ)R(2)(2)n (ST)Q (ST)Q(3)T(3)T(4)(4)n求证求证R R。46第46页，本讲稿共52页命题逻辑在计算机科学中的应用命题逻辑在计算机科学中的应用 逻辑难题逻辑难题 可以用逻辑推理解决的难题称为可以用逻辑推理解决的难题称为逻逻辑难题辑难题。求解逻辑难题是实践逻辑规则的一种。求解逻辑难题是实践逻辑规则的一种好方法好方法涉及用于执行逻辑推理的计算机程序涉及用于执行逻辑推理的计算机程序通常也使用著名的逻辑难题来演示它们的能力通常也使用著名的逻辑难题来演示它们的能力47第47页，本讲稿共52页1.7 1.7 命题逻辑在计算机科学中的应用命题逻辑在计算机科学中的应用 爱因斯坦的一道题。一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘。这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快地说出自己头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来接着把电灯打开，这时那两个应试者看到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：“我戴的是黑帽子。”请问这个人猜得对吗？是怎么推导出来的？48第48页，本讲稿共52页命题逻辑在计算机科学中的应用命题逻辑在计算机科学中的应用 分析1：如果我戴的也是红帽子，那么，B就马上可以猜到自己是戴黑帽子(因为红帽子只有两顶)；而现在B并没有立刻猜到，可见，我戴的不是红帽子。可见，B的反应太慢了。49第49页，本讲稿共52页命题逻辑在计算机科学中的应用命题逻辑在计算机科学中的应用 分析2：设P1表示“猜对的人戴红帽子”；P2表示“猜对的人戴黑帽子”；Q1表示“另一个人戴红帽子”；Q2表示“另一个人戴黑帽子”；R1表示“商人戴红帽子”。现在知道，商人头上戴的是红帽子，即R1为真，又知道另一个人没有作出断定，即既不能断定Q1为真，也不能断定Q2为真。50第50页，本讲稿共52页命题逻辑在计算机科学中的应用命题逻辑在计算机科学中的应用 根据题设条件，可得如下公式：R1P1Q2：如果商人和猜对的人戴的都是红帽子，那么另一个戴的就是黑帽子，因为红帽子只有两顶。R1Q1P2：如果商人和另一个戴的都是红帽子，那么猜对的人戴的就是黑帽子。P1P2：如果猜对的人戴的不是红帽子，那么他戴的就是黑帽子。Q1Q2：如果另一个人戴的不是红帽子，那么他戴的就是黑帽子。51第51页，本讲稿共52页命题逻辑在计算机科学中的应用命题逻辑在计算机科学中的应用 推演步骤如下：（1）P1（根据假设）；（2）R1（根据题设）（3）R1P1（合取构成）；（4）R1P1Q2（根据题设）（5）Q2（3）（4）分离）。这就是说，“另一个人戴黑帽子”这个判定是必然可以作出的，但是这与题设条件（即“另一个没有作出判定”）相矛盾，因此，P1为假，即P1为真，故可得：（6）P1；（7）P1P2（根据题设）；（8）P2（6）（7）分离）。这就是说，“猜对的人戴着黑帽子”是真的，所以猜对的人肯定的说：“我戴的是黑帽子”。52第52页，本讲稿共52页