精选
中央电大离散数学（本科）考试试题
一、单项选择题（每小题3分，本题共15分）
1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( a )． A．A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B
2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( d )．
图一
A．（a）是强连通的 B．（b）是强连通的
C．（c）是强连通的 D．（d）是强连通的
3．设图G的邻接矩阵为
?0?1??1??0??01001110000010010?1??0??1?0??
则G的边数为( b )．
A．6 B．5 C．4 D．3 4．无向简单图G是棵树，当且仅当( a )．
A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( c )为重言式．
A．?P??Q?P?Q B．(Q?(P?Q)) ?(?Q?(P?Q)) C．(P?(?Q?P))?(?P?(P?Q)) D．(?P?(P?Q)) ?Q 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（ a ）． A．A?B，且A?B B．A?B，但A?B C．A?B，但A?B D．A?B，且A?B
2．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
C．传递且对称的 D．反自反且传递的 3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（ b ）个． A．0 B．2 C．1 D．3 4．如图一所示，以下说法正确的是 ( d ) ．
A．{(a, e)}是割边 B．{(a, e)}是边割集 C．{(a, e) ,(b, c)}是边割集 D．{(d, e)}是边割集
图一
5．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（ c ）． A．(?x)(A(x)∧B(x)) B．┐(?x)(A(x)∧B(x)) C．┐(?x)(A(x) →B(x)) D．┐(?x)(A(x)∧┐B(x))
1．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={
A．R1和R2 B．R2 C．R3 D．R1和R3
2．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( b )． A．8、2、8、2 B．无、2、无、2 C．6、2、6、2 D．8、1、6、1
3．若集合A的元素个数为10，则其幂集的元素个数为（ a ）． A．1024 B．10 C．100 D．1
4．设完全图Kn有n个结点(n≥2)，m条边，当（ c ）时，Kn中存在欧拉回路．
-可编辑修改-
精选
A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数
5．已知图G的邻接矩阵为
，
则G有（ d ）．
A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边
1．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( c )． A．{a，{a}}?A B．{2}?A C．{a}?A D．??A
?2．设图G＝
? C．v D． 3．命题公式（P∨Q）→R的析取范式是 ( d ) A．?（P∨Q）∨R B．（P∧Q）∨R C．（P∨Q）∨R D．（?P∧?Q）∨R 4．如图一所示，以下说法正确的是 ( a )．
A．e是割点 B．{a, e}是点割集 C．{b, e}是点割集 D．{d}是点割集
5．下列等价公式成立的为( b )．
A．?P??Q?P?Q B．P?(?Q?P) ??P?(P?Q) C．Q?(P?Q) ??Q?(P?Q) D．?P?(P?Q) ?Q
1．若G是一个汉密尔顿图，则G一定是( d )． A．平面图 B．对偶图 C．欧拉图 D．连通图
2．集合A={1, 2, 3, 4}上的关系R={
3．设集合A={1，2，3，4，5}，偏序关系?是A上的整除关系，则偏序集
图一
5．设?A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（ a ）． A．(x)(A(x)∧B(x)) B．(?x)(A(x)∧B(x))
C．┐(?x)(A(x) →B(x)) D．┐(?x)(A(x)∧┐B(x)) 1．若集合A＝{ a，{a}}，则下列表述正确的是( a )． A．{a}?A B．{{{a}}}?A C．{a，{a}}?A D．??A
2．命题公式（P∨Q）的合取范式是 ( c ) A．（P∧Q） B．（P∧Q）∨（P∨Q） C．（P∨Q） D．?（?P∧?Q） 3．无向树T有8个结点，则T的边数为( b )． A．6 B．7 C．8 D．9 4．图G如图一所示，以下说法正确的是 ( b )． A．a是割点 B．{b, c}是点割集 C．{b, d}是点割集 D．{c}是点割集
图一
5．下列公式成立的为( d )．
A．?P∧?Q ? P∨Q B．P??Q ? ?P?Q
-可编辑修改-
b ）． 精选
C．Q?P ? P D．?P∧(P∨Q)?Q 1．“小于5的非负整数集合”采用描述法表示为___a___．
A．{x?x?N, x<5 } B．{x?x?R, x<5 } C．{x?x?Z, x<5 } D．{x?x?Q, x<5 }
2．设R1，R2是集合A={a,b,c,d}上的两个关系，其中R1={(a,a),(b,b),(b,c), (d,d)}，R2={(a,a),(b,b),(b,c),(c,b),(d,d)}，则R2是R1的__b____闭包．
A．自反 B．对称 C．传递 D．以上答案都不对
3．设函数f：R→R，f(a)=2a+1；g：R→R，g(a)=a2，则___c___有反函数． A．f?g B．g?f C．f D．g
0 4．已知图G的邻接矩阵为???1?0??1?1?1000100011101011?，则图?1?1??1?0??G有___d___．
A．5点，8边 B．6点，7边
C．6点，8边 D．5点7边
5．无向完全图K4是___a___．
A．汉密尔顿图 B．欧拉图 C．非平面图 D．树
6．在5个结点的完全二叉树中，若有4条边，则有___b___片树叶． A．2 B．3 C．4 D．5
7．无向树T有7片树叶，3个3度结点，其余的都是4度结点，则T有__c___个4度结点． A．3 B．2 C．1 D．0
8．与命题公式P?（Q?R）等值的公式是___a___． A．(P?Q)?R B．(P?Q)?R C．(P?Q)?R D．P?(Q?R)
?x(P(x)??yR(y))?Q(x)中量词?x的辖域是___b___．
9．谓词公式
?x(P(x)??yR(y)) B．P(x)??yR(y)
A．
Q(x)
C．P(x) D．
?xP(x)?(?x?Q(x)???xQ(x))的类型是___c___．
10．谓词公式
A．蕴涵式 B．永假式
C．永真式 D．非永真的可满足式 1．设A={1,2,3,4}，B={1,3}，C={-1,0,1,2}，则___a___． A．B?A B．B?C C．B?A D．B?C
2．若集合A的元素个数为10，则其幂集的元素个数为___b___． A．1000 B．1024 C．1 D．10
(A?B)?C?__c____．
3．设集合A={1,2}，B={a,b}，C={?}，则 A．{<1,a,?>,<1,b,?>,<2,a,?>,<2,b,?>}
B．{<1,
4．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为___d___． A．8、1、6、1 B． 8、2、8、2 C．6、2、6、2 D．无、2、无、2 5．有5个结点的无向完全图K5的边数为___a___． A．10 B．20 C．5 D．25
6．设完全图Kn有n个结点(n≥2)，m条边，当___b___时，Kn中存在欧拉回路． A．n为偶数 B．n为奇数 C．m为偶数 D．m为奇数
7．一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，则T有__c___个顶点． A．3 B．8 C．11 D．13
8．命题公式（P∨Q）→R的析取范式是___b___． A．（?P∧?Q）∨R B． ?（P∨Q）∨R C．（P∧Q）∨R D．（P∨Q）∨R 9．下列等价公式成立的是___b___．
A．?P??Q?P?Q B． P?(?Q?P) ??P?(P?Q) C．?P?(P?Q) ?Q D．Q?(P?Q) ??Q?(P?Q)
?xP(x)?(?x?Q(x)???xQ(x))的类型是__c____．
10．谓词公式
A．蕴涵式 B．永假式
C．永真式 D．非永真的可满足式
6．命题公式P?(Q?P)的真值是 T （或1） ．
7．若图G=
-可编辑修改-
二、填空题（每小题3分，本题共15分）
精选
8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 0 ，则该序列集合构成前缀码． 9．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 ． 10．(?x)(P(x)→Q(x)∨R(x，y))中的自由变元为R(x，y )中的y
6．若集合A的元素个数为10，则其幂集的元素个数为 1024 ． 7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为 8 ． 8．若A={1,2}，R={
7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．
8．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树． 9．设连通平面图G的结点数为5，边数为6，则面数为 3 ．
10．设个体域D＝{a, b}，则谓词公式(?x)A(x)∧（?x）B（x）消去量词后的等值式为(A (a)∧A (b))∧(B（a）∨B（b）) ． 6．设集合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>．
7．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2 ．
8．设G＝
7．若图G=
8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 0 ，则该序列集合构成前缀码． 9．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 ．
10．(?x)(P(x)→Q(x)∨R(x，y))中的自由变元为R(x，y )中的y
6．若集合A的元素个数为10，则其幂集的元素个数为 1024 ． 7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为 8 ． 8．若A={1,2}，R={
10．设个体域D＝{a, b, c}，则谓词公式(?x)A(x)消去量词后的等值式为A (a) ∧A (b)∧A（c）
6．若集合A={1，3，5，7}，B={2，4，6，8}，则A∩B=空集（或?） ．
7．设集合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>,}
8．设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为2|E|（或“边数的两倍”） 9．无向连通图G的结点数为v，边数为e，则G当v与e满足 e=v-1 关系时是树． 10．设个体域D＝{1, 2, 3}， P(x)为“x小于2”，则谓词公式(?x)P(x) 的真值为假（或F，或0） ．
6．设集合A={2, 3, 4}，B={1, 2, 3, 4}，R是A到B的二元关系， R?{?x,y?x?A且y?B且x?y}
则R的有序对集合为{<2, 2>，<2, 3>，<2, 4>，<3, 3>}，<3, 4>，<4, 4>}
7．如果R是非空集合A上的等价关系，a ?A，b?A，则可推知R中至少包含
8．设G＝
EA ={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>} 12．设集合A＝{a，b}，那么集合A的幂集是{?,{a},{b},{a,b}} 13．设集合A={1,2,3}，B={a,b}，从A到B的两个二元关系R={<1,a>,<2,b>, <3,a>}，S={<1,a>,<2,a>,<3,a>}，则R-S=_ R-S={<2,b>}．
14．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2． 15．无向连通图G是欧拉图的充分必要条件是结点度数均为偶数．
16．设G＝
17．设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有____14___条边，G的总度数是___28_____，G的分支点数是____7____．
18．设P，Q的真值为1，R，S的真值为0，则命题公式(P?Q)?R?S?Q的真值为___0_____． 19．命题公式P?(Q?R)的合取范式为P?(?Q?R)析取范式为(P??Q)?(P?R) 20．设个体域为整数集，公式?x?y(x?y?0)真值为___1_____． 11．设集合A={1,2,3,4}，B={3,4,5,6}，则：
A?B?___{3,4}_____，A?B?_____{1,2,3,4,5,6}_____．
12．设集合A有n个元素，那么A的幂集合P(A)的元素个数为 ．
13．设集合A={a,b,c,d}，B={x,y,z}，R={
?1?则关系矩阵MR＝?0?0??0?01??10?． 01??10??-可编辑修改-
精选
14．设集合A={a,b,c,d,e}，A上的二元关系R={
15．无向图G存在欧拉回路，当且仅当G连通且__所有结点的度数全为偶数 16．设连通平面图G的结点数为5，边数为6，则面数为 3 ． 17．设正则二叉树有n个分支点，且内部通路长度总和为I，外部通路长度总和为E，则有E=___ I+2n 18．设P，Q的真值为0，R，S的真值为1，则命题公式(P?R)?(Q?S)的真值为_____1___． 19．已知命题公式为G＝(?P?Q)?R，则命题公式G的析取范式是(P??Q)?R
20．谓词命题公式(?x)(P(x)→Q(x)∨R(x，y))中的约束变元为___x___． 三、逻辑公式翻译（每小题4分，本题共12分）
11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式． 设P：所有人今天都去参加活动，Q：明天的会议取消， （1分） P? Q． （4分） 12．将语句“今天没有人来．” 翻译成命题公式．
设 P：今天有人来， （1分） ? P． （4分） 13．将语句“有人去上课．” 翻译成谓词公式．
设P(x)：x是人，Q(x)：x去上课， （1分） (?x)(P(x) ?Q(x))． （4分） 11．将语句“如果你去了，那么他就不去．”翻译成命题公式．
设P：你去，Q：他去， （1分） P??Q． （4分） 12．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．
设P：小王去旅游，Q：小李去旅游， （1分） P?Q． （4分） 13．将语句“所有人都去工作．”翻译成谓词公式．
设P(x)：x是人，Q(x)：x去工作， （1分） (?x)(P(x)?Q(x))． （4分） 11．将语句“他不去学校．”翻译成命题公式．
设P：他去学校， （1分） ? P． （4分） 12．将语句“他去旅游，仅当他有时间．”翻译成命题公式．
设 P：他去旅游，Q：他有时间， （1分） P ?Q． （4分） 13．将语句“所有的人都学习努力．”翻译成命题公式．
设P(x)：x是人，Q(x)：x学习努力， （1分） （?x）(P(x)?Q(x))． （3分） 11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．
设P：他接受了这个任务，Q：他完成好了这个任务， （2分） P?? Q． （6分） 12．将语句“今天没有下雨．”翻译成命题公式．
设P：今天下雨， （2分） ? P． （6分） 11．将语句“他是学生．”翻译成命题公式．
设P：他是学生， （2分） 则命题公式为： P． （6分） 12．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．
设P：明天下雨，Q：我们就去郊游， （2分）
则命题公式为：? P? Q． （6分） 11．将语句“今天考试，明天放假．”翻译成命题公式．
设P：今天考试，Q：明天放假． （2分）
则命题公式为：P∧Q． （6分） 12．将语句“我去旅游，仅当我有时间．”翻译成命题公式．
设P：我去旅游，Q：我有时间， （2分） 则命题公式为：P?Q． （6分） ⑴ 将语句“如果明天不下雨，我们就去春游．”翻译成命题公式． ⑵ 将语句“有人去上课．” 翻译成谓词公式． ⑴设命题P表示“明天下雨”，命题Q表示“我们就去春游”.
则原语句可以表示成命题公式 ?P→Q. （5分） ⑵设P(x)：x是人，Q(x)：x去上课
则原语句可以表示成谓词公式 (?x)(P(x) ?Q(x))．
四、判断说明题（每小题7分，本题共14分）
14．┐P∧（P→┐Q）∨P为永真式．
正确． （3分） ┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，
如果P的值为真，则┐P∧（P→┐Q）∨P为真， （5分）
-可编辑修改-
2020年电大离散数学(本科)考试试题及答案参考资料重要知识点
