集合论与图论.ppt

1、1,第3-2讲 笛卡儿积与关系,1. 序偶的概念 2. 笛卡儿积 3. 笛卡儿积的性质 4. 关系的概念 5. 关系的表示 6. 关系的性质 7. 课堂练习 8. 第3-2讲 作业,2,1、序偶的概念,定义 两个元素x、y构成的有序二元组，叫有序对或序偶。,按序偶的定义，序偶具有如下性质： 1若xy时，。 2=，当且仅当x=u,y=v。 序偶的概念可推广到三元组、四元组、 n元组: 有序三元组表示序偶,z; 有序四元组表示序偶,w; 有序n元组表示序偶,xn,3,2、笛卡儿积,定义2 设A、B为集合，由序偶组成的集合|xA,yB叫A与B的笛卡儿积，记作AB。,例1 设A =a,b， B =1，

2、2，3, 求AB， BA。 解：AB=,。 BA=,。 由此例可知，笛卡儿积不满足交换律。 约定：当 A= 或 B=时， AB=,4,3、笛卡儿积的性质,笛卡儿积的运算有如下性质：设A、B、C为任意集合，则 （1）A=，A= （2）AB BA（当A B A B时） （3）(AB)C A(BC)（当A B C 时） （4）A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 后四个式子按集合相等的概念可以证明。,例2 证明(B C)A=(BA) (CA) 证:在集合(BC)A中任取，那么 (BC)A x(BC)yA (xBxC)y

3、A xByAxCyA (xByA)(xCyA) (BA)(CA) (BA)(CA) 所以(BC)A=(BA)(CA)。,5,3、笛卡儿积的性质(续1),（5）若C ,则 AB (AC BC) (CA CB),证:若yC, AB, 任取 AC，有 AC xAyC xByC BC 因此， AC BC。 反之，若C , AC BC。取yC ，则有 xA xAyC （已设yC ，故yC 为真） AC BC xByC xB 因此， AB 类似可证： AB (CA CB)。,（6）设A、B、C、D为任意非空集合，则 (AB CD) AC BD （证明与性质（5）的证明方法类似，从略）,6,3、笛卡儿积的性

4、质(续2),例3 证明(A-B)C=(AC)-(BC)。,证：(A-B)C x(A-B)yC xAxB yC (x AyC xB) (xAyC yC) (x AyC) (xByC) (x AyC) (xByC) (x AyC)(xByC) ACBC (AC)-(BC) 所以，(A-B)C=(AC)-(BC)。,7,4、关系的概念,定义3 任一序偶的集合R称为一个二元关系。 R 也记作 xRy,事物之间存在着各式各样的关系，例如，三名学生A、B、C选修、四门课，设A选和，B选，C选和，那么，学生选课的对应关系可记作 ： R=, 这个序偶的集合R反映了学生集合S=A,B,C与课程集合T=,之间的关

5、系。,定义4 设R是二元关系,集合 xy (R) 叫R的定义域,记作domR。集合 yx (R) 叫R的值域,记作ranR。 domR ranR叫R的域，记作fldR。,8,4、关系的概念(续1),定义5 设X和Y是两个任意集合，直积XY的任一子集R称为X到Y的关系。 直积XY本身和空集，分别称为X到Y的全域关系和空关系 若X=Y，R XX，R称为X上的二元关系。,定义6 记IX= ( x X) ,称IX 是X上的恒等关系。,9,4、关系的概念(续2),例4 设A=1，2，3，4，求A上的小于等于关系LA。 解：LA=|x,yAxy =, ,例5 设集合A有n个元素,问A上可能的二元关系有多少

6、个？ 解：集合A上的二元关系与AA的子集个数相同。若|A|=n，则|AA|=n2, AA的子集个数就有2的n2次方个。所以A上不同的二元关系有2的n2次方个。 例如，集合A=a,b上的二元关系有16个,10,4、关系的概念(续3),例5 设集合A有n个元素,问A上可能的二元关系有多少个？ 解（续）：集合A=a,b上的16个二元关系： R1= (空关系) ; R2=, R3=, R4=, R5=; R6= , (恒等关系IA)， R7=, R8=, R9=, R10=, R11=,; R12=, R13=, R14=, R15=,; R16= , (全域关系EA) 。,11,5、二元关系的表示,

7、关系矩阵 设A=x1,x2,xn，R为A上的二元关系。令,则称（ri,j）为R的关系矩阵，记为MR。,一个二元关系可用集合、关系矩阵和关系图表示。,12,5、二元关系的表示(续1),设A=x1,x2,xn，R为A上的二元关系。用n个小圆圈表示x1,x2,xn，xi称为顶点。若xiRxj，则从顶点xi到顶点xj画一条有向弧，称为边。这样得到的图叫R的关系图。记为GR=，其中V表示顶点集合，E表示边集合。,例6 设A=1，2，3，4，用集合表示法、关系矩阵和关系图给出A上的整除关系DA。 解：DA=| x,yAx整除y =,13,6、关系的性质,定义3 设R为A上的关系， （1）若x xAx,xR

8、，则称R在A上是自反的。 （2）若x xAx,xR，则称R在A上是反自反的。,关系的性质主要有以下五种：自反性，反自反性，对称性，反对称性和传递性。,例如，集合A上的全域关系EA、恒等关系IA、小于等于关系LA、整除关系DA都是A上的自反关系；包含关系(R )、平面几何中的全等和相似关系也是自反关系。 小于关系和真包含关系都不是自反关系，它们是反自反关系。,14,6、关系的性质(续1),例7 设A=1,2,3，R1, R2, R3,是A上的关系，其中 R1=, R2=, R3= 说明R1, R2, R3,是否为A上的自反关系和反自反关系 解：R2是自反的。 R3是反自反的。 R1既不是自反的，

9、因为它不包含；也不是反自反的，因为它包含了,。,15,6、关系的性质(续2),定义3 设R为A上的关系， （1）若xyx,yARR，则称R为A上对称关系。 （2）若xyx,yARRx = y，则称R为A上反对称 关系。,A上的空关系既是A上对称关系,又是A上反对称关系。 恒等关系IA、全域关系EA是A上的对称关系。 同学关系、几何中的相似关系是对称关系。 小于等于()关系不是对称关系，而是反对称关系。,16,6、关系的性质(续3),例8 设A=2，3，5，7，R=|(x-y)/2为整数，证明R在A上是自反的和对称的。 证：对任意 xA，有(x-x)/2=0为整数，故R，所以R在A上是自反的。

10、设x,yA，如果R, 那么(x-y)/2为整数，从而-(x-y)/2=(y-x)/2亦为整数,所以R,故R是对称的。 对本例可直接写出R，画出关系图，观测其性质：,R=, , ,， R的关系图如右:,17,6、关系的性质(续5),定义3 设R为A上的关系，若 xyzx,y,zARR R 则称R为A上传递关系。,例如，A上的全域关系、恒等关系和空关系都是A上的传递关系。小于关系，小于等于关系、整除关系、包含关系和真包含关系也是相应集合上的传递关系。,例9 设A=1，2，3，R1, R2, R3,都是A上的关系， R1=,， R2=, ，R3= 问R1, R2, R3,是否为A上的传递关系?,解：

11、R1和R3是A上的传递关系；R2不是A上的传递关系，因为 ,R ，但R 。,18,7、课堂练习,练习1：设A=1，2，3，A上的关系S如下： S=,，讨论S的性质 。 解： S不是自反的，因S，也不是反自反的，因,S。 S不是对称的，因S，但S，也不是反对称的，因,S。 S不是传递的，因,S，但S。,问题: 为使S成为自反、对称、传递的,应作如何扩充？,19,7、课堂练习(续),练习2：设R是集合X上的自反关系，求证：R是对称的和传递的，当且仅当R,R，则R。 证：(1)证：如果R是自反、对称的和传递的，则当R,R，必有R。 对任意a,b,c R, 如果R,R,则R(因对称),进而有R(因传递