重庆大学谓词逻辑.ppt

表示具体的或特定的个体的词称为个体常项或个体常元 一般用小写英文字母a b c ai bi ci表示 第2章谓词逻辑 2 1谓词逻辑基本概念 1个体 个体变项的取值范围称为个体域或论域 个体域可以是有限事物的集合 如D 1 2 3 等 也可以是无限事物的集合 如自然数集合N等 当未指定个体域时 将宇宙间一切事物组成的客体集合作为个体域 称为全总个体域 定义2 1 个体是指可以独立存在的客观实体 表示抽象的或泛指的个体的词称为个体变项或个体变元 常用小写英文字母x y z xi yi zi表示 2 1谓词逻辑基本概念 例 对于下面3个简单命题 1 2是偶数 2 小王和小李是好朋友 3 小刘坐在小张和小赵的中间 其个体可以表示为 a 2 b 小王c 小李 d 小刘e 小张f 小赵 2 1谓词逻辑基本概念 2谓词 如上面三个命题可以表示为 F a 2是偶数 G b c 小王和小李是好朋友 H d e f 小刘坐在小张和小赵的中间 定义2 2 刻画个体具有的性质或个体之间的关系的词叫谓词 表示具体性质或关系的谓词称为谓词常项或谓词常元 表示抽象的或泛指的谓词称为谓词变项或谓词变元 谓词常项和谓词变项都用大写英文字母如F G H Fi Gi Hi等表示 因此 要根据上下文来确定表示的是谓词常项还是变项 2 1谓词逻辑基本概念 谓词中包含的个体数称为元数 含n n 1 个个体的谓词称为n元谓词 一元谓词常表示所含个体的性质 n n 2 元谓词常表示所含个体的之间的关系 一般 n元谓词表示以个体变项的个体域为定义域 以 0 1 为值域的n元函数 并且n个个体变项的顺序不能随意改动 若一个谓词中不含个体变项称这个谓词为0元谓词 如F a G b c H d e f 它们都是0元谓词 但不是命题 当给F G H赋以确切的意义 它们才是命题 可见 命题逻辑中的任何简单命题都能用0元谓词表示 并且命题逻辑中的所有联结词在谓词逻辑中都能应用 所以 命题只是谓词的特殊情况 任意命题都能在谓词逻辑中符号化 1 全称量词 自然语言中常用的 所有 都 任何一个 一切 凡 统称为全称量词 用符号 表示 x表示个体域中的所有个体 xF x 表示个体域中的所有个体都具有性质F 2 1谓词逻辑基本概念 例 用0元谓词符号化下列命题 林平不仅喜欢唱歌 而且喜欢跳舞 解 F x x喜欢唱歌 G x x喜欢跳舞 a 林平 命题符号化为 F a G a 3量词 定义2 3 量词 2 存在量词 自然语言中常用的 存在 有一些 至少有一个 有一个 统称为存在量词 用符号 表示 x表示个体域中存在个体 xF x 表示个体域中存在个体具有性质F 2 1谓词逻辑基本概念 在谓词逻辑中进行命题的符号化 首先应明确个体变项的取值范围即个体域 如符号化下列命题 1 所有的人都是要死的 2 有的人精神永存 对于上面两个命题指定个体域D为人类集合 则分别符号化为 1 xF x 其中F x x是要死的 2 xG x 其中G x x精神永存 若不指定个体域 则指的是全总个体域 此时上面两个命题确切叙述为 1 对于所有的个体 如果它是人 则它是要死的 2 存在一些个体 它是人并且精神永存 2 1谓词逻辑基本概念 1 x M x F x 2 x M x G x 引入用于限定个体域的词 M x x是人 称谓词逻辑中这种限定个体域的词为特性谓词 上面两个命题确切符号化为 若D a1 a2 an 则对于任意的谓词F x 都有 1 xF x F a1 F a2 F an 2 xF x F a1 F a2 F an 2 1谓词逻辑基本概念 4命题符号化 在谓词逻辑中将命题符号化 即明确个体域后 分别找出个体常项 个体变项 量词 谓词 按照原命题的意思用适当的联结词将它们组合 此外 1 引入特性谓词时 全称量词和存在量词的符号化形式不同 2 多个量词同时出现时 它们的顺序不能随意颠倒 例 符号化命题 存在x 使x 2 0 个体域分别为 1 自然数集合 2 整数集合 3 实数集合 解 不用引入特性谓 在上述3个个体域中 均符号化为 xF x 其中F x x 2 0 但在个体域为 1 时 为假命题 为 2 3 时 为真命题 2 1谓词逻辑基本概念 例 将下列命题符号化 有的自然数是偶数 个体域分别为 1 自然数集合 2 实数集合 3 全总个体域 解 1 不用引入特性谓词符号化为 xF x 其中 F x x是偶数 2 引入特性谓词M x x是自然数符号化为 x M x F x 其中 F x x是偶数 3 引入特性谓词M x x是自然数符号化为 x M x F x 其中 F x x是偶数 在上面3个个体域中 均为真命题 2 符号化为 x M x F x 其中M x x是大学生 F x x能成才 本命题还可叙述为 存在一些大学生不能成才 符号化为 x M x F x 2 1谓词逻辑基本概念 例 将下列命题符号化 1 没有人不爱看电视 2 并非所有的大学生都能成才 解 本题未指定个体域 所以取全总个体域为个体域 1 符号化为 x M x F x 其中M x x是人 F x x爱看电视 本命题还可叙述为 所有的人都爱看电视 符号化为 x M x F x 2 符号化为 x y M x M y H x y z M z L x y z 其中M x x是实数 H x y x y L x y z x z y 2 1谓词逻辑基本概念 例 多元谓词的符号化 1 所有对顶角都相等 2 任何两个实数之间都存在无穷多个实数 解 1 符号化为 x y M x M y H x y L x y 其中M x x是角 H x y x和y互为对顶角 L x y x y 命题的符号化是没有止境的 只做到能明确表明命题的意思 满足后面对推理有效性讨论要求就可以了 说明 作业5 A本 P51 3 2 2谓词公式及其解释 1谓词公式 同命题逻辑中的命题公式类似 谓词公式是由一系列个体常项符号 个体变项符号 函数符号 谓词符号 量词符号 联结词符号等组成 定义2 4项的构成如下 1 个体常项和个体变项是项 2 若f x1 x2 xn 是n元函数 t1 t2 tn是项 则f t1 t2 tn 也是项 3 仅当有限次地应用 1 2 生成的符号串是项 2 2谓词公式及其解释 定义2 5设P x1 x2 xn 是任意的n元谓词 t1 t2 tn是项 则称P t1 t2 tn 为原子谓词公式 简称原子公式 定义2 6谓词公式 谓词公式的最外层括号可以省略 并将谓词公式简称为公式 2 2谓词公式及其解释 2约束变项和自由变项 定义2 7在谓词公式 xA和 xA中 x称为指导变项 A称为相应量词的辖域 辖域中x的所有出现称为约束出现 x称为约束变项 A中不是约束出现的其它变项的出现称为自由出现 自由出现的变项称为自由变项 例 对于 x F x yP x y yP x y 中 y为指导变项 量词 的辖域为P x y 其中 y是约束出现的 x是自由出现的 整个公式中 x为指导变项 量词 的辖域为 F x yP x y x y都是约束出现的 其中 x约束出现2次 y约束出现1次 因此 在一个公式中 有的个体变项既是约束出现的 又是自由出现的 如上面 中的x 为避免混淆 常采用下面规则 2 2谓词公式及其解释 定义2 8设A是任一公式 若A中无自由出现的个体变项 则称A为封闭的公式 简称闭式 1 约束变项换名规则将量词辖域中出现的某个约束变项及其对应的指导变项 改成公式中未曾出现过的个体变项符号 公式中其余部分不变 2 自由变项代替规则将公式中某自由变项用原公式中未曾出现过的某个个体变项符号代替 且处处代替 如 x F x M x 是闭式 而 xF x yG x y 不是闭式 定义2 9为使公式成为真值确定的命题而指定的有关规定 叫做谓词公式的一个解释I 一个解释I由下面4部分组成 2 2谓词公式及其解释 如 对于xF x yG x y 利用换名规将x改成z得 zF z yG x y 利用代替规用z代替x得 xF x yG z y 1 特定的个体域D 2 D中一部分特定元素 3 D上每个函数变项所取的具体函数 4 D上每个谓词变项所取的具体谓词 3谓词公式的解释 2 2谓词公式及其解释 例给定解释I如下 1 D1 2 3 2 D1中特定元素a 3 3 函数f x 为f 2 2 f 3 3 4 谓词F x 为F 2 1 F 3 0 G x y 为G i j 0 i j 2 3H x y 为H 2 3 H 3 2 1 H 2 2 H 3 3 0判断在解释I下 下列公式的真值 1 xyH x y 2 x F x G x a 3 x F f x G x f x 2 2谓词公式及其解释 解 1 原式 H 2 2 H 2 3 H 3 2 H 3 3 0 1 1 0 1 1 1 2 原式 F 2 G 2 3 F 3 G 3 3 1 0 0 0 0 3 原式 F f 2 G 2 f 2 F f 3 G 3 f 3 F 2 G 2 2 F 3 G 3 3 1 0 0 0 0 定义2 10设A为一谓词公式 1 若A在任何解释下都为真 则称A为逻辑有效式 永真式 2 若A在任何解释下都为假 则称A为矛盾式 永假式 3 若至少存在一个解释使A为真 则称A为可满足式 2 2谓词公式及其解释 4谓词公式的分类 定义2 11设A0是含命题变项p1 p2 pn的命题公式 A1 A2 An是n个谓词公式 用Ai i 1 2 n 代换A0中每一处pi所得公式A称为A0的代换实例 如 F x G x 是p q的代换实例 xF x xG x H x 是p q r的代换实例 解 此公式是p p q 的代换实例 在命题逻辑中它为重言式 因此原公式为逻辑有效式 此公式是 p q q的代换实例 在命题逻辑中它为矛盾式 因此原公式也为矛盾式 2 2谓词公式及其解释 定理2 1命题公式中的重言式的代换实例在谓词公式中为逻辑有效式 命题公式中的矛盾式的代换实例在谓词公式中仍为矛盾式 例 判断下列公式的类型 xF x xF x yG y L x y P x y P x y 2 3谓词逻辑等值式 定义2 12设谓词逻辑中任意两个公式A B 若A B为逻辑有效式 则称A与B为等值式 记作A B 说明 由于命题逻辑中重言式的代换实例在谓词逻辑中都是逻辑有效式 因此1 3中给出的24个等值式的代换实例都是谓词逻辑中的等值式 另外 对某公式运用2 2节中给出的换名规则与代替规则后 所得公式与原来的公式等值 下面给出谓词逻辑中其它一些重要的等值式 1量词否定等值式 设A x 为任意的谓词公式 则有 1 xA x x A x 2 xA x x A x 2 3谓词逻辑等值式 2量词辖域收缩与扩张等值式 设A x 是含自由变项x的公式 B是不含变项X的公式 则 1 x A x B xA x B x A x B xA x B x A x B xA x B x A x B xA x B 2 x A x B xA x B x A x B xA x B x B A x B xA x x B A x B xA x 2 3谓词逻辑等值式 3量词分配等值式 设A x 和B x 是含自由变项x的任意公式 则有 1 x A x B x xA x xB x 2 x A x B x xA x xB x 称 1 为对 的分配 2 为对 的分配 4量词交换等值式 设A x y 是任意的含x y自由出现的谓词公式 有 1 xyA x y yxA x y 2 xyA x y yxA x y 作业6 B本 P52 11 2 4前束范式 定义2 13如果一个谓词公式A具有如下形式Q1x1Q2x2 QkxkB其中 Qi i 1 2 k 为量词或 B为不含量词的谓词公式 则称A为前束范式 如xy F x G y L x y 是前束范式 而x F x y G y L x y 不是前束范式 即一个前束范式就是量词全在公式的开头 而量词的整个辖域延伸到整个公式的末尾的句子 定理任意谓词公式都有一个与之逻辑等值的前束范式 求一个给定公式的前束范式 就是利用各种等值式及等值规则进行等值演算 把所有量词都变换到公式的开头 2 4前束范式 例求公式xF x xG x 的前束范式 解方法 xF x xG x xF x xG x x F x xG x x F x G x 方法 xF x xG x xF x yG y x F x yG y xy F x G y 可见 对一个公式运用不同规则进行变换 可得到不同的前束范式 其缺点是形式不唯一 2 4前束范式 例求公式 xF x yG x y 的前束范式 约束变项换名规则 xF x yG x y zF z yG x y z F z yG x y z y F z G x y 自由变项代替规则 xF x yG x y xF x yG z y x F x yG z y x y F x G z y 解分别采用约束变项换名规则和自由变项代替规则 前束范式中的各指导变项应各不相同 原公式中的自由变项在前束范式中还应是自由变项 说明 2 5谓词逻辑的推理理论 定理2 14设谓词逻辑中任意两个公式A B 若A B为逻辑有效式 则称A蕴涵B 记作A B 前面介绍的命题逻辑中的重言蕴涵式 这些蕴涵式在谓词逻辑中的代入实例都是有效蕴涵式 另外 由等值式与蕴涵式的关系可知 每一个等值式均可当作两个有效蕴涵式使用 关于量词分配的几个常用蕴涵式 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 xA x xB x x A x B x 2 5谓词逻辑的推理理论 定理2 15对于谓词公式A1 A2 An B 若有A1 A2 An B则称B为A1 A2 An逻辑结论或有效结论 也称B可由一组前提A1 A2 An逻辑推出 记为A1 A2 An B 谓词逻辑中的推理是命题逻辑中推理的推广 1UI 全称量词消去规则 两种形式 xA x A y xA x A c 其中 A是谓词 中y为任意不在A x 中约束出现的个体变元 中c为个体域中的任意一个个体常元 2 5谓词逻辑的推理理论 2UG 全称量词引入规则 A y xA x 其中 y为个体域中任意一个个体 且y取任何值时A均为真 x不在A y 中约束出现 3EI 存在量词消去规则 xA x A c 其中 c为个体域