1-logic数理逻辑.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 5.2 一阶逻辑前束范式 定义5.2 设A为一个一阶逻辑公式，若A具有如下形式 Q1x1Q2x2…QkxkB 则称A为前束范式，其中Qi (1? i ?k)为?或?，B为不含量词 的公式. 例如， ?x?(F(x)?G(x)) ?x?y(F(x)?(G(y)?H(x,y))) 是前束范式 而 ??x(F(x)?G(x)) ?x(F(x)??y(G(y)?H(x,y))) 不是前束范式， * 前束范式存在定理 定理5.1（前束范式存在定理） 一阶逻辑中的任何公式都存在与之等值的前束范式 例4 求下列公式的前束范式 (1) ??x(M(x)?F(x)) 解 ??x(M(x)?F(x)) ? ?x(?M(x)??F(x)) （量词否定等值式） ? ?x(M(x)??F(x)) 后两步结果都是前束范式，说明公式的前束范式不惟一. * 求前束范式的实例 (2) ?xF(x)???xG(x) 解 ?xF(x)???xG(x) ? ?xF(x)??x?G(x) （量词否定等值式） ? ?x(F(x)??G(x)) （量词分配等值式） 或 ?xF(x)???xG(x) ? ?xF(x)??x?G(x) 量词否定等值式 ? ?xF(x)??y?G(y) 换名规则 ? ?x?y(F(x)??G(y)) 辖域收缩扩张规则 * 求前束范式的实例 (3) ?xF(x)??y(G(x,y)??H(y)) 或 ? ?xF(x)??y(G(z,y)??H(y)) 代替规则 ? ?x?y(F(x)?(G(z,y)??H(y))) 解 ?xF(x)??y(G(x,y)??H(y)) ? ?zF(z)??y(G(x,y)??H(y)) 换名规则 ? ?z?y(F(z)?(G(x,y)??H(y))) 辖域收缩扩张规则 * 5.3 一阶逻辑的推论理论 推理的形式结构 1. A1?A2???Ak ?B 若次式是永真式, 则称推理正确, 记作A1?A2???Ak ?B 2. 前提: A1, A2,?, Ak 结论: B 推理定理: 永真式的蕴涵式 * 推理定理 第一组 命题逻辑推理定理的代换实例 如, ?xF(x)??yG(y) ? ?xF(x) 第二组 基本等值式生成的推理定理 如, ?xF(x) ????xF(x), ???xF(x) ??xF(x) ??xF(x)??x?F(x), ?x?F(x) ? ??xF(x) 第三组 其他常用推理定律 (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) ?x(A(x)?B(x)) ? ?xA(x)??xB(x) * 量词消去引入规则 1. 全称量词消去规则(?-) 或 其中x,y是个体变项符号, c是个体常项符号, 且在A中x不在?y 和?y的辖域内自由出现. 2. 全称量词引入规则(?+) 其中x是个体变项符号, 且不在前提的任何公式中自由出现 ?xA(x) ?A(y) ?xA(x) ?A(c) A(x) ??xA(x) * 量词消去引入规则 3. 存在量词消去规则(?-) 其中x是个体变项符号, 且不在前提的任何公式和B中自由 出现 A(x)?B ??xA(x)?B * 量词消去引入规则 4. 存在量词引入规则(?+)