离散数学第四章：二元关系和函数

二元关系和函数,第四章,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 <2, x+5> = <3y 4, y>，求 x, y. 解 3y 4 = 2, x+5 = y  y = 2, x =  3,§4.1 二元关系的概念,1. 有序对/序偶：由两个元素x和y按一定顺序排成二元组，记作： 其中x称作第一个元素；y称作第二个元素5,实例 ：1.空间直角坐标系中的坐标 <3，5，－6> 是有序三元组2. 图书馆记录<书类别，书号，书名，作者，出版社，年份>是一个有序六元组.,2. 有序n元组：一个有序 n (n3) 元组 是一个有序对，其中第一个元素是一个有序 n-1元组，即 < , xn>= 。

我们将来的研究重点为有序二元组，即有序对/序偶,6,例4.2 A={1,2,3}, B={a,b,c},C=  AB ={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>, <3,a>,<3,b>,<3,c>} BA ={,,,,,, , ,} AA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>, <3,1>,<3,2>,<3,3>}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={<1,2>}, (AB)C={<<1,2>,3>}={<1,2,3>}BC={<2,3>}, A(BC) ={<1,<2,3>>}  {<1,2,3>},8,二元关系：集合中两个元素之间的某种关系例3 甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。

假设比赛结果是乙胜甲，甲胜丙，乙胜丙比赛结果可表示为： {<乙,甲>， <甲,丙 >， <乙,丙>}，其中表示x胜y，它表示了集合{甲,乙,丙}中元素之间的一种胜负关系.例4 有A、B、C3个人和四项工作G1、 G2、 G3、 G4，已知A可以从事工作G1和G4，B可以从事工作G3，C可以从事工作G1和G2. 那么，人和工作之间的对应关系可以记作 R＝ {, , , , ∈R, 可记作 xRy；如果R, 则记作xR y实例：R1={<1,2>,}, R2=  , R3={<1,2>,3,4}，R4={|x∈N∧y ∈Z}R1,R2,R4是二元关系；R3不是二元关系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={<0,2>}, R2=A×B, R3=, R4={<0,1>}. 那么 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={<1,1>,<1,2>,<2,1>,<2,2>} IA={<1,1>,<2,2>}注：{<1,1>} ≠ IA; {<2,2>} ≠ 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={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>} DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>},P(B)={,{a},{b},{a,b}}, 则 B上的包含关系是 R={<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>, <{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>},14,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若A={x1, x2, …, xm}，B={y1, y2, …, yn}，R是从A到B的关系，以A元素为行，B元素为列，MR = [ rij ] mn, 其中 rij = 1 < xi, yj> 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={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系矩阵MR和关系图GR如下：习题：4.1,练习,1.令A={1,2,3};B={a,b},求R1={<1,a>,<1,b>,<2,b>,<3,a>}的关系矩阵2.令A={1,2,3};求R2={<1,1>,<1,3>,<2,1>,<3,2>}的关系图3. 令F={<1,2>,<2,3>,<3,1>,<1,3>}，G={<2,1>,<2,2>,<2,3>,<1,4>}求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={<1,2>,<1,3>,<2,4>,<4,3>}, 则  domR={1, 2, 4}  ranR={2, 3, 4} fldR={1, 2, 3, 4},20,关系的基本运算定义（续）,R1 = { | R} R∘S = | |  z ( S < z, y > R) } 例2 R={<1,2>, <2,3>, <1,4>, <2,2>} S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R1={<2,1>, <3,2>, <4,1>, <2,2>} R∘S ={<1,2>, <1,4>, <3,2>, <3,3>} S∘R ={<1,3>, <2,2>, <2,3>},二. 逆与合成,21,合成运算的图示方法,利用图示（不是关系图）方法求合成 R={<1,2>, <2,3>, <1,4>, <2,2>} S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R∘S = {<1,2>, <1,4>, <3,2>, <3,3>} S∘R ={<1,3>, <2,2>, <2,3>},,R,S,S,R,S○ R≠R ○ S,22,实例 R={<1,2>, <3,2>, <1,4>, <2,2>} R↾{1}={<1,2>,<1,4>} R[{1}]={2,4} R↾{1,2}={<1,2>,<1,4>,<2,2>} R↾= R[{1,2}]={2, 4},三 限制和像： 已知二元关系F 和集合A F 在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,。