离散数学

【第一篇 集合论：1.集合与其运算 2.关系与函数】

第1章 集合及其运算

一、主要内容

1．集合的概念

 集合与元素——具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素．集合的元素不能重复出现，集合中的元素无顺序之分. 集合与其元素之间存在属于“”或不属于“”关系.

集合A中元素的个数为集合的元数，记作A．  集合的表示方法

列举法是列出集合的所有元素，并用花括号括起来．例如A = {a,b,c,d}，N = {0, 1, 2, 3, „}．

描述法是将集合中元素的共同属性描述出来．例如B = {xx210且xR}，D = {xx是正整数}．

文氏图法是用一个简单的平面区域表示一个集合，用区域内的点表示集合内的元素．

2．集合的关系

 包含(子集)——若对任一aA，都有aB，则称B包含A(或A包含于B)，称A是B的子集，记AB；又若AB，则称A是B的真子集，记AB．

 集合相等——若AB，BA，则A＝B.

注意：要正确理解元素与集合、集合与子集、子集与幂集、与()、空集与所有集合等的关系．

3．特殊集合

 全集合E——在一个具体问题中，所涉及的集合都是某个集合的子集，该集合为全集．

 空集——不含任何元素的集合为空集，空集是惟一的，它是任何集合的子集．  集合A的幂集P(A)——集合A的所有子集构成的集合称为A的幂集，记作

P(A)={xxA}. 若A＝n，则P(A)=2.

4．集合的运算

 集合A和B的并AB——由集合A和B的所有元素组成的集合．  集合A和B的交AB——由集合A和B的公共元素组成的集合．  集合A的补集A——属于E但不属于集合A的元素组成的集合，记作A．补集总相对于一个全集．

 集合A与B的差集A－B——由属于A，而不属于B的所有元素组成的集合..  集合A与B的对称差记作

AB＝(A－B)(B－A)，或AB＝）AB〕－（AB）

要熟练掌握运算的性质 (运算律)，即交换律、结合律、分配律、幂等律、同一律、零律、补余律、吸收律、摩根律和双补律等．

5．恒等式证明

集合运算部分有三个方面的问题：其一是进行集合的运算；其二是集合运算式的化简；

n 1

其三是集合恒等式的推理证明.

集合恒等式的证明方法通常有二：

(1) 要证明A＝B，只需要证明AB，又AB； (2) 通过运算律进行等式推导． 6．有限集合的计数方法

首先根据已知条件把对应的文氏图画出来，然后将已知集合的元素填入表示该集合的区域内．通常从几个集合的交集填起，根据计算结果将数字逐步填入所有的空白区域内．如果交集的数字是未知的，可以将其设为x，再根据已知条件列出方程或方程组，解出未知数x． 也可以用容斥定理计算有限集合的元素个数．

定理1.2.2（容斥定理） 对任意两个有限集合A和B，有

AB= A+B - AB

其中A，B分别表示A，B的元素个数．

定理1.2.2的推广结论：对于任意三个有限集合A, B, C，有

ABC = A+B+C-AB-AC-BC+ABC

二、实例

例1 已知S＝{2, a, {3}, 4}，R={{a}, 3, 4, 1}，判断下列各题是否正确：.

(1) {a}S; (2) {a}R;

(3) {a, 4, {3}}S; (4) {{a}, 1, 3, 4}R; (5) R=S; (6) {a}S (7) {a}R (8) R (9) {{a}}R (10) {}S

(11) R (12) {{3}, 4}

解 集合S有四个元素：2，a，{3}，4，而元素{3}又是集合；集合R类似．

(1) 错．因为{a}是单元素的集合，{a}不是集合S的元素，所以“{a}S”是错的． (2) 对．因为{a}是R的元素，所以“{a}R”是正确的．

(3) 对．因为a, 4, {3}都是S的元素，以此为元素构成的集合是S的子集．所以“{a,4,{3}}S”是正确的．

(4) 对．因为{a}, 1, 3, 4都是R的元素，以此为元素构成的集合是R的子集，所以“{{a},1,3,4}R”是正确的．

(5) 错．因为元素2S，但2R，所以S R．

(6),，和题号的命题真值为1；而, ,题号命题真值为0．

(7) 错．因为{a}是集合R的元素，元素与集合之间不能用“”，正确的表示为：{a}R． (8) 对．因为空集是任意集合的子集。

(9) 对．因为是集合{{a}}的子集，{{a}}是集合R的子集，所以{{a}}R是正确的。

(10) 错．因为不是集合S的元素，所以由空集构成的集合不是S的子集，即{}S是错的．

(11) 错．因为不是集合R的元素，所以R是错的． (12) 对．因为空集是任意集合的子集。

例2 写出下列集合的子集：

2

(1) A={a，{b}，c}； (2) B={}； (3) C=

解 (1) 因为是任何集合的子集，所以是集合A的子集；

由A的任何一个元素构成的集合，都是A的子集，所以{a}，{{b}}，{c}是A的子集； 由A的任何两个元素构成的集合，也是A的子集，即{a，{b}}，{{b},{c}}，{a, c}； 同理，A的三个元素构成的集合，也是A的子集，于是集合A的所有子集为：

，{a}，{{b}}，{c}，{a，{b}}，{{b},c}，{a, c}，{a，{b}，c}

(2) 分析同(1)，B的子集有：，{}。

(3) 因为是任何集合的子集，故也是C的子集。因为C中没有元素，因此C就没有其它子集，所以C的子集只有：

说明：

(1) 在第1小题中，以集合A的8个子集为元素的集合，就是集合A的幂集，即 P(A)={ ，{a}，{{b}}，{c}，{a，{b}}，{{b},c}，{a, c}，{a，{b}，c}} 集合B的幂集为；P(B)={,{}}；集合C的幂集：P(C)={}

一般地，如果集合A的元素个数为An,那么P(A)有2个元素，即P(A)=2． (2) 根据真子集的定义，对于任何集合A，除了集合A本身不是A的真子集外，其它子集均是A的真子集. 于是本例

集合A有7个真子集：，{a}，{{b}}，{c}，{a，{b}}，{{b},c}，{a, c} 集合B只有1个真子集： 集合C没有真子集。

例3 判断下列哪些运算结果是对的？哪些是错的？请将错误的运算结果更正过来．

(1) {}； (2) {}；

(3) {}{,{}}{}； (4) {,{}}{}{,{}}； (5) (AB)BA； (6) (AB)BA； (7) AAA； (8) (AB)A.

解 (1) 对． (2) 错．应为{}． (3) 对．

(4) 错．应为{{}}.

(5) 错．应为AB.

(6) 错．应为AB(或A~B或A－AB).

(7) 错．应为，即AAAAAA. (8) 对．

例4 设集合A={a, b, c, d, e}，B={b, d, e}，C={a, b, d}，求(A－B)(BC) 解 (A－B)(BC)

＝（{a, b, c, d, e}－{b, d, e}） ({b, d, e}{a, b, d}) ={a, c} {a, b, d, e} ={a, b, c, d, e}－{a}

3

nn={b, c, d, e}

例5 设A，B，C为三集合，证明：AC且BC的充分必要条件是(AB)C． 证明：必要性．因为AC且BC，所以

(AB)C(AB)CC

＝(AC)(BC) ＝CCC

所以，ABC

充分性．因为(AB)C，所以

AA(AB)AC，故AC

同理，BB(AB)BC．故BC．

例6 某所大学计算机专业的80名学生在期末考试中，Pascal语言课有58人达到优秀，数据结构课有30人达到优秀，离散数学课有25人达到优秀．并且，Pascal语言和数据结构两门课都达到的有20人，Pascal语言和离散数学两门课都达到的有19人，数据结构和离散数学两门课都达到的有17人．还有10人一门优秀都没得到．如果获得3门优秀者可得奖学金200元，获得2门优秀者可得奖学金100元，那么计算机系应为本专业学生发奖学金多少元？

解 设期末考试中Pascal语言课、数据结构课、离散数学课达到优秀的学生集合分别为A , B , C，那么

A = 58，B = 30，C = 25， AB= 20，AC= 19，BC= 17

而1门课都没达到优秀的学生~(ABC)= 10，即至少有1门课达到优秀的学生

ABC= 80-~(ABC)= 70．

那么，由定理1.2.2的推广结论，得3门课都达到优秀的学生数为：

ABC=ABC- (A+B+C-AB-AC-BC)

=70 -58 -30 -25 +20 +19 +17= 13 所以，计算机系应为本专业学生发奖学金：

13200 +（20-13）100 +（19-13）100 +（17-13）100 = 4300（元）

三、练习题

1．设S，T，M为任意集合，判定下列各题是否正确：

(1) 是的子集； (2)如果ST＝SM，则T＝M； (3) 如果S－T＝ ，则S＝T； (4)如果ST＝E，则ST； (5) SS=S

4

2．用列举法表示以下集合：

(1) A{xxNx27}； (2) A{xxN3x3}； (3) A{xxR(x1)20}．

3．设A，B为任意集合，试证明ABBAAB

4．化简集合表达式(((AB)B)(CB))(((AB)~B)A)

四、练习题答案

1．(1)，(4)正确，其余错误.

2．(1) A={0, 1, 2}；(2) A={1, 2, 3, 4, 5}； (3) A={－1} 3．当A＝B时，必有A－B＝B－A；

反之，由A－B＝B－A，得到：(AB)B(BA)B 化简后得到BA，即BA；

同理，由A－B＝B－A，得到：(AB)A(BA)A 化简后得到AB，即AB. 所以A＝B． 4．A

第2章 关系与函数

一、主要内容

1．有序对与笛卡儿积

 有序对，就是有顺序的数组，如，x, y 的位置是确定的，不能随意放置. 注意：有序对，以a, b为元素的集合{a, b}={b, a}；有序对(a, a)有意义，而集合{a, a}是单元素集合，应记作{a}.

 笛卡儿积，把集合A，B合成集合A×B，规定

A×B＝{xAyB}

由于有序对中x, y的位置是确定的，因此A×B的记法也是确定的，不能写成B×A.

笛卡儿积也可以多个集合合成，A1×A2ׄ×An. 笛卡儿积的运算性质. 一般不能交换. 2．关系的概念

包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.

 二元关系，是一个有序对集合，设集合A，B，从集合A到B的二元关系

R{x,yxAyB}，

记作xRy． 二元关系的定义域：Dom(R)A； 二元关系的值域：Ran(R)B

 关系的表示方法：

集合表示法：关系是集合，有类似于集合的表示方法.

列举法，如R＝{<1, 1>,<1, 2>}；描述法：如R{x,yxAyB}

5

1 关系矩阵： RA×B，R的矩阵MR(rij)mn,rij0aiRbji1,2...,m, aiRbjj1,2,...,n关系图：R是集合上的二元关系，若R，由结点aI画有向弧到bj构成的图形.

3．几个特殊的关系

空关系；唯一是任何关系的子集的关系. 全关系EA{a,ba,bA}AA

恒等关系IA{a,aaA}，MI 是单位矩阵. 4．关系的运算

 关系的集合运算，有并、交、补、差和对称差.

 复合关系 RR1R2{a,cb使a,bR1b,cR2}，有 复合关系矩阵：MRMR1MR2(布尔运算)，有结合律：(RS)T＝R(ST)  逆关系R1－1－1－1T，(RS)=SR. {y,xx,yR}，MR1MR5．关系的性质

 自反性 xA,x,xR；矩阵MR的主对角线元素全为1；关系图的每个结点都有自回路.

 反自反性 xA,x,xR；矩阵MR的主对角线元素全为0；关系图的每个结点都没有自回路.

 对称性 若x,yR，则y,xR；矩阵MR是对称矩阵，即rijrji；关系图中有向弧成对出现,方向相反.

 反对称性 若x,yR且y,xR，则x=y或若x,yR,xy，则

y,xR；矩阵MR不出现对称元素.

 传递性 若a,bR且b,cR，则a,cR；在关系图中，有从a到b的弧，有从b到c的弧，则有从a到c的弧. 判断传递性较为困难.

可以证明：R是集合A上的二元关系，

(1) R是自反的IAR; (2) R是反自反的IAR＝;

－1－1

(3) R是对称的 R＝R； (4) R是反对称的RRIA； (5) R是传递的RRR.

关系的性质所具有的运算见表4－1.

表4－1 二元运算的并、交、补、差、逆、复合具有的性质表

运算 关系性质 自反性 反自反性   对称性   反对称性 传递性     6

R－1   R1R2

R1R2 R1－R2 R1R2 IA                         由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系.具有反自反性、对称性、反对称性和传递性．是偏序关系.

关系性质的判定，可以用定义、关系矩阵或关系图. 6. 关系的闭包

设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R表示，使得R具有关系的自反(对称、传递)性质，R就是R的自反(对称、传递)闭包，记作r(R) ，s(R)和t(R)．

闭包的求法： 定理12：自反闭包 r(R)RIA；

定理13：对称闭包 s(R)RR1； 定理14的推论：传递闭包 t(R)

Ri1ni

7. 等价关系、相容关系和偏序关系

等价关系、相容关系和偏序关系是具有不同性质的两个关系.

性相容系 自反性性等价系

反性性偏序系 等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双

向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线．

等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={bbAaRb}.

相容类，设B是A的子集，如果在B中的任意两个元素都是相关的，则称为由相容关系R产生的相容类．

偏序集的哈斯图 偏序集概念和偏序集的哈斯图．哈斯图的画法：

(1) 用空心点表示结点，自环不画；

(2) 若ab，则结点b画在上边，a画在下边，并画a到b的无向弧； (3) 若,,则R，此时，a到c的有向弧不画出. 确定任一子集的最大(小)元，极大(小)元.

极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样. 8. 函数

7

函数, 设f是集合A到B的二元关系，aA,bB,且f，且Dom(f)=A，f是一个函数(映射). 函数是一种特殊的关系.

集合A×B的任何子集都是关系，但不一定是函数. 函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制.

二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同.

函数的类型

单射 若a1a2f(a1)f(a2)

满射 f(A)=B. 即yB,xA,使得yf(x) 双射 单射且满射.

复合函数 若f:AB,g:BC,则fg:AC,即fg(x)g(f(x)). 复合成立的条件是：Ran(f)Dom(g)

一般fggf，但(fg)hf(gh)

复合函数的性质：

如果f,g都是单射的，则fg是单射的； 如果f,g都是满射的，则fg是满射的；如果f,g都是双射的，则fg是双射的； 如果f,g是单射的，则f是单射的； 如果f,g是满射的，则g是满射的；

如果f,g是双射的，则f是单射的，g是满射的.

反函数 若f：AB是双射，则有反函数f－1

：BA

f1{b,abB,f(a)b,aA}，(fg)1g1f1,(f1)1f 二、实例

例1 设给定集合A＝{a,b}，写出P(A)和P(A)上的包含关系的集合表达式．

解 P(A){,{a},{b},{a,b}}

{,{a},,{b},,{a,b},{a},{a,b},{b},{a,b}}

例2 设A＝{1,2,3},用列举法给出A上的恒等关系IA，全关系EA，A上的小于关系 LA{x,yx,yAxy} 及其逆关系和关系矩阵.

解 IA{1,1,2,2,3,3}

EA{1,2,1,3,2,1,2,3,3,1,3,2,}IA

L1,2,1,3,2,3}, LA的逆关系L1A{A{2,1,3,1,3,2}

011

MLA001 M000100. 有 MTL1LAML1 A 000A110

例3 设集合A={a, b, c}，A上的二元关系

R＝{,,,}，S={,,} 求RS，并用关系矩阵验证．

解 RS＝{,,,}{,,}

8

＝{,,}

110MR001,M001001,

010S001110MRS001001001001001010，

001001从矩阵也可得RS＝{,,}

例4 设R和S是集合A＝{1,2,3}上的二元关系， R＝{<1,1>,<1,2>,<2,3>,<3,1>,<3,3>}

S={<1,2>,<1,3>,<2,1>,<3,3>}

求RS和S2

以及MS2．

解 RS= {<1,1>,<1,2>,<2,3>,<3,1>,<3,3>}{<1,2>,<1,3>,<2,1>,<3,3>} ={1,2,1,3,1,1,2,3,3,2,3,3}

S2

=SS={<1,2>,<1,3>,<2,1>,<3,3>}{<1,2>,<1,3>,<2,1>,<3,3>}

={1,1,1,3,2,2,2,3,3,3}

101 MSS011

001例5 设R是实数集，R上的二元关系S为

S＝{x,yRx=y}

试问二元关系S具有哪些性质？简单说明理由．

解 12. S具有自反性，显然S； S具有对称性，S，有x=y，则S； S具有反对称性，,S，有x=y；

S具有传递性，,S,因为x=y=z，故S．

例6 设集合A1,2,3,4,A上的二元关系R1,2,3,2,2,3,3,4（1）求出R2，R3

的集合表达式；

（2）画出R2

的关系图． 1  2 解 (1)R2

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

(2) R2

的关系图如例6图

4  3

例6图 R2的关系图

例7 设集合A＝{a,b,c,d,e}，定义A上的二元关系 R1{a,b,b,a,d,e,e,d}IA

R2{a,b,b,a,b,b,c,c,d,d,d,e} 判断R1，R2是否为等价关系？

分析 判断等价关系，就是验证是否具有自反性、对称性和传递性.

9

解 写出R1的关系矩阵，

MR111000100010000100

00110011 a 

b   e

c   d 例7图

由关系矩阵可知，R1具有自反性和对称性. 由关系图(例7图)可知它具有传递性，故R1是等价关系.

R2不是等价关系，因为(a,a)R2(或(e,e)R2)，故R不具有自反性.

注意：自反性，对称性和传递性之一不具备，就是破坏了等价关系的定义. 事实上d,eR2,但e,dR2，故R2不具有对称性；b,aR2，

但a,aR2，R2也不具有传递性.

对例7的R1进行分类：元素a，因为a,a,a,b,b,a,b,b均属于R1，所以a生成的等价类[a]R1{a,b}或记作[b]R1.

元素c，因为c,cR1，所以c生成的等价类[c]R1{c}; 类似地， d生成的等价类[d]R1{d,e}＝[e]R1.

例8 设集合A＝{0，1，2，3，4，5，6}上的偏序关系R如下：

R＝{<0,1>,<0,2><0,3>,<0,4>,<0,5>,<0,6>,<2,5>,<3,5>，<4,6>}IA

做偏序集的哈斯图，并求B={0,2,3}的极大元、极小元、最大元和最小元，B的上界和

6 5 最小上界，下界和最大下界． 解 A＝{0,1,2,3,4,5,6}, B={0，2，3}，

4 3 2 1 哈斯图如例8图所示．

B的极大元：2，3, B的极小元：0

0 B的最大元：无 B的最小元：0

例8图 B的上界为5，最小上界也是5；B的

下界和最大下界均为0．

若C＝{0,3}，那么C的上界为5，3，最小上界为3．

若D＝{4,6}，那么D的上界和最小上界为6，下界为0，4，最大下界为4．

再强碉一下，子集B的极大(小)、最大(小)元，一定是B的元素；而B的界可以不是B的元素，只要是所讨论的集合A的元素即可．

例9 已知如图，集合A上的关系，请回答下列问题：

1   1 1   1 1   1 2   2 2   2 2   2 3   3 3   3 3  3 4   4 4   4 4  4 10

f g h 例9图

求：(1) f,g,h哪个是函数，若是，指出它的象； (2) fg, gg;

(3) 指出f,g中哪个是单射，满射或双射；

(4) f,g,中哪个函数存在反函数，给出其反函数的表达式. 解 (1) f,g是函数，h不是函数，因为其中4无定义．

f(A)={1,2,4}, g(A)=A．

(2) fg={<1,4>,<2,2>,<3,2>,<4,3>} gg={<1,4>,<2,3,>,<3,2>,<4,1>}

(3) 只有g是单射，又是满射，即为双射.

－1－1

(4) 只有g有反函数g：AA，且满足, g＝{<1,3>,<2,1>,<3,4>,<4,2>}

例10 确定以下各题的f是否为从A到B的函数，并对其中的函数f：AB指出它是单射，满射或双射？如果不是，请说明理由.

(1) A,B为实数集，f(x)x2x; (2) A,B为实数集合，f(x)x3; (3) A,B为实数集合，f(x)1; (4) A,B为正整数集，f(x)x1; x解 (1) f是从A到B函数，但不是单射，因为f(0)=f(1)=0；也不是满射，因为该函数的最小值是－1/4，所以Ran(f)是[1/4,)，不是整个实数集.

(2) f是从A到B的双射函数．

因为任意x1，x2A，只要x1x2，则有f(x1)x1x2f(x2)，故f(x)是单射函数． 又任意yB,x=3yA，使得f(x)=(3y)3y．所以f(x)是满射函数． 所以，f(x)=x是双射函数． (3) f(x)3

331不是函数，因为0A，但x=0无定义． x(4) f是从A到B函数，且f是单射，因为易验证 n1,n2Z,n1n2n11n21

但f不是满射，因为1Ran(f).

例11 证明如果非空集合A上的二元关系R和S是偏序关系，则RS也是A上的偏序关系．

证明 ① 任意xA,x,xR,x,xSx,xRS，所以RS有自反

性；

② 任意x,yA,因为R，S是反对称的，

x,yRSy,xRS(x,yRx,yS)(y,xRy,xS)(x,yRy,xR)(x,ySy,xS)xyyxxy

11

所以，RS有反对称性． ③ 任意x,y,zA，因为R，S是传递的，

x,yRSy,zRS

x,yRx,ySy,zRy,zS x,yRy,zRx,ySy,zS x,zRx,zSx,zRS 所以，RS有传递性． 总之，R是偏序关系.

三、练习题

1. 设集合A={0,1,2,3,4}，定义A上的二元关系R为： R＝{x, yA且(x=y或x+yA)}

试写出二元关系R的集合表达式，并指出R具有的性质．

2. 设A＝{1,2,3,4}, R是A上的二元关系，其关系矩阵为

11MR010000000010 10试求 (1) R的关系表达式； (2) Dom(R)和Ran(R)；

－1

(3) RR中有多少个有序对 (4) R的关系图中有多少条自回路? 3. 设A＝{1,2,3,4,5,6},定义A上的二元关系

R＝{<1,1>,<1,4>,<2,2>,<2,3>,<2,6>,<3,2>,<3,3>,<3,6>,<4,1>,<4,4>, <5,5>,<6,2>,<6,3>,<6,6>} (1) 判定R是否为等价关系？

(2) 若是等价关系，写出A的关于R的等价类. 4. 设A＝{1,2,3,4,5},R是A上的二元关系

R＝{<1,1>,<2,2>,<3,3>,<3,4>,<4,4>,<5,3>,<5,4>,<5,5>} (1) 试写出R的关系矩阵和关系图；

(2) 证明R是A上的偏序关系，并画出哈斯图；

(3) 若BA，且B＝{2,3,4,5},求B的最大元，最小元，极大元极小元最小上界和最大下界.

5. 设R，Z，N分别表示实数、整数和自然数集，定义函数f1,f2,f3,f4, 试确定它们的性质.

f1:RR,f(x)2x

f2:ZN,f(x)x

f3:NN,f(x)x(mod3),x除3的余数f4:NNN,f(n)(n,n1)

f4(5)()6. 选择填空题

(1) 设集合A={1,2,3,4}, A上的二元关系R的关系矩阵为

12

11MR＝000000010010 00

则关系R的表达式是( )

(A) {<1,1>,<1,4>,<2,1>,<2,3>} (B) {<1,1>,<1,2>,<1,4>,<2,3>} (C) {<1,1>,<2,1>,<3,2>,<1,4>} (D) {<1,1>,<2,1>,<3,2>,<4,1>} (2) 设A={a，b，c}，R={，}，则R具有性质（ ） (A) 自反的 (B) 反自反的 (C) 反对称的 (D) 等价的

(3) 4. 设集合A＝{，a}，则P(A)＝ ( )

(A){,{a},{,a}} (B){{},{a},{,a}} (C){,{},{a},{,{a}}},{2},A} (D){,{},{a},{,a}}

（4） 设R是集合A上的二元关系，IA是A上的恒等关系，如果RIA，，则下面四个命题中为真的是（ ）

(A) R不是自反的 (B) R不是传递的 (C) R不是对称的 (D) R不是反对称的 (5) 设函数f：NN，f(n)n+1，下面四个命题中为真的是（ ）

(A) f是满射的 (B) f是双射的 (C) f是单射函数 (D) f存在反函数 (6) 设A={a，b，c}，R={，}，则R具有性质（ ）

(A) 自反的 (B) 反自反的 (C) 反对称的 (D) 等价的

(7) 设集合A{a1,a2,a3,a4},B{b1,b2,b3},是从A到B的函数， {a1,b2,

a2,b2,a3,b1,a4,b3}，则是( )

(A) 双射 (B) 满射但不是单射 (C) 单射但不是满射 (D)非单射也非满射 (8) 设R，S都是集合A上的等价关系，则对称闭包s(RS)=

(9) 设A＝{1,2},B={a, b},试问从A到B的二元关系有 ，其中函数有 (10) 设A、B为有限集，且m,n,那末A与B间存在双射，当且仅当 ． (11) 如果关系R是传递的，则RR ．

四、练习题答案

1. R＝IA{<0,1>,<1,0>,<0,2>,<2,0>,<0,3>,<3,0>,<0,4>,<4,0>,<1,2>,<2,1>,<1,3>,<3,1>} R具有自反性和对称性．

2. (1) {<1,1>,<1,4>,<2,1>,<4,1>,<3,4>} (2) {1,2,3,4}, {1,4}

(3) 7个是<1,1>,<1,4>,<2,1>,<2,4>,<3,1>,<4,1><4,4> (4) 1个是<1,1> 3. (1) 是等价关系；(2) 等价类分别 为{2,3,6}, (1,4), {5}

1  3  4.

2  4   5 图1

13

关系图如图1． 4 (1)R具有自反性；R具有传递性；R具有反对称性， 10(1) MR000000010000110,

00100111故R是偏序关系. 作的哈斯图(图2)． (2)当B＝{2,3,4,5}时，B的极大元为2，4； 极小元为2，5；B无最大元和最小元；B无上界和下界. 5. f1双射；f2满射不单射；f3不单射也不满射；f4

单射不满射；f4(5)=(5,6) 6. 选择填空题 (1) A (2) C (3) D （4）A (5) C (6) C (7) B (8) (9) 16个；4个 (10) m=n (11) R

3

2 1 5 图 2 哈斯图

RS

14