第五章：非形式的谓词演算.ppt

第五章 非形式的谓词演算 荣立武hooeyrong 5非形式的谓词演算 我们首先来看下面一个论证 所有的人都是会死的 苏格拉底是人 苏格拉底是会死的 这个是一个直觉上有效的推理 但是 按照前面所讲的方法来分析 它的形式是 p q所以r 显然 从命题演算的角度来看这不是一个有效的推理 原因在哪里呢 这种情况下 推理的有效性不是依赖于作为简单命题的前提和结论之间的关系 而依赖于命题各个组成部分之间的关系 依赖于这些命题本身的形式 5非形式的谓词演算 一般来说 我们可以把它分析成以下形式 所有的A是B a是A 所以 a是A 在这个推理形式中 有几个值得我们注意的地方 谓词变元A B 个体变元a和量词 所有的 一般的简单命题都具有 主词 和 谓词 主词是命题要加以断定的事物 而谓词是指该事物具有的 属性 我们来分析下列命题 5非形式的谓词演算 在下列各命题中 主词是用红字标记的 余下的部分是谓词 a 苏格拉底是人 b 我写书 c 平方为 1的数不是实数 d 世界给人以生存 以后 我们用大写的英文字母A B C 表示谓词 用小写的英文字母a b c 表示主词 相应地 以上命题 a 可以表示为H s H表示 是人 s代表苏格拉底 命题 b 可以表示为B i B表示 写书 i代表我 命题 c 可以表示为 R j R表示 是实数 j代表平方为 1的数 命题 d 可以表示为L w L表示 给人以生存 i代表世界 5非形式的谓词演算 只要我们知道了简单命题如何按照这种形式翻译成符号语言 加上前面的知识 我们自然也就知道了复合命题如何翻译成这种符号语言 现在的问题是 对于 所有人都是会死的 这样的命题我们怎么办 这类命题的主词不是指称单个的对象 而是用量词 所有 赋予多个对象以某个性质 我们参考数学符号体系中的常用方法 例如 说 每个整数都有素因子 就被翻译成 对于所有的x来说 如果x是整数 那么x就有素因子 类似地 所有人都是会死的 也被翻译成 对于所有的x来说 如果x是人 那么x是会死的 5非形式的谓词演算 以后 为了记法上的方便 我们把这个命题记为 x Mx Dx 其中 1 谓词M D分别表示 是人 和 是会死的 2 是全称量词符号 表示所有的意思 3 x是个体变元 当它没有被量词约束时 它表示不确定的主体 这个时候我们一般也称之为自由变元 自由变元的论域是不确定的 4 单个的全称量词符号是不完整的 当它和自由变元结合成 x 这样的形式 我们就表示自由变元x被全称量词 约束了 在这里x就成为了约束变元 约束变元的论域是确定的 我们可以指定一个特定的论域 例如 全体自然数 当没有指定特定论域时 我们就把论域看成是全域 即万事万物 5非形式的谓词演算 5 但是 仅仅是 x 仍然不是完整的公式 它仅仅表示 所有的事物 或 所有的数 显然这样还不能完整地构成一个公式 从而表达一个全称命题 只有当它和谓词变元结合在一起才构成合式公式 例如 xMx 表示 所有的事物是人 或者限定x的论域是全体整数 我们用 xAx 表示 所有的整数都有素因子 其中 A 表示 有素因子 请大家注意 如果x是全域中的不确定个体的话 那么这句话 所有的整数都有素因子 就翻译成 x Ix Ax 其中 I 和 A 分别表示 是整数和 有素因子 5非形式的谓词演算 一般来说 还有一个量词在我们把自然语言翻译成谓词符号语言时也是需要的 例如 有些猪是有翅膀的 我们一般可以把它看成 至少存在有一个x使得x是一头猪并且x有翅膀 同样地 我们可以将这个命题翻译成 x Px Wx 其中 P 和 W 分别表示 是一头猪 和 有翅膀 一般来说 全称量词 普通名词 属性 翻译时我们使用蕴含联结词把前后两个谓词符号联结起来 存在量词 普通名词 属性 翻译时我们使用合取联结词把前后两个谓词符号联结起来 5非形式的谓词演算 请大家把以下自然语言翻译成谓词符号语言 1 所有的鸟都会飞 2 并非所有的鸟都会飞 3 所有的鸟都不会飞 4 并非所有的鸟都不会飞 5 至少有一只鸟会飞 6 并非至少有一只鸟会飞 7 至少有一只鸟不会飞 8 并非至少有一只鸟不会飞 9 有一个整数大于其他所有整数 10 所有的马都是动物 所以所有的马头都是动物头 1 8 论域是全域 B 鸟 F 会飞 1 x Bx Fx 2 x Bx Fx 3 x Bx Fx 4 x Bx Fx 5非形式的谓词演算 5 x Bx Fx 6 x Bx Fx 7 x Bx Fx 8 x Bx Fx 9 论域为全域 I 整数 LI x y x y x Ix y Iy LI x y 10 首先 我们把后面那句话等价地翻译为 对于所有的x而言 如果存在有一个y y是马并且x是y 马 的头 那么也存在有一个z z是动物并且x是z 动物 的头 论域为全域 H 马 A 动物 T x y x是y的头 x Hx Ax x y Hy T x y z Az T x z 5非形式的谓词演算 课后作业 请把 没有一个人尊重不自重的人 并且没有一个人信任他不尊重的人 所以 一个不受尊重的人是不受任何人信任的 翻译成谓词符号语言 其中 论域为全域 M 是人 R x y x尊重y 注 R x x 表示x自重 H x y x信任y 5非形式的谓词演算 现在我们来进一步考察 1 8 直觉上 我们是用 7 至少有一只鸟不会飞 来证实 2 并非所有的鸟会飞 即 x Bx Fx x Bx Fx 根据前面的知识 x Bx Fx x Bx Fx 2 2 4 12 等值置换 x Bx Fx 2 2 4 1 等值置换 x Bx Fx 2 2 4 6a 等值置换现在 我们比较 x Bx Fx 和 x Bx Fx 我们发现 后者与前者的区别仅在于 x 代替了 x 这样我们据明白一个道理 x 可以替换 x 另一方面 x 也可以替换 x 5非形式的谓词演算 因为直观上 1 并非所有的x都不具有属性P x Px 等价于 存在有某个x具有属性P xPx 2 并非存在有某个x不具有属性P x Px 等价于 所有的x都具有属性P xPx 于是 存在量词和全称量词只需要有一个 另一个可以借助否定联结词相应地定义出来 同样的道理 1 x Bx Fx 8 x Bx Fx 3 x Bx Fx 6 x Bx Fx 4 x Bx Fx 5 x Bx Fx 上面的证明 大家任意选做一个 写清楚理由 5非形式的谓词演算 课后作业 把下列各命题写成符号形式 先不用存在量词 然后不用全称量词 任意选择两个做 1 并非所有的汽车都是三只轮子 2 有些人或者是懒惰的 或者是愚蠢的 3 没有一只耗子比任何一只象重 4 每个数或者是负的或者有一平方根 要求 把论域和谓词符号所代表的含义写清楚 5 1一阶语言 一阶符号语言由下列7类符号构成 1 个体变元符号 x1 x2 xn 2 联结词符号 3 量词符号 4 技术符号 5 个体常元 a1 a2 an 6 函数符号 7 谓词符号 注1 以后我们用表示苏格拉底是人 其中个体常元表示苏格拉底 而一元谓词表示性质 是人 5 1一阶语言 注2 谓词符号的上标表明了谓词是几元谓词 如果是1就表示一个性质 如果是2就表示一个二元关系 如果是3就表示一个三元关系 如此类推 注 函数符号的上标和谓词符号的上标解释差不多 表示函数所带参数的个数 不过请大家区别函数符号和谓词符号 谓词符号可以看成这样一个函数 而函数符号则应看成 5 1一阶语言 一般地 所有的个体变元的集合记为Var 所有的个体常元集记为Con 由 5 7 中的符号构成的集合称为L的特征符号集 一般情况下 我们固定 1 4 而随着情况不同改变 5 7 给定了一个特征符号集也就给定了一个语言的初始符号集 我们在后面常常使用下列元语言符号 x y z表示个体变元 P Q R表示谓词符号 F G H表示函数符号 c d e表示个体常元 5 2一阶语言L中项和原子公式的定义 为了定义一阶语言L中的合式公式 我们首先必须定义L中的项 1 变元和个体常元是项 2 如果是L中的函数符号 且是L中的项 则也是L中的项 3 所有的项都是按照 1 和 2 生成的 项在形式语言中将被解释为对象 即函数作用于其上的事物 具有某种属性的事物 对之作出某种断定的事物 以后在元语言中 我们用t和u表示项 L中的原子公式定义为 如果是L中的一个谓词符号 是L中的项 则是L中的原子公式 5 2L中合式公式的定义 注 原子公式是语言中可断定的最简单的公式 例如 某些对象具有某种性质 这里 原子 一词当然是表示不能再分解了 L中的一个合式公式的定义如下 1 L中的每个原子公式是L中的合式公式 2 如果A和B是L中的合式公式 则 A A B xiA 其中xi是任意个体变元 也是合式公式 3 L中的所有合式公式都是按照 1 和 2 生成的 注1 xiA并不要求A中一定有个体变元xi的出现 5 2L中合式公式的定义 注2 我们规定 xiA是 xi A的缩写 A B是 A B 的缩写 A B是 A B的缩写 注3 我们要注意 xi A B 和 xiA B之间的区别 为此 我们需要再引入一些相关的定义 定义 在公式 xiA中 我们称A是量词的辖域 更一般地 当 xiA作为子公式出现在B中时 我们称这个量词在B中的辖域是A 定义 变元xi在一个公式中的出现称为约束的 如果它出现在公式中的 xi的辖域之内 或者xi在 xi中 如果一个变元的出现不是约束的 那么我们就称它是自由的 5 2辖域 约束变元和自由变元 例 请说明下列公式中量词的辖域 以及个体变元的每一次出现是约束的还是自由的 5 2辖域 约束变元和自由变元 当我们仅仅对公式中的变元感兴趣时 我们常常有这种写法 A x1 或B x1 xn 在这种情况中 我们一般指其中的变元是自由出现的 如果xi在A中确实是自由出现 那么对于任何项t A t 将指对xi的每次自由出现都代入t后所得到的结果 下面我们解释一个比较重要的概念 令A是L中的任意公式 我们称项t对A中的个体变元xi是自由的 如果xi并不自由地出现在A的一个 xj的辖域中 这里的xj是指出现在t中的任何变元 粗略地说 所谓项对个体变元的自由指的是 项可以代入A中的xi每个自由出现 而不引起和A中的量词相互作用 项对个体变元的代入 举例来说 1 x3对公式中的x2是自由的 而x1对公式中的x2则是不自由的 因为x2自由地出现在 x1的辖域中 而x2并没有自由地出现在 x3的辖域中 在这里有两个意思 或者x2没有出现在 x3的辖域中 或者x2出现在 x3的辖域中 但是x2的出现是不自由的 对于 1 中所举的例子来说 是因为x2没有出现在 x3的辖域中 2 也有可能出现x2约束地出现在 x3的辖域中的情况 例如x3对公式中的x2是自由的 因为在这个公式中没有x2的自由出现 项对个体变元的代入 由上不难看出 项t对公式A中的变元x是自由的 主要是看t对x在A中的自由出现进行代入是不是自由的 而对x的约束出现进行代入则没有太多的意义 就好像 2 中例子所看到的那样 课后作业 项对公式的替换定义 项对公式的替换定义 举例 课后作业 5 3解释 定义5 3 1 L的一个解释I是由以下几部分内容构成的 1 一个非空集DI I的论域 2 一个特别的元素集 a1 a2 3 一个在DI上的函数集 4 一个在DI上的关系集我们的意图是 L中的变元将会被解释为 对象 而集合DI将被解释为变元在其上取值的论域 特别的元素集将对应L中个体常元的取值 DI上的函数和关系将分别对应L中函数和关系的解释 注 以后为了方便 在不会引起混淆的情况下 我们不区分a1与 a1 5 3解释 一阶语言 如果一个语言的解释中 量词仅仅作用于将被解释为 对象 的个体变元之上 二阶语言 如果一个语言的解释中 量词不仅可以作用于将被解释为 对象 的个体变元之上 还可以作用于将被解释为对象关系的谓词变元之上 N阶语言 如果一个语言的解释中 量词可以作用于将被解释为N 1阶关系之间的关系之上 一阶符号语言系统又可称为一阶逻辑 二阶以上的符号语言系统统称为高阶逻辑 在本课程中 我们只讨论一阶逻辑 5 3解释 举例 1 用一阶语言表示有关自然数的算术命题 解释I 论域DI 0 1 2 特别元素只有一个0 它将被解释为个体常元a1所对应的对象 于是 在这样一个解释I下 公式 1 将被解释为 对于所有的自然数x y来说 并非对所有的自然数z 都有x y z 5 3解释 另一方面 我们知道上述公式逻辑等值于 这个公式将被解释为 对于所有的自然数x y来说 存在有一个自然数z 使得x y z 但是 我们要注意到一阶语言不能表达这样的算术命题 每个非空的自然数集都有一个最小数 显然在描述这个命题是 我们不得不将全称量词作用于自然数集 这样的表述将成为二阶语言中的一个公式 只有当一个语言被给定一个解释之后 我们才能对有关公式的意义说些什么 也就是说 只有在 5 3解释 一个解释下 才能考察这个公式的真假 上述公式 1 在解释I下显然是假的 但是 我们可以给这个公式另一种解释I 使得它为真 在解释I 下DI 是正有理数 这样 公式 1 将会被解释为 对任意的有理数x y来说 存在有有理数z使得xy z 显然这个命题是真的 5 3解释 课后作业 5 4满足和真 正如命题逻辑系统PC中的讨论一样 只有对命题公式中的命题变元指派真值 命题公式才会有真假 在谓词逻辑中 一阶公式只有在一个具体的解释下才有真假 在这里 解释相当于命题逻辑系统中所介绍的赋值 指派 令I是以DI为论域的语言L上的一个解释 定义5 4 1 I上的一个赋值是一个从L的项集到集DI具有下列性质的一个函数v 1 v ai ai 对于L中的每个个体常元ai 2 5 4满足和真 赋值是这样一个规则 它给语言L中的每一个项指派了DI中的一个对象作为它的解释 注记 1 在一个给定的解释下 将有多种不同的赋值 因为对于个体变元总有不同赋值的可能 2 一给定的赋值将对L中的每一个变元xi指派DI中的一个元素 因此 如果对L中个体变元的赋值被确定了 那么这个赋值也被确定下来了 这是因为个体常元和复杂项都在5 4 1 1 和 2 中被指派了DI中的一个元素 其中 2 是对复杂项的指派的归纳定义 下面我们介绍一个后面经常会用到的定义 i 等值 称两个赋值v和v 是i 等值 如果v xj v xj 对每个i j 即 两个赋值只有在xi上可能不同 也可能相同 一般情况下是不同的 5 4满足和真 现在我们来考察在一个解释和赋值之下 一阶公式的满足 定义5 4 2 令A是L的一个公式 I是L的一个解释 I中的一个赋值v称为满足A 记为vI A 1 在不混淆的情况下记为v A 1 如果 1 如果A是原子公式 2 如果A是 B 这样的形式 那么v A 1当且仅当v B 1 这也就是说 v不满足B 当且仅当v就满足 B 3 如果A是 B C 这样的形式 那么v B C 1 当且仅当 或者v B 1或者v C 1 即或者v不满足B或者v满足C 5 4满足和真 4 解释I中的一个赋值v满足当且仅当 每个i 等值于v的赋值v 满足B 注 我们有必要对 4 做出一些解释 首先 我们说I中的赋值v满足一个公式是这个意思 对于任意DI中的对象d I中的赋值v都会满足公式 其中对象d 是个体常元d在I下的解释 但是 怎么表示DI中的任意对象d 这就得要引入前面的与vi 等值的赋值v 了 由于v和v 的唯一区别是在xi的赋值上有不同 因此引入v 的意图就在于可以给xi赋值不同的DI中的对象 而其他 5 4满足和真 的情况则保持不变 如果在任意的与vi 等值的赋值v 下 公式都有 其中个体常元c替换个体变元xi表示在赋值v 下xi将被解释为论域中的对象c 当然我们也可以选择a b e 替换xi 这正是其他与vi 等值的赋值所干的事情 假如所有的与vi 等值的赋值都有使得 d 表示某个个体常元 则我们前面所说的意思已经充分地表达出来了 5 4满足和真 例 1 算术解释N 论域DI 0 1 2 个体常元a1被解释为0 在解释N的一个赋值v下 v x1 2 v x1 6 v x1 3 v x1 4 显然 赋值下v满足公式 1 因为2 6 3 4 5 4满足和真 例2 在解释N中被解释为 对任意的自然数n nm mn 这显然是一个真命题 现在我们面对的一个问题是 公式 2 是可以从公式 1 中可推导出来的 或者说 公式 1 是否逻辑蕴涵公式 2 呢 分析步骤1 令v是N中的任意一个赋值 显然v x1 和v x2 是自然数 因此公式 1 被解释为v x1 v x2 v x2 v x1 而这显然是真的 分析步骤2 对任意与v1 等值的赋值v 来说 v 无非是要改变v对于x1的赋值 但是 无论如何 5 4满足和真 v x1 仍然是一个自然数 因此v x1 v x2 v x2 v x1 仍然是真的 这意味着对任意与v1 等值的赋值v 都有成立 所以根据定义5 4 2 4 我们有结论 赋值v在解释N下满足公式 2 再由于赋值v的任意性 解释N下所有的赋值都满足公式 2 同理可证 在解释N下的所有赋值都满足这个公式 5 4满足和真 例3 在解释N下是什么意思 请大家思考解释N下是否有赋值v是否满足公式 不难发现 以后用另外的项或者变元去替代一个变元是经常用到的技巧 因此 以下定理是必须的 5 4有穷指派引理 1命题逻辑中的有穷指派引理 令 p1 pn 是命题公式A中出现的所有命题变元所构成的集合 假如v和u分别是对A的任意两组真值指派 赋值函数 并且有v p1 u p1 v pn u pn 那么v A u A 证明思路 施归纳于公式A的结构易证 其中我们会用到赋值函数的定义 这个证明比较简单 请同学们作为课后作业完成 有穷指派引理旨在说明 一个赋值函数对于命题公式A的真值的影响仅仅在于它给A中出现的命题变元指派怎样的真值 而与A中不出现的命题变元被指派什么真值无关 5 4有穷指派引理 循着这样的思路 我们试图考察对一阶公式是不是也存在有类似的有穷指派引理呢 谓词逻辑中的有穷指派引理旨在表明 在一个确定的解释下 一个赋值函数v是否满足一阶公式A 仅仅取决于v给A中出现的自由变元的赋值是什么 而与A中不出现的自由变元或A中约束出现的自由变元无关 5 4有穷指派引理 定理5 4 3 令I是L的一个解释 A是L的一个公式 如果v和w都是赋值 并且对A中的每个自由变元xi 有v xi w xi 那么v满足A 当且仅当 w满足A 证明 对A中的联结词和量词的数目施归纳 基础步骤 A是一个原子公式 例如A t1 tn 赋值v和w对出现在A中的所有自由变元和个体常元赋值都是一样的 所以对任意项ti n i 1 有v ti w ti 为什么 请同学们在课后作业中证明 又因为v和w对谓词A的赋值是一样的 所以v满足A 当且仅当 w满足A 5 4有穷指派引理 归纳步骤 情形1 A是 B情形2 A是B C情形1 2易证 请同学们在课后作业中完成 情形3 A是 xiB假设v满足A 那么对于所有的与vi 等值的v 都满足B 现在 我们对赋值w 我们任意选择一个与wi 等值的赋值函数w 由于xi在 xiB中不自由出现 所以只要个体变元y在 xiB是自由的 就有w y v y 现在 我们对任意的w 相应地构造v 如下 5 4有穷指派引理 1 v xi w xi 在xi这一点上 2 v xj w xj j i 在xi这一点之外显然 对于B中出现的任意自由变元y 我们有w y v y 因为对 xiB中出现的自由变元 我们已经有w y v y v y 所以 对于公式B来说 最多无非多增加一个自由变元xi 但是根据v 的构造 1 显然我们就有了以上结论 进一步 根据前面的结论 v 都是满足B的 根据归纳假设 条件1B中出现的任意自由变元y 我们有w y v y 条件2B比 xiB结构简单 有w 也 满足B 再根据w 的任意性和满足的定义 我们有w满足 xiB 用类似方法可以证明 w满足 xiB v满足 xiB 5 4有穷指派引理 定理5 4 4 令A xi 是L中的一个公式 其中xi自由出现 并且令t是对A xi 中的x