习题十五
1、设下面所有谓词的论域D={a、b、c}。试将下面命题中的量词消除，写成与之等值的命题公式。 分析：本题主要是考察对全称量词、存在量词的理解，然后通过合取词、析取词把全称量词和存在量词消去。 （1）xRxSx
解：R(a)R(b)R(c)S(a)S(b)S(c) （2）xPxQ(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）xPQ(x))R(e)
其中，P:"3＞2",Q(x):"x3",R(x):"x＞5",e:5， 论域D={-2，3，6} 解：假。
（x为-2时不成立） （2）xP(x)Q(x)
其中，P(x):"x＞3",Q(x):"x4"， 论域D={2}。 解：真。
3、在一阶逻辑中，将下列命题符号化：
分析：本题主要是考察存在量词、全称量词已经基本的连接词的运用。 （1）凡有理数均可表示为分数。
解：令：P(x)： x是有理数；Q（x）:x可表示为分数。
x(P(x)Q(x))
（2）有些实数是有理数。 解：P（x）：:x是实数,
Q(x)：x是有理数。
xPxQ(x)
（3）并非所有实数都是有理数。 解：P（x）：:x是实数,
Q(x)：x是有理数。
x(P(x)Q(x))
（4）如果明天天气好，有一些学生将去公园。
解：P（x）: x去公园
S（x）: x是学生
W：明天天气好
Wx(P(x)S(x))
（5）对任意的正实数，都存在大于该实数的实数。 解：P（x）: x是实数；
G（x, y）：:x大于y。
x(P(x)y(P(y)G(y,x))) （6）对任意给＞0，x0a,b，都在存在N，使当n＞N时，有
fx0fnx解：G（x，y）: x＞y, Sx:xa,b
＜
x0G,0Sx0Nn(Gn,NG(,f(x0)fn(x))))
4、指出下列公式中的自由变元和约束变元，并指出各量词的作用域。
分析：本题主要是考察自由边缘、约束变元的定义，以及量词的作用域的概念。 （1）xPxQxxRxQz
解；自由变元z, 约束变元x, 第一个x的作用域是PxQx，第二个是R(x)。
（2）x(P(x)y(Q(y))(xP(x)Q(z))
中的Px 解：自由变元z，约束为元：x，y。第一个x的作用域为PxyQy
第二个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）xy(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）xyP(x,y)
解：真
（2）xyP(x,y)
解：假
（3）xy(P(x,y)P(y,x)) 解：真 （4）xP(x,x)
解：真
7．判断下列公式的恒真性和恒假性
分析：本题主要是根据已知的命题公式、合式公式的基本等值式来进行推导，看该合式公式是与1等值还是与0等值。
（1）xF(x)xF(x)
解：恒真 （2）xF(x)(xyG(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)H7(xG(x))HxG(x)H
证明（2）
x(G(x)H)x(7G(x)H)x7G(x)H7(xG(x))HxG(x)H
9．设G（x，y）是任意一个含x，y自由出现的谓词公式，证明： （1）xyG(x，y)yxG(x，y)
分析：本题主要是根据两个合式公式等值的定义进行证明。 证：设D是论域，I是G（x，y）的一个解释。
（a）若xyG(x，y)在I下的为真，则在I下，对任意的x,yD,G(x,y)即yxG(x,y)是真命题，反之亦然。
（b）若xyG(x,y)在I下为假，则在I下必存在x0D或y0D，使得G（x0, y）或G（x, y0）为假，于是，此xo或yo亦弄假yxG(x,y)， 反之亦然。
（2）xyG(x，y)yxG(x，y)
分析：本题主要是根据两个合式公式等值的定义进行证明。
证：设D是论域，I是G（x, y）的一个解释。
（a）若xyG(x，y)在I下为真，则在I下存在x0D与y0D,使G（x0,y0）为真命题，于是，yxG(x,y)也是真命题， 反之亦然。
（b）若xyG(x，y)在I下为假，则对任意x，yD，G（x, y）均为假，故yxG(x,y)亦为假，反之亦然。
10．将下列公式化成等价的前束范式：
分析：本题主要是根据已知的基本等值式通过消去蕴含连接词、等价连接词，依据改名规则、代替规则进行等值演算化成前束范式。
（1）xF(x)xG(x)
解：xF(x)xG(x)xF(x)xG(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)xz(7F(x,y)G(z))xH(x,y) xz(F(x,y)7G(z))uH(u,y) xzu((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))xy(7P(x)Q(x,y))
11．给出下面公式的skolem范式：
分析：本题主要是根据已知的基本等值式通过消去蕴含连接词、等价连接词，依据改名规则、代替规则进行等值演算化成前束范式，然后根据前束范式写出对应的skolem范式。
（1）7(xP(x)yzQ(y,z)) 解：
7(xP(x)yzQ(y,z))(xP(x)yzQ(y,z)xyz(P(x)Q(y,z))
∴所求为:xz(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)(yz(E(y),g(x)E(z),g(x)E(y,z))))
x(7E(x,o)7(yz(E(y)g(x))E(y,g(x)E(y,z))) )x(7E(x,o)(u7(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))
xu(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(7xP(x)yP(y)7(x7P(x)yP(y)
7(xy(7P(x)P(y)))xy(P(x)7P(y)) 即为所求。
12．假设xyM(x，y)是公式G的前束范式，其中M（x, y）是仅仅包含变量x，y的母式，设f是不出现在M（x, y）中的函数符号。证明：G恒真当且仅当xyM(x,f(x))恒真。
分析：本题主要是用反证法，根据解释的定义来证明结论成立。
证：设GxyM(x，y)恒真。若xM(x,f(x))不真，则存在一个解释I, 使得对任意的x0D（论域），M(x0,f(x0))为假。于是，G在I下也为假。此为矛盾。
反之，设xM(x,f(x))恒真。若xyM(x，y)不是恒真，则存在一个解释I’，使得对任意xiD，存在yiD，使M(xi，yi)为假。由于f是不出现在M(x，y)中的函数符号，故可定义函数f:使得f(xi)yi。于是，xM(x,f(x))在I’下为假。矛盾。
故结论成立。 13．证明
DD，(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） （4）(x)(Q(x)R(x))
化简（1）
（5）Q(y)R(y)
US规则，根据（4）
（6）P(y)R(y)
假言三段论，根据（3），（5） （7）(x)(P(x)R(x))
ES规则，根据（6）
14．构造下面推理的证明：
分析：本题是根据基本的等值式、蕴含式、以及US、UG、ES、EG规则证明结论成立。 前提：x(F(x)H(x)),x(G(x)H(x)) 结论：xG(x)7F(x)
证：（1）x(F(x)H(x))
前提引入
（2）x(7F(x)7H(x))
等价式（1） （3）x(H(x)7F(x))
等值式（2） （4）H(y)7F(y)
US规则（3） （5）x(G(x))H(x)
前提引入 （6）G(y)H(y)
US规则（5） （7）G(y)F(y)
假言三段论（4），（6）
（8）x(G(x)7F(x))
UG规则（7）
15．指出下面两个推理的错误。
分析：本题主要是考察US、UG、ES、EG规则的适用范围，也就是前提条件。 （1）x(F(x)G(x))
前提引入
（2）F(y)G(y)
US规则，根据（1） （3）xF(x)
前提引入
（4）F（y）
ES, (3) （5）G（y）
假言推理，（2），（4） （6）xGx
UG, (5）
解：（4）错误。Fy中的变元y与（2）中的变元重名。
（1）xyx，y
前提引入 （2）yF(z,y)
US规则，（1） （3）F(z,c)
ES规则，（2） （4）xFx,c
UG，（3） （5）yxF(x,y)
EG，（4） 解：（3）错误。在yF(z,y)中变元并非只有y。
16.每个学术会的成员都是知识分子并且是专家，有些成员是青年人。证明：有的成员是青年专家。 分析：本题主要是首先把明天符号化，符号化前提，结论。然后根据US、UG、ES、EG规则证明结论成立。
解：P（x）：x是学术会的成员；
E（x）：x是专家；
G（x）：x是知识分子；
Y（x）：x是青年人。
前提：x(P(x)G(x)E(x)),
(x)(P(x)Y(x)) 结论：x(P(x)Y(x)E(x))
证明：（1）x(P(x)G(x)E(x)))
前提引入
（2）P(c)(G(x)E(c))
US, (1)
（3）x(P(x)Y(x))
前提引入 （4）P(c)Y(c)
ES,（3） （5）P（c）
化简（4）
（6）G(c)E(c)
假言推理,（2），（5） （7）E（c）
化简,（6）
（8）Y(c)
化简,（4）
（9）P(c)Y(c)E(c)
合取（5）（7）（8） （10）x(P(x)Y(x)E(x))
EG
