第四章谓词演算王元元.ppt

1 第四章 谓词演算 2 重点 谓词及谓词演算永真式掌握谓词的概念 掌握两种量词及其用法 掌握谓词公式的定义 掌握基本的谓词演算的等价式和蕴涵式 3 谓词演算引入的必要性 命题逻辑以由原子命题通过联结词构成的复合命题为讨论对象 不再对原子命题作进一步的分析 即命题逻辑只讨论以原子命题为基本元素的复合命题之间的推理关系 这种逻辑体表达能力很弱 4 谓词演算引入的必要性 例如 考虑下面的语句 p n是一个奇数 再例 在命题演算中 对下述论断无法判断其正确性 苏格拉底三段论 所有的人都是要死的 苏格拉底是人 所以苏格拉底是要死的 5 类似的例还有许多 例如 所有的人都要呼吸 所有的正整数都大于0 李莉是人 3是正整数 所以李莉要呼吸 所以3大于0 谓词演算引入的必要性 6 只有对简单命题做进一步剖析 才能认识这种推理规律 这就需要引入个体 谓词 引入变量并考虑到表示变量的数量上一般与个别的全称量词和存在量词 进而研究它们的形式结构和逻辑关系 这便构成了谓词演算 谓词演算引入的必要性 7 4 1谓词演算基本概念 在谓词演算中 可将原子命题分解为谓词与个体词两部分 4 1 1个体与个体域1 定义 一切讨论对象都称为个体注意 它们可以是客观世界中的具体客体 也可以是抽象的客体 诸如数字 符号等 8 2 分类个体常元表示具体或特定的个体称为个体常元 常用a b c等小写字母或字母串表示 个体变元表示抽象的 或泛指的 或者说取值不确定的 个体称为个体变元 常用字母x y z u v w等来表示 4 1 1个体与个体域 9 4 1 1个体与个体域 3 个体域 D 个体的全体 即 个体变元的取值范围 并约定任何D都至少含有一个成员 注意 当讨论对象遍及一切客体时 个体域特称为全总域 universe 用字母U表示 10 4 1 2谓词与谓词填式 1 定义 语句中表示个体性质或关系的语言成分 通常是谓语 称为谓词 谓词所携空位的数目称为谓词的元数 一元谓词表达了个体的性质 而多元谓词表达了个体间的关系 11 4 1 2谓词与谓词填式 例如 1 李明是学生 2 张亮比陈华高 3 陈华坐在张亮与李明之间 在这三个命题中 李明 张亮 陈华都是个体 是学生 是一元谓词 比 高 是二元谓词 坐 与 之间 是三元谓词 12 4 1 2谓词与谓词填式 例如 1 苏格拉底是人 中的 是人 2 苏格拉底是要死的 中的 是要死的 3 实数的平方非负 中的 是实数 是非负的 4 董旎生于青岛 中的 生于 5 3小于2 中的 小于 6 3 5 8 中的 13 4 1 2谓词与谓词填式 2 表示 谓词演算中用携有空位的大写字母表示谓词 字母的选择是随意的 以方便记忆为好 M 表示 是人 L 表示 小于 ADD 表示 谓词命名式 用变元来表示谓词的空位 如M x ADD x y z 14 4 1 2谓词与谓词填式 3 谓词填式谓词的空位上填入个体 如 M 张三 ADD 2 3 5 谓词填式P t1 tn 表示 个体项t1 tn所代表的个体满足n元谓词P x1 xn 注意 当空位处填入变元时 谓词命名式与谓词填式同形 但它们表示不同的意义 15 4 1 2谓词与谓词填式 当谓词填式中所填个体都是常元时 它是一个命题 因而有确定的真值 如 ADD 2 3 5 L 3 2 一些复杂的性质和关系 可以用谓词和联结词复合的形式来描述 例如 如果一个人生于北京 那么他不生于上海 可表示为B x beijing B x shanghai 16 4 1 3量词及其辖域 使用前面介绍的概念 还不足以表达日常生活中的各种命题 例如 对于命题 所有的正整数都是素数 和 有些正整数是素数 仅用个体词和谓词是很难表达的 17 4 1 3量词及其辖域 1定义 量词在命题里表示数量的词 1 全称量词 如 所有人都是要死的 可表示为 xD x x的个体域为全体人的集合 18 4 1 3量词及其辖域 2 存在量词 如 有些有理数是整数 令I x x是整数 于是命题可表示为 xI x 其中x的个体域为有理数集合 19 指导变元 辖域与约束变元 在公式 xA 和 xA中 x是指导变元A为相应量词的辖域在辖域中出现的x为约束变元其他变元为自由变元注A可为一谓词填式或复合的谓词表达式式 20 例1 指出下列谓词公式中的量词及其辖域 指出各自由变元和约束变元 并回答它们是否是命题 P x y x P x B x y P x 解 全称量词 辖域 x P x B x y 其中y为约束变元 存在量词 辖域P x B x y 其中x为约束变元 不在量词辖域中的P x 中的x为自由变元 P x y x P x B x y P x 不是命题 21 说明 1 量词的指导变元和量词 管辖 的谓词填式中的变元是可以改名 rename 的 2 量词不仅可用于谓词填式之前 还可用于复合的谓词表达式之前 这时应对该表达式使用括号 例如 x M x B x 22 说明 3 量词的指导变元和量词辖域内的约束变元与通常谓词填式中的个体变元不同 因为它可以改名却不能取值代入 例如 5P 5 都是毫无意义的 因此 我们把 xP x 和 xP x 中变元称为约束变元 boundvariables 而那些可以取值代入的变元则称为自由变元 freevariables 综合 1 3 可知 约束变元是形式记号的一部分 对它可以改名但不能代入 其实数学中常常使用这种约束变元作为数学符号的一部分 23 说明 4 对于一元谓词P x xP x 为一命题 它断言所有个体满足性质P x 其真值已经确定 同理 xP x 也是命题 24 说明 例 D表示某班全体学生 G x 表示x是男生 xG x 全班每个人都是男生 xG x 全班存在一个人是男生 含量词的谓词公式的真值不在依赖于x的取值 25 说明 特别是 当个体域中个体有穷时 例如D a1 an 的意义与命题P a1 P an 等同 而 xP x 的意义与命题P a1 P an 等同 例D 0 1 2 y y2 y y y2 y 26 例2 对个体域 0 1 判定下列公式的真值 E x 表示 x是偶数 1 x E x x 1 解 1 x E x x 1 真 x E x x 1 可表示成命题公式 E 0 0 1 E 1 1 1 其中E 0 0 1真 E 1 1 1也真 故 E 0 0 1 E 1 1 1 真 27 4 1 4谓词公式及语句的形式化 定义4 1归纳定义谓词公式 predicateforrmula 谓词公式又称合式公式 简称公式 1 谓词填式是公式 命题常元是公式 看作零元谓词 常称原子公式 2 如果A B是公式 x为任一变元 那么 A A B A B A B A B xA xA 都是公式 3 只有有限步使用 1 2 条款所形成的符号串是公式 28 括号省略原则同命题公式 并约定 xA xA 中最外层括号也可省略 1 公式最外层括号一律可省略 2 联结词的结合能力强弱依次为 表示 与 平等 3 结合能力平等的联结词在没有括号表示其结合状况时 采用左结合约定 29 例 依定义 p P x y Q y x A x B x x A x yB x y 都是谓词公式 注意 yL 3 2 也是公式 一般地 当A中无变元x时 xA xA 均被看作与A相同 30 1 当个体域给定 2 谓词公式中的谓词都有明确意义 关于个体域中个体的某个性质或关系 3 并且在谓词公式中自由变元均已取定个体谓词公式也就具有了确定的意义 成了关于个体域的一个断言 可判定其真值 谓词公式 31 例4 3 设D为实数域 E x y 表示D上关系 x y L x y x y那么 1 xL 0 x2 1 4 xE x2 y 允许常用的数学符号表示谓词 例如用x y代替L x y x2 y代替E x2 y 32 7 x y x y 0 8 y x x y 0 9 y x x y 0 10 x y x y 0 例4 3 33 使用计算机来处理由自然语句或非形式化陈述的问题 首要的是工作是问题本身的形式描述 命题逻辑的表达问题的能力 仅限于联结词的使用 而谓词逻辑由于个体 谓词 量词和函数的引入具有强得多的表达问题的能力 已成为描述计算机所处理的知识的有力工具 人工智能学科将谓词逻辑看作是一种基本的知识表示方法和推理方法 4 1 4语句的形式化 34 使用谓词逻辑描述以自然语句表达的问题 首先要将问题分解成一些原子谓词 引入谓词符号 进而使用量词 函数 联结词来构成合式公式 这种形式描述是进而作推理的先决条件 所以从实用角度显得十分重要 4 1 4语句的形式化 35 例 个体域是人类 1 人人都能骗Fred 2 Mary能骗所有人 3 没有人能骗所有人 4 人人都会被人骗 5 勇敢者未必都是成功者 6 有人勇敢 但不是所有的人都勇敢 7 人人都不互相依靠 但互相帮助 8 我为人人 人人为我 9 每个人都有人爱 但没有人为所有人爱 4 1 4语句的形式化 36 语句形式化过程的三个关键问题是 1 准确地从语句中提取谓词 表示性质的谓语用一元谓词表示 表示关系的谓语用二元或更多元数的谓词来表示 2 准确地使用量词和确定量词的辖域 当辖域中多于一个谓词时必须注意括号的使用 3 准确地使用多个重叠的量词 其排列次序应与原语句意义一致 37 在全总域讨论 首先 在讨论个体域的某个局部的所有个体或某些个体时 要使用把量词限于该局部的所谓 限定谓词 其次 限定谓词与其它谓词之间应使用适当的联结词 当限定谓词用于限定全称量词时 它必须作为蕴涵词的前件加入 当限定谓词用于限定存在量词时 它必须作为合取词的合取项加入 38 例 1 所有的人都是要呼吸的 2 有人勇敢 4 1 4语句的形式化 39 例 3 所有的有理数都是实数 4 有的狮子不凶猛 4 1 4语句的形式化 40 例 5 没有不犯错误的人 6 实数的加运算满足交换律 4 1 4语句的形式化 41 例 7 每列火车都比某些汽车快 8 某些汽车比所有的火车慢 4 1 4语句的形式化 42 例9 苏格拉底三段论可用谓词公式表示 令M x x是人 D x x是要死的 a 苏格拉底 则三段论可表示为 x M x D x M a D a 43 4 2 1谓词公式的真值规定 1 x M x B x 2 x ax2 bx c 0 3 x ax2 bx c 0 y 1 4 2谓词演算永真式 44 4 2 1谓词公式的真值规定 谓词公式的真值不仅依赖于个体域 依赖于对公式中谓词符号 函数符号 常元符号所作的解释 即符号与个体域上具体性质 关系 函数 对象间的映射 常用I表示一种解释 I恒把命题常元解释为真值0或1 还依赖于公式中各自由变元的取值状况 45 4 2 1谓词公式的真值规定 例4 6分别给定个体域D1 3 4 D2 3 5 以及解释I1I2 I1把P x 解释为 x是质数 I2把P x 解释为 x是合数 时的情况 分别讨论P x yP y 和 yP y P x 的真值 46 4 2 1谓词公式的真值规定 47 真值概念 定义4 2给定个体域D及公式A中各谓词符号的解释I 如果A中个体变元x1 xn分别取值u1 un时A真 则称A在u1 un处真 当x1 xn无论取D中怎样的个体u1 un A在u1 un处均真 则称A在解释I下真 48 真值概念 定义4 3给定个体域D 若公式A在每一解释I下均真 那么称A在D上永真 若公式A对任何个体域D均有D上永真 则称A为永真式 或称A永真 valid A永真仍记为 A 49 沿用命题演算中引入一些符号和称谓 A B表示 A B 永真 称A逻辑蕴涵B A B当且仅当对任意个体域和解释 一切使A真的变元取值状况均使B亦真 A同前 可作类似的定义 A B表示 A B 永真 称A逻辑等价B A B当且仅当对一切域 解释和变元取值状况 A与B都具有相同的真值 真值概念 50 真值概念 定义4 4公式A称为可满足的 如果对某一个体域 某一解释和变元的某一取值状况 A在此处取值真 公式A不可满足时也称A为永假式 当公式A永真时 A必定是永假式 51 例试说明下列各公式的类型 个体域取为全总个体域 1 F x 其中F x x 6 5 2 x F x F x 52 1 所有重言式用谓词公式去取代命题演算中逻辑等价式或逻辑蕴涵式的命题变元时 便得到谓词演算的逻辑等价式或逻辑蕴涵式 4 2 2谓词演算永真式 53 由于谓词演算中允许使用命题常元 因而谓词公式中仍包含命题公式 其中的重言式显然在谓词演算中仍然是永真式 1 所有重言式 54 例4 8A x A x A A A xA x xA x xA x 1 所有重言式 55 xA A xA A由于A与自由变元x无关 根据我们的约定两式显然成立 2 当A不含自由变元x时 56 xA x A x A x xA x xA x xA x 3 57 量词与否定词交换 xA x x A x xA x x A x x A x xA x x A x xA x 4 否定型逻辑等价式 58 在 1 2 域上分析 xA x A 1 A 2 A 1 A 2 x A x xA x A 1 A 2 A 1 A 2 x A x 这样看来 否定词越过量词的内移规律 就是摩根律的推广 59 例4 9 x y z x y z x y z x y z x y z x y z x y z x y z 60 xA x B x A x B xA x B x A x B xA x B x A x B xA x B x A x B 这是一组量词对 的分配律 其中B是命题变元与个体变元x无关 这是很重要的条件 5 量词对 的分配率 61 6 量词 对 量词 对 的分配率 这是当A x B x 都含有个体变元x时 量词 对 量词 对 所遵从的分配律 然而 对 对 的分配律一般并不成立 x A x B x xA x xB x x A x B x xA x xB x xA x xB x x A x B x x A x B x xA x xB x 62 证明 xA x xB x x A x B x 证 对任一个体域D和解释I 若 xA x xB x 真 那么或者 a xA x 真 即对一切个体d D A d 真 从而A d B d 真 故有 x A x B x 真 b xB x 真时 同理可证 x A x B x 亦真 63 证明 xA x xB x