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

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

亲爱的读者：

本文内容由我和我的同事精心收集整理后编辑发布到文库，发布之前我们对文中内容进行详细的校对，但难免会有错误的地方，如果有错误的地方请您评论区留言，我们予以纠正，如果本文档对您有帮助，请您下载收藏以便随时调用。下面是本文详细内容。

最后最您生活愉快 ~O(∩_∩)O ~

《离散数学》试卷第1 页共 4 页

《 离散数学 》试卷 第 1 页 共 4 页

安徽大学20 09 — 20 10 学年第 1 学期 《 离散数学 》考试试卷（A 卷）

（时间120分钟）

院/系 专业 姓名 学号

一、单项选择题（每小题2分，共20分）

1. 设:P 天没下雪，:Q 我去镇上，则命题“天正在下雪，我没去镇上”可符号化为（ ）

A.Q P ?→?；

B. P Q ?→?；

C.Q P ?∧；

D. Q P ?∧?。 2.下列命题是重言式的是（ ）

A.)()(P Q Q P →∧→；

B. )()(Q P P Q P ???∧；

C. )(Q P Q P →→∧；

D. Q P R Q P ∧?∧?∨→))((。

3. 设解释R 如下：论域D 为实数集，0=a ，y x y x f -=),(，y x y x f <=),(。下列公式在R 下为真的是( )

A.))),(),,((),((z y f z x f A y x A z y x →???；

B.)),,((a x a f xA ?；

C.)),,((x y x f yA x ??；

D.))),,((),((a a x f A y x A y x →??。 4. 对任意集合,,A B C ，下列结论正确的是（ ）

A. C A C B B A ???∧?][；

B. C A C B B A ∈??∧∈][；

C. C A C B B A ???∧∈][；

D. C A C B B A ∈?∈∧?][。

5. 关于},,{c b a X =到}3,2,1{=Y 的函数{,1

,,1,,3}f a b c =<><><>，下列结论不正确的是（ ）

A 、1({3}){}f c -=；

B 、1(3)f c -=；

C 、({}){3}f c =；

D 、()3f c =。 6. 设I 为整数集合，则I 上的二元关系}4|||,{=-><=y x y x R 具有（ ）

A.自反性和对称性；

B.反自反性和对称性；

C.反自反性和传递性；

D.反对称性和传递性。

《 离散数学 》试卷 第 2 页 共 4 页

7. 设R 为非空集合A 上的关系R 的逆关系，则下列结论不成立的是（ ）

A.若R 为偏序，则R 为偏序；

B.若R 为拟序，则R 为拟序；

C.若R 为线序，则R 为线序；

D.若R 为良序，则R 为良序。

8. 设1π和2π是非空集合A 的划分，则下列结论正确的是（ ）

A. 1π细分21ππ?；

B. 1π细分21ππ+；

C. 非空集合A 的划分1

2ππ细分1π； D. 1π细分非空集合A 的划分12ππ。

9. 设},,{c b a X =，X I 是X 上恒等关系，要使R a b a c c b b a I X ?><><><><?},,,,,,,{为X 上的等价关系，R 应取( )

A. },,,{><><c a a c ；

B. },,,{><><a b b c ；

C. },,,{><><a b a c ；

D. },,,{><><b c c a 。

10. 设N 和R 分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合是（ ）

A.R ；

B.N N ；

C.()N ρ；

D.n N （n N ∈）。

二、判断题（每小题2分，共10分。对的打√，错的打×） 1.（ ）P Q P ?∧∧)(为矛盾式。 2.（ ）A 、B 、C 是任意集合，如果B A C A ?=?，一定有C B =。

3.（ ）若集合A 上的二元关系R 是对称的，R 的绝对补R 一定是对称的。

4.（ ）有理数集是可数的。

5.（ ）若函数f ，g 为单射，则它们的复合函数也为单射的。

三、填空题（每小空2分，共20分）

1．设)(x R ：x 是实数，)(x Q ：x 是有理数，)(x Z ：x 是整数，则 “有理数都是实数，但实数并非都是有理数”符号化为： ；

“不是这样情况：某些整数不是有理数”符号化为： 。

2. 设集合},,{c b a A =，},{b a B =， 那么 )()(A B ρρ-= ____ __ ；)(A B -ρ= ____ __。

3. 设}5,4,3,2,1,0{=A ，则定义在集合A 上二元关系}2(|,{<∧=?><=k ky x k y x R 的关系矩阵为

《 离散数学 》试卷 第 3 页 共 4 页

R M =＿＿＿＿＿＿＿＿＿＿ ；=)(R t M ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。

4. 设]1,0[=U ，]1,21[=A ，13(,)44

B =，则()A B x ψ=＿＿＿＿＿＿＿＿＿＿，()A B x ψ⊕=＿＿＿

＿＿＿＿＿＿＿。 5.设N 为自然数集合，Q 为有理数集合，R 为实数集合，则||Q N ? ||N ，||Q R - ||Q （填

=，>，<）。

三、解答题（每小题10分，共20分） 1. 求))(()(R Q P R Q P ?∧?→?∧∧→的主析取范式和主合取范式。

2. 给定集合}6,5,4,3,2,1{=A 上的偏序关系

A I R ?><><><><><><><><><=}1,5,3,5,1,3,1,4,3,4,2,4,1,6,1,2,2,6{。

求：（1）给出了偏序集合,A R <>的哈斯图；（2分）

（2）完成下表。（每空2分）

《 离散数学 》试卷 第 4 页 共 4 页

四、证明题（每小题10分，共30分）

1. 用推理规则证明： ))()(())()(())()((x P x R x Q x R x x Q x P x ?→→?→??→?。

2. 设R 1是A 上的等价关系，R 2是B 上的等价关系，A ≠?且B ≠?。关系R 满足：<<x 1，y 1>，<x 2，y 2>>∈R ?<x 1，x 2>∈R 1且<y 1

，y 2>∈R 2，证明R 是A ×B 上的等价关系。

《 离散数学 》试卷 第 5 页 共 4 页

3. 设I 为整数集合，E 为偶数集合，函数E E I I f ?→?:定义为：>-+=<><y x y x y x f ,),(，

证明：f 是双射函数。

《 离散数学 》试卷 第 1 页 共 2 页

安徽大学20 07 —20 08 学年第 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.))()(())()((x Q x R x x R x Q x ?∧?∧→?或))()(())()((x Q x R x x R x Q x →??∧→?； ))()((x Q x Z x ?∧??或))()((x Q x Z x →?。

2. }},,{},,{},,{},{{)()(c b a c b c a c A B =-ρρ；

}}{,{)(c A B φρ=-。

3. R M =????????????????1000001000

001000001011111；)(R t M =???????

?????????1000001000001000001011111 4. ???=?01)(x B A ψ )2

1,41(]1,21[]41,0[∈?∈x x 当当； ()A B x ψ⊕=???01 )4

3,21[]41,0[]1,43[)21,41(?∈?∈x x 当当 5. ||Q N ? = ||N ；||Q R - > ||Q 。

三、解答题（每小题10分，共30分）

1. ))(()(R Q P R Q P ?∧?→?∧∧→

)()(R Q P R Q P ?∧?∨∧∧∨?? 2分 )()()()(R P Q P R P Q P ?∨∧?∨∧∨?∧∨?? 4分 )()()(R Q P R Q P R Q P ?∨?∨∧∨?∨∧?∨∨?

《 离散数学 》试卷 第 2 页 共 2 页

)()()(R Q P R Q P R Q P ∨?∨?∧?∨∨?∧∨∨?∧ )6,5,4,3,2,1(π?(主合取范式) 8分 )7,0(∑?（主析取范式） 10分 2. （1）,A R <>的哈斯图为

2分

（2）（空2分）

10分

四、证明题（每小题10分，共30分）

1. 根据CP 规则，上式等价于

))()(())()(())()((x P x R x Q x R x x Q x P x ?→??→?∧→? 2分 而

))()(())()((x Q x R x x Q x P x ?→?∧→?

)))()(())()(((x Q x R x Q x P x ?→∧→?? 10Q 4分

)))()(())()(((x Q x R x P x Q x ?→∧?→??? 245,E E 6分 ))()(())()((x Q x R x P x Q ?→∧?→?? 1Q 8分 )()(x P x R ?→? 6I 10分 所以，))()(())()(())()((x P x R x Q x R x x Q x P x ?→→?→??→?

5

《 离散数学 》试卷 第 3 页 共 2 页

2. 证明 对任意的<x ，y >∈A ×B ，由R 1是A 上的等价关系可得<x ，x >∈R 1，由R 2是B 上的等价关系可得<y ，y >∈R 2。再由R 的定义，有<<x ，y >，<x ，y >>∈R ，所以R 是自反的。 2分

对任意的<x ，y >、<u ，v >∈A ×B ，若<x ，y >R <u ，v >，则<x ，u >∈R 1且<y ，v >∈R 2。由R 1对称得<u ，x >∈R 1，由R 2对称得<v ，y >∈R 2。再由R 的定义，有<<u ，v >，<x ，y >>∈R ，即<u ，v >R <x ，y >，所以R 是对称的。 6分

对任意的<x ，y >、<u ，v >、<s ，t >∈A ×B ，若<x ，y >R <u ，v >且<u ，v >R <s ，t >，则<x ，u >∈R 1且<y ，v >∈R 2，<u ，s >∈R 1且<v ，t >∈R 2。由<x ，u >∈R 1、<u ，s >∈R 1及R 1的传递性得<x ，s >∈R 1，由<y ，v >∈R 2、<v ，t >∈R 2及R 2的传递性得<y ，t >∈R 1。再由R 的定义，有<<x ，y >，<s ，t >>

∈R ，即<x ，y >R <s ，t >，所以R 是传递的。 10分

综上可得，R 是A ×B 上的等价关系。

3.（1）1122,,,x y x y I I ?<><>∈?，若),(),(2211><=><y x f y x f ，即

>-+>=<-+<22221111,,y x y x y x y x ，则?????-=-+=+2

2112211y x y x y x y x ，

易得21x x =且21y y =，因此1122,,x y x y <>=<>，所以f 是单射函数。 4分

（2）取任意E E q p ?>∈<,，若存在I I y x ?>∈<,，使>=<><q p y x f ,),(，

则有?????=-=+q y x p y x ，易得???

????-=+=22q p y q p x ，由于E q p ∈,，从而存在I k k ∈21,，使212,2k q k p ==，

于是?????-=+=2

121k k y k k x

所以有I y I x ∈∈,。因此对于E E q p ?>∈<,，总存在,x y I I <>∈?，使得>=<><q p y x f ,),(，

所以f 是满射函数。 9

分

综上所述，f是双射函数。 10分

结尾处，小编送给大家一段话。米南德曾说过，“学会学习的人，是非常幸福的人”。在每个精彩的人生中，学习都是永恒的主题。作为一名专业文员教职，我更加懂得不断学习的重要性，“人生在勤，不索何获”，只有不断学习才能成就更好的自己。各行各业从业人员只有不断的学习，掌握最新的相关知识，才能跟上企业发展的步伐，才能开拓创新适应市场的需求。本文档也是由我工作室专业人员编辑，文档中可能会有错误，如有错误请您纠正，不胜感激！

At the end, Xiao Bian gives you a passage. Minand once said, "people who learn to learn are very happy people.". In every wonderful life, learning is an eternal theme. As a professional clerical and teaching position, I understand the importance of continuous learning, "life is diligent, nothing can be gained", only continuous learning can achieve better self. Only by constantly learning and mastering the latest relevant knowledge, can employees from all walks of life keep up with the pace of enterprise development and innovate to meet the needs of the market. This document is also edited by my studio professionals, there may be errors in the document, if there are errors, please correct, thank you!

《离散数学》试卷第4 页共 2 页

本文来源：https://www.bwwdw.com/article/6ov1.html