1、第三章 集合与关系,为什么要研究集合？,3-1 集合的概念和表示方法,定义(集合set)：把具有共同性质的一些对象汇集成一个整体，就构成一个集合，这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,表示集合用小写英文字母a,b,c,表示元素aA：表示a是A的元素，读作“a属于A”aA：表示a不是A的元素，读作“a不属于A”,3-1.1 有关集合的概念,n元集(n-set) : 有n个元素的集合称为n元集。|A|: 表示集合A中的元素个数, A是n元集 |A|=n0元集: 记作 1元集(或单元集),如a, b, 有限集 (finite set): |A|是有限数,
2、|A|0且x是偶数 =x|x=2(k+1)，k为非负整数 =2(k+1) | k为非负整数两个集合相等的外延性原理：两个集合A、B是相等的，当且仅当它们有相同的成员，记作A=B；否则记作AB 。集合的元素还可以是一个集合。例如：S=a,1,2,p,q,3-1.3 数的集合,N：自然数(natural numbers)集合N=0,1,2,3,Z：整数(integers)集合Z=0,1,2,=,-2,-1,0,1,2,Q：有理数(rational numbers)集合R：实数(real numbers)集合C：复数(complex numbers)集合,3-1.4 集合之间的关系,子集、相等、真子
3、集；空集、全集；幂集、n元集、有限集；,（1）子集,定义子集(subset)：设A、B是任意两个集合，如果A的每一个元素是B的成员，则称A为B的子集, 或说A包含于B, 或说B包含A, 记作AB，或BA。AB (x)(xAxB)若A不是B的子集, 则记作ABAB (x)(xAxB),证明AB x(xAxB)成立 证明：根据定义 AB (x)(xAxB)则 AB (x)(xAxB)(x)(xA)(xB)(x)(xA)(xB)(x)(xAxB)子集(举例)设A=a,b,c,B=a,b,c,d,C=a,b,则AB, CA, CB,定理3-1.1集合A和集合B相等的充分必要条件是这两个集合互为子集。A
4、=B ABBAA=B (x)(xA xB)证明A=B ABBA (=定义)(x)(xAxB)(x)(xBxA) (定义)(x)(xAxB)(xBxA) (量词分配)(x)(xA xB) ( 等价式),包含()的性质：,1AA（自反性）证明: AA(x)(xAxA) T2若AB,且AB,则 BA（反对称性）3若AB,且BC, 则AC（传递性）证明: AB (x)(xAxB)x, xA xB (AB) xC (BC) (x)(xAxC), 即AC.,（2）真子集,定义真子集(proper subset)如果集合A的每一个元素都属于B，但集合B至少有一个元素不属于A，则称A为B的真子集，记作AB。A
5、B AB ABAB(x)(xAxB)(x)(xBxA),AB的含义：,AB (AB AB) (定义) (AB) (A=B) (德摩根律) x(xAxB) (A=B) (定义) AB (A=B)含义：A不是B的子集或者A和B相等。,真包含()的性质,1AA （反自反性）证明: A A AA AA TF F. 2若AB,则 BA （反对称性）证明: (反证) 设BA, 则AB AB AB AB (化简)BA BA BA BA所以 AB BA A=B (=定义)但是 AB AB AB AB (化简) 矛盾!,3若AB,且BC, 则AC （传递性）证明: AB AB AB AB (化简),同理 BC
6、BC, 所以AC.假设A=C, 则BCBA, 又AB, 故A=B, 此与AB矛盾, 所以AC.所以, AC. #,（3）空集,定义空集(empty set)：没有任何元素的集合是空集,记作例如： xR|x2 +1=0定理 对任意集合A空集是它的子集也就是对任意集合A, A证明: Ax(xxA)x(FxA)T. 对于每一个非空集合A，至少有两个不同的子集，A和，称为A的平凡子集。, 推论 空集是唯一的.（可作为讨论）证明: 设1与 2都是空集, 则12 21 1=2 . #,（4） 全集,定义全集: 在一定范围内，如果所有集合均为某一集合的子集,则称这个集合是全集,记作E。E=x | P(x)
7、P(x)，P(x)为任何谓词全集是相对的, 视情况而定, 因此不唯一。例如, 讨论(a,b)区间里的实数性质时, 可以选 E=(a,b), E=a,b), E=(a,b, E=a,b, E=(a,+), E=(-,+)等,（5）幂集,定义幂集(power set)给定集合A，由集合A的所有子集为元素组成的集合,称为A的幂集,记作P (A)P (A)=x|xA注意: xP (A) xA例如: A=a,b, P (A)=,a,b,a,b.,定理如果有限集合A有n个元素，则幂集P (A)有2n个元素。证明: 见课本第85页，利用二项式展开定理。,3-2集合的运算,2.1.1 定义 集合的交(inte
8、rsection): 设任意两个集合A和B，由集合A和B的所有共同元素组成的集合S，称为A和B的交集，记作AB 。S=AB = x | (xA) (xB) xAB (xA) (xB),例2: 设An=xR|0x1/n,n=1,2,则A1 A2 An =,2.1.2 交集(举例),例1: 设An=xR|n-1xn,n=1,2,10,则A1 A2 An=,0,2.1.3 不相交(disjoint),不相交：AB=互不相交：设A1,A2,是可数多个集合, 若对于任意的ij, 都有AiAj=, 则说它们互不相交。例: 设 An=xR|n-1xn,n=1,2,10, 则 A1,A2,是不相交的,2.1.
9、4 集合交运算的性质,a) A A = A （幂等律）b) A = （零律）c) A E = A （同一律）d) A B = B A （交换律）e) (A B) C = A (B C) （结合律）因为集合交运算满足结合律，故n个集合的交记为： nP=A1 A2 An = Ai i=1,2.2 集合的并,2.2.1 定义并集(union)：设任意两个集合A和B，由所有集合A和B的元素组成的集合S，称为A和B的并集，记作AB 。 S=AB = x | (xA) (xB) xAB (xA) (xB),例2: 设An=xR|0x1/n,n=1,2,则A1 A2 An =,2.2.2 并集(举例),例1
10、: 设An=xR|n-1xn,n=1,2,10,则A1 A2 An=,0，10,0，1,2.2.3 集合并运算的性质,a) A A = A （幂等律）b) A = A （同一律）c) A E = E （零律）d) A B = B A （交换律）e) (A B) C = A (B C) （结合律）因为集合并运算满足结合律，故n个集合的并记为： nP=A1A2 An = Ai i=1,2.3 集合的补相对补,2.3.1 定义补集相对补集(relative complement , difference set)：属于A而不属于B的全体元素组成的集合S，称为B对于A的补集相对补集, 记作A-BS=A
11、-B = x | (xA) (xB) 2.3.2 定义绝对补(complement)：设E为全集，对任一集合A关于E的补E-A，称为集合A的绝对补，记作 A。A=x|(xExA),2.4 集合的对称差,2.4.1 定义对称差 (symmetric difference)：属于A而不属于B, 或属于B而不属于A的全体元素组成的集合S, 称为A与B的对称差, 记作AB。AB=x|(xAxB)(xAxB)AB=(A-B)(B-A)=(AB)-(AB),2.5 相对补、对称差 (举例),例: 设A=xR|0x2, B=xR|1x3,则A-B= xR|0x1=0,1)B-A= xR|2x3=2,3)AB
12、=xR|(0x1)(2x.定义 n(2)元组： =,an.定理: = ai = bi, i =1,2,n.,3-4.3笛卡尔积(Cartesian product)及其性质,定义笛卡尔积：A和B为任意两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样序偶的集合，称为A和B的笛卡尔积或直积，记为： AB=|(xA)(yB).,例1: A=,a, B=1,2,3.AB= ,.BA= ,.AA= , , , .BB= , , .,3-4.4 笛卡尔积的性质：,当|A|=m，|B|=n时，|AB|是多少？|AB|= mn,3-4.4 笛卡尔积的性质：,1.非交换: AB BA (除
13、非 A=B A= B=)反例: A=1, B=2.AB=, BA=.2.非结合: (AB)C A(BC) (除非 A= B= C=)反例: A=B=C=1. (AB)C=,1, A(BC)=.,3. 笛卡尔积分配律：（对或运算满足）（1） A(BC) = (AB)(AC)（2） A(BC) = (AB)(AC)（3） (BC)A = (BA)(CA)（4） (BC)A = (BA)(CA),3. 笛卡尔积分配律(证明(1) A(BC) = (AB)(AC).证明: , A(BC) x A y (BC) x A (y B y C) (xAyB)(xAyC) (AB)(AC) (AB)(AC) A
14、(BC) = (AB)(AC). #,4. 其他性质：设A,B,C,D是任意集合,(1) 若A, 则ABAC BA CA BC（即书上的定理3-4.2）(2) AC BD ABCD.（即书上的定理3-4.3）(3) AB= A= B=,证明(1) 若A, 则ABAC BC.证明: () 若 B=, 则 BC. 设 B, 由A, 设xA, y, yB， AB AC xAyC yC. BC ()若B=,则AB=AC. 设 B. , AB xAyB xAyC AC ABAC. #,3-4.5 推广：n维笛卡尔积,定义 n维笛卡尔积：A1A2An = | x1A1x2A2xn An AAA = An|
15、Ai|=ni , i =1,2,n |A1A2An| = n1n2nn.n维笛卡尔积性质与2维笛卡尔积类似.,作业：,P104 (1) b) (2) (5),3-5关系及其表示,3-5.1关系的概念及记号兄弟关系、长幼关系、同学关系、邻居关系，上下级关系等。在数学上有大于关系、小于关系，整除关系。例如：“3小于5”，“x大于y”， “点a在b与c之间”。我们又知道序偶可以表达两个客体、三个客体或n个客体之间的联系，因此用序偶表达这个概念是非常自然的。,例如：火车票与座位之间有对号关系。设X表示火车票的集合，Y表示座位的集合，则对于任意的 xX 和 y Y，必定有 x 与y有“对号”关系 x 与
16、y没有“对号”关系。二者之一令R表示“对号”关系，则上述问题可以表示为 xRy 或 xRy 。,亦可表示为 R 或 R，因此我们看到对号关系是序偶的集合。,定义关系：二元关系(binary relation) ，简称关系，任一序偶的集合即确定了一个二元关系R，R中任一序偶 可记为 R或xRy。不在R中的任一序偶 可记为 R或xRy,例1: 在实数中关系“”可记作 “ ”=|x,y是实数且x y。例2: R1=, R1是二元关系. 例3: A=,a,1 A不是关系.,二元关系的记号：,设R是二元关系, 则R x与y具有R关系 xRy。对比: xRy (中缀(infix)记号) R (后缀(suf
17、fix)记号) R(x,y) (前缀(prefix)记号)例如: 2 R 1 R 2 , R 5 R 4。,A到B的二元关系,也可定义关系为：设有任意两个集合A和B，直积AB的子集R称为A到B的二元关系。R是A到B的二元关系 RAB RP (AB)（幂集）若|A|=m, |B|=n, 则|AB|= mn , 故|P (AB)|=2mn，即A到B不同的二元关系共有2mn个,A到B的二元关系(举例),例: 设 A=a1,a2, B=b, 则A到B的二元关系共有221=4个: R1=, R2=, R3=, R4=,B到A的二元关系也有4个: R5=, R6=, R7=, R8=,。,A上的二元关系,
18、定义 A上的二元关系: 是AA的任意子集。 R是A上的二元关系 RAA RP (AA)。若|A|=m, 则|AA|=m2, 故|P (AA)|= 2 m2 ，即A上不同的二元关系共有2 m2个。,A上的二元关系(举例),例1: 设 A=a1,a2, 则A上的二元关系共有16个: R1 = , R2 = , R3 = , R4 = , R5 = , R6 = , , R7 = , , R8 = , ,R9 = , ,R10 = , ,R11 = , , R12 = , ，R13 = , ，R14 = , , ，R15 = , ，R16 = , 。,例2: 设 B=b, 则B上的二元关系共有2个:
19、 R1=, R2=. 例3: 设 C=a,b,c, 则C上的二元关系共有29=512个!,3-5.2与二元关系有关的概念,对任意集合R, 可以定义:前域定义域（domain）： dom R = x | y (xRy) 值域（range）: ran R = y | x(xRy) 域（field）: FLD R = dom R ran R前域定义域,值域,域图示见书106页例题1。,定义域,值域,域(举例),例: R1=a,b, R2=, R3=,.当a,b不是序偶时, R1不是关系.dom R1=, ran R1=, FLD R1=dom R2=c,e, ran R2=d,f, FLDR2=c,
20、d,e,fdom R3=1,3,5, ran R3=2,4,6,FLD R3=1,2,3,4,5,6.,3-5.3一些特殊关系,设A是任意集合, 则可以定义A上的：空关系(empty relation): 恒等关系(identity relation): IA = | a A 全域关系(universal relation): UA = AA = | xA yA,此外，设AI, 则可以定义A上的：整除关系: DA = | xA yA x|y 例: A=1,2,3,4,5,6, 则 DA=,。,设AR, 则可以定义A上的：小于等于(less than or equal to)关系：LEA = |
21、 xA yA xy 小于(less than)关系：LA = | xA yA xy 大于等于(greater than or equal to)关系，大于(great than)关系,设A为任意集合, 则可以定义P (A)上的:包含关系:： A = | xA yA xy 真包含关系： A = | xA yA xy 见P107 例2和例3,3-5.4 关系的运算,定理：若Z和S是从集合X到集合Y的两个关系，则Z和S的并、交、补、差仍是X到Y的关系。证明见书108页。,3-5.5二元关系的表示,(1) 序偶集合的形式表达 (2) 关系矩阵：设 A=a1,a2,an, B=b1,b2, ,bm,RA
22、B, 则R的关系矩阵 MR=(rij)nm, 其中rij = 1, ai R bj 或 R 0, ai R bj 或 R,例题：P103 例题5例如: A=a,b,c, R1=,R2=, 则 1 1 0 0 1 1 MR1 = 1 0 1 MR2= 0 0 1 0 0 0 0 0 0,(3) 关系图：,A=a1,a2,an，B=b1,b2,bn ，RAB, 首先在平面上做结点a1,a2,an ，b1,b2,bn以“”表示(称为顶点)， 若aiRbj ，则从结点ai向结点bj画有向边，箭头指向bj，若aiRbj , 则ai与bj之间没有线段连接，这样得到的图称为R的关系图 GR 。P109 例题7,定义在集合A上的关系图有所不同例如（上例）, A=a,b,c, R1=,R2=, 则关系图如下：,关系矩阵、关系图(讨论)：,当A中元素标定次序后, RAA的关系图GR与R的序偶集合表达式可以唯一互相确定。R的序偶集合表达式，关系矩阵，关系图三者均可以唯一互相确定。,作业(3-5),P109 (1) (5) c) 给出关系图和关系矩阵 (8) 选做,
