离散数学复习指导2

《离散数学复习指导2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、离散数学复习指导II集合论部分一学习要求1.领会集合的各种运算，掌握各种集合式的谓词演算的证明方法；2.领会序偶及笛卡积的定义,理解二元关系的定义，掌握及关系的运算（定义域、值域、逆、复合、闭包）；掌握关系的三种表示方法（集合、关系图、关系矩阵）.3.领会关系的性质,能判断或证明一个关系所具有的性质，4.理解等价关系及划分的定义，掌握等价类及集合商集的求法，理解等价关系与划分的关系。5.理解偏序关系的定义，特別注意偏序集中元素的可比性（“大小”的含义），能画出哈斯图，并能求出集合中的特殊元及集合的界；6•理解函数的定义，掌握函数的复合及逆运算，领会特殊函数（单射，满射，双射）的概念。二范例例1

2、已知£={1,2,3,4,5,6,7,10,12},A={x2

3、A

4、=6；p(B)二{0{6},{7}川0},{6,7},{6」0},{7」0},{6,7」0}}；Bx(AcB)={〈6,6》〈6,7》〈7,6》〈7,7》〈10®〈10,7〉}例2己知A={a,b,c,d},R

5、=,S={〈a,b),@,〃〉，e，d〉,〈d,c〉2厶，求：(1)Ri;R2,RoS,So/?2(2)r(R),s(R),t(R),rst(R)解：(1)/?J={〈d,a〉,〈b,a),〈c,b),〈d，M};F二{@,»,〈a,c〉,〈d,d〉}R°S二R2°S二{〈a,b〉,〈a,d),〈a,c〉,〈Q,d〉}(2)厂(/?)二@,/»,〈b,c・〉,〈b,d〉2lAs(R)={@,Q),〈a,b)，e，d),〈b,c〉,〈c,b)，e，〃〉,〈d,/»}t(R)={〈a,Q〉,〈a,b〉,〈b,c),〈b,d),〈a,c),〈a,d〉}rst(R)={〈d,b)，e，a〉0，c〉,〈

6、c,»，e，〃〉,〈d,Z?),〈a,c〉,〈c,a),〈G,d〉,〈d,o〉2IA例3已知X={a,b,c},给出X上的所有等价关系。解:X的划分其冇五种：Si={{a,b,c}},S2={{a,b},{c}},S3={{a,c},{b}},S严{{a},{b,c}},S5={{a},{b},{c}},因为X上划分与等价关系一一对应，故x上共有五个等价关系，它们是:R【={,,,,},〈b,a>}x,R：<={〈a,c>〈c,a>}jIxRi={〈b,c>,〈c,b>}u/x,&=Ix例4已知偏序集〈X,R

7、〉，其中X={a,b,c,d,e},Y={d,e},R的关系矩阵为100001100011000011求：(1).用集合的列举法写出R(2)•画出R的哈斯图;(1).找出X的极人元、极小元、最大元、最小元;(2).找出Y的上界、下界、最小上界、最人下界。解：(1).R=人(2)•略(3).X的极大元:a;极小元:c,d;最大元:a;最小元：无.(4).Y的上界e,a;下界d;最小上界e;最大下界d。例5(1)实数集R上的函数/(兀)=兀+3,g(x)=3x+5,(2)A=[a,b,c],A上函数={〈d,»,〈b,c),〈c,a〉},g={〈a,c〉,〈b,b〉,〈c,d)}判断f是否单射、满

8、射、双射，并求gof,go/-1.解：(l)/(x)=x+3为双射，g(Q=3x+5为双射g。/(x)=/(g(x))=/(3x+5)=3x+8,v*1Af。g(x)=g(fM)=g(x+3)=3x+14,(fog)T(x)=--y,f-x)=x-3,g。厂⑴二(g⑴)二厂(3x+5)=3x+2.(2)y,g均为双射g。/=f°g={〈d,b),〈b,a〉,〈c,c〉},(fog)"={〈b,a),〈a,b〉,〈c,c〉}={〈b,a〉,〈c,b〉,〈Q,c〉},g°f~l=@,b),〈b,d〉,〈c,c〉}.三练习题1.已知£={1,2,3,4,5,6,7,8},A={x3

9、B={x4<兀v7},求：(1)〜A；AnB；AuB；A-B；4㊉B(2)

10、A

11、；p(B)；Bx(AnB)；1.已知A={123,4},R={〈2,1),〈1,2〉,〈3,1〉,〈1,4〉},5={(1,1),〈2,3〉,〈3,3〉,〈3,4〉,〈4,2〉},(1)求R-';RRoS,SoR2(2)求f(R),s(R),t(R),rst(R)(3)利用关系短阵求R，,S。R2.已知X={a,b