教案第3章-一阶逻辑

3.2.1一阶逻辑等值式与置换规则3.2.2一阶逻辑的前束范式3.2一阶逻辑等值演算一、一阶逻辑等值式的定义

二、一阶逻辑的基本等值式三、3条规则

四、一阶逻辑等值演算3.2.1一阶逻辑等值式与置换规则

3.2.1一阶逻辑等值式与置换规则一、等值式的定义定义3.10

（P.94）设A，B是一阶逻辑中的任意两个公式，若AB

是永真式，则称A与B是等值的。记作：AB，并称AB

为等值式。与命题逻辑中的等值式类似，一阶逻辑中也有基本而重要的等值式。二、一阶逻辑的基本等值式第1组(P.95)：

命题逻辑中基本等值式的代换实例，都是一阶逻辑中的等值式。例如：xF(x)yG(y)xF(x)yG(y)

是命题公式

AB

A∨B

的代换实例。(xF(x)yG(y))xF(x)yG(y)

是命题公式

(AB)

AB

的代换实例。第2组（一阶逻辑特有的）

（1）消去量词等值式

设个体域为有限集：

D={a1,a2,…,an}

①

xA(x)

A(a1)A(a2)…A(an)

②

xA(x)

A(a1)A(a2)…A(an)

二、一阶逻辑的基本等值式第2组（一阶逻辑特有的）

（2）量词否定等值式设A(x)

是任意的含x

自由出现的公式，则

①

xA(x)xA(x)

②

xA(x)xA(x)

二、一阶逻辑的基本等值式证明：设个体域为有限集：D={a1,a2,…,an}，

①

xA(x)

(A(a1)∧A(a2)∧…∧A(an))

A(a1)∨A(a2)∨…∨A(an)

xA(x)对于无穷个体域，xA(x)可理解为：“不是任意的x满足A(x)”，即“存在某些

x，不满足A(x)”。

∴

xA(x)

xA(x)课堂练习（教材p104习题3.20(1)）证(2)

xA(x)

(A(a1)∨A(a2)∨…∨A(an))

A(a1)∧A(a2)∧…∧A(an)

xA(x)类似地，在无限域上，可解释为：如果x

A(x)为真，则

xA(x)表示： “至少存在一个x，能使A(x)为真”命题为假。它等价于“不存在任何一个x能使A(x)为真”，或者“对于所有的x，A(x)是假的”。即：xA(x)

xA(x)（3）量词辖域收缩与扩张等值式

假设个体变项

x在公式A(x)

中自由出现，

x不在公式

B

中出现，则①关于全称量词

“”

的等值式有：

x

(A(x)B)

xA(x)B

x

(A(x)B)

xA(x)B

x

(A(x)B)

xA(x)B

x

(BA(x))

BxA(x)

二、一阶逻辑的基本等值式前变后不变证明等值式

x(A(x)∨B)

x

A(x)∨B

证：设个体域为有限集D

={a1,a2,…,an}，

x(A(x)∨B)

(A(a1)∨B)∧(A(a2)∨B)∧…∧(A(an)∨B)

(A(a1)∧A(a2)…∧A(an))∨B

xA(x)∨B

二、一阶逻辑的基本等值式（3）量词辖域收缩与扩张等值式

②关于存在量词“”的等值式：（设x在A(x)中自由出现，x不在B中出现。）

x

(A(x)

B)

xA(x)Bx

(A(x)B)

xA(x)B

x

(A(x)B)

xA(x)B

x

(BA(x))

BxA(x)

二、一阶逻辑的基本等值式前变后不变证明等值式

x

(A(x)B)

x

A(x)B

证明：x(A(x)

B)

x(A(x)∨B)

(x

A(x)∨B)

(量词辖域收缩)

(xA(x)∨B)

(量词否定等值式)

xA(x)B

二、一阶逻辑的基本等值式例子：联欢会上所有的人既唱又跳联欢会上所有的人唱歌且所有的人跳舞

∴

x(A(x)∧B(x))

xA(x)∧xB(x)例子：联欢会上，有的人唱，有的人跳。

∴

x(A(x)∨B(x))

xA(x)∨xB(x)

二、一阶逻辑的基本等值式（4）量词分配等值式

①

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)

二、一阶逻辑的基本等值式例3.11(P.97)判断下式是否为重言式？(1)x(A(x)∨B(x))xA(x)∨xB(x)证：给出一个解释I：设个体域

D=N，F(x)：x

是奇数，G(x)：x

是偶数。

公式左

=

x(F(x)∨G(x))

公式右

=

x

F(x)∨x

G(x)

∴

x(A(x)∨B(x))xA(x)∨xB(x)不是重言式。

∴

x(A(x)∨B(x))

≠

xA(x)∨xB(x)真命题假命题例3.11

验证下式是否为重言式？

(2)

x(A(x)∧B(x))

x

A(x)∧x

B(x)

证：给出一个解释I：设个体域D=N，F(x)：x是奇数，G(x)：x是偶数。公式右

=

xF(x)∧xG(x)公式左

=

x(F(x)∧G(x))∴

x(A(x)∧B(x))

x

A(x)∧x

B(x)

不是重言式

∴

x(A(x)∧B(x))

≠

x

A(x)∧x

B(x)真命题假命题（1）置换规则设Φ(A)是含公式A

的公式，Φ(B)是用公式

B

取代Φ(A)中所有公式A

得到的公式，若AB，则Φ(A)

Φ(B)。注意：这里的置换规则与命题逻辑中的置换规则，形式上完全一样，但公式内容是不同的。

三、3条规则（2）换名规则－－对约束变项①对公式A

中的约束变项及相应的指导变项换名，对该变项在辖域中的所有出现，均须同时更改，公式的其余部分不变。②

换名时，一般用公式

A

中未出现过的字母符号去更换。若记换名后的公式为A，则A

A。什么时候需要对公式中变项进行换名？

三、3条规则例子：试对如下公式中既约束出现、又自由出现

的个体变项使用换名规则。x

(Q(x)R(x,y))∨zP(

x,z

)解：对约束变项

x

换名后得：u

(Q(u)R(u,y))∨zP(x,z)试判断下面的换名是否正确：

①

u(Q(u)R(x,y))∨zP(x,z)②

x(Q(u)R(u,y))∨zP(x,z)③

u(Q(u)R(u,y))∨zP(u,z)④

y(Q(y)R(y,y))∨zP(x,z)

（3）

代替规则－－对自由变项①对公式A

中某个自由变项，可以用新变项名代替。代替时，需要对该自由变项的所有出现，同时代替。②

代替的字母符号，一般取原公式A中，没有出现的。若记代替后所得公式为A，则A

A。什么时候需要使用代替规则？

三、3条规则例子：试对如下公式中既约束出现、又自由出现

的个体变项使用代替规则。

x

(Q(x)R(x,y))∨zP(x,z)解：由换名规则：

原式

u(Q(u)R(u,y))∨zP(x,z)由代替规则：

原式

x(Q(x)R(x,y))∨zP(u,z)例3.10

(P.96)消去下列公式中既约束出现、又自由出现

的个体变项。(1)xF(x,y,z)

yG(x,y,z)

tF(t,y,z)

yG(x,y,z)或者

xF(x,y,z)

yG(x,y,z)

xF(x,t,z)

yG(x,y,z)

xF(x,t,z)

yG(w,y,z)换名规则代替规则

tF(t,y,z)

w

G(x,w,z)四、一阶逻辑等值演算课堂练习（教材p104习题3.21(1)）例3.12(P.97)

设个体域D={a,b,c

}，试将下面各公式中的量词消去。

(1)

x

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

x

(F(x)∨yG(y))

xF(x)∨yG(y)(3)

xyF(x,y)解：（板书）四、一阶逻辑等值演算课堂练习（教材p105习题3.23(1)）

例3.13

(P.98)求下面公式在解释I

下的真值。

(1)x(F(x)∧G(x,a))(2)x(F(f(x))∧G(x,f(x)))

解释I如下：

D={2,3}；

a=2；

f

(2)=3、f

(3)=2；F(2)=0、F(3)=1；G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0；

解：

(1)x(F(x)∧G(x,a))

(F(2)∧G(2,2))∧(F(3)∧G(3,2))

(0∧1)∧(1∧1)

0(2)x(F(f(x))∧G(x，f(x)))

(F(f(2))∧G(2，f(2)))

∨

(F(f(3))∧G(3，f(3)))

(F(3)∧G(2，3))∨(F(2)∧G(3，2))

(1∧1)∨(0∧1)

1解释I

：

D={2,3}；a：2；

f(2)=3、f(3)=2；

F(2)=0、F(3)=1；

G(2,2)=

G(2,3)=G(3,2)=1、G(3,3)=0；例3.14

（P.98）证明下列各等值式：(1)

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))量词否定等值式置换规则(2)xy

(F(x)G(y)H(x,y))

xy(F(x)G(y)

H(x,y))四、一阶逻辑等值演算定义3.11（P.99）

设

A

为一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且它们的辖域一直延伸到公式的末尾，则称这种形式的公式为A

的前束范式。记为：

Q1x1Q2x2

…Qkxk

B其中，每个Qi

(1≤i≤k)为量词或，

B

为不含量词的谓词公式。3.2.2

一阶逻辑前束范式例子：(1)xy

(F(x)∧G(y)

H(x,y))

(2)

xy

z

(F(x)∧G(y)∧H(z)

L(x,y,z))(3)

F(

x,

y

)都是前束范式。(4)x

F(x)

∧y

G(x,y)(5)x

P(x)

y

Q(y)都不是前束范式。3.2.2

一阶逻辑前束范式定理3.3(P.99)

任一谓词公式都存在与之等值的前束范式。证明：（构造性证明）

(1)

将否定联结词“”

内移，使之只作用于原子公式。

(2)

利用换名或代入规则，使所有约束变项的符号，均不相同，并且自由变项与约束变项的符号，也不相同。3.2.2

一阶逻辑前束范式(3)

利用量词辖域的扩张和收缩等值式，将所有量词以在公式中出现的顺序，移到公式最前面，以扩大量词的辖域至整个公式。注意：原公式中自由出现的个体变项，在前束范式中仍是自由出现。3.3.2

一阶逻辑前束范式

例3.15（P.99）求下列公式的前束范式。

(1)

xF(x)

xG(x)

解：

xF(x)

xG(x)xF(x)xG(x)(量词否定等值式)

x(F(x)G(x))

(量词分配等值式)3.2.2

一阶逻辑前束范式例3.15（P.99）求下列公式的前束范式(2)

xF(x)

xG(x)

解：

xF(x)

xG(x)xF(x)

xG(x)(量词否定等值式)xF(x)

yG(y)

(换名规则)

x

(F(x)

yG(y))

(量词辖域扩张)

xy(F(x)G(y))

(量词辖域扩张)3.2.2

一阶逻辑前束范式

例3.16

（P.100）求下列公式的前束范式

(2)

xF(x)xG(x)

解:

xF(x)xG(x)xF(x)

yG(y)

(换名规则)x

(F(x)yG(y))

(量词辖域扩张)3.2.2

一阶逻辑前束范式x

y

(F(x)G(y)

)

(量词辖域扩张)例3.17

(P.101)

(1)

xF(x,y)yG(x,y)

解1

tF(t,y)wG(x,w)换名规则

t

(F(t,y)

wG(x,w))

量词辖域扩张

解2xF(x,y)

yG(x,y)

xF(x,t)yG(w,y)代替规则

xy(F(x,t)G(w,y))

量词辖域扩张3.2.2

一阶逻辑前束范式

t

w

(F(t,y)G(x,w))

量词辖域扩张例3.17（2）板书课堂练习（教材p105习题3.29）例：求公式A：(xP(x)∨yQ(y))

xR(x)

的前束范式。解：A

(xP(x)∨yQ(y))

∨

xR(x)

(xP(x)∧yQ(y))

∨

xR(x)

(xP(x)

∧yQ(y))

∨

zR(z)

x(P(x)

∧yQ(y))

∨

zR(z)

xy(P(x)

∧Q(y))

∨

zR(z)

x(y

(P(x)

∧Q(y))

∨

zR(z))

xy

((P(x)

∧Q(y))

∨

zR(z))