51一阶逻辑等值式与置换规则.ppt

第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理第第1节节 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则 第第2节节 一阶逻辑的前束范式一阶逻辑的前束范式 第第3节节 一阶逻辑推理理论一阶逻辑推理理论 第第1 1节节 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则 一、一、基本等值式基本等值式 二、二、基本规则基本规则 三、三、等值演算等值演算  谓词逻辑中关于联结词的等值式与命题逻辑中谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似相关等值式类似. .下面主要讨论关于量词的等值式下面主要讨论关于量词的等值式. . 定义定义5.1 设设 A，，B 是一阶逻辑中任意两个公式，是一阶逻辑中任意两个公式，若若A↔B是永真式，则称是永真式，则称 A 与与 B 是是等值的等值的.记做记做 A B，称，称 A B 是是等值式等值式. 一、一、基本等值式基本等值式 第一组第一组 代换实例代换实例 由于命题逻辑中的重言式的代换实例都是一由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的阶逻辑中的永真式，因而第二章的16组等值式给组等值式给出的代换实例都是一阶逻辑的等值式的模式出的代换实例都是一阶逻辑的等值式的模式.例如：例如： 等都是等都是 的代换实例的代换实例.又如：又如：等都是等都是 的代换实例的代换实例.  第二组第二组 消去量词等值式消去量词等值式 (1) (2)    设设个体域个体域为为有限域有限域               ，， 则则有有(5.1)第三组第三组 量词否定等值式量词否定等值式 (1) (2)    设设        是任意的含有自由出现个体变项是任意的含有自由出现个体变项 x 的公式，则的公式，则(5.2) 第四组第四组 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 (1) 设设 是任意的含自由出现个体变项是任意的含自由出现个体变项 x 的公式，的公式，B中不含中不含 x 的出现，则的出现，则 (5.3)(2)  注意注意 这些等值式的条件这些等值式的条件. . (5.4) 第五组第五组 量词分配等值式量词分配等值式 (1) (2) 设设                 是任意的含自由出现个体变项是任意的含自由出现个体变项 x 的的公式，则公式，则(5.5) 二、基本规则二、基本规则 1．置换规则．置换规则  设设Φ(A)是含公式是含公式A 的公式，的公式，Φ(B)是用公式是用公式 B 取代取代Φ(A)中所有的中所有的A 之后的公式，之后的公式，若若A B，，则则Φ(A) Φ(B). 一阶逻辑中的置换规则与命题逻辑中的置换规则一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同形式上完全相同, 只是在这里只是在这里 A, B是一阶逻辑公式是一阶逻辑公式.   设设A为一公式，将为一公式，将A中某量词辖域中某约束变项中某量词辖域中某约束变项的的所有出现及相应的指导变元改成该量词辖域中所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分未曾出现过的某个体变项符号，公式的其余部分不变，不变，    2 2．换名规则．换名规则．换名规则．换名规则 设所得公式为设所得公式为A'，则，则3 3．代替规则．代替规则．代替规则．代替规则 A中其余部分不变，设所得公式为中其余部分不变，设所得公式为A'，则，则设设A为一公式，将为一公式，将A中某个中某个自由出现的个体变项的自由出现的个体变项的所有出现所有出现用用A中未曾中未曾出现过的个体变项符号代替，出现过的个体变项符号代替，三、等值演算三、等值演算 例例5.1 将下面公式化成与之等值的公式，使其将下面公式化成与之等值的公式，使其没有既是约束出现又是自由出现的个体变项没有既是约束出现又是自由出现的个体变项.(1) (2) (换名规则换名规则) (换名规则换名规则)       原公式中，原公式中，x，，y 都是既约束出现又有自由出现的个都是既约束出现又有自由出现的个体变项，只有体变项，只有 z 仅自由出现。

而在最后得到的公式中，仅自由出现而在最后得到的公式中，x，，y，，z，，t，，w 中再无既是约束出现又有自由出现个体中再无既是约束出现又有自由出现个体变项了变项了.还可以如下演算，也可以达到要求还可以如下演算，也可以达到要求. 解解 (1) (代替规则代替规则) (代替规则代替规则) (2)  (代替规则代替规则) 或者或者  (换名规换名规则则) 例例5.2 证明证明(1) (2) 其中其中                  为含为含 x 自由出现的公式自由出现的公式 证证:  (1) 只要证明在某个解释下两边只要证明在某个解释下两边的式子不等值的式子不等值.则则 为真命题，而为真命题，而为假命题为假命题.对于对于(2)可以类似证明可以类似证明.  奇数，代替奇数，代替         ；取；取         ：：x是偶数，代替是偶数，代替取取解释解释I：：个体个体域域为自然数集合为自然数集合N；取；取         ：：x是是故两边不等值故两边不等值.例例5.2说明，全称量词说明，全称量词“ "对对"∨∨"无分配律无分配律. 同样的，存在量词同样的，存在量词" " " "对对"∧""∧"无分配律无分配律. . 这是式这是式(5.3)和式和式(5.4)中出现的两个等值式中出现的两个等值式. 但当但当         换成换成没有没有x出现的出现的B时时，则有，则有(1) (2) (3) 例例5.3 设设个体域个体域为为 ，将下面各公式，将下面各公式 的的量词量词消去：消去： 解解 (1) (2)  (公式公式5.3)  如果不用公式如果不用公式(5.3)将量将量词的的辖域域缩小，演算小，演算过程程较长.注意注意注意注意 此时此时 是与是与 x 无关的公式无关的公式 B. (3)   在演算中先消去存在量词也可以，得到结果是在演算中先消去存在量词也可以，得到结果是等值的等值的. 例例 5.4 给定解释如下给定解释如下:(1) 个体域个体域 . (2) 中的特定元素中的特定元素 . . (3) 上的特定函数上的特定函数: , . : , . (4) 上的特定谓词上的特定谓词 分别为分别为: : 特定谓词特定谓词          为为:在下求下列各式的的真值在下求下列各式的的真值:(1)(2)(3)(4)例例5.5 证明下列各等值式证明下列各等值式(1)(2)(3)(4)作业：作业： P852. (1) (4)5. (3)。