第二章谓词逻辑.ppt

离散数学 国际学院孙延鹏Email meng yu sun 2020 2 22 国际学院 2 解 假设 著名的苏格拉底三段论 设自然语言中的三个命题 所有的人都是要死的 苏格拉底是人 所以 苏格拉底是要死的 P 所有的人都是要死的 Q 苏格拉底是人 R 所以 苏格拉底是要死的 则有 P Q R但在上述式子中 取P 1 Q 1 R 0 此时 R不是P Q的逻辑结果 第二章 谓词逻辑 2020 2 22 国际学院 3 一个推理 得出矛盾的结论 问题在哪里呢 问题就在于这类推理中 各命题之间的逻辑关系不是体现在原子命题之间 而是体现在构成原子命题的内部成分之间 即体现在命题结构的更深层次上 对此 命题逻辑是无能为力的 所以 在研究某些推理时 有必要对原子命题作进一步分析 分析出其中的个体词 谓词和量词 研究它们的形式结构的逻辑关系 正确的推理形式和规则 这些正是谓词逻辑的基本内容 2020 2 22 国际学院 4 2 1 谓词的基本概念与表示 例2 1 如有句子 张红是一个大学生 王南是一个大学生 李华是一个大学生 则在命题中必须要用三个命题P Q R来表示 但是 它们都具有一个共同的特征 是一个大学生 因此 若将句子分解成 主语 谓语 用P表示 是一个大学生 P后紧跟 某某人 则上述句子可写为 P 张红 P 王南 P 李华 一般地 P x x是一个大学生 P 谓词x 个体词P x 命题函数 2020 2 22 国际学院 5 2 1 1 谓词定义2 1 在句子中 可以独立存在的客体称为个体词 而用以刻划客体的性质或客体之间的关系即是谓词 个体词用a b c x y z a1 a2 a3等表示 谓词用A B C P Q R A1 A2 A3 等表示 例 上海 教师 班级 电子计算机等等都是个体词 2020 2 22 国际学院 6 成都是一个省会城市 离散数学是计算机的基础课程 刘东是一个游泳健将 人是聪明的 例2 2 2020 2 22 国际学院 7 表示具体或特定的个体词称为个体常量 一般个体词常量用带或不带下标的小写英文字母a b c a1 a2 a3 表示 表示抽象的或泛指的个体词称为个体变量 一般用带或不带下标的小写英文字母x y z x1 x2 x3 表示 个体词的取值范围称为个体域或论域 常用D表示 而宇宙间的所有个体域聚集在一起所构成的个体域称为全总个体域 设D为非空的个体域 定义在Dn 表示n个个体都在个体域D上取值 上取值于 0 1 上的n元函数 称为n元命题函数或n元谓词 记为P x1 x2 xn 此时 个体变量x1 x2 xn的定义域都为D P x1 x2 xn 的值域为 0 1 定义2 2 2020 2 22 国际学院 8 设有如下命题 P 上海是一个现代化的城市 Q 甲是乙的父亲 R 3介于2和5之间 T 李兰与高翔是同班同学 解 设有如下命题函数 C x x是一个现代化的城市 F x y x是y的父亲 B x y z x介于y和z之间 S x y x与y是同班 例2 3 2020 2 22 国际学院 9 则上述命题可表示为 P C 上海 Q F 甲 乙 R B 3 2 5 T S 李兰 高翔 上述符号P Q R T表示的是命题 而符号C 上海 F 甲 乙 B 3 2 5 S 李兰 高翔 则是命题所对应的谓词表示形式 它们都有确切的真值 2020 2 22 国际学院 10 a 上海 b 甲 c 乙 d 3 e 2 f 5 g 李兰 h 高翔 则上述命题又可表示为 P C a Q F b c R B d e f T S g h 2020 2 22 国际学院 11 例2 4 设S x 表示 x是大学生 D 某大学班级中的学生 则S x 是永真式 D 某中学里班级中的学生 则S x 是永假式 D x是所有的中国人 则这些人中有的是大学生 有的不是大学生 那么对有些人来讲 S x 为真 对另外一些x来说 S x 为假 2020 2 22 国际学院 12 谓词中个体词的顺序是十分重要的 不能随意变更 一元谓词用以描述某一个个体的某种特性或性质 而n元谓词则用以描述n个个体之间的关系 0元谓词 不含个体词的 实际上就是一般的命题 几个结论 2020 2 22 国际学院 13 4 具体命题的谓词表示形式和n元命题函数 n元谓词 是不同的 前者是有真值的 而后者不是命题 它的真值是不确定的 如上例中C 上海 是有真值的 但C x 却没有真值 5 一个n元谓词不是一个命题 但将n元谓词中的个体变元都用个体域中具体的个体取代后 就成为一个命题 而且 个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响 2020 2 22 国际学院 14 2 2量词 例2 5符号化下述命题 所有的老虎都要吃人 每一个人都会犯错误 有一些人会摔跤 有一些人是大学生 每一个带伞的人都不怕雨 有一些自然数是素数 上述每一个描述量词的语句下划有 下划线 2020 2 22 国际学院 15 例2 5 续 解 设立如下谓词 R x x会吃人 P x x会犯错误 N x x会摔跤 Q x x是大学生 C x x不怕雨 S x x是素数 则有 1 所有的x R x x 老虎 2 每一个x P x x 人 3 有一些x N x x 人 4 有一些x Q x x 人 5 每一个x C x x 带伞的人 6 有一些x S x x 自然数 2020 2 22 国际学院 16 量词的定义 上述一系列例子 都仅仅只符号化了一部分内容 而对句子中的 对每一个 对任意的 有一些 等等无法用谓词来表示 这些都是与个体词的数量有关的语句 为了把它们符号化 引进如下两个符号 x 所有的x x 有些x 任意的x 至少有一个x 一切的x 存在x 每一个x 等等 等等 补充 符号 称为存在唯一量词符 用来表达 恰有一个 存在唯一 等词语 x称为存在唯一量词 称x为指导变元 2020 2 22 国际学院 17 量词的定义 定义2 3 x 称为全称量词 x 为存在量词 其中的x称为作用变量 一般将其量词加在其谓词之前 记为 x F x x F x 此时 F x 称为全称量词和存在量词的辖域 仅跟量词之后的谓词为此量词的辖域 2020 2 22 国际学院 18 例2 5 续 x R x x 老虎 x P x x 人 x N x x 人 x Q x x 人 x C x x 带伞的人 x S x x 自然数 三段论中的P也可表示为 x H x D x 在例2 5中 利用量词则有 2020 2 22 国际学院 19 不便之处 从书写上十分不便 总要特别注明个体域 在同一个比较复杂的句子中 对于不同命题函数中的个体可能属于不同的个体域 此时无法清晰表达 如讨论求上述例中 1 和 3 的合取而得的新命题有 x R x x Q x 其中 全称量词中的x 苹果 存在量词中的x 实数 有时 由于个体域的注明不清楚 造成无法确定其真值 对于同一个公式 不同的个体域有可能带来不同的真值 如 x x 6 5 1 在实数范围内时 确有x 1使得x 6 5 因此 x x 6 5 为 真 2 在正整数范围内时 则找不到任何x 使得x 6 5为 真 所以 x x 6 5 为 假 2020 2 22 国际学院 20 全总个体域 对于全称量词 刻划其对应个体域的特性谓词作为蕴涵的前件加入 对于存在量词 刻划其对应个体域的特性谓词作为合取式之合取项加入 基于上述情况 必需要对个体域进行统一 全部使用全总个体域 此时 对每一个句子中个体变量的变化范围用一定之特性谓词刻划之 而统一成全总个体域后 此全总个体域在谓词公式中就不必特别说明 常常省略不记 同时 这种特性谓词在加入到命题函数中时必定遵循如下原则 2020 2 22 国际学院 21 例2 5 续 解 U x x是老虎 x U x R x H x x是人 x H x P x H x x是人 x H x N x H x x是人 x H x Q x M x x是带伞的人 x M x L x T x x是自然数 x T x S x 对于例2 5中的例子运用特性谓词描述 上述三段论可完整翻译为 x H x D x H S D S 2020 2 22 国际学院 22 2 3谓词公式与解释 同命题演算一样 在谓词逻辑中也同样包含命题变元和命题联结词 为了能够进行演绎和推理 为了对谓词逻辑中关于谓词的表达式加以形式化 利用联结词 谓词与量词构成命题函数 我们必须引入公式的概念 2020 2 22 国际学院 23 四类符号 常量符号 一般用a b c a1 b1 c1 来表示 它可以是D中的某个元素 变量符号 一般用x y z x1 y1 z1 来表示 它可以取值于D中的任意元素 函数符号 普通函数 一般用f g h f1 g1 h1 来表示 n元函数符号f x1 x2 xn 可以是Dn D的任意一个函数 谓词符号 命题函数 一般用P Q R P1 Q1 R1 来表示 n元谓词符号P x1 x2 xn 可以是Dn 0 1 的任意一个谓词 2020 2 22 国际学院 24 例2 6 1 设 f x y x y N x x是自然数 则f 4 6 表示个体常量 10 而N f 4 6 表示 10 是自然数 2 设 f x x的父亲 P x x是教授 c 周红则P f c 表示 周红的父亲是教授 这一命题 2020 2 22 国际学院 25 2 3 1谓词的合式公式 定义2 6满足下列条件的表达式 称为合式公式 简称公式 定义2 5 形如Q Q x Q x y Q a y Q f x y 等公式是原子谓词公式 简称原子公式 原子公式是合式公式 若G H是合式公式 则 G H G H G H G H G H 也是合式公式 若G是合适公式 x是个体变量 则 x G x G也是合式公式 仅仅有1 3 产生的表达式才是合式公式 2020 2 22 国际学院 26 P x Q x y R x a f z p x R y x P x 等都是公式 而 P x R x x x P x 等则不是公式 例2 7 2020 2 22 国际学院 27 1 天下乌鸦一般黑 2 那位身体强健的 用功的 肯于思考的大学生 解决了一个数学难题 3 张强和李平都是足球运动员 4 每个实数都存在比它大的另外的实数 5 并非所有的动物都是脊椎动物 6 尽管有人很聪明 但未必一切人都聪明 7 对于任意给定的 0 必存在着 0 使得对任意的x 只要 x a 就有 f x f a 成立 例2 8符号化下述语句 2020 2 22 国际学院 28 解 1 天下乌鸦一般黑 设F x x是乌鸦 G x y x与y一般黑 则句子 1 可完整地符号化为 x y F x F y G x y 或 x y F x F y G x y 例2 8 续 2020 2 22 国际学院 29 2 那位身体强健的 用功的 肯于思考的大学生 解决了一个数学难题 设P x x是身体强健的 Q x x是用功的 R x x是肯于思考的 S x x是大学生 T x y x解决了y a 那位 b 一个数学难题 则句子 2 可完整地符号化为 P a Q a R a S a T a b 2020 2 22 国际学院 30 3 张强和李平都是足球运动员 设Z x x是足球运动员 c 张强 d 李平 则句子 3 可完整地符号化为 Z c Z d 4 每个实数都存在比它大的另外的实数 设R x x是实数 L x y x小于y 则句子 4 可以完整地符号化为 x R x y R y L x y 2020 2 22 国际学院 31 5 并非所有的动物都是脊椎动物 设A x x是动物 B x x是脊椎动物 则句子 5 可以完整地符号化为 x A x B x 或 x A x B x 6 尽管有人很聪明 但未必一切人都聪明 设M x x是人 C x x很聪明 则句子 6 可以完整地符号化为 x M x C x x M x C x 2020 2 22 国际学院 32 7 对于任意给定的 0 必存在着 0 使得对任意的x 只要 x a 0 0 x x a f x f a 2020 2 22 国际学院 33 辖域的概念强化 设有谓词公式 x P x Q x 此时 x 的辖域仅为P x 而非P x Q x 因此 P x 与Q x 中的x具有完全不同的意义 2020 2 22 国际学院 34 2 4自由变元和约束变元 定义2 7合式公式中的变元x若出现在以x为作用变元的量词的辖域之内 则称变元x的出现为约束出现 此时的变元x称为约束变元 量 若x的出现不是约束出现 则称它为自由出现 此时的变元x称为自由变元 量 2020 2 22 国际学院 35 y P y z Q x y R y x P x Q x x P x y R x y x P x R x y Q x y 例2 9 解 在1 中 P y z 与Q x y 中的y为约束变元 x z为自由变元 R y 中的y为自由变元 在2 中 P x 和Q x 中的x都为约束变元 在3 中 P x 中的x和R x y 中的y都为约束变元 R x y 中的x为自由变元 在4 中 P x R x 中的x和Q x y 中的y都是约束变元 Q x y 中的x为自由变元 2020 2 22 国际学院 36 两个规则 规则1 约束变元的改名规则 1 将量词中出现的变元以及该量词辖域中此变量之所有约束出现都用新的个体变元替换 2 新的变元一定要有别于改名辖域中的所有其它变量 规则2 自由变元的代入规则 1 将公式中出现该自由变元的每一处都用新的个体变元替换 2 新变元不允许在原公式中以任何约束形式出现 2020 2 22 国际学院 37 在公式 x P x R x y Q y 中 变元x是约束变元 y是自由变元 利用规则1对x进行改名 则 合法的改名有 z P z R z y Q y 不合法的改名有 z P z R x y Q y y P y R y y Q y 利用规则2对y进行代入 则 合法的代入有 x P x R x z Q z 不合法的代入有 x P x R x y Q z x P x R x x Q x 例2 10 2020 2 22 国际学院 38 改名规则和代入规则之间的共同点都是不能改变原有的约束关系 而不同点是 1 施行的对象不同 改名规则是对约束变元施行 代入规则是对自由变元施行 2 施行的范围不同 改名规则可以只对公式中的一个量词及其辖域内施行 即只对公式的一个子公式施行 而代入规则必须对整个公式同一个自由变元的所有自由出现同时施行 即必须对整个公式施行 3 施行后的结果不同 改名后 公式含义不变 因为约束变元只改名为另一个个体变元 约束关系不改变 约束变元不能改名为个体常量 代入后 不仅可用另一个个体变元进行代入 并且也可用个体常量去代入 从而使公式由具有普遍意义变为仅对该个体常量有意义 即公式的含义改变了 2020 2 22 国际学院 39 谓词的语言翻译 x G x x G x 当个体域D是有限集合时 如 D a1 a2 a3 an 则有 x G x G a1 G a2 G a3 G an x G x G a1 G a2 G a3 G an 2020 2 22 国际学院 40 说 明 如有多个量词 则读的顺序按从左到右的顺序 即 x y G x y x y G x y 另外 量词对变元的约束 往往与量词的次序有关 不同的量词次序 可以产生不同的真值 此时对多个量词同时出现时 不能随意颠倒它们的顺序 颠倒后会改变原体的含义 2020 2 22 国际学院 41 例2 11 则有 P a x P x P 2 P 2 P 3 1 1 0 0 x P x P a P 2 P 3 P 2 1 0 1 1 设公式 P a x P x 和 x P x P a 求公式的真值 其中 个体域为D 2 3 a指定为 2 P 2 指定为 1 P 3 指定为 0 2020 2 22 国际学院 42 例2 12 个体域为D a指定为 f 指定为 f 指定为 P 指定为 1 P 指定为 0 Q 指定为 0 Q 指定为 1 Q 指定为 1 Q 指定为 1 设有公式 x P f x Q x f a 判断该公式的真值 其中 2020 2 22 国际学院 43 例2 12 续 解 原式 P f a Q a f a P f Q f a 因当x 时 有 f P f x P f P 1 f a f Q x f a Q f Q 1 所以 P f Q f a 1 1 1 即存在x 使得P f Q f a 1 即 x P f x Q x f a 1 2020 2 22 国际学院 44 谓词公式的类型 例2 13 求公式的真值 P a x P x 和 x P x P a 解 1 对任何的解释I a 当P a 取值为真时 P x 也必为真 此时 P a x P x 的真值为真 b 当P a 取值为假时 P x 可为真 也可为假 此时 P a x P x 的真值也为真 所以 公式P a x P x 就是关于一切结构与一切赋值下恒取 T 值的谓词公式 2020 2 22 国际学院 45 2 对任何的解释I a 当P x 取值为真时 P a 也必为真 此时 x P x P a 的真值为真 b 当P x 取值为假时 P a 可为真 也可为假 此时 x P x P a 的真值也为真 所以 公式 x P x P a 就是关于一切结构与一切赋值下恒取 T 值的谓词公式 2020 2 22 国际学院 46 例2 14 判断下列公式的真假 1 x y P x y Q x y P x y 2 P x y P x y 3 P x y P x y 解 无论在何种结构中 无论对变元作何种赋值 公式1 和2 均取真值T 公式3 均取真值F 2020 2 22 国际学院 47 定义2 9 公式G称为有效公式 永真式 如果G在它所有的解释I下都取值为 真 公式G称为矛盾公式 如果G在它所有的解释I下都取值为 假 公式G称为可满足公式 如果至少有一种解释I使得G取值为 真 从上述定义可知三种特殊公式之间的关系 有效公式的否定为矛盾公式 矛盾公式的否定为有效公式 有效公式一定为可满足公式 可满足公式的否定不一定为不可满足公式 矛盾公式 2020 2 22 国际学院 48 谓词逻辑是不可判定的 对任一谓词公式而言 没有可行的方法判明它是否是有普遍有效性的 像命题逻辑就可用真值表法判明任一命题公式的永真性 谓词逻辑的判定问题的困难在于个体域是个无穷集以及对谓词设定的任意性 由于谓词公式的复杂性和解释的多样性 至今还没有一个可行的算法判定任何公式的类型 当然 对于一些较为简单的公式 或某些特殊公式 还是可以判定其类型的 2020 2 22 国际学院 49 2 5等价关系与蕴涵关系 定义2 10公式G H称为等价的 记为G H 如果公式G H是恒真的 公式G蕴涵公式H 记为G H 如果公式G H是恒真的 2020 2 22 国际学院 50 代入实例 定义2 11 设 P1 P2 Pn 是命题演算中的命题公式 P1 P2 Pn是出现在G中的命题变元 当用任意的谓词公式Gi 1 i n 分别代入Pi后 得到的新谓词公式 G1 G2 Gn 称为原公式的代入实例 命题演算的永真公式的任意一个代入实例必为谓词演算的有效公式 2020 2 22 国际学院 51 代入实例 如 x P x Q x x P x Q x x P x Q x x P x Q x x G x x G x T 2020 2 22 国际学院 52 下面给出涉及量词的一些等价式 它们的证明略去了 1 量词否定等价式 a x A x x A x b x A x x A x 这两个等价式 可用量词的定义给予说明 由于 并非对一切x A为真 等价于 存在一些x A为真 故 a 成立 由于 不存在一些x A为真 等价于 对一切x A为真 所以 b 成立 2020 2 22 国际学院 53 这两个等价式的意义是 否定联结词可通过量词深入到辖域中 对比这两个式子 容易看出 将 x 与 x 两者互换 可从一个式子得到另一个式子 这表明 x 与 x 具有对偶性 另外 由于这两个公式成立也表明了 两个量词是不独立的 可以互相表示 所以只有一个量词就够了 对于多重量词前置 可反复应用上面结果 逐次右移 例如 x y z P x y z x y z P x y z 2020 2 22 国际学院 54 2 量词辖域缩小或扩大等价式设B是不含x自由出现 A x 为有x自由出现的任意公式 则有 a x A x B x A x B b x A x B x A x B c x A x B x A x B d x B A x B x A x e x A x B x A x B f x A x B x A x B g x A x B x A x B h x B A x B x A x 2020 2 22 国际学院 55 证明 c x A x B x A x B x A x B x A x B x A x B x A x B 2020 2 22 国际学院 56 3 量词分配律等价式 a x A x B x x A x x B x b x A x B x x A x x B x 其中 A x B x 为有x自由出现的任何公式 4 多重量词等价式 a x y A x y y x A x y b x y A x y y x A x y 其中A x y 为含有x自由出现的任意公式 2020 2 22 国际学院 57 2 蕴涵式由于命题逻辑中蕴涵式 或永真条件式 在谓词逻辑中都是逻辑有效的 而且使用代入规则得到蕴涵式也都是谓词逻辑中逻辑有效的 例如 x P x x P x y Q y 附加 x P x Q x y x P x Q x y 假言推理 2020 2 22 国际学院 58 1 a x A x x B x x A x B x b x A x B x x A x x B x c x A x B x x A x x B x d x A x B x x A x x B x 其中 A x 和B x 为含有x自由出现的任意公式 下面将给出谓词逻辑中的一些蕴涵式 其证明省略 2020 2 22 国际学院 59 2 a x y A x y y x A x y b y x A x y x y A x y c y x A x y x y A x y d x y A x y y x A x y e x y A x y y x A x y f y x A x y x y A x y 其中 A x y 为含有x y的自由出现的任意公式 2020 2 22 国际学院 60 三 基本等价公式和蕴涵公式 假设G x H x 是只含自由变元x的公式 S是不含x的公式 则在全总个体域中 有 E22 x G x y G y E23 x G x y G y E24 x G x x G x E25 x G x x G x E26 x G x S x G x SE27 x G x S x G x SE28 x G x S x G x SE29 x G x S x G x S 2020 2 22 国际学院 61 基本等价公式和蕴涵公式 续 E30 x G x H x x G x x H x E31 x G x H x x G x x H x E32 x G x x H x x y G x H y E33 x G x x H x x y G x H y I16 x G x x G x I17 x G x x H x x G x H x I18 x G x H x x G x x H x I19 x G x H x x G x x H x I20 x G x H x x G x x H x 2020 2 22 国际学院 62 多个量词的基本等价公式和蕴涵公式 E34 x y G x y y x G x y E35 x y G x y y x G x y I21 x y G x y y x G x y I22 x y G x y y x G x y I23 x y G x y x y G x y I24 y x G x y x y G x y I25 x y G x y y x G x y I26 x y G x y x y G x y I27 x y G x y x y G x y I28 y x G x y y x G x y 2020 2 22 国际学院 63 上述结论的量词关系可用如下图表示 E35 E34 x y y x I22 I23 y x x y I28 I24 I21 x y y x I27 I25 I26 y x x y 2020 2 22 国际学院 64 基本等价公式和蕴涵公式的证明 倘若个体域为有限域D a1 a2 an 时 很容易加以证明 如证明E24 E25 此时有 x G x G a1 G a2 G an G a1 G a2 G an x G x x G x G a1 G a2 G an G a1 G a2 G an x G x 2020 2 22 国际学院 65 例2 15 设P x x今天来上课 个体域为计算机学院2005级全体同学的集合 则 1 x P x 表示所有同学今天都来上课了 x P x 表示不是所有的同学今天来上课了 x P x 表示今天有同学没来上课 所以 x P x x P x 2 x P x 表示有同学今天来上课了 x P x 表示今天没有同学来上课 x P x 表示所有同学今天都没来上课 所以 x P x x P x 2020 2 22 国际学院 66 例2 16 设G x x勤奋学习 H x x喜欢体育活动 其中 个体域是大学里的学生 则 x G x H x 表示 大学里的所有学生即勤奋学习又喜欢体育活动 x G x x H x 表示 大学里的所有学生都勤奋学习且大学里所有的学生都喜欢体育活动 两者意义是相同的 即有 x G x H x x G x x H x 2020 2 22 国际学院 67 例2 17 设G x x是高才生 H x x是运动健将 其中 个体域是某班的学生则 x G x x H x 表示 该班的所有学生是高才生或该班的所有学生是运动健将 x G x H x 表示 该班的所有学生是高才生或是运动健将 显然 前者可推出后者 但反之则不然 即有 x G x x H x x G x H x 2020 2 22 国际学院 68 例2 18 设 D 1 2 G 1 0 G 2 1 H 1 1 H 2 0 1 x G x H x G 1 H 1 G 2 H 2 0 1 1 0 1 1 12 x G x x H x G 1 H 1 G 2 H 2 0 1 1 0 0 0 0所以 I17的逆不成立 2020 2 22 国际学院 69 2 6谓词公式范式 前束范式定义2 6 1一个合式公式称为前束范式 如果它有如下形式 Q1x1 Q2x2 Qkxk B其中Qi 1 i k 为 或 B为不含有量词的公式 称Q1x1Q2x2 Qkxk为公式的首标 特别地 若 中无量词 则 也看作是前束范式 2020 2 22 国际学院 70 可见 前束范式的特点是 所有量词均非否定地出现在公式最前面 且它的辖域一直延伸到公式之末 例如 x y z P x y Q y z R x y 等都是前束范式 而 x P x y Q y x P x y Q x y 不是前束范式 定理2 6 1 前束范式存在定理 Lp中任意公式A都有与之等价的前束范式 例题见课本P73 2020 2 22 国际学院 71 斯柯林范式 补充 前束范式的的优点是全部量词集中在公式前面 其缺点是各量词的排列无一定规则 这样当把一个公式化归为前束范式时 其表达形式会显现多种情形 不便应用 1920年斯柯林 Skolem 提出对前束范式首标中量词出现的次序给出规定 每个存在量词均在全称量词之前 按此规定得到的范式形式 称为斯柯林范式 显然 任一公式均可化为斯柯林范式 它的优点是 全公式按顺序可分为三部分 公式的所有存在量词 所有全称量词和辖域 这给Lp的研究提供了一定的方便 2020 2 22 国际学院 72 2 7谓词逻辑的推理理论 Lp是Ls的进一步深化和发展 因此Ls的推理理论在Lp中几乎可以完全照搬 只不过这时涉及的公式是Lp的公式罢了 在Lp中 某些前提和结论可能受到量词的约束 为确立前提和结论之间的内部联系 有必要消去量词和添加量词 因此正确理解和运用有关量词规则是Lp推理理论中十分重要的关键所在 2020 2 22 国际学院 73 Lp中推理实例Lp的推理方法是Ls推理方法的扩展 因此在Lp中利用的推理规则也是T规则 P规则和CP规则 还有已知的等价式 蕴涵式以及有关量词的消去和产生规则 使用的推理方法是直接构造法和间接证法 2020 2 22 国际学院 74 1 2 3 n 考虑如何推理苏格拉底三段论 前提 所有的人都是要死的 苏格拉底是人 结论 苏格拉底是要死的 x H x D x H s D s 2020 2 22 国际学院 75 2 7 1 推理规则 量词的四条重要的推理规则 US 全称特指规则 x G x G c UniversalSpecify ES 存在特指规则 x G x G c ExistentialSpecify UG 全称推广规则 G c x G x UniversalGeneralize EG 存在推广规则 G c x G x ExistentialGeneralize 2020 2 22 国际学院 76 有关规则US 实际可有两种书写形式 x G x G c 成立的条件是 c为任意的个体常量 一 有关规则US的正确使用 2020 2 22 国际学院 77 设实数集中 语句 不存在最大的实数 可符号化为 x y G x y 其中 G x y y x 请看下述推导 1 x y G x y P 2 y G y y US 正确地推导为 1 x y G x y P 2 y G c y US 例2 7 1 2020 2 22 国际学院 78 二 有关规则ES的正确使用 x G x G c 成立的条件是 c是使G x 为真的特定的个体常量 不是任意的 如 x G x x P x 均为真 则对于某些c和d可以断定G c P d 为真 G c P c 不一定为真 2020 2 22 国际学院 79 在例2 7 1中 接着第 2 步进行如下推导 1 x y G x y P 2 y G c y US 1 3 G c b ES 例2 7 1 续 2020 2 22 国际学院 80 三 有关规则UG的正确使用 G c x G x 成立的条件和限制是 x取遍整个个体域时 都有G x 为真 C是全称特指的一个变量 2020 2 22 国际学院 81 例2 7 2 请看如下推导 1 y G x y P 2 y y G y y UG 1 结论 2 是错误的 正确的推导为 1 y G x y P 2 z y G z y UG 1 2020 2 22 国际学院 82 例2 7 3 设在实数域中 令G x x 0 则请看下述推导 1 G x P 2 x G x UG 1 此时结论 2 是错误的 2020 2 22 国际学院 83 四 有关规则EG的正确使用 该规则有两种形式 G c x G x 成立的条件和限制是 c是使G c 为真的特定的个体常量 需要限制x不出现在G c 中 例2 7 4 请看下述推导 1 G x c P 2 x G x x EG 1 上述推导是错误的 2020 2 22 国际学院 84 继续使用例2 7 1 请看如下推导 1 x y G x y P 2 y G z y US 1 3 G z c ES 4 x G x c UG 3 5 y x G x y EG 结论 5 是错误的 2020 2 22 国际学院 85 例2 7 5 G x y xy 0 其中 x y为实数 则句子 存在一个y 使得对任何x 都有xy 0 可符号化为 y x G x y 请看下面推导 1 y x G x y P 2 x G x c ES 3 x x G x x EG 4 x G x x E结论 4 是错误的 2020 2 22 国际学院 86 五 谓词演算的综合推理方法 在推导的过程中 可以引用命题演算中的规则P和规则T 如果结论是以条件的形式 或析取形式 给出 我们还可以使用规则CP 为了在推导过程中消去量词 可以引用规则US和规则ES来消去量词 当所要求的结论可能被定量时 此时可引用规则UG和规则EG将其量词加入 证明时可采用如命题演算中的直接证明方法和间接证明方法 在推导过程中 对消去量词的公式或公式中没含量词的子公式 完全可以引用命题演算中的基本等价公式和基本蕴涵公式 2020 2 22 国际学院 87 谓词演算的综合推理方法 续1 在推导过程中 对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式 在推导过程中 如既要使用规则US又要使用规则ES消去公式中的量词 只要有可能 我们总是先使用规则ES 再使用规则US 然后再使用命题演算中的推理规则 最后使用规则UG或规则EG引入量词 得到所要的结论 如一个变量是用规则ES消去量词 对该变量在添加量词时 则只能使用规则EG 而不能使用规则UG 如使用规则US消去量词 对该变量在添加量词时 则可使用规则EG和规则UG 2020 2 22 国际学院 88 谓词演算的综合推理方法 续2 如有两个含有存在量词的公式 当用规则ES消去量词时 不能选用同样的一个常量符号来取代两个公式中的变元 而应用不同的常量符号来取代它们 在用规则US和规则ES消去量词时 此量词必须位于整个公式的最前端 并且它的辖域为其后的整个公式 在添加的量词 x x 时 所选用的x不能在公式G c 或G y 中以任何约束出现 在使用EG规则引入存在量词 x 此x不得仅为G c 或G y 中的下标变元 在使用UG规则引入全称量词 x 时 此x不得为G y 中的下标变元 因该下标变元不得作为自由变元 在使用EG规则引入存在量词 x 此x不得仅为G c 或G y 中的函数变元 在使用UG规则引入全称量词 x 时 此x不得为G y 中的函数变元 因该函数变元不得作为自由变元 2020 2 22 国际学院 89 例2 0 解 设H x x是人 M x x是要死的 s 苏格拉底 则符号化为 x H x M x H s M s 证明 所有的人都是要死的 苏格拉底是人 所以苏格拉底是要死的 证明 1 x H x M x P 2 H x M x US 1 3 H s P 4 M s T 2 3 I 证明 1 x H x M x P 2 H s M s US 1 3 H s P 4 M s T 2 3 I 4 错了 正确的为 2020 2 22 国际学院 90 例2 1 请看推导 1 x P x Q x P 2 P x Q x US 1 3 x P x P 4 P x ES 5 Q x T 2 4 I 6 x Q x EG 5 证明 x P x Q x x P x x Q x 2020 2 22 国际学院 91 例2 1 续1 请看推导 1 x P x Q x P 2 P x Q x US 1 3 x P x P 4 P c ES 3 5 Q c T 2 4 I 6 x Q x EG 5 2020 2 22 国际学院 92 例2 1 续 请看推导 1 x P x Q x P 2 P c Q c US 1 3 x P x P 4 P c ES 3 5 Q c T 2 4 I 6 x Q x EG 5 2020 2 22 国际学院 93 例2 1 续 正确地推导如下 1 x P x P 2 P c ES 1 3 x P x Q x P 4 P c Q c US 3 5 Q c T 2 4 I 6 x Q x EG 5 2020 2 22 国际学院 94 例2 2 证明 1 x P x Q x P2 P c Q c ES 1 3 P c T 2 I4 Q c T 2 I5 x P x EG 3 6 x Q x EG 4 7 x P x x Q x T 5 6 I 证明 x P x Q x x P x x Q x 2020 2 22 国际学院 95 例2 2 续1 1 x P x x Q x P2 x P x T 1 I3 P c ES 2 4 x Q x T 1 I5 Q c ES 4 6 P c Q c T 3 4 I7 x P x Q x EG 6 请看上述推论的逆推导 正确 2020 2 22 国际学院 96 例2 2 续2 正确地推导如下 1 x P x x Q x P2 x P x T 1 I3 P c ES 2 4 x Q x T 1 I5 Q b ES 4 6 P c Q b T 3 4 I7 x y P x Q y EG 6 2020 2 22 国际学院 97 例2 3 证明下述论断的正确性 所有的哺乳动物都是脊椎动物 并非所有的哺乳动物都是胎生动物 故有些脊椎动物不是胎生的 解 设谓词如下 P x x是哺乳动物 Q x x是脊椎动物 R x x是胎生动物 则有 x P x Q x x P x R x x Q x R x 2020 2 22 国际学院 98 请看下面推导 x P x R x P P x R x US 1 P x R x T 2 E P x R x T 3 EP x T 4 I R x T 4 I x P x Q x PP x Q x US 7 Q x T 5 8 I Q x R x T 6 9 I x Q x R x EG 10 x Q x R x UG 10 2020 2 22 国际学院 99 证明 x P x R x P x P x R x T 1 E P c R c ES 2 P c R c T 3 EP c T 4 I R c T 4 I x P x Q x PP c Q c US 7 Q c T 5 8 I Q c R c T 6 9 I x Q x R x EG 10 2020 2 22 国际学院 100 例2 4 证明下述论断的正确性 所有爱学习 有毅力的人都有知识 每个有知识 爱思考的人都有创造 有些有创造的人是科学家 有些有毅力 爱学习 爱思考的人是科学家 有些爱学习 有毅力 有创造的人是科学家 解 设P x x是爱学习的人 Q x x是有毅力的人 R x x是有知识的人 S x x是有创造的人 U x x是科学家 V x x是爱思考的人 2020 2 22 国际学院 101 则原论断可符号化为 x P x Q x R x x R x V x S x x S x U x x Q x P x V x U x x P x Q x S x U x 证明 1 x Q x P x V x U x P 2 Q c P c V c U c ES 1 3 Q c P c T 2 4 x P x Q x R x P 5 P c Q c R c US 4 6 R c T 3 5 I 7 V c T 2 2020 2 22 国际学院 102 8 R c V c T 6 7 I 9 x R x V x S x P 10 R c V c S c US 9 11 S c T 8 10 I 12 Q c P c U c T 2 I 13 Q c P c S c U c T 11 12 I 14 x P x Q x S x U x ES 13 2020 2 22 国际学院 103 例2 5 证明下述论断的正确性 每个报考研究生的大学毕业生要么参加研究生的入学考试 要么被推荐为免试生 每个报考研究生的大学毕业生当且仅当学习成绩优秀才被推荐为免试生 有些报考研究生的大学毕业生学习成绩优秀 但并非所有报考研究生的大学毕业生学习成绩都优秀 因此 有些报考研究生的大学毕业生要参加研究生的入学考试 2020 2 22 国际学院 104 解 设P x x是报考研究生的大学毕业生 Q x x参加研究生入学考试 R x x被推荐为免试生 S x x学习成绩优秀 则原论断可符号化为 x P x Q x R x x P x R x S x x P