离散数学第五版第四章(耿素云、屈婉玲、张立昂编著).ppt

4.7 函数的复合与反函数 一、函数的复合定理（定理4.6） dom(F?G)={x|x?domG ? G(x)?domF}； ?x?dom(F?G) 有F?G(x)=F(G(x)) ； 设F,G是函数，则F?G也是函数，且满足 4.7函数的复合与反函数 二、函数复合的结合律（推论） 设f:A?B,g:B?C,则f?g：A?C，且?x?A都有 f?g(x)=f(g(x))。 4.7函数的复合与反函数 三、函数复合的性质（定理4.7） 设f:B?C,g:A?B。 (1)如果f，g都是满射的，则f?g:A?C也是满射的。 (2)如果f，g都是单射的，则f?g:A?C也是单射的。 (3)如果f，g都是双射的，则f?g:A?C也是双射的。 4.7函数的复合与反函数 四、反函数（定理4.8） 设f:A?B是双射的，则有 是函数，并且是双射函数。 五、反函数的性质 设f:A?B是双射的，则有 f-1?f=IA,f?f-1=IB 4.7函数的复合与反函数 例7：设 求f ? g，g ? f。如果f和g存在反函数，求出它们的反函数。 * 4.4关系的闭包 三、关系闭包的性质(3) ； ； 。 设R是非空集合A上的关系，则 4.4关系的闭包 三、关系闭包的性质(4) r(s(R))=s(r(R))。 r(t(R))=t(r(R))。 s(t(R))?t(s(R))。 设R是非空集合A上的关系，则 第四章 二元关系和函数 4.1 迪卡尔乘积与二元关系 4.2 二元运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义与性质 4.7 函数的复合与反函数 4.5等价关系与偏序关系 一、等价关系的定义 设R为非空集合A上的关系，如果R是自反的、对称的、 传递的，则称R为A上的等价关系。对任何x,y?A，如果 x,y?等价关系R，则记作x?y。 4.5等价关系与偏序关系 例4：A={1,2,3,?,8},R={x,y|x,y?A ? x?y(mod 3)}, 其中x?y(mod 3)的含义就是x-y可以被3整除。求证：R 是否为等价关系？ 5 8 2 4 7 1 6 3 对任何正整数n可以定义整数集合Z上模n的等价关系： R={x,y|x,y?Z ? x?y(mod n)} 4.5等价关系与偏序关系 例5: 在一群人的集合上，年龄相等的关系、朋友关系。 动物是按种属分类的，“具有相同种属”的关系。 集合上的恒等关系。 在同一平面上，三角形之间的相似关系。 在同一平面上，直线间的平行关系。 4.5等价关系与偏序关系 二、等价类的定义 设R是非空集合A上的等价关系，对任意的x?A，令 [x]R={y|y?A ? xRy}, 则称[x]R为x关于R的等价类，简称为x的等价类，简记为[x]。 集合A={1,2,3,?,8},R={x,y|x,y?A ? x?y(mod 3)}中的 等价类有：[1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6} 4.5等价关系与偏序关系 三、等价关系、等价类的性质 [x]??，且[x]?A; 若xRy，则[x]=[y]; 若x，y?R，则[x]?[y]=?; ; 4.5等价关系与偏序关系 四、商集的定义 设R是非空集合A上的等价关系，以R的不交的等价类为元素的 集合叫做A在R下的商集，记作A/R，即 A/R={[x]R|x?A}。 集合A={1,2,3,?,8},R={x,y|x,y?A ? x?y(mod 3)}，则 A在R下的商集是： A/R=｛{1,4,7}，{2,5,8}，{3,6}} 4.5等价关系与偏序关系 例6: 非空集合A上的全域关系EA是A上的等价关系，对任意x?A 有[x]= ,商集A/EA= 非空集合A上的恒等关系IA是A上的等价关系，对任意x?A 有[x]= ,商集A/EA= 。 4.5等价关系与偏序关系 五、划分的定义 设A是非空集合，如果存在一个A的子集族?(??P(A))满足以下 条件： ???， ?中任意两个元素不交， ?中所有元素的并集等于A， 则称?为A的一个划分，且称?中的元素为划分块。 4.5等价关系与偏序关系 例7:考虑集合A={a,b,c,d}的下列子集族，哪些是A的划分 {{a},{b,c},{d}} {{a,b,c,d}} {{a,b},{c},{a,d}} {?,{a,b},