CH4_二元关系和函数____1_二元关系的基本概念.ppt

离散数学 CH4二元关系和函数 回顾 用推理规则证明： |= A 证明： 设论域D=a , b , c，求证： 第4章二元关系和函数 本章学习 1.集合的笛卡尔积 2.关系及其表示 3.关系的运算 4.关系的性质 5.关系的闭包 6.等价关系和偏序关系 7.函数的定义和性质 8.函数的复合和反函数 今日内容 集合的笛卡尔积 关系及其表示 关系的运算 笛卡尔乘积 定义：由两个元素x和y（允许x=y）按 一定的顺序排列成的二元组叫做一个 有序对（也称序偶），记做，其 中x是它的第一元素，y是它的第二元 素。 平面直角坐标系中点的坐标就是序偶。 例如，,.都代 表坐标系中不同的点。 序偶的特点（与集合的不同之处） 当xy时， 两个有序对相等，即=的充 要条件是x=u,且y=v 定义（有序n元组）:一个有序n元组（n3）是 一个有序对，记做, 其中第一个元组是一个有序n-1元组， 即 =,xn, 例如，空间直角坐标系中点的坐标 1,-1,3,2,4,0等都是有序3元组。 N维空间中点的坐标或n维向量都是有序n元组 定义（笛卡儿积）: 设A，B为集合，用A中元 素作为第一元素，B中元素作为第二元素，构 成序偶。所有这样的序偶组成的集合叫做A和 B的笛卡儿积，记作AB。符号化表示为 AB=|xAyB 例:若A=a,b,B=0,1,2,则 AB=, , BA=, , , , , 笛卡儿积中元素的个数 如果A中有m个元素,B中有n个元素, 则AB和BA中都有mn个元素 笛卡儿积运算的性质 若A,B中有一个空集,则它们的笛卡儿积是空集.即 B=A = 笛卡儿积运算不适合交换律: 当AB且A,B都不是空集时,有ABBA 笛卡儿积运算不适合结合律: 当A,B,C都不是空集时,有(AB)CA(BC) 设xA,yB,zC,那么,z(AB) C, A(BC)。 一般情况下, ,z 所以, (AB)CA(BC) 笛卡儿积运算对或运算满足分配律，即 A (BC) = (A B) (A C) (BC) A = (B A) (C A) A (BC) = (A C) (A C) (BC) A = (B A) (C A) 证明A (BC) = (A B) (A C) 对于任何的x,y ， x, y A (B C) x A yBC x A (y B y C) (x A y B) (x A yC) x, y A B x, y A C x, y (A B) (A C) 所以 A (BC) = (A B) (AC) 例:设A=1，2，求P（A）A 解: P（A）A = ，1，2，1,2, 1，2 = ,1, , , ， ，, 这是人的集合甲，乙，丙到工作的集合 ，b，c，d之间的关系。 除了二元关系以外还有多元关系 本书只讨论二元关系。以后凡是出现关系的地 方均指二元关系 下面给出二元关系的一般定义 定义（二元关系）如果一个集合为空集或它的 元素都是有序对，则称这个集合是一个二元关 系，一般记作R。 对于二元关系R，如果x，y R，则记作 xRy。 设A，B为集合，AB的任何子集所定义的二元 关系称作从A到B的二元关系，特别当A=B时， 则叫做A上的二元关系。 例：集合A0,1，B2,3 AB， ， ， AA的子集： R3=， R4=， ， 都是A上的二元关系 AA， ， ， AB的子集：R1= ， R2=， ， 都是A到B上的二元关系 |A|=n， AA的子集有2n2个，每个子集代表一个A上的 关系， 所以A上有2n2个不同的二元关系。 A上的3种特殊的关系 空关系： 空集 全域关系:EA= AA 恒等关系:IA=x，x| x A 例：集合A0,1 为A上的空关系 EA ， ， ， 为A上的全域关系 IA ， 为A上的恒等关系 AA， ， ， 其它一些常见关系: 设A为实数集R的某个子集，则A上小于等 于关系定义为: LA=x，y| x，y Axy 例如： A=-1 ，3， 4，则 A上小于等于关系 LA= -1，-1,-1，3,-1，4, 3，3,3，4，4，4 设B为实数集Z+的某个子集，则B上整除关 系定义为: DB=x，y| x，y B x|y 例：B=1，2，3，6，则 B上整除关系DB= 1,1,1,2,1,3,1,6, 2,2,2,6, 3,3,3,6, 6,6 集合A的幂集P(A)上的包含关系： R=x，y| x，y P(A) x y 例:设A=a，b，则有: P(A)=, a，b，A R=, , , 2、关系的表示方法 集合表示法 关系矩阵法（A是有穷集时） 设A=x1，x2，xn， B=y1，y2，ym， R是A到B的关系，则R的关系矩阵是MR=（rij)n*m, 其中 rij= 1 若 R rij= 0 若 R （i=1,n;j=1m） MR= 例:A=1,2,3,4,B=a,b,c，A到B的关系 R=, R的关系矩阵: 1 11 1 1 例:A=1,2,3,4,B=a,b,c，A到B的关系 R=, R的关系矩阵: 例:A=1,2,3,4,A上的关系 R=, R的关系矩阵: 关系图法（A是有穷集时） 集合A=x1，x2，xn， B=y1，y2，ym， R是A到B上的关系。 首先在平面上画上n个结点分别代表x1，xn， 再画上m个结点分别代表y1，y2，ym。 如果 R ，则在xi到yj之间画上一 条从xi指向 yj的带箭头的直线 。 这样得到的图就是R的关系图。 例:A=1,2,3,4,B=a,b,c，A到B的关系 R=, R的关系图: A上关系R的关系图： 集合A=x1，x2，xn，R是A上的关系 首先在平面上画上n个结点分别代表x1，xn， 如果 R ，则在xi到xj之间画上一 条从xi指向 yj的有向边 。 这样得到的图就是R的关系图。 例如：设 A=1，2，3，4, A 上的关系 R=1,1,1,2,2,3,2,4, 4,2 R的关系图: 课堂练习： 集合A=1，2，3 写出A上的恒等关系，全域关系，小于等于 关系，整除关系，并画出关系图 4.2关系的运算 本节学习与关系有关的各种运算: 域 关系的逆、关系的合成 关系的幂 1.域 定义（域）关系R的定义域domR，值域 ranR和域fldR分别是: domR = x | y（x，y R） ranR = y | x（x，y R） fldR = domR ranR 例: 下列关系都是整数Z上的关系，分别求 出它们的定义域和值域 R1=x，y | x，y Zxy R2=x，y | x，y Zy=2x R3=x，y | x，y Z|x|=|y|=3 解: DomR1= RanR1=Z DomR2= Z,RanR2=（2z | z Z），即偶 数集 DomR3= RanR3=-3，3 2. 关系的逆、合成 定义： 设F，G为集合A上任意的关系， 则F的逆记作F-1，F-1=x，y| yFx F与G的合成记作FG， FG=x，y| z（xGzzFy） 例:设A=1，2，3，4，5， A上关系 R, , S, 求R-1, RS, SR 。 解: R-1 , RS , SR , 例: 设F，G是N上的关系，其定义为 F=x，y| x，y N y=x2 G=x，y| x，y N y=x+1 求G-1，FG，GF。 解 : G-1=y，x| y，x N y=x+1 =x，y| y，x N x=y+1 =x，y| y，x N y=x-1 =1，0，2，1， ，x+1，x