1、第 二 篇集 合 论北京理工大学北京理工大学 郑军郑军谢谢你的关注2019-10-13v十六世纪末十六世纪末 起源起源v十九世纪十九世纪 德国数学家德国数学家康托康托创立创立古典古典 集合论集合论v1900年前后年前后 出现各种出现各种悖论悖论v1908年年 策莫罗建立集合论的公理系统策莫罗建立集合论的公理系统v目前目前 集合论公理系统有两种形式集合论公理系统有两种形式:策莫罗策莫罗-弗兰克尔弗兰克尔-柯很形式柯很形式（ZFC）贝尔内斯贝尔内斯-诺伊曼诺伊曼-葛德尔形式（葛德尔形式（BNG）v在在计算机领域计算机领域得到广泛应用得到广泛应用 集合论溯源集合论溯源谢谢你的关注2019-10-13
2、 康托称集合是康托称集合是“一些确一些确定的、不同的东西的总体，定的、不同的东西的总体，这些东西，人们能够意识到，这些东西，人们能够意识到，并且能够判断一个给定的东并且能够判断一个给定的东西是否属于这个总体西是否属于这个总体”。谢谢你的关注2019-10-13 在一个小岛上有唯一的在一个小岛上有唯一的一位理发师。他宣称：我为一位理发师。他宣称：我为岛上所有不为自己理发的人岛上所有不为自己理发的人理发，而不给那些为自己理理发，而不给那些为自己理发的人理发。发的人理发。”。请问：理发师的头发由谁来请问：理发师的头发由谁来理呢？理呢？谢谢你的关注2019-10-13 令集合令集合S为包含所有不以为包
3、含所有不以自身为元素的那些集合，即自身为元素的那些集合，即S=x|x x 请问：请问：S S吗吗？假定假定S S，那么，那么S 应满足应满足条件条件x x，因此，因此S S。自相矛盾 假定假定S S，那么，那么S 已经满已经满足条件足条件x x，因此，因此S S。又自相矛盾谢谢你的关注2019-10-13包括九个公理包括九个公理外延公理外延公理空集公理空集公理无序对公理无序对公理正则公理正则公理替换公理替换公理方幂集公理方幂集公理集公理集公理无限公理无限公理选择公理选择公理 谢谢你的关注2019-10-13 假定假定A和和B都是集合，如果都是集合，如果任何一个事物属于任何一个事物属于 A也一定
4、也一定属于属于B，属于，属于B 也一定属于也一定属于A，那么那么A和和B是同一个集合，或是同一个集合，或称两个集合称两个集合A和和B相等。相等。外延公理外延公理谢谢你的关注2019-10-13 存在一个不包括任何元素存在一个不包括任何元素的集合。的集合。空集公理空集公理正则公理正则公理 任何一个非空集合任何一个非空集合A一定一定包含一个元素包含一个元素a，A的任何一的任何一个元素都不是个元素都不是 a 的元素。的元素。谢谢你的关注2019-10-13集合论是学习计算集合论是学习计算机科学必备的基础机科学必备的基础知识知识,计算机领域计算机领域的大多数基本概念和理论都可以采的大多数基本概念和理论
5、都可以采用集合论的有关术语来描述和论证用集合论的有关术语来描述和论证,集合论被广泛地应用于形式语言、集合论被广泛地应用于形式语言、编译理论、信息检索、数据结构、编译理论、信息检索、数据结构、算法分析、程序设计、人工智能等算法分析、程序设计、人工智能等领域领域。谢谢你的关注2019-10-1310集合与关系第 三 章谢谢你的关注2019-10-133.1 集合的概念和表示法集合的概念和表示法 集合的概念和表示法v 集合与元素集合与元素v 集合的势集合的势v 集合的表示法集合的表示法v 集合相等集合相等v 子集、全集、空集子集、全集、空集v 幂集及在计算机中的表示幂集及在计算机中的表示谢谢你的关注
6、2019-10-13具有某种性质的客体所汇成的一个整体叫。通常用大写字母大写字母 A,B,C,(或带有下标的字母 A1,B1,C1,)表示集合的名称。特殊的集合采用特殊的记号。3.1 集合的概念集合的概念集合的概念和表示法谢谢你的关注2019-10-13C实数集复数集RQ整数集+z非负整数集P有理数集z素数集常用的集合符号谢谢你的关注2019-10-13英文字母表 鲁迅狂人日记中所有 的汉字我校2004级的全体学生“伊拉克战争”美国部署在海湾地区的航空母舰的集合两条平行线的“交点”的集合谢谢你的关注2019-10-13属于给定集合的任何客体为该集合集合的的成员成员或或元素元素。通常用小写字母小
7、写字母表示。若元素a属于集合A,记作aA(亦称为A包含a；a在A 之中；a是A的成员）若元素a不属于集合A,记作 aA(或aA)(亦称为A不包含a；a不在A 之中；a不是A的成员）元素谢谢你的关注2019-10-13 j:北京 C:中国 U:联合国成员国，Cj，UC jUAeAa A=a,b,c,d 谢谢你的关注2019-10-13F集合中的元素可以是具体的(直观上可以触摸的、可观测的)，也可以是抽象的(想象的)；关于集合概念的说明F集合中的元素是确定的，可以明确区分不同的元素，即集合中的元素是不相同的(相同的元素看作是一个)；谢谢你的关注2019-10-13F元素与集合间的属于关系是确定的.
8、对于某个元素a与某个集合A,要么aA,要么aA,二者必居其一，绝无其他情况产生；关于集合概念的说明F集合中的元素可以是集合,且是无序的；F由元素构成的集合是一个已经形成的整体,而不是正在形成的整体。谢谢你的关注2019-10-13|S|是有限的集合为有穷集合有穷集合（无限为无穷集合）。集合 S 中不同元素的数目称为 S 的基数基数或势势记为|S|或#S.谢谢你的关注2019-10-13V=a,e,i,o,u将集合的元素列举出来例3Zm=1,2,mN=0,1,2,谢谢你的关注2019-10-1322yxIyxS)(xpxS 101xIxxS所必需满足的条件。xS即513xIxxS4是中国的直辖市
9、是中国的直辖市xxS例4 p(x)表示任何谓词若p(b)为真,则bS谢谢你的关注2019-10-13,2,1,baqpaS Sbaq,baqqSq 可以是集合可以是集合集合的元素集合的元素S12abq,baap,baq2,1谢谢你的关注2019-10-13任意两个集合 A 和 B 相等相等的充要条件是 A、B 具有同样的成员具有同样的成员.记作 A=B.否则，记作 A B.)(BxAxxBA)(BxAxx)(AxBxx谢谢你的关注2019-10-13,cccbaa,.1bcaabccba,.2cbaQcbaPQP 1,00)1(.3BxxxABA,.4aa aa 谢谢你的关注2019-10-1
10、3任意两集合A、B,若 A 的每一个元素都是 B 的一个元素,则称 B 包含 A,或说 A 是 B 的子集，A 包含于 B.记作).(ABBA)(BxAxxBAu自反性自反性u传递性传递性谢谢你的关注2019-10-13如果集合 A 的每一个元素都属于B,但集合 B 中至少有一个元素不属于 A,则称 A 为 B 的真子集，记作.BA)(BABABAu传递性传递性谢谢你的关注2019-10-13,cbaba,cbacba,cbaba,edcaba,cbacba谢谢你的关注2019-10-13包含关系：例例:A=a,a与与a的关系的关系成员关系隶属关系:元素与集合之间的关系.即属于和不属于.两个集
11、合间的关系.隶属关系隶属关系:不同层次上的两个集合不同层次上的两个集合包含关系包含关系:同一层次上的两个集合同一层次上的两个集合谢谢你的关注2019-10-13集合A和集合B相等的充要条件是这两个集合互为子集。证明:设任意两个集合A和B相等,则根据定义A和B 有相同的元素,故（x)(xA xB)为真,且 （x)(xB xA)为真,即AB 且 B A反之,若AB 且 BA,假设AB,则根据定义A和B 的元素不完全相同,设有某一元素xA 但 xB,而前提条件为AB,产生矛盾;或设有某一元素xB 但 xA,与条件 BA矛盾,故两集合元素相同,A=B。谢谢你的关注2019-10-13在一个具体问题中，
12、如果所有集合均为某个集合的子集，则称该集合为全集,记为E.)()(xpxpxE谢谢你的关注2019-10-13F全集相当于论域全集相当于论域 若若A 为论域中任一集合为论域中任一集合,则则.EAF全集是有相对性的全集是有相对性的 不同的问题有不同的全集，即使不同的问题有不同的全集，即使是同一个问题也可以取不同的全集是同一个问题也可以取不同的全集.一般情况下一般情况下,全集取得小一些全集取得小一些,问题的描述和处理会简单些。问题的描述和处理会简单些。例如例如:研究平面上直线相交关系研究平面上直线相交关系谢谢你的关注2019-10-13F对于任意一个集合A,不包含任何元素的集合是空集,记为 )()
13、(xpxpx.AF空集是唯一的.谢谢你的关注2019-10-13,.,用空集可构成一些有用的集合,谢谢你的关注2019-10-13由空集和子集的定义可以看到,任何一个非空集合 A,至少有两个不同的子集 A和,即AA和 A,称A和为A的平凡子集.集合中的每个元素都能确定集合中的每个元素都能确定该集合的一个子集该集合的一个子集,即若即若 a A,则则 a A.谢谢你的关注2019-10-13给定集合 A，由集合 A 的所有子集组成的集合,称为集合 A 的幂集，记为 P(A).)(AxxAP谢谢你的关注2019-10-13,1aS,)(11SaSP则,2baS,)(2babaSP则,3cbaS,)(
14、3bacbaSP,cbacbca谢谢你的关注2019-10-13)(xxP)(P),(P,谢谢你的关注2019-10-13,3cbaS,)(3bacbaSP,cbacbca将将 S3 的子集分类的子集分类:0元子集元子集:1元子集元子集:a,b,c 2元子集元子集:a,b,a,c,b,c 3元子集元子集:a,b,cC30C31C32C33n元集、元集、m元子集元子集谢谢你的关注2019-10-13S 1,2,3,.,n将将 S 的子集分类的子集分类:0元子集元子集:1元子集元子集:1,2,.,n 2元子集元子集:1,2,1,3,.,n-1,n 3元子集元子集:1,2,3,1,2,4,.,n-2
15、,n-1,nn元子集元子集:1,2,.,n|P(S)|=+.+=Cn0Cn1Cn2Cn3CnnCn0Cn1Cn2CnnCnkk=0n谢谢你的关注2019-10-13如果有限集合 A有n个元素,则其幂集有2n 个元素。|P(S)|=+.+=Cn0Cn1Cn2CnnCnkk=0n因为(x+y)n=xk yn-k令令 x=y=1,2n=Cnk k=0n.Cnk k=0n谢谢你的关注2019-10-13 为在计算机上表示有限集合S 的幂集的元素，一般需要:给S中各元素规定某种次序,如 a1,an.用一个 n 位的二进制数表示该集合的任意子集 A.当 ai A 时，该二进制数的第 i 位为 1,否则为
16、0.谢谢你的关注2019-10-13,2baS a第一个元素，b第二个元素，00B,10Ba,01Bb 11,Bba,)(2JiBSPi1100ii iJ为二进制数，其中谢谢你的关注2019-10-13nSSP22)(,3cbaS 其中,)(3JiBSPi111000为二进制数ii iJ，nS,10 i,)(JiBSPi12,2,-=n.111000.=iiJ二进制数，nn谢谢你的关注2019-10-133.2集合的运算v 集合的交集合的交v 集合的并集合的并v 集合的补集合的补v 集合的对称差集合的对称差3.2 集合的运算集合的运算 谢谢你的关注2019-10-13)()(BxAxxBAS(
17、1)定义:共同元素若 即 A和B 没有公共元素,则称A和B不相交不相交.,BAAB文氏图E谢谢你的关注2019-10-13.ECBACBA)()(.AAAA.BA.CAEA.DABBA交换律交换律结合律结合律谢谢你的关注2019-10-13AB文氏图EBAS)()(BxAxx(1)定义:属于A或属于B谢谢你的关注2019-10-13.ECBACBA)()(.AAAA.BEEA.CAA.DABBA交换律结合律谢谢你的关注2019-10-13吸收律吸收律)()()(CABACBA分配律分配律.F)()()(CABACBAABAA)(.GABAA)(谢谢你的关注2019-10-13 试证)()()(
18、CABACBAABCABCABCABCCB BA)()(CABACA ABC)(CBA文氏图相等谢谢你的关注2019-10-138,48,28,2,1321AAA831iiA8,4,2,131iiAmimimAAAA121.iimAAAA121.例谢谢你的关注2019-10-13ABE(1)定义:属于A 不属于B BAS)()(BxAxx谢谢你的关注2019-10-13,6,5,2A7,4,2,1B BA,2,1,0A3,2,1B BA AB,6,5,0.3 AB.7,4,1谢谢你的关注2019-10-13.DBCACBA)()(.C)()()(CBCACBA)()(CBACBA.B.A)(B
19、AABA谢谢你的关注2019-10-13 对任意两个集合A,B,试证BABAA)(证明证明对于任意的x)(BAAx)(BxAxAxxx)(BAxAxxx)(BAxAxxx)(BxAxAxxxBxAxxxBAx因为 x 是任意的,所以有)()(BAxBAAxx的真值为T,BABAA)(因此谢谢你的关注2019-10-13 (1)定义:A关于全集E的补AEAS)(Axx)()(AxExxAxxAE谢谢你的关注2019-10-13 .CEAA.DAA.AAAA)(.FBABA)(BABA)(.E.BEE谢谢你的关注2019-10-13 .GEBA BA且的充分必要条件为AB若,4,3,2,1E2,1
20、A则4,3A例谢谢你的关注2019-10-13 (1)定义:或属于A或属于B)()(ABBABAS文氏图BA)()(BxAxxBAx谢谢你的关注2019-10-13 .AABBA)()(CBACBA.E.CAA.B AA)()(ABBABA.D谢谢你的关注2019-10-13 试证ABCBA ABCCB ABCCBA)(ABC)(CBA文氏图相等)()(CBACBA谢谢你的关注2019-10-13AAAAAA幂等律幂等律ABBAABBA交换律交换律A,B,C为E的任何子集,则有CBACBA)()(CBACBA)()(结合律结合律AA)(对合律对合律)()()(CABACBA分配律分配律)()(
21、)(CABACBA谢谢你的关注2019-10-13同一律同一律AEAAAAEEA零零 律律BABA)(BABA)(摩根律摩根律EAA AA否定律否定律吸收律吸收律ABAA)(ABAA)(谢谢你的关注2019-10-13CBA,为E的任何子集,则有BBABA.AABABA.B)()(DCBA)()(DBCA.C)()(DCBA)()(DBCA.D谢谢你的关注2019-10-13EBAAFABAGABAHAAI)(ABAJBAABA)(L)()()(CABACBAK)()()(CABACBA谢谢你的关注2019-10-13BA)(ABEAB)(BA)(BABABABA+3.3 包含排斥原理包含排斥
22、原理 定理:设A,B为有限集合,其元素个数分别为|A|,|B|,则谢谢你的关注2019-10-13设在20名学生中,有12人是足球队员,10人是篮球队员,兼是两队球员的人数为5名,请问既不是足球队员也不是篮球队员的学生有几人?解:设足球队员的集合为A,篮球队员的集合为B,则|A|=12,|B|=10,|AB|=5.又因为|AB|+|A B|=20,则|AB|=20-(|A|+|B|-|AB|)=20-(12+10-5)=3谢谢你的关注2019-10-13CBACBA+CBCABACBA+EABC谢谢你的关注2019-10-13nAAA.21njijiniiAAA11+nkjikjiAAA1nn
23、AAA.+.211)1(谢谢你的关注2019-10-133.4序偶与笛卡尔积v 序偶序偶v 笛卡尔乘积笛卡尔乘积v 三个定理三个定理3.4 序偶与笛卡尔积序偶与笛卡尔积 谢谢你的关注2019-10-13具有确定次序的两个元素的集合，记为.,yx,baaabbaabba,aaaaaa,例谢谢你的关注2019-10-13n 元组也可以定义为一个序偶nxxx,.,21nnxxxx,.,121nnyyyxxx,.,.,2121)(.)()(2211nnyxyxyx谢谢你的关注2019-10-13)()(,ByAxyxBA也是一集合,元素为序偶.BA 约定：BA,B或A若则谢谢你的关注2019-10-1
24、3BB AB BA AA 求解：2,1,2,1,bbaaBA,2,1,2,1bbaaAB,bbabbaaaAA2,2,1,2,2,1,1,1BB2,1,BbaA已知ABBA谢谢你的关注2019-10-13)(CBA)()(CBACBA,CBcbAacbaCBA)(,CcBAbacba,CcBbAacba不是三元组谢谢你的关注2019-10-13321321)(AAAAAA为了与 n 元组一致，我们约定：nAAA 21nnAAAA)(121,1121nnnAxAxxxx,1121nnnAxAxxxx 特别地nnAAAA 谢谢你的关注2019-10-13|BABA 则则S L包含了所有人群的分类包
25、含了所有人群的分类(8类）类）做一个市场调查，被调查的人群按照如下规则分类：性别性别S：男：男(m);女女(f)学历学历L：初中：初中(e);高中高中(h);大学大学(c);大学以上大学以上(g)即即 S=m,f,L=e,h,c,g谢谢你的关注2019-10-13 一个软件厂商为其所开发的软件提供了三个属性：开发语言：开发语言：L=c,f,j 内存：内存：M=8,16,32 操作系统：操作系统：O=u,d|CBACBA则 L M O包括了该软件的所有分类包括了该软件的所有分类（1818类）。类）。谢谢你的关注2019-10-13nnAAAA|1 2|nA A A|21nAAA YXYXP2|)
26、(|YX 2XXXXP2|)(|XX 2 谢谢你的关注2019-10-13定理1 设 A,B,C 为任意三个集合,则有)()()()CBCACBAd)()()()CABACBAa)()()()CABACBAb)()()()CBCACBAc谢谢你的关注2019-10-13 试证(A B)C=(A C)(B C)证明:若 (A B)C (x(A B)(y C)(xA x B)(y C)(xA yC)(x B y C)(AC)(BC)(AC)(BC)因此,(A B)C=(A C)(B C)谢谢你的关注2019-10-13定理2：若 C,则)(BCAC)(CBCABA定理3：若A,B,C,D 为四个非
27、空集合，则 的充分必要条件为DCBA.DBCA，谢谢你的关注2019-10-133.5 关系及其表示v 二元关系二元关系v X 到到Y 的关系的关系v 前域、值域前域、值域v 关系的表示关系的表示3.5 关系及其表示关系及其表示 谢谢你的关注2019-10-13任一序偶的集合,确定了一个二元关系R.若任一序偶在在 R中，则记为 R 或 xRy;否则记为 R 或yRxY)R(x谢谢你的关注2019-10-13X Y 的任何子集,都定义一种关系 R，称作 X 到 Y 的关系.若 X=Y,则 R 为集合 X 上的关系.空关系:全域关系:YX 恒等关系:IX 是 X 上的二元关系，且满足如果集合如果集
28、合X 有有n个元素个元素,则其恒等则其恒等关系也有关系也有n个元素个元素.,XxxxIX谢谢你的关注2019-10-13)(),(,2xyRyxyxuQ实数中的平方关系3,2,1uA3,3,2,2,1,1AI集合A上的恒等关系,3,2,1 srYuX 1,r,2,s,3,r R 3,2,1uAR是A中的小于关系3,2,3,1,2,1R从X到Y的关系谢谢你的关注2019-10-13已知有五个城市的航班服务，下表是从ci到cj的航线的票价，R是定义在城市的集合A=c1,c2,c3,c4,c5上的关系，ci R cj当且仅当从ci到cj的票价小于1500.解解：R=,C1C2C3C4C5C1 140
29、0100015002000C21900 200016002200C311001800 19002500C4190020001200 1500C52000100020001500 FromTo 谢谢你的关注2019-10-13：？n 个元素的集合上,可以定义多少个关系？因为一个集合 X 上的关系是 X X 的子集，而XXXXP2|)(|XX 222n)2(2n谢谢你的关注2019-10-13 若存在y,使S的所有x的集合,称为S的前域(定义域),记为D(S)或Dom(S).YyXxyxSDom()(),Syx谢谢你的关注2019-10-13YyXxxySRan()(),Syx若存在x,使S的所有
30、y的集合,称为S的值域，记为 R(S)或Ran(S).谢谢你的关注2019-10-13R,3,2,1srYuXXRDom3,2,1)(ARRan3,2)(3,2,1uAR是X中的小于关系3,2,3,1,2,1RARDom2,1)(YsrRRan,)(设设 R 是从是从 X 到到 Y 的关系，则的关系，则Dom(R)X Ran(R)Y 1,r,2,s,3,r 谢谢你的关注2019-10-13xSyxRyySRx)(xSyxRyySRx)(xSyxRyySRx)(xRyyRx)(xSyxRyySRx)(若R和S是从集合X到集合Y的两个关系，则R、S的并、交、补、差、对称差仍是X到Y的关系。谢谢你的
31、关注2019-10-13 已知：已知：A 是一所学校所有学生的集合，是一所学校所有学生的集合，B是该校所有课程的集合。是该校所有课程的集合。R1：包含所有的序偶包含所有的序偶,其中学生其中学生a 学习了课程学习了课程b;R2：包含所有的序偶包含所有的序偶,其中学生其中学生a需要学习课程需要学习课程b。求：求：R1R2,R1 R2,R1 R2？谢谢你的关注2019-10-13解：解：R1R2 包含所有的序偶包含所有的序偶,其其中学生中学生a学习了课程学习了课程b,或或a需要学习需要学习b.R1 R2 包含所有的序偶包含所有的序偶,其中学其中学生生a学习了课程学习了课程b，并且他需要学习，并且他需
32、要学习b.R1 R2 包含所有的序偶包含所有的序偶,其中学其中学生生a学习了课程学习了课程b，但是他并不需要学，但是他并不需要学习习b;或或a需要学习课程需要学习课程b，但是他没有，但是他没有学习学习.谢谢你的关注2019-10-13两个有穷集合且R是从X到Y的二元关系，若jijiijRyxRyxr10则称nmijRrM是R的关系矩阵.,21mxxxX,21nyyyY 谢谢你的关注2019-10-13)(),(,yxXyxyxR试求.RM,3,4,2,4,1,4R1,2,2,3,1,30111001100010000RM解:4,3,2,1X已知谢谢你的关注2019-10-13 设R是有限集合X
33、到集合Y上的一个二元关系.以X和Y中的元素为图中的结点,如果是R的元素,则以xi 为起点,以yj 为终点,作有向边所构成的图.谢谢你的关注2019-10-13例6)(),(,yxXyxyxR试求关系图.4,3,2,1X已知,3,4,2,4,1,4R1,2,2,3,1,3解：1234谢谢你的关注2019-10-13 已知求关系及关系矩阵R=,1010011100100001RM解：abdc谢谢你的关注2019-10-13 F关系（二元关系）关系（二元关系）从从X到到Y的关系、的关系、X上的关系上的关系F关系的域（前域）、值域关系的域（前域）、值域F关系的集合运算仍然是关系关系的集合运算仍然是关系
34、F关系的表示方式：集合表达式、关系的表示方式：集合表达式、关系矩阵、关系图关系矩阵、关系图谢谢你的关注2019-10-133.6 关系的性质v 自反性自反性v 反自反性反自反性v 对称性对称性v 反对称性反对称性v 传递性传递性3.6 关系的性质关系的性质 谢谢你的关注2019-10-13),(RxxXxx 在在 MR 中中,rii=1.即关系矩阵中主对角线上所有元素都是即关系矩阵中主对角线上所有元素都是1.在关系图中每个结点都有自回路在关系图中每个结点都有自回路.abc1.1.1M谢谢你的关注2019-10-13,2acbbbaaaR,1ccbbbaaaR,3ccabbacaR,4ccabb
35、aaaR,6cacbbaR,7accbbaR,8cabaR,5ccbbabbaaaR 谢谢你的关注2019-10-13),(RxxXxx 在在 MR 中中,rii=0.即关系矩阵中主对角线上所有元素都是即关系矩阵中主对角线上所有元素都是0.在关系图中任一结点均无自回路在关系图中任一结点均无自回路.abc0.0.0M谢谢你的关注2019-10-13,2acbbbaaaR,1ccbbbaaaR,3ccabbacaR,4ccabbaaaR,6cacbbaR,7accbbaR,8cabaR,5ccbbabbaaaR 谢谢你的关注2019-10-13一个关系不是自反的，就一一个关系不是自反的，就一定是反
36、自反的吗？定是反自反的吗？不一定。不一定。如：如：A=1,2,3,S=,则则 S 既不是自反的也不是反自反的。既不是自反的也不是反自反的。？谢谢你的关注2019-10-13),(RxyRyxXyxyx 在在 MR 中中,若若 rij=1,则必有则必有rji=1.即关系矩阵是对称的即关系矩阵是对称的.在关系图中结点间若有边在关系图中结点间若有边,必是往返两条必是往返两条.100001011Mabc谢谢你的关注2019-10-13,2acbbbaaaR,1ccbbbaaaR,3ccabbacaR,4ccabbaaaR,6cacbbaR,7accbbaR,8cabaR,5ccbbabbaaaR 谢谢
37、你的关注2019-10-13),(RxyyxRyxXyxyx),(yxRxyRyxXyxyx 在在 MR 中中,若若 i j,且且 rij=1,则则 rji=0.即关系矩阵中以主对角线对称的元素不能即关系矩阵中以主对角线对称的元素不能同时为同时为1(但可同时为但可同时为0).在关系图中若两点间有边在关系图中若两点间有边,只会是一条只会是一条,没有返回边没有返回边.谢谢你的关注2019-10-13,2acbbbaaaR,1ccbbbaaaR,3ccabbacaR,4ccabbaaaR,6cacbbaR,7accbbaR,8cabaR,5ccbbabbaaaR 谢谢你的关注2019-10-13 一
38、个关系不是对称的，就一定一个关系不是对称的，就一定是反对称的吗？是反对称的吗？不一定。不一定。如：如：A=1,2,3,S=,则则 S 既不是对称的也不是反对称的。既不是对称的也不是反对称的。N=,N即是对称的，也是反对称的。即是对称的，也是反对称的。？谢谢你的关注2019-10-13RyxXzyxzyx,(),RzxRzy 在在 MR 中中,若若 rij=1,rjk=1则则 rik=1.在关系图中在关系图中,若从结点若从结点 a 到结点到结点 b 有有长度大于长度大于 1 的路的路,则从则从 a 到到 b 必有长度必有长度为为 1 的路存在的路存在.谢谢你的关注2019-10-13,2acbb
39、baaaR,1ccbbbaaaR,3ccabbacaR,4ccabbaaaR,6cacbbaR,7accbbaR,8cabaR,5ccbbabbaaaR 谢谢你的关注2019-10-13,1ccbbbaaaR1000100111RMabc1RR1 是自反的、反对称、传递的。谢谢你的关注2019-10-13,2acbbbaaaR0010100112RM2RabcR2 是反对称的。谢谢你的关注2019-10-13,3ccabbacaR1000011103RMabc3R谢谢你的关注2019-10-13 1000010114RMabc4R,4ccabbaaaRR4 是对称的。谢谢你的关注2019-10
40、-13,5ccbbabbaaaRabc5R1000110115RMR5 是自反的、对称的、传递的。谢谢你的关注2019-10-13,6cacbbaRabc6R0001001106RMR6 是反自反的、反对称、传递的。谢谢你的关注2019-10-13,7accbbaRabc7R0011000107RMR7 是反自反、反对称的。谢谢你的关注2019-10-13,8cabaR0000001108RMR8 是反自反、反对称、传递的。abc8R谢谢你的关注2019-10-13 自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1 R2 R3 R4 R5 R6 R7 R8 等价关系序关
41、系谢谢你的关注2019-10-13 在关系矩阵中在关系矩阵中自反性自反性 主主对角线上的所有元素都是1.反自反性反自反性 主主对角线上的所有元素都是0.对称性对称性 关系矩阵是对称的.反对称性反对称性 以主对角线对称的元素不能同时为1.传递性传递性 对 M2 中1所在的位置,M中 相应的位置都是1.谢谢你的关注2019-10-13 在关系图中在关系图中自反性自反性 每点必有自回路.反自反性反自反性 任一结点均无自回路.对称性对称性 结点间若有边,必是往返两条.反对称性反对称性 若两点间有边,只会是一条,没有返回边.传递性传递性 若从结点 a 到结点 b 有长度大于 1 的路,则从 a 到 b
42、必有长度为 1 的路存在.谢谢你的关注2019-10-13？n 个元素的集合上，可以有个元素的集合上，可以有多少个自反的关系？多少个自反的关系？)2()1(nn因为一个集合因为一个集合 X 上的关系是上的关系是 X X 的的子集子集,X X 共有共有 n2 个元素个元素.R 如果是自反的如果是自反的,则对于任意则对于任意 x X,R,而另外而另外 n(n-1)个元素可能在个元素可能在或不在或不在 R 中，所以共有中，所以共有 2n(n-1)个关系个关系.谢谢你的关注2019-10-133.7 复合关系和逆关系复合关系和逆关系 3.7 复合关系和逆关系v复合关系复合关系v逆关系逆关系 例如例如:
43、F:父子关系父子关系 F1:,F2:F1 F2:祖孙关系祖孙关系 B:兄弟关系兄弟关系 B F :叔侄关系叔侄关系 例如例如:整数集合整数集合Z上的大于关系上的大于关系 逆关系为逆关系为 Z上的小于关系上的小于关系谢谢你的关注2019-10-13显然显然 R S 是从是从 X 到到 Z 的关系的关系。设 R 是从 X 到 Y 的关系,S 是从 Y 到 Z 的关系,则 R S 称为 R 和 S 的复合关系(合成关系),表示为ZzXxzxSR,),(SzyRyxYyy谢谢你的关注2019-10-13已知,4,3,2,1X,4,3,2Y,3,2,1Z6,+yxYyXxyxR1,zyZzYyzyS求:
44、R S 和 S R2,4,3,3,4,2R3,4,2,3,1,2S1,4,2,3,3,2SR解:SR RS 3,4,4,3谢谢你的关注2019-10-13,ZYXSRZXSR X1234Y234123Z1234X123Z谢谢你的关注2019-10-13WZYXRRRR 4321已知集合 X,Y,Z,W则有2313112)()RRRRRRRa 4342432)()RRRRRRRb 复合对复合对集合并集合并运算运算有分配律有分配律;复合对复合对集合交集合交运算运算没有分配律没有分配律.4342432)()RRRRRRRd 3121321)()RRRRRRRc谢谢你的关注2019-10-13 WZY
45、XRRR 321已知集合 X,Y,Z,W则有)()(321321RRRRRR结合律结合律谢谢你的关注2019-10-13 设 R 为集合 A 上的关系，R 的 n 次幂R(n)可以定义如下：|,)1()0(AxxxR1,)2()1()(nRRRnnoRRRRo)0()1(显然,R(0)是 A 上的恒等关系。RRRRRoo)1()2(ooon-1nRRRR)(谢谢你的关注2019-10-13)()()(nmnmRRR+o)()()()(mnnmRR设 R 为 A 上的关系，m,n 是自然数，则下面的等式成立：在关系图中，xRy 表示从结点 x 到 y 有一条长度为 1 的有向路径，xRny 则表
46、示从结点 x 到结点 y 有一条长度为 n 的有向路径。谢谢你的关注2019-10-13,cbaX,2accbbaR,1bccabaR,3cccbbaR,4ccabbaR求关系的幂运算。已知已知且有且有谢谢你的关注2019-10-13,)3(1R,)2(1baR.,)4(1R,1bccabaR谢谢你的关注2019-10-13,)2(2bcabcaR,)3(2ccbbaaR)0(2R,)4(2accbbaR2R,2accbbaR.,)3(2)6(2RR,)2(2)5(2RR即.,1,0,2)1(2)13(2+kRRRk.,1,0,)2(2)23(2+kRRk.,1,0,)3(2)33(2+kRR
47、k3,2,1,1,0,)(2)3(2+ikRRiik.谢谢你的关注2019-10-13,)2(3cccbcaR.)4(3)3(3RR,3cccbbaR谢谢你的关注2019-10-13 ,)2(4ccbbaaR)0(4R.,)1(44)3(4RRR1,0,1,0)(4)2(4+ikRRiik.,4ccabbaR.,)0(4)4(4RR对于有穷集对于有穷集 A 和和 A 上的关系上的关系 R，R 的不同次幂只有有限个的不同次幂只有有限个.谢谢你的关注2019-10-13b:2Rac解：,2accbbaR:)2(2Rabc:)3(2Rabc谢谢你的关注2019-10-13,21nyyyY.,21mx
48、xxX.,21pzzzZ.,ZYXSRnmijRaMpnijSbM,pmijcSRSRMMMoo o)(1kjiknkijbac其中逻辑加逻辑乘逻辑加逻辑加()0 0=00 1=11 0=11 1=1逻辑乘逻辑乘()0 0=00 1=01 0=01 1=1谢谢你的关注2019-10-13,2accbbaR0011000102RM001100010,)2(2bcabcaR22)2(2RRRMMM001100010001100010谢谢你的关注2019-10-13 100010001,2accbbaR,)3(2ccbbaaR,)2(2bcabcaR2)2(2)3(2RRR MMM001100010
49、010001100谢谢你的关注2019-10-13,RyxxyRCRRCC)(设 R 为 X 到 Y 的二元关系,如将 R 中每一序偶的元素顺序互换,所得到的集合称为 R 的逆关系.记作 Rc.谢谢你的关注2019-10-13 设 R,R1,R2都是从 X 到 Y 的二元关系，则CCCRRRR2121)()b)aCCCRRRR2121)(XYYXC)()c)dCCRR)(R XY R,其中)eCCCRRRR2121)(谢谢你的关注2019-10-13设 R,R1,R2都是从 X 到 Y 的二元关系，则)dCCRR)(R XY R,其中)eCCCRRRR2121)(R)c R R Rc Rc因为
50、R1-R2=R1 R2 故(R1-R2)c=(R1 R2)c=R1c (R2)c=R1c R2c=R1c-R2c谢谢你的关注2019-10-13 定理定理5 5,ZYXSR则定理定理6 6 R 为 X 上的二元关系,则b)R 为反对称的充分必要条件是.XCIRRa)R 为对称的充分必要条件是 R=RcCCCRSSR)(谢谢你的关注2019-10-13 已知：集合 A=1,2,3,令关系R=,S=,求：RS、Rc、解:2,3,1,3,3,2,1,2R.RAA=,RS=,Rc=,谢谢你的关注2019-10-133.8 关系的闭包运算关系的闭包运算 3.8 关系的闭包运算v自反自反(对称、传递对称、
