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