《离散数学》(上)试卷(A卷)及参考答案

《离散数学》试卷第1页共4页安徽大学2009—2010学年第1学期《离散数学》考试试卷（A卷）（时间120分钟）院/系专业姓名学号题号一二三四五六七总分得分一、单项选择题（每小题2分，共20分）1.设:P天没下雪，:Q我去镇上，则命题“天正在下雪，我没去镇上”可符号化为（D）A.QP；B.PQ；C.QP；D.QP。2.下列命题是重言式的是（C）A.)()(PQQP；B.)()(QPPQP；C.)(QPQP；D.QPRQP))((。3.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):xy.下列公式在R下为真的是()A.(x)(y)(z)(A(x,y)→A(f(x,z),f(y,z)))B.(x)A(f(a,x),a)C.(x)(y)（A(f(x,y),x))D.(x)(y)(A(x,y)→A(f(x,a),a))4.对任意集合,,ABC，下列结论正确的是（B）A.CACBBA][；B.CACBBA][；C.CACBBA][；D.CACBBA][。5.9．关于{,,}Xabc到{1,2,3}Y的函数{,1,,1,,3}fabc，下列结论不正确的是（）A、1({3}){}fc；B、1(3)fc；C、({}){3}fc；D、()3fc。6.设I为整数集合，则I上的二元关系}4|||,{yxyxR具有（B）A.自反性和对称性；B.反自反性和对称性；C.反自反性和传递性；D.反对称性和传递性。7.设R为非空集合A上的关系R的逆关系，则下列结论不成立的是（D）A.若R为偏序，则R为偏序；B.若R为拟序，则R为拟序；C.若R为线序，则R为线序；D.若R为良序，则R为良序。8.设1和2是非空集合A的划分，则下列结论正确的是（B）A.1细分21；B.1细分21；C.非空集合A的划分12细分1；D.1细分非空集合A的划分12。得分《离散数学》试卷第2页共4页9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取(D)A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}10.设N和R分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合是（D）A.R；B.NN；C.()N；D.nN（nN）。二、判断题（每小题2分，共10分。对的打√，错的打×）1.（）命题联结词{，，}是最小联结词组。2.（）（PQ）P为矛盾式。3.（）（（PQ）（QR））（PR）为重言式。4.（）A、B、C是任意集合，如果AC=AB，一定有B=C。5.（）若集合A上的二元关系R是对称的，R的绝对补R一定是对称的。6.（）R是A上的二元关系，R是自反的，当且仅当r(R)=R。7.（）集合A上的等价关系确定了A的一个划分。8.（）有理数集是可数的。9.（）若函数f，g为单射的则其复合函数也为单射的。10.（）R是集合A上的关系，R有传递性的充要条件是RoRR。二、填空题（每小空2分，共20分）1．设)(xR：x是实数，)(xQ：x是有理数，)(xZ：x是整数，则“有理数都是实数，但实数并非都是有理数”符号化为：；“有理数都是实数但并非都是整数”符号化为：。3.设集合A＝{a,b,c},B={a,b},那么ρ(B)－ρ(A)=______。ρ(B-A)=______2.设}5,4,3,2,1,0{A，则定义在集合A上二元关系}2(|,{kkyxkyxR的关系矩阵为＿＿＿＿＿＿＿＿＿＿。)(RtM＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。6.设]1,0[U，]1,21[A，13(,)44B，则()ABx＿＿＿＿＿＿＿＿＿＿，()ABx＿＿＿＿＿＿＿＿＿＿。设N为自然数集合，Q为有理数集合，R为实数集合，则|NXQ||N|，|R-Q||Q|（填=，，）三、解答题（每小题10分，共20分）1.求))(()(RQPRQP的主析取范式和主合取范式。得分。得分《离散数学》试卷第3页共4页3.给定集合{1,2,3,4,5,6,7}A上的偏序关系R={}。集合最大元最小元极大元极小元{2,3,4}B13245《离散数学》试卷第4页共4页集合上界下界上确界下确界{3,4,5,6}C（1）给出了偏序集合,AR的哈斯图(2)求出A的最小元素和最大元素，如果不存在，则指出不存在。（3）求出A的极小元素和极大元素；(4)令}4,3,2{B，}5,4,3{C，分别求出B和C的最大、最小、极大、极小元及其上界、下界、最小上界和最大下界。四、证明题（每小题10分，共30分）1.设I为整数集合，函数:fIIII定义为：(,),fxyxyxy，证明：f是单射的但不是满射的。得分《离散数学》试卷第5页共4页2.设R是集合{1,2,3,4,5}A上的关系{(1,1),(1,3),(2,2),(2,5),(3,1),(3,3),(4,4),(5,2),(5,5)}R（1）画出R的关系图;（2）证明R是等价关系；（3）写出R的所有等价类。2.用推理规则证明：))()(())()(())()((xPxRxQxRxxQxPx。《离散数学》试卷第6页共4页3.设R为实数集合，Q为整数集合，证明：cQR||。《离散数学》试卷第1页共2页安徽大学2007—2008学年第1学期《离散数学》考试试题（A卷）参考答案及评分标准一、单项选择题（每小题2分，共20分）1.D；2.C；3.A；4.B；5.C；6.B；7.D；8.B；9.D；10.D。二、填空题（每小空2分，共20分）1.},4,2,0,2,4{]0[2,},5,3,1,1,3{]1[2；2.1000001000001000001011111；3.162，15；4.0101010111010101)(RtM；5.双，满，单；6.01)(xA时当时当210121xx。三、解答题（每小题10分，共30分）1.))(()(RQPRQP)()(RQPRQP2分)()()()(RPQPRPQP4分)()()(RQPRQPRQP)()()(RQPRQPRQP)6,5,4,3,2,1((主合取范式)8分)7,0(（主析取范式）10分2.{(1,1),(1,3),(2,2),(2,5),(3,1),(3,3),(4,4),(5,2),(5,5)}R.(1)R的关系图4分(2)因为R满足自反、对称和传递性，所以R是等价关系；3分(3)等价类：{1,3},{2,5},{4}。3分31524《离散数学》试卷第2页共2页3.（1）,AR的有向图为2分（2）A的最小元素不存在，最大元素是1；4分（3）A的极小元为：4，5；极大元为；16分（4）B最大元素不存在，最小元素为：4，极大元为：2，3，极小元为：4，上界为：1，下界为：4，上确界为1，下确界为：4；8分C的最大元素为：3，最小元素不存在，极大元为：3，极小元为：4，5，上界为：1，3，下界不存在，上确界为3，下确界不存在。10分四、证明题（每小题10分，共30分）1.（1）1122,,,xyxyII，若),(),(2211yxfyxf，即22221111,,yxyxyxyx，则22112211yxyxyxyx，3分易得21xx且21yy，因此1122,,xyxy，所以f是单射函数。5分（2）取,0,1pqII，对,xy，若qpyxf,),(，则有01xypxyq，易得1/21/2xy，但,1/2,1/2xyII，8分所以对于,pqII，不存在,xyII，使得qpyxf,),(，所以f不是满射的。10分2.根据CP规则，上式等价于))()(())()(())()((xPxRxQxRxxQxPx2分《离散数学》试卷第3页共2页而))()(())()((xQxRxxQxPx)))()(())()(((xQxRxQxPx10Q4分)))()(())()(((xQxRxPxQx245,EE6分))()(())()((xQxRxPxQ1Q8分)()(xPxR6I10分所以，))()(())()(())()((xPxRxQxRxxQxPx3.设RQRf:，()fxx，则f是从QR到R的单射函数，所以cRQR||||。3分构造从]1,0[到QR的函数QRg]1,0[:如下：xxxg2)(QxQx]1,0[]1,0[8分则g是从]1,0[到QR的单射函数（双射函数），所以cQR|]1,0[|||。综合以上，||||RNR。10分