《离散数学 Discrete Mathematics》课程教学资源（习题集）《离散数学教程》期中试题及解答

《离散数学教程》期中考试 200年4月 学号 姓名 填空题(20分) 1设集合A={{a,b},c},则A的幂集 P(A){,{ab}{c}、{{ab}c}}。 2设R1是从A到B的二元关系,R2是从B到C的二元关系,则从A到C的 二元关系记为R1°R2, 定义R1°R2=a2c)a∈Ac∈C3b使(ab)∈R(bc)∈R2 3设R是集合A上的二元关系,定义R的传递闭包,记为R',满足: (1)R'是传递的: (2)RR (3)对任一传递关系R”,若R〓R',则R'<R”s 4设(A,≤)是偏序集合,BcA,若存在一个元素b∈B,对所有b'∈B3 都有b’≤b;则称b是B的最大元 5设集合A的划分兀={A1,,An},则由π建立A上的等价关系R, R=(Ax×A)(A2×A2…∪(An×An) 二判断下列命题是否正确,并说明理由。(括号内写“是”或“否”)(40分) 1设R和S是集合A上的二元关系,若R和S是反对称的,则R∪S是反对称 的 (否) R={(a,b),(a,c)},S={(ca),(c,d)均为反对称,R∪S={(a,b),(a,c),(c,a,(c,d)}不是反 对称。 2设集合A={a},b},则{a}cP(A) 否) P(A)={,{a},{b},{a},b},{a}不是P(A)中的元素 3设R是集合A上的二元关系,若R是对称的和反自反的,则R一定不是传 递的。 (是) 假设R是传递的,若(a,b)∈R,由于R是对称的,所以(b,a)∈R,所以(a,a)∈R 因为R是反自反的,所以与条件矛盾。 4设函数gA_→B,fBC,fog;A-C,若f和g是满射,则fog是满射

1 《离散数学教程》期中考试 200 年 4 月 学号______________ 姓名__________________________ 一 填空题（20 分） 1 设集合 A={{a, b}, c}，则 A 的幂集 P(A)={, {{a, b}}, {c}, {{a, b}, c} }。 2 设 R1 是从 A 到 B 的二元关系， R2 是从 B 到 C 的二元关系，则从 A 到 C 的 二元关系记为 R1°R2， 3 定义 R1°R2 ={(a, c) | aA, cC, b 使(a, b)R1, (b,c)R2}。 3 设 R 是集合 A 上的二元关系，定义 R 的传递闭包，记为 R’，满足： （1）R’是传递的; （2）R’R; （3）对任一传递关系 R”，若 RR”，则 R’R”。 4 设（A, ）是偏序集合，BA，若存在一个元素 bB，对所有 b’B, 都有 b’b；则称 b 是 B 的最大元。 5 设集合 A 的划分={A1, , An}，则由建立 A 上的等价关系 R， R=(A1A1) (A2A2)……(AnAn)。 二 判断下列命题是否正确，并说明理由。（括号内写“是”或“否” ）（40 分） 1 设 R 和 S 是集合 A 上的二元关系，若 R 和 S 是反对称的，则 RS 是反对称 的。 （ 否 ） R={(a, b), (a,c)}, S={(c,a), (c,d)}均为反对称，RS={(a, b), (a,c), (c,a), (c,d)}不是反 对称。 2 设集合 A={{a}, b}，则{{a}}P(A)。 （ 否 ） P(A)={, {{a}}, {b}, {{a}, b}}, {a}不是 P(A)中的元素。 3 设 R 是集合 A 上的二元关系，若 R 是对称的和反自反的，则 R 一定不是传 递的。 （ 是 ） 假设 R 是传递的，若(a, b)R，由于 R 是对称的，所以(b, a)R，所以(a, a)R， 因为 R 是反自反的，所以与条件矛盾。 4 设函数 g: AB, f: BC, f o g: AC，若 f 和 g 是满射，则 f o g 是满射

(是) 因为f是满射,所以对c∈C,3b∈B使b)=c;因为g是满射,对b∈B,彐a∈A使 g(a)=b。所以fog(a)=f(g(a)=f(b)=c。则fog是满射 5设R是集合A上的二元关系,若R是对称的和传递的,则R是自反的 (否) A={1,2,3,4},R={(1,2),(2,1),(1,1),(2,2)} 6设R是A上的二元关系,A’是A的子集,定义A’上的关系R=R∩(AxA) 如果R在A上是传递的,则R’在A’上是传递的 (是) 反证法。假设R’在A’上不是传递的,则存在(a,b),(b,c)∈R',(a,c)∈R'。因为 (a,b),(b,c)∈R,所以a,b,c∈A。所以a,c∈A×A。因为(a,c)∈R',所以(a,c)R; 因为(a,b,(b,c)∈R,所以R在A上不是传递的,导致矛盾。 三综合题(40分) 1设A={1,2,3,4,6,8,12,24},在A上定义整除关系,画出(A,/)的哈斯图, 并设BcA,试对 (1)B={1,2,3},求B的极大元和极小元 (2)B={1,2,3,6},求B的上界和下界 (1)B的极大元2,3,极小元1 (2)B的上界6,12,24,下界1。 2设正整数集合I,又设R是定义在I×上的二元关系:(a,b)R(c,d)当且仅当 axd=bxc,(即ac=b/d),证明:R是在r×I上的一个等价关系 证明: (1)对任一(a,b)∈I×I,有(a,b)R(a,b),所以R是在Ixr上的一个自反关系 (2)若(a,b)R(c,d)→a/c=b/d=ca=dhb→(c,dR(a,b),所以R是在Ixr上的一个 对称关系。 (3)若(a,bR(c,d),(c,d)R(e,f→a/c=b/d,ce=df→ae=bf→(a,b)R(e,f),所 以R是在I×I上的一个传递关系 3证明:对于集合A和B,若有A⌒B=A∪B,则A=B。 证明: A=A∩(AUB) A∩(A∩B =(A∩A)⌒B A∩B A∩(B⌒B) F(AUB)nB 4对于集合A和B,证明AcB当且仅当P(A)P(B)

2 （ 是 ） 因为 f 是满射，所以对 cC, bB 使 f(b)=c; 因为 g 是满射，对 bB，aA 使 g(a)=b。所以 f o g(a)=f(g(a))=f(b)=c。则 f o g 是满射。 5 设 R 是集合 A 上的二元关系，若 R 是对称的和传递的，则 R 是自反的。 （ 否 ） A={1, 2, 3, 4}，R={(1, 2), (2, 1), (1, 1), (2, 2) } 6 设 R 是 A 上的二元关系，A’是 A 的子集，定义 A’上的关系 R’=R(A’A’)。 如果 R 在 A 上是传递的，则 R’在 A’上是传递的； （ 是 ） 反证法。假设 R’在 A’上不是传递的，则存在(a, b), (b,c)R’，(a, c)R’。因为 (a, b), (b,c)R’，所以 a, b, cA’。所以(a, c) A’A’。因为(a, c)R’，所以(a, c) R； 因为(a, b), (b,c)R，所以 R 在 A 上不是传递的，导致矛盾。 三 综合题（40 分） 1 设 A={1, 2, 3, 4, 6, 8, 12, 24}，在 A 上定义整除关系/，画出（A, /）的哈斯图， 并设 BA，试对 （1）B={1, 2, 3}，求 B 的极大元和极小元。 （2）B={1, 2, 3, 6}，求 B 的上界和下界。 (1) B 的极大元 2,3, 极小元 1。 (2) B 的上界 6, 12, 24，下界 1。 2 设正整数集合 I + ，又设 R 是定义在 I + I+上的二元关系：(a, b)R(c, d)当且仅当 ad=bc，(即 a/c=b/d)，证明：R 是在 I + I+ 上的一个等价关系。 证明： （1）对任一(a, b) I+  I+ ，有(a, b)R(a, b)，所以 R 是在 I + I+ 上的一个自反关系。 （2）若(a, b)R(c, d) a/c=b/dc/a=d/b(c, d)R(a, b), 所以 R 是在 I + I+ 上的一个 对称关系。 （3）若(a, b)R(c, d)，(c, d)R(e, f)  a/c=b/d, c/e=d/f  a/e=b/f  (a, b)R(e, f)，所 以 R 是在 I + I+上的一个传递关系。 3 证明：对于集合 A 和 B，若有 AB=AB，则 A=B。 证明： A=A(AB) =A(AB) =(AA)B =AB =A(BB) =(AB)B =(AB)B =B 4 对于集合 A 和 B，证明 AB 当且仅当 P(A)P(B)

证明: P(AX XCA →:y∈P(A)→ycA→ycB→ycP(B) :y∈A→{y}eP(A)→{y}∈P(B)→y∈B 5证明A∩(BeC=(A∩BA(A∩C) 证明 A∩(BC) A∩(B-C)~(CB) =(A(BC)(A∩(CB) =(A∩B)(AC)(A∩C)(AB) =(A⌒B)(A∩C 6举出A={a,b,c,d}上关系R的例子,使其具有下述性质: a)既是对称的,又是反对称的; b)既不是对称的,又不是反对称的; c)是传递的。 解 a)Rl={(a,a),(b,b),(c,c)} b)R2={(a,b),(b,a),(c,d)} )R3={(a,b),(b,c),(a,c)} 7设R1和R2是A上的等价关系,C1和C2分别是A中关于R1和R2的划分。 证明:RcR2,当且仅当C1中的每个等价类是包含于C2的一些等价类之中。 证明: 关键:等价关系与等价类。 分析:在集合A上的任何一个等价关系,都可以确定一个划分(A/R),其元素 是有关等价类。所以C1=A/R1,C2=A/R2。反之,集合A上的任何一个划分都 可以确定一个等价关系 C1=A/R={C1,C12, A/R2={C21,C2 R={C1xC1lCxC.…∪Cm×C1m} R2={C21XC2C2×C22 ∪CnxC2n} RR2→对任意C1,1≤≤m,存在C2,1≤n,使得CisC2j 对任意C1,1≤m,存在C2,1≤j≤n,使得C1cC2→R≌R2

3 证明： P(A)={x | xA} ： yP(A)  yA  yB  yP(B) ： yA  {y}P(A)  {y}P(B)  yB 5 证明 A(BC)=(AB)(AC) 证明： A(BC) =A((B-C)(C-B)) =(A(B-C))(A(C-B)) =((AB)-(AC))((AC)-(AB)) = (AB)(AC) 6 举出 A={a, b, c, d}上关系 R 的例子，使其具有下述性质： a) 既是对称的，又是反对称的； b) 既不是对称的，又不是反对称的； c) 是传递的。 解： a) R1={(a,a), (b,b), (c, c) } b) R2={(a, b), (b, a), (c, d) } c) R3={(a, b), (b, c), (a, c ) } 7 设 R1 和 R2 是 A 上的等价关系，C1 和 C2 分别是 A 中关于 R1 和 R2 的划分。 证明： R1R2，当且仅当 C1 中的每个等价类是包含于 C2 的一些等价类之中。 证明： 关键：等价关系与等价类。 分析：在集合 A 上的任何一个等价关系，都可以确定一个划分（A/R），其元素 是有关等价类。所以 C1= A/ R1，C2= A/ R2。反之，集合 A 上的任何一个划分都 可以确定一个等价关系。 C1= A/ R1={C11, C12, ……, C1m} C2= A/ R2={C21, C22, ……, C2n} R1={C11C11C12C12…… C1m C1m } R2={C21C21C22C22…… C2n C2n } R1R2 对任意 C1i,1 im, 存在 C2j, 1jn，使得 C1iC2j。 对任意 C1i,1 im, 存在 C2j, 1jn，使得 C1iC2j  R1R2