第3 章
一阶逻辑
3.1 内容提要
1.一阶逻辑基本概念 
个体词 个体常项、个体变项、个体域、有限个体域、全总个体域. 
谓词 谓词常项、谓词变项、1元谓词(表示事物的性质)、n(n≥2)元谓词(表示事物之
间的关系)、0元谓词、特性谓词. 
量词 全称量词、存在量词. 
命题符号化 设D 为个体域. 
(1)“D 中所有x 都有性质F”,符号化为
.xF(x) 
(2)“D 中存在x 具有性质F”,符号化为
.xF(x) 
(3)“对D 中所有x 而言,如果x 有性质F,则x 就有性质G”,符号化为
.x(F(x)→G(x)) 
(4)“D 中存在x 既具有性质F,又有性质G”,符号化为
.x(F(x)∧G(x)) 
(5)“对于D 中的所有x 和y 而言,若x 有性质F,y 有性质G,则x 与y 有关系H ”, 
符号化为
.x.y(F(x)∧G(y)→H (x,y)) 
(6)“对于D 中所有x 而言,若x 具有性质F,就存在y 有性质G,并且x 与y 有关系
H ”,符号化为
.x(F(x)→.y(G(y)∧H (x,y))) 
(7)“存在D 中的x 有性质F,并且对D 中所有y 而言,如果y 有性质G,则x 与y 就
有关系H ”,符号化为
.x(F(x)∧.y(G(y)→H (x,y))) 
(8)“D 中存在着x 与y,x 有性质F,y 有性质G,并且x 与y 有关系H ”,符号化为
.x.y(F(x)∧G(y)∧H (x,y)) 
一阶逻辑公式、解释与赋值、分类: 
一阶语言L 字母表、项、原子公式、合式公式(公式)、指导变元、量词的辖域、自由出现
的个体变项、约束出现的个体变项、闭式及性质、公式的解释与赋值、永真式(逻辑有效式)、

52
离散数学习题解答与学习指导(第4版) 

矛盾式(永假式)、可满足式、代换实例
. 

2. 
一阶逻辑等值演
算
一阶逻辑等值式与基本等值式
:
等值式
A 
.
B 
当且仅当A.
B 
为永真式
.
基本等值式
:
第一组命题逻辑重言式的代换实例
.
第二组一阶逻辑中的重要等值式
:
(1)量词否定等值式
:
①...xA(x)..x..A(x)
.
②...xA(x)..x..A(x)
.
(2)量词辖域收缩与扩张等值式,A(x)中
x 
是自由出现的,
B 
中不含
x 
的自由出现,则
有下面8个等值式
:
①.x(A(x)∨B)..xA(x)∨B.
②.x(A(x)∧B)..xA(x)∧B.
③.x(A(x)→B)..xA(x)→B.
④.x(B→A(x)).B→.xA(x)
⑤.x(A(x)∨B)..xA(x)∨B.(.) ⑥.x(A(x)∧B)..xA(x)∧B.
⑦.x(A(x)→B)..xA(x)→B.
⑧.x(B→A(x)).B→.xA(x)
.


(3)量词分配等值式
:
①.x(A(x)∧B(x))..xA(x)∧.xB(x)
.
②.x(A(x)∨B(x))..xA(x)∨.xB(x)
.
一阶逻辑等值演算的2个规则: 

(1)置换规则
. 
(2)换名规则
. 
一阶逻辑前束范式: 

(1)前束范式
. 
(2)与公式
A 
等值的前束范式(也称
A 
的前束范式)
(3)求给定公式
A 
的前束范式:利用重要的等值式置换规则、换名规则等,对给定公
式
A 
进行等值演算,直到求出与
A 
等值的前束范式. 、(.) 
当个体域为有限集
D 
={a1,a2,…,an 
}时,可以消去量词,将.xA 
(x)写成
A 
(a1)∧ 

A(a2)∧…∧A(),.xA(写成A(a2)∨…∨A()

an 
x) a1)∨A(an . 

3.习题
2 

3.设个体域为实数集R,F(x):x>5,求下列0元谓词的真值.
1 

(1)F(5)
. 
(2)F(2)
. 
(3)F(-2)
. 
(4)F(6)
. 


一阶逻辑

(6)F(9)
(52)F(72).
x|
7.
. 
令F(
.
3.设个体域D={
x 
为英语单词}, x):
x 
含字母c求下列各0元谓词的
真值
. 
(1)F(about)
. 
(2)F(cal)
. 
(3)F(eror)
. 
(4)F(erect)
. 

3.将下列命题用0元谓词符号化.
3 

(1)王小山来自山东省或河北省
. 
(2)除非李联不怕吃苦,否则她不会取得这样好的成绩
. 
(3)2不是有理数
.
(4)3大于2仅当3大于4.


设个体域为D={
x 
是人},L(y):
x 
喜欢y.将下列命题符号化.

3.4 
x|x,
(1)所有的人都喜欢赵小宝
. 
(2)所有的人都喜欢某些人
. 
(3)没有人喜欢所有的人
. 
(4)每个人都喜欢自己
. 
4中4个命题符号化.
3.5 
设个体域为全总个体域,又令
M 
(x):
x 
是人.将题3.
3.6 
在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为(a)和(b)条件时命题
的真值
. 
(1)凡整数都能被2整除
. 
(2)有的整数能被2整除
. 
其中,(a)个体域为整数集合,(b)个体域为实数集合
. 
3.设个体域为整数集Z,L(x,:x+y=y.
7 
y)x-求下列各式的真值
. 

(1)L(1,1)
. 
(2)L(2,0)
. 

(3).1,
. 
4).L(2)

yL(y)(xx,
.
(x,(x,


5).x.yL(y)
. 
6).x.yL(y)
.
(7).y.xx,
. 
(x.x,


L(y)8).yL(y)

3.8 
在一阶逻辑中将下面命题符号化,并分别讨论个体域为(a)和(b)条件时命题
的真值
. 限制(.) 
(1)对于任意的x,均有x2-2=(x+2)(x-2)
. 
(2)存在x,使得x+5=9. 
其中,(a)个体域为自然数集合,(b)个体域为实数集合
. 
3.9 
设个体域为整数集Z,确定下列各公式的真值
.
(1).x(x2>0)
. 
(2).x(x2=0)
.
(3).x(x2≥x)
. 
(4).x.y(x2<y)
.
(5).x.y(x<y2)
. 
(6).x.y(x+y=0)
.
2=

(7).x2+y. 
8).y.z=(.

x.y(6)(x.z(x+y)/2)

3.在一阶逻辑中将下列命题符号化.
10 

(1)没有不吃饭的人
. 
(2)在北京卖菜的人不全是东北人
. 
第
章

53

54
离散数学习题解答与学习指导(第4版) 

(3)自然数全是整数
. 
(4)有的人天天锻炼身体
. 
3.在一阶逻辑中将下列命题符号化.
11 

(1)火车都比汽车快
. 
(2)有的火车比有的汽车快
. 
(3)不存在比所有火车都快的汽车
. 
(4)说凡是汽车就比火车慢是不对的
. 
3.将下列命题符号化, 并指出各命题的真值.
12 
个体域为实数集合R,

(1)对所有的x,都存在y,使得
x 
· y=0. 
(2)存在着x,对所有的y,都有
x 
· y=0. 
(3)对所有x,都存在着y,使得y=x+1. 
(4)对所有的
x 
和y,都有
x 
· y=y· x. 
3.将下列各公式翻译成自然语言, 并判断各命题的真假.
13 
个体域为整数集Z,
(1).x.y.z(x-y=z)
. 
(2).x.y(
x 
· y=1)
.
(3).x.y.z(x+y=z)


3.指出下列公式中的变元、量词的辖域、各个体变项的自由出现和约束出现.
14 指导(.) 

(1).x(F(x)→G(x,y))
. 

(x,y)

2).xF(y)→.yG(x,
.
(F(x,z))x,z)


3).x.y(y)∧G(y,∨.xH 
(y,
. 

3.给定解释
I 
如下:
15 

(a)个体域DI 
为实数集R.
b)
..
(a=0. 

(f(y)x-x,

c)..x,=y,y∈DI.
(F(y):y,x,:x,


d)....y∈DI.

x,x=G(y)x<y,
说明下列公式在
I 
下的含义,并指出各公式的真值
.
(G(y)→..F(y)
)


1).x.y(x,x,
.
(y),y)
)


2).x.y(F(f(x,a)→G(x,
.
(3).y(x,f(y),
.


x.G(y)→..F(x,a)
)
(4).y(f(y),→F(y)
)


x.G(x,a)x,
. 

3.给定解释
I 
如下:
16 

(a)个体域D=N(
N 
为自然数集)
.
(b)
..
a=2.
(c)
D 
上函数x,=g(y)
x ·


....

f(y)x+y,x,=y.
(d)
D 
上谓词
x
..
)
x,
σ(
x=y.
z)


F(y)
:
及赋值σ:σ(=0,y)=1,σ(=2.
说明下列各式在
I 
及
σ 
下的含义,并讨论其真值
.
(a)
,


1).xF(g(x,y)
.
(2).F(x,y)→.f(a),
.


x(f(a),yF(y,x)
)
(3).y.F(x,z)


x.zf(y),
. 


一阶逻辑

(4).xF(f(y),x,.

x,g(z))

3.判断下列各式的类型.
17 

(1)F(y)G(y)x,.

x,→(x,→F(y)
)
(2).x(F(x)→F(x))→.y(G(y)
)


y)∧..G(
.
(3).x.yF(y)→.y.F(y)


x,xx,
.
(4).yF(y)→.xx,
.


x.x,y.F(y)
(5).x.F(y)→F(y,
.


y(x,x)
)
(6)..(.xF(x)→.yG(y)


y))∧.yG(
.
(7).xF(y)


x,
.
(8).xF(y)→.x,


x,yF(y)

3.(1)给出一个非闭式的式.永真(.) 
18 

(2)给出一个非闭式的永假式
. 
(3)给出一个非闭式的可满足式,但不是永真式
. 
3.证明下面公式既不是永真式,也不是矛盾式.
19 

(F(G(y)))

1).x(x)→.y(y)∧
H 
(x,
. 

(2).y(x)∧G(→
H 
(y))

x.F(y)x,
. 

3.将下列各式的否定号内移,使得否定号只能出现在谓词前.
20 

(1)...x.yL(y)

x,
.
(2)...yL(y)
.


x.x,
(3)...x(x)∧.y..L(x,
.


F(y)
)
4)...x(.yL(y)∨.x,
.
(
21 
x,yH 
(y))
使其没有既是约束出现的
,


3.将下列公式化成与之等值的公式, 又是自由出现的个
体变项
. 
(1).xF(x,x,z).

y)∧.yG(y,
(2).F(y)∧.yG(x,
.


x(x,y))

3.证明:
22 

A(x)).x(x)
)
(x)).x)
)


(1).x(x)→B(/.A(x)∧B(
.
2).x(A(x)∧B(/.x(A(x)→B(
.


3.23 
设个体域D={b}, 
其中,A(x)和B(x)为含
x 
自由出现的公式
. 
1).x.y(F(x)∧Ga(
,
. 
消去下列各公式中的量词
. 
(y))
(2).F(x,.

x.y(x)∧G(y)
)
(3).xF(x)∧.xG(x)
.
(4).x(x,yG(y))
.


F(y)∨.

3.设个体域D={b,消去下列各公式中的量词.
24 
a,c}
,
(1).xF(x)→.yG(
.


y)
(2).x(x,y))
.


F(y)→.yG(

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

第
章

55

56
离散数学习题解答与学习指导(第4版) 

(1).x(F(x)→G(x))
. 

(2).x(F(x)∧G(x))

3.给定公式A=.xF)→.x).(x(.) 
26 
xF(

(1)在解释I1 中, a}, 
个体域D1={证明公式
A 
在I1 下的真值为1. 

(2)在解释I2 中, a1,an 
n≥2,
为什么? 
个体域D2={a2,…,},
A 
在I2 下的真值还一定是1吗? 

3.给定解释
I 
如下:
27 

(a)个体域D={3,4}
.
(b)
f 
-(x)为
f 
-(3)=4,
f 
-(4)=3.
(F(y) F(3)F(4)0,3,=4,
=
c)..........

x,为3,=4,=F(4)F(3)1.
试求下列公式在
I 
下的真值
.
(1).x,
.


x.yF(y)
(2).x.yF(y)
.


x,
(3).x.F(y)f(x),y)))
.


y(x,→F(f(

3.28 
在一阶逻辑中将下面命题符号化,要求用两种不同的等值形式
. 
(1)没有小于负数的正数
. 
(2)相等的两个角未必都是对顶角
. 
3.求下列各式的前束范式.
29 

yG(y)
(F(y)→.x,z))
.


(1).xF(x)→.x,
. 

2).x(x,yG(y,

3.求下列各式的前束范式.
30 

x)∧G(→L(y)
x1(x1)x1,→(.x2)→.x2,


(1)F(x)x,
. 

(2).F(→G(x2))x2H 
(x3L(x3))
. 

(3).x1,→(x1)→...x1,.

x1F(x2)
H 
(x2G(x2))

3.31 
将下列命题符号化,要求符号化的公式为前束范式
. 
(1)有的汽车比有的火车跑得快
. 
(2)有的火车比所有的汽车跑得快
. 
(3)说所有的火车比所有汽车都跑得快是不对的
. 
(4)说有的飞机比有的汽车慢是不对的
. 
3.求下列各公式的前束范式.
32 

x)∨L(y)
(2)..(.xF(x)∨.xG(x))
.


(1).xF(x)∨.xG(x,
. 

3.习题解答与分析
3 

3.(1)~(4)的真值为0,(5)与(6)的真值为1.
1 

分析这里的1元谓词F(F(x):x>5,为谓词常项,所以(1)~(6)全为命题
. 

由于5,2,-2,6全都小于或等于5,所以(1)~(4)为假命题.而27 和7.
所以(5)与(6)均为真命题.
x∈R)
9均大于5, 


一阶逻辑

第

3.(1)与(3)的真值为0,(2)与(4)的真值为1.
2 

3 

分析这里的1元谓词F(F(x):
x 
含字母c)为谓词常项,所以(1)~(4)全为命题, 

章

其中,(1)与(3)中单词不含字母c,所以为假命题,而(2)与(4)中单词含字母c,所以为
真
命题
.


57
3.3 
(1)设F(:G(:a:王小山.
x)
x 
来自山东省,x)
x 
来自河北省,命题符号化为
(F(a))∨(..F(a)) 或F(a)

a)∧..G(a)∧G(a)∨G(

(2)设F(:
G(
G(:
a) F(
a:李联.
a) 
x)
x 
怕吃苦,x)
x 
取得好成绩,命题符号化为
a)→..F(或a)→..G(

(3)设F(x):
x 
是有理数,命题符号化为
y)命题符号化为
..F(2)

(4)设F(x,:x>y, 
F(3,2)→F(3,4) 
分析(1)中命题的真值要根据王小山来自哪个省而定.若他既不是来自山东省,
也
不是来自河北省,则命题为假.若他真来自山东省或河北省,则命题为真,但不可能既来
自
山东省又来自河北省,所以既可以符号化为排斥或,又可以符号化为相容或
.


对于(2)中命题,注意“李联取得好成绩”的必要条件是“李联不怕吃苦” 
. 
另外,还应注意,(1)与(2)的真值要根据具体情况而定.而(3)和(4)的真值是确定的,

(3)是真命题,而(4)是假命题
. 
3.设二元谓词L(y):
x 
喜欢y.
4 
x,

(1)设a:赵小宝,命题符号化为
.xx,
L(a)
(2).x.yL(y)


x,
.
(3)...yL(y)
.


x.x,
(4).xx,
.


L(x)
3.y)


5 
设
M 
(x):
x 
是人,L(x,:
x 
喜欢y.
(a)
)


1)设a:赵小宝..x(
M 
(x)→L(x,
.
(2).
M 
(
M 
(x,
.


x(x)→.y(y)∧L(y))
)
(3)...x(x)∧.y(y)→L(x,
.


M 
(
M 
(y))
)
(4).x(
M 
(x)→L(x,x))
.


分析题3.5说明:同一个命题在不同的个体域下,

4与题3.可有不同形式的符号
化
形式,当然,也可能有相同的符号化形式.设有命题“自然数都是整数”
,


①个体域D1=R(
R 
为实数集), 命题符号化为
.x(F(x)→G(x)) 
其中,F(x):
x 
为自然数,G(x):
x 
为整数
. 

②个体域D2=Q(
Q 
为有理数集), 命题符号化为
F(x)和G(x)的含义同①
. 
.x(F(x)→G(x)) 


58
离散数学习题解答与学习指导(第4版) 

③个体域D3=N(
N 
为自然数集), 命题符号化为
G(x)的含义同①
. 
.xG(x) 
D1,D2,D3 不同,命题“自然数都是整数”在D1 与D2 下,符号化形式相同,但在D3 下
的符号化形式与D1 与D2 下的符号化形式不同
. 

3.(a)个体域为整数集合:
6 

(1).xF(x).其中,F(x):
x 
能被2整除.真值为0.例如,3为整数,但2不能整除3. 
(2).xF(x)F(x)同(1).真值为1.所有的偶数都是整数,它们都能被2整除
. 
(b)个体域数集合:为实(.) 
(1).x(G(x)→F(x)).其中,G(x):
x 
为整数,F(x):
x 
能被2整除,其真值为0. 
(2).x(G(x)∧F(x)).其中,G(x)和F(x)同(1), 其真值为1. 
3.(1)、(3)、(4)和(8)的真值为0,而(2)、(5)、(6)和(7)的真值为1.
7 

分析(1)因为1+1≠1-1,所以L(1,1)为假
. 

(2)因为2+0=2-0,所以L(2,0)为真
. 
(3)对于除0以外的任何y,-所以,.yL(1,为假.
均有1+y≠1y, y)

(4)对于任意的x,都有x+2≠x-2,所以,.xL(x,2)为假
. 
(5)取y=0, =0, x.yL(y)为真.
均有x+0x-所以.x,

(6)取y=对于任何x, =0, x.yL(y)
0, 均有x+0x-故有.x,为真
. 

(7)取y=0,则.L(x,0)( 即.x(0)) 为真,故.y.L(x,为真.
x+0=x-xy)

(8)只要y≠0, x+y≠x-y,所以,.yL(y)为假.就有(x) 
x.x,

3.设F(:2x+2)(x-2),G(x):x+5=9.
(a)(1).xF(x), 其真值为0.
8 
x)x2-=(

(2).xG(x), 其真值为1.
(b)(1).xF(x), 其真值为1.
(2).xG(x), 其真值为1. 
分析本题说明,在不同个体域中,同一个命题的符号化形式可能相同,但真值可能
不同
. 

3.9 
(1)、(7)和(8)的真值为0;(2)~(6)的真值为1. 
分析(1)因为0∈Z,而02=0,所以.x(x2>0)为假命题
. 

(2)因为0∈Z,且02=0,所以.x(x2=0)为真命题
. 
(3).x∈Z,若x=0,则02=0;若x≠0,则x2>x,所以命题.x(x2≥x)为真命题
. 
(4)对于任意的x∈Z,取y=x2+1,则y∈Z,并且x2<y,所以.x.y(x2<y)为真
命题
. 
(5)取
x 
为负整数,如x=-1,则对于任意整数y,均有-1<y2,所以.x.y(x<y2)
为真命题
. 
(6)对于任意的x∈Z,若x=0,则取y=0;若x≠0,则取y=-x,均有x+y=0,所
以.x.y(x+y=0)为真命题
. 

一阶逻辑

第

(7)在整数集合Z中,不存在
x 
和y,使得x2+y2=6,所以.x.y(x2+y2=6)为假
3 

命题
. 

章

(8)当
x 
与
y 
一个为奇数,另一个为偶数时,(
x 
+y)/2不在
Z 
中,所以
.x.y.z(z=(x+y)/2)为假命题
. 
59
3.本题中没指定个体域, 并且要引入特性谓词.
10 
因而使用全总个体域,
(1)...x(F(x)∧..G(x))..x(F(x)→G(x))
. 
其中,F(x):
x 
是人,G(x):
x 
吃饭
. 
(2)...x(F(x)→G(x))..x(F(x)∧..G(x))
. 
其中,F(x):
x 
在北京卖菜,G(x):
x 
是东北人
. 
(3).x(F(x)→G(x))
. 
其中,F(x):
x 
是自然数,G(x):
x 
是整数
. 
(4).x(F(x)∧G(x))
. 
其中,F(x):
x 
是人,G(x):
x 
天天锻炼身体
. 

3.11 
本题中没指定个体域,因而使用全总个体域.设F(x):
x 
是火车,G(
车,L(y)
x 
比
y 
快,x,
x 
比
y 
慢.
y):
y 
是汽
x,:
H 
(y)
:
(1).F(x)→.G(→L(y)))
.


x(y(y)x,
(F(G(y))
)


2).x(x)∧.y(y)∧L(x,
. 

(3)...y(y)∧.F(→L(x)))

G(x(x)y,
.
(4)...y(G(y)→.x(F(x)→
H 
(x)))
.


y,

分析以上4个命题的符号化还有不同形式
. 
2节的等值式和置换规则

利用主教材3.
可进行如下演算
.


(1) .F(y(y)x,
x(x)→.G(→L(y))) 

x)G(→L(y))) 量词辖域收缩与扩张等值式)

..x.y(F(→(y)x,( 
y)) (

..x.y(..F(x)∨..G(y)∨L(x,蕴涵等值式) 
y(..(x)∧G((

..x.F(y))∨L(x,y)) 德摩根律) 
y(x)∧G(→L(y)) (蕴涵等值式) 
通过以上演算可知,
.x(F(x)→.y(y)→L(x,G(y))) 
y(x)∧G(→L(y)) 
因而,(1)中命题常符号化为
..x.F(y)x,
.x.y(F(x)∧G(y)→L(x,

..x.F(y)x,
y)
)
x(x)∧.y(y)∧L(y))
)


(2) .F(G(xy,
)) 量词辖域收缩与扩张等值式)
..x.y(F(x)∧G(y)∧L(x,(
(3) ...y(y)∧.F(→L(x))) 
G(x(x)y,

..y(..G(xF(
(
x→
)
L(
yx,
))) 量词否定等值式
)
y)∨...F(→L(x))) ( 德摩根律
)
..y..(G(y)∧.x(x)y,( 
y)∨.F(→L(x))) ( 

..y(..G(x..(x)y,量词否定等值式) 

60
离散数学习题解答与学习指导(第4版) 

..y(..G(y)∨.x..(..F(x)∨L(y,x)))( 蕴涵等值式)
..y(..G(y)∨.x(F(x)∧..L(y,x))) ( 德摩根律)
..y(G(y)→.x(F(x)∧..L(y,x))) (蕴涵等值式)
由以上演算可知,(3)中命题符号化为
F(→L(x))
)
...y(G(y)∧.x(x)y,


或

G(x(x)∧..L(x))) 

都可以.请将后一种形式翻译成自然语言
.
(G(x(F(x)→
H 
(x))
)
4) ...y(y)→.y,
x))) (量词否定等值式
)


.y(y)→.F(y,

..y..(G(x(x)y,
y)→.F(→
H 
(

..y..(..G(x(..F(y,蕴涵等值式)y)∨.x)∨Hy(
,
x)))( 
德摩根律)
..y(G(y)∧...x(..F(x)∨
H 
(x))) ( 
..y(G(y)∧.x..(..F(x)∨
H 
(y,x))) ( 量词否定等值式) 
y)∧.F(y,
(
由以上演算可知,(4)中命题可符号化
为
...y(y)→.F(→
H 
(x))
)


..y(G(x(x)∧..
H 
(x))) 德摩根律) 
G(x(x)y,

或

.y(G(x(x)∧..
H 
(y,x))) 

y)∧.F(
请将后一种形式翻译成自然语言
.


3.(1).x· y=0), 真值为1.
12 
x.y(

(2).x.y(
x 
· y=0), 真值为1. 
(3).x.y(x+1), 真值为1.
y=

(4).x.y(
x 
· y=y· x), 真值为1. 
分析因为本题中给定的
x 
与
y 
的关系比较简单,因而没有引入2元谓词符号.若引
入2元谓词符号也可以.如设
F 
(x,y):
x 
· 
y 
=0,
G 
(x,y):
y 
=
x 
+1,
H 
(x,y): 
x 
· y=y· x.则有

(1).x,.

x.yF(y)
(x,


2).x.yF(y)
. 

(3).x.yG(y)

x,
.
(4).x.x,
.


yH 
(y)

3.13 
(1)“ 对于任意的整数
x 
和y,都存在着整数z,使得x-y=z”是真命题
. 
(2)“ 对于任意的整数x,都存在着整数y,使得
x 
· y=1”是假命题
. 
(3)“ 存在着整数x,对于任意的整数
y 
和z,都有x+y=
z 
”是假命题
. 
分析①用反例说明(2)是假命题.取x=5,在Z中不存在y,使得
x 
· y=1. 

②对于命题(3), 不可能存在固定的x0,使得对于任意的
y 
和z,都有x0+y=z,
x 
应
y=z=z=
随着
y 
和
z 
的变化而变化.例如,7,10 时,
x 
应为3;当y=2,9时,
x 
应为7,所
以(3)为假命题.若将(3)变为.y.z.x(x+y=z), 则得到一个真命题.此例说明,量词的
顺序不能随便颠倒
. 


一阶逻辑

3.14 
(1)在公式.x(F(x)→G(y)) 中,.
x 
中的
x 
为指导变元.
x,量词.的辖域A= 
(y)), 在
A 
中
x 
都是约束出现的,而
y 
是自由出现的.F(x)→G(x,
x,x,中,..的

(2)在公式.xF(y)→.yG(y) 
x 
中的
x 
和.
y 
中的
y 
都是指导变元.
辖域为F(x,其中
x 
是约束出现的,.的辖域为G(y), 
x 
是自由出现的
y,
), 而
y 
是自由出现的.x,其中,
y 
是约束出现的
. 

(3)在公式.x.y(F(x,y)∧G(y,z))∨.xH 
(x,y,z)中,.
x 
中的x,.
y 
中的y, 
.
x 
中的
x 
都是指导变元..
y 
中.的辖域为(
F 
(x,y)∧
G 
(y,z)),.
x 
中.的辖域为
.y(F(y)∧G(z)), 其中
x 
和
y 
是约束出现的,而
z 
是自由出现的..
x 
中.的辖域
x,y,
为
H 
(x,z),
y 
和
z 
是自由出现的.在整个公式中,
x 
约束出现两次,y

y,
x 
是约束出现的,
约束出现两次,自由出现一次,

z 
自由出现两次
. 

3.(1)“ 对于任意的实数
x 
和y,若x<y,则x≠y”是真命题.
15 

(2)“ 对于任意的实数
x 
和y,若x-y=0,则x<y”是假命题
. 
(3)“ 对于任意的实数
x 
和y,若x<y,则x-y≠0真命题.是(”) 
(4)“ 对于任意的实数
x 
和y,若x-y<0,则x=y”是假命题
. 
3.16 
(1)“ 对于任意的自然数x,均有
=
x×2=1假命题.
y+2=是(”) 
(2)“ 对于任意的自然数x,如果x+21,则对于任意的自然数y,
x 
”是真命题
. 
(3)“ 对于任意的自然数
x 
和y,都存在着自然数z,使得x+y=
z 
”是真命题
. 
(4)“ 存在自然数x,使得x+1=2x 
”是真命题
. 
3.(1)和(4)为永真式(逻辑有效式),(2)和(6)为永假式(矛盾式),(3)、(5)、(7)和
17 

(8)为非永真式的可满足式
. 
分析在一阶逻辑中, 由定义3.
A 
为永

判断给定公式的类型不是一件易事
. 
8可知,
真式当且仅当
A 
无成假解释和赋值,
A 
为矛盾式当且仅当
A 
无成真解释和赋值.
A 
为非
永真式的可满足式当且仅当
A 
存在成真的解释和赋值并且存在成假的解释和赋值.由于
公式的复杂性,解释的多样性,判断一阶逻辑公式的类型是不可判定的
. 

由于本题给出的8个公式的特殊性,还是可以判断其类型的.下面逐个进行分析
. 

(1)设(1)中公式为A. 
方法
1 
等值演算法
:
A=F(y)G(y)x,


x,→(x,→F(y)) 

y)∨(..G(y)∨F(y))( 
x,x,y)( 交换律、结合律) 

...F(x,x,x,蕴涵等值式) 
.(..F(y)∨F(y))∨..G(x,
(排中律)
.1∨..G(x,
.1 
y)
(零律) 
方法
2 
重言式的代换实例: 
注意到p→(为命题逻辑中的重言式, 由定理3.
知,
A 
为永真式.
q→p) 而公式
A 
为它的代换实例,2可

(2)设(2)中公式为B. 
x)∨F(G(
y)
)
B=.x(F(x)→F(x))→.y(G(y)∧..G(
..x(..F(x))→.y(y)∧..G(y)) 
第
章

61

62
离散数学习题解答与学习指导(第4版) 

由以上等值式可知,对于任意的解释I,
B 
的前件均为真,而
B 
的后件均为假,于是
B 
为矛
盾式
. 

下面论证
C 
既有成真的解释,又有成假的解释
. 
设解释I1 为:个体域为整数集Z,F(y)x<y. C 
的前件.x,
为真
(
,3
但
) 
C 
设
的后件
(3)中公式为
.y.xFC(
.
x,y)为假,所以
xI,
1 为
:
C 
的成假解释
在I1 下
. 
,x.yF(y) 
F(x,x+y=x.

设解释I2 为:个体域仍为Z,y):在I2 下,
C 
的前件与后件均为真,故
I2 为
C 
的成真解释
. 
综上所述,
C 
不是永真式,也不是矛盾式,它是非永真式的可满足式
. 

(4)设(4)中公式为D.
论证
D 
无成假的解释
.
设
I 
为任意的解释
.
若在
I 
下,
D 
的前件.x,为假,则在
I 
下
D 
为真.

① x.yF(y)
②若在
I 
下,
D 
的前件.
x 
.yF 
(x,y)为真,必存在x0∈DI 
(
I 
的定义域), 使得
.yF(y) 又由于对于任意
y 
∈DI 
,x0,x,
x0,为真.
F 
(y)为真,有.xF 
(y)为真,从而
.y.xF(y)为真.

x,
由
I 
的任意性可知,
D 
是永真式
.


(5)设(5)中公式为E. 
x,:y. E 
为真
.
设解释I1 为:个体域为整数集合Z,F(y)x=在I1 下
,
设解释I2 为:个体域仍为Z,F(y):x<y. 
若F(y) 则F(x)
x,在I2 下, x,为真, y,为
假,所以在I2 下
E 
为假
. 
综上所述,
E 
是非永真式的可满足式
. 

(6)设(6)中公式为F,可通过等值演算证明
F 
为矛盾式
.
F 
=..(.xF(x)→.yG(y)
y))∧.yG(

...(...xF(x)∨.yG(y))∧.yG(y)( 蕴涵等值式)
..xF(y)∧.yG((德摩根律)
x)∧...yG(y) 

x)∧(...yG(y)) ( 结合律)

..xF(y)∧.yG(
..xF(x)∧0 (矛盾律)
.0 (零律
)
实际上,
F 
是矛盾式..(p→q)∧
q 
的代换实例
.
(7)设(7)中公式为G. 
取解释I1:个体域N,y):y;赋值σ(在I1 和
σ 
下,
G 
为“存在自然数
x,0. 
是真命题.
F(x,x=y)=0. 

x=这(”) 取解释I2,把I1 中x=
y 
改为x<y.在I2 和
σ 
下,
G 
为“存在自然数x,x<0. 
”这是假
命题
. 
故
G 
是非永真式的可满足式
. 

(8)设(8)中公式为H. 
y)x≤y;=y)=0.
取解释I1:个体域N,F(x,:赋值σ∶σ(x)σ(在I1 和
σ 
下,
H 
为
“存在自然数x≤0 蕴涵所有的自然数y≥0. 
”这是真命题
. 


一阶逻辑

第

取解释I2,把I1 中x≤
y 
改为x=y.在I2 和
σ 
下,
G 
为“存在自然数x=0蕴涵所有的

3

自然数y=0. 
”这是假命题
. 

章

故
H 
是非永真式的可满足式
.
说明(2)~(5)都是闭式,只需考虑解释,而用不着赋值
.


63
(x,xF(y),G(y,x,z)等都是非闭式,它们都
是永真式
. 
(2)F(
y)x,
x,y) 它们都是矛盾式
. 

3.18 
1).xF(y)→.x,x,z)∨..G(y,
x)∧..F(x),.xF(y)∧.x..F(x,等都是非闭式
,
(3)F(x,→G(y)是非闭式,它是可满足式,但不是永真式
.


分析注意(2)中后一个公式: 
x,x..F(y)
.xF(y)∧.x,
x,x,


..xF(y)∧...xF(y) 
3.一个公式
A 
不是永真式当且仅当
A 
存在着成假的解释和赋值,
A 
不是矛盾式当
19 

且仅当
A 
存在着成真的解释和赋值.这两个公式都闭式,只需要考虑解释
. 

(1)设(1)中公式为A. 
①设解释I1 为:个体域为非0自然数集N+,
F 
(x):
x 
为偶数,
G 
(y):
y 
为奇数, 
H 
(x,x|y(
x 
整除y).在解释I1 下,
A 
为假命题,所以
A 
不是永真式.y):
F(
x 
为有理数,y):
y 
为分数,x,

②设解释I2 为:个体域为实数集R,x):G(
H 
(y): 
x=y.在I2 下
A 
为真命题,所以
A 
不是矛盾式
. 
综上所述,
A 
为可满足式,但不是永真式
. 

(2)设(2)中公式为B. 
x)
x 
为马,:
y 
为骡,x,
①设解释I1 为:全总个体域,F(:G(y)
H 
(y):
x 
与
y 
跑得同
样快.在I1 下,
B 
为假命题,所以
B 
不是永真式
. 
②设解释I2 为:全总个体域,F(x):
x 
为飞机,G(y):
y 
为轮船,
H 
(x,y):
x 
比
y 
快.在I2 下
B 
为真命题,所以
B 
不是矛盾式
. 
综上所述,
B 
是可满足式,但不是永真式
. 

3.解本题时应该应用量词否定等值式.
20 

x.yL(y)

(1) ...x,
x,

..x...yL(y)
..x.x,
y..L(y)

(2) ...yL(y)
x.x,

yL(y)

..x...x,
x,

..x.y..L(y)
F(y)) 

(3) ...x(x)∧.y..L(x,
F(y..L(y)) 

..x..(x)∧.x,
..x(..F(y..L(y)) 
x)∨...x,

y)) 
最后一步也用上了双重否定律
. 

..x(..F(x)∨.yL(x,
(量词否定等值式)
(量词否定等值式) 

(量词否定等值式)
(量词否定等值式) 

(量词否定等值式)
(德摩根律)
(量词否定等值式) 


64
离散数学习题解答与学习指导(第4版) 

(x,yH 
(y)) 

4) ...x(.yL(y)∨.x,

x,yH 
(y)) 量词否定等值式)

..x..(.yL(y)∨.x,( 
x,yH 
(y)) ( 

..x(...yL(y)∧...x,德摩根律)
..x(.x,x,量词否定等值式)
y..L(y)∧.y..
H 
(y)) ( 

3.解本题时,使用换名规则.
21 

(1) .x,x,z)
xF(y)∧.yG(y,

..uu,vx,z)(换名规则)
F(y)∧.G(v,
(F(y)∧.y)
)


2) .x(x,yG(x,
F(y)∧.u)) 
(


..x(x,G(x,换名规则)
3.证明本题, 用具体的谓词代替A(和B(x), 使其对应的两要找(u) 
22 
只需到解释I, x)
个命题不等值即可
.


(1)取解释I1:个体域为全总个体域,取
A 
(x):
x 
为人,
B 
(x):
x 
呼吸.此时,
“.x(A(x)→B(x))”翻译成自然语言为“人都呼吸”,这是真命题.而“.x(A(x)∧B(x))” 
翻译成自然语言应为“宇宙中的一切事物都是人并且呼吸”,这显然是假命题.这说明公式
(.x(A(x)→B(x)).(.x(Ax)∧B(x))) 存在着成假的解释,因而
.x(A(x)→B(/.x(A(x)∧B(

x)).x)) 

(2)取解释I2:个体域为自然数集合N,
A 
(x):
x 
为奇数,
B 
(x):
x 
为偶数,此时,
“.x(A(x)∧B(x))”翻译成自然语言为“存在自然数
x 
既是奇数,又是偶数”,这是假命
题.而“.x(A(x)→B(x))”翻译成自然语言为“存在自然数x,如果
x 
是奇数,则
x 
是偶
数”,这是真命题(例如A(0)→B(0),A(2)→B(2)等均为真), 这说明.x(A(x)∧B(x)). 
.x(A(x)→B(x)) 存在成假解释,因而
x(A(x)).x(x)

x)∧B(/.A(x)) 

分析(1)本题说明
.
“x))”与“
→B(
x))不(”) 等值.命题“人

.x(A(x)→B(.x(A(x)∧B(
都吃饭”“偶数都能被2整除”“兔子跑得快”等都是全称量词加蕴涵语句,都应符号化为
“.x(A(x)→B(x))的(”) 形式,而不能符号化为“.x(A(x)∧B(x))的(”) 形式
. 

(2)本题说明“.x(A(x)∧B(x))”与“.x(A(x)→B(x))等值.命题“有的人吸
烟”“存在偶素数”“有百岁老人”等都应符号化为“.x(A(x)∧B(x))”的形式,而不应该
符号化为“.x(A(x)→B(x))”的形式
. 不(”) 
3.解本题需要注意的是,若量词的辖域能收缩就收缩,使演算的步骤尽量少.
23 

(1) .x.y(F(x)∧G(y)) 
..xF(y) 量词辖域收缩与扩张等值式)
x)∧.yG(
(
消去量词,得
(F(b))∧(a)∨G(
a)∧F(G(b)
)


(2) .x.y(F(x,
x)∧G(y)) 

y))( 量词辖域收缩与扩张等值式
)
先消去.x,得
(y))∧(y)
)
F(b,
再消去.y,得
F(a)∧.yG(a,b)∧.yG(
(F(G(a)∨G(b)))∧(b)∧(b,b,


..x(F(x)∧.yG(x,
a)∧(a,a,F(G(a)∨G(b))) 


a)∧F(G(a)∨G(b))∧(G(a)∨G(b)) 

.F(b)∧(a,a,b,b,
(3) .xF(x)∧.xG(x)可写
成
(b))∧(b)
)
F(a)∨F(G(

a)∧G(

(4) .x(F(x,yG(y)) 
x,
y)∧.
y)( 量词辖域收缩与扩张等值式)
..xF(y)∧.yG(
可写成

(F(a,y)∨F(y))∧(G(b)) 

b,a)∧G(

一阶逻辑

第
章

65
分析(1)若不将量词辖域收缩,则演算过程要长些,特别是,当个体域中元素较多时
过程会更长
. 
y)) 先消去.写成

.x.y(F(x)∧G(x,
.y(F(y))∧.y(b)∧G(y)
)


a)∧G(F(
再消去.y,得
a)∧G(F(b)))∧((b)∧G(F(b))) ((F(a))∨(a)∧G(F(a))∨(b)∧G(

.(F(G(b)))∧(b)∧(a)∨G(
a)∧(a)∨G(F(G(b))) 

.(F(b))∧(a)∨G(
a)∧F(G(b)) 

这里没有使用量词辖域收缩与扩张等值式,显然演算过程就长多了.所以,若能应用
量词辖域收缩与扩张等值式就应该先用它,然后再消量词.但如果量词辖域不能缩小,那
就只好直接演算了
. 

(2)演算到.x(F(x)∧.yG(x,y)) 后,.的辖域不能再缩小了.演算也可以如下
进行: 
.x.y(x)∧G(y)) 

F(x,

F(x,
先消去.y,得
F(G(a)∨G(b))) .x(x)∧(x,x,
再消去.x,得
(F(G(a)∨G(b)))∧(b)∧(b,b,a)∧(a,a,F(G(a)∨G(b))) 

..x(x)∧.yG(y)) 
.F(b)∧(a,a,G(a)∨G(b)) 
a)∧F(G(a)∨G(b))∧(b,b,

(3).xF(x)∧.xG(x)的辖域已经不能再缩小了,所以对它消量词最简单,但有人
先将它化成前束范式后再消量词,那是自找麻烦
. 
(4)注意F(x,中的
y 
在公式中是自由出现的, 它依然自由出现.
y) 消量词之后, 

3.(1)本题量词辖域已不能再缩小,因而直接消量词.
24 

.xF(yG(可写成

x)→.y)
(F(b)∧F(→(a)∧G(c)) 
Fa(
)∧
yF)
(c))G(b)∧G(
因而.的辖域可

(2)注意,x,中的
y 
在公式中是自由出现的,.yG(y)中不含x, 
以缩小
. 
.x(x,y)) 

F(y)→.yG(

x,y)( 量词辖域收缩与扩张等值式) 
可写成

..xF(y)→.yG(

66
离散数学习题解答与学习指导(第4版) 

(F(y)∨F(y)∨F(y))G(b)∨G(

a,b,c,→(a)∨G(c)) 

3.25 
解此题,先消去量词比较方便
. 
(1).x(F(x)→G(x)) 可写
成
(F(1)→G(1))∧(F(2)→G(2)
)
(2).x(F(x)∧G(x)) 可写成
(F(1)∧G(1))∨(F(2)∧G(2)) 
取I1:个体域D={1,2},F(x):x≥1,G(x):x≤2,在I1 下,F(1),F(2),G(1), 
G(2)均为真,所以,(1)与(2)中公式在I1 下全真
. 
取I2:个体域D={1,2},F(1)=1,F(2)=0,G(1)=0,G(2)=1,在I2 下,(1)与(2)中
公式全为假
. 

(1)在I1 下, F(x)可写成F(→F(a)
公式A=.F(a)a)∨F(

3.26 
xx)→.xa)...F(
.1,所以,在I1 下公式
A 
为真
. 
(2)在I2 下,
A 
不一定为真
. 
在D2 中消去量词,得
(F(a2)∨…∨F())F(a2)∧…∧F()) 

a1)∨F(an 
→(a1)∧F(an 

当F(a1),a2),…,)中至少有1个为真,但不全为真时,蕴涵式的前件为真,后件为
假,所以蕴涵式为假.a1),a2),…,
n 
) 
A 
为真
. 

F(F(
n 

当F((a) F(F(全为真时,

3.在本题中,由于个体域
D 
中只含2 元素,因而可以消去量词,进行演算.个(a) 
27 

(1) .x.y..x,先消去.x,写成
F(y)
..
..


3,F(y)
再消去.y,得
F(3,F(3,F(4,F(4,
(..3)∨..4))∧(..3)∨..4)
)


.yF(y)∧.y4,

.(0∨1)∧(1∨0).
1
(..先消去.写
成
2) .x.yF(x,y) x,
..
..


3,F(y)
再消去.y,得
..3)∧....3)∧
..
(F(3,F(3,4))∨(F(4,F(4,4)
)


.yF(y)∨.y4,

.(0∧1)∨(1∧0).
0
-(-
(
(..→..x),y))) 先消去.写
成
-(-(-(-
(


3) .x.F(y)F(fx,

y(x,
f 

..→..3),y)))∧...→..4),y))) 

F(y)y(F(f

.y(3,F(ff 
F(4,y)
f
再消去.y,得
(F(3,3)F(3),3)))∧(F(3,4)F(3),4)))∧(F(4,3)
..→..-(-(..→..-(-(
..


ff 
ff 
F(4),3)))∧(F(4,4)F(4),4))) 

→..-(-(..→..-(-(
ff 
ff 

..→..4))∧(..→..3))∧(..

.(F(3,3)F(4,F(3,4)F(4,F(4,3) 
→....→..
F(3,4))∧(F(4,4)F(3,3)) 

.(0→0)∧(1→1)∧(1→1)∧(0→0)
.1∧1∧1∧1.1 

一阶逻辑

第

3.本题中没有指定个体域,因而使用全总个体域.
28 

3

(1)设F(:
x 
为正数,y):
y 
为负数,
H 
(y):
x)G(x,x<y. 

章

y)∧
H 
(y)
)
F(x)∧G(x,


①...x.y(F(x)∧G(x,
. 

②.x.y(y)→..
H 
(y))
. 

67
(2)设F(x):
x 
为角,
H 
(y):x=L(y):
x 
与
y 
为对顶角.
x,y,x,

y(x)∧F(x,→L(y))
②.x.y(x)∧F(x,x,

①...x.F(y)∧
H 
(y)x,
. 

F(y)∧
H 
(y)∧..L(y))
. 
分析证明两种不同形式的符号化形式是等值的
. 

(1) ...F(y)∧
H 
(x,y)) 
x.y(x)∧G(

y)) 
y..((x)∧G(

..x.y..(F(x)∧G(y)∧
H 
(x,
..x.F(y))∧
H 
(x,y)) 
y(..(x)∧G(
..x.F(y))∨..
H 
(x,y)) 
x)∧G(y)) 
由以上的证明可知,①.②
. 
其实,由②开始演算也可以
. 
.x.y(F(x)∧G(y)→..
H 
(x,y)) 

..x.y(F(y)→..
H 
(x,
..x.y(..(F(x)∧G(y))∨..
H 
(x,y)) 
y..(x)∧G(
..x.F(y)∧
H 
(x,y)) 
F(y)∧
H 
(y)) 

..x...y(x)∧G(x,
y)∧
H 
(y)) 

....x.y(F(x)∧G(x,
(2) ...y(x)∧F(x,→L(y)) 
x.F(y)∧
H 
(y)x,

F(y)∧
H 
(y)x,

..x.y..(x)∧F(x,→L(y)) 
(量词否定等值式)
(结合律)
(德摩根律)
(蕴涵等值式) 

(蕴涵等值式)
(德摩根律)
(量词否定等值式)
(量词否定等值式) 

(量词否定等值式)

..x.y..(..(F(x)∧F(x,y))∨L(y)) ( 蕴涵等值式)
y)∧
H 
(x,

F(y)∧
H 
(y)∧..L(y)) (德摩根律) 
由以上演算可知①.②
. 
从②开始演算也可以
. 
.x.y(F(y)∧
H 
(x,y)) 

..x.y(x)∧F(x,x,
x)∧F(y)∧..L(x,

x,y))( 

..x.y(....(F(x)∧F(y)∧
H 
(y))∧..L(x,双重否定律) 
y))∨L(y)) ( 

..x.y..(..(F(x)∧F(y)∧
H 
(x,x,德摩根律)
..x.y..(y)∧
H 
(y)y)) (蕴涵等值式)
F(x)∧F(x,→L(x,

y(x)∧F(→L(y)) (量词否定等值式)

....x.F(y)∧
H 
(x,y)x,
3.(1) .xF(yG(x,y)

29 
x)→
.
F(x,


..uu)→.yG(y) 
u(F(y)) 

..u)→.yG(x,
u)x,
(F(y)→.z)) 

..u.y(F(→G(y)) 
2) .x(x,yG(x,y,

..x(x,ux,z)) 
F(y)→.G(u,

u(x,→G(u,

..x.F(y)x,z)) 
(换名规则)
(量词辖域收缩与扩张等值式)
(量词辖域收缩与扩张等值式) 

(换名规则)
(量词辖域收缩与扩张等值式) 


离散数学习题解答与学习指导(第4版) 

68
3.30 
(1)F(x)∧G(x)→L(x,y)已为前束范式
. 
(2) .x1(F(x1)→G(x1,x2))→(.x2H 
(x2)→.x3L(x2,x3)) 
..x4(F(x4)→G(x4,x2))→(.x5H 
(x5)→.x3L(x2,x3)) 
x3)) 

..x4(F(x4)→G(x4,x2))→.x5(
H 
(x5)→.x3L(x2,
F(→G(x2))→.
H 
(→L(x3)) 
x4((x3))) 

..x4(x4)x4,x5.x3(x5)x2,
..F(x4)→G(x4,x2))→.x5.x3(
H 
(x5)→L(x2,
F(→G(x2))→.
H 
(→L(x3))) 

..x4.x5((x4)x4,x3(x5)x2,
x3((x2))x3))) 

在以上演算中,第一步使用换名规则,将指导变元x1 及其2个约束出现替换成x4,将
指导变元x2 及紧随其后的一个约束出现替换成x5;在第二步和第三步将蕴涵式的后件用
量词辖域收缩与扩张等值式化成前束范式;第四步~第六步将整个公式化成了前束范式
. 
在演算中注意正确地使用量词辖域收缩与扩张等值式
. 

..x4.x5.F(x4)→G(x4,→(
H 
(x5)→L(x2,
(3) .x1F(x1,x2)→(
H 
(x1)→...x2G(x1,x2)) 
..x3F(x3,x2)→(
H 
(x1)→...x4G(x1,x4)) ( 换名规则) 
→(
H 
(x4)) ( 量词否定等值式)
..x3F(x3,x2)x1)→.x4..G(x1,
..x3F(x2)→.
H 
(x1,
x3,x4(x1)→..G(x4)) 

x3,x4(

..x3(F(x2)→.
H 
(x1)→..G(x1,x4))) 
x4(x3,→(x1)→..G(x4))) 

..x3.F(x2)
H 
(x1,
3.本题没指定个体域,因而使用全总个体域.
31 

(1)设F(:G(
H 
(y)
x 
比
y 
跑得快,
x)
x 
是汽车,y):
y 
是火车
G,
(
x,:
y))) 
则
.x(F(x)∧.y(y)∧
H 
(x,

F(y)∧
H 
(y)) 
最后一步用量词辖域收缩与扩张等值式及结合律,所得公式为前束范式
. 

..x.y(x)∧G(x,
(2)设F(:G(
H 
(y)
x 
比
y 
跑得快,
x)
x 
是火车,y):
y 
是汽车,x,:则
.x(x)∧.G(→
H 
(y))) 

F(y(y)x,

y(x)∧(y)x,
最后一步所得公式为前束范式
. 

..x.F(G(→
H 
(y))) 
(3)设F(:G(
H 
(y)
x 
比
y 
跑得快,
x)
x 
是火车,y):
y 
是汽车,x,:则
..(.x(x)→.G(→
H 
(y)))) 

F(y(y)x,

x)G(→
H 
(y)))) 

...(.x.y(F(→(y)x,
y))) 

..x.y..(..F(x)∨(..G(y)∨
H 
(x,
x)∧G(y)) 
最后一步得公式所前束范式
. 

..x.y(F(y)∧..
H 
(x,
(4)设F(:G(
H 
(y)
x 
比
y 
慢,
x)
x 
是飞机,y):
y 
是汽车,x,:
y))) 
则
...x(F(x)∧.y(G(y)∧
H 
(x,

G(x,
y..(x)∧G(

....x.y(F(x)∧(y)∧
H 
(y))) 
..x.F(y)∧
H 
(x,y)) 
F(x)∧G(y)) 
y(x)∧G(

..x.y(..(y))∨..
H 
(x,
..x.F(y)→..
H 
(x,y)) 

最后一步所得公式为前束范式
. 

3.(1)可用两种方法求(1)中公式的前束范式.
32 

方法
1 
利用存在量词.对∨适合分配律
.
.xF(x)∨.G(x,


xx)∨L(y) 

x(F(x))∨L(x,

..x)∨G(y)
F(z))∨L(y)( 

..z(z)∨G(x,换名规则)
F(z)∨L(y)) ( 量词辖域收缩与扩张等值式)
方法
2 
不用.对∨的分配律
. 
.xF(x)∨.G(x,

..z(z)∨G(x,
xx)∨L(y)

F(uu)∨L(y)( 换名规则)

..zz)∨.G(x,
u(z)∨G(x,量词辖域收缩与扩张等值式)

..z.F(u)∨L(y))( 
(2) ..(.xF(x)∨.xG(x)) 
F(y)) (换名规则) 
y(x)∨G(

...(.xx)∨.yG(
....x.F(y)) (量词辖域收缩与扩张等值式)
..x.y..(F(x)∨G(y)) (量词否定等值式) 
y)) (德摩根律)
最后两步所得公式都是前束范式.注意,.对∨无分配律
. 

..x.y(..F(x)∧..G(
一阶逻辑

第
章

69