离散数学讲义(第2章).pptVIP

1 天津财经大学信息科学与技术系王宁ninglw DiscreteMathematics 离散数学讲义 电子版 2 第二章谓词逻辑 3 第二章谓词逻辑 谓词演算 一阶谓词演算 是命题演算的扩充和发展 其本质同命题演算 是把数学中的逻辑论证加以符号化 可以刻划命题内部的逻辑结构 从而推动了这个数学分支的发展 苏格拉底 Socrates 三段论 所有的人都是要死的 苏格拉底是人 所以苏格拉底是要死的 4 本章包括以下内容 2 1谓词的概念与表示2 2命题函数与量词2 3谓词公式与翻译2 4变元的约束2 5谓词演算的等价式与蕴含式2 6前束范式2 7谓词演算的推理理论 第二章谓词逻辑 5 在谓词演算中 将原子命题分解为谓词和客体两部分 客体 可以独立存在的东西 它可以是一个具体的事物 也可以是一个抽象的概念 主语一般为客体 2 1谓词的概念与表示 例如 谓词指明客体性质 谓词指明客体间关系 谓词 用于刻划客体的性质或客体与客体之间的关系 a 他是三好学生 b 7是质数 c 每天早晨做广播操是好习惯 d 5大于3 e 哥白尼指出地球绕着太阳转 6 记号 例如 2 1谓词的概念与表示 续 大写字母 表示谓词 小写字母 表示客体 个体 1 用A表示 是个大学生 c表示 张三 d表示 李四 则 A c 张三是个大学生 A d 李四是个大学生 2 用B表示 大于 e代表 5 f代表 3 则 B e f 5大于3 3 用L表示 在 和 之间 a表示 点a b表示 点b c表示 点c 则 L a b c 表示 a在b和c之间 7 记号 一元谓词 A b 二元谓词 B a b 三元谓词 L a b c n元谓词 A c1 c2 cn 代表客体名称的字母 它在多元谓词表示式中出现的次序与事先约定有关 2 1谓词的概念与表示 续 8 2 1谓词的概念与表示 续 通常 一元谓词表达了客体的 性质 多元谓词表达了客体之间的 关系 定义 单独一个谓词不是完整的命题 把谓词字母后填以客体所得的式子称为谓词填式 谓词和谓词填式是两个不同的概念 9 2 2命题函数与量词 例 H 能够到达山顶 l 李四 t 老虎 c 汽车 则H x 当x分别取l t c时表示 李四能够到达山顶 老虎能够到达山顶 汽车能够到达山顶 L x y x小于y 则L 2 3 表示 2小于3 L 5 1 表示 5小于1 A x y z x加y等于z 则A 3 2 5 表示 3加2等于5 A 1 2 4 表示 1加2等于4 10 定义 由一个谓词和一些客体变元所组成的表达式称为简单命题函数 2 2命题函数与量词 续 例如 对于谓词P P x 是变元x的函数 N元谓词是有n个客体变元的命题函数 n 0时 称为0元谓词 其本身是一个命题 定义 由一个或多个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数 11 2 2命题函数与量词 续 例1 设S x x学习很好 W x x工作很好 例2 H x y x比y长得高 l 李四 c 张三 则 S x x学习不是很好 S x W x x学习工作都很好 则 H l c 李四不比张三长得高 H l c H c l 李四不比张三长得高且张三不比李四长得高 即 李四与张三一样高 12 2 2命题函数与量词 续 注 例3 Q x y x比y重 当x y指人或物时 它是一个命题 若x y为实数时 Q x y 不是命题 1 命题函数不是命题 只有客体变元取特定名称时才能成为一个命题 2 客体变元在哪些范围内取特定的值对是否成为命题及命题的真值有影响 13 2 2命题函数与量词 续 例4 R x x是大学生 考虑x的讨论范围 例5 P x y P y z P x z 考虑P x y 的解释 1 某大学里班级中的学生 则R x 永真 2 某中学里班级中的学生 则R x 永假 3 某剧场中的观众 则R x 对某些观众为真 对某些为假 1 x小于y 则P x y 永真 2 x为y的儿子 则P x y 永假 3 x距离y10米 则P x y 可能为真或假 14 个体变元 函数P x 中的x 2 2命题函数与量词 续 说明 逻辑联结词 的意义与命题演算中的解释相同 个体域 论域 个体变元的取值 论述 范围 全总个体域 各种个体域综合在一起作为论述范围的域 15 量词 2 2命题函数与量词 续 注意 每个由量词确定的表达式都与个体域有关 因此在讨论带有量词的命题函数时 必须确定其个体域 全称量词 表示 对所有的 对每一个 对任意一个 等等 存在量词 表示 存在一个 至少有一个 等等 16 例1 有如下命题 则上述三个命题可以表述为 2 2命题函数与量词 续 a 所有人都是要呼吸的 b 每个学生都要参加考试 c 任何整数或者是正的或者是负的 设 M x x是人 P x x是学生 I x x是整数 H x x要呼吸 Q x x要参加考试 R x x是正数 N x x是负数 a x M x H x b x P x Q x c x I x R x N x 17 例2 有如下命题 a 存在一个数是质数 b 一些人是聪明的 c 有些人早饭吃面包 则上述三个命题可以表述为 2 2命题函数与量词 续 设 M x x是人 P x x是质数 R x x是聪明的 E x x早饭吃面包 a x P x b x M x R x c x M x E x 18 合式公式 谓词演算公式的合式公式 wff 简称谓词公式 可以由下述各条组成 原子公式 A x1 x2 xn 这里x1 x2 xn是个体变元 2 3谓词公式与翻译 例如 Q A x A x y A f x y A x y z A a y 等 注意 量词后面若有括号不能省略 基础 归纳 界限 1 原子谓词公式是合式公式 2 若A是合式公式 则 A也是合式公式 3 若A和B都是合式公式 则 A B A B A B 和 A B 都是合式公式 4 若A都是合式公式 x是出现在A中的任何变元 则 x A和 x A都是合式公式 5 只有经过有限次地应用规则 1 2 3 4 所得到的公式是合式公式 19 2 3谓词公式与翻译 续 例1 并非每个实数都是有理数 R x Q x 用谓词公式表达下列命题 例2 没有不犯错误的人 F x M x 例3 尽管有些人聪明 但未必一切人都聪明 P x M x 解 x R x Q x 解 x M x F x 且该命题与 任何人都会犯错误 意义相同 x M x F x 解 x M x P x x M x P x 20 2 3谓词公式与翻译 续 例4 这支大红书柜摆满了那些古书 解法1 设F x y x摆满了y R x x是大红书柜 Q y y是古书 a 这只 b 那些 则R a Q b F a b 解法2 设A x x是书柜 B x x是大的 C x x是红的 D y y是古老的 E y y是书 F x y x摆满了y a 这只 b 那些 则A a B a C a D b E b F a b 解法3 设F x y x摆满了y a 这只大红书柜 b 那些古书 则F a b 21 2 3谓词公式与翻译 续 可见 对于命题翻译成谓词演算公式 机动性很大 由于对个体描述性质刻画深度不同 就可翻译成不同形式的谓词公式 例5 数学分析中极限的定义 任给 0 存在 0 使得当0 x a 时有 f x b 则称b是f x 在x a时的极限 记为f x b 当x a 或 解 下面用谓词公式表示以上定义 设P x y x大于y Q x y x小于y 则以上定义的谓词公式表示如下 x P 0 P 0 Q x a P x a 0 Q f x b 22 几个名词 2 4变元的约束 1 指导变元 作用变元 给定为一谓词公式 其中有一部分公式形如 x P x 或 x P x 则 后面所跟的x叫做量词的指导变元 或作用变元 2 作用域 辖域 P x 3 约束出现 在作用域中x的一切出现 4 约束变元 在作用域中出现的x 5 自由变元 在谓词公式中除去约束变元以外所出现的变元 23 例1 说明以下各公式的作用域与变元约束的情况 指导变元 作用域 2 4变元的约束 续 x P x Q y x 的作用域是 P x Q y x为约束变元 b x P x y R x y x 的作用域是 P x y R x y y 的作用域是 R x y x y为约束变元 24 c x y P x y Q y z x P x y 2 4变元的约束 续 x y 的作用域是 P x y Q y z x y为约束变元 z是自由变元 x 的作用域是P x y x为约束变元 y是自由变元 整个公式中x是约束出现 y既是约束出现又是自由出现 z是自由出现 d x P x x Q x z y R x y Q x y x 的作用域是 P x x Q x z y R x y x y是约束变元 但Q x z 中的x受 x 约束而不受 x 约束 Q x y 中的x y是自由变元 25 2 4变元的约束 续 P x1 x2 xn 是n元谓词 有n个相互独立的自由变元 若对其中k个进行约束 则成为n k元谓词 换名 为避免由于变元的约束与自由同时出现引起概念上的混乱 可对约束变元进行换名 使得一个变元在一个公式中只呈一种形式出现 即呈自由出现或呈约束出现 例如 x P x y z 是二元谓词 y x P x y z 是一元谓词 26 例2 对 x P x R x y Q x y 换名 2 4变元的约束 续 约束变元的换名规则 1 对于约束变元可以换名 其更改的变元名称范围是量词中的指导变元 以及该量词作用域中所出现的该变元 在公式的其余部分不变 2 换名时一定要改为作用域中没有出现的变元名称 解 可换名为 z P z R z y Q x y 但不可换名为 y P y R y y Q x y 或 z P z R x y Q x y 27 自由变元的代入规则 2 4变元的约束 续 例3 对 x P y R x y 作自由变元代入 1 对于自由变元可以代入 代入时需对公式中出现该自由变元的每一处进行代入 2 用以代入的变元与原公式中的所有变元的名称不能相同 解 对y施行代入 得到 x P z R x z 但是 x P x R x x 和 x P z R x y 都是错误的 28 2 4变元的约束 续 当论域的元素是有限时 客体变元的所有可能的取代是可枚举的 注意 量词对变元的约束与量词的次序有关 量词次序不能颠倒 否则将与原命题意义不符 设论域元素为a1 a2 an 则 x A x A a1 A a2 A an x A x A a1 A a2 A an 29 2 5谓词演算的等价式与蕴含式 赋值 谓词公式中的客体变元由确定的客体所取代 命题变元用确定的命题取代 等价 给定任何两个谓词公式wffA和wffB 设它们有共同的个体域E 若对A和B的任一组变元进行赋值 所得命题的真值相同 则称谓词公式A和B在E上是等价的 记作A B 30 2 5谓词演算的等价式与蕴含式 续 永真 有效 给定任意谓词公式wffA 其个体域为E 对于A的所有赋值 wffA都为真 则称wffA在E上是有效的 永真的 不可满足 一个谓词公式wffA 如果在所有赋值下都为假 则称该wffA为不可满足的 可满足 一个谓词公式wffA 如果至少在一种赋值下为真 则称该wffA为可满足的 31 1 命题公式的推广 例如 2 5谓词演算的等价式与蕴含式 续 命题演算中的等价公式表和蕴含式表都可以推广到谓词演算中 x P x Q x x P x Q X x P x y R x y x P x y R x y x H x y x H x y F 32 2 量词与联结词 之间的关系 量词的转化律公式 对个体域为有限或无穷都成立 2 5谓词演算的等价式与蕴含式 续 约定 出现在量词之前的否定 不是否定该量词 而是否定被量化了的整个命题 1 x P x x P x 2 x P x x P x 33 2 5谓词演算的等价式与蕴含式 续 例 P x x今天来上课 则 P x x今天没有来校上课 a 不是所有人今天都来上课 与 存在一些人今天没来上课 含义相同 x P x x P x b 不是存在一些人今天来上课 与 所有人今天没来上课 含义相同 x P x x P x 34 上述公式在有限个体域上的证明 2 5谓词演算的等价式与蕴含式 续 结论 当将量词前面的联结词 移到量词的后面去时 存在量词改为全称量词 全称量词改为存在量词 反之 如果将量词后面的联结词 移到量词的前面去时 也要做相应的改变 设个体域中的客体变元为a1 a2 an 则 1 x A x A a1 A a2 A an A a1 A a2 A an x A x 2 x A x A a1 A a2 A an A a1 A a2 A an x A x 35 3 量词作用域的扩张与收缩 1 x A x B x A x B2 x A x B x A x B 5 x A x B x A x B 6 x A x B x A x B 7 x B A x B x A x 8 x B A x B x A x 2 5谓词演算的等价式与蕴含式 续 3 x A x B x A x B4 x A x B x A x B 36 证明 以公式1 5 6证明为例 公式1 x A x B x A x B 2 5谓词演算的等价式与蕴含式 续 证 考虑有限个体域D a1 a2 an x A x B A a1 B A a2 B A an B A a1 A a2 A an B x A x B证毕 37 公式6 x A x B x A x B 2 5谓词演算的等价式与蕴含式 续 公式5 x A x B x A x B 证 x A x B x A x B x A x B x A x B证毕 证 x A x B x A x B x A x B x A x B 证毕 38 4 量词与命题联结词之间的一些等价式 1 x A x B x x A x x B x 2 x A x B x x A x x B x 2 5谓词演算的等价式与蕴含式 续 例如 联欢会上所有人既唱歌又跳舞与联欢会上所有人唱歌且所有人跳舞含义相同 39 5 量词与命题联结词之间的一些蕴涵关系 2 x A x B x x A x x B x 3 x A x B x x A x x B x 4 x A x B x x A x x B x 2 5谓词演算的等价式与蕴含式 续 1 x A x x B x x A x B x 40 6 多个量词的使用 对于二元谓词的情况 1 x y A x y 2 x y A x y 3 x y A x y 4 x y A x y 5 y x A x y 6 y x A x y 7 y x A x y 8 y x A x y 2种排列情况 4种组合情况 2 5谓词演算的等价式与蕴含式 续 41 2 5谓词演算的等价式与蕴含式 续 具有两个量词的谓词公式的蕴涵关系式 1 x y A x y y x A x y 2 y x A x y x y A x y 3 y x A x y x y A x y 4 x y A x y y x A x y 5 x y A x y y x A x y 6 y x A x y x y A x y 42 定理 任何一个谓词公式均等价于某个前束范式 定义 如果一个谓词公式的量词均在全式的开头 而这些量词的作用域延伸至整个公式的末尾 则该公式叫做前束范式 前束范式记为 v1 v2 vn A 例 x y z Q x y R z 是一个前束范式 2 6前束范式 将一个谓词公式转化为一个与之等价的前束范式的步骤 第一步 否定深入 第二步 量词提前 43 例1 x P x x Q x 前束范式 2 6前束范式 续 把以下公式转化为前束范式 例2 x y z P x z P y z u Q x y u 解 x P x x Q x x P x x Q x x P x Q x 解 原式 x y z P x z P y z u Q x y u x y z P x z P y z u Q x y u x y z u P x z P y z Q x y u 44 2 6前束范式 续 例3 x y A x y x y B x y y A y x B x y 解 原式 x y A x y x y B x y y A y x B x y 否定深入 x y A x y x y B x y y A y x B x y x y A x y x y B x y y A y x B x y x y A x y u r B u r z A z u B u z 改名 以便量词提前 x y u r A x y B u r A z u B u z 45 定义 如果一个谓词公式wffA具有如下形式 则称其为一个前束合取范式 v1 v2 vn A11 A12 A1l1 A21 A22 A2l2 Am1 Am2 Amlm 定理 任何一个谓词公式都可以转化为与其等价的前束合取范式 例 x z y P x a z b Q y a b 就是一个前束合取范式 2 6前束范式 续 46 注意 联结词 的优先级高于 的优先级 例4 将谓词公式wffD x y P x z Q z y y R x y 化为与之等价的前束合取范式 2 6前束范式 续 解 第一步 取消多余量词 D x P x z Q z y y R x y 第二步 约束变量换名 D x P x z Q z y w R x w 第三步 消去条件联结词 D x P x z Q z y w R x w 47 第四步 将 深入 前束合取范式 2 6前束范式 续 D x P x z Q z y w R x w x P x z Q z y w R x w 第五步 将量词提前 D x z w P x Q z y R x w x z w P x R x w Q z y R x w 48 定义 如果一个谓词公式wffA具有如下形式 则称其为一个前束析取范式 v1 v2 vn A11 A12 A1l1 A21 A22 A2l2 Am1 Am2 Amlm 定理 任何一个谓词公式都可以转化为与其等价的前束析取范式 2 6前束范式 续 49 命题演算的推理规则在谓词推理理论中仍可以用 P规则 前提在推导过程中的任何时候都可以引入使用 2 7谓词演算的推理理论 但是在谓词推理中某些前提或结论受到量词限制 因此还需要补充消去或添加量词的规则以便进行谓词演算公式的推理过程 T规则 在推导过程中 如果有一个或多个公式重言蕴涵这公式S 则公式S可以引入推导之中 50 谓词演算的推理规则 1 全称指定规则US x P x P c 2 全称推广规则UG P x x P x 因为对所有的 都成立 所以对这个 也成立 因为P x 成立 所以对所有的 都成立 2 7谓词演算的推理理论 续 注意 应用UG规则必须要证明前提P x 对论域中每一个可能的x为真 51 3 存在指定规则ES x P x P c 4 存在推广规则EG P c x P x 因为有 使得 成立 所以 成立 因为 成立 所以存在 使得 成立 2 7谓词演算的推理理论 续 注意 应用ES规则 其指定的客体c不是任意的 52 例1 证明 x H x M x H s M s 其中 H x x是一个人 M x x是要死的 s 苏格拉底 2 7谓词演算的推理理论 续 证明 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 53 例2 证明 x C x W x R x x C x Q x x Q x R x 2 7谓词演算的推理理论 续 证明 1 x C x W x R x P 2 x C x Q x P 3 C a Q a ES 2 4 C a W a R a US 1 5 C a T 3 I 6 W a R a T 4 5 I 7 Q a T 3 I 8 R a T 6 I 9 Q a R a T 7 8 I 10 x Q x R x EG 9 54 例3 证明 x P x Q x x P x x Q x 2 7谓词演算的推理理论 续 证明1 把 x P x x Q x 作为附加前提 1 x P x x Q x P 附加前提 2 x P x x Q x T 1 E 3 x P x T 2 I 4 x P x T 3 E 5 x Q x T 2 I 6 x Q x T 5 E 7 P c ES 4 8 Q c US 6 9 P c Q c T 7 8 I 10 P c Q c T 9 E 11 x P x Q x P 12 P c Q c US 11 13 P c Q c P c Q c 矛盾T 10 12 I 55 证明2 利用CP规则 原题即为 x P x Q x x P x x Q x 2 7谓词演算的推理理论 续 例3 证明 x P x Q x x P x x Q x 1 x P x P 附加前提 2 x P x T 1 E 3 P c ES 2 4 x P x Q x P 5 P c Q c US 4 7 Q c T 3 6 8 x Q x EG 7 9 x P x x Q x CP 6 P c Q c T 5 E 56 例4 任何人违反交通规则 则要受罚款 因此 如果没有罚款 则没有人违反交通规则 2 7谓词演算的推理理论 续 解 符号化 表示为谓词公式 S x y x违反y 其中 x的论域为 人 M y y是交通规则 P z z是罚款 R x z x受到z 则原命题符号化为 前提H x y S x y M y z P z R x z 结论C z P z x y S x y M y 下面推导中哪里不严格 写出正确推导 57 不严格推导 2 7谓词演算的推理理论 续 1 x y S x y M y z P z R x z P 2 y S b y M y z P z R b z US 1 3 z P z P 附加前提 4 z P z T 3 E 5 P a US 4 6 P a R b a T 5 I 7 z P z R b z UG 6 8 z P