离散数学（第二版） 课件 邹丽娜 3.3 等值演算

离散数学第3章谓词逻辑3.1谓词逻辑概述目录3.2谓词公式与解释3.3谓词公式的等值演算3.4谓词推理3.3

谓词公式的等值演算3.3

谓词公式的等值演算命题逻辑中的所有等值式的代换实例都是谓词逻辑中的等值式，所以命题逻辑中的所有等值演算方法都可在谓词逻辑中使用。例如：双重否定律蕴涵-析取等值式谓词公式等值演算方法将公式中子公式利用已知的等值式替换没有完美的人

x(F(x))所有人都不完美

x(

F(x))并非所有的兔子都白

x(F(x))

x(

F(x))量词变换等值式量词消去…例3.14：设个体域D={a,b,c}，消去下列公式中的量词.(1)

x(F(x)→G(x))解(1)

x(F(x)→G(x))

(F(a)→G(a))

(F(b)→G(b))

(F(c)→G(c))例题

证明下列等值式左

(A(x1)

B)

(A(x2)

B)……

(A(xn)

B)

(A(x1)

A(x2)……A(xn))

B

xA(x)

B

右1例题

证明下列等值式2左

x(

A(x)

B)

x(

A(x)

)

B

x(A(x))

B

xA(x)→

B例题

证明下列等值式3左

(A(x1)

B)

(A(x2)

B)

……

(A(xn)

B)

A(x1)

A(x2)

……

A(xn)

B

xA(x)

B

量词辖域收缩与扩张等值式例题3.14设个体域D={a,b,c}，消去下列公式中的量词.(2)

x(F(x)

yG(y))解(2)

x(F(x)

yG(y))

xF(x)

yG(y)

(F(a)

F(b)

F(c))

(G(a)

G(b)

G(c))量词分配等值式每个人都得吃饭睡觉=每个人都吃饭，每个人都睡觉有的兔子是白色或者灰色=有的兔子是白色或者有的兔子是灰色有的人又抽烟又喝酒≠有的人抽烟，而有的人喝酒每个人要么是男人要么是女人≠每个人都是男人或者每个人都是女人量词交换等值式证明下列等值式（1）

x(A(x)→B(x))

xA(x)→

xB(x)证明

x(A(x)

B(x))

x(

A(x)

B(x))

x

A(x)

xB(x)

xA(x)

xB(x)

xA(x)

xB(x)（2）

x

y(P(x)→Q(y))

xP(x)→

yQ(y)证明x

y(P(x)

Q(y))

x

y(

P(x)

Q(y))

x(

P(x)

yQ(y))

x

P(x)

yQ(y)

xP(x)

yQ(y)

xP(x)

yQ(y)用等值演算证明下面的等值式变元换名规则约束变元换名规则要点：在辖域内更换为域内没使用过的名目的：确认子公式是否真正受到某量词的约束，使辖域更清晰。自由变元换名规则要点：在整个公式内更换为没使用过的名MN换名原则(步骤)如果约束变元与自由变元重名，约束变元重命名嵌套结构中，从内向外换名约束变元换名后，不用换自由变元练习谓词公式的前束范式不是前束范式

是前束范式

也就是说，一个谓词公式，如果量词均在全式的开头，它们的辖域延伸到整个公式的末尾，则为前束范式。求前束范式利用谓词公式的等值演算对变元换名（使约束变元之间，约束变元与自由变元之间不重名）否定后移量词前移（3）(xF(x,y)

yG(x,y))

量词前移(1)变元换名否定后移求前束范式

.(2)求前束范式变元换名量词前移求前束范式(3)(xF(x,y)

yG(x,y))

xF(x,y)

yG(x,y))

x

F(x,y)

y

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

u

F(u,y)

v

G(x,v))约束变项换名规则

u(

F(u,y)

v

G(x,v))量词收缩扩张等值式

u

v(

F(u,y)

G(x,v))量词收缩扩张等值式求前束范式

x(F(x)

yG(x,y,z))

zH(x,y,z)

x(F(x)

yG(x,y,u))

zH(v,w,z)自由变项代替规则

x

y(F(x)

G(x,y,u))

zH(v,w,z)量词收缩扩张等式

x

y

z((F(x)

G(x,y,u))

H(v,w,z))量词收缩扩张等式练习:求前束范式量词消去………例题设个体域D={a,b,c}，消去下列公式中的量词.(3)

x

y(F