左孝凌离散数学课件

左孝凌离散数学课件欢迎来到左孝凌教授的离散数学课程本课程将深入探讨离散数学的核心概念和应用我们将从基础开始，逐步深入复杂主题绪论

1.离散数学简介课程概览离散数学是研究离散结构的数学我们将学习六大主题绪论、集分支，包括集合、逻辑、图论合论、命题逻辑、谓词逻辑、关等系论和图论学习目标掌握离散数学的基本概念和方法，培养逻辑思维和问题解决能力离散数学的定义和应用定义应用领域离散数学是研究离散结构的数学分支，包括有限或可数无限的集•计算机科学合•密码学•网络分析•人工智能离散数学与其他数学分支的关系代数离散数学借鉴了代数的抽象思维和结构研究方法分析离散数学与连续数学形成对比，但在某些领域有交叉几何图论中的许多概念源自几何学，如平面图和拓扑学集合论

2.集合基础1集合运算2等势与基数3幂集与笛卡尔积4集合论是离散数学的基础，为其他分支提供了理论支撑我们将从基本概念开始，逐步深入复杂主题集合的概念定义表示方法集合是具有某种特定性质的事物列举法A={1,2,3,4,5}描述的总体，这些事物称为该集合的法B={x|x是自然数且x6}元素特殊集合空集不含任何元素的集合，用∅表示全集包含所有可能元素的集合集合的运算并集交集差集补集A∪B包含A或B中的所有元A∩B包含同时属于A和B的元A-B包含属于A但不属于B的A包含不属于A的所有元素素素元素等势集合和基数等势集合基数两个集合之间存在一一对应关系，则称这两个集合等势例如有限集的基数是集合中元素的个数无限集的基数用阿列夫数表自然数集与偶数集等势示，如ℵ₀表示可数无限集的基数幂集和笛卡尔积幂集笛卡尔积集合A的所有子集构成的集合，记两个集合A和B的笛卡尔积A×B是为PA例A={1,2}，PA=所有有序对a,b的集合，其中{∅,{1},{2},{1,2}}a∈A，b∈B应用幂集在组合数学中有广泛应用笛卡尔积用于定义关系和函数命题逻辑

3.命题概念1研究判断语句的真假及其复合关系基本运算2包括否定、合取、析取、蕴含和等价真值表3用表格形式表示复合命题的真值范式4将复合命题转化为标准形式命题的概念和分类命题定义分类命题是一个陈述句，它或真或假，但不能既真又假•原子命题不能再分解的简单命题•复合命题由多个原子命题通过逻辑联结词组成命题逻辑的基本运算否定¬合取∧p的否定为非p，记为¬p p和q的合取为p且q，记为p∧q析取∨蕴含→p和q的析取为p或q，记为p∨q p蕴含q记为p→q，表示如果p，那么q真值表和逻辑等价p q p∧q p∨qp→qT T TTTT F F TFF TF TTF FFFT两个命题具有相同的真值表，则称它们逻辑等价，记为p≡q范式和简单化范式将复合命题转化为标准形式，包括合取范式和析取范式主范式最简单的范式形式，包括主合取范式和主析取范式化简利用逻辑等价式和真值表，将复杂命题转化为简单形式谓词逻辑

4.谓词概念1量词引入2论域与真值3谓词公式4推理规则5谓词逻辑是命题逻辑的扩展，引入了变量、量词和谓词，使得逻辑表达更加精确和强大谓词的概念定义表示谓词是关于对象的陈述，可以看通常用大写字母表示，如Px表作是含有变量的命题函数示关于x的谓词例子x是偶数是一个谓词，可表示为Ex当x取具体值时，Ex成为一个命题量词和量化全称量词∀存在量词∃∀x Px表示对所有x，Px都为真∃x Px表示存在x，使得Px为真唯一量词∃!∃!x Px表示唯一存在x，使得Px为真论域和真值论域真值确定变量取值的范围，也称为个体域例如，自然数集、实数集等对于全称量化，需要检查论域中所有元素对于存在量化，只需论域的选择影响谓词的真值找到一个满足条件的元素范式和推理前束范式将所有量词移到公式前面的标准形式skolem标准形式消除存在量词，引入函数符号的标准形式推理规则全称实例化、存在实例化等推理规则的应用关系论

5.关系定义1研究事物之间联系的数学工具关系表示2集合表示、矩阵表示和图形表示关系性质3自反性、对称性、传递性等特殊关系4等价关系、偏序关系等关系的概念定义表示方法关系R是笛卡尔积A×B的子集，表集合表示R={a,b|a∈A,示A中元素与B中元素之间的某种b∈B,a和b满足某种关系}有序对联系表示aRb表示a与b之间存在关系R例子小于关系R={a,b|a,b∈R,ab}整除关系R={a,b|a,b∈Z,a能整除b}关系的运算逆关系复合关系R⁻¹={b,a|a,b∈R}R∘S={a,c|∃ba,b∈R∧b,c∈S}并运算交运算R∪S={a,b|a,b∈R∨a,R∩S={a,b|a,b∈R∧a,b∈S}b∈S}等价关系和偏序关系等价关系偏序关系同时具有自反性、对称性和传递性的关系例如集合上的相等同时具有自反性、反对称性和传递性的关系例如自然数集上关系的小于等于关系函数与映射定义类型复合函数函数是一种特殊的关系，每个输入元素恰单射、满射、双射等不同类型的函数两个函数的复合运算，f∘gx=好对应一个输出元素fgx图论

6.图的基本概念1图的表示2图的遍历3特殊图4图的应用5图论是研究图（由顶点和边组成的结构）的数学分支，在计算机科学和网络分析中有广泛应用图的基本概念图的定义有向图与无向图图G是一个二元组V,E，其中V有向图的边有方向，无向图的边是顶点集，E是边集无方向度路径与回路与顶点相连的边的数量有向图路径是顶点序列，回路是起点和分为入度和出度终点相同的路径图的遍历深度优先搜索DFS广度优先搜索BFS尽可能深地搜索图的分支可用于检测环、拓扑排序等先访问邻近顶点，再访问较远顶点可用于寻找最短路径图的着色和染色问题顶点着色边着色相邻顶点颜色不同的着色方案相邻边颜色不同的着色方案平面图着色四色定理任何平面图都可以用四种颜色着色最短路径问题Dijkstra算法用于解决单源最短路径问题，适用于边权重非负的图Floyd-Warshall算法用于解决所有顶点对之间的最短路径问题Bellman-Ford算法可处理负权边，用于检测负权回路。