第3章
集合论初
步
本章主要包括:集合的基本概念,如集合、交集、子集、空集、幂集等;集合的基本运
算,如并运算、交运算、补运算和对称差运算,集合运算的主要定律,容斥原理,文氏图;笛
卡儿积。本章的难点是集合运算的主要定律以及容斥原理。本章的重点是文氏图。
3.集合论的历史背景
1
集合是数学中最基本的概念,也是自然科学与社会科学普遍采用的描述工具。集合
论是离散数学的重要组成部分,是现代数学中占有独特地位的一个分支。
康托尔是集合论的奠基人。1870 年前后,他关于无穷序列的研究奠定了集合论的系
统发展基础;1874 年,他发表了关于实数集合不能与自然数集合建立一一对应关系的著
名证明;1878 年,他引进了两个集合具有相等“势”的概念。
然而,朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂(Burali-Forti)于
1897 年提出的最大序数悖论;1901 年,罗素提出了有名的罗素悖论,康托尔提出了关于最
大基数的悖论。
集合论的现代公理化始于1908 年策梅洛所发表的一组公理,经过弗兰克尔的加工,
这个公理系统被称为策梅洛-弗兰克尔集合论,其中包括1904 年策梅洛引入的选择公理。
另一种公理系统是冯·诺依曼-伯奈斯-哥德尔集合论。
公理集合论中,一个有名的猜想是连续统假设。哥德尔证明了连续统假设与策梅
洛-弗兰克尔集合论的相容性,科恩证明了连续统假设与策梅洛-弗兰克尔集合论的独立
性。现在把策梅洛-弗兰克尔集合论与选择公理一起称为ZFC 系统。
集合论是一个庞大的知识体系,本书只介绍集合论的基础知识和二元关系。对集合
论感兴趣的读者可以参阅有关专著。
3.1.1
集合论创立者康托尔
康托尔是德国伟大的数学家、集合论的创立者。康托尔是数学史上最富有想象力的
数学家之一。
1845 年3月3日,康托尔生于俄国的一个犹太血统的丹麦商人家庭。1856 年,康托
尔和他的父母一起迁到德国的法兰克福。像许多数学家一样,康托尔自幼对数学有浓厚
兴趣,他在中学阶段就表现出对数学的特殊敏感,并不时得出令人惊奇的结论。他的父亲
力促他学工科,因而康托尔在1863 年带着这个目的进入了柏林大学。
72
离散数学简明教程
这时柏林大学正在形成一个数学教学与研究的中心。在柏林大学,康托尔受到数学
家魏尔斯特拉斯(K.Weierstras)的影响而转攻纯粹的数学。康托尔23岁获博士学位,
以后几乎一直在哈勒大学从事数学教学与研究。
康托尔在19世纪所创立的集合论已被公认为全部数学的基础,是整个数学大厦的根
基。几乎可以说,如果没有集合论,整个数学大厦就会动摇甚至倒塌。
1.寻找微积分的根基
集合论在19世纪诞生的基本原因来自数学分析基础的批判运动。康托尔是在研究
微积分理论的逻辑基础问题时开始着手创立集合论的。
I.Newtoeibni
自从17世纪牛顿(n)和莱布尼茨(G.W.Lz)创立微积分理论体系之
后,在一两百年时间里,微积分理论一直缺乏严格的逻辑基础。它的一些基本概念的表述
还有某些混乱和自相矛盾之处。数学分析的发展必然涉及无穷过程、无穷小和无穷大等
概念,而在18世纪,由于无穷概念没有精确的定义,不仅使微积分理论遇到严重的逻辑困
难,而且使实无穷概念在数学中“声誉扫地”。
从19世纪开始,柯西(A.L.Cauchy)、魏尔斯特拉斯等人进行了微积分理论严密化
的工作,他们建立了极限理论,并把极限理论的基础归结为实数理论。那么,实数理论的
基础又该是什么呢?
柯西并没有彻底完成微积分的严密化,柯西的思想有一定的模糊性,甚至存在逻辑矛
盾。19世纪后期的数学家发现,使柯西的思想产生逻辑矛盾的原因在于奠定微积分基础
的极限概念上。严格地说,柯西的极限概念并没有真正地摆脱几何直观,切实地建立在纯
粹严密的算术的基础上。于是,许多数学家致力于这方面的工作。
总之,寻求微积分彻底严密的算术化倾向成为集合论产生的一个重要原因。康托尔
试图用集合论作为实数理论以至整个微积分理论体系的基础。出于这一目的,康托尔用
集合的观点重新考察了各种数量关系,特别是无穷数量关系。
2.创立集合论
1874年,康托尔在《数学杂志》上发表了关于无穷集合理论的第一篇革命性文章,数
学史学者一般认为,这篇文章的发表标志着集合论的诞生。集合论向人们展示了一个由
无穷数量关系组成的新奇世界。
康托尔是凭着探险家的勇气闯入这个新奇世界的,他发现了许多令人难以置信的事
情。康托尔发现,无穷集合具备有穷数量关系所不具备的性质。例如,在无穷集合领域,
所有整数和所有偶数之间是一一对应的,所有有理数和所有整数之间是一一对应的,平面
上所有的点和线段上所有的点是一一对应的……总之,在无穷的世界里,整体的所有元素
和部分的所有元素之间是可以一一对应的。另外,无穷集合并不都是相等的,例如所有实
数和所有有理数之间就不是一一对应的,因而无穷集合是有大小的。
集合论用基数这个概念来表示无穷集合间的区别,那么有没有一个最大的集合呢?
康托尔通过研究得出了否定的结论。因为每个已知集合的所有子集所构成的集合,其基
数都大于已知集合的基数,既然没有最大的基数,当然也没有最大的集合。无穷”世界里
的这些性质初看起来真是令人头晕目眩。
最终,康托尔成功地证明了一条线段上的点能够和一个平面上的点一一对应,也能和
73
第
3
章 集合论初步
一个空间中的点一一对应。也就是说,在这个理论中,一条长为1的线段上的所有的点是
可以和一个
p
维(p=3时就是三维)空间里所有的点一一对应的,如果这条线段和这个
p
维空间之间不要求连续。这个结论和人们的常识是相违背的。因为物理常识告诉人们:
1m3 的黄金块无论如何都不会压缩成1m 长的黄金线。
当康托尔发现这逻辑事实时,连他自己都惊呆了。他在获得线性连续统和π维连续
统之间有一一对应关系的结果后,写信给数学家戴德金(R.Dedekind), 惊恐万状地写道: 我(“) 见到了,但我不相信。”
然而,集合论的成果毕竟是有严格逻辑根据的,不容置疑,并且它在解决实数理论逻
辑基础问题中发挥了别的理论无法取代的重要作用。实践使康托尔坚定了信心,更加勇
敢地前进,大胆挖掘无穷世界里的宝藏。他在提出超限基数和超限序数的过程中说:“ 我
确实不知道什么能够限制我们这种形成新数的活动。只要可以说明,为了科学的发展,引
入这种无穷的新数对于研究是必要的或者是不可少的。”
3.
悲剧式的后半生
康托尔的研究成果发表之后,由于他关于连续性和无穷的研究从根本上背离了数学
中关于无穷的使用和解释的传统,所以马上招致当时一些赫赫有名的数学家的激烈攻击。
康托尔的老师,德国数学家克罗内克(L.Kronecker)是这些人中言辞最激烈、攻击时
间最长的一个。虽然康托尔是克罗内克的学生,但由于集合论的内容同克罗内克的主张
大相径庭,所以克罗内克简直到了不能容忍的程度。克罗内克认为,康托尔关于超限数的
研究是一种非常危险的数学“疯病”。因而他用各种尖刻语言粗暴地、连续不断地攻击康
托尔达10 年之久,使得原本正常的学术争鸣变成了赤裸裸的人身攻击。克罗内克甚至在
柏林大学的学生面前公开攻击康托尔,这在许多数学家看来是很过分的事情。
康托尔一直在哈勒大学任教,薪金很微薄,他几次想在柏林得到一个薪金较高、声望
更大的教授职位,但由于克罗内克横加阻挠,使得康托尔想在柏林谋到职位以改善其地位
的努力都遭到挫折。克罗内克的影响还使康托尔的学术论文一再延误发表日期。总之,
克罗内克的专横无理令人震惊,他的激烈攻击使康托尔的精神状态受到极大损害。
除了克罗内克之外,还有一些著名数学家也对集合论发表了反对意见。数学家施瓦
茨(H.原来是康托尔的好友,但他由于反对集合论而同康托尔断交。
A.Schwarz)
在克罗内克等人暴风骤雨般的围攻和反对下,康托尔的精神逐渐崩溃了。他有着俄
罗斯诗人普希金一般的敏感性格,经受不了这种暴风雨式的攻击。尽管有希尔伯特(D.
Hilbert)等著名数学家赞同他的集合论,尽管他的集合论事实上已取得巨大的成功,仍未
能使康托尔感到欣慰和满足。从1884 年春天起,康托尔患了严重的抑郁症。在他生命的
最后几十年里,这种病时时发作,使他不得不经常住进精神病院接受治疗。他变得很自
卑,甚至怀疑自己的工作是否可靠。
难能可贵的是,康托尔从未放弃他一手创立的集合论,他始终顽强地保卫自己的胜利
果实。在抑郁症发作的间歇阶段,康托尔仍然顽强地坚持集合论的研究,而且当每次从抑
郁症发作中恢复过来的时候,他都感到自己的思维变得格外清晰。康托尔在集合论方面
取得的许多非常出色的成果是在抑郁症发作的间歇阶段获得的。然而,长期的精神折磨
所造成的危害毕竟是不容忽视的,由于健康状况逐渐恶化,1918 年,康托尔在哈勒大学附
74
离散数学简明教程
属精神病院去世。
康托尔本人也存在思想弱点,这是造成他一生悲剧的内因;外界的反对力量过于强
大,则是造成悲剧的外因。克罗内克的攻击实际上打垮了集合论这一伟大理论的创造者。
一位数学家为自己创立的理论付出这样大的代价,这种事情在数学史上还是不多见的;但
在数学史上,这样的事情绝不是第一次。
公元前5世纪,古希腊杰出学者希巴斯发现了“无理数”(这引发了数学史上的第一次
危机),使得数的概念得以扩充,将数学的研究范围扩展到实数领域。而作为毕达哥拉斯
学派一员的希巴斯却被自己的同门扔进了大海。希巴斯为数学而献出了宝贵的生命,在
科学史上留下了悲壮的一页。
希巴斯与康托尔,两人生活的年代相隔二十多个世纪,但都是年轻有为、才华横溢,都
为数学发展做出了杰出的贡献。但他们却都遭到了顽固保守势力的摧残:一个被扔进大
海,从肉体上被消灭;一个被逼疯,从精神上被摧垮。他们的命运都是那样的凄惨,都是那
样的令人同情,他们所遭受的摧残都是那样的令人愤慨。
4.拨云见日
1891年,克罗内克去世之后,康托尔的处境开始好转。
实际上,当时有许多大数学家支持康托尔的集合论,如戴德金。另外,瑞典的数学家
米塔-列夫勒(G.Mitag-Lefler)在自己创办的国际性数学杂志上把康托尔关于集合论的
论文用法文转载,从而大大促进了集合论在国际上的传播。
1897年,在第一次国际数学家大会上,康托尔的成就得到承认。霍尔维茨(W.A.
Hurwitz)在对解析函数的最新进展进行概括时,就对康托尔的集合论的贡献进行了阐
述。伟大的哲学家、数学家罗素称赞康托尔的工作“可能是这个时代所能夸耀的最巨大的
工作”。
1900年,在第二次国际数学大会上,为了捍卫集合论而勇敢战斗的希尔伯特又进一
步强调了康托尔工作的重要性,他把连续统假设列为20世纪初有待解决的23个主要数
学问题之首。希尔伯特宣称:“没有人能把我们从康托尔为我们创造的乐园中驱逐出
去。”希尔伯特所说的“乐园”就是指集合论。
事实证明希尔伯特是对的。克罗内克等人并未能阻止集合论的发展,也未能阻止绝
大多数数学家最终把集合论看作现代数学中理所当然的组成部分。特别自1901年勒贝
格积分产生以及勒贝格的测度理论充实了集合论之后,集合论得到了公认,康托尔的工作
获得了极高的评价。当第三次国际数学大会于1904年召开时,现(“) 代数学不能没有集合
论”已成为共识。真金不怕火炼,康托尔的思想终于大放光彩。康托尔的贡献得到举世
公认。
今天,集合论已成为整个数学大厦的基础。如果没有集合论,就很难对现代数学有深
刻的理解。集合论的创立不仅对数学基础研究有重要意义,而且对现代数学的发展也有
深远的影响,并且深深影响了现代哲学和逻辑。
3.1.2
罗素悖论
罗素悖论由英国数学家伯特兰·罗素提出,可以形式化地描述如下:
75
第
3
章 集合论初步
设集合S={A|
A
是集合,且A.A}。若S∈S,则
S
是集合
S
的元素,则根据
S
的
定义,有S.S,与假设矛盾;若S.S,则
S
是不以自身为元素的集合,则根据
S
的定义,
有S∈S,与假设矛盾。
1.
罗素悖论的提出
世界文学名著《唐·吉诃德》中有这样一个故事。
唐·吉诃德的仆人桑乔·潘萨跑到一个小岛上,成了这个岛的国王。他颁布了一条
奇怪的法律:每一个到达这个岛的人都必须回答一个问题———“ 你到这里来做什么?” 如
果回答对了,就允许他在岛上游玩;而如果回答错了,就要把他绞死。每一个到岛上来的
人,或者是尽兴地游玩,或者是被吊上绞架。有多少人敢冒死到这个岛上去玩呢?
一天,有一个胆大包天的人来了。他照例被问了这个问题,而这个人的回答是:“ 我
到这里来是要被绞死的。”桑乔·潘萨是让他在岛上游玩还是把他绞死呢? 如果让他在岛
上游玩,那就与他说的“要被绞死”的话不相符,也就是说,他说“要被绞死”是说错了。既
然他说错了,就应该被处以绞刑。但是,如果桑乔·潘萨要把他绞死,这时他说的“要被绞
死”就与事实相符,从而他的回答就是对的,既然他答对了,就不该被绞死,而应该让他在
岛上玩。桑乔·潘萨发现,他的法律无法执行,因为不管怎么执行,都使法律受到破坏。
桑乔·潘萨思索再三,最后让卫兵把那个人放了,并且宣布这条法律作废。这是一条
悖论。
罗素提出的理发师悖论与之相似。在某个城市中有一位理发师,他的广告词是这样
写的:“ 本人的理发技艺十分高超,誉满全城。我将为本城所有不给自己刮脸的人刮脸,
我也只给这些人刮脸。我对各位表示热诚欢迎!” 来找他刮脸的人络绎不绝,自然都是那
些不给自己刮脸的人。可是,有一天,这位理发师从镜子里看见自己的胡子长了,他本能
地抓起了剃刀。他能不能给自己刮脸呢? 如果他不给自己刮脸,他就属于“不给自己刮脸
的人”,他就要给自己刮脸;而如果他给自己刮脸,他又属于“给自己刮脸的人”,他就不该
给自己刮脸。
理发师悖论与罗素悖论是等价的。如果把每个人看成一个集合,这个集合的元素被
定义成这个人刮脸的对象。那么,理发师宣称,他的元素都是本城不属于自身的那些集
合,并且本城所有不属于自身的集合都属于他。那么他是否属于他自己? 这样就由理发
师悖论得到了罗素悖论。反过来的变换也是成立的。
2.
产生背景
19 世纪下半叶,康托尔创立了集合论。在集合论刚产生时,曾遭到许多人的猛烈攻
击,但不久这一开创性成果就为广大数学家所接受,并且获得广泛而高度的赞誉。数学家
发现,从自然数与康托尔集合论出发,可建立整个数学大厦,因而集合论成为现代数学的
基石。“一切数学成果均可建立在集合论基础上。”这一发现使数学家为之陶醉。1900
年,在国际数学家大会上,法国著名数学家庞加莱就曾兴高采烈地宣称:“ 借助集合论概
念,我们可以建造整个数学大厦…… 今天,我们可以说绝对的严格性已经达到了!” 。
可是,好景不长。1903 年,一个震惊数学界的消息传出:集合论是有漏洞的。这就
是英国数学家罗素提出的著名的罗素悖论,罗素悖论使集合理论产生了危机。罗素悖论
非常浅显易懂,而且它涉及的只是集合论中最基本的概念,所以,罗素悖论一经提出,就在
76
离散数学简明教程
当时的数学界与逻辑学界引起了极大震动。德国的著名逻辑学家弗里兹在他的关于集合
的基础理论著作完稿付印时收到了罗素关于这一悖论的信。他立刻发现,自己忙了很久
得出的一系列结果却被这条悖论搅得一团糟,他只能在其著作的末尾写道:“ 一个科学家
所碰到的最倒霉的事,莫过于在他的工作即将完成时,却发现他所干的工作的基础崩溃
了。数(”) 学的基础被动摇了,这就是所谓的第三次数学危机。
3.
问题解决
随着罗素悖论的提出,引发了数学危机,数学家纷纷提出自己的解决方案。人们希望
能够通过对康托尔的集合论进行改造,对集合定义加以限制来排除悖论,这就需要建立新
的原则。这些原则必须足够狭窄,以保证排除一切矛盾;另一方面,它们又必须充分广阔,
使康托尔集合论中一切有价值的内容得以保存下来。
1908 年,策梅洛在这一原则基础上,提出了第一个公理化集合论体系,在很大程度上
弥补了康托尔朴素集合论的缺陷。除ZF 系统外,集合论的公理系统还有多种,如冯·诺
依曼等人提出的NBG 系统等。
公理化集合系统的建立,成功排除了集合论中的悖论,从而比较圆满地化解了第三次
数学危机。但在另一方面,罗素悖论对数学有着更为深刻的影响,它使得数学基础问题第
一次以最迫切的姿态摆到数学家面前,导致了数学家对数学基础问题的研究。而这方面
的进一步发展又极其深刻地影响了整个数学。例如围绕着数学基础问题之争,形成了现
代数学史上著名的三大数学流派,而各流派的工作又都促进了数学的大发展。
3.1.3
笛卡儿
笛卡儿(R.atsu是西方近代资产阶级哲学奠基人之一,
Creis) 他的哲学与数学思想对
历史的影响是深远的。人们在他的墓碑上刻下了这样一句话:“ 笛卡儿,欧洲文艺复兴以
来,第一个为人类争取并保证理性权利的人。”
笛卡儿出生于法国土伦省莱耳市的一个贵族之家,他的父亲是布列塔尼地方议会的
议员,同时也是地方法院的法官。笛卡儿在8岁时进入拉夫勒希的耶稣会学校接受古典
教育,在此期间,他废寝忘食地阅读了大量的数学和哲学书籍。校方为照顾他孱弱的身
体,特许他可以不必受校规的约束,早晨不必到学校上课,可以躺在床上自学。因此,他养
成了早晨卧床思考问题的习惯,一直到老。
1616 年,笛卡儿结束学业后,便背离家庭的职业传统,开始探索人生之路。他投笔从
戎,想借机游历欧洲,开阔眼界。然而长期的军旅生活使笛卡儿感到疲惫,他于1628 年离
开军队来到荷兰,过着漂泊的生活,但他并没有停止思考。在荷兰长达20 年的时间里,他
集中精力做了大量的研究工作。他在1634 年写了《论世界》,书中总结了他在哲学、数学
和许多自然科学问题上的看法。1641 年,他出版了《形而上学的沉思》。1644 年,他又出
版了《哲学原理》等。1649 年,应瑞典女王克里斯蒂安的邀请,笛卡儿来到了斯德哥尔摩,
任宫廷教师。由于他身体孱弱,不能适应那里的气候,到那里不久便抱病不起,于第二年
逝世。
笛卡儿是欧洲近代哲学的奠基人之一,黑格尔称他为“现代哲学之父”。笛卡儿的思
想自成体系,熔唯物主义与唯心主义于一炉,在哲学史上产生了深远的影响。笛卡儿的哲
第3 章 集合论初步 77
学思想对后来的哲学和科学的发展产生了深远的影响。
笛卡儿在数学上也有非凡的成就,推动了数学发展的进程。1637年,笛卡儿发表了
《几何学》,创立了直角坐标系。他进而又创立了解析几何学,表明了几何问题不仅可以归
结为代数形式,而且可以通过代数变换来发现和证明几何性质。解析几何的出现,改变了
自古希腊以来代数和几何分离的局面,把相互对立的“数”与“形”统一了起来,使几何曲线
与代数方程相结合。笛卡儿的这项成就更为微积分的创立奠定了基础,从而开辟了变量
数学的广阔领域。
笛卡儿靠着天才的直觉和严密的数学推理,在物理学方面也做出了有益的贡献。例
如,他在光学、力学方面都取得了杰出的成就。
笛卡儿在其他科学领域还有不少值得称道的创见。他发展了宇宙演化论,创立了旋
涡说。笛卡儿关于太阳起源的旋涡说比康德的星云说早一个世纪,是17世纪最权威的宇
宙论。笛卡儿还提出了刺激反应说,为生理学做出了一定的贡献。
总之,笛卡儿是一位伟大的哲学家,同时又是一位勇于探索的科学家,他所建立的解
析几何在数学史上具有划时代的意义。笛卡儿堪称17世纪及其后的欧洲哲学界和科学
界最有影响的巨匠之一,被誉为“近代科学的始祖”。
3.2 集合的基本概念
定义3.1 下面是集合的一些基本概念。
(1)集合(set):具有某些共性的事物组成的群体。
(2)元素:集合中的个别事物。集合中的元素互不相同,并且没有次序关系。
(3)元素与集合的关系:包括属于(∈)、不属于(.)。
(4)空集:没有任何元素的集合,记作.。
(5)有限集合的基数:有限集合中元素的个数,记作|A|。
(6)含有n 个元素的集合称为n 元集,含有m 个(m ≤n)元素的子集称为集合的m
元子集。
(7)幂集(powerset):以集合A 的所有子集为元素的集合,记作P(A)={x|x.A}。
(8)可数集合:可以按某种顺序列举所有元素的集合,如正整数集合。
(9)不可数集合:不能按某种顺序列举所有元素的集合,如实数集合。
(10)如果其他集合都是集合E 的子集,则称E 为全集。全集通常记作E(Entire)或
者U(Universal)。
(11)对于集合A 、B,如果.x∈A 都有x∈B,那么A .B,称A 包含于B。
(12)对于集合A 、B,如果.x∈A 都有x∈B,而且$x∈B,x.A ,那么A .B,称A
真包含于B。
(13)对于集合A 、B,如果A .B 并且B.A ,那么A =B,称A 和B 相同。
定义3.2 集合表示方法有多种。
(1)元素列举法。将所有元素按某种顺序列举在花括号内,元素间用逗号隔开。例
如,A ={1,2,3}。
78
离散数学简明教程
(2)属性表示法。在花括号内注明元素符号及元素属性。例如,
A
={x|x∈R且
x2≤25 }。
(3)常用的集合符号。
N:自然数集合;
Q:有理数集合;
Q+:正有理数集合;
Q-:负有理数集合;
Z:整
数集合;
Z+:正整数集合;
Z-:负整数集合;
C:复数集合;
R:实数集合;
R+:正实数集
合;
R-:负实数集合;.:空集。
定义3.
B
是集合。
3
Ac
、
c∈
A
或c∈B}
(1)称C={|是
A
与
B
的并集,记作C=A∪B
。
c|
(2)称C={c∈
A
且c∈B}是
A
与
B
的交集,记作C=A∩B
。
c|
(3)称C={c∈
A
且c.B}为
A
与
B
的差集,记作C=A-B。
(4)若
A
是全集
E
的子集,称C={x|x∈
E
且x.A}为
A
的补集,记作C=~A。
(5)称C=(A-B)∪(B-A)为
A
与
B
的对称差集,记作A..B。
定义3.为了使得集合表达式更为简洁,对集合运算的优先顺序做如下规定。
4
(1)称并、交、幂集、补运算为一类运算,称差、对称差运算为二类运算。
(2)一类运算优先于二类运算。
(3)一类运算之间按从右向左的顺序进行。
(4)二类运算之间由括号决定先后顺序
。
定理3.空集.是任何集合的子集(证明略)
。
1
推论:空集是唯一的。
定理3.2
如果集合
A
是有限集合且|A|=n,则
A
的幂集的基数|P(A)|=2n
。
证明:
0
A
的含有0个元素的子集(0元子集)有Cn
个
。
A
的含有1个元素的子集(1元子集)有C1 个
。
n
……
n
A
的含有
n
个元素的子集(
n
元子集)有Cn
个
。
根据二项式公
式
n=C0 nX1Yn-1+
…+CnY0
(
X
+Y)nX0Yn
+C1 nXn
令
X
=1,1,
有
Y=
n
0
n
n+C1
2=Cn+
…+Cn
由此得知:
A
有2n
个子集,|P(A)|=2n 。
13
A、
a,c}
B)
(
定理3.
B
是集合,A-B=A∩(~证明略)
。
例3.求集合A={b,的幂集
。
解:将
A
的子集按照基数从小到大的顺序分类
:
0元子集,即空集,只有一个:.。
1元子集,即单元集,3 个:{b},{}。
有C1a},{
c
2元子集,有C2a,a,b,
3 个:{b},{c},{c}。
3 个:{b,}。
c},{}}。
3
则
元子集
A
的幂集是
,有C3P(A)
a=
,
{.
c
,{a},{b},{a,b},{a,c},{b,c},{a,b,
c
79
第
3
章 集合论初步
例3.2
求集合A={.,{.}} 的幂集
。
解:将
A
的子集按照基数从小到大的顺序分类
:
0元子集,即空集,只有一个:.
。
1元子集,即单元集,2 个:{.},{{.}}
。
有C1
2元子集,有C2
2 个:{.,{.}}
。
则
A
的幂集是P(A)={.,{.},{{.}},{.,{.}}}
。
例3.判断下列命题的真假
。
3
(1)... 。
(2).∈. 。
(3)..{.}。
(4).∈{.}。
(5)|.|=0
。
(6){x}∈{x,{x}}-{{x}}
。
(7){x}.{x,{x}}-{{x}}
。
(8)S..S=S
。
(9)S...=ST。
=.
,
(10)如果S-则S=T
。
解:命题(1)、(3)、(4)、(5)、(7)为真,命题(2)、(6)、(8)、(9)、(10)为假
。
3.集合的基本运算
3
定理3.下面是集合运算的主要定律, B、
C
表示任意集合,.表示空集,E
4
其中A、
表示全集(证明略)。
幂等律: A∪A=
A
A∩A=
A
结合律:(A∪B)∪C=A∪(B∪C)
(A∩B)∩C=A∩(B∩C)
(A..B)..C=A..(B..C)
交换律
:
A∪B=B∪
A
A∩B=B∩
A
A..B=B..
A
分配律
:
A∪(B∩C)=(A∪B)∩(A∪C)
A∩(B∪C)=(A∩B)∪(A∩C)
同一律
:
A∪.=
A
A∩E=
A
A...=
A
零律
:
A∪E=
E
A∩.=
.
80
离散数学简明教程
A..A=
.
排中律: A∪~A=
E
矛盾律: A∩~A=
.
吸收律: A∪(A∩B)=
A
A∩(A∪B)=
A
德摩根律
:
A-(B∪C)=(A-B)∩(A-C)
A-(B∩C)=(A-B)∪(A-C)
~(B∪C)=~B∩~
C
~(B∩C)=~B∪~
C
~.=
E
~E=
.
双重否定律: ~(~A)=
A
定理3.容斥原理(也称包含排斥原理,证明略)
。
5
设A1,A2,…,An
为有限集合,
|A1∪A2∪…∪An|
= Σ(n) |Ai|-Σ |Ai
∩Aj|
+
i=11≤i<j≤
n
Σ |Ai
∩Aj
∩Ak|
+
…
+
1≤i<j<k≤
n
n
例如,设A1、A2、A3 为有限集,则
(-1)1|A1∩A2∩…∩An|
|A1∪A2|=|A1|+|A2|-|A1∩A2|
|A1∪A2∪A3|=|A1|+|A2|+|A3|-|A1∩A2|-|A1∩A3|
例3.设|A|3,
|A2∩A3|+|A1∩A2∩A3|
求|B|、|
A
∩B|、-B|和
|A..B|。
4
=|P(B)|=64,|P(
A
∪B)|=256, |
A
解:
因为|P(B)|=64,所以|B|=6。
因为|P(A∪B)|=256,所以|
A
∪B|=8。根据容斥原理,|
A
∪B|=|A|+|B|
|A∩B|,即8=3+6-|A∩B|,因此|A∩B|=1。
根据文氏图,|A-B|=2,|A..B|=2+5=7。
5
JohnVenndiagram)
定义3.文氏图(是表示集合的直观图形,其中,闭合曲线包围
区域中的所有点组成一个集合。使用文氏图,可以方便直观地解决有穷集合的计数问题。
在画文氏图的过程中,首先画一个大矩形,表示全集E(有时为简单起见,可将全集省
略)。其次,在矩形内画一些圆(或任何其他的适当的闭合曲线), 用圆的内部表示集合,不
同的圆代表不同的集合。如果没有关于集合不交的说明,则任何两个圆均彼此相交。文
氏图中的阴影区域表示新组成的集合。
(1)并运算可以表示成文氏图,如图3.其中阴影区域代表A∪B)。
1所示(
(2)交运算可以表示成文氏图,如图3.其中阴影区域代表A∩B)。
2所示(
第
3
章 集合论初步
81
图3.1
A∪
B
的文氏图图3.
2
A∩B的文氏图
(3)补运算可以表示成文氏图,如图3.其中阴影区域代表~A)。
3所示(
(4)差运算可以表示成文氏图,4所示( B)。
如图3.其中阴影区域代表A
(5)对称差运算可以表示成文氏图,5所示(
如图3.其中阴影区域代表A..B)。
图3.~图3.
B
的文氏图
5
A..
B
的文氏图
3 A
的文氏图
4
A-图3.
例3.判断下列命题的真值。
5
(1)如果S∪T=S∪
M
,则T=
M
。
(2)如果~S∪T=E,则S.T。
(3)若A×B.A×C,一定有B.C
。
(4)A-B=B-A.A=B
。
(5)A-B=A.B=.
。
(6)A-(B∪C)=(A-B)∩(A-C)
。
(7)如果A∩B=B,则B=E
。
(8)A-(B∪C)=(A-B)∪C
。
(9)~(A-B)=~(B-A)。
(10)~(A∩B).A。
(11)(A∩B)∪(B-A).A。
解:命题(2)、(4)、(6)为真,命题(1)、(3)、(5)、(7)~(11)为假。
例3.设A={1,B={3}, A∪B)A∩B)0,2,
6
0,2},2,那么A..B=(-(={1,3}
{2}={0,1,3}。
例3.已知某地产品出口企业共520 家,其中220 家企业有产品销往美洲,185 家
7
企业有产品销往欧洲,245 家企业有产品销往日本。这520 家企业中,仅向美洲出口产品
的企业有150 家,仅向欧洲出口产品的企业有110 家,仅向日本出口产品的企业有
150 家
(1
。
)有产品销往美洲和欧洲的企业有多少家?
(2)有产品销往美洲和日本的企业有多少家?
(3)有产品销往欧洲和日本的企业有多少家?
(4)同时向美洲、欧洲、日本出口产品的企业有多少家
?
解:用文氏图解决这个问题
。
令全集是所有产品出口企业组成的集合,记作U,显然|U|=520 。
令
82
离散数学简明教程
A={x|x∈
U
且
x
有产品销往美洲}
E={x|x∈
U
且
x
有产品销往欧洲}
J={x|x∈
U
且
x
有产品销往日本}
根据题意有:|A|=|E|185,J|245, E|150,E-=
220,=|=并且|J-A-=|A-J|
150,|E-A-J|=110 。只需计算|A∩E|、|A∩J|、|E∩J|和|A∩E∩J|。
文氏图如图3.
其中,X=
6所示。
Y1=A∩E,Y3=E∩J。
A∩E∩J,Y2=A∩J,
令:x=y1=Y1|,|y3=Y3|
,
|X|,|y2=Y2|,|则有以下四元一次方程组:
|
J
-
A
-E|=|J|-y2-y3+
x
|
A
-E-J|=|A|-y1-y2+
x
|
E
-
A
-J|=|E|-y1-y3+
x
|U|=|A|+|E|+|J|-y1-y2-y3+
x
代入已知数值,
有
x-y2-y3+245=150
x-y1-y2+220=150
x-y1-y3+185=110
-y1-y2-y3+220+185+245=520
y1=y2=y3=
解得x=20,35,(x) 55,60 。
即,有产品销往美洲和欧洲的企业共35 家,有产品销往美洲和日本的企业共55 家,
有产品销往欧洲和日本的企业共60 家,同时向美洲、欧洲、日本出口产品的企业共20 家。
例3.8
有100 名程序员,其中47 名熟悉FORTRAN 语言,35 名熟悉Pascal语言,
23 名熟悉这两种语言。有多少人对这两种语言都不熟悉?
解:设F、
P
分别表示熟悉FORTRAN 和Pascal语言的程序员集合。问题对应的文
氏图如图3.
7所示。
图3.例3.图3.8的文氏图
67的文氏图
7
例3.
将熟悉两种语言的对应人数23 填到A∩
B
的区域内,不难得到:
|F-P|=|F|-|
F
∩P|=47-23=24
|
P
-F|=|P|-|
F
∩P|=35-23=12
从而
|
F
∪P|=24+23+12=59
83
第
3
章 集合论初步
|
~
(
F
∪P)|=100-59=41
所以这两种语言都不熟悉的有41 人。
例3.求11000( 中不能被5、8整除的数有多少个。
9
~包含1和1000) 6、
解:(1)S={x|x∈Z∧1≤x≤1000 }。
(2)A={x|x∈S∧
x
可被5整除}。
(3)B={x|x∈S∧
x
可被6整除}。
(4)C={x|x∈S∧
x
可被8整除}。
用[x]表示小于或等于
x
的最大整数,也就是对
x
进行下取整。lcm(x1,x2,…,xn
)
表示x1,x2,…,的最小公倍数(owetcnmutpe)。则有
xn
lsommolil
|A|=[1000/5]=200
|B|=[1000/6]=166
|C|=[1000/8]=125
|
A
∩B|=[1000/lcm(5,6)]=33
|
A
∩C|=[1000/lcm(5,8)]=25
|
B
∩C|=[1000/lcm(6,8)]=41
|
A
∩
B
∩C|=[1000/lcm(5,8)]=8
6,
对应的文氏图如图3.
8所示。
可知,不能被5、6和8整除的数有1000-(150+25+100+17+8+33+67)=
600 个。
例3.对24 名懂外语的科技人员掌握外语的情况进行调查。统计结果如下:懂
英语、日语
10
、德语和法语的人分别为13 、5、10 和9人,其中同时懂英语和日语的有2人,懂
英语、德语和法语中的两种语言的都是4人。已知懂日语的人既不懂法语也不懂德语,分
别求只懂一种语言(英、德、法、日)的人数和懂3种语言的人数。
解:令A、B、C、
D
分别表示懂英语、法语、德语、日语的人的集合。根据题意画出文
氏图,如图3.只懂英语、
9所示。设同时懂3种语言的有
x
人, 法语或德语一种语言的分
别为y1、y2 和y3 人。将
x
和y1、y2、y3 填入图3.然后依次填入其他区
9中相应的区域,
域的人数。
图3.根据题意画出的文氏图例3.
图3.10
的文氏图
89
84
离散数学简明教程
根据已知条件,列出方程组
:
y1+2×
(4-x)+x+2=13
y2+2×
(4-x)+x=
9
y3+2×
(4-x)+x=10
解得x=1,4,
y12+
,
y2+
3
y
。
3+3×
(4-x)+x=19
y1=y2=y3=
同时懂3种语言的有1人,懂英语的有4人,懂德语的有2人,懂法语的有3人,懂日
语的有5人。
例3.已知A..B=证明B=C。
11
A..C,
证明:
已知A..B=A..C,所以有
A..(A..B)=A..(A..C)
.(A..A)..B=(A..A)..
C
(结合律)
....B=...
C
.B...=C... (交换律)
.B=
C
例3.一个班有50 个学生。第一次考试中有26 人得满分,第二次考试中有21 人
12
得满分。如果两次考试中都没有得满分的有17 人,两次考试中都得满分的有多少人?
解:令A、
B
分别表示第一次考试、第二次考试得满分人的集合。根据题意画出文氏
图,如图3.
10 所示
。
首先填入A∩
B
中的人数,是本题所求,设它为x
。
然后填入其他区域中的人数,并列出方程如下
:
解得x=14 。
(26-x)+x+
(21-x)+17=50
也就是说,在两次考试中都得满分的有14 人。
例3.13
某班有学生60 人,其中有38 人学习Pascal语言,有21 人学习COBOL 语
言,有16 人学习C语言,有3个人这3种语言都学习,有2人这3种语言都不学习。仅学
习两门语言的学生数是多少?
解:令P、B、
C
分别表示学习Pascal语言、COBOL 语言、C语言的学生的集合。根
据题意画出文氏图,如图3.
11 所示。
图3.例3.图3.13
的文氏图
10
12
的文氏图11
例3.
第
3
章 集合论初步
85
列出方程:
2+
(21-3-x-y)
+
(16-x-z-3)
+
(38-y-z-3)+x+y+z+3=60
解得x+y+z=11 。
也就是说,仅学习两门语言的学生数是11 人。
例3.14
对60 个学生参加课外活动的情况进行调查。结果发现,25 人参加物理学
小组,26 人参加化学小组,26 人参加生物学小组,9人既参加物理学小组又参加生物学小
组,11 人既参加物理学小组又参加化学小组,8人既参加化学小组又参加生物学小组,8
人什么小组也没参加。回答下列各问题:
(1)有多少人参加了3个小组?
(2)只参加一个小组的有多少人
?
解:令A={x|
x
参加物理学小组}, 根据题意
,
|A|=25 。
令B={x|
x
参加化学小组}, 根据题意,|B|=26 。
令C={x|
x
参加生物学小组}, 根据题意,|C|=26 。图3.根据题意画
对应的文氏图如图3.12
出的文氏图
12 所示
。
设同时参加3个小组的人数为x,即|A∩B∩C|=x
。
由已知条件
得
|
A
∩B|-|
A
∩
B
∩C|=11-
x
|
A
∩C|-|
A
∩
B
∩C|=9-
x
|
B
∩C|-|
A
∩
B
∩C|=8-
x
|
A
-(
B
∪C)|=|A|-(11-x)-(9-x)-x=5+
x
|B-(
A
∪C)|=26-(11-x)-(8-x)-x=7+
x
|C-(
A
∪B)|=26-(9-x)-(8-x)-x=9+
x
所以
5+x+7+x+9+x+11-x+9-x+8-x+x+8=60
解得x=3
。
也就是说,有3人同时参加了3个小组
。
只参加一个组的人数为
(5+x)
+
(7+x)
+
(9+x)=(5+3)
+
(7+3)
+
(9+3)=30
3.笛卡儿积
4
定义3.若A、称<a,
a
为第一元
6 B
是集合,.a∈A,.b∈B, b>为二元有序组,
素,
b
为第二元素。称
C
={<a,b>|a∈A,b∈B}为
A
与
B
的笛卡儿积(Cartesian
t), 记作C=A×B,符号×表示笛卡儿积运算。produ
例
c3.15
设A={b},0,2},
a,B={1,则
A
×B
={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}
B
×A
={<0,
b
>,<1,
b
>,<2,
b
>}
a
>,<0,
a
>,<1,
a
>,<2,
86 离散数学简明教程
由排列组合的知识不难证明,如果|A|=m ,|B|=n,则|A ×B|=m ×n。
有序对中的元素是有序的,有序对<x,y>具有以下性质:
(1)当x≠y 时,<x,y>≠<y,x>。
(2)<x,y>=<u,v>的充分必要条件是x=u 且y=v。
例3.16 已知<x+2,4>=<5,2x+y>,求x 和y。
解:由有序对相等的充分必要条件,有方程组
x +2=5
2x +y =4
解得x=3,y=-2。
定理3.6 笛卡儿积运算满足如下定律,其中A 、B、C 代表不同的集合(证明略)。
(1)笛卡儿积运算不满足交换律,即
A ×B ≠B ×A
(2)笛卡儿积运算不满足结合律,即
A × (B ×C)≠ (A ×B)×C
(3)笛卡儿积运算对于并运算满足分配律,即
A × (B ∪C)=(A ×B)∪ (A ×C)
(A ∪B)×C =(A ×C)∪ (B ×C)
(4)笛卡儿积运算对于交运算满足分配律,即
A × (B ∩C)=(A ×B)∩ (A ×C)
(A ∩B)×C =(A ×C)∩ (B ×C)
(5).×A =A ×.=.。
(6)A .C∧B.D .A ×B.C×D 。
定义3.7 若A1,A2,…,An 是n 个集合,A1,A2,…,An 的n 阶笛卡儿积是集合C=
{<a1,a2,…,an >|a1∈A1,a2∈A2,…,an ∈An},记作C=A1×A2×…×An 。
例如,R是实数集合,则:R×R是平面点坐标的集合,代表平面;R×R×R是三维
空间点坐标的集合,代表三维空间。
例3.17 设A ={1,2},求P(A)×A 。
解:P(A)×A ={.,{1},{2},{1,2}}×{1,2}
={<.,1>,<.,2>,<{1},1>,<{1},2>,<{2},1>,
<{2},2>,<{1,2},1>,<{1,2},2>}
例3.18 设A 、B、C、D 为任意集合,判断以下命题是否为真,并说明理由。
(1)A ×B=A ×C TB=C。
(2)A -(B×C)=(A -B)×(A -C)。
(3)A =B∧C=D TA ×C=B×D 。
(4)存在集合A ,使得A .A ×A 。
解:
(1)不一定为真。当A =.,B={1},C={2}时,有A ×B=.=A ×C,但B≠C。
(2)不一定为真。当A =B={1},C={2}时,有
第
3
章 集合论初步
87
A-(
B
×C)={1}-{<1,2>}={1}
(
A
-B)
×
(
A
-C)=.
×
{1}
=
.
(3)为真。由等量代入的原理可证。
(4)为真。当A=. 时有A.A×A
成立。
3.5
习题
1. 在0.的线上应填上() 符号
。
A.= B.∈ C.. D.
.
2.设A={.},B=P(P(A)), 下列选项中错误的是( )。
A..∈
B
B.{.}∈
B
C.{{.}}∈
B
D.{.,{.}}∈P(A)
3.对任意集合A、B、C,下述论断中正确的是( )。
A. 若A∈B,B.C,则A∈
C
B. 若A∈B,B.C,则A.
C
C. 若A.B,B∈C,则A∈
C
D. 若A.B,B∈C,则A.
C
4.设P={x|(x+1)2≤4},Q={x|x2+16≥5x}, 则选项() 正确
。
A.Q.
P
B.Q.
P
C.P.
Q
D.Q=
P
5.下列各选项中错误的是( )。
A.... B..∈. C...{.} D..∈{.}
6.设S={1,2}, 二元有序组<x+2,4> 和<5,2x+y>相等,则
x
与
y
为( )。
A.x=y=B.2,1
1,2 x=y=
3,3,
C.x=y=2 D.x=y=-2
7.分别求下列集合的幂集
。
(1)P(.)
。
(2)P({.})
。
(3)P(.,{.})
。
(4)P({1,{2,3}})。
a}
}
8.求集合A={.,{的幂集。
9.假设在10 名青年中,有5名是工人,7名是学生,其中兼有工人与学生双重身份的
青年有3名。既不是工人又不是学生的青年有几名?
10.对60 人的调查表明,有25 人阅读《每周新闻》杂志,有26 人阅读《时代》杂志,有
26 人阅读《财富》杂志,有9人阅读《每周新闻》和《财富》杂志,有11 人阅读《每周新闻》和
《时代》杂志,有8人阅读《时代》和《财富》杂志,还有8人什么杂志也不阅读。阅读全部3
种杂志的有多少人? 只阅读《每周新闻》的有多少人? 只阅读《时代》的有多少人? 只阅读
《财富》的有多少人? 只阅读一种杂志的有多少人?
11.化简((A∪B∪C)∩(A∪B))-((A∪(B-C))∩A)。
12.设
F
表示一年级大学生的集合,
S
表示二年级大学生的集合,
M
表示数学专业学
生的集合,
R
表示计算机专业学生的集合,
T
表示听离散数学课的学生的集合,
G
表示星
88
离散数学简明教程
期一晚上参加音乐会的学生的集合,
H
表示星期一晚上很迟才睡觉的学生的集合。
下列各句子所对应的集合表达式分别是什么?
(1)所有计算机专业二年级的学生在学离散数学课。
(2)这些且只有这些学离散数学课的学生,或者星期一晚上去听音乐会的学生,在星
期一晚上很迟才睡觉。
(3)听离散数学课的学生都没有参加星期一晚上的音乐会。
(4)这个音乐会只有大学一、二年级的学生参加。
(5)除去数学专业和计算机专业以外的二年级学生都去参加音乐会。
13.设
S
表示某人所有树的集合,
M
是珍贵的树的集合,
T
是去年栽的树的集合,
N
是果树的集合,
P
是果园中的树的集合。
M
.S,
N
.S,T.S,P.S。
前提:
(1)所有珍贵的树都是去年栽的。
(2)所有果树都在果园里。
(3)果园里没有去年栽的树
。
结论
:
(1)所有果树都是去年栽的。
(2)没有一棵珍贵的树是果树
。
前提和结论的集合表达式分别是什么
?
14.用文氏图表示A..B..C。
15.设S、T、
M
为集合,分别画出下列各集合的文氏图
:
(1)(S∪
M
)-T
。
(2)T-(S∪
M
)
。
(3)S∩(T∪
M
)
。
(4)(S∩
M
)∪(S-T)
。
(5)(T..
M
)-S
。
16.设A、
B
为子集,
E
为全集,分别画出下列各集合的文氏图
:
(1)A∩B=.
。
(2)A.B
。
(3)A-B
。
(4)A∪B
。
(5)A∩B
。
(6)~A
。
(7)A..B
。
(8)(A∩B)-C
。
17.通过实例分析笛卡儿积和集合的具体应用。
第4章
二元关
系
本章主要包括关系的表示、关系的运算、关系的性质、关系的闭包、等价关系、偏序关
系、函数等。
4.关系的表示
1
在日常生活中,存在大量的关系,例如父子关系、上下级关系、朋友关系等。因为
n
元有序组可以表达
n
个客体之间的关系,因此用有序组表达关系这个概念。
定义4.若A、那么A×B
的任一子集称为从集合
A
到集合
B
的一种二
1 B
是集合,
元关系(binaryrelation), 记作R:A→B。二元关系简称关系。
若
R
是从集合
A
到集合
A
的一种二元关系,即
R
.
A
×A,则称
R
是集合
A
上的
关系。
b>∈R,、记作aa,
若<a,则称元素ab
符合关系R, Rb
或R(b)
。
根据定义,显然有以下推论
:
(1)关系是集合,一种关系是一个集合。
(2)关系是有序对构成的集合,二元关系是二元有序对构成的集合
。
(3)R.A×B,R∈P(A×B)
。
(4)如果|A|=m,|B|=n,则从
A
到
B
有2mn
种不同的关系。
这是因为,如果|A|=m,|B|=n,则|A×B|=mn,P(A×B)=2mn
,也就是说,集合
A×B
有2mn
个子集。A×B
的每个子集分别是从集合
A
到集合
B
的一种二元关系,因
此从集合
A
到集合
B
有2mn
种不同的关系。
(5)映射f:A→
B
是一种特殊的关系。
集合
A
上的二元关系的数目依赖于
A
中的元素个数。如果|A|=n,那么|A×A|=
n2,A×A
的子集就有2n2个。每一个子集代表一个
A
上的二元关系,所以集合
A
上有
2n2个不同的二元关系。例如|A|=3,则集合
A
上有23×3=512 个不同的二元关系。
同一个集合上可以有多种关系。例如,一个班的所有同学作为一个集合,在这个集合
上,可以定义同乡关系、同龄关系、年长关系、年少关系、学号顺序关系等。
定义4.关系的定义域和值域。
2
关系
R
的定义域domR={x|.y,<x,y>∈R}是
R
中每个有序对的第一元素构
成的集合。
90
离散数学简明教程
关系
R
的值域rany|.x,y>∈R}是
R
中每个有序对的第二元素构成的
集合。
R={<x,
定义4.下面是几种特殊的关系。
3
(1)称空集.为空关系(emptyrelation)。
(2)称E=A×B
为从集合
A
到集合
B
的全域关系(universalrelation)。
(3)称EA
=A×A
为集合
A
上的全域关系。
(4)称IA
={x>|为集合
A
上的恒等关系(dniaeain)。
<x,x∈A} ietclrlto
例如,A={1,2,3}, 则集合
A
上的恒等关系IA
={<1,1>,<2,2>,<3,3> }。
关系有多种表示方法。因为关系是有序对构成的集合,因此可以通过列举法、描述法
表示关系这种集合;除此之外,还可以通过矩阵和图形表示关系,以便引入线性代数和图
论的知识,深入研究关系。
定义4.设A={x2,…,xn R
是集合
A
上的关系。令图G=<V,其中
4
x1,},E>,
顶点集合V=A,xj
∈V,<xi,Rxj
。称图
G
为
R
的
E
为边集。对于.xi,xj
>∈E.xi
关系图,记作GR
。
(1)在空关系的关系图G.中,不存在有向边和环,只有点。
(2)在恒等关系的关系图GI
中,每个点上都有一个有向环,不存在有向边。
(3)在全域关系的关系图GE
中,每个点上都有一个有向环,任意两点之间都有两条
方向相反的有向边。
定义4.设有限集合A={x2,…,},y2,…,}, 则从集合
A
到集
5
x1,xm
B={y1,yn
合
B
的二元关系
R
对应于一个关系矩阵MR
=[ij]其中:
rm×n
,
1<xi,i=n)
xi
>∈
R
rij =
0<xi,(1,2,…,m;j=1,2,…,xi
>.
R
(1)在空关系的关系矩阵中,所有元素都为0。
(2)在恒等关系的关系矩阵中,主对角线上的元素为1,其余元素为0。
(3)在全域关系的关系矩阵中,所有元素都为1。
下面几个例子展示了如何表示关系。
例4.1
求幂集P({.,{.}})={.,{.},{{.}},{.,{.}}} 上的真包含关系。
解:(1)用集合表示真包含关系。
R.={<{.},.>,<{{.}},.>,<{.,{.}},.>,
<{.,{.}},{.}>,<{.,{.}},{{.}}>}
所示
(
。
2)用图
G
(R.)表示真包含关系,如图4.
1
例4.若A={a5},
a2,a4,b1,
b3}, 从集合
A
到集合
B
的关系
R
可以表示为
R={<a1,<a1,<a2,<a2,
2
a1,a3,B={b2,
b1>,b3>,b2>,b3>
,
<a3,b1>,<a4,<a5,
b2>,b2>
}
写出
R
的关系矩阵MR 。
图4.表示真包含关系的图G(
1
R.)