离散数学备课笔记.docx
《离散数学备课笔记.docx》由会员分享，可在线阅读，更多相关《离散数学备课笔记.docx（91页珍藏版）》请在冰点文库上搜索。
离散数学备课笔记
离散数学
主讲：
袁永红
第一篇绪言
1．计算机科学与离散数学
离散数学是了解和学习计算机科学、掌握和研究计算机科学的必需的理论基础。
2．离散数学之特征
离散数学是数学的一个分支，它以离散量作为其主要研究对象，如自然数、真假值、字母表等。
3．离散数学的内容
由于离散数学是以离散量作为其研究对象，故一切以离散现象作为其研究对象或作为其研究对象之一的数学均可属于离散数学，如集合论、代数结构、数理逻辑、图论等。
第二篇集合论
第一章集合论初步
1.1集合的基本概念
1.1.1集合及其元素
一些不同的确定的对象的全体称为集合，而这些对象称为集合的元素。
一般用带标号或不带标号的大写字母表示集合，如A、M、X1、B2等，一般用带标号或不带标号的小写字母表示集合的元素，如a1、b2、x、y等。
常用Z或I表示整数集合，用R表示实数集合。
为了表示一个集合由哪些元素组成，一般将集合的元素全部列出（元素间以逗号隔开）并左右用花括号括起，以表示由这些元素组成的集合．例如，集合A由元素a、b、c、d组成，则可写成
A=}a,b,c,d}
集合中的元素本身可以是一个集合。
例如集合{a,{b},{{a,c}}}有3个元素a、{b}和{{a,c}}。
集合中的元素具有如下性质：
（l）确定性。
也就是说，对集合A，任一元素a或属于此集合，或不属于此集合，两者必居其一。
若一元素a属于集合A，则用a∈A表示，若不属于A，则用aA表示；
（2）唯一性。
即元素在集合中最多只能出现一次。
注意：
集合{a,{a}}中有两个元素a和{a}，这两个元素并不相同，故并不违反唯一性。
（3）无序性。
即集合{a,b}和集合{b,a}相同。
集合若由有限个元素组成，则称有限集；集合若由无限个元素组成，则称无限集．如自然数集即为无限集，地球上人的集合则是有限集，特别地，对元素个数为零的集合称做空集，记以∅。
一个集合，如果它能包括人们所考虑的目标之内的所有元素，则此集合叫做全集，记以E。
前面已经提到集合的表示法，即集合A由元素a、b、c、d组成，可写为A={a,b,c,d}，这种表示法称为“枚举法”，也就是将集合所有元素一一列出．但有时也可只列出一部分元素，而其余部分可从前后关系中很显然地推出，如：
A={1,2,3,4,…｝
表示全体自然数集合，又如：
A={1,2,3,…,100}
表示从l到100的100个自然数所构成的集合．
前面所讨论的集合表示法称显式表示法，集合还可用另一种方法表示即隐式表示法（也称为描述法），这个方法是用一集合元素所具有的共同性质来刻画这个集合．如正偶数组成的集合A可写成A={x|x是正偶数}
1.1.2集合间的关系
集合间一般可有两种关系：
相等关系与包含关系。
定义1.1如果集合A与集合B的元素相同，则称这两个集合是相等的，记以A=B；否则，称这两个集合不相等，记以A≠B。
定义1.2集合A、B，如果当a∈A必有a∈B，则称B包含A，或称A包含于B，或称A是B的子集，记以BA或AB。
如果BA且存在b，使得b∈B但bA，则称B真包含A，或称A真包含于B，或称A是B的真子集，记以BA或AB。
例1.4设N={0,l,2,…｝,A={l,2,3,…,100}，则有AN，并且有AN。
例1.5设A={1,2,3}，B={1,2,3}，则有A=B。
例1.6设A={i|i为正整数}，B={j|j为正偶数}，则有BA，且BA。
对于集合的相等与包含关系，可用一种图即文氏图表示。
文氏图在表示集合相互间的关系时较为直观、形象，故目前被广泛应用．在文氏图中用一个平面中的区域表示一个全集，而对包含于全集内的集合用平面区域内的圈表示之．这样，全集内的集合间关系就可用平面区域内圆之间的关系表示．对于相等、包含等关系可以很形象地用文氏图表示，如图1.1所示．
对于相等与包含关系有下面的一些定理．
定理1.1对任一集合A，必有∅A。
即空集是任何集合的子集。
注意：
不能说空集是任何集合的真子集。
因为空集不是空集的真子集。
定理1.2对任一集合A，必有EA。
定理1.4有集合A与B，则A=B的充分必要条件是AB且BA。
补例下列正确的有（ABD）。
A.∅{∅}B.∅∈{∅}
C.{∅}{{∅}}D.{∅}∈{{∅}}
1.1.3集合代数
定义1.3由集合A、B中所有元素合并组成的集合，称为集合A与B的并集，记以AB,而称为并运算。
例1.7A={1,2,3,4}，B={3,4,5,6}，则
AB={1,2,3,4,5,6}
定义1.4由集合A、B所有的公共元素所组成的集合，称为集合A与B的交集，记以AB，而称为交运算。
例1.8A={1,3,5,7,9}，B={1,3,8,10}，则
AB={1,3}
定义1.5集合A、B若满足AB=∅，则称A与B是分离的，或称A与B不相交。
定义1.6由集合A、B中所有属于集合A而不属于B的元素所组成的集合，称为集合A对集合B的差集，记以A-B，而-称差运算。
例1.9A={a,b,c,d,e,f}，B={d,e,f,g,h}，则
A-B={a,b,c｝B-A={g,h}
定义1.7集合A的补集～A可定义为
～A=E-A
而～称为补运算，它是集合论中的一元运算。
例1.10设E={0,1,2,3,…}，A={0,2,4,6,…}，则
～A=E-A={1,3,5,7,…}
定义1.8集合A、B的对称差（或称布尔和）A+B可定义为
A+B=（A-B）（B-A）
而+称为对称差运算。
（有些书上将+写成⊕）
例1.11设A={1,2,3,4}，B={3,4,5,6}，则
A+B={l,2,5,6}
由例中可以看出A+B即为A、B的所有非公共元素所组成的集合。
到此为止，定义了四种二元运算，即并运算、交运算、差运算和对称差运算，以及一个一元运算：
补运算．这五种运算可用文氏图表示，如图1.2所示。
在这五种运算中，下面着重讨论并、交、补三种运算的基本公式．
由定义可知，并、交运算满足交换律，即
AB=BA
AB=BA
由定义可知，并、交运算满足结合律，即
A（BC）=（AB）C
A（BC）=（AB）C
由定义还可知，并、交运算满足分配律，即
A（BC）=（AB）（AC）
A（BC）=（AB）（AC）
由定义还可以得到有关空集、全集及补集的几个公式，它包括同一律：
A∅=AAE=A
互补律：
A～A=EA～A=∅
零一律：
AE=EA∅=∅
等幂律：
AA=AAA=A
吸收律：
A（AB）=AA（AB）=A[要特别记忆]
双补律：
～（～A）=A～E=∅~∅=E
德·摩根定律
～（AB）=～A～B[要特别记忆]
～（AB）=～A～B[要特别记忆]
到此为止，得到了有关集合代数的21个公式，下面举例说明这些公式的应用。
例1.13设A、B、C为任意3个集合，已知AB=AC,AB=AC，试证B=C。
证明：
B=B（AB）
=B（AC）
=（BA）（BC）
=（AC）（BC）
=（AB）C
=（AC）C
=C
例1.14化简（（ABC）（AB））（A（AC））。
解：
（（ABC）（AB））（A（AC））
=（AB）A
=A
补例：
化简A～（～AB）
解：
A～（～AB）
=A（～（～A）～B）
=A（A～B）
=A
补例：
化简A～（A～B）
A～（A～B）
=A（～A～（～B））
=A（～AB）
=（A～A）B
=∅B
=∅
1.2幂集、n元有序组及笛卡儿乘积
1.2.1幂集
定义1.9由集合A的所有子集（包括空集及A本身）所组成的集合称为A的幂集，记以2A或ρ（A）。
例1.15A={a,b}，则ρ（A）={∅,{a},{b},A}。
例l.16A={1,2,3}，则
ρ（A）={∅,{1},{2},{3},{1,2},}l,3},{2,3},A}。
补例求下列情况下的ρ（A）。
（1）A=∅
（2）A={∅}（3）A={∅,{∅}}
（4）A={a,∅}（5）A={a,{b}}（6）A={a,{a}}
解：
（1）ρ（A）={∅}
（2）ρ（A）={∅,A}
（3）ρ（A）={∅,{∅},{{∅}},A}
（4）ρ（A）={∅,{a},{∅},A}
（5）ρ（A）={∅,{a},{{b}},A}
（6）ρ（A）={∅,{a},{{a}},A}
对于幂集有下面的定理．
定理1.5若集合A为由n个元素所组成的有限集，则ρ（A）为有限且由2n个元素组成。
定义1.10两个按一定次序排列的客体a、b组成一个有序序列，称为有序偶，并记以（a,b），有些书上记以。
由定义可知，有序偶刻画了两个客体间的次序，它并不表示由两个元素所组成的集合．在很多情况下客体间的次序是很重要的，如在一个平面直角坐标系中，点（x,y）一般并不与（y,x）相等。
有序偶（a,b）中的a、b分别称为（a,b）的第一客体与第二客体。
定义1.11有序偶（a,b）与（c,d），如果有a=c，b=d，则说（a,b）与（c,d）是相等的。
由有序偶的相等性可以看出，两个有序偶只有当其两个客体相同而且次序也相同时才相等。
将有序偶推广，可以得到n元有序组。
定义1.12n个（n>l）按一定次序排列的客体a1、a2、…、an组成一个有序序列，称为n元有序组，并记以（a1,a2,…,an）。
定义1.13n元有序组（a1,a2,…,an）与（b1,b2,…,bn）如果有
ai=bi（i=1,2,…,n）
则说（a1,a2,…,an）与（b1,b2,…,bn）是相等的。
同样，n元有序组（a1,a2,…,an）中的ai称为此n元有序组的第i个客体（i=1,2,…,n）。
1.2.3笛卡儿乘积
设有两个集合A与B，用A与B的元素组成有序偶，以A的元素作为有序偶的第一个客体，以B的元素作为有序偶的第二个客体，用这种办法所组成的所有有序偶的全体构成一个集合，此集合称为A与B的笛卡儿乘积，可记为A╳B。
由此可见，两个集合A、B的笛卡儿乘积是以一些有序偶为元素所组成的集合，这些有序偶的第一个客体取自集合A，第二个客体取自集合B，这样，可以对笛卡儿乘积下一个形式化的定义．
定义1.14集合A、B的笛卡儿乘积可表示为
A╳B={（a,b）|a∈A,b∈B}
定义1.15集合A1、A2、…、An的笛卡儿乘积可表为
A1╳A2╳…╳An={（x1,x2…,xn）}xi∈Ai,i=1,2,…,n}
n个集合A的笛卡儿乘积
A╳A╳…╳A记作An，例如A2=A╳A。
例1.21设A={1,2}，B={a,b}，C={α,β}，则
A╳B={（1,a）,（l,b）,（2,a）,（2,b）}
A╳B╳C={（l,a,α）,（l,a,β）,（1,b,α）,（1,b,β）,
（2,a,α）,（2,a,β）,（2,b,α）,（2,b,β）}
A╳A={（1,1）,（1,2）,（2,1）,（2,2）}
注意：
笛卡儿乘积中的元素最好按一定次序写，以免漏写或多写。
第二章关系
2.1关系的基本概念
2.1.1关系及其定义
例2.1设一旅馆有n个房间，每个房间可住两个旅客，所以一共可以住2n个旅客。
在旅馆内，旅客与房间有一定关系，讨论关系：
“某旅客住在某房间”，用R表示这种关系，为讨论方便起见，设n=3，此时表示旅馆共有3间房间，分别记以1、2、3，而此时旅馆共住6个旅客，分别记以a、b、c、d、e、f，这些旅客住房的示意图如图2.1所示。
由图2.1可以很清楚地看出，满足R的所有关系如下：
aR1,bR1,cR2,dR2,eR3,fR3
由此可以看出：
（1）满足R的关系pRq可看成是一个有序偶：
（p,q），如上面aR1可写成有序偶：
（a,l）。
（2）满足R的所有关系可看成是一个有序偶的集合，这个集合即可叫R，上例中R即为
R={（a,1）,（b,1）,（c,2）,（d,2）,（e,3）,（f,3）}
（3）上面这种关系称为二元关系，因为它仅牵涉到两个客体间的关系．当然，还可以有三元关系、四元关系及多元关系存在。
可以用有序偶的集合定义一个关系亦即是说关系是一些有序偶的集合，下面对此做进一步说明。
（4）在上面的例子中若令A={a,b,c,d,e,f}，B={1,2,3}，则此例中关系的每一元素均属于A╳B，亦即R是A╳B的子集，或可写为RA╳B。
此时称此关系为从A到B的关系R，这样，可以给出关系的正式定义：
定义2.1从集合A到集合B的一个关系R是A╳B的一个子集。
关系R中有序偶第一个客体所允许选取对象的集合称为关系R的定义域，记以D（R），第二个客体所允许选取对象的集合称为关系R的值域，记以C（R）。
在特殊情况下，当D（R）=C（R）时，并且此时设D（R）=C（R）=M,M为一集合，此时称此关系为集合M上的关系。
例2.2整数集Z上的“>”关系可定义如下：
>={（x,y）|x∈Z,y∈Z且x>y}
从此例可以看出：
（35,24）∈>，但（24,35）>，此关系中有序偶的第一、第二客体均取自相同的集合Z，故关系>称为集合Z上的关系。
与集合论中情况类似，如果从X到Y不存在某种关系R，则称此种关系为空关系，如果X的每个元素到Y的每个元素间均具有某种关系，则称此关系为全关系．从X到Y的全关系即为X╳Y。
还可以用类似的方法定义多元关系．
定义2.2由集合X1、X2、…Xn，所确定的n元关系是X1╳X2╳…╳Xn的一个子集．由此定义可以看出，n元关系是一些n元有序组的集合。
2.1.2关系的图的表示法
通常可以用图来刻画关系。
一个集合X={x1,x2,…,xn}上的关系R可用一关系图表示之．集合X中元素可用图中结点表示；关系R的有序偶（xi,xj）可用图中从结点xi到结点xj的有向边表示．这样，即可将关系用图表示。
这种表示方法可用下面例子说明．
例2.3设有6个程序p1、p2、…、p6，它们间有一定的调用关系R：
p1Rp2、p3Rp4、p4Rp5、p5Rp2、p2Rp6、p3Rp1，这个关系是集合P={p1,p2,…,p6}上的关系，并且有R={（p1,p2）,（p3,p4）,（p4,p5）,（p5,p2）,（p2,p6）,（p3,p1）}
对于这样的一个关系可用一个图表示之，这个图如图2.2所示。
有些书上用圆圈而不是实心圆点表示结点。
关系还可以用矩阵表示，在上例中可用下面的矩阵MR表示：
2.2关系的运算
2.2.1关系的交、并、补、差
由于关系是一些有序偶的集合，这样，有关集合的运算如集合的交、并、补、差等在关系中也是适用的．例如设X={a,b,c｝,Y={1,2}，且有从X到Y的关系R={（a,1）,（b,2）,（c,1）}，S={（a,l）,（b,1）,（c,1）}，此时则有
RS={（a,1）,（b,1）,（b,2）,（c,1）}
RS={（a,1）,（c,1）}
X╳Y={（a,1）,（a,2）,（b,1）,（b,2）,（c,1）,（c,2）}
～R=（X╳Y）-R={（a,2）,（b,l）,（c,2）}
R-S={（b,2）}
上面这些关系的运算结果都建立了新的关系，而且也都是从X到Y的关系．以前有关集合运算的一些公式在关系中也同样适用。
除了上述的几种运算以外，在关系中尚有两种新的运算，它们是复合运算与逆运算，其结果所组成的关系称复合关系与逆关系，现分别介绍于下。
2.2.2复合关系
定义2.3设R是一个从X到Y的关系，S是一个从Y到Z的关系，则R与S的复合关系：
R◦S可定义为
R◦S={（x,z）|x∈X，z∈Z，至少存在一个y∈Y有（x,y）∈R且（y,z）∈S}
这个复合关系是一个从X到Z的关系。
有些书上将符号“◦”写成“·”。
补例设R={（1,2）,（2,2）,（3,4）,（4,2）}
S={（1,3）,（2,5）,（3,1）,（3,4）,（4,4）}
求：
R◦S、S◦R、R◦R、S◦S。
解：
R◦S={（l,5）,（2,5）,（3,4）,（4,5）}
S◦R={（1,4）,（3,2）,（4,2）}
R◦R={（1,2）,（2,2）,（3,2）（4,2）}
S◦S={（1,1）,（1,4）,（3,3）,（3,4）,（4,4）}
定理2.1设R、S、T分别表示从X到Y、Y到Z、Z到U的关系，则有
（R◦S）◦T=R◦（S◦T）
由于关系的复合运算满足结合律，故可以将复合运算中的括号除去，亦即有
（R◦S）◦T=R◦（S◦T）=R◦S◦T
对于某个关系R自己与自己的复合运算是R◦R，可以用R2表示，同理R◦R◦R可用R3表示，因此可以用下面的方式来定义关系的幂。
定义2.4设有一个集合X上的关系R，则Rn可定义如下：
（1）R1=R;
（2）Rn+1=Rn◦R
由定义，很容易就能知道
Rm◦Rn=Rm+n
（Rm）n=Rmn
2.2.3逆关系
定义2.5设R是一个从X到Y的关系，即R={（x,y）|x∈X,y∈Y}，则从Y到X的关系R-1:
R-1={（y,x）|x∈X,y∈Y}
称为R的逆关系。
例2.6设X={l,2,3}，Y={a,b,c}，且设R是从X到Y的关系：
R={（l,a）,（2,b）,（3,c）}
则有从R的逆关系
R-1={（a,1）,（b,2）,（c,3）}
关系的逆关系满足下面的定理．
定理2.2设R、S分别是从X到Y及Y到Z的关系，则有
（1）（R-1）-1=R
（2）（R◦S）-1=S-1◦R-1[要特别记忆]
2.3关系的重要性质
定义2.6在集合X上的关系R，如对任意x∈X，有（x,x）∈R，则称R是自反的。
定义2.7在集合X上的关系R，如对任意x∈X，有（x,x）R，则称R是反自反的。
例2.8在整数集Z上的关系“≤”是自反的，不是反自反的。
例2.9在整数集Z上的关系“<”是反自反的，不是自反的。
例2.10在集合X={1,2,3,4}上的关系R:
R={（1,1）,（1,2）,（3,4）,（2,2）,（4,2）}
此关系既不是自反的也不是反自反的，由此可知，一个关系的自反性与反自反性可以都不存在。
一个关系的自反性在图形表示法中相当于一个关系图中的每个结点均有环出现，而一个关系的反自反性相当于一个关系图中的每个结点均无环出现。
定义2.8在集合X上的关系R，如果有（x,y）∈R，必有（y,x）∈R，则称R是对称的。
定义2.9在集合X上的关系R，如果有（x,y）∈R且x≠y，必有（y,x）R，则称R是反对称的。
例2.12在整数集Z上的关系“<”及“≤”均是反对称的。
例2.13在集合X={1,2,3,4}上的关系R:
R={（l,2）,（2,1）,（3,4）,（4,2）}
此关系既不是对称的也不是反对称的。
关系的对称性在图形表示中相当于关系图中两个结点间如有有向边相连，则一定有方向相反的两条有向边连接；一个关系的反对称性相当于关系图中两个结点间如有有向边相连则一定只有一条边。
定义2.10在集合X上的关系R，对任意（x,y）∈R且（y,z）∈R，必有（x,z）∈R，则称R是传递的。
例2.15整数集Z上的“<”、“≤”关系均是传递的。
例2.17整数集Z上的“<”关系是反自反、反对称的，然而是传递的。
例2.18整数集Z上的“相等”关系是自反的、对称的，同时又是传递的。
例2.19一些人所组成的集合上的“父子”关系是反自反、反对称的，亦是非传递的。
例2.20用图2.5所表示出来的在集合X={1,2,3}上的关系的5个图形，从图中可以清楚地看出：
（l）R1是自反的、对称的，又是传递的（它是一个全关系）。
（2）R2是反自反的、反对称的。
（3）R3是对称的。
（4）R4是自反的、反对称的、传递的。
（5）R5是反自反的、对称的、反对称的、传递的（它是一个空关系）。
2.4关系上的闭包运算
定义2.11设R是集合X上的一个关系，则R的自反（对称、传递）闭包是一个满足下列条件的关系R’:
（1）R’是自反的（对称的、传递的）;
（2）R’R;
（3）设R”是自反的（对称的、传递的）且R”R，则必有R”R’。
通常用r（R）表示R的自反闭包；用s（R）表示R的对称闭包；用t（R）表示R的传递闭包。
例2.21整数集Z上的“<”关系的自反闭包是“≤”关系；它的对称闭包是“≠”关系；它的传递闭包即是它自身。
定理2.3设R是集合X上的关系，则
r（R）=R{（x,x）|x∈X}
定理2.4设R是集合X上的关系，则s（R）=RR-1。
定理2.6设R是有限集合X上的关系，并设X有n个元素,则
t（R）=RR2R3…Rn
传递闭包也可从关系图中观察得出。
补例设有集合A={1,2,3}，A上的关系
R={（1,2）,（2,1）,（3,1）}，求r（R），s（R）和t（R）。
解：
r（R）=R{（1,1）,（2,2）,（3,3）}
={（1,2）,（2.1）,（3,1）,（1,1）,（2,2）,（3,3）}
R-1={（2,1）,（1,2）,（1,3）}
s（R）=RR-1={（1,2）,（2,1）,（3,1）,（1,3）}
R2={（1,1）,（2,2）,（3,2）}
R3={（1,2）,（2,1）,（3,1）}
t（R）=RR2R3={（1,2）,（2,1）,（3,1）,（1,1）,（2,2）,（3,2）}
2.5次序关系
定义2.12集合X上的关系R如果是自反的、反对称的、传递的，则称R在X上是偏序的或称R是集合X上的偏序关系。
而称集合X为R的偏序集，用（X,R）表示。
一般地用符号“≤”表示偏序（注意，此符号在这里并不表示为小于或等于）。
例2.26由集合A所组成的幂集ρ（A）上的关系“”是自反的、反对称的又是传递的，故它是偏序的。
例2.27整数集Z上的“≤”（不是偏序的符号）是偏序关系。
例2.28集合X={2,3,6,8}上的“整除”关系R={（2,2）,（2,6）,（2,8）,（3,3）,（3,6）,（6,6）,（8,8）}是偏序的。
定义2.16设集合X上有一个偏序关系“≤”且设Y是X的一个子集，则
（1）如果存在一个元素y∈Y对每个y’∈Y均有y’≤y，则称y是Y的最大元素；如果均有y≤y’，则称y是Y的最小元素。
（2）如果存在一个元素y∈Y且在Y中不存在元素y’有y≠y’并且y≤y’，则称y是Y的极大元素；如果Y中不存在元素y’有y≠y’并且y’≤y，则称y是Y的极小元素。
（3）如果存在一个元素x∈X，对每个y∈Y均有y≤x，则称x是Y的上界；如果均有x≤y，则称x是Y的下界。
（4）如果x∈X是Y的上界且对每一个Y的上界x’均有x≤x’，则称x是Y的上确界（或称最小上界）；如果x是Y的下界且对每一个Y的下界x’均有x’≤x，则x是Y的下确界（或称最大下界）。
这个定义所确定的最大元素，极大元素、上界、上确界（相应地：
最小元素、极小元素、下界、下确界）等4个概念是有明确区
升级会员 