离散数学 第五讲.pdf

2006 3 16电子工程学院 离散数学1 2 2 2 2 2 2 2 2 一阶逻辑谓词公式及解释一阶逻辑谓词公式及解释一阶逻辑谓词公式及解释一阶逻辑谓词公式及解释 简单命题函数简单命题函数 逻辑联结词 谓词表达式逻辑联结词 谓词表达式 问题 怎样的谓词表达式 才能成为谓词公式 并能 进行逻辑演算 问题 怎样的谓词表达式 才能成为谓词公式 并能 进行逻辑演算 2006 3 16电子工程学院 离散数学2 定义定义2 4 在形式化中 我们将使用如下在形式化中 我们将使用如下7种符号 种符号 1 个体常项 用小写英文字母个体常项 用小写英文字母a b c 表示 当个 体域 表示 当个 体域D给出时 它可以是给出时 它可以是D中某个元素 中某个元素 2 个体变项 用小写英文字母个体变项 用小写英文字母x y z 表示 当个 体域 表示 当个 体域D给出时 给出时 D中任意元素可代入个体变项 中任意元素可代入个体变项 3 函数符号 用小写英文字母函数符号 用小写英文字母f g 表示 当个体 域 表示 当个体 域D给出时 给出时 n元函数符号元函数符号f x1 xn 可以是可以是Dn到到D的 任意一个映射 的 任意一个映射 4 谓词符号 用大写英文字母谓词符号 用大写英文字母F G H 表示 当 个体域 表示 当 个体域D给出时 给出时 n元谓词符号元谓词符号F x1 xn 可以是可以是Dn 上的任意一个谓词 上的任意一个谓词 2 2 1 2 2 1 2 2 1 2 2 1 合式公式与翻译合式公式与翻译合式公式与翻译合式公式与翻译 2006 3 16电子工程学院 离散数学3 5 量词符号 量词符号 6 联结词符号 联结词符号 7 括号和逗号 括号和逗号 定义定义2 5 谓词逻辑中的项 被递归定义为 谓词逻辑中的项 被递归定义为 1 个体常项是项 个体常项是项 2 个体变项是项 个体变项是项 3 若 若 x1 xn 是是n元函数 元函数 t1 tn是项 则 是项 则 t1 tn 也是项 也是项 4 所有项都是有限次使用所有项都是有限次使用1 2 3 生成的符号串才是 生成的符号串才是 项项 2 2 1 2 2 1 2 2 1 2 2 1 合式公式与翻译合式公式与翻译合式公式与翻译合式公式与翻译 2006 3 16电子工程学院 离散数学4 1 有了项的定义 函数的概念就可用来表示个体常项和 个体变项 有了项的定义 函数的概念就可用来表示个体常项和 个体变项 如 如 P x x是教授 是教授 f x x的父亲 的父亲 a 张三 那么 张三 那么P f a 则表示 则表示 张三的父亲是教授张三的父亲是教授 2 函数的使用给谓词表示带来很大的方便 函数的使用给谓词表示带来很大的方便 如 用谓词 表示命题 对任意的整数 如 用谓词 表示命题 对任意的整数x x2 1 x 1 x 1 是恒等 式 令 是恒等 式 令 I x x是整数 是整数 f x x2 1 g x x 1 x 1 E x y x y 则该命题可表示为 则该命题可表示为 x I x E f x g x 2 2 1 2 2 1 2 2 1 2 2 1 合式公式与翻译合式公式与翻译合式公式与翻译合式公式与翻译 说明说明说明说明 2006 3 16电子工程学院 离散数学5 定义定义2 6 若若R x1 xn 是是n元谓词符号 元谓词符号 t1 tn是项 则 是项 则R t1 tn 是是原子 谓词 公式原子 谓词 公式 定义定义2 7 谓词演算的合式公式 被递归定义如下 谓词演算的合式公式 被递归定义如下 1 原子公式是合式公式 原子公式是合式公式 2 若若A B是公式 则是公式 则 A A B A B A B A B 也是合式公式 也是合式公式 3 若若A是公式 是公式 x是是A中的自由变项 则 中的自由变项 则 xA xA也 是合式公式 也 是合式公式 4 只有有限次地使用只有有限次地使用1 3构成的符号串才也是构成的符号串才也是合式 公式 合式 公式 2 2 1 2 2 1 2 2 1 2 2 1 合式公式与翻译合式公式与翻译合式公式与翻译合式公式与翻译 2006 3 16电子工程学院 离散数学6 例 例 x P x Q x x y P x y R y 是 合式公式 但 是 合式公式 但 x P x R x x y P x y 不是合式公式 说明 不是合式公式 说明 1 合式公式是按定义中规则由原子公式 联结词 量 词 圆括号和逗号所组成的符号串 命题公式是合式 公式的特例 合式公式是按定义中规则由原子公式 联结词 量 词 圆括号和逗号所组成的符号串 命题公式是合式 公式的特例 2 合式公式最外层的括号可以省略 规则与命题公 式中括号省略的规则相同 但量词后面的括号是不 能省略的 如 合式公式最外层的括号可以省略 规则与命题公 式中括号省略的规则相同 但量词后面的括号是不 能省略的 如 x M x R x 2 2 1 2 2 1 2 2 1 2 2 1 合式公式与翻译合式公式与翻译合式公式与翻译合式公式与翻译 2006 3 16电子工程学院 离散数学7 例例2 3 这只大红书柜摆满了那些古书 解法 这只大红书柜摆满了那些古书 解法1 设设F x y x摆满了摆满了y R x x是大红书柜 是大红书柜 Q y y是古书 是古书 a 这只 这只 b 那些 那些 R a Q b F a b 解法解法2 设设F x y x摆满了摆满了y A x x是书柜 是书柜 B x x是大的 是大的 C x x是红的 是红的 D y y是古老的 是古老的 E y y是图书 是图书 a 这只 这只 b 那些 那些 A a B a C a D b E b F a b 结论 翻译的形式取决于个体刻画的深度 结论 翻译的形式取决于个体刻画的深度 2 2 1 2 2 1 2 2 1 2 2 1 合式公式与翻译合式公式与翻译合式公式与翻译合式公式与翻译 2006 3 16电子工程学院 离散数学8 例例2 4 高等数学里的极限定义为 任给的充分小的 正数 存在一个正数 使得当 高等数学里的极限定义为 任给的充分小的 正数 存在一个正数 使得当 2 2 1 2 2 1 2 2 1 2 2 1 合式公式与翻译合式公式与翻译合式公式与翻译合式公式与翻译 0lim lim 0 0 0 xa xa xaf xbf xb P x yxyQ x yxy f xb PP Q xaP xax Qf xb 时有 即为 解 大于 小于 则 可翻译为 2006 3 16电子工程学院 离散数学9 2 2 2 约束变项与自由变项 定义 约束变项与自由变项 定义2 8 在合式公式 在合式公式 xA或 或 xA 中 称中 称x为为指导变项指导变项 称称A为相应量词的为相应量词的辖域辖域或或作用域作用域 在辖域中 在辖域中 x的所 有出现称为 的所 有出现称为约束出现约束出现 称 称x为为约束变项约束变项 A中不是约 束出现的其它个体变项的出现称为 中不是约 束出现的其它个体变项的出现称为自由出现自由出现 这些个 体变项称为 这些个 体变项称为自由变项自由变项 约束变项和自由变项统称为 约束变项和自由变项统称为指导变项指导变项 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学10 例例2 5 指出下列公式各合式公式中的指导变项 量词 的辖域 个体变项的自由出现和约束出现 指出下列公式各合式公式中的指导变项 量词 的辖域 个体变项的自由出现和约束出现 x F x G y y H x L x y z 解 公式中含解 公式中含2个量词 前件中的量词的指导变项 约束变项 个量词 前件中的量词的指导变项 约束变项 x 的辖域为 的辖域为 F x G y 其中 其中x是 约束出现的 是 约束出现的 y是自由出现的 后件中的量词的指导 变项 约束变项 是自由出现的 后件中的量词的指导 变项 约束变项 y 的辖域为 的辖域为 H x L x y z 其中 其中y是约束出现的 是约束出现的 x与与z均是自由出现的 因此 在 整个公式中 均是自由出现的 因此 在 整个公式中 x自由出现自由出现1次 约束出现次 约束出现1次 次 y自由出 现 自由出 现1次 约束出现次 约束出现1次 次 z只自由出现只自由出现1次 次 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学11 说明 为了方便 我们常用 说明 为了方便 我们常用A x 表示表示x是自由出现的任 意的公式 如 是自由出现的任 意的公式 如 A x 可为可为F x G y 一旦在 一旦在A x 前 面加上 前 面加上 x 或 或 x 即变成 即变成 x A x 或 或 x A x x就成为 约束出现的个体变项了 反之 若将 就成为 约束出现的个体变项了 反之 若将 x A x 或 或 x A x 中的 中的 x 或 或 x去掉量词 所得去掉量词 所得A x 中的中的x就成为了 自由出现的变项了 就成为了 自由出现的变项了 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学12 定义定义2 9 设设A为任意一个公式 若为任意一个公式 若A中无自由出现的个 体变项 则称 中无自由出现的个 体变项 则称A为为封闭的公式封闭的公式 简称 简称闭式闭式 由闭式的定义 闭式中的所有个体变项均为约束 出现 如 由闭式的定义 闭式中的所有个体变项均为约束 出现 如 x F x G x 和和 x y F x G x y 是闭式 但是闭式 但 x F x G x y 和和 x F x G x y 不是闭式 不是闭式 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学13 在给定的公式中 同一个个体变项既可以约束出 现 又可以自由出现 因此为了避免混淆 我们采用 如下两个规则 在给定的公式中 同一个个体变项既可以约束出 现 又可以自由出现 因此为了避免混淆 我们采用 如下两个规则 1 换名规则换名规则 将量词辖域中某个约束出现的个体变项 及相应的指导变项 改成本公式中其它辖域中未曾出 现过的个体变项 公式中其余部分不变 如 将 将量词辖域中某个约束出现的个体变项 及相应的指导变项 改成本公式中其它辖域中未曾出 现过的个体变项 公式中其余部分不变 如 将 x F x G x y H x y 中的约束变 项 中的约束变 项x换为换为z 得 得 z F z G z y H x y 注意 注意 H x y 中的中的x是自由出现的 不能更换 因此 是自由出现的 不能更换 因此 z F z G z y H z y 为错误换名 为错误换名 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学14 2 代替规则代替规则 对某个自由出现的个体变项用与原公式 中未曾出现过的个体变项去代替 且处处代替 如 将 对某个自由出现的个体变项用与原公式 中未曾出现过的个体变项去代替 且处处代替 如 将 x F x G x y H x y 中的自由变 项 中的自由变 项y用用z代替 代替为代替 代替为 x F x G x z H x z 注意 注意 x F x G x y 中中x是约束出现的 是约束出现的 y是 自由出现 所以 不能代替为 是 自由出现 所以 不能代替为 y F y G y y H x y 为错误代替 为错误代替 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学15 2 2 3 公式的解释 谓词公式的赋值 定义 公式的解释 谓词公式的赋值 定义2 10 一个一个解释解释I由下面由下面4部分组成 部分组成 1 非空个体域非空个体域D 2 D中一些特定的元素 中一些特定的元素 3 D中一些特定的函数 中一些特定的函数 4 D中一些特定的谓词 被解释的公式不一定全部包含以上 中一些特定的谓词 被解释的公式不一定全部包含以上4部分 部分 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学16 1 x F x G x a 解 给出如下的解释解 给出如下的解释I 1 非空个体域非空个体域D 2 3 2 D中特定的元素中特定的元素a 2 3 函数函数f x 为 为 f 2 3 f 3 2 4 谓词谓词F x 为 为 F 2 0 F 3 1 G x y 为 为 G i j 1 i j 2 3 A F 2 G 2 2 F 3 G 3 2 0 1 1 0 0 结论 在解释结论 在解释I下 下 x F x G x a 为假 为假 例例例例2 62 62 62 6 给出如下两个公式 给出如下两个公式 给出如下两个公式 给出如下两个公式 2006 3 16电子工程学院 离散数学17 2 x F f x G x f x 解 给出如下的解释解 给出如下的解释I 1 非空个体域非空个体域D 2 3 2 D中特定的元素中特定的元素a 2 3 函数函数f x 为 为 f 2 3 f 3 2 4 谓词谓词F x 为 为 F 2 0 F 3 1 G x y 为 为 G i j 1 i j 2 3 B F f 2 G 2 f 2 F f 3 G 3 f 3 F 3 G 2 3 F 2 G 3 2 1 1 0 1 1 结论 在解释结论 在解释I下 下 x F f x G x f x 为真 为真 例例例例2 62 62 62 6 给出如下两个公式 给出如下两个公式 给出如下两个公式 给出如下两个公式 2006 3 16电子工程学院 离散数学18 定义定义2 11 设设A为一个公式 如果为一个公式 如果A在任何解释下都为 真 则 在任何解释下都为 真 则A为为永真式永真式 如果 如果A在任何解释下都为假 则在任何解释下都为假 则A 为为永假式永假式 如果 如果A在至少存在一个解释为真 则在至少存在一个解释为真 则A为为 可满足式可满足式 由于公式的复杂性和解释的多样性 目前还没有 一种可行的方法判断某一公式是否是可满足的 但对 某些特殊的公式还是可以判断的 由于公式的复杂性和解释的多样性 目前还没有 一种可行的方法判断某一公式是否是可满足的 但对 某些特殊的公式还是可以判断的 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学19 定义定义2 12 设设A为含命题变项为含命题变项p1 p2 pn是的命题公式 是的命题公式 A1 A2 An是是n个合式公式 用个合式公式 用Ai是处处代替是处处代替pi 所得到 的公式 所得到 的公式B称为称为A的的代换实例代换实例 如 如 F x G x x F x yG y 等都是等都是p q的 代换实例 但 的 代换实例 但 x F x G x 不是不是p q的代换实例 的代换实例 定理定理 永真式的代换实例仍为永真式 永假式的代换实 例仍为永假式 永真式的代换实例仍为永真式 永假式的代换实 例仍为永假式 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学20 例例2 7 判断下列公式那些是永真式 那些是永假式 判断下列公式那些是永真式 那些是永假式 1 x F x G x 解 为了书写方便 用解 为了书写方便 用A表示以上公式 解 表示以上公式 解 解释 解释 个体域 个体域D为实数集 为实数集 F x x是整数 是整数 G x x是有理数 显然是有理数 显然A为真 因此为真 因此A不是永假式 不是永假式 解释 解释 个体域 个体域D仍为实数集 仍为实数集 F x x是正整数 是正整数 G x x是负整数 显然此时是负整数 显然此时A为假 因此为假 因此A不是永真 式 综上所述 不是永真 式 综上所述 A为非永真式的为非永真式的可满足式可满足式 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学21 2 x F x G x 解释 个体域解释 个体域D为实数集 为实数集 F x x是整数 是整数 G x x是自然数 显然是自然数 显然B为真 因此为真 因此B不是永假式 解释 个体域 不是永假式 解释 个体域D为实数集 为实数集 F x x是非负整 数 是非负整 数 G x x是负整数 显然是负整数 显然B为假 因此为假 因此B不是永 真式 同 不是永 真式 同1 B为非永真式的为非永真式的可满足式可满足式 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学22 3 x F x x y G x y x F x 显然 上式是显然 上式是p q p 的代换实例 它为永真 式 所以 的代换实例 它为永真 式 所以C为永真式为永真式 4 x F x y G y y G y 显然 上式是 显然 上式是 p q q 的代换实例 它为永 假式 所以 的代换实例 它为永 假式 所以D为永假式为永假式 结论 有些公式即使是某些永真式或永假式的代 换实例 也不容易识别 因此只有一些简单的公式才 能判断其类型 结论 有些公式即使是某些永真式或永假式的代 换实例 也不容易识别 因此只有一些简单的公式才 能判断其类型 2 2 2 2 2 2 2 2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释一阶逻辑合式公式及解释 2006 3 16电子工程学院 离散数学23 2 3 2 3 2 3 2 3 一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式 2 3 1 谓词 公式等值的概念 例 谓词 公式等值的概念 例2 8 将命题 将命题 没有不犯错误的人没有不犯错误的人 符号化 解 设 符号化 解 设D为全总个体域 为全总个体域 F x x是人 是人 G x x犯错 误 犯错 误 x F x G x 没有不犯错误的人 或 没有不犯错误的人 或 x F x G x 只要是人 就一定会犯错误 显然 以上两种符号化形式等值 只要是人 就一定会犯错误 显然 以上两种符号化形式等值 定义定义2 1 设设A B是一阶逻辑中任意的两个公式 若是一阶逻辑中任意的两个公式 若A B是永真式 则称是永真式 则称A与与B等值 记为等值 记为A B 称 称A为为B的的 等值式等值式 2006 3 16电子工程学院 离散数学24 2 3 2 基本而重要的等值式 定理 基本而重要的等值式 定理2 1 命题逻辑中的永真式的代换实例均为一阶逻 辑中的永真式 命题逻辑中的永真式的代换实例均为一阶逻 辑中的永真式 置换规则置换规则 24个基本等值式的代换实例是一阶逻辑的永真 式的模式 如 个基本等值式的代换实例是一阶逻辑的永真 式的模式 如 x F x x F x x F x G x x F x G x 2 3 2 3 2 3 2 3 一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式 2006 3 16电子工程学院 离散数学25 定理定理2 2 量词否定等值式 量词否定等值式 1 x A x x A x 2 x A x x A x 证明 不妨设证明 不妨设D a b 1 x A x A a A b A a A b x A x 2 x A x A a A b A a A b x A x 2 3 2 3 2 3 2 3 一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式 2006 3 16电子工程学院 离散数学26 定理定理2 3 量词辖域收缩与扩张的等值式 量词辖域收缩与扩张的等值式 1 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 B A x B xA x 证明 证明 x A x B x A x B x A x B x A x B x A x B x B A x x B A x B x A x B xA x 2 3 2 3 2 3 2 3 一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式 2006 3 16电子工程学院 离散数学27 定理定理2 3 量词辖域收缩与扩张的等值式 量词辖域收缩与扩张的等值式 2 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 B A x B x A x 证明 证明 x A x B x A x B x A x B x A x B x A x B x B A x x B A x B x A x B x A x 2 3 2 3 2 3 2 3 一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式 2006 3 16电子工程学院 离散数学28 定理定理2 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 证明 不妨设证明 不妨设D a b 1 x A x B x A a B a A b B b A a A b B a B b x A x x B x 2 3 2 3 2 3 2 3 一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式 2006 3 16电子工程学院 离散数学29 定理定理2 5 下列等值式成立 下列等值式成立 1 x y A x y y x A x y 2 x y A x y x A x y 证明 略证明 略 2 3 2 3 2 3 2 3 一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式 2006 3 16电子工程学院 离散数学30 1 x M x F x x M x F x 2 x F x G x x F x G x 证明 证明 1 x M x F x x M x F x 定理 定理2 2 2 x M x F x 置换规则 置换规则 x M x F x 置换规则 置换规则 2 x F x G x x F x G x 定理 定理2 2 1 x F x G x 置换规则 置换规则 x F x G x 置换规则 置换规则 例例例例2 9 2 9 证明下列各等值式 证明下列各等值式 证明下列各等值式 证明下列各等值式 2006 3 16电子工程学院 离散数学31 3 x y F x G y H x y x y F x G y H x y 证明 证明 x y F x G y H x y x y F x G y H x y 定理 定理2 2 1 x y F x G y H x y 定理 定理2 2 1 x y F x G y H x y 置换规则 置换规则 x y F x G y H x y 置换规则 置换规则 例例例例2 9 2 9 证明下列各等值式 证明下列各等值式 证明下列各等值式 证明下列各等值式 2006 3 16电子工程学院 离散数学32 4 x y F x G y L x y x y F x G y L x y 证明 证明 x y F x G y L x y x y F x G y L x y 定理 定理2 2 2 x y F x G y L x y 定理 定理2 2 2 x y F x G y L x y 置换规则 置换规则 x y F x G y L x y 置换规则 置换规则 例例例例2 9 2 9 证明下列各等值式 证明下列各等值式 证明下列各等值式 证明下列各等值式 2006 3 16电子工程学院 离散数学33 2 3 3 前束范式 定义 前束范式 定义2 1 设设A是一公式 若是一公式 若A具有形式具有形式Q1x1Q2x2 QkxkB 则称则称A为前束范式 其中为前束范式 其中Qi为 或 为 或 B为不含量词的公 式 如 为不含量词的公 式 如 x y F x G y H x y 是前束范式 但 是前束范式 但 x F x y G y 不是前束范式 不是前束范式 定理定理2 3 6 前束范式存在定理 前束范式存在定理 一阶逻辑中的任何谓词 公式都存在与之等值的前束范式 注意 虽然前束范式存在 但一般说来并不唯一 如例 一阶逻辑中的任何谓词 公式都存在与之等值的前束范式 注意 虽然前束范式存在 但一般说来并不唯一 如例2 8 没有不犯错误的人没有不犯错误的人 两个等值式均为前束范式 两个等值式均为前束范式 2 3 2 3 2 3 2 3 一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式 2006 3 16电子工程学院 离散数学34 例例2 9 将求下列各式的前束范式 将求下列各式的前束范式 1 x F x x G x 解 解 1 x F x x G x y F y x G x 换名规则 换名规则 y