大学《离散数学》期末考试试卷及答案-(1)

《离散数学》试卷共3页第1页安徽大学2006-2007学年第1学期《离散数学》期末考试试卷（A卷）（时间120分钟）开课院（系、部）姓名学号.题号一二三四五六七得分阅卷人得分一、选择题（每小题2分，共20分）1．下列语句中，哪个是真命题（）A、42x；B、我们要努力学习；C、如果ab为奇数，那么a是奇数，或b是偶数；D、如果时间流逝不止，你就可以长生不老。2．下列命题公式中，永真式的是（）A、PQP)(；B、PPQ)(；C、QPP)(；D、)(QPP。3．在谓词逻辑中，令)(xF表示x是火车；)(yG表示y是汽车；),(yxL表示x比y快。命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的？（）I.)),()()((yxLyGxFyxII.)),()()((yxLyGxFyxIII.)),()()((yxLyGxFyxA、仅I；B、仅III；C、I和II；D、都不对。4．下列结论正确的是：（）A、若CABA，则CB；B、若BABA，则BA；C、若CABA，则CB；D、若BA且DC，则DBCA。5．设1A，}{2A，})({3A，)(4A，以下命题为假的是（）A、42AA；B、31AA；C、24AA；D、34AA。6．设R是集合},,,{dcbaA上的二元关系，},,,,,,,,,,,{bddbaccaaddaR。下列哪些命题为真？（）I.RR是对称的II.RR是自反的III.RR不是传递的A、仅I；B、仅II；C、I和II；D、全真。7．R是二元关系且4RR，则一定是传递的是（）A、4R；B、3R；C、2R；D、R。8．设1R和2R是非空集合A上的等价关系，确定下列各式，哪些是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页第2页二、填空题（每小题2分，共32分）1．全集}5,4,3,2,1{U，}5,1{A，}4,3,2,1{B，}5,2{C，则可求出：BA_________________________________；)()(CA___________________________；C_____________________________________。2．设3A，16)(B，64)(BA，则：B=______________________________，BA=__________________________，BA=__________________________，BA=__________________________。3．设}4,3,2,1{A，R是A上的二元关系，且}3,3,4,2,2,1{R，则)(Rr=________________________________________________；)(Rs=________________________________________________；)(Rt=________________________________________________；4．设A={1,2,3,4,5}，则A上共有多少个二元关系________________？其中有多少个等价关系________________？5．设函数AAf:，AB为A的子集。则：))((1Bff____________B，))((1Bff____________B；当f为__________函数时BBff))((1；当f为__________函数时BBff))((1。得分《离散数学》试卷共3页第3页三、综合题（第2小题16分，其它各小题8分，共48分）1．求命题公式PRQP))((的主析取范式与主合取范式（要求用等值演算的方法求解）。（8分）2．用推理规则证明：（每小题8分，共16分）①)(RQP，PS，Q永真蕴含RS。②前提：)))()(()((xRyQxFx，)(xxF；结论：))()((xRxFx。3．设集合},,{cbaA，)(A是集合A的幂集，试给出),(A的哈斯图，并指出子集}}{},{{ba的极大元、极小元、最大元、最小元、上界、下界、最小上界、最大下届（如果存在的话）。（8分）4．设R是集合A上的关系，令},,,,{RbcRcaAcbaS且使，证明：如果R是等价关系，则S也是等价关系。（8分）5．已知NNNf:，22),(yxyxf。请问：（8分）①f是单射吗？②f是满射吗？③计算})0({1f。④计算})2,1,0,0({f。得分《离散数学》试卷共3页第3页安徽大学2006-2007学年第1学期《离散数学》期末考试试卷答案（A卷）（时间120分钟）一、选择题（每小题2分，共20分）1．C;2.D;3.C;4.B;5.A;6.C;7.B;8.D;9.C;10.A二、填空题（每空2分，共32分）1．}5{；}}5{,{；}4,3,1{2．4，1，2，53．{1,2,2,4,3,3,1,1,2,2,4,4}；{1,2,2,4,3,3,2,1,4,2}；{1,2,2,4,3,3,1,4}4．252,525．，满射，，单射三、综合题（第2小题16分，其它各小题8分，共48分）1．PRQPA))((PRQP))((PRQP))((PRQRP)()(2分))()(()()(())()((RRQQPPPRQQQRP4分)()()()(RQPRQPRQPRQP)()()()(RQPRQPRQPRQP)()()()(RQPRQPRQPRQP)()(RQPRQP（主析取范式）6分)()(RQPRQPA))()(()(RQPRQPAA)()(RQPRQP（主合取范式）8分2．①证明：(1)PSP1分(2)SP（附加前提）2分(3)PT(1),(2)I3分(4))(RQPP4分(5)RQT(3),(4)I5分(6)QP6分(7)RT(5),(6)I7分(8)RSCP(2),(7)8分②证明：(1))(xxFP1分(2))(cFES(1)2分(3))))()(()((xRyQxFxP3分(4)))()(()(cRyQcFUS(3)4分《离散数学》试卷共3页第3页{a}{b}{c}{a,c}{b,c}{a,b}{a,b,c}(5))()(cRyQT(2),(4)I5分(6))(cRT(5)I6分(7))()(cRcFT(2),(6)I7分(8)))()((xRxFxEG(7)8分3．解：),(A的哈斯图如下图所示。（2分）；}}{},{{ba的极大元是：}{},{ba；极小元是：}{},{ba（4分）；最大元不存在；最小元不存在（6分）；上界有：},,{},,{cbaba；下界为：；最小上界为：},{ba；最大下界为：（8分）。4．证明：已知R是等价关系，对S是等价关系的证明分3步：（1）自反性R是自反的，对Aa，有Raa,，根据S的定义，有Saa,，S是自反的；（2分）（2）对称性如果Sba,，则Ac，使Rca,且Rbc,，R是对称的，Rcb,且Rac,，再根据S的定义有Sab,，S是对称的；（5分）（3）传递性如果Sba,，Scb,，则Ad使Rda,，且Rbd,。R是传递的，Rba,。则Ae使Reb,，且Rce,。R是传递的，Rcb,。根据S的定义有Sca,。S是传递的。（8分）由（1），（2），（3）得S是等价关系。5．解答：①NN1,2,2,1，521)1,2()2,1(22ff，但1,22,1，所以f不是单射（2分）。②N3，但找不出这样的NNyx,，使得3),(22yxyxf。所以f不是满射（2分）。③}0,{})0({221yxyxf，解之，得0yx，所以}0,0{})0({1f（2分）。④}5,0{}2,1,0,0{f（2分）。