集合论与图论.ppt

《集合论与图论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第3-2讲笛卡儿积与关系1.序偶的概念2.笛卡儿积3.笛卡儿积的性质4.关系的概念5.关系的表示6.关系的性质7.课堂练习8.第3-2讲作业21、序偶的概念定义１两个元素x、y构成的有序二元组，叫有序对或序偶。按序偶的定义，序偶具有如下性质：1．若xy时，。2．=，当且仅当x=u,y=v。序偶的概念可推广到三元组、四元组、…、n元组:有序三元组表示序偶<,z>;有序四元组表示序偶<,w>;有序n

2、元组表示序偶<,xn>32、笛卡儿积定义2设A、B为集合，由序偶组成的集合{

3、xA,yB}叫A与B的笛卡儿积，记作AB。例1设A={a,b}，B={1，2，3},求AB，BA。解：AB={,,,,}。BA={<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>}。由此例可知，笛卡儿积不满足交换律。约定：当A=或B=时，AB=43、笛卡儿积的性质笛卡儿积的运

4、算有如下性质：设A、B、C为任意集合，则（1）A=，A=（2）ABBA（当ABAB时）（3）(AB)CA(BC)（当ABC时）（4）A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)后四个式子按集合相等的概念可以证明。例2证明(BC)A=(BA)(CA)证:在集合(BC)A中任取，那么(BC)Ax(BC)yA

5、(xBxC)yAxByAxCyA(xByA)(xCyA)(BA)(CA)(BA)(CA)所以(BC)A=(BA)(CA)。53、笛卡儿积的性质(续1)（5）若C,则AB(ACBC)(CACB)证:若yC,AB,任取AC，有ACxAyCxByCBC因此，ACBC。反之，若C,ACBC。取yC，则有xAxA

6、yC（已设yC，故yC为真）ACBCxByCxB因此，AB类似可证：AB(CACB)。（6）设A、B、C、D为任意非空集合，则(ABCD)ACBD（证明与性质（5）的证明方法类似，从略）63、笛卡儿积的性质(续2)例3证明(A-B)C=(AC)-(BC)。证：(A-B)Cx(A-B)yCxAxByC(xAyCxB)(xAyCyC)(xAyC)(xByC)(x

7、AyC)(xByC)(xAyC)(xByC)ACBC(AC)-(BC)所以，(A-B)C=(AC)-(BC)。74、关系的概念定义3任一序偶的集合R称为一个二元关系。R也记作xRy事物之间存在着各式各样的关系，例如，三名学生A、B、C选修、、、四门课，设A选和，B选，C选和，那么，学生选课的对应关系可记作：R={,,,,}这个序偶的集合R反映了

8、学生集合S={A,B,C}与课程集合T={,,,}之间的关系。定义4设R是二元关系,集合{xy(R)}叫R的定义域,记作domR。集合{yx(R)}叫R的值域,记作ranR。domRranR叫R的域，记作fldR。84、关系的概念(续1)定义5设X和Y是两个任意集合，直积XY的任一子集R称为X到Y的关系。直积XY本身和空集，分别称为X到Y的全域关系和空关系若X=Y，RXX，R称为X上的二元关系。定义6记IX={(xX)},称IX是X上的恒等关系。94

9、、关系的概念(续2)例4设A={1，2，3，4}，求A上的小于等于关系LA。解：LA={

10、x,yAxy}={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}例5设集合A有n个元素,问A上可能的二元关系有多少个？解：集合A上的二元关系与AA的子集个数相同。若

11、A

12、=n，则