离散数学左孝陵第二章.pptVIP

第二章谓词逻辑 1谓词的概念与表示法 2命题函数与量词 3谓词公式与翻译 4变元的约束 5谓词演算的等价式与蕴含式 6前束范式 7谓词演算的推理理论 1谓词的概念与表示法 在研究命题逻辑中 原子命题是命题演算中最基本的单位 不再对原子命题进行分解 这样会产生二大缺点 1 不能研究命题的结构 成分和内部逻辑的特征 2 也不可能表达二个原子命题所具有的共同特征 甚至在命题逻辑中无法处理一些简单又常见的推理过程 例 苏格拉底论证是正确的 但不能用命题逻辑的推理规则推导出来 所有的人总是要死的 A 苏格拉底是人 B 所以苏格拉底是要死的 C 1谓词的概念与表示法 1 谓词 定义 用以刻划客体的性质或关系的即是谓词 我们可把陈述句分解为二部分 主语 名词 代词 和谓语 动词 例 张华是学生 李明是学生 则可把它表示成 H 表示 是学生 j 表示 张华 m 表示 李明 则可用下列符号表示上述二个命题 H j H m H作为 谓词 或者谓词字母 用大写英文字母表示 j m为主语 称为 客体 或称 个体 1谓词的概念与表示法 1 谓词填式 谓词字母后填以客体所得的式子 例 H a b 2 若谓词字母联系着一个客体 则称作一元谓词 若谓词字母联系着二个客体 则称作二元谓词 若谓词字母联系着n个客体 则称作n元谓词 3 客体的次序必须是有规定的 例 河南省北接河北省 nLb写成二元谓词为 L n b 但不能写成L b n 2命题函数与量词 1 命题函数客体在谓词表达式中可以是任意的名词 例 C 总是要死的 j 张三 t 老虎 e 桌子 则C j C t C e 均表达了命题 在上面的例子中 C 表示 总是要死的 x 表示变元 客体变元 则C x 表示 x总是要死的 则称C x 为命题函数 定义 由一个谓词字母和一个非空的客体变元的集合所组成的表达式 称为简单命题函数 2命题函数与量词 讨论定义 a 当简单命题函数仅有一个客体变元时 称为一元简单命题函数 b 若用任何客体去取代客体变元之后 则命题函数就变为命题 c 命题函数中客体变元的取值范围称为个体域 论述域 例 P x 表示x是质数 这是一个命题函数 其值取决于个体域 可以将命题函数 命题 有两种方法 2命题函数与量词 a 将x取定一个值 如 P 4 P 5 b 将谓词量化 如 xP x xP x 个体域的给定形式有二种 具体给定 如 j e t 全总个体域 任意域 所有的个体从该域中取得 2命题函数与量词 2 量词 1 全称量词 为全称量词符号 读作 对于所有的 对任一个 对一切 例 这里所有的都是苹果 可写成 xA x 或 x A x 几种形式的读法 xP x 对所有的x x是 x P x 对所有x x不是 xP x 并不是对所有的x x是 x P x 并不是所有的x x不是 2命题函数与量词 例 将 对于所有的x和任何的y 如果x高于y 那么y不高于x 写成命题表达形式 解 x y G x y G y x G x y x高于y 2 存在量词 为存在量词符号 读作 存在一个 对于一些 对于某些 至少存在一个 这里存在着这样的 等等 表达式的读法 xA x 存在一个x 使x是 x A x 存在一个x 使x不是 xA x 不存在一个x 使x是 x A x 不存在一个x 使x不是 2命题函数与量词 例 a 存在一个人 b 某个人很聪明 c 某些实数是有理数将 a b c 写成命题 解 规定 M x x是人 C x x是很聪明 R1 x x是实数 特性谓词 R2 x x是有理数 则 a xM x b x M x C x c x R1 x R2 x 3 量化命题的真值 决定于给定的个体域给定个体域 a1 an 以 a1 an 中的每一个代入 xP x P a1 P an xQ x Q a1 Q an 3谓词公式与翻译 1 谓词公式原子谓词公式 不出现命题联结词和量词的谓词命名式称为原子谓词公式 并用P x1 xn 来表示 P称为n元谓词 x1 xn称为客体变元 当n 0时称为零元谓词公式 定义 谓词公式的归纳法定义 原子谓词公式是谓词公式 若A是谓词公式 则 A也是谓词公式 若A B都是谓词公式 则 A B A B A B A B 都是谓词公式 若A是谓词公式 x是任何变元 则 xA xA也都是谓词公式 3谓词公式与翻译 只有按 所求得的那些公式才是谓词公式 谓词公式又简称 公式 例1 任何整数或是正的 或是负的 解 设 I x x是整数 R1 x x是正数 R2 x x是负数 此句可写成 x I x R1 x R2 x 例2 试将苏格拉底论证符号化 所有的人总是要死的 因为苏格拉底是人 所以苏格拉底是要死的 解 设M x x是人 D x x是要死的 M s 苏格拉底是人 D s 苏格拉底是要死的 3谓词公式与翻译 写成符号形式 x M x D x M s D s 2 由于对个体描述性质的刻划深度不同 可翻译成不同形式的谓词公式 4变元的约束 1 辖域 紧接在量词后面括号内的谓词公式 例 xP x x P x Q x 若量词后括号内为原子谓词公式 则括号可以省去 2 自由变元与约束变元约束变元 在量词的辖域内 且与量词下标相同的变元 自由变元 当且仅当不受量词的约束 例 xP x y x P x y P x y 4变元的约束 3 约束变元的改名规则任何谓词公式对约束变元可以改名 我们认为 xP x y 和 zP z y 是一等价的谓词公式 但是需注意 不能用同一变元去表示同一谓词公式中的二个变元 例如 yP y y 是不正确的 下面介绍约束变元的改名规则 a 在改名中要把公式中所有相同的约束变元全部同时改掉 b 改名时所用的变元符号在量词辖域内未出现的 4变元的约束 例 xP x yR x y 可改写成 xP x zR x z 但不能改成 xP x xR x x xR x x 中前面的x原为自由变元 现在变为约束变元了 4 区别是命题还是命题函数的方法 a 若在谓词公式中出现有自由变元 则该公式为命题函数 b 若在谓词公式中的变元均为约束出现 则该公式为命题 例 xP x y z 是二元谓词 y xP x y z 是一元谓词 而谓词公式中如果没有自由变元出现 则该公式是一个命题 4变元的约束 举例 例1 没有不犯错的人 解 设F x 为 x犯错误 M x 为 x是人 特性谓词 可把此命题写成 x M x F x x M x F x 例2 x是y的外祖父 x是z的父亲且z是y的母亲 设P z z是人 F x z x是z的父亲 M z y z是y的母亲 则谓词公式可写成 z P z F x z M z y 5 代入规则 对公式中的自由变元的更改叫做代入 a 对公式中出现该自由变元的每一处进行代入 b 用以代入的变元与原公式中所有变元的名称不能相同 4变元的约束 6 个体域 论述域 客体域 用特定的集合表示的被约束变元的取值范围 1 个体域不同 则表示同一命题的谓词公式的形式不同 例 所有的人必死 令D x x是要死的 下面给出不同的个体域来讨论 个体域为 人类 则可写成 xD x 个体域为任意域 全总个体域 则人必须首先从任意域中分离出来 设M x x是人 称M x 为特性谓词 命题可写成 x M x D x 4变元的约束 2 个体域不同 则表示同一命题的值不同 Q x x 5 3 对于同一个体域 用不同的量词时 特性谓词加入的方法不同 对于全称量词 其特性谓词以前件的方式加入 对于存在量词 其特性谓词以与的形式加入 4变元的约束 例 设个体域为 白虎 白猫 黄咪 黄猫 同时令C x x是猫 特性谓词 B x x是黑色的 A x x是动物 描述命题 所有的猫都是动物 即 x C x A x T 真命题 写成 x C x A x F 则为假命题了 x C x A x T T T T T x C x A x T T F F F 描述命题 一些猫是黑色的 x C x B x F F F F F而 x C x B x F F T T T 4变元的约束 7 量词对变元的约束 往往与量词的次序有关 例 y x x y 2 表示任何y均有x 使得x y 2 5谓词演算的等价式与蕴含式 基本定义 定义 A B为二个谓词公式 E为它们共同个体域 若对A和B的任一组变元进行赋值 使得A和B的值相同 则称A和B遍及E是互为等价的 记为A B或A E B 定义 给定谓词公式A E是A的个体域 若给A中客体变元指派E中的每一个客体名称所得命题的值均为真 则称A在E中是永真的 若E为任意域则称A是永真的 5谓词演算的等价式与蕴含式 定义 给定谓词公式A E是A的个体域 若给A中客体变元指派E中每一个客体名称 在E中存在一些客体名称 使得指派后的真值为 T 则A称是可满足的 定义 若给A中客体变元指派个体域中任一客体名称 使命题的值均为 F 则称A是永假的 1 不含量词的谓词公式的永真式 只要用原子谓词公式去代命题公式的永真式中的原子命题变元 则在第一章中永真蕴含式和等价公式均可变成谓词演算中的永真式 5谓词演算的等价式与蕴含式 命题逻辑谓词逻辑 x x x x x x x x x x x x x x x 5谓词演算的等价式与蕴含式 2 含有量词的等价式和永真蕴含式设个体域为 S a1 a2 an 我们有 xA x A a1 A a2 A an xA x A a1 A a2 A an 上例说明 若个体域是有限的 则可省掉量词 若个体域是无限的 则可将上述概念推广从而省去量词 不过要注意这是由无限项组成的命题 5谓词演算的等价式与蕴含式 例 设个体域为 N 0 1 2 P x 表示 x 3 则可写出 xP x P 0 P 1 P i xP x P 0 P 1 P i 下面分类介绍在谓词公式中含有量词的等价式和永真蕴含式 1 量词转换律 E25 Q3 xP x x P x E26 Q4 xP x x P x 下面证明 设个体域为 S a1 a2 an 5谓词演算的等价式与蕴含式 xP x P a1 P a2 P an P a1 P a2 P an x P x 下面举例说明量化命题和非量化命题的差别 否定形式不同例 否定下列命题 a 上海是一个小城镇A s b 每一个自然数都是偶数 x N x E x 上述二命题的否定为 a 上海不是一个小城镇 A s b 有一些自然数不是偶数 x N x E x x N x E x x N x E x x N x E x 5谓词演算的等价式与蕴含式 结论 对于非量化命题的否定只需将动词否定 而对于量化命题的否定不但对动词进行否定而且对量词同时进行否定 其方法是 x的否定变为 x x的否定变为 x 2 量词辖域的扩张及其收缩律E27 Q6 xA x P x A x P Q7 xA x P x A x P E28 Q9 xA x P x A x P Q8 xA x P x A x P P为不含有变元 的任何谓词公式 5谓词演算的等价式与蕴含式 证明E27 Q6 设个体域为 S a1 a2 an xA x P A a1 A a2 A an P A a1 P A a2 P A an P x A x P E30 Q14 xA x B x A x B E31 Q15 xA x B x A x B E32 Q16 A xB x x A B x E33 Q17 A xB x x A B x 证明E30 Q14 设个体域为 S a1 a2 an x A x B A a1 B A an B A a1 B A an B 5谓词演算的等价式与蕴含式 A a1 A an B x A x B x A x B xA x B 3 量词分配律E24 Q10 x A x B x xA x xB x E23 Q11 x A x B x xA x xB x I18 Q12 x A x B x xA x xB x I17 Q13 xA x xB x x A x B x E29 Q18 x A x B x xA x xB x I19 Q19 xA x xB x x A x B x 5谓词演算的等价式与蕴含式 证明E24 Q10 和I19 Q19 设个体域为 S a1 a2 an E24 Q10 x A x B x A a1 B a1 A an B an A a1 A an B a1 B an xA x xB x I19 Q19 xA x xB x xA x xB x x A x xB x A a1 A an B a1 B an A a1 B a1 A a1 B an A an B a1 A an B an 5谓词演算的等价式与蕴含式 A a1 B a1 A an B an x A x B x x A x B x 4 量词的添加和除去的永真蕴含式Q1 xP x P y Q2P y xP x Q5 xP x xP x xP P xP P P为不含x变元 Y是 个体域中任一元素 5谓词演算的等价式与蕴含式 5 含有多个量词的永真式 量词出现的次序直接关系到命题的含义 x y 表示 无论选定一个什么样的x值总能找到一个y能使x和y y x 表示 只选取一个y值 以致无论怎样选定一个x 能够使y和x 下面列出对应的表达式可以看出其不同处 设x的个体域为 a1 a2 an y的个体域为 b1 b2 bn 则 x yP x y yP a1 y yP an y 5谓词演算的等价式与蕴含式 P a1 b1 P a1 bn P an b1 P an bn y xP x y xP x b1 xP x bn P a1 b1 P an b1 P a1 bn P an bn 例 x y的个体域 鞋子 P x y 和 配成一双鞋子 x yP x y T y xP x y F 5谓词演算的等价式与蕴含式 在含有多个量词的谓词公式中 x y x y的位置是可以改变的 且不影响命题的真值 例 x y的个体域为N 0 1 2 则 x yP x y yP 0 y yP i y P 0 0 P 0 1 P 0 j P i 0 P i 1 P i j P 0 0 P 1 0 P i 0 P 0 1 P 1 1 P i 1 xP x 0 xP x 1 xP x j y xP x y 5谓词演算的等价式与蕴含式 同样 x yP x y y xP x y 量词转换律的推广应用 把 深入到谓词公式前面去的方法 x y zP x y z x y zP x y z x y zP x y z x y z P x y z 两个量词 所组成的谓词公式的等价式和永真蕴含式 8个 x yP x y y xP x y x yP x y y xP x y y xP x y x yP x y y xP x y x yP x y 5谓词演算的等价式与蕴含式 x yP x y y xP x y x yP x y y xP x y y xP x y x yP x y x yP x y y xP x y 6 谓词公式的对偶式 定义 在一个谓词公式A中 其中不出现 词 把公式A中 F T 变为公式A 中 T F 则称A 是A的对偶式 定理 若谓词公式A B 则A B 若谓词公式A B 则B A 这里A B有同样的个体域 5谓词演算的等价式与蕴含式 例 I17 Q13 xA x xB x x A x B x I18 Q12 xA x xB x x A x B x 6前束范式 定义 一个公式 如果量词均非否定地在全式的开头 它们的作用域延伸到整个公式的末尾 则称此公式叫前束范式 例 x y z Q x y R z 前束范式 定理 任何一个谓词公式均和一个前束范式等价 证明 利用量词转换把 深入到原子谓词公式前 利用约束变元的改名规则 利用量词辖域的扩张收缩律 把量词移到全式的最前面 这样一定可得到等价的前束范式 6前束范式 例 xP x R x yP y R x y P y R x 例 把 xP x xQ x 变成前束范式 xP x xQ x xP x xQ x x P x xQ x x P x Q x 7谓词演算的推理理论 1 含有量词的特殊永真式 定义 设A x 是一个谓词公式 x是其中的自由变元 若把y代入到A x 里而不会产生变元的新的约束出现 则称A x 对于y是自由的 例 下面A x 对于y是自由的 A x zP z Q x z 这里x为自由变元 若用y去取代A x 中的x A y zP z Q y z 这里y也仍为自由变元 7谓词演算的推理理论 下面A x 对于y不是自由的 A x y S x S y x为自由变元 若用y代入A x 的x中去得 A y y S y S y y变为约束变元了 产生了新的约束出现 如有必要代入y 则应先将式中的约束变元y改名 z S x S z 然后代入y z S y S z y仍为自由变元 归结 判定A x 对于y是自由的 只要看公式A x 中 y y的辖域内有没有x的自由出现就行 若有x的自由出现则A x 对于y不是自由的 若无的x自由出现则一定可以肯定A x 对于y是自由的 7谓词演算的推理理论 下面分别介绍四个推理规则 1 全称指定规则 US规则 如果对个体域中所有客体x A x 成立 则对个体域中某个任意客体c A c 成立 该规则表示成 xA x A c x c 个体域 2 全称推广规则 UG规则 如果能够证明对个体域中每一个客体c 命题A c 都成立 则可得到结论 xA x 成立 该规则表示成 A x xA x 7谓词演算的推理理论 3 存在指定规则 ES规则 如果对于个体域中某些客体A x 成立 则必有某个特定的客体c 使A c 成立 该规则表示成 xA x A c 例 x的个体域为I 整数 P x x是偶数 Q x x是奇数 xP x xQ x T但P c Q c F 7谓词演算的推理理论 4 存在推广规则 EG规则 如果对个体域中某个特定客体c 有A c 成立 则在个体域中 必存在x 使A x 成立 该规则表示成 A c xA x 2推论规则及使用说明命题逻辑中的P T CP规则和简接证明法 都可以引用到谓词逻辑的推论规则中来 不过要注意对量词做适当处理 其方法是 用US ES在推导中去掉量词 用UG EG使结论量化 7谓词演算的推理理论 规则使用说明 1 在使用ES US时一定要是前束范式 2 推导中连续使用US规则可用相同变元 xP x P y xQ x Q y 3 推导中既ES用 又用US 则必须先用ES 后用US方可取相同变元 反之不行 xP x P y xQ x Q y 4 推导中连续使用ES规则时 使用一次更改一个变元 7谓词演算的推理理论 例 证明苏格拉底论证 x M x D x M s D s 1 M s P 2 x M x D x P 3 M s D s US 4 D s T例 证 x H x M x xH x xM x 7谓词演算的推理理论 1 xH x P 2 H c ES 3 x H x M x P 4 H c M c US 5 M c T 6 xM x EG例 证 x P x Q x xP x xQ x 1 xP x 引入前件 2 x P x Q x P 3 P c Q c ES 7谓词演算的推理理论 4 P c US 5 Q c T 6 xQ x EG 7 xP x xQ x CP例 证明 x P x Q x xP x xQ x 1 xQ x 假设前提 2 xQ x T 3 Q c US 4 xP x P 7谓词演算的推理理论 5 P c US 6 P c Q c T 7 x P x Q x UG 8 x P x Q x P 9 x P x Q x x P x Q x T 10 F例 下列结论能否从前提中推出 x P x Q x Q a x P x a为x个体域中一个元素 1 Q a P 2 x P x Q x P 7谓词演算的推理理论 3 P a Q a US 4 P a T 5 x P x UG在使用US ES UG EG这四条规则时 要注意严格按照它们的规定去使用 7谓词演算的推理理论 书中例4证明 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 附加前提 4 z P z T 3 5 P a US 4 6 P a R b a T 5 7 P a R b a T 6 8 z P z R b z UG 7 9 z P z R b z T 8 7谓词演算的推理理论 10 y S b y M y T 2 9 11 y S b y M y T 10 12 S b c M c US 11 13 S b c M c T 12 14 S b c M c T 13 15 y S b y M y UG 14 16 x y S x y M y UG 15 17 z P z x y S x y M y CP 3 16 7谓词演算的推理理论 例 二个量词的推理比较复杂 xP x x P x Q x R x xP x xQ x x y R x R y 1 xP x P 2 P w ES 3 P w Q w T 4 xP x x P x Q x R x P 5 x P x Q x R x T 7谓词演算的推理理论 6 P w Q w R w US 7 R w T 8 xR x EG 9 xQ x P 10 Q z ES 11 P z Q z T