下载文档原格式
离散数学笔记（特级教师精心整理）第一章命题逻辑内容：命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法教学目的：1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。
2．熟练掌握常用的基本等价式及其应用。
3．熟练掌握（主）析/合取范式的求法及其应用。
4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。
5．熟练掌握形式演绎的方法。
教学重点：1．命题的概念及判断2．联结词，命题的翻译3．主析（合）取范式的求法4．逻辑推理教学难点：1．主析（合）取范式的求法2．逻辑推理1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。
1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。
A1:我是一名大学生.[10]：我是一名大学生。
R：我是一名大学生。
1.2命题联结词（1） P↑P⇔﹁（P∧P）⇔﹁P；（2）（P↑Q）↑（P↑Q）⇔﹁（P↑Q）⇔ P∧Q；（3）（P↑P）↑（Q↑Q）⇔﹁P↑﹁Q⇔ P∨Q。
（1）P↓P⇔﹁（P∨Q）⇔﹁P；（2）（P↓Q）↓（P↓Q）⇔﹁（P↓Q）⇔P∨Q；（3）（P↓P）↓（Q↓Q）⇔﹁P↓﹁Q⇔﹁（﹁P∨﹁Q）⇔P∧Q。
1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P 是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、 P↔Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。
例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）↔（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）↔（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。
离散数学期末总结离散数学是描绘一些离散量与量之间的相互逻辑构造及关系的学科。
它的思想方法及内容渗透到计算机学科的各个领域中。
因此它成为计算机及相关专业的一门重要专业根底课。
主要内容包括：集合论、关系、代数系统、图论和数理逻辑五个部分。
构造上，从集合论入手，后介绍数理逻辑，便于学生学习。
为了能很好的消化理解内容，列举了大量的较为典型、易于承受、说明问题的例题，配备了相当数量的习题，也列举了部分实际应用问题。
一．知识点第一章.集合论集合论或集论是研究集合（由一堆抽象物件构成的整体）的数学理论，包含集合、元素和成员关系等最根本数学概念。
在大多数现代数学的公式化中，集合论提供了要如何描述数学物件的语言。
本章主要介绍集合的根本概念、运算及幂集合和笛卡尔乘积。
这章是本书的根底部分，要学好离散数学就必须很好的掌握集合的内容。
集合论的概念和方法已经渗透到所有的数学分支，因而各数学分支的完整体系，都是在所取集合上。
第二章．关系关系在我们日常生活中经常会遇到关系这一概念。
但在数学中关系表示集合中元素间的联系。
本章主要学习关系的根本概念、关系的性质、闭包运算、次序关系、等价关系，本章学习的重点：关系的性质、闭包运算、次序关系。
关系这一章是集合论这一章的延伸，对集合论的理解程度对学习关系这一章是非常有影响的。
而关系又是学习下一章代数系统必不可少的，所以本章是非常重要的章节。
第三章．代数系统代数构造也叫做抽象代数，主要研究抽象的代数系统。
抽象代数研究的中心问题就是一种很重要的数学构造--代数系统：半群、群等等。
本章主要学习了运算与半群、群。
学习本章需要学会判断是否是代数系统、群和半群，以及判断代数系统具有哪些运算规律，如：结合、交换律等及单位元、逆元。
这些都在我们计算机编码中表达出重要的作用。
第四章．图论图论〔Graph Theory〕起源于著名的柯尼斯堡七桥问题，以图为研究对象。
图论中的图是由假设干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
第一章命题逻辑内容：命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法教学目的：1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。
2．熟练掌握常用的基本等价式及其应用。
3．熟练掌握（主）析/合取范式的求法及其应用。
4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。
5．熟练掌握形式演绎的方法。
教学重点：1．命题的概念及判断2．联结词，命题的翻译3．主析（合）取范式的求法4．逻辑推理教学难点：1．主析（合）取范式的求法2．逻辑推理1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。
1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。
A1:我是一名大学生.[10]：我是一名大学生。
R：我是一名大学生。
1.2命题联结词（1） P↑P⇔﹁（P∧P）⇔﹁P；（2）（P↑Q）↑（P↑Q）⇔﹁（P↑Q）⇔ P∧Q；（3）（P↑P）↑（Q↑Q）⇔﹁P↑﹁Q⇔ P∨Q。
（1）P↓P⇔﹁（P∨Q）⇔﹁P；（2）（P↓Q）↓（P↓Q）⇔﹁（P↓Q）⇔P∨Q；（3）（P↓P）↓（Q↓Q）⇔﹁P↓﹁Q⇔﹁（﹁P∨﹁Q）⇔P∧Q。
1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P 是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、 P↔Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。
例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）↔（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）↔（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。
离散数学教学大纲第一部分大纲说明一.课程的性质与任务《离散数学》是现代数学的一个重要分支，也是计算机计算机科学与技术一级学科及其相关专业必修的基础理论的核心课程。
它是学习后续专业课程不可缺少的数学工具。
该课程结合计算机学科的特点，主要研究离散量结构及相互关系，其研究对象一般是有限个或可数个元素，因此《离散数学》充分描述了计算机学科离散性的特点。
它是一门理论性较强，应用性较广的课程。
掌握集合论、数理逻辑、图论、整数、群、环、域、格、布尔代数以及语言与有限自动机等离散数学的基本概念和基本原理，为学习计算机专业各后续课程做好必要的知识准备。
并通过这些知识的学习进一步提高学生的抽象思维和逻辑推理能力，为从事计算机相关的理论研究与应用提供必要的描述工具和理论基础。
二《离散数学》的特点作为计算机科学与技术一级学科的一门课程，《离散数学》有与其他课程相同相似的地方，当然也有它自身的特点：1、义与定理多。
《离散数学》是建立在大量定义之上的逻辑推理学科，因此对概念的理解是我们学习这门课程的核心。
在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理与性质。
2、法性强。
《离散数学》的许多证明题中，方法性是非常强的，如果知道题的证明方法，很容易就可以证出来，反之则事倍功半。
所以在学习该课程中要善于总结，勤于思考，这也是培养分析问题解决问题抽象思维能力的一个过程。
三与其他相关课程的关系先修课程：高等数学（包括数学分析、线性代数）后续课程：数据结构、数据库、编译原理等四课程的主要内容与基本要求本课程分为九部分：集合论基础、命题逻辑、谓词逻辑、图与网络、数论基础、群与环、多项式与有限域、格与布尔代数以及语言和有限自动机。
（一）集合论基础：在整个《离散数学》的知识体系中，集合论处于基础的地位，对于其所包含知识的掌握程度，直接关系到是否能学好图论和抽象代数问题。
本章主要讲述集合、关系和映射。
1. 掌握集合、子集、超集、空集、幂集、集合族的概念。
离散数学第五章习题答案题目1: 定义一个关系R在集合A上，如果对于所有的a, b, c属于A，满足以下条件：- 如果(a, b)属于R，则(b, a)属于R。
- 如果(a, b)属于R且(b, c)属于R，则(a, c)属于R。
证明R是传递的。
答案：根据题目给出的条件，R是对称的和传递的。
首先，对称性意味着如果(a, b)属于R，那么(b, a)也必须属于R。
其次，传递性意味着如果(a, b)和(b, c)都属于R，那么(a, c)也必须属于R。
结合这两个性质，我们可以得出结论：对于任意的a, b, c属于A，如果(a, b)和(b, c)都属于R，那么(a, c)也属于R，从而证明了R的传递性。
题目2: 给定一个函数f: A → B，如果对于A中的每个元素a，都有唯一的b属于B使得f(a) = b，那么称f为单射（或一一映射）。
证明如果函数f是单射，那么它的逆函数f^-1也是单射。
答案：要证明f^-1是单射，我们需要证明对于B中的任意两个元素b1和b2，如果f^-1(b1) = f^-1(b2)，则b1 = b2。
假设f^-1(b1) = a且f^-1(b2) = a'，其中a, a'属于A。
由于f是单射，我们知道f(a) = b1且f(a') = b2。
根据f^-1的定义，我们有b1 = f(a) = f(a') = b2。
因此，如果f^-1(b1) = f^-1(b2)，则b1必须等于b2，这证明了f^-1是单射。
题目3: 证明一个函数f: A → B是满射（或到上映射）当且仅当对于B中的每个元素b，都存在A中的元素a使得f(a) = b。
答案：首先，我们证明如果f是满射，那么对于B中的每个元素b，都存在A 中的元素a使得f(a) = b。
假设f是满射，这意味着B中的每个元素都是A中某个元素的像。
因此，对于B中的任意元素b，我们可以找到一个a属于A，使得f(a) = b。
第八章图论例1、下面哪些数的序列,可能是一个图的度数序列?如果可能,请试画出它的图. 哪些可能不是简单图?a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) d) (1,1,1,1,4) e) (1,2, 2,4,5)解:a)不是, 因为有三个数字是奇数. b) c) d)是.e) 不是简单图,因为它有5个结点, 有一个结点度为5, 必然有环或平行边.例2、已知无向简单图G中,有10条边,4个3度结点,其余结点的度均小于或等于2,问G中至少有多少个结点?为什么?解:已知边数|E|=10, ∑deg(v)=2|E|=20其中有4个3度结点, 余下结点度之和为: 20-3×4=8 因为G是简单图, 其余每个结点度数≤2, 所以至少还有4个结点.所以G中至少有8个结点.强连通、单侧连通和弱连通在简单有向图G中,如果任何两个结点间相互可达, 则称G是强连通. 如果任何一对结点间, 至少有一个结点到另一个结点可达, 则称G是单侧连通. 如果将G看成无向图后(即把有向边看成无向边)是连通的,则称G是弱连通.在简单有向图中,具有强连通的最大子图,称为强分图.具有单侧连通的最大子图,称为单侧分图. 具有弱连通的最大子图,称为弱分图.注：我每次都会被各种分图弄糊涂！！考试时要注意啊，千万不要错了利用可达性矩阵求强分图，注意初等矩阵变换的知识不要忘了！！令图G=<V,E,W>, 集合Si V Si’=V-Si , 令|V|=nSi={u|从u0到u的最短路已求出}Si’={u’|从u0到u’的最短路未求出}Dijkstra算法:(求从u0到各点u的最短路长)第一步. 置初值: d(u0,u0)=0 d(u0,v)=∞(其中v≠u0)i=0 S0={u0} S0’=V-S0 ,第二步.若i=n-1 则停. 否则转第三步第三步. 对每个u’∈Si’计算d(u0,u’)=min{d(u0,u’), d(u0,ui)+c(ui,u’)} ui ∈Si计算min{d(u0,u’)}u’∈S i’并用ui+1记下达到该最小值的那个结点u’置Si+1 =Si∪{ui+1} i=i+1 Si’=V-Si , 转第二步.例3、求最短路解：例.求右图中从v1到v6的最短路1.置初值: u0=v1d(u0,u0)=0d(u0,v2)=d(u0,v3)=d(u0,v4)=d(u0,v5)=d(u0,v6)=∞2.3. i=0 S0={v1} S0’={v2,v3,v4,v5,v6}d(u0,v2)=min{d(u0,v2), d(u0,u0)+c(u0,v2)}=min{∞,0+3}=3d(u0,v3)=min{d(u0,v3),d(u0,u0)+c(u0,v3)}=min{∞,0+∞}=∞d(u0,v4)=min{d(u0,v4), d(u0,u0)+c(u0,v4)}=min{∞,0+5}=5d(u0,v5)=min{d(u0,v5),d(u0,u0)+c(u0,v5)}=min{∞,0+∞}=∞d(u0,v6)=min{d(u0,v6),d(u0,u0)+c(u0,v6)}=min{∞,0+∞}=∞min{3,∞,5, ∞,∞}=3ui+1 =u1=v2 , 实际已求出d(u0,v2)=3, 路是u0v2i=1 S1={v1, v2}S1’={v3,v4,v5,v6}u1=v2d(u0,u1)=3d(u0,v3)=min{d(u0,v3),d(u0,u1)+c(u1,v3)}=min{∞,3+6}=9d(u0,v4)=min{d(u0,v4), d(u0,u1)+c(u1,v4)}=min{5,3+1}=4d(u0,v5)=min{d(u0,v5),d(u0,u1)+c(u1,v5)}=min{∞,3+∞}=∞d(u0,v6)=min{d(u0,v6),d(u0,u1)+c(u1,v6)}=min{∞,3+∞}=∞min{9,4,∞,∞}=4ui+1 =u2=v4 , 实际已求出d(u0,v4)=4, 路是u0v2v4i=2 S2={v1, v2 ,v4}S2’={v3,v5,v6}u2=v4d(u0,u2)=4d(u0,v3)=min{d(u0,v3), d(u0,u2)+c(u2,v3)}=min{9 ,4+3}=7d(u0,v5)=min{d(u0,v5), d(u0,u2)+c(u2,v5)}=min{∞,4+1}=5d(u0,v6)=min{d(u0,v6), d(u0,u2)+c(u2,v6)}=min{∞,4+∞}=∞min{7,5,∞}=5ui+1 =u3=v5 , 实际已求出d(u0,v5)=5, 路是u0v2v4 v5i=3 S3={v1, v2 ,v4 ,v5}S3’={v3,v6}u3=v5d(u0,u3)=5d(u0,v3)=min{d(u0,v3),d(u0,u3)+c(u3,v3)}=min{7 ,5+3}=7d(u0,v6)=min{d(u0,v6),d(u0,u3)+c(u3,v6)}=min{∞,5+6}=11 min{7,11}=7ui+1 =u4=v3 , 实际已求出d(u0,v3)=7, 路是u0v2v4 v3i=4 S3={v1, v2 ,v4 ,v5, v3} S3’={v6} u4=v3 d(u0,u4)=7 d(u0,v6)=min{d(u0,v6),d(u0,u4)+c(u4,v6)}=min{11,7+3}=10min{10}=10ui+1 =u5=v6 , 实际已求出d(u0,v6)=10, 路是u0v2v4 v3 v6i=5 (n-1) 时算法停止.例4、求关键路径。
离散数学复习笔记数理逻辑逻辑：以研究人的思维形式及思维规律为目的的一门学科数理逻辑：利用数学符号来协助推理的一门形式逻辑学命题：能表达判断并具有确定真值的陈述句真值：每个命题都具有的一个值，要么为真，要么为假，不能随着环境变化原子命题：不能再分解的命题复合命题：由原子命题符号及联结词组成的有意义的命题表达式否定非P 合取P而且Q 析取P可兼或Q 排斥析取P不可兼或Q 单条件若P 则Q 双条件P当且仅当Q命题公式：满足特定条件的合法的命题表达式分量：命题公式中的原子命题翻译：将自然语言转化为数理逻辑语言真值表：对一个命题公式而言，将对于其分量的各种可能的真值指派汇聚成的表两个命题等价：对两个命题公式A,B,若对于A\B中的所有命题变元P1\P2..对天安门的任一组真值指派A，B相同对应的行的真值相同，则称A与B等价等价定律：交换律，结合律，分配律，摩根律，否定律，同一律重言式：永真式，无论对命题变元作何种真值指派，它都等价于T的命题公式永假式：无论对命题变元作何种真值指派，它都等价于F的命题公式用一个命题公式代替重言式中同一个分量，依然为重言式蕴含式：若A->B永真则称A蕴含B，记做A=>B原命题等价于它的逆否命题三个性质：传递性，A=>B A=>C A=>(B^C)， A=>B C=>B AvC=>B有效结论：H1，H2、、、、Hn，C为一组命题公式，若H1^H2^...^Hn=>C,称C 是一组条件下的有效结论三种方法：真值表法，直接证法，间接证法其他连接词：条件否定，与非，或非规范命题表达式：只含非且或合取范氏：当且仅当具有A1^A2^...^An形式，A1，A2...An都是命题变元或其否定组成的析取式析取范式：当且仅当具有A1vA2v...vAn形式，A1，A2...An都是命题变元或其否定组成的合取式一个命题公式的合取范氏或析取范氏并不是唯一的n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次 P^Q P^非Q一般n个命题变元共有2^n个小项n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次 PvQ Pv非Q主析取范式：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则称该等价式为原式的主析取范式主合取范式：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则称该等价式为原式的主合取范式集合论集合：满足一定特征的对象的全体扩张原则：两个集合相等，当且仅当他们有相同的元素抽象原则：任给一个集合U和一个性质P，存在一个集合A，使得A的各个元素恰好是U的具有性质P的那些成员集合表示：列举法，特征法幂集：对给定的集合A，称以A的全体子集为元素的集合为A的幂集集合的基数：|A|元素的个数无限集合：元素个数能与某个真子集一一对应的集合序偶：有序的二元数组<x,y>笛卡尔积：称A*B={<x,y>|x属于A且y属于B}二元关系：以序偶作为元素的集合即关系xRy，关系前域指x，关系值域指y，关系域是前域和值域的并集。
总 结第八章 图论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 )。
