离散数学（第2版）2.3谓词公式间的关系.pdf

2.3谓词公式间的关系

谓词公式间的关系：逻辑等价与逻辑蕴涵。

2.3.1谓词公式间的逻辑等价

定义2.15

设A、B是谓词公式，E是它们共同的个体域。若在个体域E中的任何解释下，A、B在都具有相同的

真值，则称谓词公式A和B在E上逻辑等价。

定义2.16

设A、B是谓词公式，如果在任一个体域上A和B都逻辑等价，则称A和B是逻辑等价，记作AB。

等价置换（置换规则）

设Φ(A)是含合式公式A的合式公式，Φ(B)是用合式公式B取代Φ(A)中所有的A之后的合式公式，

若AB，则Φ(A)Φ(B).

2.3.1谓词公式间的逻辑等价

根据所给出的谓词公式的逻辑等价定义，就可以讨论谓词演算的一些基本逻辑等价式。

1）命题公式的推广

由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而命题公式的基本逻辑

等价式的代换实例都是一阶逻辑的逻辑等价式。

例如：xF(x)xF(x)

xF(x)yG(y)xF(x)yG(y)

2.3.1谓词公式间的逻辑等价

2）量词否定逻辑等价式

定理2.3（1）﹁xP(x)x(﹁P(x))

（2）﹁xP(x)x(﹁P(x))

证：（1）若个体域E是有限的，设个体域为{a,a,…,a}，则有

12n

﹁xP(x)﹁(P(a)∧P(a)∧…∧P(a))

12n

﹁P(a)∨﹁P(a)∨…∨﹁P(a)

12n

x(﹁P(x))

若个体域E是无限的，设﹁xP(x)的真值为1，则xP(x)的真值为0，即存在着某个个体a∈E

0

使P(a)的真值为0，因此﹁P(a)的真值为1，从而x(﹁P(x))的真值为1。

00

因此当﹁xP(x)的真值为1时，x(﹁P(x))的真值也为1。

同理可证当﹁xP(x)的真值为0时，x(﹁P(x))的真值也为0。

故无论个体域E是有限的或是无限的都有

﹁xP(x)x(﹁P(x))

（2）的证明与（1)相似，不再详述。

证毕。

2.3.1谓词公式间的逻辑等价

3）量词辖域的扩张与收缩

定理2.4（1）x(A(x)∨B)xA(x)∨B

（2）x(A(x)∧B)xA(x)∧B

（3）x(A(x)∨B)xA(x)∨B

（4）x(A(x)∧B)xA(x)∧B

其中，公式B中不出现约束变元x。

根据对量词及其辖域的理解，很容易证明此定理。该定理还可以扩充到谓词的变元与

量词的指导变元不同的情形，如：

•x(P(x)∨Q(y))xP(x)∨Q(y)

•x(yP(x,y)∧Q(z))xyP(x,y)∧Q(z)

推论2.1（1）x(A(x)B)x(A(x)B)

（2）xA(x)Bx(A(x)B)

（3）Bx(A(x)x(BA(x))

（4）Bx(A(x)x(BA(x))

2.3.1谓词公式间的逻辑等价

4）量词分配逻辑等价式

定理2.51）xA(x)∧xB(x)x(A(x)∧B(x))

2）xA(x)∨xB(x)x(A(x)∨B(x))

证：（1）设E为任一个体域，若xA(x)∧xB(x)的真值为1，则xA(x