《离散数学》课程PPT教学课件（讲稿）第2章 一阶逻辑（2.3）一阶逻辑等值式

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 ) 定义 若AB为逻辑有效式，则称A与B是等值的， 记作 AB，并称AB为等值式

基本等值式(续) 量词辖域收缩与扩张等值式 设A(x)是含x自由出现的公式,B中不含x的出现 关于全称量词的: 关于存在量词的: Vx((x)vB)分→Vx4(x)vB 彐x(4(x)VB)B)4(x)→>B3x(4(x)->B)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)) 给出演算过程，并说明理由

前束范式 定义设A为一个一阶逻辑公式,若A具有如下形式 Q1x1Q2x2…QB,则称4为前束范式,其中Q(1≤k) 为V或彐,B为不含量词的公式 例如,Vxy(F(x)-→>(G()∧H(xy) Vx-(F)AG(r) 是前束范式,而 Vx(F(x)→>彐y(G()∧H(xy)) x(F(x)∧G(x) 不是前束范式

6 前束范式 例如，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具有如下形式 Q1 x1Q2 x2…Qk xkB, 则称A为前束范式, 其中Qi (1ik) 为或，B为不含量词的公式

公式的前束范式 定理(前束范式存在定理)一阶逻辑中的任何公 式都存在与之等值的前束范式 注意: 公式的前束范式不惟 求公式的前束范式的方法:利用重要等值式、 置换规则、换名规则、代替规则进行等值演算

7 公式的前束范式 定理（前束范式存在定理）一阶逻辑中的任何公 式都存在与之等值的前束范式 注意: 公式的前束范式不惟一 求公式的前束范式的方法: 利用重要等值式、 置换规则、换名规则、代替规则进行等值演算

换名规则与代替规则 换名规则:将量词辖域中出现的某个约束出现的 个体变项及对应的指导变项,改成另一个辖域中未 曾出现过的个体变项符号,公式中其余部分不变, 则所得公式与原来的公式等值 代替规则:对某自由出现的个体变项用与原公式 中所有个体变项符号不同的符号去代替,则所得公 式与原来的公式等值

8 换名规则与代替规则 换名规则: 将量词辖域中出现的某个约束出现的 个体变项及对应的指导变项，改成另一个辖域中未 曾出现过的个体变项符号，公式中其余部分不变， 则所得公式与原来的公式等值. 代替规则: 对某自由出现的个体变项用与原公式 中所有个体变项符号不同的符号去代替，则所得公 式与原来的公式等值

公式的前束范式(续) 例求下列公式的前束范式 (1)_3x(M(x)∧F(x) 解3x(M(x)F(x) 台x(M(x)-F(x)(量词否定等值式) Vx(M(x)→-F(x) 两步结果都是前束范式,说明前束范式不惟

9 公式的前束范式(续) 例 求下列公式的前束范式 (1) x(M(x)F(x)) 解 x(M(x)F(x))  x(M(x)F(x)) （量词否定等值式）  x(M(x)→F(x)) 两步结果都是前束范式，说明前束范式不惟一

例(续) (2)VxF()AxG(r) 解VxF(x)_3xG(x) 兮∨xF(x)∧x-(x)(量词否定等值式) →Vx(F(x)∧G(x) (量词分配等值式) 另有一种形式 VxF(x)彐xG(x) 冷VxF(x)∧Vx-G(x) →VxF(x)∧yy=G) (代替规则) 兮∨xvy(F(x)∧-G()(量词辖域扩张) 两种形式是等值的 10

10 例(续) (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)) ( 量词辖域扩张 ) 两种形式是等值的