集合论与图论zst08[1]

离散数学教程（集合论与图论）离散数学：计算机科学与技术的数学基础课内容：集合论，图论，组合数学，代数结构，数理逻辑集合论:（第1-4章）组合数学初步:（第5-7章）图论:（第8-11章）教师介绍⏹教师：吴永辉博士副教授⏹简历：⏹1984-1988 上海科技大学计算机系本科⏹1988-1991 复旦大学计算机系硕士⏹1991-2003 华东师范大学计算机系工作⏹1998-2001 复旦大学计算机系博士⏹2003-复旦大学计算机系工作⏹答疑E-mail: yhwu@《集合论与图论》课件制作软件⏹Microsoft PowerPoint⏹MathType Equation《集合论与图论》课程大纲⏹课程性质与目的⏹教学内容与要求⏹使用教材、参考书籍⏹命题说明和题型课程性质、目的与基本要求⏹课程性质本课程讲授计算机科学与技术的数学基础课《离散数学》的部分主要内容：集合论、图论与组合数学初步，是计算机专业的主干课程之一。

本课程前行课程为线性代数，数学分析(上)。

⏹课程目的使学生掌握集合论、图论与组合数学初步的基本内容，并对证明的思想和方法深入理解和体会，初步培养学生的思维过程的数学化。

⏹基本要求：⏹掌握集合论、组合学和图论的基本概念，清楚了解引入基本概念的实际背景、各概念间相互关系；掌握基本定理以及有关理论题的证明技巧；掌握解决计数问题的基本方法和技巧；掌握图论中各算法设计的思想、正确性证明以及算法的应用。

为进一步学习计算机其他课程打下坚实的基础。

教学方式本课程以课堂讲授为主。

考核方式⏹平时作业；⏹集合论、组合数学和图论3次课堂练习；⏹期中，期末的两次笔试考试。

教学内容与要求----集合论⏹第一章集合的基本概念掌握：集合的基本概念，集合的运算。

了解：集合论的悖论。

掌握证明两个集合相等的基本法和公式法。

⏹第二章关系掌握：关系的性质、运算和关系的闭包，以及等价关系和偏序关系。

了解：关系在关系数据库中的应用。

掌握证明的类型。

集合论与图论计算机学院08年秋季一、 解答以下问题，要求只给出答案〔每题2分，共16分〕1.设A B 、为集合，试求一个集合X ，合得A X B ∆=。

〔A B ∆〕2.设{}1,2,3,4A =，{}1,2B =，试求从A 到B 的满射的个数。

〔42214-=〕3.设{}1,2,,10A =，试求A 上反自反二无关系的个数。

〔29022n n -=〕4.设{}12,,,p A u u u =，()112q p p ≤-。

试求以V 为顶点集具有条边的无向图的个数。

〔 ⎝⎛-2/)1(p p q 〕5.设T 是一个有P 个顶点的正那么二元树，试求下的叶子数，其中P 是奇数。

〔12P +〕 6.正整数m 和n 为什么值时,Km n 为欧拉图？〔m n 和为偶数〕7.设(),G V E =为无向图，,V P E P ==。

如果G 是边通图，那么G 至少有几个生成树？ 〔3个〕8. 具有p 个顶点q 条边的平面连通图中，p 和q 应满足什么样的关系式？(36q p ≤-)二、以下各题要求只给出答案〔每题2分，共14分〕１.设{}()()(){},,,,,,,,,X a b c d R a b b c c a ==，试求R 的传递闭包。

〔()()()()()()()()(),,,,,,,,,,a a b b c c a b b c c a a c b a c b ，，，，，，，〕2.将置换〔123456789791652348〕分解为循环置换的乘积，然后分解成对换的乘积()()()()()()()()()173298465171329282426=。

3.设0000010110100000010000000A ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦如果A 4.设{}{}0,1,,,,,,,B E a b c x y z ==。

字母表B 上所有字符串之集记为*B ，字母表E 上所有字符串之集记为*E 。

试求*B 和*E 的基数有什么关系。

“什么是教育？教育就是当你把所学的东西都忘掉后，最终剩下的东西！”“最终剩下的东西就是一个人的创新意识和学习能力。

”把教学的着眼点集中在掌握科学基础知识和训练创新能力上，着重培养科学的思维方法，把知识传授与科学探索融为一体，激发学生的好奇心和创造性。

教学质量是“教育水平高低和效果优劣的程度”（教育大词典）前言0.1集合论与图论是数学的一部分“对于大自然这本奥秘无穷的书，我读不懂”。

──莎士比亚：《安东尼和克里奥帕特拉》（1564—1616）“如果不理解它的语言，没有人能读懂宇宙这本伟大的书，它的语言就是数学”。

──伽里略（1564—1642）“在任何特定的理论中，只有其中包含数学的部分才是真正的科学”。

──康德（1724—1804）数学不专属自然科学，也不专属社会科学，更不专属于文学艺术。

它是一种宇宙语言，为一切文明生物共有、共享。

0.2 主要内容“我想知道上帝是如何创造这个世界的。

对这个或那个现象、这个或那个元素的谱我并不感兴趣。

我想知道的是他的思想，其他的都是细节问题”。

──爱因斯坦（1879—1955）本课主要讲述集合论（Set Theory）：集合及其运算、映射及其合成、关系及其运算、无穷集合及其基数。

图论（Graph Theory）：图的一些基本概念、一些特殊的图、树及其性质、割点和桥、连通度、平面图、图的着色、有向图。

基本思想和意义我们从“集合”这个基本概念开始建立集合理论。

就某种观点来看，“集合”与“性质”是同义词，是基本概念之一。

这样，集合用来描述事物的性质——我们的研究对象，映射用来描述事物之间的联系——运算、关系，从而为集合建立了结构。

于是，为建立系统的数学模型提供了数学描述语言——工具，代数系统就是在集合上引入运算。

集合论又提供了研究数学模型的性质，发现新联系的推理方法，从而找出事物的运动规律。

而图论是上述思想的一个具体应用，事实上，图论为任何一个包含了一种二元关系的系统提供了一个数学模型；部分地，也因为使用了图解式表示方法，图就具有一种直观的和符合美学的外形。

《集合论与图论》课程教学大纲一、课程基本信息课程编号：CS31111课程名称：集合论与图论英文名称：SET THEORY AND GRAPH THEORY课程学时：64；讲课学时： 48；实验学时：上机学时：习题学时：16;课程学分：4.0开课单位：计算机科学与技术学院授课对象：计算机大类专业（包括计算机科学与技术、物联网工程、生物信息学、信息安全）、软件工程大类专业开课学期： 1春先修课程：工科数学分析、线性代数二、课程目标《集合论与图论》是计算机大类/软件工程大类专业的一门专业基础课程。

本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。

该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。

要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。

集合论与图论为此提供了强有力的描述工具与推理理论。

本课程的目标是通过理论学习，为计算机科学与技术专业的后继课及将来的科学研究提供必要的相关数学知识，提供建立离散系统的数学模型的数学描述工具；使学生正确地理解概念，正确地使用概念进行推理，养成一个好的思维习惯，理解理论与实践的关系；引导学生观察生活、社会和大自然，分析事物间的联系，建立系统的模型，提出和解决其中的复杂工程问题。

课程具体目标如下：课程目标1：掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型；课程目标2：掌握直接证明法、反证法、数学归纳法、构造法等常用的证明方法，培养机械化、自动化的逻辑推理能力，使学生能够利用集合论与图论的概念、理论与方法并通过文献研究分析复杂工程问题，并能获得有效的结论，理解并逐步设计求解这些问题的算法基本思想；课程目标3：掌握资料查阅方法，学会对课堂所学理论知识进行扩展，培养自学能力。

第一篇集合论集合论是德国数学家康托（Contor）在1874年建立的，它是现代数学的基础，当今数学中的每个对象本质上都是集合。

有时我们说：“数学能嵌套在集合论中”其含义就是指数学的一些对象如数、函数、线、面等都可以用集合来定义。

换句话说，数学的各个分支在本质上都是研究这种或那种对象的集合。

例如：几何学是研究点、线、面的集合；数学分析是研究函数的集合；代数学是研究数的集合以及在此集合上有关运算的集合等。

因此，我们把集合论作为现代各种数学的基础是有道理的、合适的。

集合论也是计算机科学的重要工具。

集合论在程序设计、数据结构、形式语言、操作系统等计算机科学中，都有重要应用，成为计算机科学工作者必不可少的基础知识。

计算机科学领域中的大多数基本概念和理论，几乎均采用集合论的术语来描述和论证。

集合论主要有以下几个特点：第一、第一、它所研究的对象十分广泛。

例如数、图形或其它任何客体作为对象。

第二、第二、因为它研究的对象是如此广泛，为了便于研究，就必须寻找对象的共性。

而要做到这一点，就必须进行抽象。

第三、第三、在抽象化的基础上，可以用统一的方法来研究和处理集合论中的各种问题。

总之，集合论的主要特点是研究对象的广泛性，分析思考问题的抽象性和处理问题的统一性。

正是这些特点，使我们便于用它来描述和研究离散对象及其关系。

第一章集合及其运算基本要求1. 1.掌握集合、子集、全集、空集和幂集等概念。

熟悉常用的表示集合的方法以及用文氏图来表示集合的方法。

能够判定元素与集合、集合与集合之间的关系；熟练掌握两个集合相等关系和包含关系的定义和性质，能够利用定义证明两个集合相等。

2. 2.熟练掌握集合之间的各种运算以及集合运算的基本等式，能够利用它们来证明更复杂的集合等式。

3. 3.掌握余集与集合笛卡儿乘积的概念以及De Morgan公式。

4．掌握求解与有穷集合计数相关的实际问题。

1.1 必备知识和考试要点1.1.1基本定义集合是一个不能精确定义的数学概念。

集合论与图论习题册软件基础教研室刘峰2019.03第一章 集合及其运算8P 习题1. 写出方程2210x x ++=的根所构成的集合。

2.下列命题中哪些是真的，哪些为假a)对每个集A ，A φ∈； b)对每个集A ，A φ⊆； c)对每个集A ，{}A A ∈； d)对每个集A ，A A ∈； e)对每个集A ，A A ⊆； f)对每个集A ，{}A A ⊆； g)对每个集A ，2A A ∈；h)对每个集A ，2A A ⊆；i)对每个集A ，{}2A A ⊆； j)对每个集A ，{}2A A ∈； k)对每个集A ，2A φ∈；l)对每个集A ，2A φ⊆；m)对每个集A ，{}A A =； n) {}φφ=；o){}φ中没有任何元素；p)若A B ⊆，则22A B ⊆q)对任何集A ，{|}A x x A =∈； r)对任何集A ，{|}{|}x x A y y A ∈=∈； s)对任何集A ，{|}y A y x x A ∈⇔∈∈； t)对任何集A ，{|}{|}x x A A A A ∈≠∈。

答案：3.设有n 个集合12,,,n A A A 且121n A A A A ⊆⊆⊆⊆，试证：12n A A A ===。

4.设{,{}}S φφ=，试求2S ？5.设S 恰有n 个元素，证明2S 有2n 个元素。

16P 习题 6.设A 、B 是集合，证明:(\)()\A B B A B B B φ=⇔=。

7.设A 、B 是集合，试证A B A B φ=⇔=∆。

9.设A ，B ，C 为集合，证明：\()(\)\A B C A B C =。

10.设A ，B ，C 为集合，证明：()\(\)(\)A B C A C B C =。

11.设A ，B ，C 为集合，证明：()\(\)(\)A B C A C B C =。

12.设A ，B ，C 都是集合，若A B A C =且A B B C =，试证B=C 。