离散数学教学课件-ch5.pptVIP

第五章 一阶逻辑等值演算与推理 主要内容 一阶逻辑等值式与基本的等值式 置换规则、换名规则、代替规则 前束范式 自然推理系统NL 及其推理规则 5.1 一阶逻辑等值式与置换规则 定义 设A, B是两个谓词公式, 如果A?B是永真式, 则称A与B等值, 记作A?B. 基本等值式 第一组 命题逻辑中16组基本等值式的代换实例 例如: ?xF(x)??yG(y) ? ??xF(x)??yG(y) 等 第二组 (1) 消去量词等值式 设D ={a1, a2, … , an}, 则 ① ?xA(x) ? A(a1)?A(a2)?…?A(an) ② ?xA(x) ? A(a1)?A(a2)?…?A(an) 基本等值式 (2) 量词否定等值式 ① ??xA(x) ? ?x?A(x) ② ??xA(x) ? ?x?A(x) (3) 量词辖域收缩与扩张等值式 设公式B 不含 x 的出现, 则 ① ?x(A(x)?B) ? ?xA(x)?B ② ?x(A(x)?B) ? ?xA(x)?B ③ ?x(A(x)?B) ? ?xA(x)?B ④ ?x(B?A(x)) ? B??xA(x) 基本等值式 ① ?x(A(x)?B) ? ?xA(x)?B ② ?x(A(x)?B) ? ?xA(x)?B ③ ?x(A(x)?B) ? ?xA(x)?B ④ ?x(B?A(x)) ? B??xA(x) (4) 量词分配等值式 ① ?x(A(x)?B(x)) ? ?xA(x)??xB(x) ② ?x(A(x)?B(x)) ? ?xA(x)? ?xB(x) 注：?对?，?对?无分配律 置换规则、换名规则、代替规则 等值演算的3条规则： 1. 置换规则 设?(A)是含A的公式, 那么, 若A?B, 则?(A)??(B). 2. 换名规则（针对约束出现的个体变项） ?xF(x,y,z)??yG(x,y,z) ? ?tF(t,y,z)??uG(x,u,z) 3. 代替规则（针对自由出现的个体变项） ?xF(x,y,z)??yG(x,y,z) ? ?xF(x,t,z)??yG(u,y,z) 实例 例1 设D={a,b,c}, 将下列公式的量词消去. (1) ?x(F(x)?G(x)) (2) ?x(F(x) ? ?yG(y)) (3) ?x?yF(x, y) 例2. 给定解释I如下： (a) D={2,3} (b) D中特定元素 (c) D上特定函数 (d) D上特定谓词 例3. 证明等值式： ? ?x?y(F(x)?G(y)?L(x,y)) ??x?y((F(x)?G(y))? ?L(x,y)) 5.2 一阶逻辑前束范式 定义 设A为谓词公式，若A具有如下形式： Q1x1Q2x2…QkxkB, 其中Qi (1? i ?k)为?或?，B为不含量词的公式， 则称A为前束范式. 例如， ?x?y(F(x)?(G(y)?H(x,y))) 是前束范式 ?x(F(x)??y(G(y)?H(x,y))) 不是前束范式 前束范式存在定理 定理（前束范式存在定理） 一阶逻辑中任何公式都存在与之等值的前束范式. 注：前束范式存在，但不惟一. 5.3 一阶逻辑的推理理论 一、推理的形式结构 前提: A1, A2,?, Ak 结论: B 推理的形式结构: A1?A2???Ak ?B (*) 判断推理是否正确归结为判断(*)式是否为永真式 二、推理定律: 1. 命题逻辑推理定律的代换实例 ?xF(x)??yG(y) ? ?xF(x) 2. 基本等值式生成的推理定律 ??xF(x)??x?F(x), ?x?F(x) ? ??xF(x) 推理定律 3. 一些常用的重要推理定律 (1) ?xA(x)??xB(x) ? ?x(A(x)?B(x)) (2) ?x(A(x)?B(x)) ? ?xA(x)? ?xB(x) (3) ?x(A(x)?B(x)) ? ?xA(x)? ?xB(x) (4) ?xA(x)? ?xB(x) ? ?x(A(x)?B(x)) 量词消去引入规则 三、4条消去量词和引入量词的规则 1. 全称量词消去规则(?-) (1) ?xA(x)?A(y) (2) ?xA(x)?A(c) 两式成立的条件： (a) x是