离散数学—第二章一阶逻辑.ppt

一阶逻辑 理学院数学系仝辉 一阶逻辑的基本概念一阶逻辑合式公式及解释一阶逻辑等值式一阶逻辑推理理论 第二章一阶逻辑 苏格拉底三段论 判断下面推理的正确性凡人都是要死的 苏格拉底是人 所以苏格拉底是要死的 用p q r表示三个命题 则 p q r并不是重言式 原因缺少命题内在的联系的反映 个体词 谓词 简单的命题被分解成个体词与谓词 6是合数 王宏是程序员 小李比小赵高2厘米 个体词相关的基本概念 个体词 是可以独立存在的客体 个体常项 用小写的英文字母a b c d 个体变项 用小写的英文字母x y z 个体域 个体的取值范围 全总个体域 指宇宙中的一切事物 谓词相关的基本概念 谓词常项 表示具体性质或关系的谓词 用F G H表示 谓词变项 表示抽象的性质或关系的谓词 也用F G H表示 但要根据个体变项x y等来定 x具有属性F 则用F x 表示 x y具有关系L 则用L x y 表示 谓词中的个体词数称为元数 含n个个体词的谓词称为n元谓词 如 P x1 x2 x3 xn 通常 一元谓词是表示个体词的性质 n n 1 元谓词是表示个体词之间的关系 且各个体词顺序不能随意改动 如 L x y 代表x小于y 而L y x 代表y小于x 谓词和命题的关系 通常 n元谓词不是命题 因其真值无法确定 如 L x y 并没说明其谓词的意思 当其谓词已为常项 其还不是命题 如 L x y x小于y 其真值仍无法确定 只有当其谓词为常项 且n元个体词全为常量时 L a b 才是命题 如 a 2 b 3 其真值可唯一确定 通常 将不带个体变项的谓词叫0元谓词 此时其不一定是命题 只有当谓词为常项时 才是命题 命题逻辑中的联结词在一阶逻辑中均可使用 例题 2是素数且是偶数 F x x是素数 G x x是偶数 a 2符号化为F a G a 如果2大于3 则2大于4 L x y x大于y a 2 b 3 c 4符号化为L a b L a c 量词 量词 表示数量的词 全称量词 对应日常生活中用到的 一切 所有的 任意的 不存在一个 不 等词 用符号 表示 x表示个体域中的所有个体 xF x 表示个体域中的所有个体具有属性F 存在量词 对应日常生活中用到的 存在着 有一个 至少有一个 不是所有的 都不 等词 用符号 表示 x表示存在个体域中的个体 xF x 表示存在个体域中的个体具有属性F 明确个体域 考虑个体域D为人类集合凡人都要死的 xF x 其中F x x是要死的 有人活百岁以上 xG x 其中G x x活百岁以上 考虑个体域为全总个体域对于所有个体而言 如果它是人 则它是要死的 引入新谓词M x x是人 M x 称为特性谓词 x M x F x 存在着个体 它是人并且活百岁以上 x M x G x 用量词时的注意点 在不同的个体域中 命题符号化的形式可能不一样 如果事先没有给出个体域 都应以全总个体域为个体域 个体域和谓词的含义确定之后 n元谓词要转化为命题至少需要n个量词 此点以后再讨论 当个体域为有限集时 如果D a1 a2 an 由量词的意义可以看出 对于任意的谓词A x 都有 xA x A a1 A a2 A an xA x A a1 A a2 A an 多个量词同时出现时 不能随意颠倒他们的顺序 例题 对任意的x 存在着y 使得x y 5 H x y 表示x y 5可符号化成 x yH x y 不可符号化成 y xH x y P40 例题2 2 2 3 2 4 2 5 一阶逻辑的基本概念一阶逻辑合式公式及解释一阶逻辑等值式一阶逻辑推理理论 第二章一阶逻辑 一阶逻辑合式公式采用字母表 定义2 1字母表个体常项 a b c ai bi ci i 1 个体变项 x y z xi yi zi i 1 函数符号 f g h fi gi hi i 1 谓词符号 F G H Fi Gi Hi i 1 量词符号 联结词 括号和逗号 项的递归定义 定义2 2个体常项和变项是项 若 x1 x2 xn 是任意的n元函数 t1 t2 tn是项 则 t1 t2 tn 是项 只有有限次地使用 生成的符号串才是项 a b x y f x y x y h x y x y都是项 原子公式 合式公式 定义2 3 原子公式设R x1 x2 xn 是任意的n元谓词 t1 t2 tn是项 则称R t1 t2 tn 为原子公式 定义2 4 合式公式原子公式是合式公式 若A是合式公式 则 7A 是合式公式 若A B是合式公式 则 A B A B A B A B 也是合式公式 若A是合式公式 则 xA xA也是合式公式 只有有限次地应用 构成的符号串才是合式公式 指导变项 辖域 约束出现 自由出现 定义2 5在合式公式 xA和 xA中 称x为指导变项 称A为相应量词的辖域 在辖域中 x的所有出现称为约束出现 即x受相应量词指导变项的约束 A中不是约束出现的其他变项的出现称为自由出现 例题2 6 指出下列合式公式中指导变项 量词辖域 个体变项的约束出现 自由出现 x F x yH x y yH x y 中 y为指导变项 的辖域为H x y 其中y为约束出现 x为自由出现 整个公式 的辖域为 F x yH x y x y为约束出现 x约束两次 y约束一次 封闭的合式公式 定义2 6 设A为任一公式 若A中无自由出现的个体变项 则称A是封闭的合式公式 简称闭式 x F x G x x y F x G x y 是闭式 x F x G x y z yL x y z 不是闭式 xF x vG x 不是闭式 换名规则 换名规则 将量词辖域中出现的某个约束出现的个体变项及对应的指导变项 改成另一个辖域中未曾出现的个体变项符号 公式其余部分不变 如 在 xF x G x y 中 将约束出现的x改成z 得到的公式为 zF z G x y 代替规则 代替规则 对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替 且处处代替 如 在 xF x G x y 中 利用代替规则 将自由出现的x用z代替 得 xF x G z y 解释I 定义2 7一个解释I由下面4部分组成非空个体域D D中一部分特定元素 D上一些特定的函数 D上一些特定的谓词 在使用一个解释I解释一个公式A时 将A中的个体常项用I中特定常项代替 函数和谓词用I中的特定函数和谓词代替 如例题2 7 见下页 例题2 7 解释I如下 D1 2 3 D1中特定元素a 2 函数f x 为f 2 3 f 3 2 谓词F x 为F 2 0 F 3 1 G x y 为G i j 1 i j 2 3 L x y 为L 2 2 L 3 3 1 L 2 3 L 3 2 0在解释I下 求下列各式的真值 1 x F x G x a 2 x F f x G x f x 3 x yL x y 2 解 1 2 3 中公式分别为A B C 则A F 2 G 2 2 F 3 G 3 2 0 1 1 1 0B 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 1C L 2 2 L 2 3 L 3 2 L 3 3 1 1 1 例题2 8解释N 解释N个体域为自然数集合Dn Dn中特定元素a 0 Dn上特定函数f x y x y g x y x y Dn上特定谓词F x y 为x y 解 在解释N下 公式分别化为 x x 0 x 假命题 2 x y F f x 0 y F f y 0 x x y x 0 y y 0 x 真命题 3 x y y z真值不确定 不是命题 在解释N下 下面那些公式为真 那些公式为假 1 xF g x a x 2 x y F f x a y F f y a x 3 F f x y f y z 永真式 矛盾式 可满足式 设A为一公式 谓词公式 如果A在任何解释下都是真的 称A为逻辑有效式 或永真式 如果A在任何解释下都是假的 称A为矛盾式 或永假式 若至少存在一个解释使A为真 则称A是可满足式 协调式 代换实例 设A0是含命题变项p1 p2 pn的命题公式 A1 A2 An是n个谓词公式 用Ai 1 i n 处处代替pi 所得公式A称为A0的代换实例 F x G X xF x xG x 都是p q的代替实例 例题2 9 判断哪些是永真式 哪些是矛盾式 xF x xF x xF x x yG x y xF x 解设I为任意的解释 其个体域为D 若存在x0 D 使得F x0 为假 xF x 为假 所以 xF x xF x 为真 对于任意x D F x 为真 则 xF x xF x 同时为真 所以 xF x xF x 是永真式 p q p 的代替实例 由p pv7q 是重言式可知 xF x x yG x y xF x 一阶逻辑的基本概念一阶逻辑合式公式及解释一阶逻辑等值式一阶逻辑推理理论 第二章一阶逻辑 一阶逻辑等值式 定义2 10设A B是一阶逻辑中任意的两公式 若A B为逻辑有效式 则称A与B是等值的 记作A B 称A B为等值式 p p p代换实例 xA x xA x xA x p q p q xA x xB x xA x xB x 量词否定等值式 定理2 1量词否定等值式 xA x x A x xA x x A x 证明 设D a1 a2 an xA x A a1 A a2 A an A a1 A a2 A an x A x xA x A a1 A a2 A an A a1 A a2 A an x A x 量词否定等值式 量词否定等值式 xA x x A x xA x x A x 所有人都不是一样高A x x是人 H x y x与y不是同一个人 B x y x与y一样高 x y A x A y H x y 7B x y x7 y A x A y H x y B x y 量词辖域收缩与扩展等式 定理2 2量词辖域收缩与扩展等式 1 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 量词辖域收缩与扩展等式 量词辖域收缩与扩展等式 1 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 证明 设D a1 a2 an x A x B A a1 VB A a2 VB A an VB A a1 A a2 A an B xA x B x A x B x A x B x A x B xA x VB xA x B 量词辖域收缩与扩展等式 量词辖域收缩与扩展等式 2 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量词分配等值式 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 取F x G x 代替A x B x 只要证明 x F x G x xF x xG x 不是逻辑有效式 解释I D为自然数集合 F x x是奇数 G x x是偶数 x F x G x 为真 但 xF x xG x 是假 故 x F x G x xF x xG x 不是逻辑有效式 交换量词 等值式 定理2 4 x yA x y y xA x y x yA x y y xA x y 前束范式 设A为一谓词公式 如果A具有如下形式 Q1x1Q2x2 QKxKB则称A为前束范式 其中每个Qi 1 i k 为 或 B为不含量词的谓词公式 例如 x y F x y G x y x y z F x y z G x y t 在一阶逻辑中 任何合式公式A的前束范式都是存在的 并且前束范式不是唯一的 例题 1 求下列公式的前束范式 xF x xG x xF x x G x x F x G x xF x xG x xF x x G x xF x y G y 换名原则 x y F x G y 例题 2 xF x xG x xF x xG x x F x xG x x F x G x 一阶逻辑的基本概念一阶逻辑合式公式及解释一阶逻辑等值式一阶逻辑推理理论 第二章一阶逻辑 推理形式 推理的形式结构为A1 A2 AK B若该式是逻辑有效式 则称推理正确 B是A1 A2 AK的逻辑结论 此时将该式记为A1 A2 AK B一般将一阶逻辑的有效蕴涵式称为推理定律 命题逻辑中重言蕴涵式 可采用代入实例也是一阶逻辑的推理定律 每个等值式可产生两条推理定理 关于量词分配的推理定理 定理2 5 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 全称量词消去规则 UI xA x A y x在A x 中是自由出现的 y为任意不在A x 中约束出现的个体变项 反例 x yF x y yF y y 真命题假命题 xA x A c c为任意的个体常项 全称量词引入规则 UG规则 A y xA x y在A y 中自由出现 且y取任何值时A均为真 取代y的x不能在A y 中约束出现 否则也会产生错误 如 在实数集中取F x y 为x y A y xF x y 对任意的y都是成立的 若取x代替y x x x x 是假命题 存在量词引入规则 EG A c xA x c特定的个体常项 取代c的x不能是在A c 中出现过 在实数集中取F x y 为x y A 2 xF x 2 真命题 若取x代替2 x x x 是假命题 存在量词消去规则 EI规则 xA x A c c是A为真的特定的个体