离散数学（本）主要概念

本文格式为Word版，下载可任意编辑——离散数学（本）主要概念《离散数学(本)》主要概念、定理与方法

第1章集合及其运算

一、概念

集合（元素）——集合是一些具有确定的、可以区分的若干事件的全体，而集合中的事件称为元素．因此，集合是由若干元素组成的．若a是集合A中的元素，则称a属于A，记作a?A；若a不是集合A中的元素，则称a不属于A，记作a?A．

定义1.1.1（子集）对任意两个集合A和B，若B中的每个元素都是A中的元素，则称B为A的子集，记作B?A或A?B．

若B是A的子集，也称A包含B，或B被A包含．若B不是A的子集，即B?A不成立时，记作B?A．

定义1.1.2（集合相等）对任意两个集合A和B，若有A?B且B?A，则称A与B相等，记作A=B．

定义1.1.3（真子集）对任意两个集合A和B，若B?A且B?A，则称B为A的真子集，记作B?A或A?B．

定义1.1.4（空集）不含任何元素的集合称为空集，记作?．空集的定义也可以写成

?={xx?x}（1.1.1）

n元集（m元子集）——含有n个元素的集合简称n元集，它的含有m（m?n）个元素的子集叫做它的m元子集．

定义1.1.5（全集）在一个具体问题中，假使所涉及的集合都是某个集合的子集，则将这个集合称为全集，记作E．

定义1.1.6（幂集）设A是一个集合，由A的所有子集组成的集合，称为A的幂集，记作P(A)或2A．

定义1.2.1（并集、交集、差集、补集、对称差）设E为全集，A和B是E中任意两个子集．

（1）所有属于A或属于B的元素组成的集合，称为集合A与B的并集，记作A?B．即

A?B?{xx?A或x?B}（1.2.1）

（2）既属于A又属于B的所有元素组成的集合，称为集合A与B的交集，记作A?B．即

A?B?{xx?A且x?B}（1.2.2）

假使两个集合A和B没有公共元素，即A?B??，称为集合A与B不相交．

（3）属于A而不属于B的所有元素组成的集合，称为A与B的差集，记作A?B．即

A?B?{xx?A且x?B}（1.2.3）（4）由E中所有不属于A的元素组成的集合，称为A的补集，记作~A．即

~A={xx?E且x?A}（1.2.4）

补集~A可以看作全集E与集合A的差集，即~A=E-A．

（5）集合(A-B)?(B-A)称为集合A和B的对称差，记作A?B．即

A?B=(A-B)?(B-A)．（1.2.5）

对称差运算的另一种定义是

A?B=(A?B)-(B?A)．（1.2.5’）

二、定理与性质

集合包含关系的自反性：对于任意集合A，有A?A．

集合包含关系的反对称性：对任意两个集合A和B，若有A?B且B?A，则A=B．集合包含关系的传递性：对任意三个集合A，B和C，若有A?B，B?C，则A?C．定理1.1.1空集是一切集合的子集．定理1.1.1的推论空集是唯一的．集合运算的交换律：A?B?B?AA?B?B?A

1

集合运算的结合律：(A?B)?C?A?(B?C)(A?B)?C?A?(B?C)

集合运算的分派律：A?(B?C)?(A?B)?(A?C)A?(B?C)?(A?B)?(A?C)集合运算的幂等律：A?A=AA?A=A集合运算的同一律：A???AA?E?A集合运算的零律：A?E=EA??=?集合运算的补余律：A?~A=EA?~A=?

集合运算的吸收律：A?(A?B)?AA?(A?B)?A

集合运算的摩根律：A-(B?C)=(A-B)?(A-C)A-(B?C)=(A-B)?(A-C)~(B?C)=~B?~C~(B?C)=~B?~C~?=E~E=?集合运算的双补律：~(~A)=A对称差的交换律：A?B?B?A

对称差的结合律：(A?B)?C?A?(B?C)

对称差的分派律：A?(B?C)?(A?B)?(A?C)对称差的同一律：A???A

对称差的零律：A?A=?对称差的性质：A?(A?B)=B

定理1.2.1对任意两个有限集合A和B，用S表示有限集合S中的元素数，则

(1)A?B?A+B；(2)A?B?min(A+B)；(3)A?B?A-B；(4)A?B=A+B-2A?B．定理1.2.2（容斥定理）对任意两个有限集合A和B，有

A?B=A+B-A?B（1.2.6）其中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.2.7）

三、方法

1．集合的三种表示方法

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

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

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

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

2

第2章关系与函数

一、概念

有序对——有序对是指两个元素x和y(允许x=y)按给定顺序排列组成的二元组合，记作．其中x是它的第一元素，y是它的其次元素．

定义2.1.1（笛卡尔积、直乘积）设A和B是任意两个集合，用A中元素为第一元素，B中元素为其次元素构成有序对，所有这样的有序对组成的集合称为集合A和B的笛卡尔积，或称为集合A和B的直乘积，记作A?B．即

A?B={x?A且y?B}

定义2.1.2（二元关系）任何一个有序对集合，称为一个二元关系，简称关系，记作R．对于二元关系R，若?R，可记作aRb；若?R，则记作aRb．

定义2.1.3（从A到B的二元关系）设A和B是两个集合，A?B的任一子集所定义的二元关系R称为从A到B的二元关系．当A=B时，称R为A上的二元关系．

定义2.1.4（定义域、值域）关系R中有序对的第一元素所允许选取对象集合称为关系R的定义域，记作Dom（R），其次元素所允许选取对象集合称为关系R的值域，记作Ran（R）．定义2.1.5（空关系、全关系、恒等关系）对任何集合A，

(1)由于空集?是A?A的子集，所以定义了A上的关系，称为A上的空关系；(2)定义EA={?a?A且b?A}=A?A，称为A上的全关系；(3)定义IA={?a?A}，称为A上的恒等关系．

定义2.1.6（关系矩阵）设集合A={a1，a2，…，am}，B={b1，b2，…，bn}，(1)若R是从A到B的一个关系，则R的关系矩阵是m?n矩阵

MR=rij，

??m?n??1,当aiRbj其中rij??，(i=1,2,…,m；j=1,2,…,n)．

??0,当aiRbj(2)若R是A上一个关系，则R的关系矩阵是m阶矩阵

MR=rij，

??m?m??1,当aiRbj其中rij??，(i,j=1,2,…,m)．

??0,当aiRbj定义2.1.7（结点、关系图、自回路）设集合A={a1，a2，…，am}，B={b1，b2，…，bn}，

若R是从A到B的一个关系，则用m空心点表示a1，a2，…，am，用n空心点表示b1，b2，…，bn，这些空心点统称为结点．假使aiRbj，那么由结点ai到结点bj作一条有向弧，箭头指向bj；假使?R，那么结点ai与bj之间没有弧连结，这样的图形称为R的关系图．若R是A上一个关系，假使aiRaj(i?j)，有向弧的画法与上面一致；假使aiRai，则画一条从结点ai到结点ai的带箭头的封闭弧，称为自回路．

定义2.2.1（复合关系）设A，B，C是三个集合，R是从A到B的一个二元关系，S是从B到C的一个二元关系，则R与S的复合关系为

R·S={?a?A，c?C，且存在b?B，使?R，?S}

这个复合关系是从A到C的一个二元关系．

布尔运算——布尔运算只涉及数字0和1，规定：加法：0+0=0，0+1=1+0=1+1=1；乘法：1?1=1，1?0=0?1=0?0=0．

定义2.2.2（复合关系矩阵）设集合A={a1，a2，…，am}，B={b1，b2，…，bn}，C={c1，c2，…，cp}，从A到B的二元关系R的关系矩阵MR是一个m行n列的矩阵，从B到C的二元关系S的关系矩阵MS是一个n行p列矩阵，则从A到C的复合关系R·S的关系矩阵MR?S是一个m行p列矩阵，并且

MR?S=MR?MS（2.2.1）

其中?表示按布尔运算进行矩阵乘法运算．

定义2.2.3（二元关系的幂）设R是集合A上的一个二元关系，n?N，则关系R的n次

3

幂Rn定义为：

(1)R0=IA，即R0是集合A上的恒等关系；(2)Rn+1=Rn·R．定义2.2.4（逆关系）设R是从集合A到B的二元关系，则从集合B到A的二元关系R–1：

–1

R={??R}(2.2.3)

称为R的逆关系．

定义2.3.1（自反关系、反自反关系）设R是集合A上的二元关系，若对任意a?A，都有aRa，即?R，则称R为A上自反的关系；若对任意a?A，都有aRa，即?R，则称R为A上反自反的关系．

定义2.3.2（对称关系、反对称关系）设R是集合A上的二元关系，对任意a，b?A，若有?R，就必有?R，则称R为A上对称的关系；若有?R，且?R，就必有b=a，则称R为A上反对称的关系．定义2.3.3（传递关系）设R是集合A上的二元关系，对任意a，b，c?A，若有?R，且?R，就必有?R，则称R为A上传递的关系．

定义2.3.4（自反闭包、对称闭包，传递闭包）设非空集合A上的二元关系R，若有A上的另一个二元关系R?满足：

(1)R?是自反的（对称的，传递的）；(2)R?R?；

(3)对A上任何包含R的自反（对称，传递）关系R??都有R??R??；则称关系R?为R的自反（对称，传递）闭包，记作r(R)（s(R)，t(R)）．

定义2.4.1（等价关系）设R是非空集合A上的二元关系，假使R是自反的、对称的和传递的，则称R是A上的等价关系．设R是一个等价关系，假使?R，称a等价于b，记作a~b．

定义2.4.2（等价类）设R是非空集合A上的等价关系，对任意a?A，令

[a]R={b?b?A且aRb}(2.4.1)则称集合[a]R为a关于R的等价类，简称a的等价类，简记作[a]或a．定义2.4.3（商集）设R是非空集合A上的等价关系，以R的所有等价类作为元素的集合，成为A关于R的商集，记作A/R．即

A/R={[a]R?a?A}(2.4.2)

定义2.4.4（划分块）设A是非空集合，若A的子集族?满足：(1)???；

(2)?中任何两个子集都不相交；(3)?中所有子集的并集就是A．

则称?为A的一个划分，称?中的元素为A的划分块．

定义2.5.1（相容关系）设R是非空集合A上的二元关系，假使R是自反的、对称的，则称R是A上的相容关系．

定义2.5.2（相容类）设R是非空集合A上的相容关系，B是A的子集，假使在B中的任意两个元素都是相关的，则称为由相容关系R产生的相容类．

最大相容类——R是A上的相容关系，B是相容类，若在差集A-B中没有一个元素能和B中所有元素都是相关的，则称B为最大相容类．

定义2.5.3（覆盖）设A是非空集合，若A的子集族?满足：(1)???；

(2)?中所有子集的并集就是A．

则称?为A的一个覆盖，称?中的元素为A的覆盖块．

定义2.5.4（完全覆盖）设集合A的子集族?={A1,A2,…,An}是A的覆盖，且对?中任意元素Ai，不存在其它元素Aj，使得Ai是Aj的子集，则称?为A的一个完全覆盖．

定义2.5.5（偏序关系）设R是非空集合A上的二元关系，假使R是自反的、反对称的和传递的，则称R是A上的偏序关系，或称序关系，记作?．设?是偏序关系，假使?a,b???，则记作a?b，读作a―小于等于‖b．

定义2.5.6（拟序关系）设R是非空集合A上的二元关系，假使R是反自反的和传递的，则称R是A上的拟序关系，记作?R，则称元素b盖住元素a．定义2.5.10（最大元、最小元、极大元、微小元）设?A，??为序集，集合B?A，存在元素b?B，

(1)若对任意a?B，都有a?b，则称b为B的最大元；(2)若对任意a?B，都有b?a，则称b为B的最小元；

(3)若对任意a?B，且b?a，都有a=b，则称b为B的极大元；(4)若对任意a?B，且a?b，都有a=b，则称b为B的微小元．

定义2.5.10（上界、下界、最小上界、上确界、最大下界、下确界）设?A，??为偏序集，集合B?A，存在元素b?A，

(1)若对任意a?B，都有a?b，则称b为B的上界；(2)若对任意a?B，都有b?a，则称b为B的下界；

(3)若集合C={b?b为B的上界}，则C的最小元称为B的最小上界或上确界；(4)若集合D={b?