【离散数学】.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}A。b和{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为集合，如