05级计算机《离散数学》期中考试试卷 南京大学计算机科学与技术系 Apr.21,2006 A,B,C为任意集合。判断下列等式是否成立,给出证明或给出反例: 1.C∩(A⊕B)=(CnA)(C∩B 2.CU(A⊕B)=(CUA)⊕(CUB) N是自然数集。在N×Ⅳ上定义关系R如下 jk)R(m,n)当且仅当max(j,k)=max(m,m) 1.证明R是等价关系。 2.写出其等价类的一般形式。 3.是否存在两个不同的等价类等势?说出理由。 4.证明:N×Ⅳ/R与自然数集等势 315p X是至少含两个元素的集合。X′=p(X)-{0}-{X} 1.偏序集(X,)是否有最大元,最小元? 2.求:偏序集(X′,)的所有极小元的集合Xmim,所有极大元的集合 Xmas 3.证明:Xmin与X等势。 415p 给定函数f:A→B,若Y≌B,定义f2(Y)={x|x∈A,f(x)∈Y}。证明:对B的任意非 空子集Y,f(Y)非空的充分必要条件是∫是满射 证明:随于任意正整数η,模n的整数加群(Zn,+n)是整数加群(Z,+)的商群 G是奇数阶有限群。证明:对任意x∈G,存在唯一的y∈G,满足:x=y2。 用1,2,3三个数字组成n(n≥3)位数,数字可以重复,且在每个n位数中每个数字至少出现 次。利用容斥原理求满足上述条件的n位数有多少个。 CompilEdbyzhuyin.nju@gmail.com
05级计算机《离散数学》期中考试试卷 南京大学计算机科学与技术系 Apr. 21, 2006 1 15pts A, B, C 为任意集合。判断下列等式是否成立，给出证明或给出反例： 1. C ∩ (A ⊕ B) = (C ∩ A) ⊕ (C ∩ B) 2. C ∪ (A ⊕ B) = (C ∪ A) ⊕ (C ∪ B) 2 15pts N 是自然数集。在 N × N 上定义关系 R 如下： h j, k i R h m, n i 当且仅当 max(j, k) = max(m, n) 1. 证明 R 是等价关系。 2. 写出其等价类的一般形式。 3. 是否存在两个不同的等价类等势？说出理由。 4. 证明：N × N/R 与自然数集等势。 3 15pts X 是至少含两个元素的集合。X0 = ρ(X) − { ∅ } − { X }。 1. 偏序集 (X0 , ⊆) 是否有最大元，最小元？ 2. 求：偏序集 (X0 , ⊆) 的所有极小元的集合 Xmin，所有极大元的集合 Xmax。 3. 证明：Xmin 与 X 等势。 4 15pts 给定函数 f : A → B，若 Y ⊆ B，定义 f 1 (Y ) = { x | x ∈ A, f(x) ∈ Y }。证明：对 B 的任意非 空子集 Y ，f 1 (Y ) 非空的充分必要条件是 f 是满射。 5 15pts 证明：随于任意正整数 n，模 n 的整数加群 (Zn, +n) 是整数加群 (Z, +) 的商群。 6 15pts G 是奇数阶有限群。证明：对任意 x ∈ G，存在唯一的 y ∈ G，满足：x = y 2。 7 10pts 用 1, 2, 3 三个数字组成 n(n ≥ 3) 位数，数字可以重复，且在每个 n 位数中每个数字至少出现一 次。利用容斥原理求满足上述条件的 n 位数有多少个。 Compiled by zhuyin.nju@gmail.com 1