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

* * 第五章 一阶逻辑等值演算与推理 第1节 一阶逻辑等值式与置换规则 第2节 一阶逻辑的前束范式 第3节 一阶逻辑推理理论 第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．换名规则 设所得公式为A，则 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时，则有