离散数学课件 第二章 谓词逻辑-2nd.pdf

1 43 第二章 谓词逻辑 大连理工大学软件学院 陈志奎 教授 办公室 综合楼411 Tel 87571525 实验室 教学楼A318 A323 Tel 87571620 24 MobileEmail zkchen zkchen00 2 43 回顾 谓词 个体 量词 一元 多元 域 全称 存在 合式谓词公式 定义 5条 自由变元和约束变元 含有量词的等价式和永真蕴含式 谓词公式的解释 3 43 记忆规律 xy yx yx xy xy yx yx xy 1B 2B 4B 3B 5B 7B 6B 8B 4 43 2 2谓词逻辑中的推理规则 推理规则 5 43 规则1 约束变元的改名规则 对约束变元进行换名 使得一个变元在一 个公式中只呈一种形式出现 规则如下 欲改名之变元应是某量词作用范围内的变 元 且应同时更改该变元在此量词辖域内的 所有约束出现 而公式的其余部分不变 新的变元符号应是此量词辖域内原先没有使 用过的 最好是公式中未出现过的符号 x P xy P y 等价于 6 43 规则1 约束变元的改名规则 例 对公式 进 行换名 使各变元只呈一种形式出现 解 需要对约束变元x y进行换名 不对的 x P x y yQ x y z S x z u P u y Q u v z S x z v u P u vQ u v z S vx z z S x z zQ u y u P u z 7 43 规则2 自由变元的代入规则 对公式中自由变元的更改叫做代入 规则 如下 欲改变自由变元的名 必改在公式中的每一 处自由出现 新变元不应在原公式中以任何约束形式出现 例 对公式 的变元 x y的自由出现用w t代入 得 x P x y x y z S x z yQ x P x t x y z S w z yQ 8 43 例如 例如 对公式对公式 x P x Q x x P x R x 为清楚起见 可对第二个约束变元为清楚起见 可对第二个约束变元x进行换名进行换名 x P x Q x y P y R y 又例如 又例如 对公式对公式 x P x R x y Q x y 可对约束变元可对约束变元x进行换名 得进行换名 得 z P z R z y Q x y z P z R x y Q x y y P y R y y Q x y 错误 错误 9 43 规则3 命题变元的代换规则 用任一谓词公式Ai 代换永真公式 中某一 命题变元Pi 的所有出现 所得到的新公式 B 仍然是永真式 但在Ai 的个体变元中不 应有 中的约束变元出现 并有 BB 10 43 规则4 取代规则 设 都是含n个 自由变元的谓词公式 且A 是A的子公式 若在A中用B 取代A 的一处或多处出现后 所得的新公式是B 则有 如果A为 永真式 则B也是永真式 1212 nnA x xxB x xx AB 11 43 谓词逻辑的推理 在谓词逻辑中 推理的形式结构仍为在谓词逻辑中 推理的形式结构仍为 CHHH n 21 若 是永真式 则称由前提 逻辑的推出结论 若 是永真式 则称由前提 逻辑的推出结论C 在此 在此 C均为谓词公式 均为谓词公式 n HHH 21 n HHH 21 CHHH n 21 12 43 规则5 量词的增加和删除规则 全称特指规则US 从 可得出结论A y 其中y是个体域中任一个体 即 注意 y不能和A x 中其它指导变元重名 存在特指规则ES 从 可得出结论A a 其中a是 和在此之前不曾出现过的个体常 量 即 注意 a不能和指定前提中任一自由变元同名 也不能和使用本规则以前任一推导步骤上得到的 公式的自由变元同名 x A x x A xA y x A x x A x x A xA a 13 43 规则5 量词的增加和删除规则 存在推广规则EG 从A x 可得出结论 其 中x是个体域中的某一个个体 即 注意 y不和A x 中其他自由变元或指导变元同名 全称推广规则UG 从A x 可得出结论 其中x是个体域中的任意个体 即 使用条件 1 x不是给定前提中任一公式的自由变元 2 x不是在前面推导步骤中使用ES规则引入的 变元 3 若在前面推导过程中使用ES规则引入新变 元u时 x是自由变元 那么在A x 中 u应 约束出现 A xy A y A xy A y y A y y A y 14 43 谓词逻辑中的推理 例1 证明 x M xx H xM x x H x 试证明是前提 和的逻辑结果 1 2 1 3 4 3 5 x H xP H yES x H xM xP H yM yUS M y 2 4 6 5 T x M xEG 15 43 谓词逻辑中的推理 例2 试证明 证明 x P xQ xx Q xR xx P xR x 1 2 1 3 4 3 5 x P xQ xP P xQ xUS x Q xR xP Q xR xUS 2 4 6 5 P xR xT x P xR xUG 16 43 谓词逻辑中的推理 例3 证明 x R xy D yL x y x R xy S yL x y x D xS x 已知前提 试推出结论 1 2 1 3 x R xy D yL x yP R ay D yL a yES R a 2 4 2 5 4 6 T y D yL a yT D uL a uUS x R xy S yL x y 7 6 8 3 7 P R ay S yL a yUS y S yL a yT 17 43 谓词逻辑中的推理 9 8 10 9 11 S uL a uUS L a uS uT D uS uT 5 10 12 11 x D xS xUG x R xy D yL x y x R xy S yL x y x D xS x 已知前提 试推出结论 接上页 18 43 例例4 指出下面推理的错误指出下面推理的错误 设设D x y 表示表示 x可被可被y 整除整除 个体域 为个体域 为 5 7 10 11 因为因为D 5 5 和和D 10 5 为真 所以 为真 所以 xD x 5 为真为真 因为因为D 7 5 和和D 11 5 为假 所以 为假 所以 xD x 5 为假为假 但有下面的推理过程 但有下面的推理过程 1 xD x 5 前提前提 2 D z 5 1 ES 3 xD x 5 2 UG 因此 因此 xD x 5 xD x 5 错 错 19 43 反证法举例 例5 证明 x A xB xx B xC xx C x x A x 给定前提 试推出结论 1 2 1 3 x A xP xA xT A a 假设前提 2 4 5 4 6 ES x A xB xP A aB aUS B a 3 5 7 B C 8 7 9 T xxxP B aC aUS C a 6 8 10 C T xxP 20 43 反证法举例 11 10 12 9 11 13 A F C aUS C aC aT xx 1 12 接上页 21 43 谓词逻辑中的推理 例6 使用CP规则证明 证明 因此原来的证明转化为证明下式 xyP xQ yxP xy Q y xP xy Qy x P xy Q yx P xy Q y 由于 xyP xQ yx P xy Q y 22 43 谓词逻辑中的推理 证明 xyP xQ yx P xy Q y 1 2 1 3 x P xP P aES xyP xQ y 附加前提 4 3 5 4 6 2 P yP aQ yUS P aQ bUS Q bT 5 7 6 8 Q y 1 7 y Q yUG x P xyCP 23 43 例7 例7 对多个量词的使用情况 观察下列推理过程对多个量词的使用情况 观察下列推理过程 证明 证明 1 前提 前提 yxyPx 2 1 US yzyP 3 2 ES dzP 4 3 UG dxxP 5 4 EG yxxPy 推出错误结论 与 可交换推出错误结论 与 可交换 y x 注意 公式注意 公式 2 中中z有两种可能有两种可能 1 若若z是自由个体变元 则此时是自由个体变元 则此时y的值是随的值是随z的变化而变 化的 因此不能用 的变化而变 化的 因此不能用ES规则将规则将y改为个体常元改为个体常元d 2 若若z是个体常元 则公式是个体常元 则公式 3 没错 但此时不能用没错 但此时不能用UG规 则得到 规 则得到 4 dxxP 错 错 错 错 24 43 谓词逻辑求解实际问题 步骤 根据问题的需要定义一组谓词 将实际问题符号化 使用推理规则有效推理 注意 符号化的原则 全称量词对应逻辑联结词 存在量词对应逻辑联结词 推理时首先引入带存在量词的前提 以保证 ES 规则的有效性 25 43 谓词逻辑求解实际问题 例8 证明苏格拉底的三段论 所有的人都是要死的 苏格拉底是人 所以苏格拉底是要死的 解 M x x是人 D x x是要死的 c 苏格拉底 苏格拉底三段论可以表示成 证明 1 M c P 2 P 3 M c D c US 2 4 D c T 1 3 x M x D x M c D c x M x D x 26 43 谓词逻辑求解实际问题 例9 所有的自然数都是整数 任何整数不是奇数 就是偶数 并非每个自然数都是偶数 所以 某 些自然数是奇数 解 第一步 定义谓词 N x x是自然数 I x x是整数 Q x x是奇数 O x x是偶数 第二步 问题符号化 x N xI x x I xQ xO x x N xO x x N xQ x 27 43 谓词逻辑求解实际问题 第三步 证明 x N xI xx I xQ xO x x N xO xx N xQ x 1 2 1 3 N a 2 4 x N xO xP xN xO xT O aES N a 3 4 3 5 6 N T O aT x N xI xP a I a 5 7 I a 4 6 US T 28 43 谓词逻辑求解实际问题 8 9 8 10 7 9 11 x I xQ xO xP I aQ aO aUS Q aO aT Q a 4 10 12 4 11 13 12 T N aO aT x N xQ xEG 接上页 29 43 谓词逻辑求解实际问题 例10 每个报考研究生的大学毕业生要么参加研究生 入学考试 要么推荐为免考生 每个报考研究生的 大学毕业生当且仅当学习成绩优秀才被推荐为免试 生 有些报考研究生的大学毕业生学习成绩优秀 但并非所有报考研究生的大学毕业生学习成绩都优 秀 因此 有些报考研究生的大学毕业生要参加研 究生入学考试 解 定义谓词如下 YJS x x是要报考研究生的大学毕业生 MKS x x是免考生 CJYX x x是成绩优秀的 CJKS x x是参加考试的 30 43 谓词逻辑求解实际问题 第二步 符号化问题 x YJS xCJKS xMKS x x YJS xMKS xCJYX x x YJS xCJYX x x YJS xCJYX x x YJS xCJKS x 31 43 谓词逻辑求解实际问题 第三步 证明 1 2 1 a 3 x YJS xCJYX xP xYJS xCJYX xT YJSCJYX a 2 a 43 5 3 6 ES YJST CJYX aT a a 76 847 9 x YJS xCJKS xMKS xP YJSCJaMKS aUS CJKSMKS aT KS xYJS xMKS xCJYX xP 32 43 谓词逻辑求解实际问题 10 9 11410 12 YJS aMKS aCJYX aUS MKS aCJYX aT MKS a 511 13812 144 13 1 5 KS T CJaT YJS aCJKS aT 1 4 x YJS xCJKS xEG 接上页 33 43 谓词逻辑求解实际问题 例11 所有的蜂鸟都五彩斑斓 没有大鸟以蜜为 生 不以蜜为生的鸟都色彩单调 因此 蜂鸟都是 小鸟 解 定义谓词如下 P x x是只蜂鸟 Q x x是大鸟 R x x是以蜜为生的鸟 S x x五彩斑斓 x P xS xx Q xR x xR xS xx P xQ x 34 43 谓词逻辑求解实际问题 x P xS xx Q xR x xR xS xx P xQ x 证明 1 2 1 3 4 3 5 4 6 7 6 8 7 9 8 10 2 5 11 x P xS xP P xS xUS xR xS xP R xS xUS S xR xT x Q xR xP xQ xR xT Q xR xUS R xQ xT P xR xT P x 10 9 12 11 Q xT x P xQ xUG 35 43 随堂练习 练习 符号化下列命题 并利用推理规则论 证结论 所有牛都有角 有些动物是牛 所以有些动 物有角 36 43 2 3谓词公式的范式 命题逻辑中的两种范式都可以直接推广到 谓词逻辑中来 只要把原子命题公式换成 原子谓词公式即可 根据量词在公式中出现的情况不同 又可 分为前束范式前束范式和斯柯林范式斯柯林范式 37 43 前束范式 定义 对任一谓词公式F 如果其中所有 量词均非否定的出现在公式的最前面 且 它们的辖域为整个公式 则称公式F为前前 束范式束范式 xyz P x yQ x yR x y z 38 43 前束范式 任意一个公式都可以转化成与之等价的前 束范式 方法如下 消去公式中的联结词 和 例如 将公式内的否定符号深入到谓词变元前并化 简到谓词变元前只有一个否定号 利用改名 代入规则使所有的约束变元均不 同名 且使自由变元与约束变元亦不同名 扩充量词的辖域至整个公式 ABABAB ABAB 39 43 前束范式 例 将下列公式转化成前束范式 解 x P xy R yx F x x P xy R yx F x