《第3章集合与关系》由会员分享，可在线阅读，更多相关《第3章集合与关系（11页珍藏版）》请在金锄头文库上搜索。
1、第3章集合与关系集合论是现代数学的基础，它几乎与现代数学的每个分支均有联系，并且已渗透到各个 科学领域。集合论的内容十分丰富，并有相应的专著论述，这里只概括介绍集合论中最基本 的内容，包括:集合的基本概念；子集、全集、军集、补集等；集合的基本运算和集合代数 的一些基本公式；基本计数原理等。利用笛卡尔积及集合的一些基本关系讨论二元关系的定义及表示、关系的运算（并、交、 差、补、复合、逆关系、闭包等、关系的基本类型，及由此导出的等价关系，集合的划分 等，并讨论两种特殊的关系，相容关系和偏序关系。一、集合的基本概念集合是数学中没有给出精确定义的基本的数学概念，我们通常把所考查的对象的全体称为集合。其
2、中的每个对象称为元素（或成员），通常用大写英文字母表示集合，如:A, B, X 等，用小写英文字母表示兀素，如a, b， x等。经常用到的几个集合有:N自然数集或正整数集（有些教材用n表示非负整数集，用P表示正整数集）Z整数集（有些教材用I表示整数集，但一般用I表示区间0, 1）Q有理数集R实数集C复数集给出一个集合的方法之一是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来，例如:Nm=0，1，2,，m-1； Pm=1，2,，m（有些教材表示为:Zm=1, 2,，m）不含任何元素的集合称为空集，用9或）表示。在所讨论的问题中，涉及到的全体对 象的集合称为全集，通常用U（或E）表
3、示。空集是惟一的，但全集只能是相对惟一的，而非绝 对惟一的。集合的元素与集会之间是属于或者不属于的关系，两者必有且只有一个成立。用AUA 表示元素a属于集合A。集合通常有两种表示方法：列举法和描述法。列举法是列出集合的所有元素，女口： A=1, 23；描述法是用谓词概括该集合中元素的属性，如：B=n2|nUN, C=xlxUR,且-lvxv1 等。集合具有几个性质:（1）确定性。对一个具体的集合来说，其元素是确定的，一个元素或者在此集合中，或 者不在此集合中，两者必居其一，这与模糊集合不同。不清晰的对象构成的集合不在本书讨 论范围之内。（2）无重复性。集合中元素彼此不同，没有重复的元素，这与后
4、面图论中涉及的多重集 合不同，那里因为特殊的原因允许有重复的元素。例如:1， 2， 1=1， 2。（3）集合中元素无顺序。例如:1， 2， 3=2， 3， 1。（4）集合中元素是抽象的，甚至可以是集合。例如:A=1, a, 1。二、子集，集合的相等定义1设有A, B两集合，若B中的每个元素都是A中的元素，称B是A的子集，也称B被 A包含，或A包含B,记为BcA。若B是A的子集，且A中至少有一个元素不属于B,则称B为 A的真子集，记为BuA。显然有：申匸A, AcA据定义有：BcAoVxUB，有 xUA定义2若两集合A与B包含的元素相同，称A与B相等，也解释为：若A是B的子集且B是 A的子集，称
5、A与B相等，即A=BoAB且BA定义3设A是一集合，A的所有子集构成的集合称为A的幕集，记为P(A)(或p(A)、2A)。 即 P(A)=BIBcA。用IAI记为A中元素的数目，也称为集合的基数(对有限集)。显然有：刚=0。对于幕集， 若A是有限集，则有：IP(A)I=2|A|。三、集合的运算及其性质定义4任意两集合A与B的并是一个集合，它由所有至少属于A或B之一的元素所构成， 记为AUB。任意两集合A与B的交是一个集合，它由所有属于A且属于B的元素所构成，记为AAB。 任意两集合A与B的差是一个集合，它由所有属于A但不属于B的元素所构成，记为 A-B(或人出)，也称为B相对A的补集。任意两集
6、合A与B的对称差是一个集合，它由所有属于A不属于B和属于B不属于A的元 素所构成。记为AB。集合A的补集是一个集合，它由所有不属于A的元素所构成，记为A(或Ac、A等)，也 称为A的绝对补集。由以上定义，有：AUB=xIxA 或 xUBAClB=xlxU A 且xUBA-B=xlxe A且x不属于BA B=(A-B) U (B-A)A=xIxe U且x不属于A上面集合的并和交可以推广到n个集合的并和交，并和交的运算还可推广到无穷集合的 情形。集合之间相互关系和运算可以用文氏图(JohnVenn)形象描述，它有助于我们理解相关 问题，有时对解题也很有帮助。定理2对于全集U的任意子集A，B，C,有
7、(下面的算律在不同老板中，可能名称、性 质都有所不同)：基本特性等幕律AHA=A, AUA=A同一律AHE=A, AU0=A零率AH0=0, AUE=E交换律AnB=BnAAUB=BUA结合律(AnB)nc=An(Bnc)(AUB)UC=AU(BUC)分配律An(BUC)=(AnB)U(AnC)AU(BnC)=(AUB)n(AUC)吸收律AU(AnB)=AAn(AUB)=A对合律(A)=AE=0,0=E排中律AUA=E矛盾律AnA=0德.摩根律(AUB)=AnB(AnB)=AUBA-B=AnBA-B=A-(AnB)An（B-c）=（AnB）-（Anc）若AcB，贝1BuA(B-A)UA=BAB
8、=BAA A=0(AB)C=A(BC)A B=(AUB)-(AnB)A n(B C)=(A n B)(A n B)但AU（BC）=（AUB）3（AUC）不一定成立，如：A=1, 2, 3, B=1, C=2，则右边 为空集，但左边为非空集。四、基本计数原理1.鸽巢原理（抽屉原理）定理把n+1个物体放入n个盒子里，则至少有一个盒子里有两个或两个以上的物体。2.容斥原理最简单情形：定理：设A, B均为有限集，则有：IAUBI=IAI+IBI-|AQB|有三个集合时,容斥原理的表现形式：定理：A, B, C均为有限集，则有：IAUBU CI=IAI+IBI+ICI-IA n BI-IB n CI-I
9、C n AI+IA HBHCI五、笛卡尔积称va, b为由元素a和b组成的有序对(或序偶)，其中a为第一元素，b为第二元素，a, b 可以相同。定义5设A, B为两集合，由A中元素为第一元素，B中元素为第二元素，构成有序对， 所有这样的有序对组成的集合称为A与B的笛卡尔积(也称为直积)，记作AXB即AXB=va, bla = A, b = B。同样可以给出n维笛卡尔积的定义。据上面定义可知：若A或B中有一个空集，则AXB=p。且一般来说：AXBBXA.关于笛卡尔积，有下面几条性质：定理4对任意集合A, B, C,有：(1) A X (B U C)=(A X B) U (A X C)(2) A
10、X(BH C)=(A XB)H(AXC)(3) (AU B)X C=(AX C)U (BX C)(4) (A HB)X C=(A XC)H(BXC)(5) 若CM0，则 ABo(A X CcB X C)o(C X AcC X B)(6) 设人，B, C, D为四个非空集合，则(7) A X BcC X D的充要条件为AcC且BD六、关系的定义及表示定义6 若RcAXB, R称为集合A到B的关系。若va, bUR，也记为aRb。我们特别称A 到A的关系为A上的关系，即若Rc A X A，则称R为A上的关系。R为A到B的关系，R的定义域Dm(R)和值域Ran(R)定义为：Dom(R)=xlxUA,
11、 3yB, URRarl(R)=ylyUB, 3xA, vx, yUR一般说来，若lAl=m, lBl=n,则A到B共有2mn个二元关系，A上共有2m2个二元关系。几种常见的A上的关系有：空关系申，恒等关系IA(明确A时，简记为I),全域关系Ea等(不 同的教材记法可能有所不同)。分别为：申=； IA=lxUA； EA=lx, yUAAA因为关系是一种集合,所以通常用来表示集合的方法自然可用来表示关系。此外,还可 以用关系图或矩阵来表示,并且这两种表示更能体现关系的特点。 (有些教材提到用表格表 示关系的方法,其实质和用矩阵表示是一样的。 )1. 用关系图表示关系图是表示关系的一种直观形象的方
12、法。限定A, B均为有限集，设A=xx，x2,， xm, B=y1, y2, , ynR是A到B的二元关系。R所对应的关系图的具体做法是：首先作出m个结点x2,， xm，再作出n个结点，y2，yn.，若XjRyj，贝I自结点xi至结点y.作一有向弧，其箭头指向 巧，若xiRyj不成立，则没有线联结.对集合A上的关系作关系图，则通常将A上的元素画成一行或适当表示在一个平面上, 不必和一般的A到B的关系一样画成A到A的情形。若审打，则自结点xi至结点y.作一有向弧， 其箭头指向y.,若x.Rx.,贝I从x.到x用一带箭头的小圆圈表示。j i i i i2. 用关系矩阵来表示 关系矩阵是表示关系的另
13、一种有效的方法，其优点是可以利用矩阵作为研究关系的手 段，而且这样做便于计算机进行处理。设A=X, x2，,xm, B=y1，y2，yn, R是A到B的二元关系，则R的关系矩阵 是一个m行n列矩阵M(R)=(r.),其中元素r.定义为：若x.Ry.,贝贝.=1,否贝贝.=0,这里i的取值 . . . . . .为1, 2, m, .的取值1, 2, n.矩阵MR)的元素取值为0或1。这样的矩阵称为布尔矩阵。显然，当有限集A和B的元素己按一定的次序排列，则从A到B的关系R与其对应的 关系矩阵MR)是对应的。七、关系的运算关系作为一种集合，具有集合所具有的运算如：并、交、差、补等。当然两个关系运算
14、 之后的结果仍为一个关系，即仍为某一笛卡尔积的子集，这就要求两个进行运算的关系应满 足一定的前提条件，即：一般我们要求两个关系应是同一笛卡尔积的子集。除这些基本运算外，作为一种特殊的集合，关系还具有下面的一些运算：1. 复合运算定义7设RXXY, ScYXZ,贝lR与S的复合(或合成)是一个从X到Z的关系，记为RS, 且|3y(xRyAySz)定理1 复合运算具有下面一些性质：(1) 若R:AXB，则RIb=R, IAoR=R(2) A, B, C, D是集合，R:AXB, S:BXC, P：CXD，则有(RoS)oP=Ro(SoP)(3)设A为集合，RcAXA，定义Rn如下：R0=IAR1=RRn+1=RnoR则有 RmoRn=Rm+n, (Rm)n=Rmn，这里 m, nN2. 逆运算定义8设有集合A和B, RcAXB，则关系lvx, yUR是从B到A的关系，称为 R的逆关系，记为(Rc或R-1)。注意：集合的补集和关系的逆关系是两个不同的概念。关于复合运算的逆运算具有下面性质：定理2设R, R2都是从A到B的关系，则下列各式成立(RUR2)C=RCUR2C(2) (叫仆严咛花2。(3) (AXB)c=BXA(4) (R1-R2)c=R1c-R2c定理3 设TXXY, ScYXZ.证明:(TS)c=ScTc.既然可以用矩阵来表示关系，我
