集合论总复习习题

集合论总复习

习题第二十一讲1作业讲评P863-1.(9)

设某集合有101个元素，试问：

a)可构成多少个子集？

b)其中有多少个子集元素为奇数？

c)是否有102个元素的子集？解：a)可构成2101个子集

b)有2100个子集元素为奇数

c)不能有102个元素的子集2

(10)设S={a1,a2,...,a8},由B17和B31所表示的S的子集各是什么?应如何表示子集{a1,a8},{a2,a6,a7}和

{a3,a8,a7}?

B17=B00010001={a4,a8} B31=B00011111={a4,a5,a6,a7,a8} {a1,a8}=B10000001=B129 {a3,a7,a8}=B00100011=B35{a2,a6,a7}=B01000110=B70作业讲评P863-1.(10)解：S有28=256个不同的子集,可表示为B0,B1,B2,B3,…,B255,二进制下标有8位.3a)证明(1)A∩(BC)=(A∩B)(A∩C)证明:(A∩B)(A∩C)=((A∩B)∩~(A∩C))∪((A∩C)∩~(A∩B))=((A∩B)∩(~A∪~C))∪((A∩C)∩(~A∪~B))=((A∩B)∩~C))∪((A∩C)∩~B))=A∩((B∩~C)∪(C∩~B))

=A∩(BC)作业讲评P953-2.(11)4作业讲评P953-2.(11)a)证明(1)A∩(BC)=(A∩B)(A∩C)证明:(A∩B)(A∩C)=((A∩B)–(A∩C))∪((A∩C)–(A∩B))=(A∩(B–C))∪(A∩(C–B))=A∩((B–C)∪(C–B))=A∩(BC)注意：

A∪(B―C)≠(A∪B)―(A∪C)5(2)A∪(BC)=(A∪B)(A∪C)不一定成立。证明:设A={2,3},B={1,4,7},C={3,5},

则BC={1,3,4,5,7}

所以A∪(BC)={1,2,3,4,5,7}

但A∪B={1,2,3,4,7} A∪C={2,3,5}

故(A∪B)(A∪C)={1,4,5,7}

因此A∪(BC)=(A∪B)(A∪C)不一定成立。作业讲评6作业讲评P1053-4.(3)c)(AB)(CD)=(AC)(BD)解:不成立。

设A=B，C和D≠

则左边=，右边≠7作业讲评P1053-4.(3)e)证明(1)(AB)C=(AC)(BC)证明:对于任意的<x,y>

(AB)Cx(AB)∧yC((xA∧xB)∨(xA∧xB))∧yC((xA∧xB)∧y

C)∨((xA∧x

B))∧yC)(<x,y>(AC)∧<x,y>(BC))∨(<x,y>(AC)∧<x,y>(BC))<x,y>(AC)(BC))8作业讲评P1053-4.(3)e)证明(1)(AB)C=(AC)(BC)证明:(AB)C=((A-B)∪(B-A))C=((A-B)C)∪(B-A))C)=((AC)-(BC))∪((BC)-

(AC))=(AC)(BC)注意：A(B*C)=(AB)*(AC)(B*C)A=(BA)*(CA)*代表∪,∩或–运算9作业讲评P1053-4.(5)(5)证明若XY=XZ，且X≠

则Y=Z证明：1)Y=,则XY=,故

XZ=∴Z=，∴Y=Z∴yZ∴YZ

同理YZ∴

Y=Z

2)Y≠,任意yY，令xX，由已知有<x,y>XY=XZ10作业讲评(5)证明若XY=XZ，且X≠

则Y=Z证明：∵XY=XZ且X≠

∴XYXZ

且XZXY∴YZ且YZ∴

Y=Z(1)AB的充分必要条件是ACBC;(2)AB的充分必要条件是CACBC是非空集合。11作业讲评补充题90名学生，55人参加数学小组，44人参加语文小组，33人参加体育小组。36人参加数学和语文小组，29人参加数学和体育小组，25人参加语文和体育小组。问多少人3个小组都没有参加？1.|A∪B|≤|A|+|B|2.|A∩B|≤min(|A|,|B|)3.|A–B|≥|A|–|B|4.|AB|=|A|+|B|–2|A∩B|12作业讲评P1133-6.(3)举出A={1,2,3}上的关系R的例子，使它有以下性质：

a)既是对称又是反对称的

b)既不是对称又不是反对称的

c)R是可传递的解:a)RIA，如R={<1,1>}

b)部分对称,如R={<1,2>,<2,1>,<1,3>}

c)R={<1,2>,<2,1>,<1,1>,<2,2>}13作业讲评P1133-6.(6)(6)设R是X上的自反关系。证明R是对称和传递的,当且仅当＜a,b>和<a,c>在R中时，则有<b,c>在R之中。任意元素a,b,c,若aRb,

由自反性得有aRa,

于是有bRa,

故R是对称的；若有aRb且bRc,由对称性得到bRa,

于是有bRa

且bRc,

故有aRc,故R传递14作业讲评P1133-6.(6)(6)设R是X上的自反关系。证明R是对称和传递的,当且仅当＜a,b>和<a,c>在R中时，则有<b,c>在R之中。必要性：因为R为X上的等价关系，所以具有自反性、对称性和传递性。对于集合X上的任意元素a,b,c，若aRb

且aRc,由对称性得：bRa，再由传递性得bRc。15作业讲评P1193-7.(3)令<x,z>SS，存在y使<x,y>S且<y,z>S∵S是传递的∴<x,z>S∴SSS设S为X上的关系，证明S是自反的和传递的，则，其逆为真吗？令<x,y>S，由自反性知<y,y>S∴<x,y>SS∴SSS

其逆不真。例如X={1，2，3}，S={<1,2>，<2,2>，<1,1>},SS=S,但S不是自反的。

16作业讲评ArelationRonasetAiscalledcircularifaRbandbRcimplycRa.ShowthatRisreflexiveandcircularifandonlyifitisanequivalencerelation.必要性：R是自反和循环的R是等价关系令<a,b>R∵R是循环的∴<b,a>R∴R对称令<a,b>,<b,c>R，∵R是对称的∴<a,c>R∴R传递∵R是自反的∴<b,b>R∵R是循环的∴<c,a>R集合A上的关系R，如果aRb且bRc蕴含cRa，那么就称R是循环的。证明：R是自反和循环的当且仅当R是等价关系17作业讲评ArelationRonasetAiscalledcircularifaRbandbRcimplycRa.ShowthatRisreflexiveandcircularifandonlyifitisanequivalencerelation.充分性令<a,b>,<b,c>R，∵R是对称的∴<c,a>R∴R循环∵R是等价关系∴R是自反,传递,对称的∵R是传递的∴<a,c>RR是等价关系R是自反和循环的18作业讲评LetS={1,2,3,4}andletA=SS.DefinethefollowingrelationRonA:<a,b>R<c,d>ifandonlyifa+d=b+c.(1)ShowthatRisanequivalencerelation.(2)ComputeA/R即证：R是自反，对称，传递的⑴a,bS，则<a,b>A∵a+b=b+a∴R自反⑵令<a,b>R<c,d>，即a+d=b+c∴a+f=b+e∴<a,b>R<e,f>∴R传递∴c+b=d+a∴R对称∴<a,b>R<a,b>⑶令<a,b>R<c,d>，<c,d>R<e,f>

即a+d=b+c，c+f=d+e∴<c,d>R<a,b>19作业讲评LetS={1,2,3,4}andletA=SS.DefinethefollowingrelationRonA:<a,b>R<c,d>ifandonlyifa+d=b+c.(1)ShowthatRisanequivalencerelation.(2)ComputeA/R<1,1>,A={<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>R={<<1,1>,<2,2>>,<<1,1>,<3,3>>,<<1,1>,<1,1>>,<<1,1>,<4,4>>,<<1,2>,<1,2>>,<<1,2>,<2,3>>,<<1,2>,<3,4>>,<<1,3>,<1,3>>,<<1,4>,<1,4>>,<<2,1>,<3,2>>,<<2,1>,<2,1>>,<<2,1>,<4,3>>,<<3,1>,<3,1>>,<<3,1>,<4,2>>，<<1,3>,<2,4>>,<<4,1>,<4,1>>}}20作业讲评LetS={1,2,3,4}andletA=SS.DefinethefollowingrelationRonA:<a,b>R<c,d>ifandonlyifa+d=b+c.(1)ShowthatRisanequivalencerelation.(2)ComputeA/RA/R={{<1,1>,<2,2>,<3,3>,<4,4>},{<1,2>,<2,3>,<3,4>},{<4,3>,<3,2>,<2,1>},

{<1,3>,<2,4>},{<3,1>,<4,2>},

{<1,4>},{<4,1>}}A={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}21作业讲评

P1463-12(6)(6)设集合P={x1,x2,x3,x4,x5,}上的偏序关系如图所示。找出P的最大(小)元素，极大(小)元素。找出子集{x2,x3,x4}{x3,x4,x5,}{x1,x2,x3}的上(下)(确)界最大元素x1,无最小元素

x5x1x2x3x4极大元素x1,极小元素x4,x5

集合上界下界上确界下确界{x2,x3,x4}x1x4x1x4{x3,x4,x5,}x1,x3无x3无{x1,x2,x3}x1x4x1x422作业讲评

P1463-12(7)(7)下图给出了集合{1,2,3,4}上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。1243(a)先去环再去掉传递最后调整位置1234(a)23作业讲评

P1463-12(7)(7)下图给出了集合{1,2,3,4}上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。1234(c)先去环再去掉传递最后调整位置421324作业讲评补充题设f,g,h是实数集R上的函数，f(x)=x+2,g(x)=x-2,h(x)=3x，求fg、ff、gf、gg、fh、hg、hfgfg(x)=xff(x)=x+4gf(x)=xgg(x)=x-4fh(x)=3x+2hg(x)=3x-6hfg(x)=h(x)=3x25作业讲评P1514-2.(6)(6)设A和B是有穷集合，有多少不同入射函数和多少不同的双射函数。入射:X中没有两个元素有相同的象(1)f:A－>B为入射,必须有|A|≤|B|,即m≤n设|A|=m，|B|=n

B中任意选出m个元素的任一全排列即为所求.满射:Y中每一个元素是X中的一个或多个元素的象点。

(2)f:A－>B为双射,必须有|A|=|B|,即m=n所以，共有m!个。26集合是什么

集合是不能精确定义的基本概念。如何理解集合：由共同性质的一些对象汇集而成的整体。集合可以是有限集，也可以是无限集集合的表示方法：

枚举法

叙述法（列判别条件）一般用大写字母表示集合，用小写字母表示元素见课本P8227集合与元素的关系集合与元素的关系：xA或xA

集合元素可以是离散型数据（如整型、逻辑型、枚举型等），也可以是非离散型数据（如实型）。

有限集一定是离散型数据，无限集可能是离散型，也可能是非离散型的数据。本书中默认：

自然数集从0开始（见P94，习题(3)中对自然数N的子集C的定义）28集合的概念子集：ＡＢ(x)(xＡ→xＢ)（B包含A）真子集：ＡＢＡＢ∧ＡＢ(x)(xＡ→xＢ)∧(x)(xB∧xA)空集：不包含任何元素的集合

φ={x|p(x)∧┑p(x)}，

p(x)为任何谓词全集：E={x|p(x)∨┑p(x)}，

p(x)为任何谓词29集合的相等集合A、B相等：

A=BA,B的元素完全相同AB且BA(x,若xA，则xB)且

(x,若xB，则xA)集合A、B不等：

A≠BA,B的元素不完全相同 （不是完全不同！)not(AB)或not(BA)(x,xA且xB)或

(x,xB且xA)30幂集幂集的概念：给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集，记为P(A)。若|A|=n，则|P(A)|=2n如何证明?注意

P(φ)={φ}≠φ区别：

{},但{},{}。A=BP(A)=P(B)ABP(A)P(B)31证明

AB当且仅当P(A)

P(B)充分性:对任意xA{x}P(A){x}P(B)

xB所以AB必要性:对任意xP(A)xAxB

xP(B)所以P(A)P(B)32集合之间的关系子集：A包含BB包含于A真子集：相等：A、B的元素完全相同不等：A、B的元素不完全相同从属：ＡＢ （一个集合是另外一个集合的元素）33空集的性质空集是一切集合的子集。空集是惟一的。空集是任何集合的幂集的元素。空集的幂集不是空集。34空集例题例判断下列命题的真假: (1)

(2)

(3)

{} (4)

{}

(2)为假;其余均为真。35集合运算的性质交换律

A∩B=B∩A A∪B=B∪A

A⊕B=B⊕A

结合律

(A∩B)∩C=A∩(B∩C) (A∪B)∪C=A∪(B∪C)

(A⊕B)⊕C=A⊕(B⊕C)

注意：

A―B≠B―A (A―B)―C≠A―(B―C)36集合运算的性质分配律（注意证明方法是典型的，见P89，P91）

A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)

A∩(B―C)=(A∩B)―(A∩C)P91定理 但：A∪(B―C)≠(A∪B)―(A∪C)

例：B=~A,C=φ时

A∩(B⊕C)=(A∩B)⊕(A∩C)

但：A∪(B⊕C)≠(A∪B)⊕(A∪C)

例：B=C,A≠φ时37集合运算的性质摩根律

~(A∪B)=~A∩~B

~(A∩B)=~A∪~B

A–(B∪C)=(A–B)∩(A–C)A–(B∩C)=(A–B)∪(A–C)吸收律

A∪(A∩B)=A=A∩(A∪B)其他

A∩BAA∪B A∩BBA∪B38证明集合相等的方法

往证A=B方法一：

证明：AB且BA

（P91定理3-2.5的证明方法）方法二： 证明满足A元素的条件逻辑等价于满足B元素的条件 （P91定理3-2.4的证明方法）方法三： 使用集合运算的性质 （P91定理3-2.6的证明方法）39证明集合不等的方法

往证AB：方法一：举反例

A≠B(x,xA且xB)

或(x,xB且xA)方法二： 说明（或证明）一个是空集（或全集），另一个不是方法三： 画文氏图示意40证明集合是空集的方法方法一： 其逻辑判断条件是永假方法二： 用反证法：设aA，引出矛盾的结果 （见P95习题(10)a)的证明）方法三： 利用等式，例如：A⊕A=φ41包含排斥原理│A∪B│=│A│+│B│-│A∩B││A∪B∪C│=│A│+│B│+│C│ -│A∩B│-│A∩C│-│B∩C│+│A∩B∩C│见P96-99例题1、2、342定义序偶序偶：有序的偶对序偶与集合的区别：有序/无序若x≠y，则<x,y>≠<y,x>，但{x,y}={y,x}序偶与集合的统一：

<x,y>={{x},{x,y}}序偶相等的定义：

<x,y>=<u,v>x=u且y=v43集合的笛卡儿乘积集合A、B的笛卡儿乘积

AB=<x,y>(xA)∧(yB)见课本P102例题1

44笛卡儿乘积的性质ABBAABC=(AB)CA(BC)An=AAA(n个A)ABABAnAnAA45笛卡儿乘积的定理以下定理均可从序偶、集合相等的定义证明：

A(B∪C)(AB)∪(AC) (B∪C)A(BA)∪(CA) A(B∩C)(AB)∩(AC) (B∩C)A(BA)∩(CA)

若C≠，则AB(AC)(BC)(CACB)

非空集合A,B,C,D, ABCDAC且BD46关系的定义关系是两个集合的笛卡儿乘积的子集。本质上关系R是序偶的集合：若<x,y>R则记为xRy若<x,y>R则记为xRy

集合A到集合B的关系：AB的子集集合A上的关系：AA的子集 见课本P106例题1、2、347特殊的关系恒等关系

IA＝x,xxA是A上的关系全域关系：R＝AB空关系：R＝定理：

A到B的两个关系的交、并、差、补仍是A到B的关系48关系的表示集合法：列举集合的所有元素（序偶）或判别条件叙述法：

叙述关系定义的判别条件；P107例4矩阵法：

A到B的关系用|A|行|B|列的0、1矩阵表示图：

A到B的关系：用有向偶图表示（点表示集合元素，弧表示序偶）A上的关系：用有向图表示（点表示集合元素，弧表示序偶）49关系的性质讨论非空集合A上的关系R（即RAA）自反性：aA,a,aR

关系图中每个点都有环

关系矩阵是对角线元素全部为1反自反性：aA,a,aR

关系图中每个点都没环

关系矩阵是对角线元素全部为050关系的性质对称性：a,bA,若a,bR，则b,aR

关系图中任意两个不同的点之间要么没有边，要么有双向边；

关系矩阵是对称矩阵反对称性：若ab，则a,bR或b,aR；或者：a,bA,若a,bR且b,aR,则a=b；

关系图任意两个不同的点之间要么没有边，要么只有单向边。关系矩阵呢？51关系的性质传递性：a,b,cA,若a,bR且b,cR，则a,cR

关系图中任意两个点之间若经过第三点有路接通，则必有直达边;

关系矩阵较复杂52定义复合关系 设R是A到B的关系，S是B到C的关系，则RS称为R和S的复合关系，表示为RS={<x,z>|xA∧zC∧ (y)(yB∧<x,y>R∧<y,z>S)}R表示关系时，Rn表示n个关系R的复合复合关系是不可交换的（没有公共域）复合关系是可结合的。53定义逆关系 设R是A到B的关系，将R中每一序偶元素顺序互换，得到的集合称为关系R的逆关系，(inverserelation)表示为Rc={<y,x>|<x,y>R}可见，Rc是B到A的关系。逆关系保持了关系的性质：

即保持了原关系的自反性、反自反性、对称性、反对称性、传递性（若原关系有这些性质的话）。见课本P119习题（5）54有关定理证明两个关系相等，实质上是证明两个集合（元素是序偶）相等

(R1∪R2)c=R1c∪R2c (R1∩R2)c=R1c∩R2c (R1-R2)c=R1c-R2c (AB)c=BA

(R1R2)c=R2c

R1c (R1R2)R3=R1(R2R3) R是对称的R=Rc R是反对称的R∩Rc

Ix

55逆关系的性质逆关系的矩阵： 原关系矩阵转置之后得到逆关系的矩阵逆关系的图： 把弧的方向反转，得到逆关系的图逆关系保留了原来关系的自反、反自反、对称、反对称、传递等性质。 56关系运算后性质的保持关系运算后性质的保持运算\性质自反性反自反性对称性反对称性传递性R∪SR∩SR–SRcR·S57关系的闭包关系R的自反（对称、传递）闭包：是指包含R的、而且是自反的、最小的自反（对称、传递）关系

严格的定义：见课本P119如果R本身是自反的（对称的、传递的），则其自反的（对称的、传递的）闭包就是R自反闭包：reflexiveclosure对称闭包：symmetricclosure传递闭包：transitiveclosure58闭包的讨论自反闭包rRR∪Ix（R是集合X上的关系）对称闭包sRR∪Rc

传递闭包t(R)=R∪R2∪…∪Rn∪…

若|X|=n，则只需前m个（mn）关系的并

rsRsr(R)

rtRtr(R)

tsRst(R)Warshall算法的实质：简化矩阵运算，此处不要求，“数据结构”课程再讲。59定义集合的划分与覆盖

A为非空集合，S={S1,S2,…,Sm}，其中（1）SiA，Si≠φ(i=1,2,…,m)（2）S1∪S2∪…∪Sm=A（3）当i≠j时，Si∩Sj=φS是A的覆盖S是A的划分定义的另一种描述： 若把集合A分成若干个叫做分块的非空子集，使得A中每一个元素至少属于一个分块，则这些分块的全体叫A的一个覆盖；若A中每一个元素属于且只属于一个分块，则这些分块的全体叫A的一个划分（或分划）。60习题解答P130习题(5)(1)∪(Ai

∩B)

=(A1∪A2

∪‥∪Ak)∩B=A∩Bi=1k(2)(Ai

∩B)∩(Aj

∩B)

=Ai∩Aj

∩

B=φ61定义等价关系

R是集合A上的关系，满足自反、对称、传递，则R是A上的等价关系。见课本P131例题1、例题2注意： 许多这类题目：给出某些性质，判别是否等价关系62定义等价类R是A上的等价关系，则等价类aRxxA且aRx等价类的性质：a,bA1）aRφ且aRA2）a,bRaRbR

3）a,bRaR∩bR=φ4）aRaA是Ａ的一个划分，记为Ａ／Ｒ（商集）

63划分和等价关系1）等价关系---------划分 （P133定理3-10.2，3-10.3）2）R1=R2A/R1=A/R2

（P134定理3-10.4）决定64定义偏序关系 非空集合A上的关系R，满足自反、反对称、传递的性质，称R是A上的一个偏序关系，记为：序偶＜A,＞称作偏序集。 见课本P140例题1、例题265定义“盖住”在偏序集中的两个元素x和y满足以下条件： ①xy ②x≠y③x,y之间没有z，使xz且zy

则称y盖住x

见课本P140例题3

对于给定的偏序集＜A,＞，其盖住关系是确定的、唯一的。66哈斯图Hassediagram回顾：偏序关系的关系图的特点？哈斯图： 关系图的简化（省略了自反性、传递性）使用了“盖住”的性质，作图规则如下：1）每个元素用一个小圆点表示；2）若元素y盖住元素x，则y画在x上方，并用直线连接；3）若xy且x≠y，则y画在x之上；若无关系，则两个点可画在同一水平，也可一上一下。67作业讲评

P1463-12(7)(7)下图给出了集合{1,2,3,4}上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。1234(c)先去环再去掉传递最后调整位置421368定义链、反链 Ａ的子集称为：

链：偏序集的每两个元素都有关系；

(哈斯图中某条链上的点集)

反链：偏序集的每两个元素都没有关系

(哈斯图中若干个没关系的点的集合)

单个元素的子集，既是链，又是反链

（注意：这是约定，不能证明）问：是否存在非链、非反链的关系？答：是。如集合{2,3,4}上的整除关系69线序关系 在偏序集＜A,＞中，如果A是一个链，则称＜A,＞为全序集合或线序集合，二元关系称为全序关系或线序关系。全序关系线序关系哈斯图是一条“链” 全序关系＜A,＞中，x,yA，xy和yx至少有一个成立。

A上的线序关系A上的偏序关系

A上的偏序关系A上的关系

A上的关系AA70AAA上的关系A上的偏序关系A上的等价关系线序关系恒等关系的子集单个元素各概念的相互关系71极大元最大元 ＜A,＞是偏序集合，且B是A的子集，对于B中的某个元素b，若B中没有其他元素x，满足bx，则称b是B的极大元。 ＜A,＞是偏序集合，且B是A的子集，对于B中的某个元素b，若对于B中每个元素x，满足xb，则称b是B的最大元。72上界、上确界 ＜A,＞是偏序集合，且B是A的子集，对于A中的某个元素a，若对于B中每个元素x，满足xa，则称a是B的上界。 注意：上界不一定是集合内的点； ＜A,＞是偏序集合，且B是A的子集，a是B的某一上界，对于B中所有上界y，满足ay，则称a是B的最小上界，或上确界。 注意：上确界不一定是集合内的点；73良序 偏序集合的每个非空子集存在最小元素，则称为良序集。良序集合一定是全序集合（P145定理12.1)良序线序偏序关系笛卡尔乘积

有限的全序集合一定是良序集合

(P145定理12.2)无限的全序集合不一定是良序集合（例如正实数集合上的小于关系，开区间子集没最小元素）74定义函数

函数（也叫映射mapping）的定义：f是集合X到集合Y的一个关系，对于每一个xX，有惟一的yY，使得<x,y>f，称关系f为函数，记为：

f:X→Y或X→Y y记为f(x)f函数与关系的区别:①定义域是整个集合X；②一个aX只能对应于惟一的一个yY，使f(x)=y；可见: 函数关系笛卡尔乘积75解(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)R3={‹a,0›,‹b,1›,‹c,1›}。76例题证明因为任一函数f是由A中n个元素的取值所唯一确定的,A中的任一元素a,f在a处的取值都有m种可能,所以A到B可以定义m·m…m=mn

=|B||A|个不同的函数。设|A|=n,|B|=m，X到Y有多少个不同的函数？77习题解答

P1514-1(2)令f:A→B，已知CA，证明：f(A)-f(C)f(A-C)证明：任意yf(A)-f(C),xA,f(x)=y

对于zC，y≠f(z)，即x≠z

因此

xA-C

故y=f(x)f(A-C)

于是有：f(A)-f(C)f(A-C)78习题解答

P1514-1(3)

假设f和g是函数，且有fg和domgdomf，证明f=g。证明：<a,g(a)>g，有adomgdomf

故adomf，

有<a,f(a)>fg，即<a,f(a)>g

由于g是函数，因此a有惟一像点， 于是有：<a,g(a)>=<a,f(a)>

<a,g(a)>=<a,f(a)>f

因此gf

已知fg，得到f=g79习题解答

P1514-1(3)假设f和g是函数，且有fg和domgdomf，证明f=g。证明：用反证法：设f≠g，由已知fg得

<a,g(a)>g，但<a,g(a)>f

由<a,g(a)>g，得adomgdomf

故adomf，有<a,f(a)>fg，

即<a,f(a)>g， 由于g是函数，因此a有惟一像点， 于是有：<a,g(a)>=<a,f(a)>

<a,g(a)>=<a,f(a)>f与题设矛盾。

因此f=g80满射、入射(单射)、双射 函数f:X→Y满射：yY，xX，使得f(x)=y；入射：x1,x2X，x1≠x2f(x1)≠f(x2)；双射：既是入射又是满射，也叫一一对应

81入射入射入射入射82逆函数inversefunction问：函数的逆关系一定是函数吗？答：只有双射才有逆函数双射函数f: