离散数学习题评讲2.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,集合论/二元关系/函数部分习题讲评,习题3-2,(11),证明：,a),A(B,C)=(AB),(AC),证明：,A(B,C),=A(B-C)(C-B),=(A(B-C)(A(C-B),=(AB-AC)(AC-AB),=(AB),(AC),习题33,(3),75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘坐过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.50元，公园游乐场总共收入70元，试确定有多少儿童没有乘坐过其中任何一种。,解：考虑每人乘坐一种玩具至多一次，设,集合,A：,乘坐旋转木马的儿童,B：,乘坐滑行铁道的儿童,C：,乘坐宇宙飞船的儿童,设一种东西都没有乘过的儿童数为,x,则共75个儿童，有|,ABC|+x=75,(1),20,人三种都乘过，有|,ABC|=20,(2),55,人至少乘坐过其中的两种，有,|(,AB)(AC)(BC)|=55,(3),公园共收入70元，有,|,A|+|B|+|C|=70/0.5=140,(4),因为|,ABC|,=|A|+|B|+|C|,-|AB|-|AC|-|BC|+|ABC|(5),又因为,|(,AB)(AC)(BC)|,=|AB|+|AC|+|BC|-2|ABC|(6),由(6)得,|,AB|+|AC|+|BC|=55+220=95,代入（5）式，可得,|,ABC|=140-95+20=65,代入(1)式，有,x=756510，,即共有10人没有参乘坐任何一种东西。,习题3-6,(6),设,R,是集合,X,上的一个自反关系，求证：,R,是对称和传递的，当且仅当,和,在,R,之中则有,在,R,之中。,证明：,a),证明必要性,若任意RR,因为,R,对称，有RR,R,传递，有R。,b),证明充分性,若对任意RR,R，,因为,R,自反，故对任意序偶R,有,RR,R,R,对称,对任意序偶RR,因为,R,对称，有,RR,R,R,传递。,习题3-7,(2)证明若,S,为集合,X,上的二元关系：,a),S,是传递的，当且仅当(,S,S),S,证明：,必要性,任取序偶S,S,则存在,cX,使得,SS,因为,S,传递，故,S,即,S,S,S.,充分性,对任意序偶SS,有,S,S,因为,S,S,S,故有S,S,传递,习题3-10,(2)求4元有限集上，所有的等价关系个数。,解：即求4元有限集上有多少种划分。,设4元集为,a,b,c,d,即划分种类有:,划分为一个子集：1种,a,b,c,d 1,种,划分为两个子集：7种,元素组合1+3:共4种,a-b,c,d b-a,c,d c-a,b,d d-a,b,c,元素组合 2+2:共,C(4,2)/23,种,a,b c,d,a,c-bd,a,d-b,c,b,c-a,d,b,d-a,c,c,d-a,b,划分三个子集：6种,元素组合1+1+2,共,C(4,2)=6,种,a-b-c,d,a-c-b,d,a-d-b,c,b-c-a,d,b-d-a,c,c-d-a,b,划分为四个子集:共1种,a-b-c-d,总计：1+7+6+1=15种。,(8)设,C*,是实数部分非零的全体复数集合，,C*,上关系,R,定义为：(,a+,bi,)R(c+,di,),ac0，,证明,R,是等价关系，并给出关系,R,的等类几何说明。,证明：,aa0,(a+,bi,)R(a+,bi,),R,自反;,(,a+,bi,)R(c+,di,),ac0,(c+,di,)R(e+fi),ce,0,显然有,ae,0,故(,a+,bi,)R(e+fi)，R,传递;,(,a+,bi,)R(c+,di,),ac0,ca0,(c+,di,)R(a+,bi,),故,R,对称。,综上所述，,R,是,C*,上的等价关系。,关系,R,将,C*,划分为两种等价类，,正实数+,bi,R,与负实数+,bi,R,在复平面上，以垂直的虚数坐标轴为分界线，将复数分为左右两部分。,习题41,（5）假定,X,和,Y,是有穷集合，找出,X,到,Y,存在入射的必要条件是什么？,答：,Y,X,（6）,设,A,和,B,是有穷集合，有多少不同入射函数和多少不同的双射函数。,解：设,Xm，Yn,且n,m,入射函数是指一个象只能有唯一的原象，即一个象映射为某个原象后，该原象不能再作为其它象所对应的原象，故入射函数的数目为,n,(n-1),(n-m+1)=P(n,m),双射函数要求,m=n，,故其数目为,P(n,n)=n!,习题42,(,3)设,f,g,是复合函数，,a),如果,f,g,是满射的，那么,f,是满射的。,b),如果,f,g,是入射的，那么,g,是入射的。,c),如果,f,g,是双射的，那么,f,是满射而,g,是入射的。,证明：,设,f：BC，g:AB，,a)C,中任取元素,c,因为,f,g,为满射,故存在,aA,使得,f,g(a)=c,故存在,bB,使g,f,即,对任意,cC,存在,bB，,使得,f(b)=c,所以，函数,f,为满射,。,b),任取,a1,a2A,且,a1a2,设,g(a1)=b1,g(a2)=b2,f(b1)=c1,f(b2)=c2,即,f,g(a1)=c1,f,g(a2)=c2,由于,f,g,为入射函数且,a1a2,故,c1c2,g,为函数，故必须,b1b2,所以，函数,g,为入射。,c),由,a),和,b),的结论，显然可证得该命题。,