安徽大学离散数学(上)试卷及参考答案

《离散数学》试卷第1页共4页安徽大学2009—2010学年第1学期《离散数学》考试试卷（A卷）（时间120分钟）院/系专业姓名学号题号一二三四五六七总分得分一、单项选择题（每小题2分，共20分）1.设:P天没下雪，:Q我去镇上，则命题“天正在下雪，我没去镇上”可符号化为（）A.QP；B.PQ；C.QP；D.QP。2.下列命题是重言式的是（）A.)()(PQQP；B.)()(QPPQP；C.)(QPQP；D.QPRQP))((。3.设解释R如下：论域D为实数集，0a，yxyxf),(，yxyxf),(。下列公式在R下为真的是()A.))),(),,((),((zyfzxfAyxAzyx；B.)),,((axafxA；C.)),,((xyxfyAx；D.))),,((),((aaxfAyxAyx。4.对任意集合,,ABC，下列结论正确的是（）A.CACBBA][；B.CACBBA][；C.CACBBA][；D.CACBBA][。5.关于},,{cbaX到}3,2,1{Y的函数{,1,,1,,3}fabc，下列结论不正确的是（）A、1({3}){}fc；B、1(3)fc；C、({}){3}fc；D、()3fc。6.设I为整数集合，则I上的二元关系}4|||,{yxyxR具有（）A.自反性和对称性；B.反自反性和对称性；C.反自反性和传递性；D.反对称性和传递性。7.设R为非空集合A上的关系R的逆关系，则下列结论不成立的是（）A.若R为偏序，则R为偏序；B.若R为拟序，则R为拟序；C.若R为线序，则R为线序；D.若R为良序，则R为良序。得分《离散数学》试卷第2页共4页8.设1和2是非空集合A的划分，则下列结论正确的是（）A.1细分21；B.1细分21；C.非空集合A的划分12细分1；D.1细分非空集合A的划分12。9.设},,{cbaX，XI是X上恒等关系，要使RabaccbbaIX},,,,,,,{为X上的等价关系，R应取()A.},,,{caac；B.},,,{abbc；C.},,,{abac；D.},,,{bcca。10.设N和R分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合是（）A.R；B.NN；C.()N；D.nN（nN）。二、判断题（每小题2分，共10分。对的打√，错的打×）1.（）PQP)(为矛盾式。2.（）A、B、C是任意集合，如果BACA，一定有CB。3.（）若集合A上的二元关系R是对称的，R的绝对补R一定是对称的。4.（）有理数集是可数的。5.（）若函数f，g为单射，则它们的复合函数也为单射的。三、填空题（每小空2分，共20分）1．设)(xR：x是实数，)(xQ：x是有理数，)(xZ：x是整数，则“有理数都是实数，但实数并非都是有理数”符号化为：；“不是这样情况：某些整数不是有理数”符号化为：。2.设集合},,{cbaA，},{baB，那么)()(AB=______；)(AB=______。3.设}5,4,3,2,1,0{A，则定义在集合A上二元关系}2(|,{kkyxkyxR的关系矩阵为RM=＿＿＿＿＿＿＿＿＿＿；)(RtM＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。4.设]1,0[U，]1,21[A，13(,)44B，则()ABx＿＿＿＿＿＿＿＿＿＿，()ABx＿＿＿＿＿＿＿＿＿＿。5.设N为自然数集合，Q为有理数集合，R为实数集合，则||QN||N，||QR||Q（填=，，）。得分得分《离散数学》试卷第3页共4页三、解答题（每小题10分，共20分）1.求))(()(RQPRQP的主析取范式和主合取范式。2.给定集合}6,5,4,3,2,1{A上的偏序关系AIR}1,5,3,5,1,3,1,4,3,4,2,4,1,6,1,2,2,6{。求：（1）给出了偏序集合,AR的哈斯图；（2分）（2）完成下表。（每空2分）集合最大元最小元极大元极小元{2,3,4}B集合上界下界上确界下确界{3,4,5,6}C得分《离散数学》试卷第4页共4页四、证明题（每小题10分，共30分）1.用推理规则证明：))()(())()(())()((xPxRxQxRxxQxPx。2.设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠。关系R满足：x1，y1，x2，y2∈Rx1，x2∈R1且y1，y2∈R2，证明R是A×B上的等价关系。得分《离散数学》试卷第5页共4页3.设I为整数集合，E为偶数集合，函数EEIIf:定义为：yxyxyxf,),(，证明：f是双射函数。《离散数学》试卷第1页共2页安徽大学2007—2008学年第1学期《离散数学》考试试题（A卷）参考答案及评分标准一、单项选择题（每小题2分，共20分）1.D；2.C；3.A；4.B；5.B；6.B；7.D；8.B；9.D；10.D。二、判断题（每空2分，共10分）1.√，2.×，3.√，4.√，5.√三、填空题（每小空2分，共20分）1.))()(())()((xQxRxxRxQx或))()(())()((xQxRxxRxQx；))()((xQxZx或))()((xQxZx。2.}},,{},,{},,{},{{)()(cbacbcacAB；}}{,{)(cAB。3.RM=1000001000001000001011111；)(RtM=10000010000010000010111114.01)(xBA)21,41(]1,21[]41,0[xx当当；()ABx01)43,21[]41,0[]1,43[)21,41(xx当当5.||QN=||N；||QR||Q。三、解答题（每小题10分，共30分）1.))(()(RQPRQP)()(RQPRQP2分)()()()(RPQPRPQP4分)()()(RQPRQPRQP)()()(RQPRQPRQP《离散数学》试卷第2页共2页)6,5,4,3,2,1((主合取范式)8分)7,0(（主析取范式）10分2.（1）,AR的哈斯图为2分（2）（空2分）集合最大元最小元极大元极小元{2,3,4}B不存在42，34集合上界下界上确界下确界{3,4,5,6}C1不存在1不存在10分四、证明题（每小题10分，共30分）1.根据CP规则，上式等价于))()(())()(())()((xPxRxQxRxxQxPx2分而))()(())()((xQxRxxQxPx)))()(())()(((xQxRxQxPx10Q4分)))()(())()(((xQxRxPxQx245,EE6分))()(())()((xQxRxPxQ1Q8分)()(xPxR6I10分所以，))()(())()(())()((xPxRxQxRxxQxPx132465《离散数学》试卷第3页共2页2.证明对任意的x，y∈A×B，由R1是A上的等价关系可得x，x∈R1，由R2是B上的等价关系可得y，y∈R2。再由R的定义，有x，y，x，y∈R，所以R是自反的。2分对任意的x，y、u，v∈A×B，若x，yRu，v，则x，u∈R1且y，v∈R2。由R1对称得u，x∈R1，由R2对称得v，y∈R2。再由R的定义，有u，v，x，y∈R，即u，vRx，y，所以R是对称的。6分对任意的x，y、u，v、s，t∈A×B，若x，yRu，v且u，vRs，t，则x，u∈R1且y，v∈R2，u，s∈R1且v，t∈R2。由x，u∈R1、u，s∈R1及R1的传递性得x，s∈R1，由y，v∈R2、v，t∈R2及R2的传递性得y，t∈R1。再由R的定义，有x，y，s，t∈R，即x，yRs，t，所以R是传递的。10分综上可得，R是A×B上的等价关系。3.（1）1122,,,xyxyII，若),(),(2211yxfyxf，即22221111,,yxyxyxyx，则22112211yxyxyxyx，易得21xx且21yy，因此1122,,xyxy，所以f是单射函数。4分（2）取任意EEqp,，若存在IIyx,，使qpyxf,),(，则有qyxpyx，易得22qpyqpx，由于Eqp,，从而存在Ikk21,，使212,2kqkp，于是2121kkykkx所以有IyIx,。因此对于EEqp,，总存在,xyII，使得qpyxf,),(，所以f是满射函数。9分综上所述，f是双射函数。10分