离散数学期末复习要点与重点Word文档格式.doc

离散数学期末复习要点与重点Word文档格式.doc

《离散数学期末复习要点与重点Word文档格式.doc》由会员分享，可在线阅读，更多相关《离散数学期末复习要点与重点Word文档格式.doc（5页珍藏版）》请在冰点文库上搜索。

m＝2n（k=0）；

5．了解C是前提集合{A1,A2,…,Am}的有效结论或由A1,A2,…,Am逻辑地推出C的概念．要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：

真值表法、直接证法、间接证法．

重点：

命题与联结词，真值表，主析取（合取）范式，命题演算的推理理论.

第2章谓词逻辑

复习要点

1．理解谓词、量词、个体词、个体域，会将简单命题符号化．

原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项．谓词用来刻划个体词的性质或之间的关系．

量词分全称量词"

，存在量词$.

命题符号化注意：

使用全称量词"

，特性谓词后用®

；

使用存在量词$，特性谓词后用Ù

．

2．了解原子公式、谓词公式、变元（约束变元和自由变元）与辖域等概念．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．

由原子公式、联结词和量词构成谓词公式．谓词公式具有真值时，才是命题．

在谓词公式"

xA或$xA中，x是指导变元，A是量词的辖域．会区分约束变元和自由变元．

在非空集合D（个体域）上谓词公式A的一个解释或赋值有3个条件．

在任何解释下，谓词公式A取真值1，A为逻辑有效式（永真式）；

公式A取真值0，A为永假式；

至少有一个解释使公式A取真值1，A称为可满足式．

在有限个体域下，消除量词的规则为：

设D＝{a1,a2,…,an}，则

会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等．

掌握谓词演算的等价式和重言蕴含式．并进行谓词公式的等价演算．

3．理解前束范式的概念，掌握求公式的前束范式的方法.

若一个谓词公式F等价地转化成 ，那么就是F的前束范式，其中Q1，Q2，…，Qk只能是"

或$，而x1,x2,…,xk是个体变元，B是不含量词的谓词公式．前束范式仍然是谓词公式．

翻译；

前束范式．

第3章集合与关系

1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法．

集合的表示方法：

列举法和描述法.

注意：

集合的表示中元素不能重复出现，集合中的元素无顺序之分．

掌握集合包含（子集）、真子集、集合相等等概念．

注意：

元素与集合，集合与子集，子集与幂集，Î

与Ì

（Í

）,空集Æ

与所有集合等的关系.

空集Æ

，是惟一的，它是任何集合的子集．

集合A的幂集P（A）＝，A的所有子集构成的集合．若½

A½

＝n，则½

P（A）½

=2n．

2．熟练掌握集合A和B的并AÈ

B，交AÇ

B，补集~A（~A补集总相对于一个全集）.差集A－B，对称差Å

，AÅ

B＝（A－B）È

（B－A），或AÅ

B＝（AÈ

B）－（AÇ

B）等运算．

掌握集合运算律（运算的性质）.

3．掌握用集合运算基本规律证明集合恒等式的方法．

集合的运算问题：

其一是进行集合运算；

其二是运算式的化简；

其三是恒等式证明．

证明方法有二：

（1）要证明A＝B，只需证明AÍ

B，又AÊ

B；

（2）通过运算律进行等式推导．

4．了解有序对和笛卡尔积的概念，掌握笛卡尔积的运算．

有序对就是有顺序二元组，如<

x,y>

，x,y的位置是确定的，不能随意放置．

有序对<

a，b>

¹

<

b,a>

，以a,b为元素的集合{a,b}={b,a}；

有序对（a,a）有意义，而集合{a,a}是单元素集合，应记作{a}．

集合A，B的笛卡尔积A×

B是一个集合，规定A×

B＝{<

x,y>

½

xÎ

A,yÎ

B}，是有序对的集合.笛卡尔积也可以多个集合合成，A1×

A2×

…×

An．

5．理解关系的概念：

二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图，掌握关系的集合运算及复合关系、逆关系的性质与求法．

二元关系是一个有序对集合，，记作xRy．

设A、B是两个集合，且|A|＝m，|B|＝n，则从A到B可产生的不同的二元关系个

数为。

关系的表示方法有三种：

集合表示法，

关系矩阵：

RÍ

A×

B，R的矩阵.

关系图：

R是集合上的二元关系，若<

ai,bj>

Î

R，由结点ai画有向弧到bj构成的图形．

空关系Æ

是唯一、是任何关系的子集的关系；

全关系；

恒等关系，恒等关系的矩阵MI是单位矩阵．

关系的集合运算有并、交、补、差和对称差．

复合关系；

复合关系矩阵：

（按逻辑运算）；

有结合律：

（RS）T＝R（ST），一般不可交换．

逆关系；

逆关系矩阵满足：

复合关系与逆关系存在：

（RS）－1=S－1R－1．

6．理解关系的性质（自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示），掌握其判别方法（利用定义、矩阵或图，充分条件），知道关系闭包（自反，对称，传递）的定义和求法．

注：

（1）关系性质的充分必要条件：

①R是自反的Û

IAÍ

R；

②R是反自反的Û

IAÇ

R＝Æ

③R是对称的Û

R＝R－1；

④R是反对称的Û

RÇ

R－1Í

IA；

⑤R是传递的Û

RRÍ

R.

（2）IA具有自反性，对称性、反对称性和传递性．EA具有自反性，对称性和传递性．Æ

具有反自反性、对称性、反对称性和传递性．

重点：

集合的运算，笛卡尔积，关系的性质，复合关系和逆关系，关系的闭包.

第4章函数

1．理解函数概念：

函数（映射），函数相等，复合函数和反函数．理解单射、满射和双射等概念，掌握其判别方法．

设f是集合A到B的二元关系，"

aÎ

A，存在惟一bÎ

B，使得<

a,b>

f，且Dom（f）=A，f是一个函数（映射）．函数是一种特殊的关系（设A、B是两个集合，且|A|＝m，|B|＝n，则从A到B可产生的不同的函数关系个数为）．

集合A×

B的任何子集都是关系，但不一定是函数．函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制．

二函数相等是指：

定义域相同，对应关系相同，且定义域内的每个元素的对应值都相同．

函数有：

单射——若；

满射——f（A）=B或使得y=f（x）；

双射——单射且满射．

复合函数即．

复合成立的条件：

．一般，但.

反函数——若f：

A®

B是双射，则有反函数f－1：

B®

A，

，

函数.

第5章代数结构

1．掌握代数系统中运算及其性质（自反，对称，传递，等幂），会判断某代数系统具有哪种性质。

2.掌握半群，独异点，群，阿贝尔群，循环群的概念及判定方法。

半群：

封闭+可结合。

独异点：

封闭+可结合+有幺元。

群：

封闭+可结合+有幺元+每个元素有逆元。

阿贝尔群：

群+可交换。

循环群：

群+有生成元。

3.掌握同态与同构的概念，理解同态的相关性质，并熟练掌握同态与同构的证明方法。

代数系统的运算性质，群与循环群的证明方法，同构与同态的证明方法。

第7章图的基本概念

1．理解图的概念：

结点、边、有向图，无向图、简单图、完全图、结点的度数、边的重数和平行边等.理解握手定理．

图是一个有序对<

V，E>

，V是结点集，E是联结结点的边的集合．

掌握无向边与无向图，有向边与有向图，混合图，零图，平凡图、自回路（环），无向平行边，有向平行边等概念．

简单图，不含平行边和环（自回路）的图、

在无向图中，与结点v（Î

V）关联的边数为结点度数（v）；

在有向图中，以v（Î

V）为终点的边的条数为入度－（v），以v（Î

V）为起点的边的条数为出度＋（v），deg（v）=deg+（v）+deg－（v）．

无向完全图Kn及其边数；

有向完全图及其边数．

了解子图、真子图、补图的概念．

知道图的同构概念，更应知道图同构的必要条件，用其判断图不同构.

重要定理：

（1）握手定理设G=<

，有；

（2）在有向图D＝<

V,E>

中，；

（3）奇数度结点的个数为偶数个．

2．了解路与回路概念．会求路和回路的长度．

了解无向图的连通性，会求无向图的连通分支．了解点割集、边割集、割点、割边等概念．了解有向图的强连通强性；

会判别其类型．

设图G＝<

，结点与边的交替序列为路．路中边的数目就是路的长度．起点和终点重合的路为回路．边不重复的路是迹；

结点不重复的路是通路.

无向图G中，结点u,v存在通路，u,v是连通的，G中任意结点u,v连通，G是连通图．P（G）表示图G连通分支的个数．

要知道：

强连通单侧连通弱连通，反之不成立．

3．掌握邻接矩阵，可达矩阵和距离矩阵的概念，掌握其构造方法及其应用．

4．理解欧拉通路（回路）、欧拉图的概念，掌握欧拉图的判别方法．

通过连通图G的每条边一次且仅一次的路（回路）是欧拉路（回路）．存在欧拉回路的图是欧拉图.

欧拉回路要求边不能重复，结点可以重复．笔不离开纸，不重复地走完所有的边，走过所有结点，就是所谓的一笔画．

欧拉图或通路的判定定理

（1）无向连通图G是欧拉图Û

G为连通图且G不含奇数度结点（即G的所有结点为偶数度）；

（2）非平凡图G含有欧拉路Û

G为连通图且G最多有两个奇数度的结点；

（3）连通有向图D含有有向欧拉回路Û

D中每个结点的入度＝出度．

（4）连通有向图D含有有向欧拉路Û

D中除两个结点外，其余每个结点的入度＝出度，且此两点满足一个结点的入度比出度大1，另一个结点的出度比入度大1．

5．了解汉密尔顿路（回路）、汉密尔顿图的概念，会做简单判断．

通过连通图G的每个结点一次，且仅一次的路（回路），是汉密尔顿路（回路）．存在汉密尔顿回路的图是汉密尔顿图.

汉密尔顿图的充分条件和必要条件

（1）在无向简单图G=<

中，½

V½

³

3，任意不同结点，则G是汉密尔顿图．（充分条件）

（2）有向完全图D＝<

若，则图D是汉密尔顿图.（充分条件）

（3）设无向图G=<

，任意V1Ì

V，则W（G－V1）£

V1½

（必要条件）

若此条件不满足，即存在V1Ì

V，使得P（G－V!

）>

则G一定不是汉密尔顿图（非汉密尔顿图的充分条件）．

6．了解树、树叶、生成树和最小生成树等概念，掌握求最小生成树的方法．

连通无回路的无向图是树．树的判别可以用图T是树的充要条件（等价定义）．

（1）树T是连通图；

（2）树T满足m＝n－1（即边数=顶点数-1）．

图G的生成子图是树，该树就是生成树．

每边指定一正数，称为权，每边带权的图称为带权图．G的生成树T的所有边的权之和是生成树T的权，记作W（T）．最小生成树是带权最小的生成树．

7．了解有向树、根树等概念．

有向图删去边的方向为树，该图为有向树．

对非平凡有向树，恰有一个结点的入度为0（该结点为树根），其余结点的入度为1，该树为根树．

有关树的求法：

（1）生成树的破圈法和避圈法求法；

（2）最小生成树的克鲁斯克尔求法；

图的概念，握手定理，路、回路以及图的矩阵表示，欧拉图和哈密顿图的基本概念及判别，树与根树的基本概念，最小生成树的求法．

5