离散数学I考试知识点

离散知识点公式总结1. 集合论集合是离散数学中的基本概念，它是由一些确定的对象所组成的一个整体。

集合之间的运算包括并集、交集、差集、补集等。

其相关公式如下：- 并集：对于集合A和B，它们的并集定义为包含A和B中所有元素的集合，记作A∪B。

公式：A∪B={x|x∈A或x∈B}- 交集：对于集合A和B，它们的交集定义为同时属于A和B的所有元素的集合，记作A∩B。

公式：A∩B={x|x∈A且x∈B}- 差集：对于集合A和B，A与B的差集定义为属于A但不属于B的元素所组成的集合，记作A-B。

公式：A-B={x|x∈A且x∉B}- 补集：对于集合A，相对于全集合U而言，A的补集定义为全集合中不属于A的元素所组成的集合，记作A'。

公式：A'={x|x∈U且x∉A}2. 关系和函数关系是一种描述元素之间的对应关系的数学工具，而函数则是一种特殊的关系。

在离散数学中，关系和函数的定义和性质是非常重要的内容。

其相关公式如下：- 关系R：对于集合A和B，关系R定义为A和B的笛卡尔积中的元素对所组成的集合。

公式：R={(a,b)|a∈A且b∈B}- 函数f：对于集合A和B，如果f是从A到B的一个映射，那么对于任意元素a∈A，都有唯一的元素b∈B与之对应。

公式：f:A→B3. 图论图论是离散数学中的一个重要分支，它研究的是由顶点和边组成的数学结构。

图论的基本概念包括图的类型、路径和回路、连通性、树等。

其相关公式如下：- 有向图：对于图G=(V,E)，如果E中的边是有方向的，则称G为有向图。

公式：G=(V,E)，E={(u,v)|u,v∈V，u→v}- 无向图：对于图G=(V,E)，如果E中的边是无方向的，则称G为无向图。

公式：G=(V,E)，E={{u,v}|u,v∈V，u≠v}- 路径：在图G中，顶点v1,v2,...,vn的一个路径是图G中的一个顶点序列，其中相邻的顶点用一条边连接。

公式：v1,v2, (v)- 回路：在图G中，如果一条路径的起点和终点是同一个顶点，则称其为回路。

离散数学知识点总结离散数学是一门研究离散对象及其关系、运算规则的数学学科。

它在计算机科学、信息学等领域中扮演着重要的角色，是这些领域的基础知识之一。

本文将对离散数学的一些重要知识点进行总结。

一、集合论集合论是离散数学的基础，它研究的是元素的集合以及集合之间的关系。

在集合论中，我们需要了解集合的运算、集合的关系、集合的分割等概念。

集合的运算包括交集、并集、差集和补集等，而集合的关系则包括子集、包含关系等。

此外，集合的分割也是一个重要的概念，它将一个集合划分为不相交的子集。

二、图论图论是离散数学中的重要分支，它研究的是图的性质和图之间的关系。

图由节点和边组成，节点表示对象，边表示对象之间的关系。

图论的核心概念包括图的表示方法、图的遍历算法、最短路径算法等。

在实际应用中，我们可以利用图论来解决线路规划、网络优化等问题。

三、逻辑与真值表逻辑是离散数学的重要组成部分，它研究的是命题之间的关系，以及命题的真值。

逻辑的核心概念包括命题、谓词、命题逻辑和一阶谓词逻辑等。

命题逻辑研究的是命题之间的关系，通过真值表可以展示命题的真值。

一阶谓词逻辑则考虑了命题中的变量、量词等。

四、组合数学组合数学是研究离散对象组合方式的数学学科。

它包括排列、组合、二项式系数等概念。

排列是指从一组对象中取出一些对象按照一定的顺序排列，而组合则是指从一组对象中取出一些对象作为一个集合。

二项式系数是组合数学中常用的工具，它表示在一组对象中选择出一个子集的方式数目。

五、数论数论是离散数学中研究自然数的性质和关系的学科。

它研究整数、素数、同余关系等。

数论的核心概念包括质数与合数、素数分解、同余关系和模运算等。

数论在加密算法、密码学中有广泛的应用，对于保证数据安全性至关重要。

总结起来，离散数学是一门研究离散对象及其关系、运算规则的数学学科，其中包括集合论、图论、逻辑与真值表、组合数学和数论等重要知识点。

它在计算机科学、信息学等领域中具有重要的应用价值。

注意/技巧：析取符号为V，大写字母Vx + y = 3不是命题前件为假时，命题恒为真运用吸收律命题符号化过程中要注意命题间的逻辑关系，认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。

也就是说，在不改变原意的基础上，按照最简单的方式翻译通用的方法：真值表法VxP（x）蕴含存在xP（x）利用维恩图解题证明两个集合相等：证明这两个集合互为子集常用的证明方法：任取待证集合中的元素<,>构造相应的图论模型第一章命题逻辑命题和联结词命题的条件：表达判断的陈述句、具有确定的真假值。

选择题中的送分题原子命题也叫简单命题，与复合命题相对简单联结词的真值表要记住非（简单）合取（当且仅当P，Q都为真时，命题为真）析取（当且仅当P，Q都为假时，命题为假），P，Q可以同时成立，是可兼的或条件（→）（当且仅当P为真，Q为假时，命题为假）P是前件，Q是后件只要P，就Q等价于P→Q只有P，才Q等价于非P→非Q，也就是Q→PP→Q特殊的表达形式：P仅当Q、Q每当P双条件（↔）（当且仅当P与Q具有相同的真假值时，命题为真，与异或相反）命题公式优先级由高到低：非、合取和析取、条件和双条件括号省略条件：①不改变先后次序的括号可省去②最外层的括号可省去重言式（永真式）、矛盾式（永假式）、偶然式可满足式：包括重言式和偶然式逻辑等价和蕴含（逻辑）等价:这是两个命题公式之间的关系，写作“⇔”，要与作为联结词的↔区分开来。

如果命题公式A为重言式，那么A⇔T常见的命题等价公式：需要背过被标出的，尽量去理解。

关键是掌握公式是将哪个符号转换为了哪个符号，这对于解证明题有很大的帮助！验证两个命题公式是否等价：当命题变元较少时，用真值表法。

当命题变元较多时，用等价变换的方法，如代入规则、替换规则和传递规则定理：设A、B是命题公式，当且仅当A↔B是一个重言式时，有A和B逻辑等价。

蕴含:若A→B是一个重言式，就称作A蕴含B，记作A⇒B常见的蕴含公式的运用方法同上面的命题等价公式证明A⇒B：①肯定前件，推出后件为真②否定后件，推出前件为假当且仅当A⇒B且B⇒A时，A⇔B，也就是说，要证明两个命题公式等价，可以证明它们相互蕴含联结词的完备集新的联结词：条件否定、异或（不可兼或）、或非（析取的否定）、与非（合取的否定）任意命题公式都可由仅含{非，析取}或{非，合取}的命题公式来等价地表示全功能联结词集合极小全功能联结词集合对偶式对偶式：将仅含有联结词非、析取、合取（若不满足，需先做转换）的命题公式A中的析取变合取，合取变析取，T变F，F变T得到的命题公式A*称为A的对偶式范式析取式：否定+析取合取式：否定+合取析取范式：（合取式）析取（合取式）……析取（合取式）。

大一离散数学知识点归纳离散数学是大一学生在计算机科学和相关学科中最常接触的数学分支之一。

它涉及的知识点广泛且重要，对于学习和理解其他高级课程至关重要。

下面是对大一离散数学知识点的归纳。

1. 集合论1.1 集合的定义和表示1.2 集合的运算（并、交、差、补）1.3 子集、真子集、幂集1.4 集合的基本性质（交换律、结合律、分配律）1.5 集合的等价关系和等价类1.6 集合的基数和无限集2. 逻辑与命题2.1 命题的定义和性质2.2 命题的逻辑运算（与、或、非、异或、蕴含、等价）2.3 命题的真值表和简化2.4 谓词逻辑和量词2.5 命题逻辑的推理和证明方法2.6 命题逻辑的应用（布尔代数、逻辑电路）3. 数理归纳法3.1 数学归纳法的基本原理3.2 强归纳法和弱归纳法3.3 数学归纳法的应用（证明数学命题、计算算法复杂度）4. 图论4.1 图的基本概念（顶点、边、度、路径、环）4.2 连通图和孤立点4.3 树和森林4.4 图的遍历算法（深度优先搜索、广度优先搜索）4.5 最小生成树和最短路径问题4.6 图的应用（社交网络、路线规划）5. 关系与函数5.1 关系的定义和表示5.2 关系的性质（自反性、对称性、传递性、等价关系） 5.3 关系的闭包和传递闭包5.4 函数的定义和性质5.5 单射、满射和双射5.6 函数的复合和反函数6. 组合数学6.1 排列和组合的基本概念6.2 二项式系数和杨辉三角6.3 递归和递推关系6.4 置换和循环节6.5 容斥原理和鸽笼原理6.6 组合数学的应用（概率、计数问题）7. 布尔代数7.1 逻辑代数和布尔运算7.2 布尔函数和真值表7.3 极小项和主析取范式7.4 逻辑函数的化简和设计7.5 布尔代数的应用（逻辑电路、开关网络）这些是大一离散数学课程中的一些重要知识点，通过对这些知识点的学习和理解，学生将能够为将来的计算机科学和相关领域的学习打下坚实的基础。

同时，离散数学的思维方式和证明方法也会培养学生的逻辑思维和问题解决能力。