下载文档原格式
离散数学的基础知识离散数学是计算机科学、数学和信息科学的一门重要学科，它研究的是离散结构，即不连续的数学对象，例如集合、图、函数和关系等。
离散数学的基础知识对于我们理解和应用计算机科学中的算法、数据结构、逻辑和推理等方面都至关重要。
本文将介绍离散数学的一些基本概念和应用。
一、集合论在离散数学中，集合是一个重要的概念。
集合是由确定的对象组成的整体，这些对象被称为集合的元素。
集合的运算有并、交、补、差等。
集合还可以用列表、描述法、泛函法等方式表示。
在计算机科学中，集合常用于表示数据的存储和操作。
二、逻辑与命题逻辑是离散数学中的另一个基础知识，它研究的是推理和论证的规律。
逻辑主要包含命题逻辑和谓词逻辑两个方面。
命题逻辑研究的是命题的真假和推理的方法，谓词逻辑则扩展了命题逻辑，研究的是谓词和量词的运算。
命题是一个陈述句，它要么为真，要么为假。
命题可以用真值表、逻辑公式等方式表示。
逻辑运算包括非、与、或、蕴含和等价等。
命题逻辑的推理方法有代入法、消解法、假设法等。
三、图论图论是离散数学中的一个重要分支，它研究的是图的性质和图的应用。
图是由节点和边组成的数学模型，用来表示事物之间的关系。
图论主要研究顶点的度、路径的搜索、连通性、环的存在性等问题。
图可以分为有向图和无向图，有向图的边有方向，无向图的边没有方向。
在图中，节点之间的连接关系称为边，边可以有权重。
图的表示方法有邻接矩阵、邻接表等。
图的应用包括网络分析、城市规划、路线规划等。
四、组合数学组合数学是离散数学中的一个分支，它研究的是集合的选择和排列方式。
组合数学在计算机科学中有重要的应用，例如密码学、编码理论和算法设计等方面。
组合数学的基本概念包括排列、组合、二项式系数等。
排列是从一组元素中选取特定顺序的方式，组合是从一组元素中选取特定组合的方式。
二项式系数是计算排列和组合数量的重要方法。
组合数学的应用有很多，包括选择算法、排列算法、图的着色等。
五、数论数论是离散数学中研究整数性质的一个分支，它研究的是整数之间的关系和性质。
02324离散数学知识点
离散数学是研究离散对象和离散结构的数学分支，其知识点包括但不限于集合论、图论、逻辑学、组合数学等。
以下是其中一些重要的知识点：
1. 集合论：集合论是离散数学的基石，它研究集合、集合之间的关系和集合的性质。
2. 图论：图论是离散数学的重要组成部分，它研究图（由节点和边构成的结构）的性质和分类。
3. 逻辑学：逻辑学是离散数学的另一个重要组成部分，它研究推理的规则和形式。
在离散数学中，逻辑通常用于描述和证明一些结构或系统的性质。
4. 组合数学：组合数学是离散数学的一个分支，它研究计数、排列和组合问题。
5. 离散概率论：离散概率论是离散数学的另一个分支，它研究离散随机事件的数学模型。
6. 离散概率分布：离散概率分布是描述离散随机事件发生概率的数学模型。
7. 离散随机变量：离散随机变量是能够取到可数无穷多个值的随机变量。
8. 离散概率空间：离散概率空间是一个集合，它包含一个可数无穷多的元素，每个元素都有一个与之相关的概率值。
9. 离散随机过程：离散随机过程是离散随机事件在时间或空间上的序列。
这些知识点都是离散数学的重要组成部分，它们在计算机科学、数学、物理学等领域都有广泛的应用。
集合论与图论基础题在数学中，集合论和图论是两个重要的分支。
集合论研究元素的归类和组织，而图论研究元素之间的关系和连接。
本文将通过一些基础题目来介绍集合论和图论的基本概念和应用。
1. 集合论1.1. 基本概念在集合论中，我们首先需要了解集合的概念及其相关术语。
一个集合是由一些确定的元素组成的整体。
通常用大写字母表示集合，而集合中的元素用小写字母表示。
例如，集合A={1, 2, 3}表示一个包含元素1、2和3的集合。
1.2. 集合的运算在集合论中，还有一些常见的集合运算：并集、交集和补集。
- 并集（Union）：将两个或多个集合中的元素合并成一个集合。
记作A∪B，表示包含了属于集合A或集合B的所有元素。
- 交集（Intersection）：将两个或多个集合中共有的元素取出来，形成一个新的集合。
记作A∩B，表示包含了同时属于集合A和集合B的所有元素。
- 补集（Complement）：给定一个全集U和一个集合A，A对于U 的补集是指在U中但不在集合A中的元素组成的集合。
记作A'或者A^c，表示不属于A的所有元素。
1.3. 集合的关系在集合论中，还可以通过比较集合的元素来描述集合之间的关系。
- 包含关系：如果集合A中的所有元素都属于集合B，我们称集合A是集合B的子集，记作A⊆B。
- 相等关系：如果两个集合A和B具有相同的元素，互相包含对方的所有元素，我们称它们相等，记作A=B。
- 真子集：如果集合A是集合B的子集，但集合A和集合B不相等，我们称集合A是集合B的真子集，记作A⊂B。
2. 图论2.1. 基本概念图是由一些顶点和连接这些顶点的边组成的数学结构。
图论研究顶点和边之间的关系及其相关性质。
2.2. 有向图与无向图图可以分为有向图和无向图两种类型。
- 有向图：图中的边有方向，连接顶点A和顶点B的边从A指向B，记作(A, B)。
- 无向图：图中的边没有方向，连接顶点A和顶点B的边可以从A到B，也可以从B到A，不加箭头表示。
离散数学的基础知识离散数学作为现代数学的一门重要分支，在计算机科学、通信工程、信息技术等领域发挥着重要的作用。
本文将介绍离散数学的基础知识，共分为三个部分：集合论、逻辑和图论。
一、集合论集合是离散数学中的基本概念，它是一个由元素组成的整体。
例如，{1，2，3}就是一个集合，其中1、2、3是元素。
集合的描述通常采用列举法或描述法。
列举法即列举集合中的元素。
例如，{1，2，3}、{a，b，c，d}等都是集合。
描述法则是通过一些规则来描述集合中的元素。
例如，{x | x是正整数且小于10}表示由所有小于10的正整数组成的集合。
集合之间有一些常见的运算：并集：将两个集合中的元素合并起来，形成一个新的集合。
例如，{1，2，3}和{3，4，5}的并集为{1，2，3，4，5}。
交集：取两个集合中相同的元素组合成一个新的集合。
例如，{1，2，3}和{3，4，5}的交集为{3}。
补集：设A为一个集合，A'为其补集，则A'包含所有不在A 中的元素。
除此之外，集合中还有子集、空集、全集等重要概念。
子集指的是一个集合中的所有元素为另一个集合的元素，则前者是后者的子集。
空集指的是一个不包含任何元素的集合，全集则是该领域的所有元素的集合。
二、逻辑逻辑是进行推理和论证的基础。
在离散数学中，布尔代数是逻辑的一种基础形式。
它是一种将推理和论证过程化为运算的数学体系。
常见的布尔运算有与（AND）、或（OR）、非（NOT）。
与运算表示只有两个值同时为真，结果才为真。
例如，1 AND 1 为真，1 AND 0 为假。
或运算表示两个值中至少一个值为真，结果才为真。
例如，1 OR 0 为真，0 OR 0 为假。
非运算表示取反，将真变为假，将假变为真。
例如，NOT 1 为假，NOT 0 为真。
布尔代数的一个重要应用是逻辑电路的设计。
逻辑电路是指由逻辑门和连线构成的电路，其中逻辑门实现着不同的布尔运算。
三、图论图论是离散数学中的重要分支。
《集合论与图论》课程教学大纲一、课程基本信息课程编号：CS31111课程名称：集合论与图论英文名称：SET THEORY AND GRAPH THEORY课程学时：64；讲课学时： 48；实验学时：上机学时：习题学时：16;课程学分：4.0开课单位：计算机科学与技术学院授课对象：计算机大类专业（包括计算机科学与技术、物联网工程、生物信息学、信息安全）、软件工程大类专业开课学期： 1春先修课程：工科数学分析、线性代数二、课程目标《集合论与图论》是计算机大类/软件工程大类专业的一门专业基础课程。
本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。
该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。
要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。
集合论与图论为此提供了强有力的描述工具与推理理论。
本课程的目标是通过理论学习，为计算机科学与技术专业的后继课及将来的科学研究提供必要的相关数学知识，提供建立离散系统的数学模型的数学描述工具；使学生正确地理解概念，正确地使用概念进行推理，养成一个好的思维习惯，理解理论与实践的关系；引导学生观察生活、社会和大自然，分析事物间的联系，建立系统的模型，提出和解决其中的复杂工程问题。
课程具体目标如下：课程目标1：掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型；课程目标2：掌握直接证明法、反证法、数学归纳法、构造法等常用的证明方法，培养机械化、自动化的逻辑推理能力，使学生能够利用集合论与图论的概念、理论与方法并通过文献研究分析复杂工程问题，并能获得有效的结论，理解并逐步设计求解这些问题的算法基本思想；课程目标3：掌握资料查阅方法，学会对课堂所学理论知识进行扩展，培养自学能力。
一．列式题。
用谓词表示法表示如下集合： 1． 所有偶数组成的集合AA={x| x ∈Z ∧ x mod 2 =0}. 2． 所有奇数组成的集合BB={x| x ∈Z ∧ x mod 2 =1}. 3． 10的整倍数组成的集合AA={x| x ∈Z ∧x mod 10 =0}. 4． 5的整倍数组成的集合BA={x| x ∈Z ∧x mod 5 =0}.5． 方程x 2-1=0的所有实数解的集合B 。
B={x|x ∈R ∧x 2-1=0}6． 小于5的非负整数组成的集合A ：A={x | x ∈ N ∧ x < 5 }. 二．判断题 1．（ F ）包含三个元素的集合A 表示成：A=（1，2，3）。
2．（ F ）集合A ={1，2，3}与集合B ={2，3，1}是两个不同的集合。
3．（ T ）R=Φ是一个二元关系。
4．（ T ）设A= {1, 2, 3}，R= {<1, 1>, <2, 2>, <3, 3>, <1, 2>}，则R 是A 上自反的关系。
5．（ T ）设A= {1, 2, 3}，R= {<1, 1>, <1, 2>, <2, 1>}，则R 是A 上对称的关系。
6．（ T ）设A= {1, 2, 3}，R= {<1, 2>,<1, 3>}，则R 是A 上反对称的关系。
7．（ T ）设A= {1, 2, 3}，R= {<1, 1>,<2, 2>}，则R 是A 上传递的关系。
8．（ F ）设A= {1, 2, 3}，R= {<1, 2>,<2, 3>}，则R 是A 上传递的关系。
9．（ T ）R 是R 的子集。
10．（ T ）设f ：A →B 是双射，则称f -1：B →A 是它的反函数。
这个反函数也是双射的。
三．计算题1．求集合A={1, 2, 3} 的所有子集？ 答：A 的0元子集，只有一个Φ，A 的1元子集，即单元集，有三：{1}、{2}、{3}； A 的2元子集有三：{1，2}、{2，3}、{1，3}；A 的3元子集就是它本身{1,2,3} ，因为A 就是三元集。
2．写出集合A={0,1,2,3}的幂集P(A)? 答：P(A)={Φ, {0}, {1}, {2}, {3},{0,1},{0,2},{0,3}, {1,2}, {1,3}, {2,3}, {0,1,2,}, {0,1,3,} {0,2,3,}, {1,2,3},A }3．设A={a,b,c},B={a},C={b,d},求A ∪B, A ∪C, A ∩B,B ∩C, A-B,B-A,A-C,B-C?答：A ∪B={a ，b ，c}，A ∪C={a ，b ，c ，d}，A ∩B={a}，B ∩C=Φ，A-B={b ，c}，B-A=Φ，A-C={a,c}，B-C=B 。
4．A={a ，b ，c}，B={b ，d}，求A ⊕B ？ 答：A ⊕B={a ，c ，d}。
5．设E={a ，b ，c ，d}， A={a ，b ，c}，求~A ？ 答：~A={d}。
6．已知A={1,2}，求P(A) ⨯ A ？ 答：P(A)={ Φ,{1}, {2},{1,2}}，P(A) ⨯ A = {<Φ, 1>, <Φ, 2>,<{1}, 1>, <{1}, 2>,<{2}, 1>, <{2}, 2>,<{1,2}, 1>, <{1,2}, 2>,} 7．A={1,2,3,4},R={<1,1>, <1,2>, <2,3>, <2,4>, <4,2>}。
求R 的关系矩阵？ 答：R 的关系矩阵为：8．关系R = {<1, 2>, <1, 3>, <2, 4>, <4, 3>},求关系R 的定义域 、值域和域？答：R 的定义域 dom R = { 1，2，4 }，值域 ran R= { 2，3，4 }，域fld R= { 1，2，3，4}。
9．设A= {1, 2, .., 8},A 上的关系R= {<x, y> | x, y ∈ A ∧x ≡ y (mod3) }，求A 中各元素的等价类。
⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0010000011000011R M解：对于元素1，有：1R1, 1R4, 1R7。
所以，[1] = {1, 4, 7}。
对于元素2，有：2R2, 2R5, 2R8。
所以，[2] = {2, 5, 8}。
对于元素3，有：3R3, 3R6。
所以，[3] = {3, 6}。
对于元素4，有：4R4, 4R1, 4R7。
所以，[4]= {4, 1, 7}= [1]。
对于元素5，有：5R5, 5R2, 5R8。
所以，[5]= {5, 2, 8}= [2]。
对于元素6，有：6R6, 6R3。
所以，[6]={6, 3}= [3]。
对于元素7，有：7R4, 7R1, 7R7。
所以，[7]= {4, 1, 7}= [1] =[4]。
对于元素8，有：8R5, 8R2, 8R8。
所以，[8]= {5, 2, 8}= [2] = [5]。
四．简答题。
1．判断以下关系的性质对称的。
但不是自反的，也不是传递的。
反自反的，反对称的。
同时又是传递的。
反对称的，自反的，但不是传递的。
五．证明题1．设A= {1, 2, .., 8}, A上的关系R= { <x, y> | x, y∈A∧x ≡y (mod3) }，求证：R是A上的等价关系。
证明：因为对于所有的x∈A，有x ≡x (mod3) ，所以关系R是自反的。
同时对于所有的x,y∈A，若x ≡y (mod3) ，则有y ≡x (mod3)，所以关系R是对称的。
对于所有的x, y, z ∈A，若x ≡y (mod3)，y ≡z (mod3)，则有x ≡z (mod3)，所以关系R是传递的。
2．求证：证明：六．有穷集合计数题1．某班有学生25人，其中会打篮球的有14人，会打排球的有12人，会打网球的有6人，有6人既会打篮球又会打排球，有5人既会打篮球又会打网球，还有2人三种球都会打。
又已知6个会打网球的学生都会打另外一种球类（篮球或排球）。
问：什么球都不会打的学生有几人？解：设A、B、C分别表示会打排球、网球、篮球的学生的集合。
则根据题意可画出文氏图：BABBA=-)(BABBABAEBABBBABBABBA=-∴====-)()()(~)()~()(假设：会打排球和网球，但不会打篮球的学生有x 人，只会打排球或篮球的学生分别有y 人和z 人，什么球都不会打的学生有k 人。
则由文氏图可知：x+2+3+0=6 ，y+x+2+4=12，z+4+2+3=14。
解得：x=1，y=5，z=5，k=5。
答：什么球都不会打的学生有五人。
七．化简题解：根据吸收律，原式八．画图题1．已知 G = < V , E >,其中 V = {v1, v2, v3, v4, v5 }, E = { (v1, v2), (v1, v2), (v1, v3), (v3, v2), (v3, v3), (v3, v4) }，画出图G .2．画出4阶3条边的所有非同构的无向简单图.答：4阶3条边的非同构的无向简单图有三个，其图如下：九．判断下列各图是否是 欧拉图？是否是哈密尔顿图？v1v2v3v4e1e2e3e4e5e62 x 0 yz43 k A B C)))((())()((A C B A B A C B A --.~)~()~()~(~)()(A B A B A B A B A A A B A A B A -=====-= φ答：1是 欧拉图。
1和4 是哈密尔顿图。
一．列式题。
设F 表示一年级大学生的集合，S 表示二年级大学生的集合，R 表示计算机系学生的集合，M 表示数学系学生的集合，T 表示选修离散数学的学生的集合，L 表示爱好文学的学生的集合，P 表示爱好体育的学生的集合。
求下列各语句所对应集合的集合表达式1．所有计算机系二年级学生都选修离散数学 R ⋂ S ⊆ T 2．数学系的学生或者爱好文学或者爱好体育 M ⊆ L ⋃ P3．数学系一年级学生都没有选修离散数学 （M ⋂ F ）⋂T = Φ4．只有一、二年级学生才爱好体育P ⊆ F ⋃ S5．除去数学系和计算机系的二年级学生外都不选修离散数学~ ((M ⋃ R)⋂ S) ⋂ T = Φ二．判断题 1．（ F ）包含三个元素的集合A 表示成：A={1、2、3}。
2．（ T ）设A= {1, 2, 3}，R= {<1, 1>,<2, 2>}，则R 是A 上对称的关系。
3．（ T ）设A= {1, 2, 3}，R= {<1, 1>,<2, 2>}，则R 是A 上反对称的关系。
4．（ T ）设A= {1, 2, 3}，R= {<1, 2>,<2, 3>,<1, 3>}，则R 是A 上传递的关系。
5．（ T ）设A= {1, 2, 3}，R= {<1, 3>}，则R 是A 上传递的关系。
6．（ F ）R 是R 的真子集。
7．（ F ）若f:A →B 为单射,则f-1:B →A 也为单射。
8．（ T ）空集是一切集合的子集。
9．（ T ）若一个有向图D 是单向连通的，则它必是弱连通图的。
10．（ F ）a ∈{{a}}。
11．（ F ）函数F=(x 2-1)/(x+1)与G=x-1相等。
12．（ F ）若一个有向图D 是单向连通的，则它必是强连通图的。
三．计算题1．求集合B={1,2,3,4}的所有子集 答：B 的0元子集，只有一个Φ，B 的1元子集，即单元集，有四：{1}、{2}、{3} 、{4}；B 的2元子集有六：{1，2}、{1，3}、{1，4} 、{2，3}、{2，4}、{3，4} ； B 的3元子集有四：{1,2,3}、 {1,2,4}、 {2,3,4}、 {1,3,4}。
B 的4元子集就是它本身{1,2,3,4} 。
2．写出集合A={1,2,3}的幂集P(A)?答：P(A)={Φ,{1}, {2},{3},{1,2}, {1,3}, {2,3},{1, 2,3},}(4)(5)(6)(1)(2) (3)3．A={张三，李四，王二}，B={赵六，张三}，求A ⊕B ？ 答：A ⊕B ={李四，王二，赵六}。
