下载文档原格式
离散数学知识点总结离散数学是一门研究离散对象及其关系、运算规则的数学学科。
它在计算机科学、信息学等领域中扮演着重要的角色，是这些领域的基础知识之一。
本文将对离散数学的一些重要知识点进行总结。
一、集合论集合论是离散数学的基础，它研究的是元素的集合以及集合之间的关系。
在集合论中，我们需要了解集合的运算、集合的关系、集合的分割等概念。
集合的运算包括交集、并集、差集和补集等，而集合的关系则包括子集、包含关系等。
此外，集合的分割也是一个重要的概念，它将一个集合划分为不相交的子集。
二、图论图论是离散数学中的重要分支，它研究的是图的性质和图之间的关系。
图由节点和边组成，节点表示对象，边表示对象之间的关系。
图论的核心概念包括图的表示方法、图的遍历算法、最短路径算法等。
在实际应用中，我们可以利用图论来解决线路规划、网络优化等问题。
三、逻辑与真值表逻辑是离散数学的重要组成部分，它研究的是命题之间的关系，以及命题的真值。
逻辑的核心概念包括命题、谓词、命题逻辑和一阶谓词逻辑等。
命题逻辑研究的是命题之间的关系，通过真值表可以展示命题的真值。
一阶谓词逻辑则考虑了命题中的变量、量词等。
四、组合数学组合数学是研究离散对象组合方式的数学学科。
它包括排列、组合、二项式系数等概念。
排列是指从一组对象中取出一些对象按照一定的顺序排列，而组合则是指从一组对象中取出一些对象作为一个集合。
二项式系数是组合数学中常用的工具，它表示在一组对象中选择出一个子集的方式数目。
五、数论数论是离散数学中研究自然数的性质和关系的学科。
它研究整数、素数、同余关系等。
数论的核心概念包括质数与合数、素数分解、同余关系和模运算等。
数论在加密算法、密码学中有广泛的应用，对于保证数据安全性至关重要。
总结起来，离散数学是一门研究离散对象及其关系、运算规则的数学学科，其中包括集合论、图论、逻辑与真值表、组合数学和数论等重要知识点。
它在计算机科学、信息学等领域中具有重要的应用价值。
离散数学笔记第一章命题逻辑合取析取定义 1. 否定：当某个命题为真时.其否定为假.当某个命题为假时.其否定为真定义 1. 条件联结词.表示“如果……那么……”形式的语句定义 1. 双条件联结词.表示“当且仅当”形式的语句定义合式公式(1)单个命题变元、命题常元为合式公式.称为原子公式。
(2)若某个字符串 A 是合式公式.则⌝A、(A)也是合式公式。
(3)若 A、B 是合式公式.则 A ∧B、A∨B、A→ B、A↔B 是合式公式。
(4)有限次使用(2)~(3)形成的字符串均为合式公式。
等值式析取范式与合取范式将一个普通公式转换为范式的基本步骤推理定义 设 A 与 C 是两个命题公式. 若 A → C 为永真式、 重言式.则称 C 是 A 的有 效结论.或称 A 可以逻辑推出 C.记为 A => C 。
（用等值演算或真值表）第二章 谓词逻辑、基本概念∀：全称量词 ∃：存在量词一般情况下. 如果个体变元的取值范围不做任何限制即为全总个体域时. 带 “全称量词”的谓词公式形如"∀x(H(x)→B(x)).即量词的后面为条件式.带“存在量词”的谓词公式形如∃x(H(x)∨WL(x)).即量词的后面为合取式 例题R(x)表示对象 x 是兔子.T(x)表示对象 x 是乌龟. H(x,y)表示 x 比 y 跑得快.L(x,y)表示x 与 y 一样快.则兔子比乌龟跑得快表示为： ∀x ∀y(R(x)∧T(y)→H(x,y))有的兔子比所有的乌龟跑得快表示为：∃x ∀y(R(x)∧T(y)→H(x,y))、谓词公式及其解释定义 、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22y x 的 f(x,y))、 谓词常元(如表示人类的 H(x))。
定义 、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。
定义 、项的定义：个体常元、变元及其函数式的表达式称为项(item)。
图论基本概念重要定义：有向图：每条边都是有向边的图。
无向图：每条边都是无向边的图。
混合图：既有有向边又有无向边的图。
自回路：一条边的两端重合。
重数：两顶点间若有几条边，称这些边为平行边，两顶点a,b间平行边的条数成为（a,b）的重数。
多重图：含有平行边的图。
简单图：不含平行边和自回路的图。
注意！一条无向边可以用一对方向相反的有向边代替，因此一个无向图可以用这种方法转化为一个有向图。
定向图：如果对无向图G的每条无向边指定一个方向由此得到的有向图D。
称为的G定向图. 底图：如果把一个有向图的每一条有向边的方向都去掉，得无向图G称为的D底图。
逆图：把一个有向图D的每条边都反向由此得到的图称为D的逆图。
赋权图：每条边都赋上了值。
出度：与顶点相连的边数称为该定点的度数，以该定点为始边的边数为出度。
入度：以该定点为终边的边数为入度。
特殊！度数为零的定点称为孤立点。
度数为一的点为悬挂点。
无向完全图：在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。
Kn完全有向图：在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。
竟赛图：阶图中如果其底图是无向完全图，则程此有向完全图是竟塞图。
注意！n阶有向完全图的边数为n的平方；无向完全图的边数为n(n-1)/2。
下面介召图两种操作：①删边：删去图中的某一条边但仍保留边的端点。
②删点：删去图中某一点以及与这点相连的所有边。
子图：删去一条边或一点剩下的图。
生成子图：只删边不删点。
主子图：图中删去一点所得的子图称的主子图。
补图：设为阶间单无向图，在中添加一些边后，可使成为阶完全图；由这些添加边和的个顶点构成的图称为的补图。
重要定理：定理5.1.1 设图G是具有n个顶点m条边的有向图，其中点集V={v,v, (v)deg+(vi)=deg-(vi)=m定理5.1.2 设图G是具有n个顶点m条边的无向图，其中点集V={v,v,v, (v)deg(vi)=2m推论在无向图中，度数为积数的顶点个数为偶数。
数学中的离散数学理论离散数学理论是数学中一门相对较新的分支，它主要研究数学结构和算法的离散化。
离散数学理论是现代信息科学和计算机科学中的核心学科，是计算机程序设计和计算机科学中不可或缺的一部分。
离散数学理论包括很多基本概念，例如图形理论、集合理论、函数理论、逻辑、代数理论等等。
这些概念不仅被应用于计算机科学和信息科学中，而且在各种各样的应用程序中都有广泛的应用。
例如，图形理论将结构的整体看作是一组点（节点）和这些点之间的线（边）的集合，这些边连接不同的顶点。
在图形理论中，有两种图形，一种是有向图，另一种是无向图。
有向图中每一条边连接两个顶点并指向其中的一个；而无向图中每一条边都连接两个顶点并没有指向性。
图形不仅能表示数据，而且还能表示图形的性质，从而最终可以被应用于极为广泛的应用程序中。
与图形理论相似，集合理论将其视为一组元素的集合，有多种运算符可以用于比较两个集合。
最基本的运算符是交并运算符，它们用于比较两个集合中是否包含共同元素。
此外，还有差分运算符，它用于比较两个集合中仅包含其中一个集合的元素。
函数理论是研究函数及其性质的一个分支。
它是在函数的定义范围内研究函数的一个基本概念，函数是一个将一组数字映射到另一组数字的关系。
在函数理论中，有两个非常相关的概念，一个是定义域（函数的输入），另一个是值域（函数的输出）。
在函数的定义域中有一组数字，或者称为输入，经过函数映射得到的输出可以再进入另一个函数，或者是一个特定的算法中，从而构成了连锁反应。
函数理论可以为开发算法和编写程序提供基本规则。
逻辑是关于推理和推导的学科，它是数学中的一种基本分支。
逻辑的主要研究内容是人类思维中的推理和证明，它是建立数学、自然科学以及社会科学中合理推论的基础。
在逻辑中，有两种主要的命题逻辑和谓词逻辑，它们被用于定义推理中的不同命题形式。
代数理论是关于代数对象或代数系统的研究。
在代数学中，对象可以是数字、符号、以及其他数学结构。
离散数学总复习第1章命题逻辑一、命题的判断例：1、仁者无敌！2、x+y<23、如果雪是红的，那么地球是月亮的卫星。
4、我正在说谎。
二、命题符号化例：1、蓝色和黄色可以调成绿色。
2、付明和杨进都是运动员。
3、刘易斯是百米游泳冠军或百米跨栏冠军。
4、李飞现在在宿舍或在图书馆。
5、只要天不下雨，我就步行上学校。
6、只有天不下雨，我才步行上学校。
7、并非只要你努力了，就一定成功。
三、主范式1、会等值演算；2、主合取和主析取范式的相互转换。
例：求命题公式P∨Q的主析取范式和主合取范式。
3、根据主范式进行方案的选择例1：某科研所要从3名科研骨干A,B,C中挑选1-2名出国进修，由于工作需要，选派需同时满足条件：（1）若A去，则C同去；（2）只有C不去，B才去；（3）只要C不去，则A或B就可以去。
问有哪些选派方案？例2：甲、乙、丙、丁四人有且仅有两个人参加比赛，下列四个条件均要满足：（1）甲和乙有且只有一人参加；（2）丙参加，则丁必参加；（3）乙和丁至多有一人参加；（4）丁不参加，甲也不会参加。
问哪两个人参加了比赛？四、简单的推理例1：如果明天天气好我们就去爬长城。
明天天气好。
所以我们去爬长城。
例3：课后习题16第2章谓词逻辑一、谓词逻辑中的命题符号化例：1、所有运动员都是强壮的2、并非每个实数都是有理数3、有些实数是有理数二、量词的辖域，约束变元换名、自由变元代替例：1、∀x(P(x)∨∃yR(x,y))→Q(x)2、∀x(P(x,z)∨∃yR(x,y))→Q(x)中量词的辖域，重名情况，改名等三、命题逻辑永真式的任何代换实例必是谓词逻辑的永真式。
同样，命题逻辑永假式的任何代换实例必是谓词逻辑的永假式。
例：1、(∀xP(x)→∃xQ(x))↔(⌝∀xP(x)∨∃xQ(x))2、(∀xP(x)→∃xQ(x))∧(∃xQ(x))→∀zR(z)))→(∀xP(x) →∀zR(z))1-2是永真式（重言式）3、⌝(∀xF(x) ∃yG(y)) ∧ ∃yG(y) 永假式（矛盾式）四、消量词例：个体域D={1,2}，对∀x∀y(P(x)→Q(y))消量词五、简单的前束范式会判断即可。
离散数学在其他学科及现实生活中的应用一、离散数学概论离散数学是现代数学的一个重要分支，也是计算机专业课程体系中地位极为重要的专业基础课之一。
它以研究离散量的结构及相互关系为主要目标，充分描述了计算机科学离散性的特点。
该课程是数据结构、操作系统、计算机网络、算法设计与分析、软件工程、人工智能、形式语言、编译原理等计算机本科阶段核心课程的基础，也是组合数学、遗传算法、数据挖掘等计算机硕士研究生阶段相关课程的重要基础。
离散数学的主要内容包括集合论、数理逻辑、代数结构和图论四部分。
数理逻辑与代数结构的研究思想和研究方法在计算机科学中的许多研究领域得到了广泛的应用，解决了大量的计算机科学问题。
数理逻辑是研究推理的学科，在人工智能、程序理论和数据库理论等的研究中有重要的应用。
代数结构是关于运算或计算规则的学问，在计算机科学中，代数方法被广泛应用于许多分支学科，如可计算性与计算复杂性、形式语言与自动机、密码学、网络与通信理论、程序理论和形式语义学等。
集合论和图论在计算机科学中也有广泛的应用，他们为数据结构和算法分析奠定了数学基础，也为许多问题从算法角度如何加以解决提供了进行抽象和描述的一些重要方法。
离散数学不仅是计算机技术迅猛发展的支撑学科，更是提高学生逻辑思维能力、创造性思维能力以及形式化表述能力的动力源，为他们今后处理离散信息，从事计算机应用、信息管理和计算机科研打下扎实的数学基础。
中国科学院也已成立了离散数学研究中心，并得到国家的重点资助。
二、应用2.1离散数学在计算机学科中的应用计算机学科主要脱胎发源于数学学科，离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。
由于计算机科学的迅速发展，与其有关的领域中，提出了许多有关离散量的理论问题，需要用某些数学的工具做出描述和深化。
离散数学把计算机科学中所涉及到的研究离散量的数学综合在一起，进行较系统的、全面的论述，为研究计算机科学的相关问题提供了有力的工具。
离散数学当前位置： 离散数学在线教程 首页 学习空间 课程教学离散数学绪论集合论初步关系与映射代数系统基础无限集重言式布尔代数及应用群论基础半群图论基本概念图的矩阵表示Euler,Hamilton图通路，回路，连通性命题及连接词命题公式基本逻辑等价式离散试卷习题讲解离散问题（集合论初步）离散问题（函数，无限集）离散问题（二元关系）离散问题（代数系统）离散问题（图论）指导老师：李志林离散数学绪论1．计算机科学与离散数学计算机科学是与计算机软件硬件有关的各学科的总称,特点是离散性,离散数学是研究离散量的结构及其相互间关系的一门学科。
【实例1】布尔代数({0,1},+,*,~)在电子科学和数理逻辑中可得到具体解释。
【实例2】计算机中鼓轮的设计用到图论知识。
2．离散数学的特征（1）研究离散量（2）重视能行性的研究3．离散数学的内容集合论初步第一节集合理论基础1．集合的概念一般认为，集合是一些确定的对象的全体，对象称为元素，若a是集合A的元素，则记为a ∈A集合的表示方法：（1）列举法：列举出元素。
（2）描述法：把元素的共同性质描述出来。
（3）谓次表示法：{x|P(x)}（借助一些逻辑记号）.常见的集合：（1）空集：{ }或（2）单元素集合：只含一个元素（3）全集：所考虑的对象的全体（4）常用记号：N, Z, Q, R等2．集合的关系【DEF1】若集合A, B的元素相同，则称A, B是相等的，记为A=B，否则A和B是不相等的，记为A≠B【DEF2】若a∈A一定有a∈B，则称A是B的子集，记为，若，但是A≠B，则称A是B的真子集，记为.3．集合的运算【DEF1】集合A与B的交集A∩B={x|x∈A或x∈B}【DEF2】并集A∪B={ x|x∈A和x∈B}【DEF3】A, B是分离的，若A∩B=【DEF4】集合A对B的差A-B={ x|x∈A和x B }【DEF5】集合A的补集为全集E与A的差，记为A’【DEF6】集合A与B的对称差A⊕B=（A-B）∪（B-A）集合的运算律如下：（1）交换律A∩B=B∩A，A∪B=B∪A（2）结合律（A∩B）∩C=A∩（B∩C）（3）分配律A∩（B∪C）=（A∩B）∪（A∩C）（4）等幂律A∩A=A，A∪A=A（5）零一律A∩E=A，A∪=A，A∩=，A∪E=E（6）互补律A∩A’ =，A∪A’ =E，A’’=A（7）DeMorgan律（A∩B）’= A’∪B’（8）吸收律A∪（A∩B）=A，A∩（A∪B）=A运算律的特点：（1）对称性（2）对偶性第二节幂集， n元有序组，Descartes积1．幂集【DEF1】由A的所有子集组成的集合称为A的幂集，记为P（A）或【DEF2】集合A中元素的个数称为A的基数，记为 |A|【TH1】 A是有限集，则||=【证明】设 |A|=n，则||=.【TH2】（包含排除原理）A1, …, A n是有限集，则|A1∪…∪A n|=【证明】数学归纳法。
【思考】（1）有一个班级50个学生，第一次考试有23人得优，第二次考试有20人得优，两次均未得优有15人，问多少人两次均得优？（1）求{a}幂集的幂集。
（2）求1到250间能被2, 3, 5, 7中任一个整除的整数个数。
2．n元有序组【DEF1】按一定次序排列的两个客体a, b组成的序列称为序偶，记为（a, b）.【DEF2】若a1=b1，a2=b2，则（a1, a2）=（a2, b2）【DEF3】按一定次序排列的n个客体a1, a2, …, a n组成的序列称为n元有序组，记为（a1，a2，…, a n）【DEF4】若a i=b（i=1, 2, …, n)，则i（a, a2, …, a n）=（b1, b2, …, b n）13． Descartes积【DEF1】集合A, B的Descartes积（又称为叉积）为A×B={（a, b）|a∈A, b∈B}，A称为前集，B称为后集。
【DEF2】集合A, A2, …, A n的Descartes积为1×…×A n={(a1, a2, …, a n）|a i∈A i}A1【注记】（1）A×B≠B×A；（2）A×A记为A2.【思考】（1）A={0, 1}，B={1, 2}，求A2×B, A×P(A)（2）判断下列各式是否正确：①（A∩B）×（C∩D）=（A×C）∩（B×D）②（A-B）×（C-D）=（A×C) -（B×D)关系与映射第一节关系的概念1.1 关系的定义【DEF1】A×B的子集R称为A到B的一个关系。
当（a, b）∈R时，称a与b有关系R，记为aRb.R的定义域为D（R）={a|存在b使得（a, b）∈R}，R的值域为C（R）={b|存在a使aRb} .A到A的关系R称为A上的关系。
A上的关系R={(a, a)|a∈A }称为A上的恒等关系。
【DEF2】A1×A2×…×A n的子集R称为由A1, A2, … , A n确定的n元关系。
1.2 关系的表示一、关系图（1）A到B的关系图采用一般的映射图。
（2）A上的关系图是图论中的有向图。
二、关系矩阵设A={a1, a2, … , a m }，B={b1, b2, … , b n }，z则A到B的关系R的矩阵为第二节关系的运算2.1 关系的补、并、交关系是集合，故可以进行集合的运算，设R、S是集合A到B的关系，则R′=A×B - R，R∪S={(a, b)|(aRb)∨(aSb)}.2.1.1 复合关系【DEF1】R是A到B的关系，S是B到C的关系，则R与S的复合关系为={(a, c)|a∈A, c∈C，有b∈B使aRb, bSc}【TH1】复合运算满足结合律。
【DEF2】R是A上的关系，则R的幂为【TH2】.2.3 关系的逆【DEF1】设R是A到B的关系，则B到A的关系R~={(y, x)|(x, y) ∈R }称为R的逆关系。
【TH1】第三节关系的性质本节讨论A上的二元关系的性质。
【DEF1】R是上的关系，对每个a均有aRa，则R称为自反关系（reflexive）.【DEF2】若对每个a均有，则R是反自反的。
【DEF3】若（a, b）∈R→（b, a）∈R，则R称为对称的（Symmetric）.【DEF4】若xRy且yRx→x=y，则R称为反对称的（Antisymmetric）.【DEF5】若xRy, yRz→xRz，则R称为传递的。
【注记】可以从关系图，关系矩阵判断关系的性质R是自反的←→关系图中每点有环←→关系矩阵d的主对角元均为1R对称←→关系图中边成对出现←→关系矩阵是对称阵。
【思考】（1）判断A上的空关系Ф，全关系A×A，恒等关系I的性质。
（2）设A={1,2,3,4}，写出关系R，使得R不是自反的，也不是反自反的。
第四节关系的闭包【DEF1】 R 是A 上的关系，若有另一个关系R’ 使得（1）R’ 是自反的（对称的，传递的），（2）R’ 包含R ，（3）对任一个自反关系（对称关系，传递关系）R’’ ，若R’’ 包含R ，则R’’ 包含R’ ，那么R’ 称为R 的自反闭包（对称闭包，传递闭包），记为r （R ）（s （R ）, t （R ））.【TH1】 设R 是A 上的关系，则r （R ）=R ∪I ，I 是A 上的恒等关系。
【TH2】 s （R ）=R ∪R ~【TH3】【TH4】 设|A |=n ，则【注记】闭包运算可以转化为矩阵运算。
【思考】 （1）A={1，2，3}，R={（1，2），（2，3），（3，1）}，求r （R ），s（R ），t （R ）.（2）N 上的关系为R={（0,1）, (1, 2), …, (n , n+1),…} 求r （R ），s （R ），t （R ）.第五节 次序关系5.1 偏序关系【DEF1】 设A 是一个集合，R 是A 上的关系，R 是自反的，反对称的，传递的，则R 称为A 上的偏序(半序)（1）偏序R 常记为≤，A 是R 的偏序集，记为(A , ≤)【注记】（1）偏序关系的实质在于建立A 的元素之间的可比结构。
（2）偏序关系可用Hasse 图（一种下行图）表示。
【DEF2】 （A ，≤)是偏序集，对任意a, b ∈A ，必有aRb （a ≤b ）或bRa （b ≥a ），则≤称为全序。
【DEF3】 设（A ，≤) 是偏序集，B 是A 的子集（1）若B 中元素X 0比B 中任何元素都要“大”（“小”），则X 0称为B 的最大元（最小元）（2）若B 中没有比X 0更大(更小)的元素，则X 0称为B 的极大元（极小元）.（3）集合A中比B中元素都大（小）的元素，称为集合B的上界（下界）.（4）B的最大的下界称为下确界，记为GLB（B），B的最小的上界称为上确界，记为LUB （B）【注记-】（1）最大元最多一个，极大元可能有多个。
（2）最大元必是极大元，反之不然。
（3）最大元必是上确界，反之不然.（4）最大元，极大元等均可从Hasse图中看出来。
【思考】集合A={1，2，3，4，6，8，12，24}，A上关系R={（x, y）|x,y∈A且x|y}，且B= {4，6，12}的最大元，最小元，极大元，极小元，上下确界。
5.2 拟序【DEF1】若A上的关系R是反自反的，传递的，则R称为A上的拟序，记为 <【TH1】若R是A上的拟序，则R是反对称的。
【注记】（1）偏序是拟序地扩充，拟序是偏序的缩减。
（2）偏序，拟序均称为次序。
第六节相容关系【DEF1】R是A上关系，R是自反的，对称的，则R称为A上的相容关系。
【例1】设集合A={cat, teacher, cold, desk, knife, by}，R={(x, y)|x, y∈A，且x, y有相同的字母}，则R是相容的。
【DEF2】设A≠Ф，S={S1, S2, …, S n}，S i是A的非空子集，且S1∪S2∪…∪S n=A，则S称为A的覆盖，若又有S i∩S j=Ф（i≠j），则称为A的划分。
【例2】写出A={1, 2, 3}的所有划分。
【DEF3】R是A上的相容关系，C r是A的子集，C r中任意的两个相容，若A-C r中没有元素与C r中所有元素相容，则C r称为A的极大相容类。
【例3】求例1中的极大相容类。
【DEF4】A的极大相容类的集合称为A的完全覆盖。
【TH1】 {A1，…, A n}是A的一个覆盖，则R=A1×A1∪…∪A n×A n是A上的相容关系。
【TH2】A上的相容关系R与完全覆盖是一一对应的。
