离散数学与4.1-2 .ppt

第4章 二元关系与函数 4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数 4.1 集合的笛卡儿积和二元关系 有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示 有序对 定义 由两个元素 x 和 y（允许 x=y），按照一定的顺序组成的二元组称为有序对（也称序偶），记作x,y，其中x是它的第一元素,y是它的第二元素。 实例：点的直角坐标(3,?4) 注:有序对是讲究次序的,例＜1,3＞和＜3,1＞是表示平面上两个不同的点,这与集合不同,{1,3}和{3,1}是两个相等的集合。从而有两个性质。 有序对性质 有序对性质 有序性 x,y?y,x （当x? y时） x,y 与 u,v 相等的充分必要条件是 x,y=u,v ? x=u ? y=v 例1 2, x+5 = 3y? 4, y，求 x, y. 解 3y? 4 = 2, x+5 = y ? y = 2, x = ? 3 有序 n 元组 定义 一个有序 n (n?3) 元组 x1, x2, …, xn 是一个 有序对，其中第一个元素是一个有序 n-1元组，即 x1, x2, …, xn = x1, x2, …, xn-1, xn 当 n=1时, x 形式上可以看成有序 1 元组. 有序 n 元组 定义：由n个元素x1,x2…xn按给定顺序排列组成的n元组合称为一个n元有序组,记作＜x1…xn＞,其中xi称为它的第i元素,i=1,…n。 同样＜x1…xn＞=＜y1…yn＞的充要条件是xi=yi,i=1,…n。 实例 n 维向量是有序 n元组. 关系数据库中表的结构也是一个N元组 笛卡儿积 笛卡儿积 例1，设集合A={a,b,c},B={0,1},求A×B，B×A，A×A,（A×B）? B×A， 解：A×B={a,0,a,1,b,0,b,1,c,0,c,1} B×A ={0,a,1,a,0,b,1,b,0,c,1,c} 显然（A×B）? B×A=? A×A ={a,a,a,b,a,c,b,a,b,b,b,c,c,a,c,b,c,c} 笛卡儿积 例2 A={1,2,3}, B={a,b,c} A?B ={1,a,1,b,1,c,2,a,2,b,2,c, 3,a,3,b,3,c} B?A ={a,1,b,1,c,1,a,2,b,2,c,2, a,3, b,3,c,3} A={?}, P(A)?A={?,?, {?},?} 笛卡儿积 例3：设A={x?1≤x≤2,x∈R} B={y?y≥0,y∈R} 求A?B，B?A 解：A?B={x,y?1≤x≤2, y≥0, y∈R} B?A={x,y?x≥0, 1≤y≤2,x, y∈R} 笛卡儿积 A?B,B?A分别表示平面直角坐标系中的某一个区域（类的集合）, 当A=B时A?B可以记作A2。 笛卡儿积的性质 说明:1 如A，B均是有限集，?A?=m,?B?=n，则必有?A?B?=mn 2 若x,y?A ?B，则有x ?A 和y ?B.若x,y? A ?B,则有x ? A 或者y ? B 笛卡儿积的性质 笛卡儿积的性质 若A或B中有一个为空集，则A?B就是空集. A??=??B=? 若|A|=m, |B|=n, 则 |A?B|=mn 性质的证明 性质的证明 A?（B?C）=（A?B）?（A?C） 证明：?a,b?A?(B?C) 则a?A,b?B?C 即a?A,b?B,且b?c,即a,b?A?B且a,b?A?C ?a,b?(A?B)?(A?C) ?A?(B?C)?(A?B)?(A?C) ?a,b?(A?B)?(A?C) 则a,b?A?B且a,b?A?C 则a?A,b?B,且a?A,b?C,则b?B?C ?a,b?A?(B?C) ?(A?B)?(A?C)?A?(B?C) 由上两条?A?（B?C）?（A?B）?（A?C） 例题 例题 例4 设A={1,2}，求P(A) ?A 解：P(A) ?A ={?,{1},{2},{1,2}} ?{1,2} ={?,1, ?,2,{1},1,{1},2,{2},1{2},2,{1,2},1},{1,2},2} 例题 (4）(A?B) × (C?D) =(A ×C) ? (B×D) 解：成立。因为对任意的x,y, x,y? (A?B) × (