复试2离散结构

12.3一阶逻辑等值式等值式基本等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式前束范式2等值式定义若AB是永真式,则称A与B是等值的,记作AB,并称AB为等值式基本等值式命题逻辑中基本等值式的代换实例如:xF(x)xF(x)xF(x)yG(y)xF(x)yG(y)(xF(x)yG(y))xF(x)yG(y)等3等值式消去量词等值式设D={a1,a2,…,an}xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)4实例例2

设个体域D={a,b,c},消去下面公式中的量词:(1)x(F(x)G(x))(F(a)G(a))(F(b)G(b))(F(c)G(c))(2)x(F(x)yG(y))xF(x)yG(y)量词辖域收缩(F(a)F(b)F(c))(G(a)G(b)G(c))x(F(x,a)F(x,b)F(x,c))(3)xyF(x,y)(F(a,a)F(a,b)F(a,c))(F(b,a)F(b,b)F(b,c))(F(c,a)F(c,b)F(c,c))5基本等值式(续)量词否定等值式设A(x)是含x自由出现的公式xA(x)xA(x)xA(x)xA(x)6基本等值式(续)量词分配等值式

x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：对无分配律，对无分配律7基本等值式(续)量词辖域收缩与扩张等值式

设A(x)是含x自由出现的公式，B中不含x的出现关于全称量词的：x(A(x)B)xA(x)Bx(A(x)B)xA(x)B

x(A(x)B)xA(x)Bx(BA(x))BxA(x)关于存在量词的:x(A(x)B)xA(x)Bx(A(x)B)xA(x)B

x(A(x)B)xA(x)Bx(BA(x))BxA(x)8置换规则、换名规则、代替规则置换规则设Φ(A)是含公式A的公式,Φ(B)是用公式B取代Φ(A)中的所有A得到的公式,则Φ(A)Φ(B)换名规则将公式A中某量词的指导变元及其在辖域内的所有约束出现改成该量词辖域内未曾出现的某个个体变项,其余部分不变,记所得公式为A,则AA

例:x(F(x,y)

yG(x,y,z))x(F(x,y)

tG(x,t,z))

代替规则将公式A中某个自由出现的个体变项的所有自由出现改成A中未曾出现的某个个体变项,其余部分不变,记所得公式为A,则AA例:x(F(x,y)

yG(x,y,z))x(F(x,t)

yG(x,y,z))

9实例例1

消去公式中既约束出现、又自由出现的个体变项

(1)xF(x,y,z)

yG(x,y,z)sF(s,y,z)

yG(x,y,z)换名规则sF(s,y,z)

tG(x,t,z)换名规则或者xF(x,u,z)

yG(x,y,z)代替规则xF(x,u,z)

yG(w,y,z)代替规则(2)x(F(x,y)

yG(x,y,z))x(F(x,y)

tG(x,t,z))换名规则或者x(F(x,t)

yG(x,y,z))代替规则10实例解(F(f(2))G(2,f(2)))(F(f(3))G(3,f(3)))例3

给定解释I:(a)D={2,3},(b)(c):x是奇数,:x=2y=2,:x=y.在I下求下列各式的真值:(1)x(F(f(x))G(x,f(x)))

(2)xyL(x,y)(11)(01)1解yL(2,y)yL(3,y)(L(2,2)L(2,3))(L(3,2)L(3,3))(10)(01)011实例例4

证明下列各等值式:

x(M(x)F(x))x(M(x)F(x))12实例例4

证明下列各等值式:

x(M(x)F(x))x(M(x)F(x))证左边x(M(x)F(x))量词否定等值式x(M(x)F(x))置换规则x(M(x)F(x))置换规则13实例例5

证明下列各等值式:x(F(x)G(x))x(F(x)G(x))14实例例5

证明下列各等值式: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))置换规则15实例例6

证明下列各等值式:xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))16实例例6

证明下列各等值式:xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))证左边x(y(F(x)G(y)H(x,y)))量词否定等值式xy(F(x)G(y)H(x,y)))置换规则

xy((F(x)G(y)H(x,y)))量词否定等值式

xy((F(x)G(y))H(x,y)))置换规则17实例例7

证明下列各等值式:xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))例8

证明下列各等值式:xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))18实例例7

证明下列各等值式:xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))证左边x(y(F(x)G(y)H(x,y))量词否定等值式xy(F(x)G(y)H(x,y))置换规则

xy((F(x)G(y))H(x,y))量词否定等值式

xy((F(x)G(y))H(x,y)))置换规则19前束范式定义设A为一个一阶逻辑公式,若A具有如下形式

Q1x1Q2x2…QkxkB则称A为前束范式,其中Qi

为或,1ik,B为不含量词的公式.例如xy(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))不是前束范式20公式的前束范式定理

(前束范式存在定理)一阶逻辑中的任何公式都存在与之等值的前束范式求前束范式的过程：(1)否定量词内移：否定量词等值式(2)合并变量：量词分配律（可选）(3)消除重名个体变项：换名规则和替换规则(4)等值推演：置换规则(5)量词前置：量词辖域收缩与扩张21公式的前束范式例9

求公式的前束范式(1)xF(x)xG(x)解xF(x)xG(x)量词否定等值式x(F(x)G(x))

量词分配等值式解2xF(x)yG(y)换名规则xF(x)yG(y)量词否定等值式x(F(x)yG(y))量词辖域扩张xy(F(x)G(y))量词辖域扩张22实例(续)(2)xF(x)xG(x)解xF(x)xG(x)量词否定规则xF(x)yG(y)换名规则x(F(x)yG(y))

量词辖域扩张xy(F(x)G(y))量词辖域扩张23实例