下载文档原格式
离散数学重要公式定理汇总分解离散数学是计算机科学领域中的一门基础课程，它主要研究离散结构和离散对象之间的关系。
离散数学中有许多重要的公式和定理，这些公式和定理在计算机科学和其他领域中有广泛的应用。
下面是对离散数学中一些重要的公式和定理的汇总。
1.集合：-幂集公式：一个集合的幂集是所有它子集的集合。
一个集合有n个元素，那么它的幂集有2^n个元素。
-集合的并、交、差运算规则：并集运算满足交换律、结合律和分配律；交集运算也满足交换律、结合律和分配律；差集运算不满足交换律和结合律。
2.逻辑：-代数运算规则：多个逻辑表达式的与、或、非运算满足交换律、结合律和分配律。
-归结原理：对于一个给定的只包含“合取”和“析取”的合式公式集合，如果假设集合中的每个合式公式都为真，以及从这些前提出发，不能推导出这个集合中的一个假命题，则称这个假设集合是不一致的。
3.图论：-图的欧拉路径和欧拉回路：对于一个连通的图，如果它存在欧拉路径，那么这个图中最多只有两个度数为奇数的节点；如果一个连通的图存在欧拉回路，那么所有节点的度数都是偶数。
-图的哈密顿路径和哈密顿回路：对于一个图，如果它存在哈密顿路径，那么这个图中任意两个不相邻的节点u和v之间必然存在一条边；如果一个图存在哈密顿回路，那么从任意一个节点开始，可以经过图中的所有节点且最后回到起点。
4.代数结构：-子群定理：如果G是群H的一个子集，并且G是关于群H的运算封闭的，那么G是H的一个子群。
- 同态定理：如果f是从群G到群H的一个满射同态，那么G的核ker(f)是G的一个正规子群，而H是G/ker(f)的同构像。
5.排列组合：-排列公式：从n个元素中取出m个元素进行排列，有P(n,m)=n!/(n-m)!-组合公式：从n个元素中取出m个元素进行组合，有C(n,m)=n!/(m!*(n-m)!)以上只是离散数学中一小部分重要的公式和定理，这些公式和定理在计算机科学、密码学、图形学等领域中有广泛的应用。
重言式
矛盾式可满足式非重言式的可满足式直接应用规则推理附加前提证明法
归谬法命题
命题变项和命题常项
简单命题（原子命题）、复合命题
联接词：否定、合取、析取、异或、蕴含、等价、与非、或非
什么是命题公式？
分类
真值表简单合取式、简单析取式
合取范式和析取范式
极小项和极大项
用途：
联接词可以等价替换
联接词全功能集
联接词的极小全功能集构造证明法真值表法
主合取范式和主析取范式
命题符号化及联接词命题公式及分类等值演算范式联接词及其全功能集推理理论第一章：命题逻辑。
总 结第八章 图论8.1 图的基本概念8.1.1 图定义8.1―1 一个图G 是一个三重组〈V (G ),E (G ),ΦG 〉,其中V (G )是一个非空的结点(或叫顶点)集合,E (G )是边的集合,ΦG 是从边集E 到结点偶对集合上的函数。
一个图可以用一个图形表示。
定义中的结点偶对可以是有序的,也可以是无序的。
若边e 所对应的偶对〈a ,b 〉是有序的,则称e 是有向边。
有向边简称弧,a 叫弧e 的始点,b 叫弧e 的终点,统称为e 的端点。
称e 是关联于结点a 和b 的,结点a 和结点b 是邻接的。
若边e 所对应的偶对(a ,b )是无序的,则称e 是无向边。
无向边简称棱,除无始点和终点的术语外,其它术语与有向边相同 每一条边都是有向边的图称为有向图。
每一条边都是无向边的图称为无向图。
有向图和无向图也可互相转化。
例如,把无向图中每一条边都看作两条方向不同的有向边,这时无向图就成为有向图。
又如,把有向图中每条有向边都看作无向边,就得到无向图。
这个无向图习惯上叫做该有向图的底图。
在图中,不与任何结点邻接的结点称为弧立结点。
全由孤立结点构成的图称为零图。
关联于同一结点的一条边称为自回路。
在有向图中,两结点间(包括结点自身间)若同始点和同终点的边多于一条,则这几条边称为平行边。
在无向图中,两结点间(包括结点自身间)若多于一条边,则称这几条边为平行边。
两结点a 、b 间互相平行的边的条数称为边［a ,b ］的重数。
仅有一条时重数为1,无边时重数为0。
定义8.1―2 含有平行边的图称为多重图。
非多重图称为线图。
无自回路的线图称为简单图。
仅有一个结点的简单图称为平凡图。
定义 8.1―3 赋权图G 是一个三重组〈V ,E ,g 〉或四重组〈V ,E ,f ,g 〉,其中V 是结点集合, E 是边的集合,f 是定义在V 上的函数,g 是定义在E 上的函数。
8.1.2 结点的次数定义 8.1―4 在有向图中,对于任何结点v ,以v 为始点的边的条数称为结点v 的引出次数(或出度),记为deg +(v );以v 为终点的边的条数称为结点v 的引入次数(或入度),记为deg -(v );结点v 的引出次数和引入次数之和称为结点v 的次数(或度数),记作deg (v )。
离散数学知识点摘要：离散数学是计算机科学和数学的一个分支，它专注于非连续结构的研究。
本文旨在概述离散数学的核心知识点，包括集合论、逻辑、关系、函数、图论、组合数学和递归等。
1. 集合论- 集合的基本概念：集合是离散数学的基础，它是一组明确的、无重复的对象的集合。
- 集合运算：包括并集、交集、差集、补集等。
- 幂集：一个集合所有子集的集合。
- 笛卡尔积：两个集合所有可能的有序对的集合。
2. 逻辑- 命题逻辑：研究命题（声明的真值）和它们之间的关系，如合取、析取、否定等。
- 谓词逻辑：使用量词（如全称量词和存在量词）来表达更复杂的逻辑关系。
- 逻辑推理：包括直接证明、间接证明和归谬法等。
3. 关系- 关系的定义：一个集合到另一个集合的有序对的集合。
- 关系的类型：自反性、对称性和传递性等。
- 关系的闭包：在给定关系下，集合的最小闭包。
4. 函数- 函数的定义：一个集合到另一个集合的映射，每个元素有唯一的像。
- 函数的类型：单射、满射和双射。
- 复合函数：两个函数可以组合成一个新的函数。
5. 图论- 图的基本概念：由顶点（节点）和边组成的结构。
- 图的类型：无向图、有向图、连通图、树等。
- 图的算法：如最短路径、最小生成树、图的着色等。
6. 组合数学- 排列和组合：从n个不同元素中取出r个元素的不同排列和组合的数量。
- 二项式定理：描述了二项式的幂展开的系数。
- 生成函数：一种编码序列的方法，用于解决复杂的计数问题。
7. 递归- 递归定义：一个对象通过引用比自己更小的版本来定义。
- 递归函数：在计算机程序中，一个函数调用自身来解决问题。
结论：离散数学为理解和设计计算机系统提供了基础工具和理论。
它的知识点广泛应用于算法设计、数据结构、编程语言理论和数据库等领域。
掌握离散数学对于任何希望在计算机科学领域取得进展的人来说都是至关重要的。
本文提供了一个简洁的离散数学知识点概述，每个部分都直接针对一个主题，避免了不必要的背景信息和解释。
