谓词逻辑与归结原理.ppt

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