《离散数学》-教案.doc

离散数学教案第一章 集合与关系集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的一个分支。G. Cantor(康脱)是作为数学分支的集合论的奠基人。1870年前后，他关于无穷序列的研究导致集合论的系统发展。1874年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。1878年，他引进了两个集合具有相等的“势”的概念。然而，朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901年罗素发现了有名的罗素悖论。1932年康脱也发表了关于最大基数的悖论。集合论的现代公理化开始于1908年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。另外一种系统是冯诺伊曼-伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理一起称为ZFC系统。一、学习目的与要求本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关系运算方法，为学习后续章节打下良好基础。二、知识点1集合的基本概念与表示方法；2集合的运算；3序偶与笛卡尔积；4关系及其表示、关系矩阵、关系图；5关系的性质，符合关系、逆关系；6关系的闭包运算；7集合的划分与覆盖、等价 关系与等价类；相容关系；8序关系、偏序集、哈斯图。三、要求1识记集合的层次关系、集合与其元素间的关系，自反关系、对称关系、传递关系的识别，复合关系、逆关系的识别。2领会领会下列概念：两个集合相等的概念几证明方法，关系的闭包运算，关系等价性证明。1.1 集合论的基本概念与运算1.1.1 集合的概念集合不能精确定义。集合可以描述为：一个集合把世间万物分成两类,一些对象属于该集合，是组成这个集合的成员，另一些对象不属于该集合。可以说，由于一个集合的存在，世上的对象可分成两类，任一对象或属于该集合或不属于该集合，二者必居其一也只居其一。直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。例如：方程x210的实数解集合；26个英文字母的集合；坐标平面上所有点的集合；集合通常用大写的英文字母A,B,C,来标记，元素通常用小写字母a,b,c,来表示。例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。集合的表示方法：表示一个集合的方法通常有三种：列举法、描述法和归纳定义法。(1) 列举法 列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。在能清楚地表示集合成员的情况下可使用省略号。例如 A=a，b，c，z，Z=0，1，2，都是合法的表示。(2) 描述法 用谓词来概括集合中元素的属性来表示这个集合。例如 Bx|xRx210表示方程x210的实数解集。许多集合可以用两种方法来表示，如B也可以写成-1，1。但是有些集合不可以用列元素法表示，如实数集合。(3) 归纳定义法：1.3节再讨论。属于、不属于：元素和集合之间的关系是隶属关系，即属于或不属于，属于记作，不属于记作。例如Aa，b，c，d，d，这里aA，b，cA，dA，dA，但bA，dA。b和d是A的元素的元素。外延公理：两个集合A和B相等，当且仅当它们有相同的成员。集合的元素是彼此不同的：如果同一个元素在集合中多次出现应该认为是一个元素。如 1，1，2，2，31，2，3。集合的元素是无序的：如1，2，33，1，2。1.1.2 集合间的关系定义1.1.1 设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作BA。称B是A的扩集。包含的符号化表示为：BAx(xBxA)。如果B不被A包含，则记作BA。例如 NZQRC，但ZN。显然对任何集合A都有AA。注意：属于关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如Aa，a和a，既有aA，又有aA。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的。定义1.1.2 设A，B为集合，如果BA且BA，则称B是A的真子集，记作BA。如果B不是A的真子集，则记作BA。真子集的符号化表示为：BABABA。例如 NZQRC，但NN。为方便起见，所讨论的全部集合和元素是限于某一论述域中，即使这个论述域有时没有明确地指出，但表示集合元素的变元只能在该域中取值。此论述域常用U表示，并称为全集。定义1.1.3 不含任何元素的集合叫空集，记作。空集可以符号化表示为x|xx。例如x|xRx2+1=0是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。定理1.1-1 空集是一切集合的子集。证：对任何集合A，由子集定义有，右边的蕴涵式因前件为假而为真命题，所以也为真。推论 空集是唯一的。证：假设存在空集和，由定理6.1有，。根据集合相等的定义，有。含有n个元素的集合简称n元集，它的含有m(mn)个元素的子集叫做它的m元子集。任给一个n元集，怎样求出它的全部子集呢？举例说明如下。例1.1.1 A1,2,3，将A的子集分类：0元子集，也就是空集，只有一个：；1元子集，即单元集：1，2，3；2元子集：1,2，1,3，2,3； 3元子集：1,2,3。一般地说，对于n元集A，它的0元子集有个，1元子集有个，m元子集有个，n元子集有个。子集总数为个。全集与空集在本章中起重要作用，注意掌握它们的基本概念。注意：与的联系与区别。(1) 表示集合的元素（可以为集合）与集合本身的从属关系，(2) 表示两个集合之间的包含关系。例如：对于集合A=a,b,c,a是A的子集：aA，a是A的元素：aA。注意：不要写成aA和aA。，但；是一元集，而不是空集。，。1.1.3 集合的运算集合的交、并和差运算1. 集合交、并、差运算的定义（注意集合运算与逻辑运算的对应关系）定义 设和是集合，(1) 和的交记为，定义为：；(2) 和的并记为，定义为：；(3) 和的差记为，定义为：。例：设，则，定义：如果是两个集合，那么称和是不相交的。如果是一个集合的族，且中的任意两个不同元素都不相交，那么称是（两两）不相交集合的族。2. 集合的并和交运算的推广（广义交、广义并）个集合 ，无穷可数个集合： ，一般情形： （），3. 集合交、并、差运算的性质：(1) 交换律 ， ，(2) 结合律 ， .(3) 分配律 ， (4) 幂等律 , ,(5) 同一律 , ，(6) 零 律 ,(7) 吸收律 ， ，(8) 德摩根律 (9) (a) , (b) , (c), (d),(e) 若，,则，,(f) 若，则, (g) 若，则，(h) 。证：利用运算的定义（与逻辑运算的关系）或已证明的性质。 集合的补运算1. 集合的补运算的定义定义：设是论述域而是的子集，则的（绝对）补为：当且仅当和。2. 集合补运算的性质：(1) 矛盾律 ； (2) 排中律 ；(3) 德摩根律 ， ， ， ；(4) 双重否定律（的补的补是）：；(5) 若，则。例：证明A(BC)(AB)( AC)。证对任意的x，xA(BC) xAxBC xA(xBxC) xA(xBxC) xAxBxC (xAxB)(xAxC) xAB)xAC x(AB)(AC)所以 A(BC)(AB)( AC)。例：证明AEA。证对任意的x，xAExAxExA(因为xE是恒真命题)，所以AEA。注意：以上证明的基本思想是：设P，Q为集合公式，欲证PQ，即证PQQP为真。也就是要证对于任意的x有 xPxQ和xQxP成立。对于某些恒等式可以将这两个方向的推理合到一起，就是 xPxQ。不难看出，集合运算的规律和命题演算的某些规律是一致的，所以命题演算的方法是证明集合恒等式的基本方法。证明集合恒等式的另一种方法是利用已知的恒等式来代入。例：证明A(AB)A。证 A(AB)(AE)(AB)A(EB)A(BE)AEA。例：证明等式ABAB。证对于任意的x，xABxAxBxAxBxAB，所以ABAB。注意：上式把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。例：证明(AB)BAB证 (AB)B(AB)B(AB)(BB)(AB)EAB。例：证明命题ABBABAAB。证(1) 证ABBAB，对于任意的x，xAxAxBxABxB(因为ABB)，所以AB。(2) 证ABABA。显然有ABA，下面证AAB，对于任意的x，xAxAxAxAxB(因为AB) xAB，由集合相等的定义有ABA。(3) 证ABAAB。ABAB(AB)B(因为ABA)A(BB)A。(4) 证ABABB。ABB(AB)BB。注意：上式给出了AB的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。例：化简(ABC)(AB)(A(BC)A)。解因为ABABC，AA(BC)，故有(ABC)(AB)(A(BC)A)(AB)ABA。定义：两集合的环和（对称差）定义为：环和： 2. 环和与环积的性质：(1) ，(2) ， ， (3) ， ；(4) ， ，(5) 例：已知ABAC，证明BC。证 已知ABAC，所以有A(AB)A(AC) (AA)B(AA)CBCBCBC。3. 集合运算的文氏图表示注意：如果没有特殊说明，任何两个集合都画成相交的。 幂集合定义：设是一个集合，的幂集是的所有子集的集合，即。若是元集，则有个元素。例：若，则；若，则。对任意集合：，。集合运算的顺序：为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：称广义交，广义并，幂集，绝对补运算为一类运算，交，并，补，环和，环积运算为二类运算。一类运算优先于二类运算；一类运算之间由右向左顺序进行；二类运算之间由括号决定先后顺序。1.2 关系及其表示1.2.1集合的笛卡儿积与二元关系定义 1 由两个元素x和y（允许x=y）组成的序列记作，称为二重组或有序对或序偶，其中x是它的第一元素（分量），y是它的第二元素（分量）。有序对具有以下性质：1当xy时，； 2=的充分必要条件是x=u且y=v。注意：这些性质是二元集x,y所不具备的。例如当xy时有x,y=y,x。原因在于有序对中的元素是有序的，而集合中的元素是无序的。例1 已知=，求x和y。解 由有序对相等的充要条件有x+2=5，2x+y=4，解得x=3，y=-2。定义2 设是个元素，定义为重组。注意：重组是一个二重组，其中第一个分量是重组。如代表而不代表，按定义后者不是三重组，并且。重组与相等当且仅当，。定义3 设A，B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积（叉积），记作AB。笛卡儿积的符号化表示为AB=|xAyB。集合（）的叉积记为或，定义为例2 设A=a,b, B=0,1,2，则AB=,；BA=,。由排列组合的知识不难证明，如果|A|=m，|B|=n，则|AB|=mn。笛卡儿积的运算性质(1).对任意集合A，根据定义有 A=, A=；(2).一般地说，笛卡儿积运算不满足交换律，即ABBA(当ABAB时)；(3)笛卡儿积运算不满足结合律，即(AB)CA(BC)(当ABC时)；(4).笛卡儿积运算对并和交运算满足分配律，即A(BC)=(AB)(AC)； (BC)A=(BA)(CA)；A(BC)=(AB)(AC)； (BC)A=(BA)(CA)。我们证明其中第一个等式。证 任取，A(BC) xAyBCxA(yByC)(xAyB)(xAyC)ABAC(ABAC)所以有 A(BC) = (AB)(AC)。(5)ACBDABCD性质5的证明和性质4类似，也采用命题演算的方法。注意：性质5的逆命题不成立，可分以下情况讨论。(a) 当A=B=时，显然有AC和BD成立。(b) 当A且B时，也有AC和BD成立。证明如下：任取xA，由于B,必存在yB，因此有xAyBABCDxCyDxC，从而证明了AC。同理可证BD。(c) 当A=而B时，有AC成立，但不一定有BD成立。反例：令A=，B=1，C=3，D=4。(d) 当A而B=时，有BD成立，但不一定有AC成立。反例类似于(c)。例3 设A=1,2,求P(A)A。解 P(A)A=,1,2,1,21,2=,例4 设A，B，C，D为任意集合，判断以下命题是否为真，并说明理由。(1) AB=ACB=C； (2) A-(BC)=(A-B)(A-C)；(3) A=BC=DAC=BD； (4) 存在集合A，使得AAA。解(1) 不一定为真。当A=，B=1,C=2时，有AB=AC，但BC。(2) 不一定为真。当A=B=1,C=2时有A-(BC)=1=1，(A-B)(A-C)= 1=(3) 为真。由等量代入的原理可证。(4) 为真。当A=时有AAA成立。 定理1：若都是有限集合，则。定义4 如果一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对；（2）集合是空集；则称该集合为一个二元关系，记作R。二元关系也可简称为关系。对于二元关系，若，则称有关系，可记作；若，则记作。一般地，因此。例1 ，则是二元关系，不是二元关系，只是一个集合，除非将a和b定义为有序对。根据以上记法可以写成，等。定义5 设为集合，的任何子集所定义的二元关系叫做从到的二元关系，特别地，当时，则叫做上的二元关系。的子集称为上的一个元关系，当时称为上的一个元关系。例2 ,，那么，等都是从到的二元关系，而其中和同时也是上的二元关系。注：可把到的二元关系看成是上的二元关系或上的二元关系。二元关系的数目：集合上的二元关系的数目依赖于中的元素数。如果，那么，的子集就有个。每一个子集代表一个上的二元关系，所以上有个不同的二元关系。例如，则上有个不同的二元关系。如果，则，因此上有个不同的元关系。一些重要关系：(1) 空关系：若，则称为空关系；(2) 全域关系：(3) 恒等关系：上的二元关系称为恒等关系。(4) 小于或等于关系：，这里；(5) 上的整除关系：，这里（非零整数集）；(6) 上的包含关系：，这里是集合族。例3 设，则，上的包含关系：。类似的还可以定义大于等于关系，小于关系，大于关系，真包含关系等等。关系是有序对的集合，因此对它可进行集合运算，运算结果定义一个新的关系。例如：设和是给定集合上的关系，则，分别称为关系与的并关系，交关系，差关系和R的补关系。这样一来，可以从已知关系派生出各种新关系。 二元关系到的二元关系可以用一个图来形象地表示。定义6 设是到的一个二元关系，则叫着关系的前域，叫着关系的陪域；称为关系的定义域；称为关系的值域。关于关系的定义域、值域的一些性质：；。证明 （证明第一个式子，其余类似）1.2.2关系矩阵与关系图(1) 集合表示法：非空关系都是元素为有序对的集合。(2) 关系图：设，是上的关系，令图，其中顶点集合，边集为，对于，满足，则称图为的关系图，记作。(3)关系矩阵：设，是上的关系，令，则称为关系的关系矩阵，记作。例 空关系的关系矩阵为全矩阵：； 全域关系的关系矩阵为全矩阵，记为；相等关系的关系矩阵为单位矩阵：。基于关系与关系矩阵互相唯一决定的特性，可用关系矩阵有效地刻画关系的许多性质。如对于有限集A上的任意关系与：；。1.3关系的运算1.3.1关系的逆定义1 设是从到的二元关系，关系的逆（的逆关系）记为，定义如下：当上的关系具有对称性时，。相等关系的逆是相等关系；空关系的逆是空关系；全域关系的逆是全域关系。列举法：把中每个有序对的第一和第二成分都加以交换，就可得到逆关系的所有元素。对和来说，这意味着。关系矩阵：将的行和列交换即可得到，即（表示的转置）。关系图：颠倒的关系图中的每条弧（有向边）的箭头，就得到的关系图。逆关系的性质：(1) 设都是从到的二元关系，则(a) ；(b) ；(c) ；(d) ；(e) ，（）； (f) ；(2) 设是从到的关系，是从到的关系，则。1.3.2关系的合成定义2 设是从到的关系，是从到的关系，则与的合成（右复合）为从到的关系，记为或（其中表示合成运算），定义为。例1 设，是从到的关系，是从到的关系：，。分别用列举法、图示法、关系矩阵表示关系的合成，。例2 设，和都是上的二元关系，如果，分别用列举法、图示法、关系矩阵表示关系的合成，等。合成关系的性质：(1) 设是从到的关系，分别是上的相等关系，则；(2) 如果关系的值域与的定义域的交集为空集，则合成关系是空关系；(3) 关系的合成关于交和并的分配律：设是从到的关系，是从到的关系，是从到的关系，则(a) ，(b) ；(c) ，(d) ；(4) 关系的合成满足结合律：设分别是从到，到，到的关系，则。1.3.3 关系的幂定义3设是集合上的二元关系，为任一自然数，则的次幂记为，定义为：(1) 为上的相等关系， (2) 。关系的幂运算的性质：(1) 对上的任意关系有：，；(2) 设是集合上的二元关系，则，；(3) 设，是集合上的一个二元关系，则存在和，使；(4) 循环性质：设是集合上的二元关系，若存在和，使，则(a) 对所有，； (b) 对所有，（其中）；(c) 令，则的每一次幂是的元素，即对，。关系的幂的计算：给定上的关系和自然数，怎样计算呢？若是或，结果是很简单的。下面考虑的情况。如果是用集合表达式给出的，可以通过次合成计算得到。如果是用关系矩阵给出的，则的关系矩阵是，即个矩阵之积。与普通矩阵乘法不同的是，其中的相加是逻辑加，即。如果R是用关系图给出的，可以直接由图得到的关系图。的顶点集与相同。考察的每个顶点，如果在中从出发经过步长的路径到达顶点，则在中加一条从到的边。当把所有这样的边都找到以后，就得到图。例3 设，求的各次幂，分别用矩阵和关系图表示。解 的关系矩阵为，则的关系矩阵分别是，因此，。所以可以得到，而，即的关系矩阵为。至此，各次幂的关系矩阵都得到了。用关系图的方法得到的关系图如下图所示。合成关系的矩阵表达二元集上的布尔运算： ，； ，； ，； ，； ，； ，； 配合的其他性质(结合律、分配律等)可计算更复杂的式子。注 关于上述两个运算构成二元数域。-矩阵的布尔运算：对于的矩阵，定义下列运算：，；对和的矩阵和：。例4 对全矩阵，全矩阵有零律：，