2022年大学《离散数学》期末考试试卷及答案-.pdf

《2022年大学《离散数学》期末考试试卷及答案-.pdf》由会员分享，可在线阅读，更多相关《2022年大学《离散数学》期末考试试卷及答案-.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、安徽大学 2006-2007 学年第 1 学期离散数学期末考试试卷（A 卷）（时间 120 分钟）开课院（系、部）姓名学号. 题号一二三四五六七得分阅卷人得 分一、选择题（每小题2 分，共 20 分）1下列语句中，哪个是真命题（）A、42x； B、我们要努力学习；C、如果ab为奇数，那么a是奇数，或b是偶数； D 、如果时间流逝不止，你就可以长生不老。2下列命题公式中，永真式的是（）A、PQP)(； B 、PPQ)(； C 、QPP)(； D 、)(QPP。3 在谓词逻辑中，令)(xF表示x是火车；)(yG表示y是汽车；),(yxL表示x比y快。命题“并不是所有的火车比所有的汽车快”的符号表示

2、中哪些是正确的（）得分精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 13 页 - - - - - - - - - - I.),()()(yxLyGxFyxII.),()()(yxLyGxFyxIII. ),()()(yxLyGxFyxA、仅 I ； B、仅 III ； C、I 和 II ； D、都不对。4下列结论正确的是：（）A、若CABA，则CB； B、若BABA，则BA；C、若CABA，则CB； D、若BA且DC，则DBCA。5设1A，2A，)(3A，)(4A，以下命题为假的是（）A、4

3、2AA； B、31AA； C、24AA； D、34AA。6设R是集合,dcbaA上的二元关系，,bddbaccaaddaR。下列哪些命题为真（）I.RR是对称的II. RR是自反的III. RR不是传递的A、仅 I ； B、仅 II ； C、I 和 II ； D 、全真。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 13 页 - - - - - - - - - - 7R是二元关系且4RR，则一定是传递的是（）A、4R； B、3R； C、2R； D 、R。8设1R和2R是非空集合 A上的等价关

4、系，确定下列各式，哪些是A上的等价关系（）A、1RAA； B、21RR； C、21RR； D、21RR。9函数:fXY可逆的充要条件是：（）A、AB； B、| |AB； C、f为双射； D、f为满射。10下列集合中，哪个集合的基数与其他集合的基数不同（）A、nN（N为自然数集，Nn） ； B 、NN（N为自然数集）；C、RR（R为实数集）； D、x坐标轴上所有闭区间集合；精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 13 页 - - - - - - - - - - 二、填空题（每小题2 分，

5、共 32 分）1全集5,4,3 ,2, 1U，5 , 1A，4, 3,2, 1B，5 ,2C，则可求出：BA_ ；)()(CA_ ；C_ 。2设3A，16)(B，64)(BA，则：B=_ ，BA=_ ，BA=_ ，BA=_ 。3设4,3 ,2, 1A，R是A上的二元关系，且3 , 3,4,2,2, 1R，则)(Rr=_；)(Rs=_；得分精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 13 页 - - - - - - - - - - )(Rt=_；4设 A=1,2,3,4,5，则 A上共有多少

6、个二元关系_其中有多少个等价关系 _5设函数AAf :，AB为A的子集。则：)(1Bff_B，)(1Bff_B；当f为_函数时BBff)(1；当f为_函数时BBff)(1。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 13 页 - - - - - - - - - - 三、综合题（第2 小题 16 分，其它各小题8 分，共48分）1求命题公式PRQP)(的主析取范式与主合取范式（要求用等值演算的方法求解） 。 （8 分）2用推理规则证明：（每小题 8 分，共 16 分）)(RQP，PS，Q永真

7、蕴含RS。前提：)()()(xRyQxFx，)(xxF；结论：)()(xRxFx。3设集合,cbaA，)(A是集合A的幂集，试给出),(A的哈斯图，并指出子集,ba的极大元、极小元、最大元、最小元、上界、下界、最小上界、最大下届（如果存在的话） 。 （8 分）得分精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 13 页 - - - - - - - - - - 4设R是集合A上的关系，令,RbcRcaAcbaS且使，证明：如果R是等价关系，则S也是等价关系。（8 分）5已知NNNf :，22),

8、(yxyxf。请问： （8 分）f是单射吗f是满射吗计算)0(1f。计算)2, 1,0, 0(f。安徽大学 2006-2007 学年第 1 学期离散数学期末考试试卷答案（A卷）（时间 120 分钟）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 13 页 - - - - - - - - - - 一、选择题（每小题2 分，共 20 分）1C;二、填空题（每空2 分，共 32分）15；5 ,； 4, 3, 124，1，2，53,；,；,4252,525，满射，单射三、综合题（第2 小题 16 分，

9、其它各小题 8 分，共 48分）1PRQPA)(PRQP)(PRQP)(PRQRP)()( 2分精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 13 页 - - - - - - - - - - )()()()()()(RRQQPPPRQQQRP 4 分)()()()(RQPRQPRQPRQP)()()()(RQPRQPRQPRQP)()()()(RQPRQPRQPRQP)()(RQPRQP（主析取范式） 6分)()(RQPRQPA)()()(RQPRQPAA)()(RQPRQP（主合取范式）

10、8分2证明：(1) PSP 1分(2) SP（附加前提） 2 分(3) PT (1),(2) I 3分(4) )(RQPP 4分(5) RQT (3),(4) I 5分(6) QP 6分(7) RT (5),(6) I 7分(8) RSCP (2),(7) 8分精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 13 页 - - - - - - - - - - ca,cb,ca,ba,b证明：(1) )(xxF P 1分(2) )(cF ES (1) 2分(3) )()()(xRyQxFx P 3

11、分(4) )()()(cRyQcF US (3) 4分(5) )()(cRyQ T (2),(4) I 5分(6) )(cR T (5) I 6分(7) )()(cRcF T (2),(6) I 7分(8) )()(xRxFx EG (7) 8分3解：),(A的哈斯图如下图所示。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 13 页 - - - - - - - - - - ab（2 分） ；,ba的极大元是：,ba；极小元是：,ba（4 分） ；最大元不存在；最小元不存在（6 分） ；上界

12、有：,cbaba； 下界为：；最小上界为：,ba；最大下界为：（8 分） 。4证明：已知R是等价关系，对S是等价关系的证明分3 步：（1）自反性R是自反的，对Aa，有Raa,，根据S的定义，有Saa,，S是自反的；（2 分）（2）对称性如果Sba,，则Ac，使Rca,且Rbc,，R是对称的，Rcb,且Rac,，精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 13 页 - - - - - - - - - - 再根据S的定义有Sab,，S是对称的；（5 分）（3）传递性如果Sba,，Scb,，则

13、Ad使Rda,，且Rbd,。R是传递的，Rba,。则Ae使Reb,，且Rce,。R是传递的，Rcb,。根据S的定义有Sca,。S是传递的。（8 分）由（1） ， （2） ， （3）得S是等价关系。5解答：NN1 , 2,2 ,1，521)1 ,2()2 ,1(22ff，但1 ,22, 1，所以f不是单射（ 2 分） 。N3，但找不出这样的NNyx,，使得3),(22yxyxf。所以f不是满射（2 分） 。 0,)0(221yxyxf，解之，得0yx，所以0,0)0(1f（2 分） 。5 ,02, 1,0,0f（2 分） 。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 13 页 - - - - - - - - - - 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 13 页 - - - - - - - - - -