阶逻辑等值演算与推理.ppt

第五章 一阶逻辑等值演算与推理 前一节课的复习 一阶逻辑命题符号化 （1）三要素之一：个体词 （2）三要素之二：谓词 (N元谓词符号化) 分析命题中表示性质和关系的谓词，分别符号化为一元和n元谓词； （3）三要素之三：量词 A) 根据命题的实际意义选用全称量词或存在量词； B) 注意量词的先后顺序。 （4） 全总个体域的约定 （5） 特性谓词的使用 （6） 联结词的使用 （7）命题的符号化形式不是唯一的 引言 一阶逻辑等值演算 一阶逻辑推理 5.1. 一阶逻辑等值式 与置换规则 定义5.1（一阶逻辑等值式的概念） 设A，B是一阶逻辑中任意两个公式，若A ? B是永真式，则称A与B是等值的。记做A B，称A B是等值式。 基本等值式 来自于代换实例 来自于量词处理 第一组基本等值式 由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。 命题逻辑中16组（24个）重要的等值式。 第二组基本等值式:消去量词等值式 第二组基本等值式:量词否定等值式 对于(1)式，“并不是所有的x都有性质A”与“存在x没有性质A”是一回事。对于(2)式，“不存在有性质A的x”与“所有x都没有性质A”是一回事。 第二组基本等值式:量词辖域收缩与扩张等值式 设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则 注意：这些等值式的条件。 第二组基本等值式:量词分配等值式 对∧ 对∨ 一阶逻辑等值演算基本规则 置换规则 设Φ(A)是含公式A的公式，Φ(B)是用公式B取代Φ(A)中所有的A之后的公式， 若A B，则Φ(A) Φ(B). ? 换名规则 设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为A，则A’ A. 代替规则 设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替，A中其余部分不变，设所得公式为A，则A A. 一阶逻辑等值演算 例5.1 将下面公式化成与之等值的公式，使其没有既是约束出现又是自由出现的个体变项。 分析 （1）哪些个体变项既是约束出现又是自由出现？ （2）选用合理的等值式或规则（换名或代替规则）。 (1)公式中，x,y都是既约束出现又自由出现的个体变项，可以通过换名规则或代替规则消去这种情况。 （练习） 换名规则 代替规则 例5.2. 证明 基本思路（等值演算） (1) 证明等价式是否为永真式; (2) 取任一解释证明即可。 例5.2（续） 量词一般无分配律 但当B(x)换成没有x出现的B时，则有 量词辖域收缩与扩张等值式 例5.3 设个体域为D＝{a,b,c}，将下面各公式的量词消去 基本思路：消去量词等值式。 给定解释求公式真值 基本思路 (1) 消去量词等值式； (2) 公式的解释。 给定解释求公式真值(续) 等值式证明 基本思路 可以从左边开始，也可以从右边开始 两大组等值式 16组重要的等值式； 有关量词的等值式。 三大规则 置换规则；换名规则；代替规则。 “选择性靠近” 例5.5 证明下列等值式 例5.5（续） 式(5.2) 式(5.2) 置换规则 例5.5（续）（练习） 课后作业 (1) 习题五 第2, 5题 （第79页）. 5.2. 一阶逻辑前束范式 析取范式、合取范式 前束范式 一阶逻辑公式的标准形——前束范式 定义5.2 设A为一个一阶逻辑公式，若A具有如下形式 ???????? ?Q1x1Q2x2…QkxkB 则称A为前束范式，其中Qi(1≤i≤k)为 或 ，B为不含量词的公式。 前束范式存在定