《离散数学》课程教学资源（试卷习题）试卷（答案）15

离散数学试卷（十五）参考答案 一、填空20%（每空2分） 1、2:2、2:3、{a,a,B01mu10(B0片4AnA2.nA.(A,=A或A),全 集，中：5、反自反性、对称性、传递性：6、有限：7、双射。 二、选择15%（每小题3分） 题目12345 答案BB,EADB 三、Warshall算法15% (11000 00010 解：MR=00001 01000 00000 i=1时，MRL,]=l,A=M8 1=2时，M1,2=M4,2=1 (11010 00010 A=00001 01010 (00000 1-3时，A的第三列全为0，故A不变 1=4时，M1,4=M2,4=M4,4= 11010 01010 A=00001 i=5时，M3,5=1,这时 01010 00000 (11010 888 01010 (00000

离散数学试卷（十五）参考答案 99 一、填空 20%（每空 2 分） 1、2 n；2、2 100；3、{a4，a8}，B01000110（B70）；4、 ) ˆ ( ˆ ˆ ˆ A1  A2  An Ai = Ai或Ai ，全 集，  ；5、反自反性、对称性、传递性；6、有限；7、双射。 二、选择 15%（每小题 3 分） 题目 1 2 3 4 5 答案 B B，E A D B 三、Warshall 算法 15% 解：                 = 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 M R i = 1 时， MR [1,1]=1, A = MR i = 2 时，M[1,2]=M[4,2]=1 A=                 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 i = 3 时，A 的第三列全为 0，故 A 不变 i = 4 时，M[1,4]=M[2,4]=M[4,4]=1 A=                 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 i = 5 时，M[3,5]=1 ，这时 A=                 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0

离散数学试卷（十五）参考答案 所以t(R)={1,1>,<1,2>,<1,4,<2,2>,<24,<3,5>,4,2>,<4,4}。 四、5% 证明： 对称性：a+bi∈C·,c+dh∈C'且<a+bi,c+dh>∈R,ac>0 ca>0.:.<c+di,a+bi>ER. 自反性：a+bi∈C(a≠0)，aa>0∴.<a+bi,a+bi>∈R 传递性：若a+bieC,c+ieC,e+ieC 当<a+bi,c+dh>eR且<c+di,e+fi>eR则 ac>0,ce>0,∴.acce>0即ae>0∴.<a+bi,e+f>eR 所以R是C*上等价关系。 R两等价类：元，={：=a+bi,a>0右半平面 元2={e|:=a+bi,a<0}左半平面. 五、计算15% 1、(4分)R={<1,1>,<2,2>,<2,3>,<3,2>,<3,3><4,4>}。 2、(5分)ZR=0,.,k},所以R秩为k。 3(6分)3,4,5：上界：1,3：上确界：3：下界：无：下确界：无 1,2,3:上界：1：上确界：1：下界：4：下确界：4。 大、证明20% 1、(10分)证明：Yb∈B,由于g是入射，所以存在唯一c∈C使g(b)=c,又go∫满射， 对上述c存在aeA,使得gof(a)=c,也即g(f(a)=c,由g单射，所以f(a)=b即：beB 均存在a∈A使得f(a)=b,所以f满射。 100

离散数学试卷（十五）参考答案 100 所以 t (R)={<1,1>, <1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>} 。 四、5% 证明： 对称性： , , , 0 * * a + bi C c + di C 且  a + bi c + di  R ac   ca  0, c + di,a + bi  R。 自反性： a + bi C (a  0), aa  0  a + bi,a + bi  R * 传递性：若 * * * a + bi C , c + di C , e + fiC ac ce acce ae a bi e fi R a bi c di R c di e fi R       + +   + +   + +  0, 0, 0 0 , , , 即 当 且 则 所以 R 是 C*上等价关系。 R 两等价类：  1 ={z | z = a + bi , a  0} 右半平面 ；  2 ={z| z = a +bi , a  0} 左半平面。 五、计算 15% 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 分）证明： b B ，由于 g 是入射，所以存在唯一 cC 使 g(b) = c ，又 g  f 满射， 对上述 c 存在 a A ，使得 g  f (a) = c ，也即 g( f (a)) = c ，由 g 单射，所以 f (a) = b 即： b B 均存在 a A 使得 f (a) = b ，所以 f 满射

离散数学试卷（十五）参考答案 2、(10分)证明： Y<x,y>eg则x∈domg且y∈rangeg→x∈domf且y∈rangeg 对上述r∈domf则妇|y'e rangef即<x,y'>ef 而∫sg<x,y'>eg但<x,y>eg由g是函数知y'=y ∴x∈domf且y∈rangef即<x,y>ef ∴f=g 101

离散数学试卷（十五）参考答案 101 2、（10 分）证明： f g x domf y rangef x y f f g x y g x y g g y y x domf y rangef x y f x y g x domg y rangeg x domf y rangeg  =             =               , , , | , , 且 即 而 但 由 是函数知 对上述 则 即 则 且 且