离散数学总结ppt课件市公开课获奖课件省名师优质课赛课一等奖课件

离散数学总结1/33离散数学离散数学(DiscreteMathematics)离散数学是以研究离散量结构和相互间关系为主要目标，其研究对象普通地是有限个或可数个元素，所以它充分描述了计算机科学离散性特点。集合论数理逻辑图论代数结构2/33离散数学应用举例关系型数据库设计(关系代数)表示式解析(树)优化编译器结构(闭包)编译技术、程序设计语言(代数结构)Lisp和Prolog、人工智能、自动推理、机器证实(数理逻辑)网络路由算法(图论)游戏中人工智能算法(图论、树、博弈论)教授系统(集合论、数理逻辑—知识和推理规则计算机表示)软件工程—团体开发—时间和分工优化(图论—网络、划分)(各种)算法结构、正确性证实和效率评定(离散数学各分支)3/33离散数学学习要领概念（正确）

必须掌握好离散数学中大量概念判断（准确）

依据概念对事物属性进行判断推理（可靠）

依据多个判断推出一个新判断4/33数理逻辑－命题逻辑命题、真值、简单命题与复合命题、命题符号化。联结词：┐，∧，∨，→，

。命题公式、求公式赋值。真值表、公式成真赋值和成假赋值。

公式类型：重言式、矛盾式、可满足式。等值式与等值演算。基本等值式，其中含：双重否定律、幂等律、交换律、结合律、分配律、德·摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。与范式相关概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。5/33求给定公式范式步骤(1)消去联结词→、(若存在)。

A→B┐A∨B

AB(┐A∨B)∧(A∨┐B)(2)否定号消去(利用双重否定律)或内移(利用德摩根律)。

┐┐AA

┐(A∧B)┐A∨┐B

┐(A∨B)┐A∧┐B(3)利用分配律：利用∧对∨分配律求析取范式，

∨对∧分配律求合取范式。

A∧(B∨C)(A∧B)∨(A∧C)

A∨(B∧C)(A∨B)∧(A∨C)6/33求公式A主析取范式方法与步骤方法一、等值演算法(1)化归为析取范式。(2)除去析取范式中全部永假析取项。(3)将析取式中重复出现合取项和相同变元合并。(4)对合取项补入没有出现命题变元，即添加如(p∨┐p)式，然后应用分配律展开公式。方法二、真值表法(1)写出A真值表。(2)找出A成真赋值。(3)求出每个成真赋值对应极小项（用名称表示），按角标从小到大次序析取。7/33求公式A主合取范式方法与步骤方法一、等值演算法(1)化归为合取范式。(2)除去合取范式中全部永真合取项。(3)将合取式中重复出现析取项和相同变元合并。(4)对析取项补入没有出现命题变元，即添加如(p∧┐p)式，然后应用分配律展开公式。方法二、真值表法(1)写出A真值表。(2)找出A成假赋值。(3)求出每个成假赋值对应极大项（用名称表示），按角标从小到大次序析取。8/33数理逻辑－命题逻辑推理形式结构

推理前提

推理结论

推理正确判断推理是否正确方法

真值表法

等值演算法

主析取范式法

对于正确推理，在自然推理系统P中结构证实

自然推理系统P定义

自然推理系统P推理规则

附加前提证实法

归谬法9/33数理逻辑－一阶逻辑个体词（个体域、全总个体域），谓词(特征谓词)，量词（全称量词、存在量词）命题符号化：当给定个体域时，在给定个体域内将命题符号化。当没给定个体域时，应在全总个体域内符号化。在符号化时，当引入特征谓词时，注意全称量词与蕴含联结词搭配，存在量词与合取联结词搭配。

逻辑有效式、矛盾式、可满足式

闭式性质：在任何解释下均为命题。

对给定解释，会判别公式真值或不能确定真值。10/33数理逻辑－一阶逻辑深刻了解主要等值式，并能熟练地使用它们。熟练地使用置换规则、换名规则和代替规则。准确地求出给定公式前束范式（形式能够不唯一）。正确地使用UI、UG、EI、EG规则，尤其地要注意它们之间关系。一定对前束范式才能使用UI、UG、EI、EG规则，对不是前束范式公式要使用它们，一定先求出公式前束范式。记住UI、UG、EI、EG规则各自使用条件。在同一推理证实中，假如既要使用UI规则，又要使用EI规则，一定要先使用EI规则，后使用UI规则，而且UI规则使用个体常项一定是EI规则中使用过。对于给定推理，正确地结构出它证实。11/33集合论－集合代数掌握集合子集、相等、空集、全集、幂集等概念及其符号化表示。B

A

x(x∈B→x∈A)

B

A

x(xBxA)……掌握集合交、并、（相对和绝对）补、对称差、广义交、广义并定义及其性质。

A∪B＝{x|x∈A∨x∈B}A－B＝{x|x∈A∧x

B}……掌握基本集合恒等式（等幂律、交换律、结合律、分配律、德·摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）。利用逻辑演算或利用已知集合恒等式或包含式证实新等式或包含式

。12/33集合恒等式证实方法逻辑演算法 利用逻辑等值式和推理规则集合演算法 利用集合恒等式和已知结论13/33逻辑演算法格式题目：A＝B证实：

x，

x∈A ……

x∈B 所以A＝B或证A

B∧A

B题目：A

B证实：

x，

x∈A ……

x∈B 所以AB14/33集合演算法格式题目：A＝B证实：A ＝…… ＝B 所以A＝B题目：A

B证实：A …… B 所以A

B15/33集合论－二元关系有序对、笛卡尔积、笛卡尔积性质

二元关系，A到B二元关系，A上二元关系，关系定义域和值域，关系逆，关系合成，关系定义域、值域、逆等主要性质

集合A上二元关系主要性质（自反性，反自反性，对称性，反对称性，传递性）定义及判别法，对一些关系证实它们有或没有中性质。A上二元关系n次幂定义及主要性质等价关系、等价类、商集、划分等概念，以及等价关系与划分之间对应偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念16/33关系性质特点自反性反自反性对称性反对称性传递性定义x∈A→<x,x>∈Rx∈A→<x,x>

R<x,y>∈R→<y,x>∈R<x,y>∈R∧<y,x>∈R→x=y<x,y>∈R∧<y,z>∈R→<x,z>集合表示式IA

RR∩IA＝

R＝R-1R∩R-1

IAR

R

R关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1，且i≠j，则rji＝0对M2中1所在位置，M中对应位置都是1关系图每个顶点都有环每个顶点都没有环假如两个顶点之间有边，一定是一对方向相反边(无单边)假如两点之间有边，一定是一条有向边(无双向边)假如顶点xi到xj有边，xj到xk有边，则从xi到xk也有边17/33关系性质证实通常证实方法是利用定义证实。R在A上自反 任取x，有 x∈A…………………<x,x>∈RR在A上对称 任取<x,y>，有 <x,y>∈R……………<y,x>∈R R在A上反对称 任取<x,y>，有 <x,y>∈R∧<y,x>∈R……………x＝yR在A上传递 任取<x,y>,<y,z>，有 <x,y>∈R∧<y,z>∈R……………<x,z>∈R18/33集合论－函数掌握函数、A到B函数、集合在函数下像、集合在函数下完全原像概念及表示法；当A与B都是有穷集时，会求A到B函数个数。

掌握A到B函数是单射、满射、和双射定义及证实方法。

掌握常函数、恒等函数、单调函数、特征函数、自然映射等概念。

掌握复合函数主要性质和求复合函数方法。

掌握反函数概念及主要性质。19/33单射和满射证实方法证实函数f:A→B是满射，基本方法是：

任取y∈B，找到x∈A(x与y相关，可能是一个关于y表示式)或者证实存在x∈A，使得f(x)＝y。证实函数f:A→B是单射，基本方法是： 假设A中存在x1和x2，使得f(x1)＝f(x2)，利用已知条件或者相关定理最终证实x1＝x2。20/33集合论－基数掌握基数基本概念掌握可数集合和不可数集合概念，以及相关结论21/33代数结构-代数系统组成代数系统基本成份 非空集合 集合上若干个封闭二元和一元运算 代数常数二元运算性质和特异元素同类型与同种代数系统子代数定义与实例22/33代数结构知识体系半群与群环与域格与布尔代数分类∑代数推广成份：载体及运算公理：运算性质代数系统组成代数系统同态与同构代数系统间关系映射子代数积代数商代数等价关系笛卡儿积子集新代数系统同种同类型产生23/33群与半群广群二元运算封闭性结合律半群单位元独异点每个元素可逆群交换律交换半群交换律交换独异点交换律Abel群有限个元素有限群生成元循环群实例n元置换群实例Klein群24/33代数结构-环代数系统<R,+,·>组成环条件：<R,+>组成Abel群；<R,·>组成半群；·对于+满足分配律。

环中运算性质：a0=0a=0；a(-b)=(-a)b=-(ab)；乘法对加法广义分配律。

环R非空子集S组成R子环条件：任取a,b属于S,有a-b属于S；ab属于S。

环同态映射定义、判别法及其实例。25/33代数结构-格与布尔代数偏序集组成格条件：任意二元子集都有最大下界和最小上界。

格实例：正整数因子格，幂集格，子群格。格性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。

格作为代数系统定义。格L非空子集S组成L子格条件： S对L两个运算封闭。

函数

组成格同态条件：

(a∧b)＝

(a)∧

(b)

(a∨b)＝

(a)∨

(b)格同态保序性。26/33代数结构-格与布尔代数假如格中一个运算对另一个运算是可分配，称这个格是分配格。

分配格两种判别法： 不存在与钻石格或五角格同构子格； 对于任意元素a,b,c,有

a∧b＝a∧c且a∨b＝a∨c

b＝c。

有界格定义及其实例。

格中元素补元及其性质（分配格中补元唯一性）。

有补格定义。27/33代数结构-格与布尔代数布尔代数两个等价定义：有补分配格；有两个二元运算并满足交换律、分配律、同一律和补元律代数系统。

布尔代数特殊性质：双重否定律和德摩根律。子布尔代数定义及其判别。

布尔代数同态判定：f(a∧b)＝f(a)∩f(b)(或f(a∨b)＝f(a)∪f(b)),f(a

)＝-f(a)

对于任意自然数n，只有一个2n元有限布尔代数，就是幂集代数。28/33图论－处理实际问题(1)很多离散问题能够用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间关系。29/33图论－基本概念了解与图定义相关很多概念，以及它们之间相互关系。深刻了解握手定理及其推论内容，并能熟练地应用它们。深刻了解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们性质和相互关系，并能熟练地应用这些性质和关系。深刻了解通路与回路定义、相互关系及其分类，掌握通路与回路各种不一样表示方法。了解无向图点连通度、边连通度等概念及其之间关系