集合论总复习习题课件.ppt

1、集合论总复习集合论总复习习题习题第二十一讲第二十一讲 作业讲评 P86 3-1.(9) 设某集合有101个元素，试问： a) 可构成多少个子集？ b) 其中有多少个子集元素为奇数？ c) 是否有102个元素的子集？ 解：a) 可构成2101个子集 b) 有2100个子集元素为奇数 c) 不能有102个元素的子集 (10)设设S = a1, a2, ., a8, 由由B17 和和B31所表示的所表示的S的子集的子集各是什么各是什么? 应如何表示子集应如何表示子集a1, a8 ,a2, a6 ,a7和和 a3, a8, a7? B17 = B00010001 = a4, a8B31 = B0001

2、1111 = a4, a5, a6, a7 , a8a1, a8 = B10000001 = B129a3, a7 ,a8 = B00100011 = B35 a2, a6 ,a7 = B01000110 = B70 作业讲评 P86 3-1.(10) 解：解：S有有28 = 256个不同的子集个不同的子集, 可表示为可表示为B0, B1, B2, B3, , B255, 二进制二进制下标有下标有8位位.a)证明证明 (1) A(B C) = (AB) (AC)证明证明: (AB) (AC) = (AB) (AC)(AC)(AB)= (AB)(AC)(AC)(AB)= (AB)C)(AC)B)

3、= A(BC)(CB) = A(B C) 作业讲评 P95 3-2.(11) 作业讲评 P95 3-2.(11)a)证明证明 (1) A(B C) = (AB) (AC) 证明证明: (AB) (AC) = (AB) (AC)(AC) (AB)= (A(B C)(A(C B)= A(B C)(C B)= A(B C)注意：注意： A(BC)(AB)(AC) (2) A(B C) = (AB) (AC) 不一定成立。不一定成立。证明证明: 设设 A = 2, 3, B = 1, 4, 7, C = 3, 5, 则则 B C = 1, 3, 4, 5, 7 所以所以 A(B C) = 1, 2,

4、3, 4, 5, 7 但但 AB = 1, 2, 3, 4, 7 AC = 2, 3, 5 故故 (AB) (AC) = 1, 4, 5, 7 因此因此A(B C) = (AB) (AC) 不一定成立。不一定成立。作业讲评作业讲评 P105 3-4.(3)c) (A B) (C D) = (A C) (B D) 解解: 不成立。不成立。 设设A=B，C和和D 则左边则左边=，右边右边 作业讲评 P105 3-4.(3)e)证明证明 (1) ( A B ) C = (A C) (B C)证明证明: 对于任意的对于任意的 (A B) C x (A B) y C( x A x B) (x A x B

5、) y C( x Ax B)y C) (x Ax B) y C)( (A C) (B C) ) ( (A C) (B C) ) (A C) (B C) )作业讲评 P105 3-4.(3)e)证明证明 (1) ( A B ) C = (A C) (B C)证明证明: ( A B ) C = (A-B)(B-A) C= (A-B) C) (B-A) C)= ( (A C) -(B C) ) ( (B C )- (A C) )= (A C) (B C)注意：注意：A (B * C) = (A B) * (A C) (B * C) A = (B A) * (C A) *代表代表, 或或运算运算作业讲

6、评 P105 3-4. (5)(5)证明证明 若若X Y = X Z，且，且X 则则Y=Z证明：证明：1) Y= , 则则X Y= , 故故 X Z = Z = ， Y=Z y Z YZ 同理同理Y Z Y= Z 2) Y , 任意任意y Y， 令令x X， 由已知有由已知有 X Y= X Z作业讲评(5)证明证明 若若X Y = X Z，且，且X 则则Y=Z证明：证明： X Y = X Z且且X X Y X Z 且且X Z X Y YZ且且Y Z Y= Z(1)A B的充分必要条件是的充分必要条件是A C B C;(2) A B的充分必要条件是的充分必要条件是C A C BC是是非空非空集合

7、集合。作业讲评 补充题 90名学生，55人参加数学小组，44人参加语文小组，33人参加体育小组。36人参加数学和语文小组，29人参加数学和体育小组，25人参加语文和体育小组。问多少人3个小组都没有参加？1. |AB| |A| + |B|2. |AB| min(|A|, |B|)3. |A B| |A| |B|4. |A B| = |A| + |B| 2|AB|作业讲评 P113 3-6.(3) 举出A=1,2,3上的关系R的例子，使它有以下性质： a) 既是对称又是反对称的 b) 既不是对称又不是反对称的 c) R是可传递的 解: a) R IA ，如R = b) 部分对称, 如R=, , c

8、) R=, , , 作业讲评 P113 3-6. (6) (6)设R是X上的自反关系。 证明R是对称和传递的,当且仅当a,b和在R中时，则有在R之中。 任意元素a,b,c,若aRb, 由自反性得有aRa, 于是有bRa, 故R是对称的；若有aRb且bRc, 由对称性得到 bRa, 于是有bRa 且bRc, 故有aRc,故R传递 作业讲评 P113 3-6. (6) (6)设R是X上的自反关系。 证明R是对称和传递的,当且仅当a,b和在R中时，则有在R之中。必要性：因为R为X上的等价关系， 所以具有自反性、对称性和传递性。 对于集合X上的任意元素a,b,c，若 aRb 且aRc,由对称性得：bR

9、a，再由传递性得 bRc。作业讲评 P119 3-7. (3)令令S S，存在y使S且SS是传递的 SS S S 设S为X上的关系，证明S是自反的和传递的，则 ，其逆为真吗？SSS令令S，由自反性知S S SS S S 其逆不真。例如X=1，2，3，S= ，, S S = S,但S不是自反的。 作业讲评 A relation R on a set A is called circular if aRb and bRc imply cRa. Show that R is reflexive and circular if and only if it is an equivalence rela

10、tion.必要性：R是自反和循环的R是等价关系令RR是循环的 R R对称令, R，R是对称的 R R传递R是自反的 RR是循环的 R 集合A上的关系R，如果aRb且bRc蕴含cRa，那么就称R是循环的。 证明：R是自反和循环的当且仅当R是等价关系作业讲评 A relation R on a set A is called circular if aRb and bRc imply cRa. Show that R is reflexive and circular if and only if it is an equivalence relation.充分性令, R，R是对称的 R R循环R

11、是等价关系 R是自反,传递,对称的R是传递的 RR是等价关系R是自反和循环的作业讲评 Let S = 1,2,3,4 and let A = SS. Define the following relation R on A: R if and only if a+d=b+c. (1) Show that R is an equivalence relation. (2) Compute A/R即证：R是自反，对称，传递的a, bS，则Aa+b = b+a R自反令R ，即a+d=b+ca+f=b+e R R传递 c + b= d + a R对称 R令 R ， R 即a+d=b+c，c+f=d+

12、eR作业讲评 Let S = 1,2,3,4 and let A = SS. Define the following relation R on A: R if and only if a+d=b+c. (1) Show that R is an equivalence relation. (2) Compute A/R,A=, , , , , , , , , , , , , R=, , , , , , , , , , , , , , , , , ，, , 作业讲评 Let S = 1,2,3,4 and let A = SS. Define the following relation R

13、 on A: R if and only if a+d=b+c. (1) Show that R is an equivalence relation. (2) Compute A/RA/R=, , , , , , ,A=, , , , , ,作业讲评 P146 3-12 (6) (6) 设集合P=x1, x2, x3, x4, x5,上的偏序关系如图所示。 找出P的最大(小)元素，极大(小)元素。 找出子集x2, x3, x4x3, x4, x5,x1, x2, x3的上(下)(确)界最大元素x1 , 无最小元素 x5x1x2x3x4极大元素x1 , 极小元素x4, x5 集合上界 下界上确

14、界下确界x2, x3, x4x1x4x1x4x3, x4, x5,x1, x3无x3无x1, x2, x3x1x4x1x4作业讲评 P146 3-12 (7)(7)下图给出了集合1,2,3,4上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。1243(a)先去环再去掉传递最后调整位置1234(a)作业讲评 P146 3-12 (7)(7)下图给出了集合1,2,3,4上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。1234(c)先去环再去掉传递最后调整位置4213作业讲评 补充题设f,g,h是实数集R上的函数，f(x)=x+2, g(x)=x

15、-2, h(x)=3x，求fg、ff、gf、gg、fh、hg、hfg fg (x) = x ff (x) = x+4 gf (x) = x gg (x) = x-4 fh (x) = 3x+2 hg (x) = 3x-6 hfg (x) = h (x) = 3x作业讲评 P151 4-2.(6) (6) 设A和B是有穷集合，有多少不同入射函数和多少不同的双射函数。入射: X中没有两个元素有相同的象(1) f: AB为入射, 必须有|A|B|, 即m n 设|A| = m，|B| = n B中任意选出m个元素的任一全排列即为所求.满射: Y中每一个元素是X中的一个或多个元素的象点。 (2) f:

16、 AB为双射, 必须有|A|=|B|, 即m= n 所以，共有m!个。集合是什么集合是不能精确定义的基本概念集合是不能精确定义的基本概念。如何理解理解集合： 由共同性质的一些对象汇集而成的整体 。 集合可以是有限集有限集，也可以是无限集无限集 集合的表示方法：枚举法枚举法叙述法叙述法（列判别条件）一般用大写字母大写字母表示集合，用小写字母小写字母表示元素 见 课本 P82 集合与元素的关系 集合与元素的关系：x A 或 x A集合元素可以是离散型离散型数据（如整型、逻辑型、枚举型等），也可以是非离散型非离散型数据（如实型）。有限集一定是离散型数据有限集一定是离散型数据，无限集可能是离散型，也可

17、能是非离散型的数据。 本书中默认：自然数集从自然数集从0开始开始（见P94，习题(3)中对自然数N的子集C的定义）集合的概念子集子集：(x)(xx) （B包含A） 真子集真子集： (x)(xx)(x) (xBxA) 空集空集：不包含任何元素的集合 = x | p(x) p(x)， p(x)为任何谓词全集全集：E = x | p(x) p(x)， p(x)为任何谓词集合的相等集合集合A、B相等相等： A = B A , B的元素完全相同 A B且B A ( x , 若xA，则xB ) 且 ( x , 若xB，则xA )集合集合A、B不等不等： AB A , B的元素不完全相同（不是完全不同不是完

18、全不同！) not (A B) 或not (B A ) ( x , xA且x B ) 或 ( x , xB且x A )幂 集幂集幂集的概念： 给定集合A，由集合A的所有子集的所有子集为元素组成的集合，称为集合集合A的幂集的幂集，记为P(A) 。若 |A| = n，则 |P(A)| = 2n如何证明如何证明?注意注意 P()=区别： , 但 , 。 A=B P(A) = P(B) A B P(A) P(B)证明证明 A B当且仅当当且仅当P(A) P(B) 充分性充分性:对对任意任意x A x P(A) x P(B) x B所以所以A B 必要性必要性:对对任意任意x P(A) x A x B

19、x P(B)所以所以P(A) P(B)集合之间的关系子集子集：A包含B B包含于A真子集真子集：相等相等：A 、B的元素完全相同不等不等：A 、B的元素不完全相同从属从属：（一个集合是另外一个集合的元素）空集的性质空集是一切集合的子集。空集是一切集合的子集。空集是惟一的。空集是惟一的。空集是任何集合的幂集的元素。空集是任何集合的幂集的元素。空集的幂集不是空集。空集的幂集不是空集。空集 例题例例 判断下列命题的真假判断下列命题的真假:(1) (2) (3) (4) (2)为假为假; 其余均为真。其余均为真。集合运算的性质交换律交换律 AB = BA AB = BA A B = B A 结合律结合

20、律(AB)C = A(BC) (AB)C = A(BC) (A B) C = A (B C) 注意：注意：AB BA (AB)C A(BC) 集合运算的性质分配律分配律 （注意证明方法是典型的，见P89，P91） A(BC) = ( AB)(AC) A(BC) = ( AB)(AC) A(BC)= (AB)(AC) P91 定理 但：A(BC)(AB)(AC) 例：B = A , C =时 A(B C) = ( AB) (AC) 但：A(B C)(AB) (AC)例：B = C , A 时 集合运算的性质摩根律摩根律 (AB) = A B (AB) = A B A (BC) = (A B)(A

21、 C) A (BC) = (A B)(A C)吸收律吸收律 A(AB) = A = A(AB)其他其他 AB A ABAB B AB证明集合相等的方法往证往证A=B方法一方法一：证明：AB 且 BA （P91定理3-2.5的证明方法）方法二方法二：证明满足A元素的条件逻辑等价于满足B元素的条件 （P91定理3-2.4的证明方法）方法三方法三：使用集合运算的性质（P91定理3-2.6的证明方法）证明集合不等的方法往证 A B： 方法一方法一：举反例AB ( x , xA且x B ) 或 ( x , xB且x A )方法二方法二：说明（或证明）一个是空集（或全集），另一个不是方法三方法三：画文氏图

22、示意证明集合是空集的方法 方法一方法一：其逻辑判断条件是永假 方法二方法二：用反证法：设aA，引出矛盾的结果（见P95习题(10)a) 的证明） 方法三方法三：利用等式，例如：A A= 包含排斥原理AB=A+B-AB ABC=A+B+C -AB-AC-BC +ABC 见P96-99例题1、2、3定义序偶序偶：有序的偶对序偶与集合的区别：有序 / 无序 若若xy，则，则，但，但x,y=y,x序偶与集合的统一： = x,x,y序偶相等的定义：= x=u 且且 y=v集合的笛卡儿乘积集合A、B的笛卡儿乘积 AB = (xA)(yB)见课本P102例题1 笛卡儿乘积的性质 AB BA ABC = (A

23、B)C A(BC) An = AAA (n个A) ABAB AnAn A A 笛卡儿乘积的定理以下定理均可从序偶、集合相等的定义证明：A(BC)(AB)(AC) (BC)A(B A)(CA) A(BC)(AB)(AC) (BC)A(B A)(CA) 若C ，则AB (AC) (BC) (CA CB) 非空集合A,B,C,D, AB CD A C且B D关系的定义关系关系是两个集合的笛卡儿乘积的子集。本质上关系关系R是序偶的集合是序偶的集合：若R则记为xRy若R则记为xRy 集合集合A到到集合集合B的关系的关系：AB的子集集合集合A上上的关系的关系： AA的子集见课本P106 例题1、2、3特殊

24、的关系恒等关系恒等关系 IA x,xxA 是A上的关系全域关系全域关系： RAB 空关系空关系： R定理定理：A到B的两个关系的交、并、差、补仍是A到B的关系 关系的表示集合法集合法： 列举集合的所有元素（序偶）或判别条件叙述法叙述法：叙述关系定义的判别条件；P107 例4 矩阵法矩阵法： A到B的关系用|A|行|B|列的0、1矩阵表示图图： A到到B的关系的关系：用有向偶图表示（点表示集合元素，弧表示序偶） A上的关系上的关系： 用有向图表示（点表示集合元素，弧表示序偶） 关系的性质讨论非空集合A上上的关系R（即RAA） 自反性自反性： aA, a, aR 关系图关系图中每个点都有环 关系矩

25、阵关系矩阵是对角线元素全部为1反自反性反自反性：aA, a, aR 关系图关系图中每个点都没环 关系矩阵关系矩阵是对角线元素全部为0关系的性质对称性对称性： a, b A, 若a, bR，则b, aR 关系图关系图中任意两个不同的点之间要么没有边，要么有双向边；关系矩阵关系矩阵是对称矩阵反对称性反对称性：若ab，则a,bR或b,aR ；或者：a,bA, 若a,bR且b,aR, 则a=b； 关系图关系图任意两个不同的点之间要么没有边，要么只有单向边。 关系矩阵关系矩阵呢？关系的性质传递性传递性： a,b,cA, 若a,bR且b,cR，则a,cR 关系图关系图中任意两个点之间若经过第三点有路接通，

26、则必有直达边; 关系矩阵关系矩阵较复杂 定义复合关系设R是A到B的关系，S是B到C的关系，则R S称为R和S的复合关系复合关系，表示为RS = | xAzC ( y)(yBRS)R表示关系时，表示关系时，Rn表示表示n个关系个关系R的复合的复合复合关系是不可交换的不可交换的（没有公共域）复合关系是可结合的可结合的。定义逆关系设R是A到B的关系， 将R中每一序偶元素顺序互换，得到的集合称为关系R的逆关系逆关系， (inverse relation)表示为 Rc = | R可见， Rc是B到A的关系。逆关系保持了关系的性质逆关系保持了关系的性质 ：即保持了原关系的自反性、反自反性、对称性、反对称性

27、、传递性（若原关系有这些性质的话）。见课本P119习题（5）有关定理证明两个关系相等，实质上是证明两个集合（元素是序偶）相等(R1R2)c = R1cR2c (R1R2)c = R1cR2c(R1-R2)c = R1c-R2c(AB)c = BA( R1R2)c = R2c R1c(R1R2) R3 = R1 (R2 R3) R是对称的 R= RcR是反对称的 RRc Ix 逆关系的性质逆关系的矩阵逆关系的矩阵：原关系矩阵转置之后得到逆关系的矩阵逆关系的图逆关系的图：把弧的方向反转，得到逆关系的图 逆关系逆关系保留了原来关系的自反、反自反、对称、反对称、传递等性质。关系运算后性质的保持 关系运

28、算后性质的保持运算运算性质性质 自反性自反性 反自反性反自反性 对称性对称性反对称性反对称性传递性传递性RS RS R S Rc R S 关系的闭包关系R的自反（对称、传递）闭包： 是指包含R的、而且是自反的、最小的自反（对称、传递）关系 严格的定义：见课本P119如果R本身是自反的（对称的、传递的），则其自反的（对称的、传递的）闭包就是R 自反闭包：reflexive closure对称闭包：symmetric closure传递闭包：transitive closure闭包的讨论自反闭包 r R RIx（R是集合X上的关系）对称闭包 s R RRc 传递闭包 t (R) = RR2Rn 若

29、 |X| = n，则只需前m个（m n）关系的并 rs R sr (R) rt R tr (R) ts R st (R)Warshall算法的实质：简化矩阵运算，此处不要求，“数据结构”课程再讲。定义集合的划分与覆盖A为非空集合，S=S1,S2,Sm，其中（1）SiA，Si(i=1,2,m)（2） S1S2Sm=A（3）当ij时，SiSj= S是是A的覆盖的覆盖S是是A的划分的划分定义的另一种描述：若把集合A分成若干个叫做分块的非空非空子集，使得A中每一个元素至少属于至少属于一个分块，则这些分块的全体叫A的一个覆盖覆盖；若A中每一个元素属于且只属属于且只属于一个分块，则这些分块的全体叫A的一个

30、划分划分（或分划）。习题解答P130习题(5) (1) (Ai B) = (A1 A2 Ak) B = A Bi=1 k (2) (Ai B) (Aj B) = Ai Aj B= 定义等价关系R是集合A上上的关系，满足自反、对称、传递，则R是A上的等价关系。见课本P131 例题1、例题2注意：注意：许多这类题目：给出某些性质，判别许多这类题目：给出某些性质，判别是否等价关系是否等价关系 定义等价类R是A上的等价关系，则等价类 aR xxA且aRx等价类的性质： a, bA 1） aR 且aR A 2） a, bR aR bR 3） a, bR aRbR = 4） aRaA是的一个划分，记为（商

31、集） 划分和等价关系1） 等价关系 - 划分 （P133定理3-10.2，3-10.3）2） R1=R2 A/R1 = A/R2 （P134定理3-10.4）决定定义偏序关系非空集合A上的关系R，满足自反自反、反对称反对称、传递传递的性质，称R是A上的一个偏序关系偏序关系，记为 ： 序偶A, 称作偏序集偏序集。见课本P140例题1、例题2定义“盖住”在偏序集中的两个元素x 和 y 满足以下条件： x y xy x, y之间没有z，使x z 且 z y 则称 y盖住盖住x 见课本P140例题3对于给定的偏序集A,，其盖住关系是确定的、唯一的。哈斯图 Hasse diagram回顾：偏序关系的关系

32、图的特点？哈斯图哈斯图：关系图的简化（省略了自反性、传递性） 使用了“盖住”的性质，作图规则如下：1）每个元素用一个小圆点表示；2）若元素y盖住盖住元素x，则y画在x上方，并用直线连接直线连接；3）若x y且xy，则y画在x之上；若无关系，则两个点可画在同一水平，也可一上一下。作业讲评 P146 3-12 (7)(7)下图给出了集合1,2,3,4上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。1234(c)先去环再去掉传递最后调整位置4213定义链、反链的子集子集称为： 链链：偏序集的每两个元素都有关系；(哈斯图中某条链上的点集) 反链反链：偏序集的每两个元素都没有

33、关系(哈斯图中若干个没关系的点的集合)单个元素的子集，既是链，又是反链（注意：这是约定，不能证明）问：是否存在非链、非反链的关系？ 答：是。如集合2,3,4上的整除关系线序关系在偏序集A,中，如果A是一个链，则称A,为全序集合全序集合或线序集合线序集合，二元关系 称为全序关系全序关系或线序关系线序关系。全序关系全序关系 线序关系线序关系 哈斯图是一条哈斯图是一条“链链”全序关系A,中，x,yA， xy和yx至少有一个成立。A上的线序关系 A上的偏序关系 A上的偏序关系 A上的关系A上的关系 AA AAA上的关系A上的偏序关系A上的等价关系线序关系恒等关系的子集单个元素各概念的相互关系极大元 最

34、大元A,是偏序集合，且B是A的子集，对于B中的某个元素b，若B中没有其他元素没有其他元素x，满足bx，则称b是B的极大元极大元。A,是偏序集合，且B是A的子集，对于B中的某个元素b，若对于B中每个元素每个元素x，满足xb，则称b是B的最大元最大元。上界、上确界A,是偏序集合，且B是A的子集，对于A中的某个元素a，若对于B中每个元素每个元素x，满足xa，则称a是B的上界上界。注意：上界不一定不一定是集合内的点；A,是偏序集合，且B是A的子集， a是B的某一上界，对于B中所有上界所有上界y，满足ay，则称a是B的最小上界，最小上界，或上确界上确界。注意：上确界不一定不一定是集合内的点；良序偏序集合

35、的每个非空子集存在最小元素，则称为良序集良序集。良序集合一定是全序集合（P145定理12.1)良序良序 线序线序 偏序偏序 关系关系 笛卡尔乘积笛卡尔乘积 有限的全序集合一定是良序集合(P145定理12.2)无限的全序集合不一定是良序集合（例如正实数集合上的小于关系，开区间子集没最小元素）定义函数函数函数（也叫映射映射mapping）的定义：f 是集合X到集合Y的一个关系，对于每一个每一个xX，有惟一惟一的yY，使得f，称关系f为函数，记为：f : XY 或 XY y记为f(x)f函数与关系的区别函数与关系的区别: 定义域是整个集合X； 一个 a X 只能对应于惟一的一个yY，使 f(x) =

36、 y；可见: 函数函数 关系关系 笛卡尔乘积笛卡尔乘积解解(1) R1不是函数不是函数, 因为元素因为元素a有有两个不同的像两个不同的像(2) R2不是函数不是函数, 因为因为A中元素中元素c没有像没有像。(3) R3是函数是函数, 函数的定义允许函数的定义允许多个元素共有一个多个元素共有一个像像例 题设设A = a, b, c, B = 0, 1, 判别下列二元关判别下列二元关系中哪个是函数？系中哪个是函数？(1) R1 = a, 0, a, 1, b, 0, c, 1。(2) R2 = a, 0, b, 1。 (3) R 3= a, 0, b, 1, c, 1。例 题 证明证明 因为任一函

37、数因为任一函数f 是由是由A中中n 个元素的个元素的取值所取值所唯一确定唯一确定的的, A中的任一元素中的任一元素a, f 在在a处的取值都有处的取值都有m种可能种可能, 所以所以A到到B可以可以定义定义 mmm = mn = |B| |A|个不同的函数个不同的函数。设设| A | = n, | B | = m ，X到到Y有多少个不同有多少个不同的函数？的函数？习题解答 P151 4-1 (2)令 f : AB，已知CA，证明：f(A)-f(C) f(A-C)证明：任意任意y f(A)-f(C), x A, f(x)=y 对于 zC，y f(z)，即 x z 因此 x A-C 故 y = f(

38、x) f(A-C) 于是有：f(A)-f(C) f(A-C)习题解答 P151 4-1 (3) 假设 f 和g是函数，且有fg和dom g dom f ，证明 f = g 。 证明： g ，有a dom g dom f 故 a dom f ， 有 f g ， 即 g 由于g是函数，因此a有惟一像点，于是有： = = f 因此 g f 已知fg ，得到f = g习题解答 P151 4-1 (3)假设 f 和g是函数，且有fg和dom g dom f ，证明 f = g 。 证明：用反证法：用反证法：设设f g，由已知fg得 g，但，但 f由由 g ，得a dom g dom f 故 a dom

39、f ，有 f g，即 g，由于g是函数，因此a有惟一像点，于是有： = = f 与题设矛盾。与题设矛盾。因此 f = g满射、入射(单射)、双射函数 f : XY满射满射：yY，xX，使得f(x)=y；入射入射：x1,x2X，x1x2 f(x1)f(x2)；双射双射：既是入射又是满射，也叫一一对应一一对应 入射入射入射入射入射入射入射入射逆函数inverse function问：函数的逆关系一定是函数吗？答：只有双射才有逆函数只有双射才有逆函数双射函数 f : XY逆函数 f 1 : YX(f 1 ) 1 = f 反函数反函数即逆函数复合函数composite function函数 f : X

40、Y ，g : WZ若 f ( X ) W ， 则：g f = | xXzZ (y)(yYy=f(x)z=g(y) 称函数函数g在函数在函数f 的左边可复合的左边可复合。设R是A到B的关系，S是B到C的关系，则R S称为R和S的复合关系复合关系，表示为RS = | xAzC ( y)(yBRS)比较复合关系：1. 证明: 任意集合A、B, P(A)P(B)= (AB)2. 证明:任意集合A、B, P(A)P(B) P(AB)3. 任意集合A、B, P(A-B) 是否等于 P(A)-P(B)？4. 对任意集合A、B、C, 已知AC BC, A-C B-C 证明: A B （提示：参考课本P89例题

41、2结论）补充习题补充习题5. R1、R2是非空集合A上的等价关系。问：R1R2、R1R2还是A上的等价关系吗？6. 画出54因子集合上整除关系的哈斯图；画出1,2,3,4,6,9,12,18,36上整除关系的哈斯图7. 下列关系中哪些能够构成函数？1)、f = | x,yR且x = y2 2)、g = | x,yN且y为小于x的素数个数3)、f = | x,yN且x+y10 4)、g = | x,yR且y = x2 补充习题证明： 对任意集合A、B，P(A)P(B) = P(AB)证明： 对任意集合A、B，P(A)P(B) P(AB)对任意集合A、B， P(A-B) 是否等于 P(A)-P(B

42、)？ 证明证明 P(AB) = P(A)P(B)证明：证明：对对任意任意x P(AB)x ABx A x B x P(A) x P(B) x P(A)P(B)所以所以 P(AB) = P(A)P(B)证明证明 对任意对任意x P(A)P(B) x P(A)x P(B) x Ax B x AB x P(AB)所以所以P(A)P(B) P(AB)； 当当A B时时, P(A) P(B)； AB = B, P(A)P(B) = P(AB) 证明证明 P(A)P(B) P(AB)补充习题对任意集合A、B、C，已知AC BC， A-C B-C证明： A B提示：参考课本P89例题2结论补充习题R1、R2

43、是非空集合A上的等价关系，问：R1R2、R1R2还是A上的等价关系吗？R1R2还是A上的等价关系，因为交运算依然保持了其自反, 对称, 传递性。R1R2不是A上的等价关系，不一定传递补充习题画出54因子集合上整除关系的哈斯图；画出1,2,3,4,6,9,12,18,36上整除关系的哈斯图121861429336补充习题下列关系中哪些能够构成函数？1、f = | x,yR且x = y2 2、g = | x,yN且y为小于x的素数个数3、f = | x,yN且x+y10 4、g = | x,yR且y = x2 解解1. f不能构成函数不能构成函数,存在存在x在在Y上有两个元素与之对应上有两个元素与之对应 2. g构成函数构成函数 3.由于由于f 仅涉及仅涉及N中的元素中的元素0, 1, 2, 9，而，而其它元素没其它元素没有像有像, 所以所以f 不是不是N上的函数。上的函数。 4. g构成函数构成函数