7.1-7.2关系.ppt

1、1,第七章 二元关系和函数,2,本章主要内容:,集合的笛卡尔积与二元关系 关系的运算 关系的性质 关系的闭包 等价关系和偏序关系,3,7.1 有序对与集合的笛卡儿积,定义7.1 由两个元素x和y(允许x=y)按一定的顺序排列成的二元组叫做一个有序对(也称序偶),记作,其中x是它的第一元素,y是它的第二元素。 平面直角坐标系中点的坐标就是有序对,例如,(1,1), (1,1) ,都代表坐标系中不同的点。,4,有序对的特点： 1.当xy时,。 2.两个有序对相等,即 的充分必要条件是xu且yv。,5,定义7.2 一个有序n元组(n3)是一个有序对,其中第一个元素是一个有序n1元组,一个有序n元组记

2、作,即 , xn 例如,空间直角坐标系中点的坐标 , 等 都是有序3元组。 n维空间中点的坐标或n维向量都是有序n元组。,6,定义7.3 设A,B为集合,用A中元素为第一元素,B中元素为第二元素,构成有序对,所有这样的有序对组成的集合叫做A和B的笛卡儿积,记作AB。符号化表示为 AB(x,y)|xAyB. 例如,Aa, b ,B 0, 1, 2,则 AB ,； BA , ,。,7,如果A中有m个元素,B中有n个元素, 则AB和BA中都有多少个元素? mn个 若AB,则有 xA和yB。 若AB,则有 xA或者y B.,8,笛卡儿积运算的性质: 1.若A,B中有一个空集,则它们的笛卡儿积是空集,

3、即 BB 2.当AB且A,B都不是空集时,有 ABBA。 所以,笛卡儿积运算不适合交换律。 3.当A,B,C都不是空集时,有 (AB)CA(BC). 所以,笛卡儿积运算不适合结合律。,9,4.笛卡儿积运算对或运算满足分配律即 A(BC)(AB)(AC)； (BC)A (BA)(CA)； A(BC)(AB)(AC)； (BC)A (BA)(CA)。,10,证明 A(BC)(AB)(AC) 证明 对于任意的, A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (x,y)(AB)(AC). 所以 A(BC)(AB)(AC)。,11,例7.1 设A=1,2,求P(A)A 解

4、 P(A)A ,1,2,1,21,2 , ,12,例7.2 设A,B,C,D为任意集合,判断以下等式是否成立,说明为什么。 (1) (AB)(CD)(AC)(BD)； (2) (AB)(CD)(AC)(BD)； (3) (AB)(CD)(AC)(BD)； (4) (AB) (CD) (AC) (BD)。,13,解.(1)成立.因为对于任意的, (AB)(CD) xAByCD xAxB yCyD AC BD (AC)(BD) (2)不成立。 举一反例如下：若AD,BC1 则有： (AB)(CD)BC, (AC)(BD)。 (3)和(4)都不成立,14,例7.3 设A,B,C,D为任意集合,判断以

5、下命题的真假. (1)若AC且BD,则有ABCD。 (2)若ABCD,则有AC且BD. 解 (1)命题为真。请思考：为什么？ (2)命题为假.当AB时,或者A且B时,该命题的结论是成立的。但是当A和B之中仅有一个为时,结论不一定成立,例如,令ACD,B1,这时ABCD,但BD。,15,定义7.4 设A1,A2, , An是集合(n2),它们的n阶笛卡儿积,记作A1A2An,其中 AlA2An|x1Alx2A2xnAn。 例如: A=a,b,则 A3= , , , ,16,7.2 二元关系Relation,所谓二元关系就是在集合中两个元素之间的某种相关性. 例如,甲、乙、丙三个人进行乒乓球比赛,

6、如果任何两个人之间都要赛一场,那么共要赛三场。假设三场比赛的结果是乙胜甲、甲胜丙、乙胜丙,这个结果可以记作 ,其中表示x胜y。它表示了集合甲,乙,丙中元素之间的一种胜负关系.,17,例子.有A,B,C三个人和四项工作,已知A可以从事工作,B可以从事工作,C可以从事工作,。那么人和工作之间的对应关系可以记作 R,。 这是人的集合A,B,C到工作的集合,之间的关系。,18,定义7.5 如果一个集合为空集或者它的元素都是有序对, 则称这个集合是一个二元关系,一般记作R。 对于二元关系R, 如果R,则记作xRy； 如果R,则记作,19,定义7.6 设A,B为集合,AB的任何子集所定义的二元关系称作从A

7、到B的二元关系,特别当AB时,则叫做A上的二元关系。 关系RAB, R is a relation from A to B. RAA, R is a relation on A. A上有多少个不同的二元关系? |A|=n |AA|=n2 |P(AA)|=2n2 每一个子集代表一个A上的关系,共2n2个关系.,20,对于任何集合A都有3种特殊的关系: 其中之一就是空集,称做空关系。 另外两种就是全域关系EA和恒等关系IA。 定义7.7 对任何集合A, EAxAyAAA。 IAxA。 例如：A=0,1,2,则 EA, IA,2,2)。,21,常用的关系:小于等于关系、整除关系,例如: 设A为实数集R的某个子集,则A上的小于等于关系定义为 LAx,yAxy 设B为正整数集Z的某个子集,则B上的整除关系定义为 DBx,yBxy.,22,例如: A=4,0.5,-1,B=1,2,3,6,则,LA , , , , DB , , , .,23,例7.4 设Aa, b ,R是P(A)上的包含关系, R|x, y P(A) x y, 则有 P(A),a, b, A。 R ,.,24,有穷集A上的关系R, 可用关系矩阵和关系图给出。 设A1,2,3,4, A上的关系 R, 。 R的关系矩阵和关系图如图,关系矩阵和关系图,25,26,关系矩阵和关系图,设V是顶点的集合,E是有向边的集合,令VAx1,