(完整版)离散数学题目及答案
挂牌仪式-磐安之窗
数理逻辑习题
判断题
1．任何命题公式存在惟一的特异析取范式
（
√
）
2． 公式
p(pq)
是永真式 （
√
）
3．命题公式
(pq)p
是永真式 （
√
）
4．命题公式
pqr
的成真赋值为010 （
×
）
5．
xA(x)Bx(A(x)B)
（ √ ）
6．命题“如果1＋2＝3，则雪是黑的”是真命题 （
×
）
7．
p(pq)p
（ √ ）
8．
x(F(x)G(x))
是永真式 （
×
）
9．“我正在撒谎”是命题 （
×
）
10．
xF(x)xG(x)
是永真式（ √ ）
11．命题“如果1＋2＝0，则雪是黑的”是假命题 （
×
）
12．
p(pq)p
（ √ ）
13．
x(F(x)G(x))
是永假式 （
×
）
14．每个命题公式都有唯一的特异（主）合取范式 （ √ ）
15．若
p:雪是黑色的
，则
公式pq
是永真式 （ √ ）
16．每个逻辑公式都有唯一的前束范式 （
×
）
17．
公式pq
的特异（主）析取式为
pq
（
×
）
18．命题公式
p(qr)
的成假赋值是110
（ √ ）
19．一阶逻辑公式
x(F(x)G(x,y))
是闭式（
×
）
单项选择题
1． 下述不是命题的是（ A ）
A． 花儿真美啊! B．
明天是阴天。
C． 2是偶数。 D．
铅球是方的。
2．谓词公式（
y）（
x）（P（x）→R（x
,y））∧
yQ（x,y）中变元y （ B ）
A．
是自由变元但不是约束变元
C． 既是自由变元又是约束变元
B． 是约束变元但不是自由变元
D． 既不是自由变元又不是约束变元
3．下列命题公式为重言式的是（ A ）
A．p→ （p∨q）
C．q∧┐q
4． 下列语句中不是命题的只有（ A ）
．．
A．花儿为什么这样红？
C．飞碟来自地球外的星球。
B．2+2=0
D．凡石头都可练成金。
B．（p∨┐p）→q
D．p→┐q
5．在公式
(x)(y)(P(x,y)Q(z))(y)
P(y,z)
中变元y是（ B ）
A．自由变元
B．约束变元
C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元
6．下列命题公式为重言式的是（ A ）
A．p→ （p∨q）
C．q∧┐q
7．给定如下4个语句:
（1）我不会唱歌。
（2）如果天不下雨,我就上街。
（3）我每天都要上课。
（4）火星上有人吗?
其中不是复合命题的是（ B ）
A．（1）（4）
B．（3）（4）
C．（1）（3）
D．（1）（3）（4）
8．下列含有命题p，q，r的公式中，是特异（主）析取范式的是 （
D ）
A．（p q r） （p q） B．（p q
r） （p q）
B．（p∨┐p）→q
D．q→┐p
C．（p q r） （p q r） D．（p q r）
（p q r）
9．设个体域为整数集,则下列公式中值为真的是（ A ）。
A． （
y）（
x）（x·y=2）
B．（
x）（
y）（x·y=2）
C．
（
x）（x－y=x） D．（
x）（
y）（x+y=2y）
10． 下述不是命题的是（ D ）
A． 花儿是红色的 B．
月亮上有水
C． 3是偶数 D．
x3
11． 用
P
表示：天下大雨；
Q
表示：
他乘公共汽车上班。将“如果天下大雨，他就乘公共
汽车上班。”符号化正确的是（ A ）
A．
P
Q
B．
Q
P
C．
P
Q
D．
P
Q
12．谓词公式（
y）（
x）（P（x）→R（x,y））∧<
br>
xQ（x,y）中变元y （ C ）
A． 是自由变元但不是约束变元
C． 既是自由变元又是约束变元
B．
是约束变元但不是自由变元
D． 既不是自由变元又不是约束变元
13．下列命题公式为永假式的是（ C ）
A．p→ （p∨q）
B．p∧q→q
C．q∧┐q
14．下列语句中，不是命题的是（ C ）
A． 铅球不是球。
B． 要是他不上场，我们就不会输。
C．
刘翔跨110米栏用了不到13秒钟，你说他是不是运动健将呢?
D．
刘翔跨110米栏用了不到13秒钟，他是一个真正的运动健将。
13．关于命题变元P和Q的成假赋值为01对应的极大项是（ C ）
A．┐P∧Q
B．┐P∨Q C．P∨┐Q D．P∧┐Q
D．p→q
14．谓词公式（<
br>
y）（
x）（P（x）→R（x,y））∧
yQ（x,
y）中变元y （ B ）
A． 是自由变元但不是约束变元
C．
既是自由变元又是约束变元
B． 是约束变元但不是自由变元
D．
既不是自由变元又不是约束变元
15． 设
p:
开关A开，
q
：开
关B开,则“开且只开A、B中一个开关”的命题公式是（ C ）
A．
pq
B．
pq
C． （
pq
）
（
pq
）
D． （
pq
）
（
pq
）
16．下列等价式正确的是（ C ）
A．┐
(x)A(x)
┐A
B．
(x)(y)A(x)(y)A
C．┐
(x)A(x)
┐A
D．
(x)(A(x)B(x))(x)A(x)(x)B(x)
17
．在论域D={a,b}中与公式（
x
）A（x）等价的不含存在量词的公式是（ B ）
A．
A(a)A(b)
C．
A(a)A(b)
B．
A(a)A(b)
D．
A(b)A(a)
18．下列命题公式为重言式的是（ C ）
A．p→ （p∧q）
C．p∨┐p
B．（p∨┐p）→q
D．p→┐q
19．下列命题中真值为1的是（ B ）
A．若2+2=4,
则3+36 B．若2+2=4, 则3+3=6
C．2+2=4,
当且仅当3+36 D．2+24, 当且仅当3+3=6
20．设个体域为整数，下列公式中真值为1的是（ B ）
A． xy（x + y
= 1） B． xy（x + y = 1）
C． xy（x
+ y = 1） D． xy（x + y = 1
21．
下列命题中真值为0的是（ C ）
A．若2+2=5, 则3+36
B．若2+2=4, 则3+3=6
C．2+2=5, 当且仅当3+36
D．2+24, 当且仅当3+3=6
22．谓词公式
x(M(x)y(E(y)
L(x,y))
中变元
x
（ C ）
A．
是自由变元但不是约束变元
C． 既是自由变元又是约束变元
B． 是约束变元但不是自由变元
D． 既不是自由变元又不是约束变元
23．设个体域为整数，下列公式中真值为1的是（ B ）
A． xy（x +
y = 1） B．xy（x + y = 1）
C．
xy（x + y = 1） D． xy（x + y = 1
填空题
1．
n
个命题变元的极小项有 2
n
个。
2．设
p:220,q:3
是奇数，则
pq
的真值是
1 。
3．含n个命题变项的重言式的特异（主）合取范式为 1
4．设个体域为整数集合Z，命题
xy(xy3
）的真值为 1
5．公式
xP（x）
xQ（x）的前束范式为
x(P(x) Q(x))
6．设p：我很累，q：我去学习，命题：“我很累，但我还去学习”的符号化为
pq
7．设P表示：天下大雨；Q表示：他乘公共汽车上班，则命题“如果天下大
雨，他就乘公共
汽车上班。”的符号化是
pq
8．设P：2+2＝4，Q：3是奇数,则命题“2+2＝4，当且仅当3是奇数．”的符号化为
PQ
9．
含n个命题变项的矛盾式的特异（主）析取范式为
0
10．命题公式
pq
成假的解释是 01,10
11．
pq
的成假解释为 01,10
计算题
1．求
xF(x)xG(x)
的前束范式。
解：
xF
x
xG
x
xF
x
xG
x
3分
x
F
x
G
x
3分
2．求
(pq)r
的真值表，并写出它的特异（主）析取范式和特异（主）合取范式。
解：真值表如下：
故主析取范式为
pqr
pqr
pqr
pqr
pqr<
br>
主合取范式为
pqr
<
br>pqr
pqr
3．求命题公式的
((pq)r)p
成真赋值。
解：
pq
r
p
pq
r
p
=
=
pq
rp
=
pq
r
p
=
pr
qr
p
成真赋值 100，010，101，110，111
4．将公式
(xP(x)yR(y))xF(x)
化为前束范式。
解：
xP
x
yR
y
xF
x
xy
P
x
R
y
xF
x
x
yP
x
R
y
zF
z
xyzP
x
R
y
F
z
5．求公式 （p∨（q∧r））→（p∧q∧r）
的特异（主）析取范式，并求成真赋值。
解：
p
qr
pqr
p
qr
pqr
p
qr
pqr<
br>
pq
p
r
pqr
pq
r
pqr
p
qr
pqr
成真赋值为：000，001，010，111
6．用谓词公式表示“有人喜欢吃所有的食物”。
解：
M
x
:x
是人，
N
y
:y
是食物
H
x,y
:x
喜欢吃
y
符号化：
x
M
x
y
N
y
H
x,y
7．
用作真值表方法确定下列命题公式的类型：
((pq)(qp))(pq).
解： 设原式=A，真值表如下：
pq(pq)(qp)pq
0
0
1
10
1
0
1
1
0
0
1
1
10
1
A
1
1
1
1
则原式为永真式。
8．用逻辑式表示“某些计算机与某些外部设备之间不能相联”。
解：
C
x
：
x
是计算机，
D
x
：
x
为外部设备，
P
x,y
：
x
与
y
相联
符号化为
xy(C(x)D(y)P(x,y))
9．在个体域
D{a,b}
，消去公式
x(F(x)yG
(y))
的量词。
解：原式＝
(F(a)yG(y))(F(b)yG(y))
＝
(F(a)(G(a)G(b)))(F(a)(G(a)G(b)))
＝
(F(a)F(b))(G(a)G(b))
10．
给定一阶逻辑公式
xP(x,y)yQ(y)
，求该公式的前束范式。
解：原式
xP
x,y
zQ
z
xzP
x,y
Q
z
11．用逻辑式表示“某些计算机与某些外部设备之间能相联”。
解：
C
x
：
x
是计算机，
D
x
：
x
为外部设备，
P
x,y
：
x
与
y
相联
符号化为
xy(C(x)D(y)P(x,y))
12．用等值演算求命题公式┐（p∨q）∧（q→r）的特异（主）析取范式，
并判断该公式的
类型。
解：原式
pq<
br>
qr
pqq
pqr
pq
pqr
pqr
pqr
公式类型为非永真的可满足式。
13．设一阶逻辑公式
Gx(yP(x,y)(zQ(z)R(x)))，试将G化成与其等价的
前束范式。
解：
Gx(yP(x,y)(zQ(z)R(x)))
＝
xy(P(x,y)z(Q(z)R(x)))
＝
xyz(P(x,y)(Q(z)R(x)))
14． 设公式G的真值表如下，试求出G的特异（主）析取范式和特异（主）合取范式。
p q r
0
0 0
0 0
1
0 1 0
0
1 1
1 0
0
1 0 1
1
1 0
1 1
1
解：
主析取范式
(pqr)(pqr)(pqr)(pqr)
主析取范式
(pqr)(pqr)(pqr)(pqr)
G
1
0
1
1
0
1
0
0
15．求公式
xF(x)yG(x,y)
的前束范式。
解：原式＝
xF(x)yG(z,y)
＝
xy(F(x)G(z,y))
证明题
1．
用等值演算证明等值式
(pr)(qr)(pq)r
。
证明：
2．设
P,Q,R
是三个命题，构造下列推理证明：
前提：
PQ,QR,P
结论：
R
证明：
左边(pvr)(qr)(pq)r
(pq)r(pq)
r右边
1
2
3<
br>
4
5
P
P
Q
Q
QR
R
前提引入
前提引入
1
2
析取三段论
前提引入
4分
<
br>
4分
3
4
假言推理<
br>3．证明下列推断
前提：
p(qs)
，
q
，
rp
结论：
rs
证明：（1）
r
附加前提引入
（2）
pr
前提引入
（3）
p
(1)（2）拒取
（4）
p
qs
前提引入
（5）
qs
(3)(4)假言推理
（6）
q
前提引入
（7）
s
(5)(6) 假言推理
4．
用构造证明法证明下列推理：
前提：
pq,(qr)r,(ps)
结论：
s
证明：
1
2
s
否定结论引入
ps
前提引入
3
ps
2
置换
4
p
1
3
析取三段论
5
pr
r
前提引入
6
pr
5
简化
7
r
5
简化
8
r
4
6
析取三段论
9
rr
7
8
合取
5．证明：
p(qr)(pr)q
。
证明：左边
p
qr
p
rq
pr
q
pr
q
pr
q
＝右边
6．证明公式G＝（（P→Q） ∧（Q→P）∧P）
→P是永真式。
证明：
G((PQ)(QP)P)P
＝
((PQ)P)P
＝
((PP)(PQ))P
＝
(PQ)P
＝
PQP
＝
1Q
＝1
G为永真式