23一阶逻辑等值式 等值式 ■基本等值式 ■量词否定等值式 ■量词辖域收缩与扩张等值式 量词分配等值式 前束范式
1 2.3 一阶逻辑等值式 ▪等值式 ▪基本等值式 ▪量词否定等值式 ▪量词辖域收缩与扩张等值式 ▪量词分配等值式 ▪前束范式
等值式与基本等值式 定义若A<>B为逻辑有效式,则称A与B是等值的, 记作AB,并称A分→B为等值式 基本等值式: 命题逻辑中16组基本等值式的代换实例 如,xF(x)→>yG(0)分-VxF(xvyG() (vxF(x)vyG()兮VxFx)∧-3yG()等 消去量词等值式设D={a142…,an} VxA(x)令4(a1)~4(a2)A…AA(an 彐xA(x)<4(a1v4(a2)V…vA(an
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 ) 定义 若AB为逻辑有效式，则称A与B是等值的， 记作 AB，并称AB为等值式
基本等值式(续) 量词辖域收缩与扩张等值式 设A(x)是含x自由出现的公式,B中不含x的出现 关于全称量词的: 关于存在量词的: Vx((x)vB)分→Vx4(x)vB 彐x(4(x)VB)<4(x)vB Vx(4(x)AB)分x4(x)入Bx(4(x)B)分→丑4(x)AB Vx(4(x)→>B)4(x)→>B3x(4(x)->B)<→Vx4(x)>B Vx(B→>4(x)分→>B-vA(x)x(B→4(x)今→B-)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)
基本的等值式(续) 量词分配等值式 vx((x)入B(x)→x(x)∧xB(x) 彐x(4(x)vB(x)冷冷x4(x)vxB(x) 注意:对v无分配律,彐对∧无分配律
4 基本的等值式(续) 量词分配等值式 x(A(x)B(x))xA(x)xB(x) x(A(x)B(x))xA(x)xB(x) 注意：对无分配律，对无分配律
基本的等值式(续) 例将下面命题用两种形式符号化 (1)没有不犯错误的人 (2)不是所有的人都爱看电影 解(1)令F(x):x是人,G(x):x犯错误 x(F(x)入G(x) eVx(F(c)G() 请给出演算过程,并说明理由 (2)令F(x):x是人,G(x):爱看电影. Vx(F(x)G()) 彐x(F(x)入_G(x) 给出演算过程,并说明理由
5 基本的等值式(续) 例 将下面命题用两种形式符号化 (1) 没有不犯错误的人 (2) 不是所有的人都爱看电影 解 (1) 令F(x)：x是人，G(x)：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)) 给出演算过程，并说明理由