《离散数学》复习提纲.docx
《《离散数学》复习提纲.docx》由会员分享，可在线阅读，更多相关《《离散数学》复习提纲.docx（18页珍藏版）》请在冰点文库上搜索。
《离散数学》复习提纲
《离散数学》期末复习大纲
一、 数理逻辑
[复习知识点]
1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价↔），复合命题
2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式
3、范式：
析取范式、合取范式，极大（小）项，主析取范式、主合取范式
4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）
5、命题逻辑的推理理论
6、谓词、量词、个体词（一阶逻辑3要素）、个体域、变元（约束出现与自由出现）
7、命题符号化、谓词公式赋值与解释，谓词公式的类型（永真、永假、可满足）
8、谓词公式的等值式（代换实例、消去量词、量词否定和量词辖域收与扩、量词分配）和置换规则（置换规则、换名规则）
9、一阶逻辑前束范式（定义、求法）
本章重点内容：
命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理、谓词与量词、命题符号化、谓词公式赋值与解释、求前束范式。
[复习要求]
1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。
2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。
3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。
4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。
5、掌握命题逻辑的推理理论。
6、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；掌握命题的符号化。
7、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。
8、掌握求一阶逻辑前束范式的方法。
二、集合
[复习知识点]
1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集
2、集合的交、并、差、补以及对称差等运算及有穷集的计数（文氏（Venn）图、包含排斥原理）
3、集合恒等式（幂等律、交换律、结合律、分配律、吸收律、矛盾律、德摩根律等）及应用
本章重点内容：
集合的概念、集合的运算性质、集合恒等式的证明。
[复习要求]
1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。
2、掌握集合的表示法和集合的交、并、差、补、对称差等基本运算。
3、掌握集合运算基本规律，证明集合等式的方法。
三、二元关系
[复习知识点]
1、序偶、迪卡儿积，迪卡儿积的性质及运算。
2、二元关系（定义、空关系、全域关系、恒等关系）、关系表达式、关系矩阵与关系图
3、关系的定义域、值域、限制、像、复合关系（右复合）与逆关系
4、关系的性质（自反性、反自反性、对称性、反对称性、传递性）
5、关系的闭包（自反闭包、对称闭包、传递闭包）
6、等价关系与等价类、商集、划分
7、偏序关系与哈斯图、极大/小元、最大/小元
本章重点内容：
二元关系的概念、关系的性质、关系的闭包、等价关系及划分、偏序关系和哈斯图
[复习要求]
1、了解序偶与迪卡儿积的概念，掌握迪卡儿积的运算。
2、理解关系的概念：
二元关系、空关系、全域关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。
3、掌握求复合关系与逆关系的方法。
4、理解关系的性质（自反性、反自反性、对称性、反对称性、传递性），掌握其判别方法（定义、图）。
5、掌握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法。
6、理解等价关系和划分、掌握等价类和划分的求法
7、理解偏序关系的概念，掌握画哈斯图的方法，极大/小元、最大/小元的求法。
四、函数
[复习知识点]
1、理解函数概念：
函数、函数相等、A到B的函数。
2、理解单射、满射、双射等概念，掌握其判别方法。
3、函数的复合与反函数
本章重点内容：
函数的定义及判别方法、函数的三大性质、函数的复合与反函数。
[复习要求]
1、掌握函数及从A到B的函数的判别方法。
2、理解函数的像与原像。
3、掌握函数的单射、满射、双射的判别方法。
4、掌握求函数的复合与反函数的方法。
五、图论
[复习知识点]
1、图的基本概念：
无向图与有向图、顶点与边的关联关系、顶点（边）与顶点（边）之间邻接关系、简单图与多重图、顶点度数（度）与握手定理、图的同构、完全图、子（补）图。
2、通路与回路、简单通（回）路与初级通（回）路；连通图与非连通图、连通分支、点割集、边割集、点（边）连通度；强连通图、单向连通图与弱连通图；二部图。
3、图的矩阵表示：
关联矩阵、邻接矩阵、可达矩阵。
4、欧拉通（回）路、（半）欧拉图；哈密尔顿通（回）路、（半）哈密尔顿图；
5、无向树、生成树、带权树、最小生成树。
6、有向树、树根、有序树、二叉树、最优二叉树、前缀码、最佳前缀码、霍夫曼（Huffman）算法、二叉树的周游及应用。
本章重点内容：
握手定理、点（边）割集、通路与回路、特殊图（欧拉图与哈密顿图、无（有）向树）、最优二叉树、最佳前缀码、霍夫曼（Huffman）算法。
[复习要求]
1、理解图的有关概念：
图、完全图、简单图、子图、母图、生成子图等。
2、深刻理解握手定理及其推论的内容，并能熟练地应用它们。
3、能判断两个图是否同构。
4、理解连通度、点割集、边割集、割边和割点。
5、能判断图是否为强连通图、单向连通图与弱连通图。
6、理解图的矩阵表示（关联矩阵、相邻矩阵）和性质以及熟练掌握用有向图的邻接矩阵及各次幂求图中通路与回路数的方法。
4、理解欧拉图、哈密顿图的定义及判别定理。
在无向图中找出一条欧拉通路或欧拉回路、哈密顿通路或哈密顿回路。
5、理解无向树的定义，熟练掌握无向树的主要性质，并能灵活应用它们。
6、理解生成树的有关概念与性质。
7、理解有向树、根树、二叉树和前缀码的有关概念；掌握用霍夫曼（Huffman）算法求带权图的最优二分树，掌握求最佳前缀码方法，二叉树的中序和前序行遍法。
考试说明
一、考核方式
1）期末笔试为100分钟的闭卷考试，占总评成绩的70％。
2）平时成绩来自作业、考勤和课堂考核，占总评成绩30％。
二、各部分比例（大概为讲授学时*2.5）
1）数理逻辑：
35分
2）集合论：
40分
3）图论：
25分
三、考题类型
1）单选题：
20题，每题1分，共20分
2）判断题：
20题，每题1分，共20分
3）填空题：
10题，每题2分，共20分
4）综合题：
5题，每题8分，共40分
四、常见综合题
1.用等值演算法证明等值式。
2.在自然推理系统P中构造证明推理（多种方法）
3.用等值演算法求解主析取范式或主合取范式，计算分析
4.集合恒等式的证明或化简（1-2例题或练习）
5.集合的运算，有穷集的计数（文氏图、包含排斥原理）
6.求二元关系导出的划分（1-2例题或作业）
7.给定一个偏序集，画出哈斯图并求极大、极小元素、求最大、最小元素、上界、最小上界、下界、最大下界、上确界和下确界。
8.图的集合表示、图形表示、矩阵表示，以及相互之间的转换。
9.利用握手定理，无向树中的顶点数、边数、度数、叶子数，知道其中部分数据，求其余部分数据。
10.用Huffman算法求最优二叉树产生的最佳前缀码（根树的应用）。
《离散数学》试卷结构及样题
一、单选题（20小题，每题1分，共20分）
1.设
是人，
犯错误，命题“没有不犯错误的人”符号化为（）
A.
B.
C.
D.
2.设A={x,y},B={y,z}则A×B为（）
A.{（x,y）,（x,z）,（y,y）,（y,z）}B.{（y,x）,（x,z）,（y,y）,（y,z）}
C.{（x,y）,（z,x）,（y,y）,（y,z）}D.{（x,y）,（x,z）,（y,y）,（z,y）}
3.设集合A={1,2,3},A上的关系R＝{（1,1）,（2,2）,（2,3）,（3,3）,（3,1）},则R具有（）
A.反自反性B.传递性C.对称性D.以上答案都不对
4.关于整数集Z上的“＜”关系R，以下描述不正确的是（）
A.R的自反闭包是“≤”关系B.R的对称闭包是“≠”关系
C.R的传递闭包是它本身D.R的反自反闭包是“＞”
5.下列图中（）是欧拉图
……
二、判断题（20小题，每题1分，共20分）
1.公式⌝（∀xF（x）→∃yG（y））∧∃yG（y）是可满足式。
（）
2.
这个定律叫做假言三段论。
（）
3.设A=｛a，b，c，d｝，R是A上的一个二元关系，R={,,,}是自反的，是反对称的，是传递的。
（）
4.在每个图中，所有顶点的度数之和等于边数的两倍。
（）
5.树是不包含回路的连通图，在（n，m）树中必有m=n+1（）。
……
三、填空题（10小题，每题2分，共20分）
1.已知命题公式
，则G的析取范式为。
2.设A={2,3,4,5}，若A上的关系为R={|（x-y）/2是整数}，则R=。
3.R是集合X上的一个关系，如果R是自反的，对称的，传递的，则R称为。
4.无向完全图Kn的边数为。
5.在一个图中，不与任何一个顶点相邻接的点叫做。
……
四、综合题（5小题，每题8分，共40分）
1．用等值演算法证明等值式（p→q）∧（p→r）
（p→（q∧r））。
2．对偏序集（{3，5，6，15，24，30}，|）上的整除关系，画出哈斯图并回答下列问题：
1）求极大、极小元素；
2）求最大、最小元素；
3）找出{3，5}的所有上界，如果存在的话求出最小上界；
4）找出{15，30}的所有下界，如果存在的话求出最大下界。
……
《离散数学》复习题
一、选择题
1.下述句子中哪一个不是命题（）
A.
是有理数B.2020年元旦下大雪
C.我正在说假话D.ln1是整数
2.在自然推理系统P中，推理规则通常不包括（）
A.直接证明法B.前提引入规则
C.置换规则D.结论引入规则
3.命题
的意义是（）
A.对任何x均存在y使得x2+y2=1B.对任何y均存在x使得x2+y2=1
C.存在y对任何x均使得x2+y2=1D.存在x对任何y均使得x2+y2=1
4.下述句子中哪一个是命题（）
A.海南岛的天气好热啊！
B.我知道我什么都不知道
C.开会时请关闭手机D.明天天气晴朗
5.判断推理是否正确的方法通常不包括（）
A.真值表法B.归纳法
C.等值演算法D.主析取范式法
6.在自然推理系统P中,联结词符号不包括（）
A.⌝B.→C.↔D.⇔
7.在自然推理系统P中，构造证明的方法通常不包括（）
A.直接证明法B.附加前提证明法
C.归纳法D.归谬法
8.对于集合的表示法，下列表示错误的是（）
A.{x|x是实数˄x2-1=0}B.{x|x2-1=0，其中x是自然数}
C.{-1,1}D.{x是实数并且x2-1=0}
9.下列命题中错误的是（）
A.{1}⊂{1,{1}}B.{1}⊆{1,{1}}
C.{1}∈{1,{1}}D.1∈{{1}}
10.下列集合的基数互不相等的是（）
A.{∅,{∅}}和{1,2}B.∅和{∅}
C.{∅,{∅}}和{1,{1,2}}D.{1，1,{1,2,3}}和{1,{1,2}}
11.设M（x）:
x是人，P（x）:
x犯错误，命题“没有不犯错误的人”符号化为（）
A.
B.
C.
D.
12.设G、H是谓词公式，P是谓词，G＝
H＝
则谓词公式
是（）
A.永真的B.永假的
C.可满足的D.矛盾的
13.对于集合的表示法，下列表示正确的是（）
A.（-1,0,1）B.{x|x2-1=0˄x是自然数}
C.[-1,0,1]D.{x是实数并且x2-1=0}
14.设a、b、c各不相同，对于下列选项中的两个集合，相等的是（）
A.{{a,b},c}和{c,{a,b}}B.{a,b,c}和{a,b,{c}}
C.{{a},b,c}和{a,b,c}D.{{a,b}}和{a,b}
15.设A、B、C为集合，下列命题中错误的是（）
A.（A⋃B）⋂B⊆BB.A-B=A⇔B=∅
C.A-B=∅⇔A⊆BD.A⋃B=B⇔A⋂B=A
16.设A={1,2,3},B={1,2},那么下列不是从A到B的二元关系的是（）
A.{<1,2>,<1,3>}B.A×B
C.∅D.{<1,1>,<2,1>,<3,1>}
17.设R={<1,2>,<1,3>,<2,4>,<4,1>},则domR和ranR分别是（）
A.{1,2,4}和{2,3,4}B.{1,2,4}和{1,2,3,4}
C.{1,2,3,4}和{1,2,3}D.{1,2,3}和{1,2,3,4}
18.设R={<1,2>,<1,4>,<2,2>,<2,3>},S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}，则R︒S是（）
A.{<1,3>}B.{<1,3>,<2,3>}
C.{<1,3>,<2,3>,<2,2>}D.{<1,3>,<2,1>,<2,3>}
19.设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,1>,<3,2>}，则R[{2}]是（）
A.{<1,2>,<2,2>,<3,2>}
B.{<2,2>,<2,4>}
C.{1,2,3}
D.{2,4}
20.列集合的基数互为相等的是（）
A.{∅,{∅}}和{1,{∅，1,2}}B.∅和{∅}
C.{∅,{∅}}和{1,{1,2},3}D.{1,1,{1,2,3}}和{1,{1,2},3}
21.设X={∅}，Y=P（∅,{∅}），下列命题为假的是（）
A.X⊂YB.X=Y
C.{X}∈YD.{X}⊆Y
22.设A={1,2,3},B={1,2},那么下列不是从A到B的二元关系的是（）
A.{<1,2>,<1,3>}B.A×B
C.∅D.{<1,1>,<2,1>,<3,1>}
23.设R={,,,},则domR和ranR分别是（）
A.{a,b,c}和{b,c,d}B.{a,b,d}和{b,c,d}
C.{a,b,c}和{b,c}D.{a,b,d}和{b,c}
24.下列关系中哪个能构成函数？
（）
A.{|x,y∈N,x+y<10} B.{|x,y∈N,x+y=20}
C.{|x,y∈R,|x|=y} D.{|x,y∈Z,x=|y|}
25.设无向图如图所示，则（）是一条哈密顿回路
A．gabcdefgB．abcdefgC．cfabcdegD．efgabcd
26.设G为n阶m条边的无向连通图，则下列（）是不可能的。
Am27.设A={1,2,3,4}，定义在A上的关系R={<1,1>,<1,2>,<2,1>,<3,4>},则关系R具有性质（）
A.自反的B.对称的
C.传递的D.以上均不对
28.设A={1,2,3}，定义在A上的关系R={<1,1>,<2,1>,<1,3>}，则R的对称闭包是（）
A.{<1,1>,<2,1>,<2,2>,<1,3>,<3,1>,<3,3>}
B.{<1,1>,<2,1>,<1,3>,<3,1>,<1,2>}
C.{<1,1>,<1,2>,<2,1>,<1,3>,<3,1>,<2,2>,<3,3>}
D.以上均不对
29.下列（）是满2元树
30.下列给出的符号串集合（）不是前缀码。
A.{1,11,101,001,0011}B.{1,01,001,000}
C.{0,10,110,1111}D.{b,c,dd,dc,aba,abb,abc}
二、判断题
1.设R是集合A上的关系，若
是对称的，则
也是对称的。
（）
2.设A=｛a，b，c，d｝，R是A上的一个二元关系，R={,,,}是自反的，是反对称的，是传递的。
（）
3.自然数集N上的关系“≤”（小于等于）是偏序关系，也是全序关系，同时也是良序关系。
（）
4.设R是整数集Z上的一个关系，如果R是拟序，则R是反对称的。
（）
5.在每个图中，所有顶点的度数等于边数的两倍。
（）
6.树是不包含回路的连通图，在（n，m）树中必有m=n+1（）。
7.公式p↔q为重言式。
（）
8.如果推理正确，则结论一定正确。
（）
9.若明天有超强台风，则明天放假。
明天不放假，所以明天没有超强台风。
（）
10.在公式
中，x为指导变元，
为
的辖域。
（）
11.公式⌝（∀xF（x）→∃yG（y））∧∃yG（y）是可满足式。
（）
12.设a、b各不相同，{{a},{b}}={{a,b}}。
（）
13.空集是所有集合的子集。
（）
14.设R为二元关系，则R既可能不是对称的，也可能不是反对称的。
（）
15.函数f:
N
N,f（x）=（x）mod3,x除以3的余数,是满射，不是单射（）
16.设T是n阶非平凡的无向树，则T中至少有两片树叶。
（）
17.如果函数f:
X→Y是满射函数，而且是一对一函数，那么f:
X→Y一定存在逆函数。
（）
18.如果函数f:
X→Y是一一对应函数，那么f:
X→Y一定存在逆函数。
（）
19.设R是整数集Z上的一个关系，R={|x−y是偶数}，则R是等价关系。
（）
20.自然数集N上的关系“≤”（小于等于）是偏序关系，也是全序关系，同时也是良序关系。
（）
21.自然数集N上的关系“<”（小于）是偏序关系，也是全序关系，同时也是良序关系。
（）
22.自然数集N上的关系“整除”是偏序关系，也是全序关系，同时也是良序关系。
（）
23.设R是整数集Z上的一个关系，如果R是拟序，则R是反对称的。
（）
24.在每个图中，所有顶点的度数等于边数的两倍。
（）
25.在任何有向图中，所以顶点的入度之和等于所有顶点出度之和。
（）
三、填空题
1.公式
（q→
p）∧
p的主合取范式为。
2.根据假言推理定律，（⌝A→⌝B）∧⌝A
。
3.设M（x）:
x是男生,F（y）:
y女生,H（x,y）:
x比y力气大，则命题“不是所有的男生都比所有的女生力气大”符合号形式为。
4.在一阶逻辑中将命题符号化时，若没有指明个体域，则使用。
5.公式⌝∃x（M（x）∧F（x））的前束范式是。
6.量词辖域收缩与扩张等值式∀x（A（x）∨B）⇔。
7.设A={∅，1,a,{b}}，B={2,{a},{b}}，则A⊕B=。
8.无向图G有生成树当且仅当_______________。
9.对于2叉有序正则树，访问次序为：
___________________的行遍法为中序行遍法。
10.一个无向树的顶点是27，则它的边数有个。
11.公式
q∨p的成真赋值是。
12.（⌝A→B）∧（B→⌝C）
为假言三段论。
13.设F（x）:
x是人，G（x）:
x喜欢共享单车，则“有人不喜欢共享单车”符号化形式为。
14.在一阶逻辑中将命题符号化时，若没有指明个体域，则使用。
15.公式⌝∃x（M（x）∧F（x））的前束范式是。
16.设A={1,3,5,7,9}，B={2,3,5,7,10}，C={2,5,6}，则B-A⋂C=。
17.设A={0,1,2}，则A上不同关系的个数为。
18.设f:
R→R,f={|x∈R},该逆函数为：
。
19.连通无回路的无向图称为_______。
20.一个无向树的边数是27，则它的顶点有个。
四、综合题
1．设命题公式G=（Q∧R）∧（P→（
Q∧
R））,求G的主析取范式。
（各种方法都要求掌握）
2．用真值表判断下列公式的类型：
（p∧r）
（
p∧
q）
3．用等值演算法证明等值式（p∧
q）∨（
p∧q）
（p∨q）∧
（p∧q）。
4．在自然推理系统P中用附加前提法证明下面推理：
前提：
s
p,p
（q
r）,q
结论：
s
r
5．在自然推理系统P中构造下面推理的证明：
若明天是星期一或星期三，我明天就有课。
若我明天有课，今天必备课。
我今天没备课。
所以，明天不是星期一，也不是星期三。
6．某班有30个学生，其中18人会打篮球，10人会打排球，8人会打篮球和排球，7人会打篮球和网球，还有3人会打这三种球。
已知7个会打网球的人都会打篮球或排球。
求不会打球的人数。
7．设A={1,2,3,4,5,6,8,10,12,16,18}，“≤”为A上的整除关系，试完成：
哭—笑早—晚出—入左—右上—下1）画出偏序集的哈斯图；
2）设B={x|x∈A∧x＜5}，求出B的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界。
一（竿）翠竹一（方）鱼塘一（列）火车一（道）小溪
8．
9．一本书一顿饭一片田一块田一口牙设A={1,2,3,4}，在A⨯A上定义二元关系R：
,∈R⇔x+y=u+v，求R导出的划分。
10．
11．非和飞气和汽以和已请和情玩和完很和得跳和桃无向图G有18条边，3个4度顶点，4个5度顶点，其余顶点度数均小于3，问G的阶数n为至少是多少？
女字旁：
奶、妈、姑、妹10.在通信中，八进制数字出现的频率如下：
三、句子0：
35%1：
25%
2：
20%3：
15%
高兴＝开心＝快活＝快乐时刻＝时时＝时常4：
10%5：
10%
（男）——（女）湿——（干）红——（绿）6：
5%7：
5%
求传输它们的最佳前缀码，并求传
升级会员 