序偶与集合的笛卡尔积-集合与关系-离散数学

序偶与集合的笛卡尔积第1页目标：计算集合的笛卡尔积。要求：1、理解概念；2、掌握序偶和笛卡尔积的定义和性质。第2页一、序偶与有序n元组两个具有固定次序的客体x、y组成序偶，也称为有序二元组，记作x,y；称x、y分别为序偶x,y的第一，第二元素。固定次序是指调换第一和第二元素位置后，含义不同。注意，第一、二元素未必不同。1.定义：说明2,33,21,-2-2,1-4,-3第3页序偶的性质（1）当x≠y时，x,y≠y,x。{x,y}={y,x}（2）序偶二个元素可以重复，即x,x也是序偶。无{x,x}（3）序偶中两个元素可以来自不同的集合。x,y：x∈A,y∈B{x,y}∈A（4）序偶与集合的统一：x,y={{x},{x,y}}（5）序偶相等的定义：(x,y=u,v)(x=u)∧(y=v)由序偶相等的定义有x+2＝52x+y＝4解得x＝3,y＝-2。解答例已知x+2,4＝5,2x+y，求x和y。第4页序偶的推广：有序N元组定义由N个元素x1,x2,…,xn-1,xn按照一定的次序组成的N元组称为有序N元组，记为x1,x2,…,xn-1,xn。xi叫做该n元组的第i个分量i=1,…,n。有序N元组与序偶的关系：x1,x2,…,xn-1,xn=x1,x2,…,xn-1,xn三元组x1,x2,x3=x1,x2,x3四元组x1,x2,x3,x4=x1,x2,x3,x4=x1,x2,x3,x4注意：x1,x2,x3≠x1,x2,x3x1,x2,x3,x4≠x1,x2,x3,x4x1,x2,x3,x4,x5≠x1,x2,x3,x4,x5例如：a年b月c日d时e分f秒，可用六元组表示a,b,c,d,e,f第5页定义：两个n元组相等设x1,x2,…,xn与y1,y2,…,yn是两个n元组，如果xi=yi，i=1,…,n，则称这两个n元组相等，记为x1,x2,…,xn=y1,y2,…,yn。用逻辑的方法表示为(x1,x2,…,xn=y1,y2,…,yn)(x1=y1)∧(x2=y2)∧…∧(xn=yn)。a,b,c,db,a,d,ca,b,d,c第6页二、集合的笛卡尔积引例“斗兽棋”虎象狮豹狼鼠猫狗虎象狮豹狼鼠猫狗每个棋子可以看成一个序偶:红,象,红,狮,红,虎,红,豹,红,狼,红,狗,红,猫,红,鼠,蓝,象,蓝,狮,蓝,虎,蓝,豹,蓝,狼,蓝,狗,蓝,猫,蓝,鼠可看成是由两种颜色的集合A和8种动物的集合B做运算得到的。A={红,蓝}B={象,狮,虎,豹,狼,狗,猫,鼠}斗兽棋可记成集合：}{斗兽棋可记成集合：第7页补充的定义:A和B的笛卡尔积或直积设A、B是集合，由A的元素为第一元素，B的元素为第二元素组成的所有序偶的集合，称为A和B的笛卡尔积或直积，记作A×B，即AB={x,y|xA∧yB}x,yABxA∧yBx,yABxA∨yB例如：A表示某大学所有学生的集合，B表示大学开设的所有课程的集合。则A×B可以用来表示该校学生选课的所有可能情况。1、集合的笛卡尔积的定义第8页AB={0,a,0,b,1,a,1,b,2,a,2,b}BA={a,0,a,1,a,2,b,0,b,1,b,2}AA={0,0,0,1,0,2,1,0,1,1,1,2,2,0,2,1,2,2}可见A×B≠B×A集合的笛卡尔积运算不满足交换律。例：A={0,1}，B={a,b}，C={z}(AB)C={0,a,0,b,1,a,1,b}×{z}={0,a,z,0,b,z,1,a,z,1,b,z}A(BC)={0,1}{a,z,b,z}={0,a,z,0,b,z,1,a,z,1,b,z}(AB)C={x,y,z|x,yAB∧zC}A(BC)={x,y,z|xA∧y,zBC},可见(AB)CA(BC)。集合的笛卡尔积运算也不满足结合律。例：设A={0,1,2}，B={a,b}，求AB，BA，AA。|AB|=6=|BA||AA|=9第9页1)如果A、B都是有限集，且|A|=m,|B|=n，则|AB|=m•n.证明：由笛卡尔积的定义及排列组合中的乘法原理，直接推得此定理。2)AΦ=ΦB=Φ3)对∪和∩满足分配律。设A,B,C是任意集合，则①A(B∪C)=(AB)∪(AC)；②A(B∩C)=(AB)∩(AC)；③(A∪B)C=(AC)∪(BC)；④(A∩B)C=(AC)∩(BC)4)若C,则AB(ACBC)(CACB)。5)设A,B,C,D为非空集合，则ABCDAC∧BD。（两个笛卡尔积具有包含关系，则相应的分量也具有包含关系）2、集合的笛卡尔积的性质第10页2、集合的笛卡尔积的性质（续）求证：①A(B∪C)=(AB)∪(AC)分析：x,yA(B∪C)??x,y(AB)∪(AC)证明：任取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)所以A(B∪C)=(AB)∪(AC)其余可以类似证明。A(B∪C)x,yA(B∪C)(AB)∪(AC)x,y(AB)∪(AC)A={a},B={1,2},C={2,3}A(B∪C)={a}{1,2,3}={a,1,a,2,a,3}AB={a}{1,2}={a,1,a,2}AC={a}{2,3}={a,2,a,3}(AB)∪(AC)={a,1,a,2,a,3}A(B∪C)=(AB)∪(AC)第11页即AB(ACBC)类似可以证明AB(CACB)。4)若C,则AB(ACBC)(CACB).证明:证AB(ACBC)①证：ABACBC设AB,任取x,yACxA∧yC(由AB)xB∧yCx,yBC即x,yBC所以,ACBC。2、集合的笛卡尔积的性质（续）②证：(ACBC)AB若C,任取yC,任取xAxA∧yCx,yAC(由ACBC)x,yBCxB∧yCxB所以,AB。x,yABxA∧yBAB(x)(x∈Ax∈B)第12页5)设A,B,C,D为非空集合，则ABCDAC∧BD。证明:①证：由ABCDAC∧BD。任取xA，任取yB，xA∧yBx,yA×B(由ABCD)x,yC×DxC∧yD即xC∧yD所以,AC∧BD.②证：由AC∧BDABCD。任取x,yA×Bx,yA×BxA∧yB(由AC，BD)xC∧yDx,yC×D即x,yC×D所以,ABCD因此，ABCDAC∧BD。2、集合的笛卡尔积的性质（续）第13页注意：两集合的笛卡尔积仍是一个集合，故对于有限集合可进行多次笛卡尔积运算。A×B×C=(A×B)×CA×B×C×D=(A×B×C)×D=((A×B)×C)×DA1×A2×…×An=(A1×A2×…×An-1)×An={x1,x2,…,xn|x1∈A1,x2∈A2,…,xn∈An}A×A=A2,A×A×A=A3,A×A×…×A=An第14页例：令A1={x|x是学号}A2={x|x是姓名}A3={男,女}A4={x|x是出生日期}A5={x|x是班级}A6={x|x是籍贯}则A1A2A3A4A5A6中一个元素：001，王强，男，1981-02-16，计2001-1，河南是学生档案数据库的一条信息，所以学生的档案就是A1A2A3A4A5A6的一个子集。3、集合的笛卡尔积的应用作业第105页⑵第15页