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, , , ， ，2，2， 1，2，1,1，2，2,定义 (n阶笛卡儿积) 设A1, A2, An是n个集合(n2)。 它们的n阶笛卡儿积 A1 A2 An =x1,x2,xn|x1A1x2A2xnAn 当A1 = A2 = An = A时，可将它们的n阶笛卡儿积 简记为An 例如，A=a，b，则 A3=a，a，a，a，a，b，a，b，a， a，b，b，b，a，a，b，a，b， b，b，a，b，b，b,关系及其表示,什么是关系 关系的表示,所谓二元关系就是在集合中两个元素之间的某种相关性 例如：甲、乙、丙三人进行乒乓球比赛，如果任何两人之间都要赛一场，那么共要赛三场。假设三场比赛的结果是乙胜甲，甲胜丙，乙胜丙，这个结果可以记作 乙，甲，甲，丙，乙，丙 其中x，y表示x胜y。 它表示了集合甲、乙、丙中元素之间的一种胜负关系,1、什么是关系,再例如，有甲，乙，丙三个人和四项工作a，b，c，d。 已知甲可以从事工作a和b，乙可以从事工作c，丙可以从事工作a和d。 那么人和工作之间的对应关系可以记作 R=, 这是人的集合甲，乙，丙到工作的集合a，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,1,1,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之间