离散数学 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, , ，,这是人的集合甲，乙，丙到工作的集合a，b，c，d之间的关系。 l除了二元关系以外还有多元关系本书只讨论二元关系。以后凡是出现关系的地方均指二元关系下面给出二元关系的一般定义l定义（二元关系）如果一个集合为空集或它的元素都是有序对，则称这个集合是一个二元关系，一般记作R。 对于二元关系R，如果x，y R，则记作xRy。l设A，B为集合，AB的任何子集所定义的二元关系称作从A到B的二元关系，特别当A=B时，则叫做A上的二元关系。例：集合A0,1，B2,3AB， ， ， AA的子集： R3=， R4=， ， 都是A上的二元关系AA， ， ， AB的子集：R1= ， R2=， ， 都是A到B上的二元关系l|A|=n，AA的子集有2n2个，每个子集代表一个A上的 关系，所以A上有2n2个不同的二元关系。lA上的3种特殊的关系空关系： 空集全域关系:EA= AA恒等关系:IA=x，x| x A例：集合A0,1为A上的空关系 EA ， ， ， 为A上的全域关系 IA ， 为A上的恒等关系AA， ， ， 其它一些常见关系:l设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，4l设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，AR=, , 2、关系的表示方法集合表示法关系矩阵法（A是有穷集时）设A=x1，x2，xn， B=y1，y2，ym， R是A到B的关系，则R的关系矩阵是MR=（rij)n*m,其中rij= 1 若 Rrij= 0 若 R （i=1,n;j=1m）MR=例:A=1,2,3,4,B=a,b,c，A到B的关系 R=,R的关系矩阵:1 111 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,2R的关系图:课堂练习：集合A=1，2，3写出A上的恒等关系，全域关系，小于等于 关系，整除关系，并画出关系图Q & A36