离散数学第五版第二章ppt课件

离散数学 著名的 苏格拉底三段论 凡是人都是要死的 苏格拉底是人 所以苏格拉底是要死的 如何判定该推理是否是正确的 前提p 凡是人都是要死的 q 苏格拉底是人 结论r 苏格拉底是要死的 推理无效 一阶逻辑的研究内容 将简单命题再细分 分析出个体词 谓词和量词 从而达到表达出个体与总体的内在联系和数量关系 这就是一阶逻辑所研究的内容 一阶逻辑又称为一阶谓词或谓词逻辑 第二章一阶逻辑基本概念 2 1一阶逻辑的基本概念2 2一阶逻辑合式公式及解释2 3一阶逻辑等值式2 4一阶逻辑推理理论 2 1一阶逻辑的基本概念 1 个体词是指所研究对象中可以独立存在的具体或抽象的客体 个体词 例如 张明 中国 精神 计算机 2 个体常项是指表示具体或者特定的客体的个体词称作个体常项 通常用a b c 表示 例如 6大于5 2 1一阶逻辑的基本概念 例如 x大于y 3 个体变项是指表示抽象或者泛指的客体的个体词称作个体常项 通常用x y z 表示 4 个体域是指个体变项的取值范围为个体域 或称论域 个体域可以是有穷集合 也可以是无穷集合 例如 1 2 3 4 a b c d e 自然数集合N 0 1 2 3 实数集合R x x是实数 宇宙间一切事物的集合 全总个体域 2 1一阶逻辑的基本概念 谓词 1 谓词是用来刻画个体词性质及个体之间相互关系的词 当与一个个体相关时 它刻画了个体的性质 当与两个或两个以上个体相关时 则刻画了个体之间的关系 是无理数x是有理数 小王与小李同岁 x与y具有关系L 2 1一阶逻辑的基本概念 例如 x大于y 2 谓词常项是指表示具体性质或关系的谓词称为谓词常项 通常用F G H 表示 3 谓词变项是表示抽象的或泛指的性质或关系的谓词称为谓词变项 常用F G H 表示 注 n元谓词并不是命题 4 n元谓词P x1 x2 xn 表示含有n n 0 个命题变项 当n 1时 P x1 表示x1具有性质P 当n 1时 表示x1 x2 xn具有关系P 2 1一阶逻辑的基本概念 注 命题可以表示成0元谓词 命题是特殊的谓词 5 0元谓词表示不含有个体变项的谓词 例如 F a G a b 例1 将下列命题在一阶逻辑中用0元谓词符号化 并讨论它们的真值 只有2是素数 4才是素数 如果5大于4 则4大于6 如果张明比李民高 李民比赵亮高 则张明比赵亮高 2 1一阶逻辑的基本概念 量词 1 量词是表示个体常项或变项之间数量关系的词 2 全称量词是表示日常用语中 一切的 所有的 每一个 任意的 凡是 都 等词 可符号化为 并用 x y等表示个体域中的所有个体 用 xF x yG y 表示个体域中的所有个体都有性质F和都有性质G 3 存在量词是表示日常用语中 存在 有一个 有的 至少有一个 等词 可符号化为 并用 x y表示个体域中有的个体 用 xF x yG y 表示个体域中有的个体有性质F和有的有性质G 2 1一阶逻辑的基本概念 例2 在个体域分别限制 a 和 b 条件时 将下面两个命题符号化 凡人都呼吸 有的人用左手写字 其中 a 个体域D1为人类集合 b 个体域D2为全总个体域 a 令F x x呼吸 G x x用左手写字 1 xF x 2 xG x b 令F x x呼吸 G x x用左手写字 M x x是人 1 x M x F x 2 x M x G x 同一命题 在不同的域中命题符号化的形式也不同 2 1一阶逻辑的基本概念 例3 在个体域分别限制 a 和 b 条件时 将下面两个命题符号化 对于任意的x 均有x x 3x 2 x 1 x 2 存在x 使得x 5 3 其中 a 个体域D1 N N为自然数集合 b 个体域D2 R R为实数集合 a 令F x x x 3x 2 x 1 x 2 G x x 5 3 1 xF x 真命题2 xG x 假命题 b 令F x x x 3x 2 x 1 x 2 G x x 5 3 1 xF x 真命题2 xG x 真命题 同一命题 在不同域中的真值可能不同 2 1一阶逻辑的基本概念 例4 将下列命题符号化 并讨论真值 凡是偶数均能被2整除 存在着偶素数 4 说明 本书中 讨论命题符号化时 若没有指明个体域 就采用全总个体域 没有不犯错误的人 在北京工作的人未必都是北京人 一切人都不一样高 每个自然数都有后继数 2 1一阶逻辑的基本概念 分析命题中表示性质和关系的谓词 分别符号化为一元和n n 2 元谓词 根据命题的实际意义选用全称量词或存在量词 5 注意 一般来说 多个量词出现时 它们的顺序不能随意调换 有些命题的符号化形式不仅一种 在引入特性谓词后 使用全称量词与存在量词符号化的形式是不同的 个体域为有限集D a1 a2 an 则 xA x A a1 A a2 A an xA x A a1 A a2 A an 2 1一阶逻辑的基本概念 例5 将下列命题符号化 并讨论真值 一切人都不一样高 每个自然数都有后继数 有的自然数无先驱数 第二章一阶逻辑基本概念 2 1一阶逻辑的基本概念2 2一阶逻辑合式公式及解释2 3一阶逻辑等值式2 4一阶逻辑推理理论 2 2一阶逻辑合式公式及解释 一阶语言的字母表 定义2 1 一 一阶语言 1 个体常项 a b c 2 个体变项 x y z 3 函数符号 f g h 5 量词符号 6 连接词符号 4 谓词符号 F G H 7 括号与逗号 2 2一阶逻辑合式公式及解释 一阶语言的项 定义2 2 1 个体常项和个体变项是项 2 若 x1 x2 xn 是任意的n元函数 t1 t2 tn是任意的n个项 则 t1 t2 tn 是项 3 所有的项都是有限次使用 1 2 得到的 例如 a b x y f x y x y g x y x y h x y x y f a g x y a x y g h x y f a b x y a b 2 2一阶逻辑合式公式及解释 一阶语言的原子公式 定义2 3 设R x1 x2 xn 是任意的n元谓词 t1 t2 tn是一阶语言的任意n个项 则称R t1 t2 tn 是一阶语言的原子公式 例如 F x G y H x y L x y 2 2一阶逻辑合式公式及解释 一阶语言的合式公式 定义2 4 1 原子公式是合式公式 2 若A是合式公式 则 A 是合式公式 3 若A B是合式公式 则 A B A B A B A B 也是合式公式 4 若A是合式公式 则 xA xA也是合式公式 5 只有有限次地使用 1 4 构成的符号串才是合式公式 2 2一阶逻辑合式公式及解释 指导变元 辖域 约束出现 自由出现 定义2 5 二 与合式公式相关的概念 在公式 xA和 xA中 称x为指导变元 A为相应量词的辖域 在 x和 x的辖域中 x的所有出现均为约束出现 A中不是约束出现的其它变项均称为自由出现 2 2一阶逻辑合式公式及解释 例1 指出下列各公式中的指导变项 量词的辖域 个体变项的自由出现和约束出现 x F x yH x y xF x G x y x y R x y L y z xH x y x F x y G x z x F x G y y H x L x y z 2 2一阶逻辑合式公式及解释 封闭的公式 定义2 6 设A是任意的公式 若A中不含自由出现的个体变项 则称A为封闭的公式 简称闭式 例如 x F x G x x y F x G x y 闭式 x F x G x y x yL x y z 不是闭式 换名规则将量词辖域中出现的某个约束出现的个体变项及对应的指导变项 该成另一个辖域中未曾出现过的个体变项符号 公式中其余部分不变 代替规则对某个自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替 且处处代替 2 2一阶逻辑合式公式及解释 定义2 7 三 解释 a 非空个体域DI 封闭公式在任何解释下都变成命题 的解释I由下面4部分组成 b DI中一些特定元素的集合 c DI上特定函数集合 d DI上特定谓词集合 2 2一阶逻辑合式公式及解释 F f x a y F g x y z F g x y g y z F f x y g x y xF g x a x F x y xF g x a x x y zF f x y z x y F f x a y F f y a x xF f x x g x x xF g x y z 2 2一阶逻辑合式公式及解释 说明 2 在解释的公式A中的个体变项均取值于DI 6 被解释的公式不一定全部包含解释中的四个部分 1 在解释的定义中引进了几个元语言符号 如 3 若A中含个体常项 就解释成 4 为第i个n元函数 5 为第i个n元谓词 2 2一阶逻辑合式公式及解释 定义2 8 三 公式的类型 设A为一公式 若A在任何解释下均为真 则称A为永真式 或称逻辑有效式 若A在任何解释下均为假 则称A为矛盾式 或永假式 若至少存在一个解释使A为真 则称A是可满足式 如何判断公式的类型 在一阶逻辑中 由于公式的复杂性和解释的多样性 到目前为止 没有找到一种可行的方法来判断公式的类型 2 2一阶逻辑合式公式及解释 代换实例 定义2 9 设A0是含命题变项p1 p2 pn的命题公式 A1 A2 An是n个谓词公式 用Ai 1 I n 处处代替A0中的pi 所得公式A称为A0的代换实例 例如 F x G x xF x yG y 都是p q的代换实例 而 x F x G x 不是p q的代换实例 重言式的代换实例都是永真式 矛盾式的代换实例都是矛盾式 2 2一阶逻辑合式公式及解释 例3 判断下列公式哪些是永真式 哪些是矛盾式 x F x G x xF x x yG x y xF x x F x G x xF x xF x yG y xF x yG y yG y 可以根据命题公式重言式的代换实例来判断公式的类型 2 2一阶逻辑合式公式及解释 例4 判断下列公式的类型 xF x xF x x yF x y x yF x y x F x G x yG y 通过构造一些特殊的解释 来判断公式的类型 第二章一阶逻辑基本概念 2 1一阶逻辑的基本概念2 2一阶逻辑合式公式及解释2 3一阶逻辑等值式2 4一阶逻辑推理理论 2 3一阶逻辑等值式 将下面命题符号化 没有不犯错误的人 1 x F x G x 2 x F x G x 在一阶逻辑中 有些命题可以有不同的符号化形式 2 3一阶逻辑等值式 等值式 定义2 10 一 一阶逻辑等值式 设A B是一阶逻辑中任意两个公式 若A B是永真式 则称A与B是等值的 记作A B 成A B是等值式 一阶逻辑中的几个基本的等值式 1 命题逻辑中16组等值式 例如 xF x xF x F x G x F x G x 2 3一阶逻辑等值式 2 一阶逻辑中的4组特殊的等值式 消去量词等值式 设个体域为有限集D a1 a2 an 则有 xA x A a1 A a2 A an xA x A a1 A a2 A an 量词否定等值式 设A x 为任意的含自由出现个体变项x的公式 则 xA x x A x xA x x A x 2 3一阶逻辑等值式 量词辖域收缩与扩张等值式 设A x 为任意的含自由出现个体变项x的公式 B中不含x的出现 则 x A x B xA x B x A x B xA x B x A x B xA x B x B A x B xA x x A x B xA x B x A x B xA x B x A x B xA x B x B A x B xA x 2 3一阶逻辑等值式 量词分配等值式 设A x B x 为任意的含自由出现个体变项x的公式 则 x A x B x xA x xB x x A x B x xA x xB x 2 3一阶逻辑等值式 置换规则 二 一阶逻辑置换规则 设 A 是含公式A的公式 B 是公式B取代 A 中的所有的A之后的公式 若A B 则 A B 换名规则 设A为一公式 将A中某量词辖域中某约束变项的所有出现及相应的指导变元 改成该量词辖域中未曾出现过的某个变项符号 公式中其余部分不变 所得公式A 则A A 2 3一阶逻辑等值式 代替规则 设A为一公式 将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替 A中其余部分不变 所得公式为A 则A A 2 3一阶逻辑等值式 例1 将下列公式化成与之等值的公式 使其没有既是约束出现的又是自由出现的个体变项 x F x y yG x y z x y R x y L y z xH x y xF x y z yG x y z x F x G y y H x L x y z 利用置换规则 换名规则 代替规则消除既是约束出现又是自由出现的个体变元 2 3一阶逻辑等值式 例2 证明 x A x B x xA x xB x x A x B x xA x xB x 利用构造解释的方法来证明两个谓词公式不等值 2 3一阶逻辑等值式 例3 设个体域为D a b c 将下面各公式中的量词消去 x F x yG y x F x G x 首先 将量词的辖域缩小 然后 层层脱去量词 全称量词用所有个体属性或关系的合取表示 存在量词用所有个体属性或关系的析取表示 x yF x y 2 3一阶逻辑等值式 例4 给定解释I如下 D中的特定元素a 2 个体域D 2 3 D上的特定函数f x 为 f 2 3 f 3 2 D上的特定谓词G x y 为 G 2 2 G 2 3 G 3 2 1 G 3 3 0 L x y 为 L 2 2 L 3 3 L 3 2 0 F x 为 F 2 0 F 3 1 在I下求下列各式的真值 x F x G x a x F f x G x f x x yL x y y xL x y 量词的顺序不能随意调换 2 3一阶逻辑等值式 例5 证明下列各等值式 x M x F x x M x F x x F x G x x F x G x x y F x G y H x y x y F x G x H x y x y F x G y L x y x y F x G x L x y 利用一阶逻辑等值演算公式以及命题逻辑等值演算公式来证明两个公式是否等值 2 3一阶逻辑等值式 设A为一个一阶逻辑公式 若A具有如下形式Q1x1Q2x2 QkxkB则称A为前束范式 其中Qi 1 i k 为 或 B为不含量词的公式 例如 x y F x G y H x y x y z F x G y H z L x y z x F x y G y H x y x F x y G y H x y 三 前束范式定义 定义2 11 2 3一阶逻辑等值式 例6 求下列公式的前束范式 xF x xG x xF x xG x xF x xG x xF x xG x 注意 1 由于 对 适合分配律 所以1 式才有只带一个量词的前束范式 而 对 不适合分配律 因此2 式不能有带一个量词的前束范式 xF x y yG y xH x y 2 使用 x A x B xA x B x A x B xA x B时 必须注意条件 3 公式的前束范式不唯一 第二章一阶逻辑基本概念 2 1一阶逻辑的基本概念2 2一阶逻辑合式公式及解释2 3一阶逻辑等值式2 4一阶逻辑推理理论 2 4一阶逻辑推理理论 一阶逻辑的推理正确性 一 一阶逻辑推理理论 在一阶逻辑中 从前题A1 A2 Ak出发推结论B的推理的形式结构 若A1 A2 Ak B为永真式 则称推理正确 一阶逻辑的推理定律 1 命题逻辑推理定律的代入实例 例如 xF x yG y xF x xF x xF x yG y 2 4一阶逻辑推理理论 2 基本等值式生成的推理定律 例如 xF x xF x xF x xF x xF x F x F x xF x 3 几个重要的推理定律 例如 xA x xB x x A x B x x A x B x xA x xB x x A x B x xA x xB x x A x B x xA x xB x 2 4一阶逻辑推理理论 一阶逻辑的推理规则 两式成