2020 年电大离散数学（本）期末考试题库及答案
一、单项选择题
1．设 P：a 是偶数，Q：b 是偶数。R：a + b 是偶数，则命题“若 a 是偶数，b 是偶数，则 a + b 也是偶数”符号化为（D． P Q→R）。 2．表达式? x（P（x，y） ? Q（z） ? ? y（Q（x，y）→ ? zQ（z））中? x 的辖域是（P（x，y） Q（z）。 3．设 S1 ? ?, S2 ? {?}, S3 ? P({?}), S4 ? P(?) 则命题为假的是（ S2 ? S4 ）。 4．设 G 是有 n 个结点的无向完全图，则 G 的边数（ 1/2 n（n-1）。 5．设 G 是连通平面图，有 v 个结点，e 条边，r 个面，则 r=（ e-v+2）。 6．若集合 A={1，{2}，{1，2}}，则下列表述正确的是( {1}
A )．
7．已知一棵无向树 T 中有 8 个顶点，4 度、3 度、2 度的分支点各一个，T 的树叶数为( 5 )．
?0 1 1 1 1??
?1 0 0 1 1??
? 则 G 的边数为( 7 )． 8．设无向图 G 的邻接矩阵为 ??
?1 ?0 0 0 0 ??????
1 1 1 0 0 ???
??1 1 0 1 0???
9．设集合 A={a}，则 A 的幂集为({，{a}} )． 10．下列公式中 (AB (AB) )为永真式．
11．若 G 是一个汉密尔顿图，则 G 一定是( 连通图 )．
12．集合 A={1, 2, 3, 4}上的关系 R={
13．设集合 A={1，2，3，4，5}，偏序关系是 A 上的整除关系，则偏序集
14．图 G 如图一所示，以下说法正确的是 ( {(a, d) ,(b, d)}是边割集 ) ． 图一 15．设 A（x）：x 是人，B（x）：x 是工人，则命题“有人是工人”可符号化为（( ? x)(A(x)∧B(x)) ）． 16．若集合 A={1，2}，B={1，2，{1，2}}，则下列表述正确的是(AB，且 AB )．
17．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( （d）是强连通的 )．
?0 1 1 0 0??
?
1 0 0 1 1??
? 则 G 的边数为( 5 )． ?18．设图 G 的邻接矩阵为 ?
??0 0 ?1 0 0 ?
????
1 0 1 0 0 ???
??0 1 0 1 0???
19．无向简单图 G 是棵树，当且仅当(G 连通且边数比结点数少 1 )． 20．下列公式 ((P(QP))(P(PQ)) )为重言式．
21．若集合 A＝{ a，{a}，{1，2}}，则下列表述正确的是({a}A)．
22．设图 G＝
(
P∧
v?V
?deg(v) ? 2 E
Q）∨R )
) ．
QP) P(PQ) )．
25．设 A={a, b}，B={1, 2}，R1，R2，R3 是 A 到 B 的二元关系，且 R1={
26．设 A={1, 2, 3, 4, 5, 6, 7, 8}，R 是 A 上的整除关系，B={2, 4, 6}，则集合 B 的最大元、最小元、上界、下界依次为 (无、2、无、2)．
27．若集合 A 的元素个数为 10，则其幂集的元素个数为（1024）．
28．如图一所示，以下说法正确的是 (e 是割点)． 图一
29．设完全图 K n 有 n 个结点(n≥2)，m 条边，当（ n 为奇数）时，K n 中存在欧拉回路．
30．已知图 G 的邻接矩阵为 ，则 G 有（ 5 点，7
边 ）．二、填空题（每小题 3 分，共 15 分）
1．设 A，B 为任意命题公式，C 为重言式，若 A ? C ? B ? C，那么 A ? B 是 重言 式（重言式、矛盾式或可满足式）。 2．命题公式（P→Q） ? P 的主合取范式为 3．设集合 A={ ? ，{a}}，则 P（A）=
(P ? Q) ? (?P ? Q)
。 。
{?,{?},{{a}},{?,{a}}}
V′=V,E′ E
4．设图 G =〈V，E〉， G ′=〈V′，E′〉，若
r
,则 G′是 G 的生成子图。
5．在平面 G =〈V，E〉中，则 0）
．
?deg(r) = 2|E| ，其中 r（i=1，2，…，r）是 G 的面。6．命题公式 P ? ?P 的真值是 假（或 F，或
i?1
i
i
7．若无向树 T 有 5 个结点，则 T 的边数为 4 ． t-1
．
<2, 1>
，就可使新得到的关系为对称的．
8．设正则 m 叉树的树叶数为 t，分支数为 i，则(m-1)i=
9．设集合 A={1，2}上的关系 R＝{<1, 1>,<1, 2>}，则在 R 中仅需加一个元素 10．(
x)(A(x)→B(x，z)∨C(y))中的自由变元有 z，y ．
）
．
{<1, 2>, <2, 3>, <3,
11．若集合 A={1，3，5，7}，B={2，4，6，8}，则 A∩B= 空集（或2>,}
．
12．设集合 A={1，2，3}上的函数分别为：f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，则复合函数 gf = 13．设 G 是一个图，结点集合为 V，边集合为 E，则 G 的结点度数之和为 14．无向连通图 G 的结点数为 v，边数为 e，则 G 当 v 与 e 满足
2|E|（或“边数的两倍”）
关系时是树． 假（或 F，或 0）
． ．
e=v-1
15．设个体域 D＝{1, 2, 3}， P(x)为“x 小于 2”，则谓词公式(x)P(x) 的真值为
16．命题公式 P ? (Q ? P) 的真值是 T （或 1）
．
17．若图 G=
18．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素
0 ，则该序列集合构成前缀码．
5
．
19．已知一棵无向树 T 中有 8 个结点，4 度，3 度，2 度的分支点各一个，T 的树叶数为 20．(
x)(P(x)→Q(x)∨R(x，y))中的自由变元为 R(x，y )中的 y ．
21．设集合 A={0, 1, 2, 3}，B={2, 3, 4, 5}，R 是 A 到 B 的二元关系， R ? {? x, y ? x ? A且y ? B且x, y ? A ? B} 则 R 的有序对集合为 {<2, 2>，<2, 3>，<3, 2>}，<3, 3>
．
3
22．设 G 是连通平面图，v, e, r 分别表示 G 的结点数，边数和面数，则 v，e 和 r 满足的关系式 23．设 G＝
所有结点的度数全为偶数
． ．
v-e+r=2 ．
条边，可以确定图 G 的一棵生成树．
25．设个体域 D＝{1,2}，则谓词公式 ?xA(x) 消去量词后的等值式为
A(1)A(2)
．
26．设集合 A＝{a，b}，那么集合 A 的幂集是 {,{a,b},{a},{b }}
27．如果 R1 和 R2 是 A 上的自反关系，则 R1∪R2，R1∩R2，R1-R2 中自反关系有 28．设图 G 是有 6 个结点的连通图，结点的总度数为 18，则可从 G 中删去
2 4
个．
条边后使之变成树．
29．设连通平面图 G 的结点数为 5，边数为 6，则面数为 3 ．
30．设个体域 D＝{a, b}，则谓词公式(x)A(x)∧（x）B（x）消去量词后的等值式为 (A (a)∧A (b))∧(B（a）∨B（b）) ．
31. 设集合 A={0，1 ，2} ，B={l ，2 ，3 ， 剖，R 是 A 到 B 的二元关系，R= {
32. 设 G 是连通平面图，v， e ， r 分别表示 G 的结点数， 边数和面数， 则 v， e 和 r 满足的关系式 v-e+r=2 33.G=
xA(x)消去量词后的等值式为 A(1)∧A(2)
三、化简解答题
11．设集合 A={1，2，3，4}，A 上的二元关系 R，R={〈1，1〉，〈1，4〉，〈2，2〉，〈2，3〉，〈3，2〉，〈3，3〉，〈4，1〉，〈4，4〉}，说明 R 是A 上的等价关系。 解
从 R 的表达式知，
?x ? A,(x, x) ? R, 即 R 具有自反性；
三、逻辑公式翻译
1．将语句“今天上课．”翻译成命题公
式． 设 P：今天上课， 则命题公式为：P．
2．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．
设 P：他去操场锻炼，Q：他有时间， 则命题公式为：P 3．将语句“他是学生．”翻译成命题公
式．设 P：他是学生， 则命题公式为： Q．
P．
4．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．
设 P：明天下雨，Q：我们就去郊游， 则命题公式为： P5．将语句“他不去学校．”翻译成命题公
式．设 P：他去学校，
P．
6．将语句“他去旅游，仅当他有时间．”翻译成命题公
式．设 P：他去旅游，Q：他有时间， P 设 P(x)：x 是人，Q(x)：x 学习努力， （式．设 P：你去，Q：他去， P
Q．
Q．
x）(P(x)Q(x))．
7．将语句“所有的人都学习努力．”翻译成命题公式． 8．将语句“如果你去了，那么他就不去．”翻译成命题公
Q．
9．将语句“小王去旅游，小李也去旅游．”翻译成命题公
式．设 P：小王去旅游，Q：小李去旅游， PQ． 10．将语句“所有人都去工作．”翻译成谓词公式．
设 P(x)：x 是人，Q(x)：x 去工作， (
x)(P(x)Q(x))．
Q．
11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公
式．设 P：所有人今天都去参加活动，Q：明天的会议取消， P12．将语句“今天没有人来．” 翻译成命题公
式．设 P：今天有人来，
P．
13．将语句“有人去上课．” 翻译成谓词公式．
设 P(x)：x 是人，Q(x)：x 去上课， (
x)(P(x) Q(x))．
1 1. 将语句\如果小李学习努力，那么他就会取得好成绩. \翻译成命题公式.
设 P：小李学习努力，Q:小李会取得好成绩，P→Q 12. 将语句\小张学习努力,小王取得好成绩. \翻译成命题公式.
设 P：小张学习努力，Q:小王取得好成绩，P∧Q
四、判断说明题
1．设集合 A={1，2}，B={3，4}，从 A 到 B 的关系为 f={<1, 3>}，则 f 是 A 到 B 的函
数． 错误． 因为 A 中元素 2 没有 B 中元素与之对应，故 f 不是 A 到 B 的函数．
2．设 G 是一个有 4 个结点 10 条边的连通图，则 G 为平面图．
错误． 不满足“设 G 是一个有 v 个结点 e 条边的连通简单平面图，若 v≥3，则 e≤3v-6．”
3．设 N、R 分别为自然数集与实数集，f：N→R，f (x)=x+6，则 f 是单射．
正确． 设 x1，x2 为自然数且 x1x2，则有 f(x1)= x1+6
x2+6= f(x2)，故 f 为单射．
4．下面的推理是否正确，试予以说明．
(1) （x）F（x）→G（x） (2) F（y）→G（y） （1）．错误．
（2）应为 F（y）→G（x），换名时，约束变元与自由变元不能混淆． 5．如图二所示的图 G 存在一条欧拉回路．
前提引入 US
图二
错误． 因为图 G 为中包含度数为奇数的结点．
6．设 G 是一个有 6 个结点 14 条边的连通图，则 G 为平面图．
错误． 不满足“设 G 是一个有 v 个结点 e 条边的连通简单平面图，若 v≥3，则 e≤3v-6．” 7．如果 R1 和 R2 是 A 上的自反关系，则 R1∪R2 是自反的．
正确． R1 和 R2 是自反的，x
A，
8．如图二所示的图 G 存在一条欧拉回路．
v1
v5 e f a v2 h d g v4 n c
b 图二
v3 正确． 因为图 G 为连通的，且其中每个顶点的度数为偶数．
9．┐P∧（P→┐Q）∨P 为永真
式． 正确．
┐P∧（P→┐Q）∨P 是由┐P∧（P→┐Q）与 P 组成的析取式， 如果 P 的值为真，则┐P∧（P→┐Q）∨P 为真，
如果 P 的值为假，则┐P 与 P→┐Q 为真，即┐P∧（P→┐Q）为真，
也即┐P∧（P→┐Q）∨P 为真， 所以┐P∧（P→┐Q）∨P 是永真
式． 另种说明：
┐P∧（P→┐Q）∨P 是由┐P∧（P→┐Q）与 P 组成的析取式， 只要其中一项为真，则整个公式为真．
可以看到，不论 P 的值为真或为假，┐P∧（P→┐Q）与 P 总有一个为真， 所以┐P∧（P→┐Q）∨P 是永真式． 或用等价演算┐P∧（P→┐Q）∨PT
10．若偏序集
图一
正确．
对于集合 A 的任意元素 x，均有
正确，R1 和 R2，是自反的，x∈A,
正确，因为图 G 为连通的，且其中每个顶点的度数为偶数。
五．计算题（每小题 12 分，本题共 36 分） 1．试求出（P∨Q）→（R∨Q）的析取范式．
（P∨Q）→（R∨Q）
┐(P∨Q)∨（R∨Q） (┐P∧┐Q)∨（R∨Q） (┐P∧┐Q)∨R∨Q（析取范式）
2．设 A={{1}, 1, 2}，B={ 1, {2}}，试计算（1）（A∩B）
（1）（A∩B）={1}
（2）（A∪B）={1, 2, {1}, {2}} （3） A（A∩B）={{1}, 1, 2}
（2）（A∪B）
（3）A （A∩B）．
3．图 G=
（3）求出 G 权最小的生成树及其权值．
（1）G 的图形表示如图一所示：
a ? 1 2 3 4 ? d 5
?????b 1 图一
c
?0
??1 ?（2）邻接矩阵： ?1 ? ?1 1 1 1??
??0 1 1 ??
1 0 1??
??
1 1 0 ??
?
?
?
a ???3 ? d 1 ? b 2 4 5 1 图二
??c
（3）最小的生成树如图二中的粗线所示：
权为：1+1+3=5
4．画一棵带权为 1, 2, 2, 3, 4 的最优二叉树,计算它们的
权． 最优二叉树如图三所示 .
12 ??
2020年电大离散数学(本)期末考试题库及答案
