计算机学院2010—2011年离散数学(上)试卷(A卷)

第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.PQQ。3.设解释I如下：论述域为整数集，xyyxP:),(，yxyxE:),(，yxyxG:),(，则下列公式在I下为真的是（）A.))),(),,(())1,(),,1(((xxPyyPGxPyPGyx；B.)0),1,((xPxE；C.)1),0,(()0),1,((xPxExPxE；D.))1),,(()),,(((xxPGyyxPGyx。4.对任意集合,,ABC，下列结论不正确的是（）A.()()ABCACB；B.()()ABCABC；C.()()()ABCACBC；D.()()ABCABC。5.关于}3,2,1{X到},,{cbaY的函数},3,,2,,1{cabf，下列结论错误的是（）A.bf)1(；B.1)(1bf；C.}1{})({1bf；D.}1{)(1bf。6.整数集合I上的二元关系{,|(2)}Rxykxkyk具有（）A.自反性和对称性；B.反自反性和对称性；C.自反性和传递性；D.反对称性和传递性。7.设1R，2R为非空集合A上的二元关系，则下列结论不成立的是（）A.)()()(2121RrRrRRr；B.)()()(2121RsRsRRs；C.)()()(2121RtRtRRt；D.)()(11RtrRrt。8.设1和2是非空集合A的划分，则下列集合一定是A的划分的是（）A.21；B.21；C.12；D.1121)]([。9.设XI是集合},,{cbaX上的恒等关系，要使RabacbaIX},,,,,{为X上的等价关系，R可取（）A.{,,,,,}caaccb；B.{,,,,,}cbbaac；题号一二三四五六七总分得分阅卷人院/系年级专业姓名学号答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------得分第2页共4页C.{,,,,,}cababc；D.{,,,,,}accbbc。10.设N和R分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合是（）A.R；B.NN；C.()N；D.)(R。二、判断题（每小题2分，共10分）1.联结词集合},{为全功能的。（）2.对任意集合,,ABC，若BA及CB，则CA。（）3.(),N一定是良序集合。（）4.如果合成函数fg是双射的，则函数f必是单射的而g是满射的。（）5.有理系数的所有多项式集合是可数的。（）三、填空题（每小空2分，共20分）1.设)(xE：x是偶数，)(xP：x是质数，()Ix：x是整数，)(xN：x是负数，则在全总个体域下“有某个质数其平方是偶数”符号化为：；“对任何两个整数x和y，yx或xy是非负的”符号化。2.设{,}Aab，{,,}Babc，则)()(AB=；(())BA=。3.设I为整数集合，则集合{0,1,2,3,4}A上的二元关系{,|(2)}RxykxkykIk的关系矩阵为RM=；R传递闭包的关系矩阵为)(RtM。4.设]1,0[U，1(,1]2A，13[,)44B，则特征函数)(xBA，)(xBA。5.设N为自然数集，I为整数集，R为实数集，则||NI||I，||RN||I（填=，，）。四、解答题（每小题10分，共20分）1.设集合}30,15,10,6,5,3,2,1{S，定义S上的偏序关系D为整除关系，（1）给出偏序集合DS,的哈斯图；（2）求出}10,3,2{B的最大元、最小元、极大元和极小元，并填入下表；（3）求出}5,3,2{C的上界、下界、上确界和下确界，并填入下表。得分得分得分第3页共4页2.求)()(RQPRQP的主析取范式和主合取范式。五、证明题（每小题10分，共30分）1.用推理规则证明：))()(())()(())()((xPxRxQxRxxQxPx集合最大元最小元极大元极小元}10,3,2{B集合上界下界上确界下确界}5,3,2{C得分答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------)()(RQPRQP第4页共4页2.设R是A上一个二元关系，)},,,(),(|,{RbcRcaAcAbabaS且有对于某一个试证明若R是A上一个等价关系，则S也是A上的一个等价关系。3.设I为整数集合，函数IIIIf:定义为：xyyxyxf,),(，证明：f不是单射也不是满射。