第1页 / 共86页
第2页 / 共86页
第3页 / 共86页
第4页 / 共86页
第5页 / 共86页
第6页 / 共86页
第7页 / 共86页
第8页 / 共86页
离散数学习题集(十五套).doc
一、填空 20% （每小题2分）
二、选择 20% （每小题 2分）
三、证明 26%
四、逻辑推演 16%
五、计算 18%
试卷二试题与答案
一、填空 20% （每小题2分）
二、选择 20% （每小题2分）
三、证明 46%
四、计算 14%
一、填空 20% （每空 2分）
二、选择 20% （每小题 2分）
三、用CP规则证明 16% （每小题 8分）
四、（14%）
五、（10%）
六、（20%）
一、填空 10% （每小题 2分）
二、选择 25% （每小题 2.5分）
三、逻辑判断30%
四、计算10%
五、谓词逻辑推理 15%
六、证明：（10%）
试卷五试题与答案
一、填空15%（每空3分）
二、选择15%（每小题3分）
三、证明 48%
四、计算22%
一、填空（15%）每空3 分
二、选择（15%）每小题3分
三、证明（48%）
四、计算（22%）
一、填空 15% （每小题 3分）
二、选择 15% （每小题 3分）
三、证明 50%
四、10%
五、10%
一、填空 15%（每小题3分）
一、填空 15% （每小题 3分）
二、选择 15% （每小题 3分）
三、证明 34%
四、中国邮递员问题13%
五、根树的应用 13%
六、10%
一、填空 15% （每小题 3分）
二、选择 15% （每小题 3分）
三、证明 45%
四、生成树及应用 10%
五、5%
一、填空 30% （每空 3分）
二、选择 20% （每小题 2分）
三、简答题 15%
四、逻辑推理 10%
五、10%
六、证明 15%
一、填空 10% （每小题 2分）
二、选择 30% （每小题 3分）
三、逻辑判断 28%
四、计算 12%
五、逻辑推理20%
一、填空 20% （每小题 2分）
二、选择 20% （每小题 2分）
三、命题演绎28%
四、8%
五、8%
六、证明16%
五、填空 20% （每空 2分）
六、选择 20% （每小题 2分）
三、8%
四、证明42%
五、布尔表达式 10%
七、填空 10% （每小题 2分）
八、选择 10% （每小题 2分）
三、判断10% （每小题 2分）
四、证明 38%
五、应用 32%
九、填空 10% （每小题 2分）
十、选择 20% （每小题 2分）
十一、判断 10% （每小题 2分）
四、证明 46%
五、布尔表达式 8%
六、图的应用 16%
十二、填空 20% （每空 2分）
十三、选择 15% （每小题 3分）
三、 15%
四、15%
五、计算 15%
六、证明 20%
离散数学试题与答案试卷一
一、填空 20% （每小题 2 分）
1．设
A
(|{
x
Nx
)
且
(
x
)},5
B
|{
Exx
且
x
}7
（N：自然数集，E+ 正偶
数） 则
BA
。
2．A，B，C 表示三个集合，文图中阴影部分的集合表达式为
。
A
3．设 P，Q 的真值为 0，R，S 的真值为 1，则
QP
R
P
)))
(
R
(
(
(
S
)
的真值=
C
B
。
4．公式
(
RP
)
(
RS
)
P
的主合取范式为
5．若解释 I 的论域 D 仅包含一个元素，则
。
xP
)(
x
xP
)(
x
。
在 I 下真值为
6．设 A={1，2，3，4}，A 上关系图为
则 R2 =
。
7．设 A={a，b，c，d}，其上偏序关系 R 的哈斯图为
则 R=
8．图
9．设 A={a，b，c，d} ，A 上二元运算如下：
的补图为
。
。
*
a
b
c
d
a
a
b
c
b
b
c
d
c
c
d
a
a
b
d
，有逆元的元素为
。
d
d
a
b
c
，它们的
那么代数系统的幺元是
逆元分别为
10．下图所示的偏序集中，是格的为
。
二、选择 20% （每小题 2 分）
1、下列是真命题的有（
）
}{
a
}}
{{
a
A．
；
}
{{
},
C．
2、下列集合中相等的有（
；
{{
{,{
}}
}}
；
B．
}{
{{
}}
。
D．
）
A．{4，3} ；B．{ ，3，4}；C．{4， ，3，3}；D． {3，4}。
3、设 A={1，2，3}，则 A 上的二元关系有（ ）个。
A． 23 ； B． 32 ； C．
332
； D．
223
。
4、设 R，S 是集合 A 上的关系，则下列说法正确的是（
）
A．若 R，S 是自反的， 则 SR 是自反的；
B．若 R，S 是反自反的， 则 SR 是反自反的；
C．若 R，S 是对称的， 则 SR 是对称的；
D．若 R，S 是传递的， 则 SR 是传递的。
5、设 A={1，2，3，4}，P（A）（A 的幂集）上规定二元系如下
R
{
,
ts
|
,
ts
)
(
Ap
(|
s
|}|
|
t
则 P（A）/ R=（
）
A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；
D．{{ }，{2}，{2，3}，{{2，3，4}}，{A}}
6、设 A={ ，{1}，{1，3}，{1，2，3}}则 A 上包含关系“ ”的哈斯图为（
）
）
f (n) = ；
7、下列函数是双射的为（
f (x) = 2x ； B．f : N N N,
A．f : I E ,
C．f : R I ,
f (x) = [x] ； D．f :I N, f (x) = | x | 。
（注：I—整数集，E—偶数集， N—自然数集，R—实数集）
8、图 中 从 v1 到 v3 长度为 3 的通路有（
）条。
A． 0； B． 1； C． 2； D． 3。
9、下图中既不是 Eular 图，也不是 Hamilton 图的图是（
）
10、在一棵树中有 7 片树叶，3 个 3 度结点，其余都是 4 度结点则该树有（
）个 4
度结点。
A．1；B．2； C．3； D．4 。
三、证明 26%
１、R 是集合 X 上的一个自反关系，求证：R 是对称和传递的，当且仅当
< a, b> 和在 R 中有<.b , c>在 R 中。（8 分）
２、f 和 g 都是群到< G2, *>的同态映射，证明是的一个子
群。其中 C=
|{
)(
xfGxx
且
1
)}(
xg
(8 分)
３、G= (|V| = v，|E|=e ) 是每一个面至少由 k（k 3）条边围成的连通平面
e
)2
(
vk
2
k
图，则
， 由此证明彼得森图（Peterson）图是非平面图。（11 分）
四、逻辑推演 16%
用 CP 规则证明下题（每小题 8 分）
A
EDDC
BA
F
,
1、
F
(
)(
xPx
(
xQ
))
xP
)(
x
xQ
)(
x
2、
五、计算 18%
1、设集合 A={a，b，c，d}上的关系 R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算
求出 R 的传递闭包 t (R)。
（9 分）
2、如下图所示的赋权图表示某七个城市
,
vv 及预先算出它们之间的一些直接通
v
,
,
7
2
1
信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （９分）
试卷一答案：
一、填空 20% （每小题 2 分）
(
1、{0，1，2，3，4，6}； 2、
CB
)
A
；
5、1；6、{<1,1>, <1,3>, <2,2>, <2,4> }；7、{,,,,} IA ；8、
(
；3、1； 4、
RSP
)
RS
P
(
)
9、a ；a , b , c ,d ；a , d , c , d ；10、c;
二、选择 20% （每小题 2 分）
题目
1
2
答案 C D
B、C
3
C
4
A
5
D
6
C
7
A
8
D
9
B
10
A
三、证明 26%
1、 证：
“ ”
a,c<,>a,b<
R
,
,
Xcba
，由 R 传递性得
>c,a<,>b,a<
R
由 R 对 称 性 知
若
R >c,b<
>b,a<
R
，
R
>b,a<
>c,a<
R
有
R
>a,b<
R
>cb,<
则
>ab,<
“ ” 若
R
>a,a<
若
R
，
>b,a<
若
即 R 是传递的。
R >c,b<
任 意
Xba ,
， 因
所以 R 是对称的。
R
R
cb,
R
>c,a<
,
Cba
，
有
)(
af
)(
(
bfag
),
)(
bg
，
又
2、 证
(
bf
1
)
f
1
,)(
b
1
(
bg
)
g
1
)(
b
af (
★
1
b
)
*)(
af
f
1
)(
b
(*)(
bg
ag
(
bf
1
)
g
1
)(
b
(
bg
1
)
1
)
f
(
ag
1
)(
b
★ )1b
C
b 1
a ★
3、 证：
< C , ★> 是 < G1 , ★>的子群。
① 设 G 有 r 个 面 ， 则
2
e
r
i
1
(
Fd
)
i
rk
r
2
e
k
。 而
v
， 即
2
e
r
故
2
e
v
e
v
r
2
e
k
即得
e
(
)2
vk
2
k
。（8 分）
(
)2
vk
2
k
e
，这样
不成立，
②彼得森图为
k
,5
e
,15
v
10
所以彼得森图非平面图。（3 分）
一、 逻辑推演 16%
1、 证明：
① A
P（附加前提）
②
③
BA
BA
DC
④
⑤ D
⑥
⑦
⑧ F
DC
ED
ED
F
A
F
⑨
2、证明
xP
)(x
①
② )(cP
)(
(
xPx
③
(
xQ
))
)(
cP
)(
cQ
④
⑤ )(cQ
xQ
⑥
)(x
xP
)(
x
xQ
)(
x
⑦
T①I
P
T②③I
T④I
T⑤I
P
T⑥⑦I
CP
P（附加前提）
US①
P
US③
T②④I
UG⑤
CP
二、 计算 18%
1、 解：
RM
0010
0101
1000
0000
M
2
R
，
MM
R
M
3
R
M
2
R
M
R
M
4
R
M
3
R
M
R
1010
0101
0000
0000
0101
1010
0000
0000
R
0101
1010
0000
0000
，
M
(
Rt
)
M
R
M
M
3
R
M
4
R
2
R
1111
1111
1000
0000
t (R)={ , , < a , c> , , , < b ,b > , < b , c . > ,
< b , d > , < c , d > }
2、 解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：
树权 C(T)=23+1+4+9+3+17=57 即为总造价。
试卷二试题与答案
一、填空 20% （每小题 2 分）
1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为
；“虽然你努力了，但还是失败了”的翻译为
2、论域 D={1，2}，指定谓词 P
。
P (1,1)
P (1,2)
P (2,1)
P (2,2)
则公式
yPx
T
),(
xy
T
F
F
真值为
。
2、 设 S={a1 ，a2 ，…，a8}，Bi 是 S 的子集，则由 B31 所表达的子集是
3、 设 A={2 ， 3 ， 4 ， 5 ， 6} 上 的 二 元 关 系
。
|
x
R
{
,
yx
y
}
是质数x
， 则 R=
R 的关系矩阵 MR=
（列举法）。
。
5 、 设 A={1 ， 2 ， 3} ， 则 A 上 既 不 是 对 称 的 又 不 是 反 对 称 的 关 系
； A 上 既 是 对 称 的 又 是 反 对 称 的 关 系
R=
R=
。
*
a
b
c
a
a
b
b
b
b
c
c
c
c
b
c
7、4 阶群必是
8、下面偏序格是分配格的是
6、设代数系统，其中 A={a，b，c},
则 幺 元 是
； 是 否 有 幂 等
性
；是否有对称性
。
群或
群。
。
9、n 个结点的无向完全图 Kn 的边数为
，欧拉图的充要条件是
10、公式
(
P
QP
(
))
QP
((
。
)
R
的根树表示为
。
二、选择 20% （每小题 2 分）
1、在下述公式中是重言式为（
(
A．
QP
QP
(
)
)
；B．
(
P
）
Q
)
(
Q
((
Q
)
P
P
))
；
QQ
P
)
(
C．
D．
PQ
；
)
Q
P
(
P
QP
(
)
。
)
中极小项的个数为（
），成真赋值的个数
2、命题公式
(
为（
）。
A．0；
B．1；
}}2,1{},1{,{S
3、设
C．2； D．3 。
，则
S2 有（
）个元素。
A．3；
} 3 ,2 ,1 {S
,
ba
,
,
dc
D．8 。
B．6； C．7；
，定义 SS 上的等价关系
,
dc
SS
|
,
ba
,
daSS
}
cb
,
则由 R 产 生
4、 设
{
R
的 SS 上一个划分共有（
）个分块。
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
