离散知识点公式总结
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→B
3. 图论
图论是离散数学中的一个重要分支，它研究的是由顶点和边组成的数学结构。图论的基本概念包括图的类型、路径和回路、连通性、树等。其相关公式如下：
- 有向图：对于图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中的一个顶点序列，其中相邻的顶点用一条边连接。
离散数学重要公式定理汇总分解
离散数学是计算机科学领域中的一门基础课程，它主要研究离散结构和离散对象之间的关系。离散数学中有许多重要的公式和定理，这些公式和定理在计算机科学和其他领域中有广泛的应用。下面是对离散数学中一些重要的公式和定理的汇总。
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)!)
以上只是离散数学中一小部分重要的公式和定理，这些公式和定理在计算机科学、密码学、图形学等领域中有广泛的应用。对于学习离散数学的同学来说，熟悉这些公式和定理的含义和运用方法，能够帮助他们更好地理解和应用离散数学的知识。
基本等值式
1.双重否定律 A Û ┐┐A
2.幂等律 A Û A∨A, A Û A∧A
3.交换律 A∨B Û B∨A， A∧B Û B∧A
4.结合律 (A∨B)∨C Û A∨(B∨C) (A∧B)∧C Û A∧(B∧C)
5.分配律 A∨(B∧C) Û (A∨B)∧(A∨C) （∨对∧的分配律）
A∧(B∨C) Û (A∧B)∨(A∧C) （∧对∨的分配律）
6.德·摩根律 ┐(A∨B) Û ┐A∧┐B ┐(A∧B) Û ┐A∨┐B
7.吸收律 A∨(A∧B) Û A，A∧(A∨B) Û A
8.零律 A∨1 Û 1,A∧0 Û 0
9.同一律 A∨0 Û A，A∧1 Û A
10.排中律 A∨┐A Û 1
11.矛盾律 A∧┐A Û 0
12.蕴涵等值式 A→B Û ┐A∨B
13.等价等值式 A«B Û (A→B)∧(B→A)
14.假言易位 A→B Û ┐B→┐A
15.等价否定等值式 A«B Û ┐A«┐B
16.归谬论 (A→B)∧(A→┐B) Û ┐A
求给定公式范式的步骤
(1)消去联结词→、«(若存在)。
(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。
(3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。
推理定律--重言蕴含式
(1) A Þ (A∨B) 附加律
(2) (A∧B) Þ A
化简律
(3) (A→B)∧A Þ B
离散数学基本公式
离散数学是数学的一个重要分支，它主要研究的是非连续的、分离的对象，如集合、图论、数论、逻辑等。在这些领域中，一些基本的公式和定理是理解和应用离散数学的关键。以下是一些离散数学的基本公式：
1、德摩根定律
德摩根定律是布尔代数中的基本公式之一，它表示对于任何逻辑运算，如果我们把所有的否命题和原命题结合在一起，我们就会得到一个恒等式。
用符号表示为：
P ∧ Q) ∨ (¬P ∧ ¬Q) ≡ P ∨ Q
P ∨ Q) ∧ (¬P ∨ ¬Q) ≡ P ∧ Q
2.集合论中的互补律
在集合论中，互补律表示对于任何集合A和它的补集A'，我们有：
A ∪ A' = U,其中U是全集 A ∩ A' = ∅,其中∅表示空集
3.图论中的欧拉公式
欧拉公式是图论中的一个基本公式，它表示对于一个连通无向图G，其顶点数v、边数e和欧拉数euler(G)之间有以下关系：
euler(G) = v + e - 2
其中euler(G)是图G的欧拉数，v是图G的顶点数，e是图G的边数。这个公式在计算图的欧拉数或者判断一个图是否连通等方面都有重要应用。
4.数论中的费马小定理
费马小定理是数论中的一个重要定理，它表示对于任何正整数n，如果它是质数p的幂次方，那么我们可以找到一个整数x，使得x的n次方等于1（模p）。
用数学语言表示为：
x^n ≡ x (mod p)
其中n是正整数，p是质数，x是整数。这个定理在密码学、计算机科学等领域都有广泛的应用。
5.逻辑中的排中律和反证法
排中律是指对于任何命题P，P或非P必定有一个是真命题。反证法则是通过假设相反的命题成立来证明原命题的一种方法。在证明过程中，如果假设的相反命题成立会导致矛盾，那么原命题就一定是正确的。
这些公式和定理只是离散数学中的一小部分，但它们是理解和应用离散数学的基础。在学习的过程中，我们还需要掌握更多的公式和定理，以及它们的应用方法。
离散数学教程集合的基本概念
