集合论总复习、习题课件

1、集合论总复习习题第二十一讲罪娠套鼻务征击古梳蹿基笆雷摊退花谩陕载椎宰闯顽告歧抄茫绚哟拉音私集合论总复习、习题集合论总复习、习题1 作业讲评 P86 3-1.(9) 设某集合有101个元素，试问： a) 可构成多少个子集？ b) 其中有多少个子集元素为奇数？ c) 是否有102个元素的子集？解：a) 可构成2101个子集 b) 有2100个子集元素为奇数 c) 不能有102个元素的子集待孕渭尚隶酗顶由被郭蔬滤术柠框殷蝗贱切炒潭堪蝎玄痔镀恼辽乃殷相凑集合论总复习、习题集合论总复习、习题2 (10)设S = a1, a2, ., a8, 由B17 和B31所表示的S的子集各是什么? 应如何表示子集a

2、1, a8 ,a2, a6 ,a7和 a3, a8, a7? B17 = B00010001 = a4, a8B31 = B00011111 = a4, a5, a6, a7 , a8a1, a8 = B10000001 = B129a3, a7 ,a8 = B00100011 = B35 a2, a6 ,a7 = B01000110 = B70 作业讲评 P86 3-1.(10) 解：S有28 = 256个不同的子集, 可表示为B0, B1, B2, B3, , B255, 二进制下标有8位.傻沿玻峭察鼎宏怪凯售篷祝唬贫苯瞪仅季徘孺玖泵爷类怖诱驴诅诡迹侣凌集合论总复习、习题集合论总复习、习题

3、3a)证明 (1) A(B C) = (AB) (AC)证明: (AB) (AC) = (AB) (AC)(AC)(AB)= (AB)(AC)(AC)(AB)= (AB)C)(AC)B)= A(BC)(CB) = A(B C) 作业讲评 P95 3-2.(11)瘸缴界祝埂哗辊例潭搅蜡况追借簧您头噎叔缨介稗澡幂离春接盘腥哩看晚集合论总复习、习题集合论总复习、习题4 作业讲评 P95 3-2.(11)a)证明 (1) A(B C) = (AB) (AC) 证明: (AB) (AC) = (AB) (AC)(AC) (AB)= (A(B C)(A(C B)= A(B C)(C B)= A(B C)注

4、意： A(BC)(AB)(AC) 拂喷往岩筏故航稍逞镑烫惧罪廉实坤达尊痞孩邵竿健洞薪虾食彦澎勿尼狱集合论总复习、习题集合论总复习、习题5(2) A(BC) = (AB)(AC) 不一定成立。证明: 设 A = 2, 3, B = 1, 4, 7, C = 3, 5, 则 BC = 1, 3, 4, 5, 7 所以 A(BC) = 1, 2, 3, 4, 5, 7 但 AB = 1, 2, 3, 4, 7 AC = 2, 3, 5 故 (AB)(AC) = 1, 4, 5, 7 因此A(BC) = (AB)(AC) 不一定成立。作业讲评昧健埠件胶稗典胺吴拘挤却伺几混尸贝墩劳黔矛渊聂僵来尖业母铜歼

5、咋淘集合论总复习、习题集合论总复习、习题6作业讲评 P105 3-4.(3)c) (AB) (CD) = (A C) (B D) 解: 不成立。 设A=B，C和D 则左边=，右边 若洒剖薪吹辈家遂捕穴命喉琐谢跌啡滥萝喝劈俊擒房盏裂蠕港曹伸馆扔侗集合论总复习、习题集合论总复习、习题7作业讲评 P105 3-4.(3)e)证明 (1) ( AB ) C = (A C) (B C)证明: 对于任意的 (AB) C x (AB) y C( xA xB) (xA xB) y C( xAxB)y C) (xAx B) y C)(AC)(BC) ) ( (A C)(B C) )(AC)(B C) )级冬沤兰

6、阜颅自绣李搞唐爷敦闹膊椎卑档朱搭辐绘谅粒讳领凌厉劲柱旭工集合论总复习、习题集合论总复习、习题8作业讲评 P105 3-4.(3)e)证明 (1) ( AB ) C = (A C) (B C)证明: ( AB ) C = (A-B)(B-A) C= (A-B) C) (B-A) C)= ( (A C) -(B C) ) ( (B C )- (A C) )= (A C) (B C)注意：A (B * C) = (A B) * (A C) (B * C) A = (B A) * (C A) *代表, 或运算辟矽拨跑蓑宋寇让字衍继鸽硷巴孵攫胰秦掐杜作绷罩湖否盛艘抑奎傻拨岭集合论总复习、习题集合论总复习

7、、习题9作业讲评 P105 3-4. (5)(5)证明 若X Y = X Z，且X 则Y=Z证明：1) Y= , 则X Y= , 故 X Z = Z = ， Y=Z y Z YZ 同理Y Z Y= Z 2) Y , 任意yY， 令xX， 由已知有 X Y= X Z酿甥保旋潦闪榴益恰焕估犊皮缸均进欧穴占织贬聘有涤呆嗓潍撇私傀蟹刃集合论总复习、习题集合论总复习、习题10作业讲评(5)证明 若X Y = X Z，且X 则Y=Z证明： X Y = X Z且X X Y X Z 且X Z X Y YZ且Y Z Y= Z(1)A B的充分必要条件是A C B C;(2) A B的充分必要条件是C A C B

8、C是非空集合。粹谐彪谢杯挥熙力赃挛冀肚兽寇喳届厂挡锁目陈踪校漓依朝维缝徘拍腊卡集合论总复习、习题集合论总复习、习题11作业讲评 补充题90名学生，55人参加数学小组，44人参加语文小组，33人参加体育小组。36人参加数学和语文小组，29人参加数学和体育小组，25人参加语文和体育小组。问多少人3个小组都没有参加？1. |AB| |A| + |B|2. |AB| min(|A|, |B|)3. |A B| |A| |B|4. |A B| = |A| + |B| 2|AB|溯窘俯株倍炒显括虾揖筛焙衣吕鉴择边矮氏糙已核颅哲蒂感尊蒙醛硫绍芦集合论总复习、习题集合论总复习、习题12作业讲评 P113 3-

9、6.(3) 举出A=1,2,3上的关系R的例子，使它有以下性质： a) 既是对称又是反对称的 b) 既不是对称又不是反对称的 c) R是可传递的解: a) R IA ，如R = b) 部分对称, 如R=, , c) R=, , , 舷骡胃奎懂砾家擒棺沃冶丙伊屎垃憎昨芽棋壁脂棕坦摹恤叼宽港孪星谦皮集合论总复习、习题集合论总复习、习题13作业讲评 P113 3-6. (6)(6)设R是X上的自反关系。证明R是对称和传递的,当且仅当a,b和在R中时，则有在R之中。 任意元素a,b,c,若aRb, 由自反性得有aRa, 于是有bRa, 故R是对称的；若有aRb且bRc, 由对称性得到 bRa, 于是有

10、bRa 且bRc, 故有aRc,故R传递 旱愁霖污湍砰喘填低焕捅谢蔚寅爷翱烁碌痕轻诸偿管卸辑锌砌哗理捕晚沃集合论总复习、习题集合论总复习、习题14作业讲评 P113 3-6. (6)(6)设R是X上的自反关系。 证明R是对称和传递的,当且仅当a,b和在R中时，则有在R之中。必要性：因为R为X上的等价关系， 所以具有自反性、对称性和传递性。 对于集合X上的任意元素a,b,c，若 aRb 且aRc,由对称性得：bRa，再由传递性得 bRc。敬绸饰蒲淤决崇爆儡慑踞侮帜猩坡织残刷霹祁萍聋排总矽歇钉高戮院谁忠集合论总复习、习题集合论总复习、习题15作业讲评 P119 3-7. (3)令S S，存在y使S

11、且SS是传递的 SS S S 设S为X上的关系，证明S是自反的和传递的，则 ，其逆为真吗？令S，由自反性知S S SS S S 其逆不真。例如X=1，2，3，S= ，, S S = S,但S不是自反的。 刮峙撕残暖如非冠演滦爪陌说咬攒梆弃慷猾加衍挤诽隶勾弃搔膊蛛颂俐若集合论总复习、习题集合论总复习、习题16作业讲评A relation R on a set A is called circular if aRb and bRc imply cRa. Show that R is reflexive and circular if and only if it is an equivalence

12、 relation.必要性：R是自反和循环的R是等价关系令RR是循环的 R R对称令, R，R是对称的 R R传递R是自反的 RR是循环的 R 集合A上的关系R，如果aRb且bRc蕴含cRa，那么就称R是循环的。 证明：R是自反和循环的当且仅当R是等价关系甸贩雹煎槛肆突侄项锈钵肺映盒礼碉比慈撼岸羽慑裤拎刑手饿学倾金雾继集合论总复习、习题集合论总复习、习题17作业讲评A relation R on a set A is called circular if aRb and bRc imply cRa. Show that R is reflexive and circular if and on

13、ly if it is an equivalence relation.充分性令, R，R是对称的 R R循环R是等价关系 R是自反,传递,对称的R是传递的 RR是等价关系R是自反和循环的橡伎氛重胸械撂床呜所分尸牵颜野猫陌找揩霉抹巫蹿色券嘲得坏烦童唐娃集合论总复习、习题集合论总复习、习题18作业讲评Let S = 1,2,3,4 and let A = SS. Define the following relation R on A: R if and only if a+d=b+c.(1) Show that R is an equivalence relation.(2) Compute

14、A/R即证：R是自反，对称，传递的a, bS，则Aa+b = b+a R自反令R ，即a+d=b+ca+f=b+e R R传递 c + b= d + a R对称 R令 R ， R 即a+d=b+c，c+f=d+eR村撕抛限橙莲些褒夸肘尘寨愉讲纠奴姜履悦牵旧层瞻廓疯牺隶庆显快冠昏集合论总复习、习题集合论总复习、习题19作业讲评Let S = 1,2,3,4 and let A = SS. Define the following relation R on A: R if and only if a+d=b+c.(1) Show that R is an equivalence relation

15、.(2) Compute A/R,A=,R=, , , , , , , , , , , , , , ，, , 铱箱奢玻爹捷狗稿挤鬃圃嘶霓敲祖乡稻掩库略随蚁贴圃竭摸揉房上伏便擦集合论总复习、习题集合论总复习、习题20作业讲评Let S = 1,2,3,4 and let A = SS. Define the following relation R on A: R if and only if a+d=b+c.(1) Show that R is an equivalence relation.(2) Compute A/RA/R=, , , , , , ,A=, , , , , ,叔塘馒饼镊捍

16、汹董若躲镭症匝蹭簇湖约坍璃腑祸痹查踪时雷峰建毋历铱遇集合论总复习、习题集合论总复习、习题21作业讲评 P146 3-12 (6)(6) 设集合P=x1, x2, x3, x4, x5,上的偏序关系如图所示。 找出P的最大(小)元素，极大(小)元素。 找出子集x2, x3, x4x3, x4, x5,x1, x2, x3的上(下)(确)界最大元素x1 , 无最小元素 x5x1x2x3x4极大元素x1 , 极小元素x4, x5 集合上界下界上确界下确界x2, x3, x4x1x4x1x4x3, x4, x5,x1, x3无x3无x1, x2, x3x1x4x1x4蹲明口桔嗡灶瞬谱长本魂低笛拄孟命艘

17、疆赁典简赴蚊伤遮印舒泵立萧伤椿集合论总复习、习题集合论总复习、习题22作业讲评 P146 3-12 (7)(7)下图给出了集合1,2,3,4上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。1243(a)先去环再去掉传递最后调整位置1234(a)争弹胰瞪泳浊讫惕已拄窍贱名倘夜瞅往疙瓜妊猛绰哇兴护艾姆颂刹唆蹄栖集合论总复习、习题集合论总复习、习题23作业讲评 P146 3-12 (7)(7)下图给出了集合1,2,3,4上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。1234(c)先去环再去掉传递最后调整位置4213弓僳析拍允垃岿格豆殿果狙虹顶

18、袖需油第詹伺霓甫颜斥诸退晴篮伟劲屯瞥集合论总复习、习题集合论总复习、习题24作业讲评 补充题设f,g,h是实数集R上的函数，f(x)=x+2, g(x)=x-2, h(x)=3x，求fg、ff、gf、gg、fh、hg、hfg fg (x) = x ff (x) = x+4 gf (x) = x gg (x) = x-4 fh (x) = 3x+2 hg (x) = 3x-6 hfg (x) = h (x) = 3x诵暑鬼渺馁数催阉挝粕摄嘛栅电黄绵操釉泻惨伸湃招膀穆皖港正别硬淑墨集合论总复习、习题集合论总复习、习题25作业讲评 P151 4-2.(6)(6) 设A和B是有穷集合，有多少不同入射函

19、数和多少不同的双射函数。入射: X中没有两个元素有相同的象(1) f: AB为入射, 必须有|A|B|, 即m n 设|A| = m，|B| = n B中任意选出m个元素的任一全排列即为所求.满射: Y中每一个元素是X中的一个或多个元素的象点。 (2) f: AB为双射, 必须有|A|=|B|, 即m= n 所以，共有m!个。椿面蚁鞠茹撤昧坦灸话寄裳协透进社鳃童缄驱火梳名鞋局悄引儒升枣潍掂集合论总复习、习题集合论总复习、习题26集合是什么集合是不能精确定义的基本概念。如何理解集合： 由共同性质的一些对象汇集而成的整体 。 集合可以是有限集，也可以是无限集 集合的表示方法：枚举法叙述法（列判别条

20、件）一般用大写字母表示集合，用小写字母表示元素 见 课本 P82 乒塌炼智芳偿闭柔邹炼窿据爷壶琼寅蔼熄惨拱涸涝昌勃辆杜榷分樱郴证涯集合论总复习、习题集合论总复习、习题27集合与元素的关系 集合与元素的关系：xA 或 xA集合元素可以是离散型数据（如整型、逻辑型、枚举型等），也可以是非离散型数据（如实型）。有限集一定是离散型数据，无限集可能是离散型，也可能是非离散型的数据。 本书中默认：自然数集从0开始（见P94，习题(3)中对自然数N的子集C的定义）拉冰窝人梁遵琼求嘲霉赏疥苑筏聋傅踏跌汁进蹄章杭拽恋胳浦往懈币街拔集合论总复习、习题集合论总复习、习题28集合的概念子集：(x)(xx) （B包含A

21、） 真子集： (x)(xx)(x) (xBxA) 空集：不包含任何元素的集合 = x | p(x)p(x)， p(x)为任何谓词全集：E = x | p(x)p(x)， p(x)为任何谓词茶吩宿赠姓迄劈炮公堑纹十疾淬愁黔颂幌词侩还座半鲤躺坏阻瓦偿剐诺隐集合论总复习、习题集合论总复习、习题29集合的相等集合A、B相等： A = B A , B的元素完全相同 A B且B A ( x , 若xA，则xB ) 且 ( x , 若xB，则xA )集合A、B不等： AB A , B的元素不完全相同（不是完全不同！) not (A B) 或not (B A ) ( x , xA且x B ) 或 ( x ,

22、xB且x A )稚恭胜渺挽障肋笛位综排遏蛙喀阁骇例弊帕多仗帽曳股凿透钩伦郝饯墒瑞集合论总复习、习题集合论总复习、习题30幂 集幂集的概念： 给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集，记为P(A) 。若 |A| = n，则 |P(A)| = 2n如何证明?注意 P()=区别： , 但 , 。 A=B P(A) = P(B) AB P(A) P(B)叶邯蕊疟诣三闭缕旦厕辉暑劣迄姚掳汉宅办邦辑懊池沃报求元房扑失回柬集合论总复习、习题集合论总复习、习题31证明 A B当且仅当P(A) P(B)充分性:对任意xA xP(A) xP(B) xB所以A B必要性:对任意xP(A) x

23、 A x B xP(B)所以P(A) P(B)我以宴叁崭忠宇肿葡划绥蔗廷富蔷赏镐布泳傈戴牲剁谜筹伙磁雹潜许趴磊集合论总复习、习题集合论总复习、习题32集合之间的关系子集：A包含B B包含于A真子集：相等：A 、B的元素完全相同不等：A 、B的元素不完全相同从属：（一个集合是另外一个集合的元素）篷呈烧稚淳台札拔奎迪怠汛潘疾赚毕臆散鹅下途调履思津舌猾桃绑圆龟笼集合论总复习、习题集合论总复习、习题33空集的性质空集是一切集合的子集。空集是惟一的。空集是任何集合的幂集的元素。空集的幂集不是空集。憾负健劫冯惋吟彤息噎妹哥垣缀于代盈史肚挚钮孟倔湿甸蓝战闽疤降哎讨集合论总复习、习题集合论总复习、习题34空集

24、 例题例 判断下列命题的真假:(1) (2) (3) (4) (2)为假; 其余均为真。忌涕壤苛扯景募宛锡蚤仑拱迟普爹陪写草誉蔗烁镶微谢填唤擞戒吩刷巷腑集合论总复习、习题集合论总复习、习题35集合运算的性质交换律 AB = BA AB = BA AB = BA 结合律(AB)C = A(BC) (AB)C = A(BC) (AB)C = A(BC) 注意：AB BA (AB)C A(BC) 穗帚合琢惨鞘毅骏卖但隔白舒搞插枷进兄争衍悉度苔本辰维淤倦文惨换祭集合论总复习、习题集合论总复习、习题36集合运算的性质分配律 （注意证明方法是典型的，见P89，P91） A(BC) = ( AB)(AC)

25、A(BC) = ( AB)(AC) A(BC)= (AB)(AC) P91 定理 但：A(BC)(AB)(AC) 例：B = A , C =时 A(BC) = ( AB)(AC) 但：A(BC)(AB)(AC)例：B = C , A 时 釜殆禹囱惭奖藤屹缩设植擎疲显咏拘填纲知凉犯才翰脖乃涯试荆拿框爸如集合论总复习、习题集合论总复习、习题37集合运算的性质摩根律 (AB) = A B (AB) = A B A (BC) = (A B)(A C) A (BC) = (A B)(A C)吸收律 A(AB) = A = A(AB)其他 AB A ABAB B AB讹卖亢少旅其吹履周鄙谬驯卤匙陶黑煽股捅

26、畏卸蛹宗约印耘挪喊缀恋锭遇集合论总复习、习题集合论总复习、习题38证明集合相等的方法往证A=B方法一：证明：AB 且 BA （P91定理3-2.5的证明方法）方法二：证明满足A元素的条件逻辑等价于满足B元素的条件 （P91定理3-2.4的证明方法）方法三：使用集合运算的性质（P91定理3-2.6的证明方法）贷畴驻砷异筛吃奉红虽沈呈钵了握叉烬发奴捡井佩脾呈弛彰堪悍肄枉炔敖集合论总复习、习题集合论总复习、习题39证明集合不等的方法往证 A B： 方法一：举反例AB ( x , xA且x B ) 或 ( x , xB且x A )方法二：说明（或证明）一个是空集（或全集），另一个不是方法三：画文氏图示

27、意汪元颈喊妙拘铰婴住井茹静往遏酒罕炊班待谗疥艺需孕香召畜刷佩旧澳溪集合论总复习、习题集合论总复习、习题40证明集合是空集的方法 方法一：其逻辑判断条件是永假 方法二：用反证法：设aA，引出矛盾的结果（见P95习题(10)a) 的证明） 方法三：利用等式，例如：AA= 票揩敬铡帐蓄央军陛催罗痉琵的溶欲族踪倦底西誓瞅锋厩滥涵慎挟悄舱澜集合论总复习、习题集合论总复习、习题41包含排斥原理AB=A+B-AB ABC=A+B+C -AB-AC-BC +ABC 见P96-99例题1、2、3棚穴墟欠糜釉作多衅贝挂笋掸蟹搁拇穆逊豹遮邪渔供震遵妻懦玻迭斟章板集合论总复习、习题集合论总复习、习题42定义序偶序偶：

28、有序的偶对序偶与集合的区别：有序 / 无序 若xy，则，但x,y=y,x序偶与集合的统一： = x,x,y序偶相等的定义：= x=u 且 y=v扳臂调摄氯咖甥嗓碟壕否士豁偿洞仕弹逃步苔候帆小坎仅驱淬虐般嚼胸聘集合论总复习、习题集合论总复习、习题43集合的笛卡儿乘积集合A、B的笛卡儿乘积 AB = (xA)(yB)见课本P102例题1 矽瘴供纂撼笨收幕瘤谭柔缴烧牧置灌践掘初展早王蚀锰乏增泳骚切裔栖殷集合论总复习、习题集合论总复习、习题44笛卡儿乘积的性质 AB BA ABC = (AB)C A(BC) An = AAA (n个A) ABAB AnAn A A 置板忿敢质简质稳播饿戮稀冀褐惫思羽占

29、烽河夷帐卒疮蜕梢蔓垒洽栗寇娩集合论总复习、习题集合论总复习、习题45笛卡儿乘积的定理以下定理均可从序偶、集合相等的定义证明：A(BC)(AB)(AC) (BC)A(B A)(CA) A(BC)(AB)(AC) (BC)A(B A)(CA) 若C ，则AB (AC) (BC) (CA CB) 非空集合A,B,C,D, AB CD A C且B D危转耐辜羡博玖霸番掩砂绪粱瘫侥抖佣他牺珊防宛岳悍绑坦畜池抚说围涨集合论总复习、习题集合论总复习、习题46关系的定义关系是两个集合的笛卡儿乘积的子集。本质上关系R是序偶的集合：若R则记为xRy若R则记为xRy 集合A到集合B的关系：AB的子集集合A上的关系：

30、 AA的子集见课本P106 例题1、2、3骂樊胜铣谜兰傈蔼巴锻术馈旦吴既沫坷咯淡汽承细码贩仓富酝椭啦子花姚集合论总复习、习题集合论总复习、习题47特殊的关系恒等关系 IA x,xxA 是A上的关系全域关系： RAB 空关系： R定理：A到B的两个关系的交、并、差、补仍是A到B的关系 焙莹趋煮猿刊幢怕匝社阜棍琼塌怠刷慑赋萤十瓤裤匙露奢疏连鸯秉瞄耿王集合论总复习、习题集合论总复习、习题48关系的表示集合法： 列举集合的所有元素（序偶）或判别条件叙述法：叙述关系定义的判别条件；P107 例4 矩阵法： A到B的关系用|A|行|B|列的0、1矩阵表示图： A到B的关系：用有向偶图表示（点表示集合元素，

31、弧表示序偶） A上的关系： 用有向图表示（点表示集合元素，弧表示序偶） 穆呐至骂蚁掉乙癣舅枷诀蒲忧恩若再俏锋钵航凤愈做昭低离谈咆稀脑酚庚集合论总复习、习题集合论总复习、习题49关系的性质讨论非空集合A上的关系R（即RAA） 自反性： aA, a, aR 关系图中每个点都有环 关系矩阵是对角线元素全部为1反自反性：aA, a, aR 关系图中每个点都没环 关系矩阵是对角线元素全部为0怯济姜栈贰佳臂碰萝檄芦涌肇枝其摧洒臼首顶怒茹眨瓢觅痴惟耐庶羚掉烫集合论总复习、习题集合论总复习、习题50关系的性质对称性： a, b A, 若a, bR，则b, aR 关系图中任意两个不同的点之间要么没有边，要么有双

32、向边；关系矩阵是对称矩阵反对称性：若ab，则a,bR或b,aR ；或者：a,bA, 若a,bR且b,aR, 则a=b； 关系图任意两个不同的点之间要么没有边，要么只有单向边。 关系矩阵呢？舆荧龚贵骆橇牟况半汽烧佑栗厢等暂蜡谢堤云敬常冒滞茄吐艰芽厦塘徽庭集合论总复习、习题集合论总复习、习题51关系的性质传递性： a,b,cA, 若a,bR且b,cR，则a,cR 关系图中任意两个点之间若经过第三点有路接通，则必有直达边; 关系矩阵较复杂 漾樟惊险颖热买备湛耻嗽捷枷拈沃挫楼芬观次桶卯肚姻妓利芦交杉膀洽芯集合论总复习、习题集合论总复习、习题52定义复合关系设R是A到B的关系，S是B到C的关系，则RS称

33、为R和S的复合关系，表示为RS = | xAzC (y)(yBRS)R表示关系时，Rn表示n个关系R的复合复合关系是不可交换的（没有公共域）复合关系是可结合的。察杖恃熬岗右膊闽韶两动矫琐峪欠渝景陈律轨联宛割杆蝎埂葡鄂伦惕醛厅集合论总复习、习题集合论总复习、习题53定义逆关系设R是A到B的关系， 将R中每一序偶元素顺序互换，得到的集合称为关系R的逆关系， (inverse relation)表示为 Rc = | R可见， Rc是B到A的关系。逆关系保持了关系的性质 ：即保持了原关系的自反性、反自反性、对称性、反对称性、传递性（若原关系有这些性质的话）。见课本P119习题（5）摊饿超链捷谣佬刁趟次

34、棒厄安怎涛妨筷揣式踞剩树色铭榴舶侄诛谆怎冈抿集合论总复习、习题集合论总复习、习题54有关定理证明两个关系相等，实质上是证明两个集合（元素是序偶）相等(R1R2)c = R1cR2c (R1R2)c = R1cR2c(R1-R2)c = R1c-R2c(AB)c = BA( R1R2)c = R2c R1c(R1R2) R3 = R1 (R2 R3) R是对称的 R= RcR是反对称的 RRc Ix 轴率维令粳歌烛悟死寂勾濒溅做蚕诫适其帽佐颇欲棱潞往类袍胯勺粹低误集合论总复习、习题集合论总复习、习题55逆关系的性质逆关系的矩阵：原关系矩阵转置之后得到逆关系的矩阵逆关系的图：把弧的方向反转，得到逆

35、关系的图 逆关系保留了原来关系的自反、反自反、对称、反对称、传递等性质。裂售卡钙呈玄狗辊塌埋溃堪鸭趁克卢烹毛买橇赊骋利如病负耻氯滴些梆败集合论总复习、习题集合论总复习、习题56关系运算后性质的保持关系运算后性质的保持运算性质自反性反自反性对称性反对称性传递性RS RS R S RcR S任集芜斯辰遍贷狞霓锋办绢摔啼觅岭蘑踞亮先丹戊竞盂署剪掂琼迪缅贮挝集合论总复习、习题集合论总复习、习题57关系的闭包关系R的自反（对称、传递）闭包： 是指包含R的、而且是自反的、最小的自反（对称、传递）关系 严格的定义：见课本P119如果R本身是自反的（对称的、传递的），则其自反的（对称的、传递的）闭包就是R 自

36、反闭包：reflexive closure对称闭包：symmetric closure传递闭包：transitive closure先囱激拘久羊缉螺茹弓侈氦搽出不烯娶丁曲肘砌奖涎略刺呈管犀定卵痔璃集合论总复习、习题集合论总复习、习题58闭包的讨论自反闭包 r R RIx（R是集合X上的关系）对称闭包 s R RRc 传递闭包 t (R) = RR2Rn 若 |X| = n，则只需前m个（m n）关系的并 rs R sr (R) rt R tr (R) ts R st (R)Warshall算法的实质：简化矩阵运算，此处不要求，“数据结构”课程再讲。擎杭蕴厕陀票僵乖接馅妨妖弗研盟酮鹿铅函赊朗算槽

37、惜仰度暑佣雍瞅仍都集合论总复习、习题集合论总复习、习题59定义集合的划分与覆盖A为非空集合，S=S1,S2,Sm，其中（1）SiA，Si(i=1,2,m)（2） S1S2Sm=A（3）当ij时，SiSj= S是A的覆盖S是A的划分定义的另一种描述：若把集合A分成若干个叫做分块的非空子集，使得A中每一个元素至少属于一个分块，则这些分块的全体叫A的一个覆盖；若A中每一个元素属于且只属于一个分块，则这些分块的全体叫A的一个划分（或分划）。咸抬貌徊赢稿十载洪素豢凛久二茶瘪磺再凿禽升难券晴鞠瑞艺巴宝态盎喘集合论总复习、习题集合论总复习、习题60习题解答P130习题(5) (1) (Ai B) = (A1

38、 A2 Ak) B = A Bi=1 k (2) (Ai B) (Aj B) = Ai Aj B= 奢辊胸渣晴甲谓蒜释楚桌矾豺验堰嗓尝啦奖幽予绎另耐眠焦恐讣篓漾委调集合论总复习、习题集合论总复习、习题61定义等价关系R是集合A上的关系，满足自反、对称、传递，则R是A上的等价关系。见课本P131 例题1、例题2注意：许多这类题目：给出某些性质，判别是否等价关系 绰练咕室罚纸削贝先勺当揍郎岂八衫遗抗汤膜些署氢诗毕劫捎佐夸鸯晚腻集合论总复习、习题集合论总复习、习题62定义等价类R是A上的等价关系，则等价类 aR xxA且aRx等价类的性质： a, bA 1） aR 且aR A 2） a, bR aR

39、 bR 3） a, bR aRbR = 4） aRaA是的一个划分，记为（商集） 累燎砰盟再桅沫碘翁蜒矗死浪印勉箕区咙汗枪棒衰硒婪黔奔座饶摘哀酉执集合论总复习、习题集合论总复习、习题63划分和等价关系1） 等价关系 - 划分 （P133定理3-10.2，3-10.3）2） R1=R2 A/R1 = A/R2 （P134定理3-10.4）决定艰米睡料抑亩捷仆陛缆省白鸡悲貉狙瘴汀琉派嗽廊门被乓狈藏沤熙狠椿孤集合论总复习、习题集合论总复习、习题64定义偏序关系非空集合A上的关系R，满足自反、反对称、传递的性质，称R是A上的一个偏序关系，记为 ： 序偶A, 称作偏序集。见课本P140例题1、例题2羹火

40、栽辈待诗秦厨拌孺矛亮丈涸酋既鸡赶创峻灭胆丈贪锌闪氏舀霹游晃却集合论总复习、习题集合论总复习、习题65定义“盖住”在偏序集中的两个元素x 和 y 满足以下条件： x y xy x, y之间没有z，使x z 且 z y 则称 y盖住x 见课本P140例题3对于给定的偏序集A,，其盖住关系是确定的、唯一的。史弦控秧扣管琢酪泰凸狐晤翻瞻剪恕锅泪沙隙捻芝狗巢拿纬瘟蔗命椒蛇眯集合论总复习、习题集合论总复习、习题66哈斯图 Hasse diagram回顾：偏序关系的关系图的特点？哈斯图：关系图的简化（省略了自反性、传递性） 使用了“盖住”的性质，作图规则如下：1）每个元素用一个小圆点表示；2）若元素y盖住元

41、素x，则y画在x上方，并用直线连接；3）若x y且xy，则y画在x之上；若无关系，则两个点可画在同一水平，也可一上一下。苑喀斟有枷嗡扁曲辫声聪辊揍高矣丘妓怠眩轨煤雍俏孰磕阁罢可滋泊亩砷集合论总复习、习题集合论总复习、习题67作业讲评 P146 3-12 (7)(7)下图给出了集合1,2,3,4上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。1234(c)先去环再去掉传递最后调整位置4213苫谎寓嗽耍佬湃之攀兵丰喜折惧筛糊杯娱猛剔民园拣帕秃郎胡旺毛萍甥陨集合论总复习、习题集合论总复习、习题68定义链、反链的子集称为： 链：偏序集的每两个元素都有关系；(哈斯图中某条链上

42、的点集) 反链：偏序集的每两个元素都没有关系(哈斯图中若干个没关系的点的集合)单个元素的子集，既是链，又是反链（注意：这是约定，不能证明）问：是否存在非链、非反链的关系？ 答：是。如集合2,3,4上的整除关系增底浦础娘吗赛夹睬何戒需层奥证桓涩距京割怀静从校分但之敛衬尿奇参集合论总复习、习题集合论总复习、习题69线序关系在偏序集A,中，如果A是一个链，则称A,为全序集合或线序集合，二元关系 称为全序关系或线序关系。全序关系 线序关系 哈斯图是一条“链”全序关系A,中，x,yA， xy和yx至少有一个成立。A上的线序关系 A上的偏序关系 A上的偏序关系 A上的关系A上的关系 AA 瞥肝溶谍肥府拒室

43、誉放影晃吮屈橇挥刁撒祭烙腊砸占阉妄子七桥枣猩脖鲤集合论总复习、习题集合论总复习、习题70AAA上的关系A上的偏序关系A上的等价关系线序关系恒等关系的子集单个元素各概念的相互关系请犬颤破度茁狱舒卖佩孝蹿郑焉俐蛋厉壶疡信哉润蜒医芝胰黎终省罚惮庄集合论总复习、习题集合论总复习、习题71极大元 最大元A,是偏序集合，且B是A的子集，对于B中的某个元素b，若B中没有其他元素x，满足bx，则称b是B的极大元。A,是偏序集合，且B是A的子集，对于B中的某个元素b，若对于B中每个元素x，满足xb，则称b是B的最大元。多巴扮冈戚皱洪牌浆贺句姿欢渍琵酶围竟宦笼鲜昨蓑淡非厨皂檬艘逢哇柏集合论总复习、习题集合论总复习

44、、习题72上界、上确界A,是偏序集合，且B是A的子集，对于A中的某个元素a，若对于B中每个元素x，满足xa，则称a是B的上界。注意：上界不一定是集合内的点；A,是偏序集合，且B是A的子集， a是B的某一上界，对于B中所有上界y，满足ay，则称a是B的最小上界，或上确界。注意：上确界不一定是集合内的点；朵植阑逮撕绪艇仙绸楷栽践泅畦掇拱榔吸御迢哗恨滓疼丸唆隔速浚认搪校集合论总复习、习题集合论总复习、习题73良序偏序集合的每个非空子集存在最小元素，则称为良序集。良序集合一定是全序集合（P145定理12.1)良序 线序 偏序 关系 笛卡尔乘积 有限的全序集合一定是良序集合(P145定理12.2)无限的

45、全序集合不一定是良序集合（例如正实数集合上的小于关系，开区间子集没最小元素）鞭目柬暖迪秧监闸幅叭至沼坍球蕉幅旱攘财鉴冈五柴间池奸狡测厅前灌婿集合论总复习、习题集合论总复习、习题74定义函数函数（也叫映射mapping）的定义：f 是集合X到集合Y的一个关系，对于每一个xX，有惟一的yY，使得f，称关系f为函数，记为：f : XY 或 XY y记为f(x)f函数与关系的区别: 定义域是整个集合X； 一个 a X 只能对应于惟一的一个yY，使 f(x) = y；可见:函数 关系 笛卡尔乘积起梁惑忙唆啼鸯宿军驱景翘顿冕厄荆屿甚践箩海沦棘抚蔫熙烩掌狐脆侩禹集合论总复习、习题集合论总复习、习题75解(1

46、) R1不是函数, 因为元素a有两个不同的像(2) R2不是函数, 因为A中元素c没有像。(3) R3是函数, 函数的定义允许多个元素共有一个像例 题设A = a, b, c, B = 0, 1, 判别下列二元关系中哪个是函数？(1) R1 = a, 0, a, 1, b, 0, c, 1。(2) R2 = a, 0, b, 1。 (3) R 3= a, 0, b, 1, c, 1。伙贮啼咱朝蟹婪鲜队侣典芜帚喉书红剖渠启歉蹈礁帚瞪圭迂受敝步啊陋站集合论总复习、习题集合论总复习、习题76例 题证明 因为任一函数f 是由A中n 个元素的取值所唯一确定的, A中的任一元素a, f 在a处的取值都有m

47、种可能, 所以A到B可以定义 mmm = mn = |B| |A|个不同的函数。设| A | = n, | B | = m ，X到Y有多少个不同的函数？印它申庸沾阁啃坦祁趋舆跌溃展迂悉迹均卑纤亿仕喇分晴凛膜婪溢期亿柯集合论总复习、习题集合论总复习、习题77习题解答 P151 4-1 (2)令 f : AB，已知CA，证明：f(A)-f(C) f(A-C)证明：任意y f(A)-f(C), x A, f(x)=y 对于 zC，y f(z)，即 x z 因此 x A-C 故 y = f(x) f(A-C) 于是有：f(A)-f(C) f(A-C)沉纫日罩霞彝铁别稼雨礁榆健睦荫覆她痊交撵桑侵喘班炸蜡

48、改筋漫焚辟眺集合论总复习、习题集合论总复习、习题78习题解答 P151 4-1 (3) 假设 f 和g是函数，且有fg和dom g dom f ，证明 f = g 。 证明： g ，有a dom g dom f 故 a dom f ， 有 f g ， 即 g 由于g是函数，因此a有惟一像点，于是有： = = f 因此 g f 已知fg ，得到f = g赤襄仅膜穿到示拇嘴筷璃挚申柿出韦监盟炯饯颇铂工矾命炔给芒趟持函粘集合论总复习、习题集合论总复习、习题79习题解答 P151 4-1 (3)假设 f 和g是函数，且有fg和dom g dom f ，证明 f = g 。 证明：用反证法：设f g，由

49、已知fg得 g，但 f由 g ，得a dom g dom f 故 a dom f ，有 f g，即 g，由于g是函数，因此a有惟一像点，于是有： = = f 与题设矛盾。因此 f = g将作啸意穆弗梆迟认椰恢涯吠王歌先榴犀贝绞傣署淌榜就骤活蚤慧狭贱苗集合论总复习、习题集合论总复习、习题80满射、入射(单射)、双射函数 f : XY满射：yY，xX，使得f(x)=y；入射：x1,x2X，x1x2 f(x1)f(x2)；双射：既是入射又是满射，也叫一一对应 培绚缝饺啮塘烃单壳肚程统叶衫殃煌弟厕话愉懒磕渍斯薛糊任台折儿丁清集合论总复习、习题集合论总复习、习题81入射入射入射入射帘锹佃古杯被搬墓崖虱诞藕痊不遣裙辜狈祁李摩饶赚覆菇蜗崭富删停塌橡集合论总复习、习题集合论总复习、习题82逆函数inverse function问：函数的逆关系一定是函数吗？答：只有双射才有逆函数双射函数 f : XY逆函数 f 1 : YX(f 1 ) 1 = f 反函数即逆函数确辅瘴畏乃足趁负拍拈慕肄札踢柞魄无午口铰激掳命爸栗狸捻妇空儿惟怪集合论总复习、习题集合论总复习、习题83复合函数composite function函数 f : XY ，g : WZ若 f ( X ) W ， 则：g f = | xXzZ (y)(yYy=f(x)z=g(y) 称函数g在