第3章集合与关系(杨圣洪版教材).

离散数学授课教师：刘慧明Email：[e-mail]青岛科技大学青岛市郑州路53号(四方校区)邮编:266042第三章集合与关系《离散数学》第三章集合与关系引言集合论是研究集合的数学理论，包含了集合、元素和成员关系等最基本的数学概念。集合论是现代数学的基础，它的基本概念已渗透到数学的所有领域。集合论、命题逻辑与一阶逻辑共同构成了数学的公理化基础。本章主要学习集合的概念、运算、性质、计数、序偶和关系等。《离散数学》第三章集合与关系本章内容1、集合的基本概念6、关系及其表示2、集合的运算与性质7、关系的复合3、有穷集的计数8、关系的分类4、序偶9、关系的闭包5、直积或笛卡尔积10、等价关系与集合的划分11、偏序关系《离散数学》集合：由一堆物件构成的整体。（集合没有精确的定义）描述集合常用的方法：1、枚举法:列出集合中的所有对象。如：青科大教学楼={一教,二教,三教,弘毅楼,明德楼}2、描述法:描述集合各对象的性质。如：偶数集={除以2，余为0的所有整数}元素：构成集合的对象称为元素。元素是无序的，重复的元素视为同一元素；元素与集合之间的关系有“属于∈”或“不属于∉”二种关系。3.1集合的基本概念《离散数学》子集AB：A中的每个元素都是B的元素。（A包含于B，或B包含A）幂集P(A)：P(A)={A的所有子集构成的集合}。如：A={1,2,3}A000={},——空集（常记为φ）A001={3},A010={2},A100={1},A011={2,3},A101={1,3},A110={1,2},A111={1,2,3}P(A)={A000,A001,A010,A011,A100,A101,A110,A111}={φ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}P(A)其有23个元素,即2|A|个。幂集又记为2A。3.1集合的基本概念《离散数学》1、交集：AB={由同时属于A与B的元素组成}2、并集：AB={由属于A或属于B的元素组成}3、差集：A-B={由属于A但不属于B的元素组成}4、余集(补集)：A={全集U中不属于A的元素组成}=U-A5、对称差：AB=(AB)-(AB){由属于A与B的并集但不属于A与B的交集元素组成}AAA-BABABABABABABAB3.2集合的运算与性质《离散数学》【定义3.2.3】（集合相等）设A、B是两个集合，若AB、BA，则称两个集合A与B相等，记为A=B。集合的运算性质：（与命题逻辑类同：∨,∧,）幂等律：AA=A，AA=A结合律：ABC=A(BC)=(AB)CABC=A(BC)=(AB)C交换律：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=排中律：AA=E；矛盾律：AA=吸收律：A(BA)=A，A(BA)=A(大吃小)德摩律：(AB)=AB，(AB)=AB双重否定律：A=A3.2集合的运算与性质《离散数学》|A|=集合A的元素个数。A1A23.3有穷集的计数定理3.3.1：（包含排斥原理）|A1A2|=|A1|+|A2|-|A1A2|因为公共部分算了两次！例：A1={蓝球队}，|A1|=10，A2={足球队}，|A2|=13，双重身份球员3人，请问这二个球队总共多少人？解：|A1A2|=|A1|+|A2|-|A1A2|=10+13-3=20人《离散数学》n个集合的包含排斥原理:|A1A2…An|=|Ai|-|AiAj|+|AiAjAk|-|AiAjAkAL|…+(-1)n-1|A1A2…An|记忆方法：“+”奇数个集合相交“-”偶数个集合相交3.3有穷集的计数例题：设校足球队队员有38人，蓝球队队员有15人，排球队队员有20人，三队总人数为58人，同时参加3个队的球员有3人，请问同时参加二队的有多少人？解：|A1A2A3|=|Ai|-|AiAj|+|AiAjAk|58=(38+15+20)-|AiAj|+3|AiAj|=18，即同时参加二队的有18人。《离散数学》例题：求在[1,300]的整数中，能被3或5或7整除的整数的个数。解：设A3表示能被3整除的数，|A3|=[300/3]=100；A5表示能被5整除的数，|A5|=[300/5]=60；A7表示能被7整除的数，|A7|=[300/7]=42；则能被3与5同时整除的个数：|A3A5|=[300/15]=20能被3与7同时整除的个数：|A3A7|=[300/21]=14能被5与7同时整除的个数：|A5A7|=[300/35]=8能被3、5、7同时整除的个数：|A3A5A7|=2能被3或被5或被7整除的个数：|A3A5A7|=|A3|+|A5|+|A7|-|A3A5|-|A3A7|-|A5A7|+|A3A5A7|=100+60+42-20-14-8+2=1623.3有穷集的计数《离散数学》小结：一、基本概念集合、子集、幂集二、集合的运算及性质1、交、并、差、余（补）、对称差2、有穷集合的计数（包含互斥原理）要求：熟练掌握集合的运算及其相关性质。3.1-3.3小结《离散数学》【定义3.4.1】（序偶）将有固定次序的两个对象写在一块，称为序偶，即有秩序的两个对象，记为对象1，对象2或x,y。3.4序偶【定义3.4.2】令x,y与u,v是二个序偶，如果x=u、y=v，那么称这两个序偶相等。记为x,y=u,v。在日常生活中，有许多事物是成对出现的，并且这对事物之间具有一定的次序，如：天地,夫妻,乾坤等，反过来就不习惯。如：天,地,夫,妻,乾,坤,…；平面坐标1,2等注意：序偶x,y与y,x是不同的，次序不能乱，就如同1,2与2,1表示的是不同坐标点一样。《离散数学》序偶的概念可推广到三元组、四元组、多元组：【定义3.4.3】如果x,y是序偶，且x,y,z也是一个序偶，则称x,y,z为三元组。如：夫，妻，子，主，谓，宾，家，春，秋，宿舍，食堂，教室，三维空间中点的坐标x,y,z等。【定义3.4.4】如果x1,x2,…,xn-1是n-1元组，而x1,x2,…,xn-1,xn是序偶，则称为x1,x2,…,xn-1,xn为n元组。3.4序偶《离散数学》【定义3.5.1】（直积）令A、B是两个集合，称集合{x,y|xA,yB}为A与B的直积或笛卡尔积，记为AB。（直积的结果是一个集合！）3.5直积或笛卡尔积如：A={1,2,3},B={a,b,c}AB={1,2,3}{a,b,c}={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}BA={a,b,c}{1,2,3}={a,1,b,1,c,1,a,2,b,2,c,2,a,3,b,3,c,3}由于1,aa,1，所以ABBA。直积不满足交换律若A,B是有穷集合，则有|A×B|=|A|·|B|(·为数乘运算)《离散数学》易证直积具有以下性质：1、A(BC)=ABAC2、A(BC)=ABAC3、(BC)A=BACA4、(BC)A=BACA5、ABACBCCACB6、AB,CDACBD3.5直积或笛卡尔积【定义3.5.2】令A1,A2,…,An是n个集合，称n元组的集合{x1,x2,…,xn|x1A1,x2A2,…,xnAn}为A1,A2,…,An的直积或笛卡尔积，记为A1A2…An。我们仅证明(1)。对任意的x,y∈A×(B∪C)x∈A∧y∈(B∪C)x∈A∧(y∈B∨y∈C)(x∈A∧y∈B)∨(x∈A∧y∈C)x,y∈A×B∨x,y∈A×Cx,y∈(A×B)∪(A×C)《离散数学》关系是客观世界存在的普遍现象，它描述了事物之间存在的某种联系。例如：人类集合中的父子、兄弟、同学、同乡等关系；实数之间的大于、小于、等于关系；两条直线间的平行、垂直等关系；集合间的包含、元素与集合的属于等等都是关系。两个个体之间的关系称为二元关系；三个以上个体之间的关系称为多元关系。我们主要讨论二元关系。3.6关系及其表示《离散数学》关系并不限于同一类事物之间，也存在于不同事物之间。如：旅客住店的关系：假设有张、王、李、赵四人，分别住在1，2，3号三个房间，其中：张住1号，李住1号，王住2号，赵住3号。若分别以a、b、c、d表示四人，R表示住宿关系，则住宿关系R可表示为：R={a,1,c,1,b,2,d,3}。可以看出这里的住宿关系R是序偶的集合。3.6关系及其表示《离散数学》【定义】一个序偶的集合就称为一个二元关系，常用符号R表示。二元关系也简称关系。若个体a与b之间存在关系R，则记作aRb，或x,y∈R。若规定关系R中序偶x,y的x∈A,y∈B，（如上面的住店关系），这样的序偶构成的关系R，称之为从A到B的一个二元关系。由A×B的定义知，从A到B的任何二元关系，均是A×B的子集。3.6关系及其表示实际上，一个序偶的集合就确定了一个二元关系。《离散数学》如：AB={1,2,3}{a,b,c}={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}R1={前后两个元素的序号一样}={1,a,2,b,3,c}关系除了可用序偶集合的形式表示外，还可用关系矩阵、关系图表示。100301020011cba123abc3.6关系及其表示《离散数学》关系矩阵：设RA×B，A=｛a1,a2,…,am｝，B={b1,b2,…,bn｝，那么R的关系矩阵MR为一m×n矩阵，它的第i,j分量rij只取值0或1，其中：3.6关系及其表示1,0,ijijijabRrabR当当如：AB={1,2,3}{a,b,c}R={1,a,1,b,3,c}110000001RM《离散数学》关系图：令RAB，将A、B的元素均画成一个点，如果序偶x,yR，则从点x画一条有向边到点y。3.6关系及其表示如：A={1,2,3,4,5,6,7,8}，R={2,1,3,1,3,2,4,1,4,2,4,3,5,4,6,4,6,5,7,4,7,5,7,6,8,5,8,6,8,7}注：序偶前后元素的集合相同时，关系图还可简化！《离散数学》3.6关系及其表示如：A={1,2,3,4,5}，R={1,2,1,3,1,4,1,5,2,2,2,3,2,4,2,5,3,4,3,5,4,5}，则其关系图如下：关系图：令RAB，将A、B的元素均画成一个点，如果序偶x,yR，则从点x画一条有向边到点y。《离散数学》3.6关系及其表示关系R的集合表达式、关系图、关系矩阵三者可以唯一相互确定，并且它们各有各的特点，可以根据不同的需要选用不同的表达方式。《离散数学》3.4-3.6小结小结:一、基本概念序偶、笛卡尔积、关系二、关系R的三种表达方式集合表达式、关系图、关系矩阵要求：掌握关系及其表达方法。《离散数学》日常生活中经常遇到关系的传递（复合）：如：设R1表示父与子的关系(毛泽东)R1(毛岸青)，(毛岸青)R1(毛新宇)前一个关系R1与后一个关系R1复合（传递），可得到“毛泽东”与“毛新宇”的关系为双重父子关系——爷孙关系。再如：设R2表示兄和弟的关系(毛岸英)R