《《集合与关系》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《集合与关系》PPT课件.ppt（88页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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,q3-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。AB AB ABAB(x)(
5、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 BC,所以AC.假设A=C,则BCBA,又AB,故A=B,此与AB矛盾,所以AC
6、.所以,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)P(x)，P(x)为任何谓词全集是相对的,视情况而定,因此不唯一。例如,讨论(a,b)区间里的实数性质时,可以选 E=(a,b)
7、,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 定义 集合的交(intersection):设任意两个集合A和B，由集合A和B的所有共同元素组成的集合S，称为A和B的交集，记作AB。S=AB=x|(xA)(xB)xAB (xA)(xB)例2:设
8、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=02.1.3 不相交不相交(disjoint)不相交：AB=互不相交：设A1,A2,是可数多个集合,若对于任意的ij,都有AiAj=,则说它们互不相交。例:设 An=xR|n-1xn,n=1,2,10,则 A1,A2,是不相交的2.1.4 集合交运算的性质a)A A=A （幂等律）b)A =（零律）c)A E=A （同一律）d)A B=B A （交换律）e)(A B)C=A (B C)（结合律）因为集合交运算满足结合律，故n个集合的交记为：n
9、P=A1 A2 An =Ai i=12.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，100，12.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)（结合律）因为集合并运算满足结合
10、律，故n个集合的并记为：nP=A1A2 An=Ai i=12.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|(xExA)2.4 集合的对称差2.4.1 定义对称差(symmetric difference)：属于A而不属于B,或属于B而不属于A的全体元素组成的集合S,称为A与B的对称差,
11、记作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)结合律(associative laws)(AB)C=A(BC)(AB)C=A(BC)(3)交换律(commutative laws)AB=BAAB=BA(4)分配律(distributive laws)A(BC)
12、=(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)=AA(AB)=A(12)德.摩根律(DeMorgans laws)(AB)=AB(AB)=AB(13)补交转换律(difference as intersection)A-B=AB 2.7 集合
13、恒等式证明(方法)（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)(定义)xA (xB xC)(定义)(xAxB)(xAxC)(命题逻辑分配律)(xAB)(xAC)(定义)x(AB)(AC)(定义)A(BC)=(AB)(AC)成立例2：零律(证明)A=证明:x,xA
14、 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=(?)(?)=BBA=B.#AB.#例1：吸收律(一式证明)A(AB)=A证明:A(AB)=(AE)(AB)(同一律)=A(EB)(逆用分配律)=AE (零律)=A (同一律)A(AB)=A例2：吸收律(二式证明)A(AB)=A证明:A(AB)=(AA)(AB)(分配律)=A(AB)(幂等律)=A (吸
15、收律第一式)A(AB)=A(2)集合演算法（格式）续题型题型:A B 证 明:AB(或AB)=(?)=A(或B)AB.#说明说明:化化 成成=题型题型:A=B证明:()AB ()A B A=B.#说明说明:把把=分成分成 与与 AB=AABAB=BAB2.8 集合恒等式证明(举例)1.基本集合恒等式例如：补交转换律A-B=AB 证明:x,xA-B xA xB xA xB x ABA-B=AB.德摩根律的相对形式A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)证明:A-(BC)=A(BC)(补交转换律)=A(BC)(德摩根律)=(AA)(BC)(幂等律)=(AB)(AC)(交
16、换律,结合律)=(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 包含排斥原理集合的运算，可用于有限个元素的计数问题。设A1，A2为有限集合，其元素个数分别记为|A1|，|A2|，根据集合运算的定义，显然以下各式成立。|A1A2|A1|+|A2|A1A2|min(|A1|，|A2|
17、)|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 见P97例题1：P96 例题2：P97作业(3-3)P100 (4)3-4序偶与笛卡尔积3-4.1序偶(二元组)定义序偶ordered pair：由两个固定次序的客体 a,
18、b组成的序列称为序偶，记作，其中a,b称为序偶的分量。其中,a是第一元素,b是第二元素,记作也记作(a,b)。定理：序偶和 相等，当且仅当a=c且b=d，即=(a=c)(b=d)推论:ab 3-4.2三元组(orderedtriple)定义三元组：=,c.定义n(2)元组：=,an.定理:=ai=bi,i=1,2,n.3-4.3笛卡尔积(Cartesianproduct)及其性质定义笛卡尔积：A和B为任意两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样序偶的集合，称为A和B的笛卡尔积或直积，记为：AB=|(xA)(yB).例1:A=,a,B=1,2,3.AB=,.BA=,
19、.AA=,.BB=,.3-4.4笛卡尔积的性质：当|A|=m，|B|=n时，|AB|是多少？|AB|=mn3-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)=1,.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)xA y(BC)
20、xA(yB yC)(xAyB)(xAyC)(AB)(AC)(AB)(AC)A(BC)=(AB)(AC).#4.其他性质：设A,B,C,D是任意集合,(1)若A,则ABAC BACABC（即书上的定理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|A
21、i|=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和yY，必定有x与y有“对号”关系x与y没有“对号”关系。二者之一令R表示“
22、对号”关系，则上述问题可以表示为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 (后缀(suffix)记号)R(x,y)(前缀(prefix)记号)例如:215 (2,15)。R 1R
23、2,R 5R4。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上的二元关系定义A上的二元关系:是AA的任意子集。R是A上的二元关系 RAA RP(AA)。若|A|=m,则|AA|=m2,故|P(AA)|=2 m2
24、，即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=.例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 ra
25、n 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 R3=1,2,3,4,5,6.3-5.3一些特殊关系设A是任意集合,则可以定义A上的：空关系(emptyrelation):恒等关系(identityrelation):IA =|a A 全域关系(universalrelation):UA=AA=|xA yA设AR,则可以定义A
26、上的：小于等于(less than or equal to)关系：LEA=|xA yA xy 小于(less than)关系：LA=|xA yA xy 大于等于(greater than or equal to)关系，大于(great than)关系,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 Rbj或R 0,ai Rbj或R例题：P1
27、03 例题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 例题7abcGR2abcGR1定义在集合A上的关系图有所不同例如（上例）,A=a,b,c,R1=,R2=,则关系图如下：关系矩阵、关系图(讨论)：当A中元素标定次序后,RAA的关系图GR与R的序偶集合表达式可以唯一互相确定。R的序偶集合表达式，关系矩阵，关系图三者均可以唯一互相确定。作业(3-5)P109 (1)(5)c)给出关系图和关系矩阵 (8)选做