《离散数学本科》20192020期末试题及答案
一、单项选择题（每小题3分，本题共15分）
1．若集合Aa，b，Ba，b，a，b，则（）．
A．AB，且AB
B．AB，但AB
C．AB，但AB
D．AB，且AB
2．集合A12345678上的关系Rx，yxy10且xyA，则R的性质为
（）．
A．自反的
B．对称的
C．传递且对称的
D．反自反且传递的
3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1R2中自反关系有（）个．
A．0
B．2
C．1
D．3
4．如图一所示，以下说法正确的是．
A．ae是割边
B．ae是边割集
C．aebc是边割集
D．de是边割集
图一
5．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为
（）．
A．xAx∧Bx
B．┐xAx∧Bx
C．┐xAx→Bx
D．┐xAx∧┐Bx
二、填空题（每小题3分，本题共15分）
6．若集合A的元素个数为10，则其幂集的元素个数为
．
7．设Aa，b，c，B1，2，作f：A→B，则不同的函数个数为
．
8．若A12，RxyxAyAxy10，则R的自反闭包为
．
1
f9．结点数v与边数e满足
关系的无向连通图就是树．
10．设个体域D＝abc，则谓词公式xAx消去量词后的等值式
为
．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．12．将语句“今天没有下雨．”翻译成命题公式．
四、判断说明题（每小题7分，本题共14分）
判断下列各题正误，并说明理由．
13．下面的推理是否正确，试予以说明．
1（x）F（x）→G（x）2F（y）→G（y）
前提引入US（1）．
14．若偏序集A，R的哈斯图如图二所示，则集合A的最大元为a，最小元不存在．
图二
五．计算题（每小题12分，本题共36分）
15．求（P∨Q）→（R∨Q）的合取范式．16．设A0，1，2，3，4，Rx，yxA，yA且xy0，Sx，yxA，yA且xy3，试求R，S，RS，R1，S1，rR．17．画一棵带权为12234的最优二叉树计算它们的权．
六、证明题（本题共8分）18．设G是一个
阶无向简单图，
是大于等于2的奇数．证明G与G中的奇数度顶
点个数相等G是G的补图．
2
f试题解答
一、单项选择题（每小题3分，本题共15分）1．A2．B3．B4．D5．C二、填空题（每小题3分，本题共15分）6．10247．88．11229．ev1
10．Aa∧Ab∧A（c）
三、逻辑公式翻译（每小题6分，本题共12分）
11．设P：他接受了这个任务，Q：他完成好了这个任务，PQ．
12．设Pr