《集合与关系》PPT课件.ppt

《《集合与关系》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《集合与关系》PPT课件.ppt（88页珍藏版）》请在三一办公上搜索。

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|是有限数,|A|,也叫有穷集，否

2、则为无限集。,3-1.2 集合的表示方法,通常使用“列举法”和“叙述法”两种方法来给出一个集合（1）列举法(roster)列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来，例如A=a,b,c,d,x,y,zB=0,1,2,3,4,5,6,7,8,9集合中的元素不规定顺序C=2,1=1,2集合中的元素各不相同C=2,1,1,2=2,1,3-1.2 集合的表示方法,（2）叙述法(defining predicate)用谓词P(x)表示“x具有性质P”，用A=x|P(x)表示元素具有性质 P 的集合A，如果P(b)为真，那么bA，否则bA。例如P1(x):x是英文字母A=x|P1(x)=

3、x|x是英文字母=a,b,c,d,x,y,zP2(x):x是十进制数字B=x|P2(x)=x|x是十进制数字=0,1,2,3,4,5,6,7,8,9,两种表示法可以互相转化,例如：E=2,4,6,8,=x|x0且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

4、,1,2,Q：有理数(rational numbers)集合R：实数(real numbers)集合C：复数(complex numbers)集合,3-1.4 集合之间的关系,子集、相等、真子集；空集、全集；幂集、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

5、)(x)(xAxB)子集(举例)设A=a,b,c,B=a,b,c,d,C=a,b,则AB,CA,CB,定理3-1.1集合A和集合B相等的充分必要条件是这两个集合互为子集。A=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）真子集

6、,定义真子集(proper subset)如果集合A的每一个元素都属于B，但集合B至少有一个元素不属于A，则称A为B的真子集，记作AB。AB 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(化简)矛盾

7、!,3若AB,且BC,则AC（传递性）证明:AB AB AB AB(化简),同理 BC 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）全集,定义全集:在一定范围内，如果所有集合均为某一集合的子集,则

8、称这个集合是全集,记作E。E=x|P(x)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 定义 集合的交(in

9、tersection):设任意两个集合A和B，由集合A和B的所有共同元素组成的集合S，称为A和B的交集，记作AB。S=AB=x|(xA)(xB)xAB(xA)(xB),例2:设An=xR|0 x1/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.4 集合交运算的性质,a)A

10、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|0 x1/n,n=1,2,则A1 A2 An=,2.2.2 并集(举例),例1:设An=xR|n-1xn,n=1,2,10,则A1 A2 An=,0，10,0，1,2.2.3 集

11、合并运算的性质,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-B=x|(xA)(xB)2.3.2 定义绝对补(complement)：设E为全集，对任一集合A关于E的补E-A，称为集合A的绝对补，记作 A。A=x|(x

12、ExA),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|0 x2,B=xR|1x3,则A-B=xR|0 x1=0,1)B-A=xR|2x3=2,3)AB=xR|(0 x1)(2x3)=0,1)2,3),2.6 集合运算的性质（集合恒等式）,(1)幂等律(idempotent laws)AA=A AA=A(2)结合律(associati

13、ve laws)(AB)C=A(BC)(AB)C=A(BC)(3)交换律(commutative laws)AB=BAAB=BA,(4)分配律(distributive laws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)(5)对合律(double complement law)A=A(6)零律(dominance laws)AE=E A=,(7)同一律(identity laws)A=AAE=A(8)排中律(excluded middle)AA=E(9)矛盾律(contradiction)AA=(10)全补律=EE=,(11)吸收律(absorption laws)A(AB)=

14、AA(AB)=A(12)德.摩根律(DeMorgans laws)(AB)=AB(AB)=AB(13)补交转换律(difference as intersection)A-B=AB,2.7 集合恒等式证明(方法),（1）逻辑演算法:利用逻辑等价式和逻辑推理规则（2）集合演算法:利用集合恒等式和已知的集合结论,（1）逻辑演算法(格式),题型:A=B.证明：x,xA(?)xB A=B 证毕.或证明：x,xA(?)xB.另，x,xB(?)xA.A=B证毕.,题型:A B.证明:x,xA(?)xB A B证毕.,例1：分配律(证明),A(BC)=(AB)(AC)证明:x,xA(BC)xA x(BC)(

15、定义)xA(xB xC)(定义)(xAxB)(xAxC)(命题逻辑分配律)(xAB)(xAC)(定义)x(AB)(AC)(定义)A(BC)=(AB)(AC)成立,例2：零律(证明),A=证明:x,xA xA x(定义)xA F(定义)F(命题逻辑零律)A=成立,例3.排中律(证明),AA=E证明:x,xAA xA xA(定义)xA xA(定义)xA(xA)(定义)T(命题逻辑排中律)AA=E 成立,(2)集合演算法（格式）,题型:A=B.题型:AB.证明:A 证明:A=(?)(?)=B B A=B.#AB.#,例1：吸收律(一式证明),A(AB)=A证明:A(AB)=(AE)(AB)(同一律)

16、=A(EB)(逆用分配律)=AE(零律)=A(同一律)A(AB)=A,例2：吸收律(二式证明),A(AB)=A证明:A(AB)=(AA)(AB)(分配律)=A(AB)(幂等律)=A(吸收律第一式)A(AB)=A,(2)集合演算法（格式）续,题型:AB 证明:AB(或AB)=(?)=A(或B)AB.#说明:化成=,题型:A=B证明:()AB()A B A=B.#说明:把=分成与,AB=AABAB=BAB,2.8 集合恒等式证明(举例),1.基本集合恒等式例如：补交转换律A-B=AB 证明:x,xA-B xA xB xA xB x ABA-B=AB.,德摩根律的相对形式A-(BC)=(A-B)(A

17、-C)A-(BC)=(A-B)(A-C)证明:A-(BC)=A(BC)(补交转换律)=A(BC)(德摩根律)=(AA)(BC)(幂等律)=(AB)(AC)(交换律,结合律)=(A-B)(B-A)(补交转换律).#,2.对称差()的性质,（1）交换律：AB=BA（2）结合律：A(BC)=(AB)C（3）分配律：A(BC)=(AB)(AC)（4）同一律：A=A（5）排中律：AA=E（6）AA=（7）AE=A,作业(3-1,3-2)：,P85(1)a),c)(6)b),c)P94(5)a)思考题(8)(9)(11)b)提示:举例说明即可,3-3 包含排斥原理,集合的运算，可用于有限个元素的计数问题。

18、设A1，A2为有限集合，其元素个数分别记为|A1|，|A2|，根据集合运算的定义，显然以下各式成立。|A1A2|A1|+|A2|A1A2|min(|A1|，|A2|)|A1-A2|A1|-|A2|A1A2|=|A1|+|A2|-2|A1A2|,3-3 包含排斥原理,定理3-3.1 设A1，A2为有限集合，其元素个数分别为|A1|，|A2|，则|A1A2|=|A1|+|A2|-|A1A2|证明：见P96推理：对于任意三个有限集合A1，A2和A3，则|A1A2 A3|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2 A3|,3-3 包含排斥原理,定理3-3.2

19、见P97例题1：P96 例题2：P97,作业(3-3),P100(4),3-4序偶与笛卡尔积,3-4.1 序偶(二元组)定义序偶ordered pair：由两个固定次序的客体 a,b组成的序列称为序偶，记作，其中a,b称为序偶的分量。其中,a是第一元素,b是第二元素,记作也记作(a,b)。定理：序偶和 相等，当且仅当a=c 且b=d，即=(a=c)(b=d)推论:ab,3-4.2 三元组(ordered triple),定义三元组：=,c.定义 n(2)元组：=,an.定理:=ai=bi,i=1,2,n.,3-4.3笛卡尔积(Cartesian product)及其性质,定义笛卡尔积：A和B为

20、任意两个集合，若序偶的第一个成员是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(除非 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

21、)(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(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,y

22、B，AB AC xAyC yC.BC()若B=,则AB=AC.设 B.,AB xAyB xAyC AC ABAC.#,3-4.5 推广：n维笛卡尔积,定义 n维笛卡尔积：A1A2An=|x1A1x2A2xn An AAA=An|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之间”。我们又知道序偶可以表达两个客体、三个客

23、体或n个客体之间的联系，因此用序偶表达这个概念是非常自然的。,例如：火车票与座位之间有对号关系。设X表示火车票的集合，Y表示座位的集合，则对于任意的 xX 和 y Y，必定有 x 与y有“对号”关系 x 与y没有“对号”关系。二者之一令R表示“对号”关系，则上述问题可以表示为 xRy 或 xRy。,亦可表示为 R 或 R，因此我们看到对号关系是序偶的集合。,定义关系：二元关系(binary relation)，简称关系，任一序偶的集合即确定了一个二元关系R，R中任一序偶 可记为 R或xRy。不在R中的任一序偶 可记为 R或xRy,例1:在实数中关系“”可记作“”=|x,y是实数且x y。例2:

24、R1=,R1是二元关系.例3:A=,a,1 A不是关系.,二元关系的记号：,设R是二元关系,则R x与y具有R关系 xRy。对比:xRy(中缀(infix)记号)R(后缀(suffix)记号)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的二元

25、关系共有221=4个:R1=,R2=,R3=,R4=,B到A的二元关系也有4个:R5=,R6=,R7=,R8=,。,A上的二元关系,定义 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个:R1=,R2

26、=.例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,d,e,fdom R3=1,3,5,ran R3=2,4,6,FLD R

27、3=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=|xA yA xy 小于(less than)关系：LA=|xA yA xy 大于等于(greater than or

28、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,RAB,则R的关系矩阵 MR=(rij)nm,其中rij=1,ai R bj 或 R 0,ai R bj 或 R,例题：P103 例题5例如:A=a,b,c,R1

29、=,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)选做,