离散数学屈婉玲第五章.pptVIP

* * * * * * 主要内容 一阶逻辑等值式与基本的等值式 置换规则、换名规则、代替规则 前束范式 第五章 一阶逻辑等值演算 * 5.1 一阶逻辑等值式与置换规则 定义5.1 设A, B是两个谓词公式, 如果A?B是永真式, 则称A 与B等值, 记作A?B, 并称A?B是等值式 基本等值式 第一组 命题逻辑中16组基本等值式的代换实例 例如，???xF(x)??xF(x), ?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) 量词辖域收缩与扩张等值式. A(x) 是含 x 自由出现的公式，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) 注意：?对?，?对?无分配律 * 置换规则、换名规则、代替规则 1. 置换规则 设?(A)是含A的公式, 那么, 若A?B, 则?(A)??(B). 2. 换名规则 设A为一公式，将A中某量词辖域中个体变项的所有约束 出现及相应的指导变元换成该量词辖域中未曾出现过的个 体变项符号，其余部分不变，设所得公式为A?，则A??A. 3. 代替规则 设A为一公式，将A中某个个体变项的所有自由出现用A中 未曾出现过的个体变项符号代替，其余部分不变，设所得 公式为A?，则A??A. * 实例 例1 将下面命题用两种形式符号化, 并证明两者等值: (1) 没有不犯错误的人 解 令F(x)：x是人，G(x)：x犯错误. ??x(F(x)??G(x)) 或 ?x(F(x)?G(x)) ??x(F(x)??G(x)) ? ?x?(F(x)??G(x)) 量词否定等值式 ? ?x(?F(x)?G(x)) 置换 ? ?x(F(x)?G(x)) 置换 * 实例 (2) 不是所有的人都爱看电影 解 令F(x)：x是人，G(x)：爱看电影. ??x(F(x)?G(x)) 或 ?x(F(x)??G(x)) ??x(F(x)?G(x)) ? ?x?(F(x)?G(x)) 量词否定等值式 ? ?x?(?F(x)?G(x)) 置换 ? ?x(F(x)??G(x)) 置换 * 实例 例2 将公式化成等值的不含既有约束出现、又有自由出现 的个体变项: ?x(F(x,y,z)??yG(x,y,z)) 解 ?x(F(x,y,z)??yG(x,y,z)) ? ?x(F(x,y,z)??tG(x,t,z)) 换名规则 ? ?x?t(F(x,y,z)?G(x,t,z)) 辖域扩张等值式 或者 ?x(F(x,y,z)??yG(x,y,z)) ? ?x(F(x,u,z)??yG(x,y,z)) 代替规则 ? ?x?y(F(x,u,z)?G(x,y,z)) 辖域扩张等值式 * 实例 例3 设个体域D={a,b,c}, 消去下述公式中的量词: (1) ?x?y(F(x)?G(y)) 解 ?