离散数学试卷十五试题与答案

1、试卷十五试卷与答案一、填空 20% （每空 2 分）A1、 如果有限集合 A 有 n 个元素，则 |2 |= 。2、 某集合有 101 个元素，则有个子集的元素为奇数。3、 设 S=a 1，a2, ， a8 ， Bi 是 S 的子集，由B17 表达的子集为，子集a 2,a6,a7 规定为。4、 由 A 1， A 2, ， A n，生成的最小集的形式为，它们的并为集，它们的交为集。5、 某人有三个儿子，组成集合A=S 1,S2,S3 ，在 A 上的兄弟关系具有性质。6、每一个良序集必为全序集，而全序集必为良序集。7、若 f : AB 是函数，则当 f 是 AB 的， f c : BA 是 f 的

2、逆函数。二、选择 15% （每小题 3 分）1、集合B, ,的幂集为（）。A、, , ；B、, , , , , ,B ；C、 , , , , , , , , , B ；D、,，, , B2、 下列结果正确的是（）。A、(A B)A B；B、(A B)A；C、 (A B) BA ；D 、；E、 ；F、A A=A 。3、集合AB 的最小集范式为（）（由A 、B、C 生成）。(ABC)(ABC)(ABC)A、(ABC)(ABC)(ABC)；B、( AB) (AB)( AB) ；(ABC)(ABC)(ABC)C、( A BC)(ABC)(ABC)；D、1 / 5(A B) (A B)( AB) 。4、

3、 在（）下有 ABA 。A、A B；B、BA；C、 AB；D、 A或 B5、 下列二元关系中是函数的有（）。A 、 R x, y| xN y Nx y 10 ；B、 R x, y | xR y R y x 2 ；C、 R x, y | x R y R x y 2 。三、 15%用 Warshall 算法，对集合 A=1 ， 2 ， 3 ， 4， 5 上二元关系R=<1,1>,<1,2>,<2,4>,<3,5>,<4,2>求 t（R）。四、 15%集合 C* abi | i 21, a, b是任意实数 ，a 0 ， C* 上定义关系R

4、a bi , cdi | ac0 ，则 R 是 C* 上的一个等价关系，并给出R 等价类的几何说明。五、计算 15%1、 设 A=1 ， 2，3， 4 ， S=1 ， 2 ，3 ， 4 ，为 A 的一个分划，求由S 导出的等价关系。（4分）2、 设为整数集，关系 R a, b | a, b Z a b (mod k ) 为 Z 上等价关系，求 R的模 K 等价关系的商集Z/R ，并指出 R 有秩。（ 5 分）3、 设 A=1 ， 2，3， 4， 5 ， A 上的偏序关系为求 A 的子集 3 ，4， 5 和 1 ，2， 3 ，的上界，下界，上确界和下确界。（ 6 分）2 / 5六、证明 20%1

5、、 假定 f : AB, g : BC ，且 g f 是一个满射， g 是个入射，则f 是满射。（10分）2、 设 f ，g 是 A 到 B 的函数， fg 且 domgdomf ，证明 fg 。（ 10 分）答案一、填空 20%（每空 2 分）1、 2n； 2、2100 ；3 、 a 4， a8 ， B 01000110（B70）；4、?Ai 或 Ai ) ，全集，； 5、反自反性、对称性、传递性；6、A1A2An ( Ai有限； 7、双射。二、选择15% （每小题3 分）题目12345答案BB，ADBE三、 Warshall 算法 15%1100000010M R0000101000解：0

6、0000i 1时， MR1,1=1,A= MRi 2 时， M1,2=M4,2=111010000100000101010A=00000i3时， A 的第三列全为0，故 A 不变i4时， M1,4=M2,4=M4,4=13 / 511010010100000101010A= 00000i 5 时， M3,5=1，这时11010010100000101010A=00000所以 t (R)=<1,1>, <1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>。四、 5%证明：

7、对称性：abiC * ,cdiC * 且abi, cdiR , ac0ca0,cdi ,a biR 。自反性：abiC * (a0),aa0abi, abiR传递性：若abiC * ,cdi C * ,e fiC *当abi ,cdiR 且cdi , efiR则ac0, ce0,acce0即 ae0abi , e fiR所以 R 是 C* 上等价关系。R 两等价类：五、计算 15%1 z | zabi , a0右半平面 ；2 z | zabi , a0左半平面 。1、（ 4分）R=<1,1>,<2,2>,<2,3>,<3,2>,<3,3><4,4> 。2、（ 5分） Z/R=0 ， 1 ， ， k-1 ，所以 R 秩为 k。3、（ 6分） 3 ， 4， 5 ：上界： 1， 3；上确界： 3；下界：无；下确界：无；1 ， 2，3 ：上界： 1；上确界： 1；下界： 4；下确界： 4。六、证明 20%1、（ 10 分）证明：bB ，由于 g 是入射，所以存在唯一 c C 使 g(b)c ，又 g f满射，对上述c 存在 aA ，使得 g f (a)c ，也即 g ( f (a)c ，由 g 单射，所以f ( a) b 即：bB 均存在 aA使得 f (a)b ，所以 f 满射。4 / 52、（ 10