（5）?x(P(x,肖琴)?Q(x,肖琴)) （6）?x?y(y?x?P(x,y))

（7）?x?y(y?x?(P(x,y)?Q(x,y))) （8）?x?y(x?y?P(x,y)?P(y,x)) （9）?xP(x,x)

（10）?x?y(x?y?P(x,y)?Q(y,x))

§2.2 谓词公式及其解释

习题2.2

1. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。

（1）?x(P(x)?Q(x，y)) （2）?xP(x，y)??yQ(x，y)

（3）?x?y(P(x，y)?Q(y，z))??xR(x，y，z)

解 （1）?x中的x是指导变元；量词?x的辖域是P(x)?Q(x,y)；x是约束变元，y是自由变元。

（2）?x中的x，?y中的y都是指导变元；?x的辖域是P(x，y)，?y的辖域是

Q(x，y)；P(x，y)中的x是?x的约束变元，Q(x，y)中的x是自由变元，y是自由变元；

y是?y的约束变元。

（3）?x中的x，?y中的y 以及?x中的x都是指导变元；?x的辖域是

?y(P(x，y)?Q(y，z))，?y的辖域是P(x，y)?Q(y，z)，?x的辖域是R(x，y，z)；P(x，y)中的x，Q(y，z)中的y是约束变元；R(x，y，z)y都是约束变元；z是自由变元，

中的x为约束变元，y，z是自由变元。

，2}，请给出两种不同的解释I1和I2，使得下面谓词公式在I1下都2. 设个体域D?{1是真命题，而在I2下都是假命题。

（1）?x(P(x)?Q(x))

（2）?x(P(x)?Q(x))

，2}，P(x):x?0,Q(x):x?0。 解（1）解释I1：个体域D?{1，2}，P(x):x?0,Q(x):x?2。 （2）解释I2：个体域D?{1

3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。 （1）?x(P(x)??y(Q(y)?R(x，y))) （2）?x?y(P(x)?Q(y)?R(x,y))

解 （1）成真解释：个体域D＝{1,2,3},P(x):x?0,Q(y):y?2,R(x,y):x?y?3。 成假解释：个体域D＝{1,2,3},P(x):x?0，Q(y):y?2，R(x,y):x?y?1。 （2）成真解释：个体域D＝{1,2,3}，P(x):x?0，Q(y):y?2，R(x,y):x?y?3。

成假解释：个体域D＝{1,2,3},P(x):x?0，Q(y):y?0，R(x,y):x?y?1。

4. 给定解释I如下：

个体域D?R（这里R为实数集合）。 个体常元a?0。

二元函数f(x，y)?x?y。

二元谓词P(x，y)：x?y，Q(x，y)：x?y。

在解释I下，下列公式的含义是什么？哪些成为命题哪些不成为？成为命题的其真值又（1）?x?y(Q(x，y)??P(x，y)) （2）?x?y(P(f(x，y)，a)?Q(x，y)) （3）?x?y(Q(x，y)??P(f(x，y)，a)) （4）?x?y(Q(f(x，y)，a)?P(x，y))

解（1）公式被解释成“?x?y(x?y?x?y)”，为真命题。 （2）公式被解释成“?x?y(x?y?0?x?y)”，为假命题。

（3）公式被解释成“?x?y(x?y?x?y?0)”，为真命题。 （4）公式被解释成“?x?y(x?y?0?x?y)”，为假命题。

5. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。

（1）P(x)??xP(x) （3）P(x)??xP(x)

（2）?xP(x)?P(x)

（4）?xP(x)?P(x)

（6）?x?yP(x，y)??y?xP(x，y) （8）?x?yP(x，y)??x?yP(x，y) （10）?x?y(P(x，y)?P(y，x))

如何？

（5）?x(P(x)??P(x))

（7）?x?yP(x，y)??x?yP(y，x) （9）?x?yP(x，y)??y?xP(x，y)

解（1）因为当存在某个x使P(x)取1时?xP(x)一定取1，所以公式是为永真式。

2P(x)：x?0。在I1下公式的前件与后件均I（3）取解释1：个体域为自然数集合，

为真，所以公式为真，即不是永假式。取解释I2：个体域仍为自然数集合，但P(x)取为x?0。

在I2下公式不成为命题，即不是永真式。综合知公式为可满足式。

2P(x)：x?0。在I1下，对任意的x，P(x)I1（5）取解释：个体域为自然数集合，

为真而?P(x)为假，所以公式为假，即不是永真式。取解释I2：个体域仍为自然数集合，2但P(x)取为x?0。在I2下，对任意的x，P(x)为假而?P(x)为真，所以公式为真，即

不是永假式。综合知公式为可满足式。

（7）公式为永真式，用非形式化的反证法证明如下：若公式非永真，则存在一个解释，使得?x?yP(x，y)取1而?x?yP(y，x)取0。?x?yP(y，x)取0表明存在某对x0,y0使

得P(y0，x0)取0，从而?x?yP(x，y)也应取0。这与前面说?x?yP(x，y)取1矛盾。故公式是永真式。

（9）

设I为任意一个解释，个体域为D。若?x?yP(x，y)取1，即存在x0?D，

使得?yP(x0，y)为真，从而?y?xP(x，y)为真，故?x?yP(x，y)??y?xP(x，y)为真。所以在解释I下公式为真，由I的任意性可知，公式为永真式。

（2）、（4）、（6）、（8）、（10）略。

6. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。

（1）?x(P(x)?Q(x))?(?xP(x)??yQ(y)) （2）?x(P(x)?Q(x))?(?xP(x)??yQ(y)) （3）?(?xP(x)??yQ(y))??yQ(y) （4）?x(P(y)?Q(x))?(P(y)??xQ(x)) （5）?x(P(x)?Q(x))?(P(x)??xQ(x)) （6）?(P(x)?(?yQ(x，y)?P(x))) （7）P(x，y)?(Q(x，y)?P(x，y)) 解 略

7. 给出一个非闭式的永真式，给出一个非闭式的永假式，给出一个非闭式的可满足式。 解 略

§2.4 谓词公式的推理演算

习题2.4

1. 利用非形式化证明方法或等价演算法证明如下推理关系： （1）?x(A(x)?B(x))??x(A(x)?B(x)) （2）?xA(x)??xB(x)??xA(x)??xB(x) （3）?xA(x)??xB(x)??xA(x)??xB(x) （4）?xA(x)??xB(x)??xA(x)??xB(x) （5）?xA(x)??xB(x)??xA(x)??xB(x) （6）?xA(x)??xB(x)??xA(x)??xB(x) 解 略

2. 指出下面演绎推理中的错误，并给出正确的推导过程。 （1） ①?xP(x)?Q(x)

②P(y)?Q(y) ②P(a)?Q(b) ②P(a)?Q(a)

（2） ①?x(P(x)?Q(x))

（3） ①P(x)??xQ(x)

P规则

US规则：① P规则 US规则：①

P规则

ES规则：①

（4） ①P(a)?G(a)

（5） ①P(a)?G(b)

（6） ①P(y)?Q(y)

P规则 UG规则：① P规则 EG规则：① P规则 EG规则：①

②?x(P(x)?G(x))

②?x(P(x)?G(x))

②?x(P(c)?Q(x))

解 略

3. 指出下面演绎推理中的错误，并给出正确的推导过程。 （1）?x?y(x?y) （2）?y(z?y) （3）z?a （5）a?a

（4）?x(x?a)

P规则 US规则：（1） ES规则：（2） UG规则：（3） US规则：（4）

解 错误出现在步骤（3）。因为?y(z?y)中含有自由变元，所以不能使用ES规则得到

z?a。 正确的推导过程为：

（1）?x?y(x?y) （2）?y(z?y)

4. 指出下面演绎推理中的错误，并给出正确的推导过程。 （1）?x(P(x)?Q(x)) （2）P(y)?Q(y) （3）?xP(x) （4）P(y) （5）Q(y) （6）?xQ(x)

P规则 US规则：（1） P规则 ES规则：（3） T规则：（2），（4） EG规则：（5）

P规则 US规则：（1）

解 错误出现在步骤（4）。使用ES规则得到的P(y)中的y已经出现在前面的公式中，所以错误，正确的推导过程为：

（1）?x(P(x)?Q(x)) （2）P(y)?Q(y) （3）?xP(x) （4）P(a)

5. 用演绎法证明下列推理式

（1）?x(A(x)?B(x))??xA(x)??xB(x)

P规则 US规则：（1） P规则 ES规则：（3）