谓词逻辑与归结原理1

《谓词逻辑与归结原理1》由会员分享，可在线阅读，更多相关《谓词逻辑与归结原理1（52页珍藏版）》请在金锄头文库上搜索。

1、大工软院06级选修课 人工智能 （by Weifeng Sun, ）人工智能基础谓词逻辑与归结原理1归结 推理命题 逻辑谓词逻 辑Skolem标准形、 子句集基本 概念谓词逻辑 归结原理合一和置换、 控制策略数理 逻辑命题逻辑 归结Herbrand 定理2命题与联结词n称能判断真假而不是可真可假的陈述句为命题 （proposition）。n作为命题的陈述句所表达得的判断结果称为命 题的真值。n真值只取两个：真与假。n真值为真的命题称为真命题。n真值为假的命题称为假命题。q感叹句、疑问句、祈使句都不能称为命题。q判断结果不唯一确定的陈述句不是命题。q陈述句中的悖论不是命题。说 明3q4是素数。q

2、 qx大于y。q充分大的偶数等于两 个素数之和。q今天是星期二。q q请不要吸烟！q这朵花真美丽啊！q我正在说假话。例1.1 判断下列句子是否为命题。 (1)是，假命题(2)是，真命题(3)不是，无确定的真值(4)是，真值客观存在(5)是，真值根据具体情 况而定。(6)不是，疑问句(7)不是，祈使句(8)不是，感叹句(9)不是，悖论 4命题和真值的符号化n用小写英文字母p,q,r,pi ,qi ,ri 表示命题n用“1”表示真，用“0”表示假 r：充分大的偶数等于两个素数之 和。s：今天是星期二。p：4是素数。q：q 不能被分解成更简单的陈述句，称这样的命题为简单命题或 原子命题。q 由简单陈

3、述句通过联结词而成的陈述句，称这样的命题为复 合命题。 5例将下面这段陈述中所出现的原子命题符号化，并指出它 们的真值，然后再写出这段陈述。 是有理数是不对的；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。6n半形式化形式n数理逻辑研究方法的主要特征是将论述或推 理中的各种要素都符号化。即构造各种符号 语言来代替自然语言。n形式化语言：完全由符号所构成的语言。n将联结词（connective）符号化

4、，消除其二义 性，对其进行严格定义。n例如： 他是100米或400米赛跑的冠军。 鱼香肉丝或锅包肉，加一碗汤。7定义1.1 否定(negation)n设p为命题，复合命题“非p”( 或“p的否定”)称为p的否定式, 记作p，符号称作否定联 结词，并规定p为真当且仅 当p为假。 例如：p： 哈尔滨是一个大城市。 p：哈尔滨是一个不大城市。p：哈尔滨不是一个大城市。pp10018定义1.2 合取(conjunction)n设p,q为二命题，复合命题 “p并且q”(或“p与q”)称为p与 q的合取式，记作pq， 称作合取联结词，并规定 pq为真当且仅当p与q同 时为真。使用合取联结词时要注意的两点：

5、1) 描述合取式的灵活性与多样性。 自然语言中的“既又”、“不但而且”、 “虽然但是”、“一面一面”等联结词都 可以符号化为。2) 分清简单命题与复合命题。 不要见到“与”或“和”就使用联结词。 pqpq1111000100009例 将下列命题符号化吴颖既用功又聪明。吴颖不仅用功而且聪明 。吴颖虽然聪明，但不用 功。张辉与王丽都是三好学 生。张辉与王丽是同学。 p: 吴颖用功。 q: 吴颖聪明。 r: 张辉是三好学生。 s: 王丽是三好学生。 t: 张辉与王丽是同学。 (1)pq (2)pq (3)qp (4)rs (5)t10合取举例np：我们去看电影。 q：房间里有十张桌子。 pq：我们去

6、看电影并且房间里有十 张桌子。 在数理逻辑中，关心的只是复合命题与构成复合 命题的各原子命题之间的真值关系，即抽象的逻 辑关系，并不关心各语句的具体内容。说 明11定义1.3 析取(disjunction)n设p，q为二命题，复合 命题“p或q”称作p与q的析 取式，记作pq，称 作析取联结词，并规定 pq为假当且仅当p与q 同时为假。 自然语言中的“或”具有二义性，用它联结的命 题有时具有相容性，有时具有排斥性，对应的联 结词分别称为相容或和排斥或(排异或)。 说 明pqpq11110101100012例将下列命题符号化 q张晓静爱唱歌或爱听音乐。q张晓静只能挑选202或203房间。q张晓静

7、是江西人或安徽人。q他昨天做了二十或三十道习题。 (1)设 p：张晓静爱唱歌，q：张晓静爱听音乐。 相容或，符号化为 pq(2)设t：张晓静挑选202房间， u：张晓静挑选203房间。 排斥或，符号化为：(tu)(tu)(3)设r：张晓静是江西人， s：张晓静是安徽人。 排斥或，符号化为：rs。 (排斥或联结的两个命题事实上不可能同时为真) 或符号化为：(rs)(rs)(4)原子命题，因为“或”只表示了习题的近似数目。13定义1.4 蕴涵(implication)n设p，q为二命题，复合命题“ 如果p，则q”称作p与q的蕴涵 式，记作pq，并称p是蕴涵 式的前件，q为蕴涵式的后件 ，称作蕴涵联

8、结词,并规定 pq为假当且仅当p为真q为 假。 说 明qpq的逻辑逻辑 关系表示q是p的必要条件。 qq是p的必要条件有许许多不同的叙述方式 只要p，就q 因为为p，所以q p仅仅当q只有q才p除非q才p除非q，否则则非p pqp q11110001100114例 将下列命题符号化，并指出其真值 q如果3+36，则雪是白的。q如果3+36，则雪是白的。q如果3+36，则雪不是白的。q如果3+36，则雪不是白的。解：令p：3+36，p的真值为1。q：雪是白色的，q的真值也为1。 (1) pq (2)pq (3) pq (4) pq110115例 将下列命题符号化，并指出其真值 以下命题中出现的a

9、是一个给定的正整数： (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值不定时，真值未知。16关于蕴含的进一步说明n作为一种规定，当p为假时

10、，无论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定义1.5 等价(two-way-implication)n设p，q为二命题，复合 命题“p当且仅当q”称作p 与q的等价式，记作pq ，称作等价联结词，并规 定pq为真当且仅当p与 q同时为真或同时为假。说 明q“当且仅当”（if and only if）q pq的逻辑关系

11、为p与q互为充分必要条件。 q (pq)(qp)与pq的逻辑关系完全一致。pqp q11110001000118关于基本联结词的说明n,，称为一个联结词集。n由联结词集,中的一个联结词联 结一个或两个原子命题组成的复合命题是最 简单的复合命题，可以称它们为基本的复合 命题。 n基本复合命题的真值见下表： 19关于基本联结词的说明n多次使用联结词集中的联结词，可以组成更 为复杂的复合命题。 n求复杂复合命题的真值时，除依据上表外， 还要规定联结词的优先顺序，将括号也算在 内。n本书规定的联结词优先顺序为：( )， ， ，对于同一优先级的联结词， 先出现者先运算。 20例令 p：北京比天津人口多

12、。 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我们关心的是复合命题中命题之间的真值关系， 而不关心命题的内容。 说 明21关于合式公式n(A)、(AB)等公式单独出现时，外层括号可以 省去，写成A、AB等。n公式中不影响运算次序的括号可以省去， 如公式(pq)(r)可以写成pqr。 n合式公式的例子： (pq)(q r) (pq)r p(qr)n不是合式公式的例子 pqr (p(rq) 22赋值举例n在公式(p1p2p3)(p1p

13、2)中， 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真值表求下列公式的真值表，并求成真赋值和成 假赋值。 (1)(pq)r (2)(pp)(qq) (3)(pq)qr 24定义1.10 重言式、永真式、可满足式设A为任一命题公式 (1)若A在它的各种赋值下取值均为真,则称A是 重言式(tau

14、tology)或永真式。 (2)若A在它的各种赋值下取值均为假,则称A是 矛盾式(contradiction)或永假式。 (3)若A不是矛盾式,则称A是可满足式（ satisfactable formula）。 25例题下列各公式均含两个命题变项p与q，它们 中哪些具有相同的真值表? (1) pq(4) (pq)(qp) (2) pq(5) qp (3) (pq) 26哑元n设公式A,B中共含有命题变项 p1,p2,pn，而A或B不全含有这些命 题变项，比如A中不含pi,pi+1,pn ,称 这些命题变项为A的哑元，A的取值与 哑元的变化无关，因而在讨论A与B是 否有相等的真值表时，将A,B都

15、看成 p1,p2,pn的命题公式。 27例题 例1.10 下列公式中,哪些具有相同的 真值表? (1)pq (2)qr (3)(pq)(pr)p) (4)(qr)(pp) 28自动推理29Resolutionn归结方法是一种机械化的,可在计算机 上加以实现的推理方法n可认为是一种反向推理形式n提供了一种自动定理证明的方法30Resolution Refutations（1）n定理证明的任务: 由前提A1 A2 . An 推出结论B 即证明:A1 A2 . AnB 永真n转化为证明: A1 A2 . An B为永假式n归结推理就是:从A1 A2 . An B出 发,使用归结推理规则来找出矛盾,最后证明 定理A1 A2 . AnB的成立31Resolution Refutations（2）n定理证明的任务: 由前提A1 A2 . An 推出结论B 即证明:A1 A2 . AnB 永真n转化为证明: A1 A2 . An B为永假式n归结推理就是:从A1 A2 . An B出 发,使用归结推理规则来找出矛盾,最后证明 定理