《离散数学》-教案.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 集合的概念集合不能精确定义集合可以描述为：一个集合把世间万物分成两类,一些对象属于该集合，是组成这个集合的成员，另一些对象不属于该集合可以说，由于一个集合的存在，世上的对象可分成两类，任一对象或属于该集合或不属于该集合，二者必居其一也只居其一直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员例如：方程x2－1＝0的实数解集合；26个英文字母的集合；坐标平面上所有点的集合；……集合通常用大写的英文字母A,B,C,…,来标记，元素通常用小写字母a,b,c,…,来表示。

例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等集合的表示方法：表示一个集合的方法通常有三种：列举法、描述法和归纳定义法1) 列举法 列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来在能清楚地表示集合成员的情况下可使用省略号例如 A={a，b，c，…，z}，Z={0，±1，±2，…}都是合法的表示2) 描述法 用谓词来概括集合中元素的属性来表示这个集合例如 B＝{x|x∈R∧x2－1＝0}表示方程x2－1＝0的实数解集许多集合可以用两种方法来表示，如B也可以写成{-1，1}但是有些集合不可以用列元素法表示，如实数集合3) 归纳定义法：1.3节再讨论属于、不属于：元素和集合之间的关系是隶属关系，即属于或不属于，属于记作∈，不属于记作例如A＝{a，{b，c}，d，{{d}}}，这里a∈A，{b，c}∈A，d∈A，{{d}}∈A，但bA，{d}Ab和{d}是A的元素的元素外延公理：两个集合A和B相等，当且仅当它们有相同的成员集合的元素是彼此不同的：如果同一个元素在集合中多次出现应该认为是一个元素如 {1，1，2，2，3}＝{1，2，3}。

集合的元素是无序的：如{1，2，3}＝{3，1，2}1.1.2 集合间的关系定义1.1.1 设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集这时也称B被A包含，或A包含B，记作BA称B是A的扩集包含的符号化表示为：BAx(x∈B→x∈A)如果B不被A包含，则记作BA例如 NZQRC，但ZN显然对任何集合A都有AA注意：属于关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系例如A＝{a，{a}}和{a}，既有{a}∈A，又有{a}A前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的定义1.1.2 设A，B为集合，如果BA且B≠A，则称B是A的真子集，记作BA如果B不是A的真子集，则记作BA真子集的符号化表示为：BABA∧B≠A例如 NZQRC，但NN为方便起见，所讨论的全部集合和元素是限于某一论述域中，即使这个论述域有时没有明确地指出，但表示集合元素的变元只能在该域中取值此论述域常用U表示，并称为全集定义1.1.3 不含任何元素的集合叫空集，记作空集可以符号化表示为＝{x|x≠x}例如{x|x∈R∧x2+1=0}是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。

定理1.1-1 空集是一切集合的子集证：对任何集合A，由子集定义有，右边的蕴涵式因前件为假而为真命题，所以也为真推论 空集是唯一的证：假设存在空集和，由定理6.1有，根据集合相等的定义，有含有n个元素的集合简称n元集，它的含有m(m≤n)个元素的子集叫做它的m元子集任给一个n元集，怎样求出它的全部子集呢？举例说明如下例1.1.1 A＝{1,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的子集：{a}A，a是A的元素：a∈A注意：不要写成{a}∈A和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－(B∪C)＝(A－B)∩( A－C)证对任意的x，x∈A－(B∪C) x∈A∧xB∪C x∈A∧┐(x∈B∨x∈C) x∈A∧(┐x∈B∧┐x∈C) x∈A∧xB∧xC (x∈A∧xB)∧(x∈A∧xC) x∈A－B)∧x∈A－C x∈(A－B)∩(A－C)所以 A－(B∪C)＝(A－B)∩( A－C)例：证明A∩E＝A证对任意的x，x∈A∩Ex∈A∧x∈Ex∈A(因为x∈E是恒真命题)，所以A∩E＝A注意：以上证明的基本思想是：设P，Q为集合公式，欲证P＝Q，即证PQ∧QP为真也就是要证对于任意的x有 x∈Px∈Q和x∈Qx∈P成立对于某些恒等式可以将这两个方向的推理合到一起，就是 x∈Px∈Q不难看出，集合运算的规律和命题演算的某些规律是一致的，所以命题演算的方法是证明集合恒等式的基本方法证明集合恒等式的另一种方法是利用已知的恒等式来代入例：证明A∪(A∩B)＝A证 A∪(A∩B)＝(A∩E)∪(A∩B)＝A∩(E∪B)＝A∩(B∪E)＝A∩E＝A例：证明等式A－B＝A∩～B证对于任意的x，x∈A－Bx∈A∧xBx∈A∧x∈～Bx∈A∩～B，所以A－B＝A∩～B。

注意：上式把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的例：证明(A－B)∪B＝A∪B证 (A－B)∪B＝(A∩～B)∪B＝(A∪B)∩(～B∪B)＝(A∪B)∩E＝A∪B例：证明命题A∪B＝BA∩B＝AA－B＝证(1) 证A∪B＝BAB，对于任意的x，x∈Ax∈A∨x∈Bx∈A∪Bx∈B(因为A∪B＝B)，所以AB2) 证ABA∩B＝A显然有A∩BA，下面证AA∩B，对于任意的x，x∈Ax∈A∧x∈Ax∈A∧x∈B(因为AB) x∈A∩B，由集合相等的定义有A∩B＝A3) 证A∩B＝AA－B＝A－B＝A∩～B＝(A∩B)∩～B(因为A∩B＝A)＝A∩(B∩～B)＝A∩＝4) 证A－B＝A∪B＝BA∪B＝B∪(A－B)＝B∪＝B注意：上式给出了AB的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简例：化简((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)解因为A∪BA∪B∪C，AA∪(B－C)，故有((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)＝(A∪B)－A＝B－A定义：两集合的环和（对称差）定义为：环和： 2. 环和与环积的性质：(1) ，(2) ， ， (3) ， ；(4) ， ，(5) 例：已知AB＝AC，证明B＝C。

证 已知AB＝AC，所以有A(AB)＝A(AC) (AA)B＝(AA)CB＝CB＝CB＝C3. 集合运算的文氏图表示注意：如果没有特殊说明，任何两个集合都画成相交的 幂集合定义：设是一个集合，的幂集是的所有子集的集合，即若是元集，则有个元素例：若，则；若，则对任意集合：，集合运算的顺序：为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：称广义交，广义并，幂集，绝对补运算为一类运算，交，并，补，环和，环积运算为二类运算一类运算优先于二类运算；一。