习题六
1、设下面所有谓词的论域D={a、b、c}。试将下面命题中的量词消除，写成与之等值的命题公式。 分析：本题主要是考察对全称量词、存在量词的理解，然后通过合取词、析取词把全称量词和存在量词消去。 （1）?xR?x???S?x?
解：?R(a)?R(b)?R(c)???S(a)?S(b)?S(c)? （2）?x?P?x??Q(x)?
解：?P(a)?Q(a))??P(b)?Q(b)???P(c)?Q(c)? （3）?x7P(x)??xP(x)
解：?7P(a)?7P(b)?7P(c))??P(a)?P(b)?P(c)? 2、指出下列命题的真值：
分析：本题主要是考察合式公式的解释的定义，已经判定给定解释下合式公式的真值。 （1）?x?P?Q(x))?R(e)
其中，P:\3＞2\,Q(x):\x?3\,R(x):\x＞5\,e:5， 论域D={-2，3，6} 解：假。 （x为-2时不成立） （2）?x?P(x)?Q(x)?
其中，P(x):\x＞3\,Q(x):\x?4\， 论域D={2}。 解：真。
3、在一阶逻辑中，将下列命题符号化：
分析：本题主要是考察存在量词、全称量词已经基本的连接词的运用。 （1）凡有理数均可表示为分数。
解：令：P(x)： x是有理数；Q（x）:x可表示为分数。
?x(P(x)?Q(x))
（2）有些实数是有理数。 解：P（x）：:x是实数, Q(x)：x是有理数。
?x?P?x??Q(x)?
（3）并非所有实数都是有理数。 解：P（x）：:x是实数, Q(x)：x是有理数。
??x(P(x)?Q(x))
（4）如果明天天气好，有一些学生将去公园。
解：P（x）: x去公园 S（x）: x是学生 W：明天天气好
W??x(P(x)?S(x))
（5）对任意的正实数，都存在大于该实数的实数。 解：P（x）: x是实数； G（x, y）：:x大于y。
?x(P(x)??y(P(y)?G(y,x))) （6）对任意给?＞0，x0??a,b?，都在存在N，使当n＞N时，有
f?x0??fn?x?解：G（x，y）: x＞y, S?x?:x??a,b?
＜?
???x0?G??,0??S?x0???N?n(G?n,N??G(?,f(x0)?fn(x))))
4、指出下列公式中的自由变元和约束变元，并指出各量词的作用域。
分析：本题主要是考察自由边缘、约束变元的定义，以及量词的作用域的概念。 （1）?x?P?x??Q?x????xR?x??Q?z?
解；自由变元z, 约束变元x, 第一个?x的作用域是?P?x??Q?x??，第二个是R(x)。 （2）?x(P(x)??y(Q(y))?(?xP(x)?Q(z))
中的P?x? 解：自由变元z，约束为元：x，y。第一个?x的作用域为P?x???yQ?y??
?
第二个?x的作用域为第二个P(x)； ?y的作用域为Q(y)。 （3）?x(P(x)?Q(x))??yR(y)?s(z)
解：自由变元：z，约束变元：x和y；
?x的作用域为(P(x)?Q(x))， ?y的作用域为R(y)
（4）?x(F(x)??yH(x,y))
解：无自由变元 约束变元x，y；
?x的作用域：(F(x)??yH(x，y))，?y的作用域：H(x,y)
（5）?xF(x)?G(x,y)
解：自由变元：y与G(x，y)中的x，约束变元：F(x)中的x； ?x的作用域：F(x)
（6）?x?y(R(x,y)?Q(x,z))??xH(x,y)
解：自由变元：Z与H(x，y)中的y； 约束变元：x,y,
?x和?y的作用范围：?(R(x,y)?Q(x,z)?，?x的作用范围：H(x,y)
5．设谓词公式?x(P(x,y)?Q(x,z))。判定以下改名是否正确 ：
分析：本题主要是考察改名规则的定义，以及它的适用范围。有兴趣的同学可以顺便了解一下代替规则情形。
（1）?u(P(u,y)?Q(x,z)) 解：错误 （2）?u(P(u,y)?Q(u,z)) 解：正确 （3）?x(P(u,y)?Q(u,z)) 解：错误 （4）?u(P(x,y)?Q(x,z)) 解：错误 （5）?y(P(y,y)?Q(y,z)) 解：错误 6．设I是如下一个解释 ：
D:??a，b? ，P(a，a):?1 ，P(a,b):?0， P(b,a):?0，P(b,b):?1。
试确定下列公式在I下的真值：
分析：本题主要考察合式公式在特定解释下的真值。 （1）?x?yP(x,y) 解：真
（2）?x?yP(x,y) 解：假
（3）?x?y(P(x,y)?P(y,x)) 解：真 （4）?xP(x,x)
解：真
7．判断下列公式的恒真性和恒假性
分析：本题主要是根据已知的命题公式、合式公式的基本等值式来进行推导，看该合式公式是与1等值还是与0等值。
（1）?xF(x)??xF(x) 解：恒真 （2）?xF(x)?(?x?yG(x,y)??xF(x)) 解：恒真 （3）?xF(x)?(?x(F(x)??yG(y)) 解：恒真 （4）?(F(x,y)?F(x,y)) 解：恒假
8．设G（x）是恰含自由变元x的谓词公式，H是不含变元x的谓词公式，证明： （1）?x(G(x)?H)??xG(x)?H （2）?x(G(x)?H)??xG(x)?H 分析：本题根据量词作用域的扩张进行证明。 证明（1）
?x(G(x)?H)??x(7G(x)?H)??x7G(x)?H?7(?xG(x))?H??xG(x)?H
证明（2）
?x(G(x)?H)??x(7G(x)?H)??x7G(x)?H?7(?xG(x))?H??xG(x)?H
9．设G（x，y）是任意一个含x，y自由出现的谓词公式，证明： （1）?x?yG(x，y)??y?xG(x，y)
分析：本题主要是根据两个合式公式等值的定义进行证明。 证：设D是论域，I是G（x，y）的一个解释。
（a）若?x?yG(x，y)在I下的为真，则在I下，对任意的x,y?D,G(x,y)即?y?xG(x,y)是真命题，反之亦然。
（b）若?x?yG(x,y)在I下为假，则在I下必存在x0?D或y0?D，使得G（x0, y）或G（x, y0）为假，于是，此xo或yo亦弄假?y?xG(x,y)， 反之亦然。
（2）?x?yG(x，y)??y?xG(x，y)
分析：本题主要是根据两个合式公式等值的定义进行证明。
证：设D是论域，I是G（x, y）的一个解释。
（a）若?x?yG(x，y)在I下为真，则在I下存在x0?D与y0?D,使G（x0,y0）为真命题，于是，
?y?xG(x,y)也是真命题， 反之亦然。
（b）若?x?yG(x，y)在I下为假，则对任意x，y?D，G（x, y）均为假，故?y?xG(x,y)亦为假，反之亦然。
10．将下列公式化成等价的前束范式：
分析：本题主要是根据已知的基本等值式通过消去蕴含连接词、等价连接词，依据改名规则、代替规则进行等值演算化成前束范式。
（1）?xF(x)???xG(x)
解：?xF(x)???xG(x)??xF(x)??x?G(x)??x(F(x)??G(x)) （2） ?xF(x)??xG(x) 解：
?xF(x)??xG(x)???xF(x)??xG(x)??x(7F(x))??xG(x)??x(7F(x)?G(x)) （3）(?xF(x,y)??yG(y))??xH(x,y)
解：
(?xF(x,y)??yG(y))??xH(x,y)?(7(?xF(x,y))??yG(y))??xH(x,y) ?(?x(7F(x,y))??zG(z))??xH(x,y)??x?z(7F(x,y)?G(z))??xH(x,y) ??x?z(F(x,y)?7G(z))??uH(u,y) ??x?z?u((F(x,y)?G(z))?H(u,y))
（4）?x(P(x)??yQ(x,y))
解：?x(P(x)??yQ(x,y))??x(7P(x)??yQ(x,y))??x?y(7P(x)?Q(x,y))
11．给出下面公式的skolem范式：
分析：本题主要是根据已知的基本等值式通过消去蕴含连接词、等价连接词，依据改名规则、代替规则进行等值演算化成前束范式，然后根据前束范式写出对应的skolem范式。
（1）7(?xP(x)??y?zQ(y,z)) 解：
7(?xP(x)??y?zQ(y,z))?(?xP(x)??y?zQ(y,z)??x?y?z(P(x)?Q(y,z))
∴所求为:?x?z(P(x)?Q(f(x),z))
（2）?x(7E(x,o)?(?y(E(y,g(x))??zE(z,g(x))?E(y,z)))))
解:
原式??x(7E(x,o)?(?y?z(E(y),g(x)?E(z),g(x)?E(y,z)))) ??x(7E(x,o)?7(?y?z(E(y)g(x))?E(y,g(x)?E(y,z))) )??x(7E(x,o)?(?u??7(E(y),g(x))?E(?,g(x)?E(y,z))))
??x(7E(x,o)??u??((7(E(u),g(x)))?(7E(?1g(x)))?E(y,z))
??x?u??(E(x,o)?((7E(u,g(x)))?(7E(?,g(x)))?E(y,z))
即为所求
（3）7(?xP(x)??yP(y))
解：7(?xP(x)??yP(y))?7(7?xP(x)??yP(y)?7(?x7P(x)??yP(y) ?7(?x?y(7P(x)?P(y)))??x?y(P(x)?7P(y)) 即为所求。
12．假设?x?yM(x，y)是公式G的前束范式，其中M（x, y）是仅仅包含变量x，y的母式，设f是不出现在M（x, y）中的函数符号。证明：G恒真当且仅当?x?yM(x,f(x))恒真。
分析：本题主要是用反证法，根据解释的定义来证明结论成立。
证：设G??x?yM(x，y)恒真。若?xM(x,f(x))不真，则存在一个解释I, 使得对任意的x0?D（论域），M(x0,f(x0))为假。于是，G在I下也为假。此为矛盾。
反之，设?xM(x,f(x))恒真。若?x?yM(x，y)不是恒真，则存在一个解释I’，使得对任意xi?D，存在yi?D，使M(xi，yi)为假。由于f是不出现在M(x，y)中的函数符号，故可定义函数f:使得f(xi)?yi。于是，?xM(x,f(x))在I’下为假。矛盾。
故结论成立。 13．证明
D?D，
(?x)(P(x)?Q(x))?(?x)(Q(x)?R(x))?(?x)(P(x)?R(x))
分析：本题是根据基本的等值式、蕴含式、以及US、UG、ES、EG规则证明结论成立。 证：（1）(?x)(P(x)?Q(x))?(?x)(Q(x)?R(x))前提引入
(2)(?x)(P(x)?Q(x)) 化简（1）
（3）P(y)?Q(y) US规则，根据（2）
习题6
