离散数学第四章二元关系和函数-课件.ppt

二元关系和函数,第四章,2,第4章 二元关系与函数,4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数,3,4.1 集合的笛卡儿积和二元关系,有序对笛卡儿积及其性质二元关系的定义二元关系的表示,4,有序对的性质：1） 有序性  （当x y时） 2） 与 相等的充分必要条件是=  x=u  y=v,例4.1 = ，求 x, y. 解 3y 4 = 2, x+5 = y  y = 2, x =  3,§4.1 二元关系的概念,1. 有序对/序偶：由两个元素x和y按一定顺序 排成二元组，记作： 其中x称作第 一个元素；y称作第二个元素5,实例 ： 1.空间直角坐标系中的坐标 是有序三元组 2. 图书馆记录是一个有序六元组.,2. 有序n元组：一个有序 n (n3) 元组 是一个有序对，其中第一个元素是一个有序 n-1元组，即, xn>= 我们将来的研究重点为有序二元组，即有序对/序偶,6,例4.2 A={1,2,3}, B={a,b,c},C= AB ={,,,,,, ,,} BA ={,,,,,,, ,} AA={,,,,,,,,} AC=  CA= ,3. 笛卡儿积：设A, B为集合，用A中元素为第一个元素，B中元素为第二个元素，构成有序对. 所有这样的有序对组成的集合叫做 A与B 的笛卡儿积记作AB, 即 AB ={ | xA  yB }。

7,笛卡儿积的性质：1. 不适合交换律 ABBA (AB, A, B) 2.若A或B中有一个为空集，则AB就是空集.A=B= 3. 若|A|=m, |B|=n, 则 |AB|=mn 4.不适合结合律 (AB)CA(BC) (A,B,C) 例： A={1},B={2},C={3} AB={}, (AB)C={,3>}={} BC={}, A(BC) ={>}  {},8,二元关系：集合中两个元素之间的某种关系例3 甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场假设比赛结果是乙胜甲，甲胜丙，乙胜丙 比赛结果可表示为： {， ， }，其中表示x胜y，它表示了集合{甲,乙,丙}中元素之间的一种胜负关系.例4 有A、B、C3个人和四项工作G1、 G2、 G3、 G4，已知A可以从事工作G1和G4，B可以从事工作G3，C可以从事工作G1和G2.那么，人和工作之间的对应关系可以记作R＝ {, , , ,

4. 二元关系：如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对(以有序对为元素的集合) （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作R.,,10,5.从A到B的关系与A上的关系 设A,B为集合, A×B的任何子集所定义的二元 关系叫做从A到B的二元关系, 当A=B时则叫做 A上 的二元关系.,例5 A={0,1}, B={1,2,3}, R1={}, R2=A×B, R3=, R4={}. 那么 R1, R2, R3, R4是从 A 到 B 的二元关系, R3和R4同时也是 A上的二元关系. 计数： |A|=n, |B|=m, |A×B|= n×m , A×B的子集有 个. 所以 A到B上有 个不同的二元关系. |A|=n, |A×A|= , A×A的子集有 个. 所以 A上有 个不同的二元关系. 例如 |A|=3, 则 A上有512个不同的二元关系.,11,A上重要关系的实例,设 A 为任意集合， 是 A 上的关系，称为空关系 EA, IA 分别称为全域关系与恒等关系，定义如下：  EA={|x∈A∧y∈A}=A×A  IA={|x∈A} 例如, A={1,2}, 则  EA={,,,}  IA={,} 注：{} ≠ IA; {} ≠ IA,12,A上重要关系的实例（续）,小于等于关系 LA, 整除关系DA, 包含关系R定义：LA={| x,y∈A∧x≤y}, DA={| x,y∈A∧x整除y}, R={| x,y∈P(A)∧xy}, A是某集合. 类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等.,13,实例,例如 A = {1, 2, 3}, B ={a, b}, 则 LA={,,,,,} DA={,,,,},P(B)={,{a},{b},{a,b}}, 则 B上的包含关系是 R={,,,,, ,,,},14,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若A={x1, x2, …, xm}，B={y1, y2, …, yn}，R是从A到B的关系，以A元素为行，B元素为列，MR = [ rij ] mn, 其中 rij = 1 R，否则rij = 0。

关系图：若A= {x1, x2, …, xm}，R是从A上的关系，R的关系图是GR=, 以A中元素为结点，如果  R，则从 xi 到 xj 有一条有向边. 注意：A, B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图仅适于表示A上的关系,15,实例,A={1,2,3,4}, R={,,,,}, R的关系矩阵MR和关系图GR如下：习题：4.1,练习,1.令A={1,2,3};B={a,b},求R1={,,,}的关系矩阵 2.令A={1,2,3};求R2={,,,}的关系图 3. 令F={,,,}，G={,,,}求F∘G, G∘F, F∘F方法自选）,17,基本运算定义 定义域、值域、域 逆、合成、限制、像 基本运算的性质 幂运算 定义 求法 性质,4.2 关系的运算,§4.2 关系的运算,,关系R的定义域： domR = {x | (y)R} (即R中有序组的第一个元素构成的集合),关系R的值域： ranR ={y | (x)R} (即R中有序组的第二个元素构成的集合),一、关系的定义域与值域,关系R的域： fldR = domR  ranR,19,关系的基本运算定义,例1 R={,,,}, 则  domR={1, 2, 4}  ranR={2, 3, 4} fldR={1, 2, 3, 4},20,关系的基本运算定义（续）,R1 = { | R}R∘S = | |  z ( S  R) } 例2 R={, , , }S={, , , , } R1={, , , } R∘S ={, , , }S∘R ={, , },二. 逆与合成,21,合成运算的图示方法,利用图示（不是关系图）方法求合成R={, , , }S={, , , , } R∘S = {, , , } S∘R ={, , },,R,S,S,R,S○ R≠R ○ S,22,实例 R={, , , } R↾{1}={,}R[{1}]={2,4}R↾{1,2}={,,}R↾=R[{1,2}]={2, 4},三 限制和像： 已知二元关系F 和集合AF 在A上的限制 F↾A = { | xFy  xA}A 在F下的像F[A] = ran(F↾A),注意：,F↾AF, F[A] ranF,23,四. 关系运算的基本性质,,(1),(2),(3) 不满足交换律： F○ G≠G ○ F,(4) 满足结合律： F○ G ○ H=F○ (G ○H),(5),25,五. A上关系的幂运算,设R为A上的关系, n为自然数, 则 R 的 n次幂定义为：(1) R0={ | x∈A }=IA(2) Rn+1 = Rn○ R注意：对于A上的任何关系R1和R2都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R,26,(1) 定义法：对于集合表示的关系R，计算 Rn 就是n个R左复合 . (2) 矩阵乘法：矩阵表示就是n个矩阵相乘, 其中相加采用逻辑加. （线性代数，逻辑乘法） (3) 关系图法：若点a经k(k=1,2,…,n)条线可到达点b，则在的关系图上，a到b有线相连。

例3 设A={a,b,c,d}, R={,,,}, 求R的各次幂, 分别用矩阵和关系图表示. 解 R与R2的关系矩阵分别为,,六. 幂的求法：,27,同理，R0=IA, R3和R4的矩阵分别是：因此M4=M2, 即R4=R2. 因此可以得到 R2=R4=R6=…, R3=R5=R7=…,,,28,R0, R1, R2, R3,…的关系图如下图所示,关系图法,结论： 仅当A有回路时，上述结论成立当图中没有回路时：,30,七. 幂的性质：,当关系图有回路时：,(2),(3),31,证明（2）：用数学归纳法 若n=0, 则有 Rm○R0=Rm○IA=Rm=Rm+0 假设Rm○Rn=Rm+n, 则有 Rm○Rn+1=Rm○ (Rn○R)=(Rm○Rn) ○R=Rm+n+1 幂运算的性质（续）,证明（3）：若n=0, 则有  假设 则有,课后习题：4.2，4.3，4.13,§4.3 关系的性质,,R的关系矩阵：主对角线元素全是1,R的关系图：每个顶点都有环,自反性： x  A 有R (R是A上的关系),关系矩阵：主对角线元素全是0,关系图： 每个顶点都没有环,反自反性：x  A  R,例1： A={1,2,3}, R1={,} R2={,,} R3={,,, } R4={,,} R5={,},既不是自反的也不是非自反的,自反的,自反的,既不是自反的也不是非自反的,反自反的,例1：,是自反的一定不是反自反的；是反自反的一定不是自反的,！在自反性方面R有3种可能：自反的；反自反的；既非自反又非反自反的,对称性：若  R，则  R,关系矩阵：对称阵(aij=aji),关 系 图：如果两个顶点之间有边，一定是一对方向相反的边。

反对称性：若  R且xy，则  R,关系矩阵：如果rij = 1，且 i j，则rji = 0,关系图： 如果两个顶点之间有边，一定是只有一条有向边R= {|xR}既是对称关系又是反对称关系,例2：,A={1,2,3}, R1={,,,} R2={,,} R3={,,} R4={,,} R5={,,},反对称的,既对称又反对称的,对称的,反对称的,既非对称又非反对称的,！在对称性方面R有4种可能：对称的；反对称的；既对称又反对称的；既非对称又非反对称的,,传递性：若  R且  R，则  R,关系图：如果顶点xi到xj有边， xj到xk有边，则从xi到xk有边,！若a可经过两条或两条以上的线到达b，则 R,例3：,A={1,2,3,4}, R1={,,} R2={,} R3={,,} R4={,,,} R5={,,,,},传递的,传递的,非传递的,传递的,非传递的,！在传递性方面，R有两种可能：传递的；非传递的练习：,自反的,对称的,反对称的,传递的,自反的,对称的,传递的,反自反的,反对称的,反对称的,传递的,课后习题：4.4，4.12,根据关系图判断关系的综合性质：,,§4.4 关系的闭包运算,。