安徽大学20 09 — 20 10 学年第 1 学期 《 离散数学 》考试试卷（A 卷）（时间120分钟）院/系 专业 姓名 学号一、单项选择题（每小题2分，共20分）1. 设:P 天没下雪，:Q 我去镇上，则命题“天正在下雪，我没去镇上”可符号化为（ D ）A.Q P ⌝→⌝；B. P Q ⌝→⌝；C.Q P ⌝∧；D. Q P ⌝∧⌝。
2.下列命题是重言式的是（ C ）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 为实数集，a=0, f(x,y)=x-y, A(x,y):x<y.下列公式在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. 对任意集合,,A B C ，下列结论正确的是（ B ）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. 9．关于{,,}X a b c =到{1,2,3}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 具有（ 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ππI 细分1π；D. 1π细分非空集合A 的划分12ππU 。
9. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈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.N N ；C.()N ρ；D.n N （n N ∈）。
二、判断题（每小题2分，共10分。
对的打√，错的打×）1. （ ）命题联结词{⌝，∧，∨}是最小联结词组。
2. （ ）（P ∧Q ）∧⌝P 为矛盾式。
3. （ ）（（⌝P ∨Q ）∧（Q →R ））→（P →R ）为重言式。
4.（ ）A 、B 、C 是任意集合，如果A C U =A B U ，一定有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．设)(x R ：x 是实数，)(x Q ：x 是有理数，)(x Z ：x 是整数，则“有理数都是实数，但实数并非都是有理数”符号化为： ； “有理数都是实数但并非都是整数”符号化为： 。
3. 设集合A ＝{a,b,c},B={a,b}, 那么 ρ(B)－ρ(A)= ____ __ 。
ρ(B-A) = ____ __ 2. 设}5,4,3,2,1,0{=A ，则定义在集合A 上二元关系}2(|,{<∧=∃><=k ky x k y x R 的关系矩阵为＿＿＿＿＿＿＿＿＿＿。
=)(R t M ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。
6. 设]1,0[=U ，]1,21[=A ，13(,)44B =，则()A B x ψ=U ＿＿＿＿＿＿＿＿＿＿，()A B x ψ⊕=＿＿＿＿＿＿＿＿＿＿。
设N 为自然数集合，Q 为有理数集合，R 为实数集合，则|NXQ| |N| ，|R-Q| |Q| （填=，>，<）三、解答题（每小题10分，共20分）1. 求))(()(R Q P R Q P ⌝∧⌝→⌝∧∧→的主析取范式和主合取范式。
A=上的偏序关系R={ }。
3. 给定集合{1,2,3,4,5,6,7}（1）给出了偏序集合,A R <>的哈斯图(2)求出A 的最小元素和最大元素，如果不存在，则指出不存在。
（3）求出A 的极小元素和极大元素；(4) 令}4,3,2{=B ，}5,4,3{=C ，分别求出B 和C 的最大、最小、极大、极小元及其上界、下界、最小上界和最大下界。
四、证明题（每小题10分，共30分）1. 设I 为整数集合，函数:f I I I I ⨯→⨯定义为：(,),f x y x y x y <>=<+->， 证明：f 是单射的但不是满射的。
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⌝→→⌝→∀⇒→∀。
3. 设R 为实数集合，Q 为整数集合，证明：c Q R =-||。
安徽大学20 07 —20 08 学年第 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.⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡10000010*******0001011111；3.162，15；4. ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0101010111010101)(R t M ； 5.双，满，单；6. ⎩⎨⎧=01)(x A ψ 时当时当210121<≤≤≤x x 。
三、解答题（每小题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 ⌝∨⌝∨∧∨⌝∨∧⌝∨∨⇔)()()(R Q P R Q P R Q P ∨⌝∨⌝∧⌝∨∨⌝∧∨∨⌝∧ )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分3. （1）,A R <>的有向图为2分（2）A 的最小元素不存在，最大元素是1； 4分 （3）A 的极小元为：4，5；极大元为；1 6分 （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,,,x y x y I I∀<><>∈⨯，若),(),(2211><=><y x f y x f ，即>-+>=<-+<22221111,,y x y x y x y x ，则⎩⎨⎧-=-+=+22112211y x y x y x y x ， 3分易得21x x =且21y y =，因此1122,,x y x y <>=<>，所以f 是单射函数。
5分 （2）取,0,1p q I I <>=<>∈⨯，对,x y ∀<>，若>=<><q p y x f ,),(，则有01x y p x y q +==⎧⎨-==⎩，易得1/21/2x y =⎧⎨=-⎩，但,1/2,1/2x y I I <>=<->∉⨯， 8分 所以对于,p q I I <>∈⨯，不存在,x y I I <>∈⨯，使得>=<><q p y x f ,),(，所以f 不是满射的。
10分2. 根据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 ⌝→→⌝→∀⇒→∀3. 设R Q R f →-:，()f x x =，则f 是从Q R -到R 的单射函数，所以c R Q R =≤-||||。