2.3一阶逻辑等价式与前束范式.ppt

* 以此页符号为修改标准 * 2.3 一阶逻辑等值式与前束范式 等值式 基本等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式 前束范式 5.1 一阶逻辑等值式与置换规则 在一阶逻辑中，有些命题可以有不同的符号化形式。 例如：没有不犯错误的人 令 M(x):x是人。 F(x):x犯错误。 则将上述命题的符号化有以下两种正确形式： (1) ┐?x(M(x)∧┐F(x)) (2) ?x(M(x)→F(x)) 我们称(1)和(2)是等值的。 说明 * 等值式与基本等值式 基本等值式: 命题逻辑中16组基本等值式的代换实例 如，?xF(x)??yG(y) ? ??xF(x)??yG(y) ?(?xF(x)??yG(y)) ? ??xF(x)???yG(y) 等 消去量词等值式 设D={a1,a2,…,an} ?xA(x)?A(a1)?A(a2)?…?A(an) ?xA(x)?A(a1)?A(a2)?…?A(an) 定义 若A?B为逻辑有效式，则称A与B是等值的， 记作 A?B，并称A?B为等值式. * 基本等值式(续) 量词辖域收缩与扩张等值式 设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) * 基本的等值式(续) 量词否定等值式 设A(x)是含x自由出现的公式 ??xA(x)? ?x ?A(x) ? ?xA(x)??x ?A(x) 量词分配等值式 ?x(A(x)?B(x))??xA(x)??xB(x) ?x(A(x)?B(x))??xA(x)??xB(x) 注意：?对?无分配律，?对?无分配律, 即 ?x(A(x)?B(x)) ?xA(x)??xB(x) ?x(A(x)?B(x)) ?xA(x)??xB(x) * 定理2．4 多个量词间的次序排列等值式。 (1) (2) * 例 例 将下面命题用两种形式符号化 (1) 没有不犯错误的人 (2) 不是所有的人都爱看电影 解 (1) 令F(x)：x是人，G(x)：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?y(F(x)?(G(y)?H(x,y))) ?x?(F(x)?G(x)) 是前束范式, 而 ?x(F(x)??y(G(y)?H(x,y))) ??x(F(x)?G(x)) 不是前束范式. 定义 设A为一个一阶逻辑公式, 若A具有如下形式 Q1x1Q2x2…QkxkB, 则称A为前束范式, 其中Qi (1?i?k) 为?或?，B为不含量词的公式. * 公式的前束范式 例 求下列公式的前束范式 (1) ??x(M(x)?F(x)) 解 定理（前束范式存在定理）一阶逻辑中的任何公 式都存在与之等值的前束范式 求前束范式: 使用重要等值式、置换规则、换名规则进行等值演算. ? ?x(?M(x)??F(x)) 量词否定等值式 ? ?x(M(x)??F(x)) 两步结果都是前束范式，说明前束范式不惟一. * 例(续) (2) ?xF(x)???xG(x) 解 ??xF(x)??x?G(x) （量词否定等值式） ??x(F(x)??G(x)) （量词分配等值式） 或者 ??xF(x)??x?G(x) ??xF(x)??y?G(y) ( 换名规则 ) ??x?y(F(x)??G(y)) ( 量词辖域扩张 ) * 例(续)