离散数学课件-第4章

离散数学课件-第4章目录CONTENTS•集合论基础•关系•图论初步•离散概率论•逻辑初步01集合论基础集合的定义与表示01020304空集表示没有任何元素理解集合的基本概念和集合是由确定的、不同常用大括号{}来表示集合，的集合，常用希腊字母表示方法的元素所组成的总体元素之间用逗号隔开∅表示子集、超集与补集010203子集超集补集一个集合中的所有元素都一个集合的所有元素都属一个集合中不属于另一个是另一个集合中的元素，于另一个集合，则称这个集合的元素组成的集合称则称这个集合为另一个集集合为另一个集合的超集为另一个集合的补集合的子集集合的运算交、并、差交运算并运算差运算两个集合中共同的元素组两个集合中所有元素组成从一个集合中去除另一个成的集合称为这两个集合的集合称为这两个集合的集合中的元素后得到的集的交集并集合称为这两个集合的差集02关系关系的定义与表示总结词关系的定义与表示是离散数学中的基本概念，它们为后续学习提供了基础详细描述在离散数学中，关系被定义为两个集合之间的映射关系，通常用笛卡尔积来表示关系可以用多种方式表示，如矩阵、图等关系在集合论、逻辑、数据库等领域有着广泛的应用关系的性质自反、对称、传递总结词关系的性质是关系的基本特征，它们决定了关系的内在规律详细描述自反关系是指集合中的元素与其自身有映射关系；对称关系是指对于任意两个元素，如果它们之间有关系，则它们之间的关系是对称的；传递关系是指如果元素A和元素B有关系，且元素B和元素C有关系，则元素A和元素C有关系这些性质在逻辑推理、集合运算等领域有着重要的应用关系的闭包运算总结词闭包运算是离散数学中处理关系的重要工具，它能够描述关系的扩展和限制详细描述闭包运算是一种将关系进行转换的操作，通过闭包运算可以获得原关系的扩展或限制闭包运算在数据库设计、集合运算等领域有着广泛的应用，它可以用于处理关系的并、交、差等运算，以及解决一些复杂的关系问题03图论初步图的基本概念01020304节点边定向图与无向图权重图中的顶点称为节点连接两个节点的线段称为边边是否有方向决定图是有向图边的权重表示两个节点之间的还是无向图距离或连接强度路径与回路路径最短路径一系列的边和节点，其中每条两个节点之间的最短路径是路边都有一个方向径长度最小的一条路径回路欧拉路径有方向的路径，起点和终点是至少经过图中的每条边一次的同一个节点路径，不一定经过所有节点图的连通性连通性强连通图与弱连通图如果图中任意两个节点之间都存在一条路有向图中，如果任意两个节点都存在有向径，则图是连通的路径，则为强连通图；无向图中，任意两个节点都存在路径，则为弱连通图连通度最小生成树表示一个图连通性的度量，表示需要多少一个连通无向图中，连接所有节点且边的个节点或边才能将图分割成不连通的子图权值和最小的树称为最小生成树04离散概率论概率的基本概念概率必然事件描述随机事件发生的可能性大小的量概率等于1的事件，表示一定会发生度不可能事件互斥事件概率等于0的事件，表示一定不会发两个事件不能同时发生生条件概率与独立性独立性两个事件之间没有相互影响，一个条件概率事件的发生不影响另一个事件的发生概率一个事件在另一个事件已经发生的条件下的发生概率全概率公式计算复杂事件的概率，通过将其分解为若干个互斥事件的概率的和离散随机变量及其分布离散随机变量分布列取值可以一一列举的随机变量描述离散随机变量取每个可能值的概率期望值方差离散随机变量的所有可能取值的概率加权和描述离散随机变量取值分散程度的量度05逻辑初步命题逻辑命题一个具有真假意义的陈述句基本命题永真、永假和可变真假三种类型复合命题由基本命题通过逻辑联结词组合而成的命题逻辑联结词与、或、非、蕴含等谓词逻辑01020304谓词逻辑是命题逻辑的扩展，谓词表示某个事物的性质或谓词逻辑中的命题由谓词、变它引入了变量和谓词的概念，关系的词变量表示某个事物的符号量和量词组成可以更精确地描述事物之间的关系逻辑推理规则0102演绎推理归纳推理从一般到特殊的推理方式，即从普从特殊到一般的推理方式，即从个遍性命题推导出特殊性命题别性命题推导出普遍性命题反证法枚举法通过否定结论来证明原命题的正确通过列举所有可能的情况来证明原性的方法命题的正确性的方法0304。