离散数学PPT教学谓词逻辑.ppt

第三章谓词逻辑 第一节谓词和量词第二节谓词演算的永真公式第三节前束范式 本章重难点 重点 1 谓词 个体域 全总体域 全称量词 存在量词 谓词公式的定义和理解 2 谓词公式的符号化形式3 谓词演算推理中的等价公式难点 1 谓词公式的翻译2 谓词演算的推理理论 为什么引入谓词逻辑 著名的苏格拉底三段论问题 所有的人都是要死的 苏格拉底是人 所以苏格拉底是要死的 无法用命题逻辑推理证明 但用自然语言逻辑可推出 是有效结论 可看出命题逻辑的局限性 由此引出谓词逻辑 一 谓词二 量词1 全称量词 x2 存在量词 x3 量词的作用4 全总个体域5 举例三 量化断言和命题的关系 第一节谓词和量词 四 谓词公式1 原子公式2 谓词演算的合式公式五 自由变元与约束变元1 量词的辖域2 自由变元与约束变元3 约束变元改名规则 第一节谓词和量词 a 小陈是大学生b 小张生于苏州c 8 3 2x是大学生小陈 客体 是大学生 谓词 是大学生刻划了x的性质x生于y生于 谓词 刻划了x和y的关系 一 谓词 x y z 谓词 刻划了x y z三元的关系 定义返回目录 1 定义 代表客体 个体 的变元叫客体 个体 变元 一 谓词 例 A表示 是大学生 则A x 表示 x是大学生 这个命题变元B表示 生于 则B x y 表示 x生于y 这个命题变元C表示 则C x y z 表示 x y z 这个命题变元A x B x y C x y z 称为谓词定义2返回 客体 个体 变元常用x y z u v 表示 刻划客体的性质或几个客体间关系的模式叫谓词 常用大写字母A B P Q 表示 2 定义 有N个客体变元的谓词称为N元谓词谓词命名式中客体变元的取值范围叫客体域例 论述域a 人 b 人 地名 c 实数 实数 实数 注意 空集不能作为论述域若A代表一特定谓词 A称为谓词常元 若A代表任意谓词 A称为谓词变元 注 1 单独的客体或单独的谓词不能构成命题 一 谓词 2 在谓词命名式中 若谓词是常元 个体变元代以论述域中某客体才成为命题 3 命题是0元谓词返回 x读作 对任意x xP x 表示 对一切x P x 为真 x P x 表示 对任意x P x 是真 xP x 表示 并非对任意x P x 是真 x P x 表示 并非对任意x P x 是真 二 量词 1 全称量词 x x读作 至少有一x 存在一x x P x 表示 存在一x 使 P x 为真 x P x 表示 并非存在一个x 使 P x 为真 二 量词 2 存在量词 x 返回目录 在P x P x y 前加上 x或 x 称变元x被存在量化或全称量化 二 量词 将谓词F x 变成命题有两种方法 a 将x取定值例 F x 表示 x是质数 那么F 4 是命题 假 b 将谓词量化例 1 xF x F x 任意的x是质数2 y y y 1 3 y y y 1 返回目录 3 量词的作用 任意谓词中任意个体变元的所有个体域称全总个体域 注 使用全总个体域后 个体变元取值范围一致 但不同论述对象须用不同的特性谓词加以刻划 例 F x x是不怕死的D x x是要死的M x x是人解 返回目录 二 量词 4 全总个体域 4 全总个体域例 若论述域是全人类 则人总是要死的可译为 xD x 有些人不怕死可译为 x D x 返回 4 全总个体域 若论述域是全总个体域 则译为 x M x D x 注意 不能译为 x M x D x 这样意义成为 所有的x x都是人并且都是要死的 全总个体域人全总个体域要死的二条规则返回 4 全总个体域故得二条规则 对全称量词 特性谓词作为蕴含式之前件而加入之 对存在量词 特性谓词作为合取项而加入之 返回 5 举例a b c d e注 命题翻译为谓词公式 由于对个体的刻划深度不同 可译成不同形式的谓词公式 返回目录 5 举例a 没有不犯错误的人解 设F x 为 x是犯错误 M x 为 x是人 则译为 x M x F x 返回 b 某些人对某些食物过敏解 设F x y 为 x对y过敏 M x 为 x是人 G x 为 x是食物 则译为 x y M x G x F x y 返回 c 尽管有人聪明 但未必一切人聪明解 设M x 为 x是人 F x 为 x聪明 则译为 x M x F x x M x F x 返回 d 如果X Y 并且Z 0 那么XY YZ解 设 X Y 为 X Y R X 为 X是实数 则译为 X Y Z R X R Y R Z X Y Z 0 XY YZ 返回 e 每个建筑物都有一些装饰品解 设A X 为 X是建筑物 B X Y 为 X有Y C X 为 X是装饰品 则可译为 X A X Y B X Y C Y 返回 1 若论述域是有限的 设是 1 2 N 则 XP X P 1 P 2 P N XP X P 1 P 2 P N 2 若论述域是可数无限则 XP X 为P 0 P 1 P 2 P N XP X 为P 0 P 1 P 2 P N 三 量化断言和命题的关系 返回目录 定义 不出现命题联结词和量词的谓词命名式P X1 X2 Xn 称为谓词演算的原子公式 返回目录 四 谓词公式 1 原子公式 谓词演算的合式公式简称谓词公式定义 1 谓词演算的原子公式是谓词演算公式2 若A B是谓词演算公式 则 2 谓词演算的合式公式 返回目录 A A B A B A B A B XA 和 XA 是谓词演算公式 3 只有有限次应用步骤1 和2 构成的公式才是谓词演算公式 注 由定义知 命题公式也是谓词公式例 XR X XR X XR X XS X XR X XS X A B C 命题公式均是谓词公式 定义 量词的辖域是邻接量词之后的最小子公式 故除非辖域是个原子公式 否则应在该子公式的两端有括号 例 XP X Q X X的辖域是P X X P X Y Q X Y P Y Z X的辖域是P X Y Q X Y 返回目录 五 自由变元与约束变元 1 量词的辖域 定义 在量词 X X辖域内变元X的一切出现叫约束出现 称这样的X为约束变元 变元的非约束出现称为自由出现 称这样的变元为自由变元 例返回目录 五 自由变元与约束变元 例 指出下列谓词公式中的自由变元和约束变元 并指明量词的辖域a X P X R X XP X Q X 解 表达式中的 X P X R X 中X的辖域是P X R X 其中的X是约束出现Q X 中的X是自由变元b X P X Y YR X Y 解 其中的P X Y 中的Y是自由变元 X是约束变元 R X Y 中的X Y是约束变元 注 在一个公式中 一个变元既可以约束出现 又可以自由出现 为避免混淆可用改名规则对变元改名 返回 五 自由变元与约束变元 1 若要改名 则该变元在量词及该量词的辖域中的所有出现须一起更改 3 约束变元改名规则 2 改名时所选用变元必须是量词辖域内未出现的 最好是公式中未出现的 注 对自由变元换名 可称为代入例返回目录上一页26下一页28 例1 X P X Y YR X Y 可改为 X P X Y ZR X Z 例2 XP X Q X 可改为 YP Y Q X 例3 X A X B X Y C X D W 可改为 X A X B X Y C Z D W 注意 Z A Z B Z Y C X D W 不可改为 Y A Y B Y Y C X D W 想想为什么 返回 3 约束变元改名规则 一 基本定义二 谓词演算的基本永真公式上一节下一节 第二节谓词演算的永真公式 1 公式A和B在个体域上等价定义 一 基本定义 对公式A和B中的谓词变元 包括命题变元 指派任一在E上有定义的确定的谓词 指派E中任一确定的个体 若所得命题有相同的真值 称在E上A B 2 A与B等价定义 若两公式A B在任意论述域上都等价 称A B 3返回目录 3 对任一公式A 若在论述域E上 对A中的谓词和个体变元进行指派后 所得命题 一 基本定义 1 都真 称A在E上永真或在E上有效 若E任意 称A永真 2 至少一个为真 称A在E上可满足 3 都假 称A永假或在E上不可满足 若E任意 称A永假或不可满足 注 当谓词公式A的个体域有限 谓词变元的指派也有限 才能用真值表判定A是否为永真 例 返回 例 当A x P x XP x 且P x 只能解释 1 R x x是质数 2 S x x是合数 论述域为 3 4 判定A x 是否为永真解 P x xP x XP x R x 31 1 1S x 30 1 0R x 40 1 0S x 41 1 1所以 一般用真值表难以判定谓词公式是否为真 必须使用推导方法 首先讨论基本的谓词公式永真公式 一 基本定义 1 命题演算的永真公式也是谓词演算的永真公式2 含有量词的谓词演算的永真公式3 量词的否定4 量词辖域的扩展和收缩5 结束量词的分配公式6 量词对 及 的处理7 关于多个量词的永真式返回返回目录 二 谓词演算的基本永真公式 例 XP X XR X XP X XR X 例 Q X XP X Q X XP X 返回 1 命题演算的永真公式也是谓词演算的永真公式 1 XA A XA A这里A不含自由变元X证 因A的真值与X无关例 XP y z P y z 但是 yP y z P y z 不一定成立 2 返回 2 含有量词的谓词演算的永真公式 2 a XP X P Y 或 XP X P X b P Y XP X 或P X P X c XP X XP X 证 a 对 XP X 为真 则对某一具体Y P Y 为真b 对某一确定的Y P Y 为真 即则存在一X 使P X 为真c XP X P X XP X 返回 2 含有量词的谓词演算的永真公式 3 a XP X X P X b XP X X P X 证法1 3 量词的否定 a 并非对任意x P X 是真 等价于 至少存在一个x 使P X 为假 b 并非存在一个x 使P X 为真 等价于 对所有的x P X 为假 注 1 从上述公式可以看出 X和 X具有对偶性 将 X与 X互换 可看出 2 出现在量词之前的否定 是否定量词 而是否定被量化了的整个命题 证法2返回 证法2 对个体域为 a1 a2 an 可详细证明如下 XP X P a1 P a2 P an P a1 P a2 P an X P X 返回 3 量词的否定 4 a XA X P X A X P b XA X P X A X P c XA X P X A X P d XA X P X A X P 这里P是不含自由变元X的谓词公式 证明 a 因P的值与x无关 若P为真 等价式两边都真 若P为假 两边也都为 XA X 例返回82上一页26下一页28 4 量词辖域的扩展和收缩 例1 XA X Y P Y X X Y P Y XP X Y XP X Z X P X Y XP X Z 定理证法2 证明 当个体域为 a1 a2 an 证明如下 其余式子证明类同 XA X P P a1 P a2 P an P P a1 P P a2 P P an P X A X P 例2返回 4 量词辖域的扩展和收缩 例2 X Y P X Q Y XP X YQ Y 证明 X Y P X Q Y X Y P X Q Y X P X YQ Y X P X YQ Y XP X YQ Y XP X YQ Y 4返回 4 量词辖域的扩展和收缩 5 量词的分配公式 a X A X B X XA X XB X 证明 因为对一切X A X B X 为真 所以对一切XA X 为真 对一切XB X 为真 b X A X B X XA X XB X 证 X A X B X X A X X B X X A X B X X A X X B X 两边取非 X A X B X X A X X B X X A X B X XA X XB X C返回 5 量词的分配公式 a X A X B X XA X XB X 证法二 证 对个体域为 a1 a2 an X A X B X XA X XB X A a0 B a0 A an B an A a0 A a1 A an B a0 B a1 B an XA X XB X b 返回 5 量词的分配公式 c X A X B X XA X XB X 5 量词的分配公式 证 因存在x使A X B X 为真 故该X使A X 为真 该X使B X 为真 即 XA X XB X 为真 注意 注意逆方向不成立即 XA X XB X X A X B X 不成立证 举反例 设论述域是整数 A x x为奇数 B x x为偶数 则 XA X XB X 为真 但 X A X B X 为假d返回 d XA X XB X X A X B X 证 若 XA X 为真 则 X A X B X 为真 若 XB X 为真 则 X A X B X 亦真 注意逆方向不成立 返回 5 量词的分配公式 注 只须应用量词对 的恒等式即可推出例 证明 XA X XB X X A X B X 证 XA X XB X XA X XB X X A X XB X X A X B X X A X B X 返回 6 量词对 及 的处理 X YP X Y Y XP X Y 二者同义 X YP X Y Y XP X Y X YP X Y X YP X Y y xP x y x yP x y 证例返回 7 关于多个量词的永真式 注意逆方向不成立例 设论述域为有理数 P x y 表示x y 0 则 x y x y 0为真 但是 y x x y 0为假 返回 7 关于多个量词的永真式 y xP x y x yP x y 证法1 存在一y 对任意的x P x y 为真即对任意x存在 对这个y而言 使P x y 为真证法2 y xP x y P a1 a1 P a1 a2 P a1 an P a2 a1 P a2 a2 P an an P an a1 P an a2 P an an P a1 a1 P a1 a2 P a1 an P a1 a1 P a1 a2 P a1 an P a1 a1 P a1 a2 P a1 an x yP x y 返回 7 关于多个量词的永真式 x yP x y x yP x y y xP x y y xP x y y xP x y y xP x y 7 关于多个量词的永真式 注 上述公式 当论述域为 a1 a2 时 亦均可用列举法证明例 对第 式证明返回 一 前束范式1 定义2 任意谓词公式均可化为前束范式3 举例二 前束合取范式和前束合取析取范式1 定义2 任意谓词公式均可化为前束合取范式和前束合取析取范式3 举例上一节下一节 第三节前束范式 1 定义 量词均在谓词公式开头 作用域延伸到整个谓词公式末尾的谓词公式称为前束范式 一 前束范式 例1 x y z Q x y R z 例2 x y P x y Q y 返回目录 证 1 把否定词深入到命题变元和谓词前面 2 利用A xB x x A B x A xB x x A xB x 把量词推到前面 3 利用改名规则 xA x xB x uA u xB x u x A u B x 把量词推到前面返回目录 2 任意谓词公式均可化为前束范式 3 举例例1把 x y zP x y z P y z uQ x y u 化为前束范式 前束范式 解 原式 x y z P x z P y z uQ x y u x y z P x z P y z uQ x y u x y z u P x y P y z Q x y u 例2返回目录 3 举例例2 把 xP x y xQ x z 化为前束范式解 原式 xP x z uQ z u x u P x y Q z u 返回 前束范式 1 定义 若谓词公式是前束范式且作用域为合取范式 则称为前束合取范式 二 前束合取范式和前束合取析取范式 前束合取范式形式 u1 u2 un A11 A1m1 An1 Anmn 定义 若谓词公式是前束范式且作用域为析取范式 则称为前束析取范式 前束析取范式形式 u1 u2 un A11 A1m1 An1 Anmn 返回目录 2 任一谓词公式均可化为前束析取范式或前束合取范式 二 前束合取范式和前束合取析取范式 证 首先把谓词公式化为前束范式 然后对作用域用命题演算方法转化之 返回目录 3 举例例1 x y zP x y z uQ x u uR x u 化为前束合取范式 二 前束合取范式和前束合取析取范式 解 原式 x y z P x y z uQ x u vQ y v x y z u v P x y z Q x u Q y v x y z u v P x y z Q y v Q x u Q y v 返回目录 一 命题演算中的所有推理规则都是谓词演算中的推理规则 谓词演算的所有永真式也是谓词推理规则 4 谓词演算与推理规则 二 四条重要的推理规则1 全称指定规则 简记为US2 存在指定规则 简记为EG3 存在推广规则 简记为EG4 全称推广规则 简记为UG三 举例上一节 1 全称指定规则简记为US规则 xP x P c 二 四条重要的推理规则 返回目录 含义 对一切x P x 为真 可推得任意一个确定的c 使P c 为真 意义 删除全称量词例 x P x y yQ x y P c y yQ c y 但 x P x y yQ x y P y y yQ y y 错误 2 存在指定规则简记为EG规则 xP x P c 含义 至少存在一个x使得A x 为真 即可推得有一个确定的c 使P c 为真注意 选定的变元c必须是谓词公式中没有出现过的 例 y Q y Q x xA x z y Q y Q y A y z 均错 x A x z A y A y z A y 均错返回目录 二 四条重要的推理规则 3 存在推广规则简记为EG规则P c xP x 含义 c是某个确定的个体 若P c 为真 则 xP x 为真注意 c不能出现在P c 中的x的辖域中例 x P c zQ c z x xP x zQ x z 为错 x P c zQ c z y xP y zQ y z 正确返回目录 二 四条重要的推理规则 4 全称推广规则简记为UG规则P c xP x 含义 若对个体域中每一个客体c P c 断言为真则 xP x 为真P x xP x 注意 1 P x 中的x不是使用ES而引入的 二 四条重要的推理规则 2 若x是使用us而自由的 后继推导中 使用ES而引入的新变元都没有在P x 中自由出现的情况下 才能使用UG规则 所以 一般推导中只能先采用ES规则 后采用US规则 例返回目录 例 观察下列推理过程y x 11 x yP x y p2 yP c y T1 US3 P c d T2 ES4 yP y d T3 UG5 y xP y x T4 EG错在何处 第4条错误例 x y y x 1 正确 但是 y x y x 1 错误返回 二 四条重要的推理规则 例1 下列推导有何错误 1 1 y P y Q y P 2 P a P b T1 ES解 2 应改为P a P a 2 1 xP x Q x P 2 P x Q x P1 us解 仅当 x P x Q x 为真时 才能推出 P x Q x 3 1 xR x x Q x R x P 2 P a x Q x R x T1 ES解例2返回目录 三 举例 3 应改为 1 xR x Q x R x P 2 xR x x Q x R x T1 3 R a x Q x R x T2 ES返回 三 举例 例2 会议的每一个成员都是专家并且都是党员 一些成员是老人 三 举例 所以成员有一些是老党员 试构造一个证明 解 设C x 表示 x是会议成员 S x 表示 x是专家 W x 表示 x是党员 O x 表示 x是老人 则 x C x W x S x x C x O x x O x W x 证例3返回 例2证 1 x C x W x S x P2 x C x O x P3 C y W y S y T1 US4 C y O y T2 ES3 C y O y T2 ES4 C y W y S y T1 US5 C y T36 W y S y T5 47 O y T38 W y T69 O y W y T7 810 x O x W x T9 EG是否有错 错在哪里 返回 三 举例 例3 证明 x P x Q x x R x Q x x R x P x 证 1 x P x Q x P2 x R x Q x P3 P x Q x T1 US4 R x Q x T2 US5 Q x R x T46 P x R x T3 57 x R x P x T6 UG例4返回 三 举例 例4 证明 x P x Q x xP x xQ x 法一 附加前提法 略 自己动手做 法二 用归谬法1 x P x Q x P2 xP x xQ x P 归谬法3 x P x x Q x T24 x P x T35 x Q x T 6 P y T4 ES7 Q y T5 US8 P y Q y T6 79 P y Q y T1 US10 P y Q y P y Q y T8 9矛盾 三 举例 返回 本章小结 本章是因为命题逻辑的局限性才引入的谓词逻辑 重点介绍了谓词和量词及谓词公式的符号化 谓词等价式的转换和谓词演算的推理理论 通过研究命题本身的内部结构关系才看出命题结构的相似性 共通性和公用性 课后练习和作业 课后练习 P74 1 所有奇数题 P75 9 10P76 12 13课后作业 P74 1 所有偶数题 P76 11 14 谢谢