安徽大学离散数学上试卷及参考复习资料

1、安徽大学20 09 20 10学年第1学期离散数学考试试卷（A卷）得 分)、单项选择题（每小题2分，共20分）（时间120分钟）院/系 专业 姓名 学号题号一一二四五六七总分得分.设P:天没下雪，Q:我去镇上，则命题 天正在下雪，我没去镇上 ”可符号化为（A. p q ；B.P；C.下列命题是重百式的是A. (P Q) (QP);B.(PP) (PQ);C. P Q (PQ) .，D.(P(QR)Q。3.设解释R如下：论域D为实数集,f(x,y)f （x, y） x y。下列公式在R下为真的是（）4.5.6.7.a. x y z(A(x, y) A( f (x, z), f (y, z)；C.

2、 x yA( f (x, y), x);对任意集合 A, B,C ,下列结论正确的是（A.C.关于A、B.xA( f(a,x), a)；D.x y(A(x,y) A( f (x,a),a)。A B B CA B B CX a,b,c到 Yf 1(3)c;AC； B.AC; D.1,2,3的函数fB、f 1(3) c；设I为整数集合，则I上的二元关系R A.自反性和对称性；B.反自反性和对称性;设飙非空集合A上的关系R的逆关系,AA a,1CC,b,1 ,C 、f (c)c,33；x, y |x y | 4具有C.反自反性和传递性;则下列结论不成立的是（C；,下列结论不正确的是（D 、 f(c)

3、 3。D.反对称性和传递性。A.若R为偏序,则R为偏序;B.若R为拟序，则为拟序;C.若R为线序,D.若R为良序，则F%为良序。8.设1和2是非空集合 A的划分，则下列结论正确的是(A. 1 细分 1? 2； B.1细分i2 ； C.非空集合A的划分1 I 2细分1 ； D.1细分非空集合A的划分1 U 29.设X a,b,c , Ix是X上恒等关系，要使Ix a,bb,c , c,ab,a R为X上的等价关系，R应取()A. c, a , a,c ;B. c,b , b,a ;C. c, a , b,a ；D. a,c , c,b 。10.设N和R分别为自然数和实数集合,则下列集合中与其他集

4、合的基数不同的集合是(A. R; B. NN ; C. (N) ; D. Nn ( n N )。.、判断题(每小题2分，共10分。对的打，错的打X).() (P Q)P为矛盾式。得 分. () A、B、C是任意集合，如果A C A B, 一定有B C。.()若集合A上的二元关系 R是对称的，R的绝对补R 一定是对称的。.()有理数集是可数的。.()若函数f, g为单射，则它们的复合函数也为单射的。三、填空题(每小空2分，共20分)得 分1.设R(x) : x是实数,Q(x) ： x是有理数，Z(x) ： x是整数，则“有理数都是实数，但实数并非都是有理数”符号化为： “不是这样情况：某些整数不

5、是有理数”符号化为： .设集合 A a,b,c, B a,b,那么(B)(A) =； (BA) =.设A 0,1,2,3,4,5,则定义在集合A上二元关系R x, y| k(x ky k2的关系矩阵为Mr=； M t(R) 1 一 1 3.设 U 0,1 A 二,1，B (一,一)，贝U AUB(x) ， A B(x) 24 4.设N为自然数集合，Q为有理数集合，R为实数集合,则 |N Q| | N |, | R Q| |Q| (填=,)。、解答题（每小题10分，共20分）得 分.求（P Q R） （ P （ Q R）的主析取范式和主合取范式。.给定集合A 1,2,3,4,5,6上的偏序关系R

6、 6,2 , 2,1 , 6,1 , 4,2 , 4,3 , 4,1 , 3,1 , 5,3 , 5,1 相。求：（1）给出了偏序集合A,R 的哈斯图；（2分）（2）完成下表。（每空2分）集合取大兀最小元极大兀极小元B 2,3,4集合上界下界上确界下确界C 3,4,5,6四、证明题（每小题10分，共30分）.用推理规则证明：x(P(x) Q(x) x(R(x) Q(x)(R(x)P(x)。.设Ri是A上的等价关系，R是B上的等价关系，A丰 且Bw。关系R满足：,CR 6兄且CR2,证明R是AX B上的等价关系。. 设 I 为整数集合， E 为偶数集合，函数 f : I I E E 定义为： f

7、 ( x, y ) x y,x y证明： f 是双射函数。安徽大学20 07 20 08学年第1学期离散数学考试试题（A卷）参考答案及评分标准、单项选择题（每小题2分，共20分）8.B ; 9.D ; 10.D。二、判断题（每空2分,共10分）V, 2. X, 3.、填空题（每小空2分，共20分）1.x(Q(x)R(x) x(R(x) Q(x)或x(Q(x) R(x)x(R(x) Q(x);2.3.4.x(Z(x)(B)(B A)10M R= 000A B (x)Q(x)或 x(Z(x) Q(x)。(A)11000 c, a,c, b,c, a,b, c,c。10100100101000110

8、；M t(R) = 0001100010100100101000110,幻4,1百1.,1) TOC o 1-5 h z w/1 1、,3 -当x(-,) ,1B( x)4 2411 3当x叼Q4)5.|NQ| j| N |；|RQ Q |。解答题（每小题10分,共30分）1. (PQ R) ( PR)R)(PR)Q)P R)(PQ) (PR)(PR)(PR) (PR)R)R) ( P Q R)(1,2,3,4,5,6)(主合取范式)10(0,7)(主析取范式)(1)A, R的哈斯图为P(x)2分Q104分E5,E246分Q18分I 610分(R(x)P(x)(2)(空2分)集合取大兀最小元极

9、大兀极小元B 2,3,4不存在42, 34集合上界下界上确界下确界C 3,4,5,61不存在1不存在10分四、证明题(每小题10分，共30分)1.根据CP规则，上式等价于x(P(x) Q(x) x(R(x) Q(x)(R(x)而x(P(x) Q(x) x(R(x) Q(x) x(P(x)Q(x) (R(x)Q(x)x( Q(x) P(x) (R(x)Q(x)(Q(x)P(x) (R(x)Q(x)R(x) P(x) 所以， x(P(x) Q(x) x(R(x) Q(x)2.证明对任意的CAXB,由Ri是A上的等价关系可得CRi,由R是B上的等价关系可得CR。再由R的定义，有, R,所以R是自反的。2 分对任意的 、C AX B,若 R,则 CR 且C R2。由 Ri 对称得 e Ri,由R2对称得e R2o再由R的定义，有, CR,即 R,所以 R是分对任意的 、CAXB,若 R 且 R,贝 U CR 且 e R2,CRi且 R20由 CRi、eRi 及 Ri 的传递性得CRi,由 R2、e R2及R2的传递性得e Rio再由R的定义，有, CR,即 R,所以10R是传递的。综上可得，R是AX B上的等价关系。3. (i)Xi, yiX2,y2 Ixi，yi )f(X2，y2)，即Xiyi, XiyiX2y2,X