（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）