《离散数学》期末考试复习指导

第一篇：《离散数学》期末考试复习指导

《离散数学》期末考试复习指导

期末考试仅限于期中考试以后的内容：Chapter 7 Trees;Chapter 8 Topics in

graph theory.考试题型：计算题；简答题；证明题；构造图形（构造满足一定条件的图，如：

6个顶点，11条边且无Hamiltonian circuit）。题目共计6题，无选择题和填空题。

考试难度：基本与期中考试相同，有一定数量的题直接来自于习题，最后一题较

难（构造图形）。

复习要点：基本概念及定义：

rooted tree;binary tree;labeled tree;positional tree;tree

searching;undirected tree;weighted graph;minimal spanning tree;(undirected)graph;degree;Euler path and Euler circuit;Hamiltonian path and Hamiltonian circuit;matching function;coloring graph;chromatic number;chromatic polynomial;planar graph;

基本内容：

tree searching;the prefix(Polish form)and infix form of the

algebraic expression;minimal spanning tree;the sufficient-necessary condition for a graph G to have Euler circuit(or path);coloring graph;chromatic number;chromatic polynomial;construct a graph(directed or undirected)subject to some given conditions.不要求的内容：

Computer representation of binary positional tree;searching general tree;algorithms.复习中如遇困难请联系：钱建国***，jgqian@jingxian.xmu.edu.cn徐伟***

陈美润***

祝大家取得好成绩！

第二篇：离散数学期末考试

一、单项选择题（本大题共10小题，每小题2分，共20分）

1、设集合M={a，}，N ={{a}，}则MN=（）。A、 B、{} C、{a} D、{{a}，，a}

2、设关系F={<1，a >，<2，2>，}，G={，，<1，2>}则 FG=（）。

A、{<1，b>，<1，c>，}

B、{，，<1，b>} C、{，<1，2>}

D、{，<2，2>，<1，b>}

3、设集合H={1，2，3，4}，则H上的关系R={

。x +y是偶数}具有（）A、自反性、反对称性和传递性

B、反自反性、反对称性和传递性

C、反自反性、对称性和传递性

D、自反性、对称性和传递性

4、设T是一棵完全二叉树，则T的每个结点都（）。

A、至少有两个子结点

B、至多有两个子结点

C、恰有两个子结点

D、可以有任意多个子结点

5、设R是实数集，“+，—，A、

>是群

B、是群

 >是半群

D、是独异点

6、下面关系中，函数关系是（）。

A、{，，}

B、{，，<1，x>} C、{<1，y>，<1，x>，}

D、{，，}

7、设是一个代数系统，若多任意的x，yS，都有xy=yx，则称运算在S上满足（）。

A、结合律

B、交换律

C、分配律

D、幂等律

8、设Z是整数集，“—”是整数减法，则下列说法正确的是（）。A、不是代数系统

B、的单位元是0

C、是代数系统

D、的单位元是1

9、设L是无向图G中的一条通路，L中的顶点各不相同，则L是一条（）。A、简单通路

B、初级通路

C、简单回路

D、初级回路

10、设G有6个3度点，2个4度点，其余顶点的度数均为0，则G的边数是（）。A、10

B、13

C、11

D、6

二、填空题(本大题共8题，共10个空，每空2分，共20分)

1、设关系R={，<2，1>，<2，b>}，则R逆关系R1=_______________________________。

2、在代数系统（Q是有理数集，“+”是有理数加法）中，单位元是______，2的逆元是___________。

3、设集合M={1，2，3，5}，则M的幂集P（M）包含___________个元素。

4、设T是一棵有n(n2)个顶点的树，则T有_____________条边。

5、设是一个代数系统，是S上的二元运算，若存在S，对任意xS，有x=x=，则称是的_______________。

6、设是一个代数系统，若满足结合律且中有单位元，则称为一个___________________。

7、设D是有向图，若D的基图是连通图，则称D是_________________图

8、既不含________________也不含____________________的无向图称为简单图。

三、计算题(本大题共3小题，每小题10分，共30分)

1、用等值演算法求公式A=(pq)(pr)的主析取范式。

2、求公式x(Q(x)G(x，s))(yP(y)zH(y，z))的前束范式。

3、设集合A={1，2，3，4，5}，关系R={（1）列出R的所有元素；（2）写出R的关系矩阵Mx，y A且x整除y}，要求：

R；

（3）求偏序集的极大元、极小元和最小元。

四、应用题(本大题共2小题，每小题5分，共10分)

1、用命题公式将下列命题符号化： 2和5是偶数，当且仅当5>2。

2、用谓词公式将下列命题符号化：

每个计算机专业的学生都要学《编译原理》，但有些计算机专业的学生不学《经济学》。

五、证明题（本大题共2小题，每小题10分，共20分）

1、在命题逻辑系统中用归结法证明下列推理是有效的： 前提：sq，pq，s 结论：p

2、在谓词逻辑系统中写出下列推理的（形式）证明：

前提：x(M(x)P(x))，x(M(x)G(x))，x(G(x))结论：xP(x)

计算题

6.设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。

7.(9分)设一阶逻辑公式：G =(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.9.设R是集合A = {a, b, c, d}.R是A上的二元关系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；(2)画出r(R), s(R), t(R)的关系图.11.通过求主析取范式判断下列命题公式是否等价：

(1)G =(P∧Q)∨(P∧Q∧R)

(2)H =(P∨(Q∧R))∧(Q∨(P∧R))13.设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝

{(a, b),(b, c),(b, d),(d, d)}.(1)试写出R和S的关系矩阵；(2)计算R•S, R∪S, R1, S1•R1.－

－

－证明题

1.利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。2.设A,B为任意集合，证明：(A-B)-C = A-(B∪C).3.(本题10分)利用形式演绎法证明：{A∨B, C→B, C→D}蕴涵A→D。4.(本题10分)A, B为两个任意集合，求证：

A－(A∩B)=(A∪B)－B.答案：

1-5

BADBB 6-10 BBABB

1.{<1，a>，<1，2>，} 2.0，-2 3.16 4.n-1 5.零元 6.半群 7.弱连通 8.平行边

环 三．

(pq)(pr)(pq)(pr)1.(pqr)(pqr)(pqr)(pqr)m011m010m111m1012.x(Q(x)G(x,s))yz(P(y)H(y,z))

yzx((Q(x)G(x,s))(P(y)H(y,z))3.(1)R{1,1,2,2,3,3,4,4,5,5,1,2,1,3,1,4,1,5,2,4}

12(2)MR345123451111101010

（3）最小元=1 极小元=1 极大元=5 001000001000001四

1.令p表示2是偶数；令q表示5是偶数；r表示5>2；

(pq)r

2.S（x）：x是计算机专业的学生；G（x）：x要学《编译原理》； F（x）：x学经济学；

x(S(x)G(x))x(S(x)F(x))

五 1，（1）

s

前提引入（2）

sq

前提引入（3）

qs

置换规则

（4）

q

1,3析取三段论（5）

pq

前提引入（6）

p

4,5拒取

（1）

x(M(x)G(x))

前提引入（2）

M（x）v G（x）

EI规则（3）

x(G(x))

前提引入（4）

G(x)（5）

M(x)

AI规则

2,4析取三段论

（6）

x(M(x)P(x))

前提引入（7）

M(x)→P（x）

AI规则（8）

P（x）

5,7假言推理（9）

xP(x)

EG规则

6.G = (P→Q)∨(Q∧(P→R))

= (P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧P)∨(Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = (3, 4, 5, 6, 7).7.G =(xP(x)∨yQ(y))→xR(x)

= (xP(x)∨yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨zR(z)= xyz((P(x)∧Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}, －t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2)

关系图: abr(R)dcabs(R)dabt(R)dc c

11.G＝(P∧Q)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3 ＝(3, 6, 7)H =(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝(3, 6, 7)G,H的主析取范式相同，所以G = H.1013.(1)MR00000011000000

MS10001000010001 01(2)R•S＝{(a, b),(c, d)}, R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R1＝{(a, a),(c, a),(c, b),(d, c)}, －S1•R1＝{(b, a),(d, c)}.－－四 证明题

1.证明：{P→Q, R→S, P∨R}蕴涵Q∨S

(1)P∨R

(2)R→P(3)P→Q(4)R→Q(5)Q→R(6)R→S

P Q(1)P Q(2)(3)Q(4)P

(7)Q→S(8)Q∨S Q(5)(6)Q(7)2.证明：(A-B)-C =(A∩~B)∩~C

3.= A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)证明：{A∨B, C→B, C→D}蕴涵A→D(1)A D(附加)P(2)A∨B(3)B Q(1)(2)P Q(4)(4)C→B(5)B→C(6)C

Q(3)(5)P(7)C→D(8)D Q(6)(7)D(1)(8)(9)A→D

所以 {A∨B, C→B, C→D}蕴涵A→D.1.证明：A－(A∩B)

= A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝∪(A∩~B)＝(A∩~B)＝A－B 而(A∪B)－B =(A∪B)∩~B =(A∩~B)∪(B∩~B)=(A∩~B)∪ = A－B 所以：A－(A∩B)=(A∪B)－B.

第三篇：《李刚版离散数学》大一期末考试复习方向

《离散数学大一期末考试复习方向》

一、命题逻辑

证明等值式

①等值演算

判断公式的类型

合取（析取）范式

②范式

主合取（主析取）范式

重点复习题目：课本P55的2.5.3和2.5.2

③推理证明

P63 的2.6.2

二、谓词逻辑

①前述范式。P88的3.35

②推理论证P91的苏格拉底、P93的3.4.1（4）

三、关系 P152的5.4.3。

四、等价转换。P157的.5.5.4

第四篇：离散数学复习重点

离散数学复习重点：

1、集合的运算以及运算律；

2、关系的三种表示方法，以及他们之间的转化；

3、常见关系的定义；

4、哈斯图的画法，以及最大最小元、极大极小元、上下界，上下确界的求法；

5、单射、满射以及双射的证明（尤其是在代数系统中）；

6、代数系统的概念以及代数系统的常用性质，能够证明具体的代数系统的运算律，找出单

位元，零元、以及逆元等；

7、环和格只要记住不同的环和格满足的运算律就好；

8、各种图和树的概念及相关的结论，比如：欧拉图的充要条件，哈密顿图的充分条件、必

要条件、充要条件等；

9、图的矩阵计算；

10、会画一些简单的树；

11、五种联结词的真值表；

12、一些要求记住的命题公式；

13、命题公式的证明；

14、命题公式的析取范式，合取范式，主析取范式和主合取范式的求法。

题型：填空题、证明题和解答题。

友情提醒：

1、周三下午一点半到三点半在逸夫楼519答疑。

2、概念、定理和公式请务必记住，可能会出填空题；

3、考试内容不会超出我们的重点；

请大家好好复习，争取一次性通过。

第五篇：《离散数学》期末复习

《离散数学》期末复习

内容：第一章~第七章 题型：

一、选择题（20%，每题2分）二．填空题（20%，每题2分）

三、计算题（20%，每题5分）

四、证明题（20%，每题5分）

五、判断题（20%，每题2分）

第1章 数学语言与证明方法

1.1 常用的数学符号

1.计算常用的数学符号式子 1.2 集合及其表示法

1.用列举法和描述法表示集合

2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集()4.计算集合的幂集

5.求集合的运算：并、交、相对补、对称差、绝对补

6.用文氏图表示集合的运算 7.证明集合包含或相等

方法一： 根据定义, 通过逻辑等值演算证明

方法二： 利用已知集合等式或包含式, 通过集合演算证明

1.3 证明方法概述

1、用如下各式方法对命题进行证明。 直接证明法：AB为真

 间接证明法：“AB为真”  “ ¬B ¬A为真”  归谬法(反证法)： A¬B0为真

 穷举法： A1B, A2B,…, AkB 均为真

 构造证明法：在A为真的条件下, 构造出具有这种性质的客体B  空证明法：“A恒为假”  “AB为真” 平凡证明法：“B恒为真”  “AB为真”  数学归纳法： 第2章 命题逻辑

2.1 命题逻辑基本概念

1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。

命题的定义和联结词(¬, , , , )

2、判断命题公式的类型

赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。2.2 命题逻辑等值演算

1、用真值表判断两个命题公式是否等值

2、用等值演算证明两个命题公式是否等值

3、证明联结词集合是否为联结词完备集 2.3 范式

1、求命题公式的析取范式与合取范式

2、求命题公式的主析取范式与主合取范式（两种主范式的转换）

3、应用主析取范式分析和解决实际问题 2.4 命题逻辑推理理论

1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效 第3章 一阶逻辑

3.1 一阶逻辑基本概念

1、用谓词公式符号命题（正确使用量词）

2、求谓词公式的真值、判断谓词公式的类型 3.2 一阶逻辑等值演算

1、证明谓词公式的等值式

2、求谓词公式的前束范式 第4章 关系

4.1 关系的定义及其表示

1、计算有序对、笛卡儿积

2、计算给定关系的集合

3、用关系图和关系矩阵表示关系 4.2 关系的运算

1、计算关系的定义域、关系的值域

2、计算关系的逆关系、复合关系和幂关系

3、证明关系运算满足的式子 4.3 关系的性质

1、判断关系是否为自反、反自反、对称、反对称、传递的2、判断关系运算与性质的关系

3、计算关系自反闭包、对称闭包和传递闭包 4.4 等价关系与偏序关系

1、判断关系是否为等价关系

2、计算等价关系的等价类和商集

3、计算集合的划分

4、判断关系是否为偏序关系

5、画出偏序集的哈期图

6、求偏序集的最大元、最小元、极小元、极大元、上界、下界、上确界、下确界

7、求偏序集的拓扑排序 第5章 函数

1.判断关系是否为函数 2.求函数的像和完全原像

3.判断函数是否为满射、单射、双射 4.构建集合之间的双射函数 5.求复合函数

6.判断函数的满射、单射、双射的性质与函数复合运算之间的关系 7.判断函数的反函数是否存在，若存在求反函数 第6章 图

1.指出无向图的阶数、边数、各顶点的度数、最大度、最小度

2.指出有向图的阶数、边数、各顶点的出度和入度、最大出度、最大入度、最小出度最小入出度

3.根据握手定理顶点数、边数等

4.指出图的平行边、环、弧立点、悬挂顶点和悬挂边 5.判断给定的度数列能否构成无向图

6.判断图是否为简单图、完全图、正则图、圈图、轮图、方体图 7.求给定图的补图、生成子图、导出子图 8.判断两个图是否同构 6.2 图的连通性

1.求图中给定顶点通路、回路的距离

2.计算无向图的连通度、点割集、割点、边割集、割边 3.判断有向图的类型：强连通图、单向连通图、弱连通图 6.3 图的矩阵表示

1.计算无向图的关联矩阵 2.计算有向无环图的关联矩阵 3.计算有向图的邻接矩阵 4.计算有向图的可达矩阵

5.计算图的给定长度的通路数、回路数 6.4 几种特殊的图

1、判断无向图是否为二部图、欧拉图、哈密顿图 第7章 树及其应用 7.1 无向树

1.判断一个无向图是否为树

2.计算无向树的树叶、树枝、顶点数、顶点度数之间的关系 3.给定无向树的度数列，画出非同构的无向树 4.求生成树对应的基本回路系统和基本割集系统 5.求最小生成树 7.2 根树及其应用

1.判断一个有向图是否为根树

2.求根树的树根、树叶、内点、树高 3.求最优树

4.判断一个符号串集合是否为前缀码 5.求最佳前缀码

6.用三种方法遍历根树