《离散数学》复习提纲(2018)Word文件下载.doc
- 文档编号:6848092
- 上传时间:2023-05-07
- 格式:DOC
- 页数:14
- 大小:162KB
《离散数学》复习提纲(2018)Word文件下载.doc
《《离散数学》复习提纲(2018)Word文件下载.doc》由会员分享,可在线阅读,更多相关《《离散数学》复习提纲(2018)Word文件下载.doc(14页珍藏版)》请在冰点文库上搜索。
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={<
a,a>
<
a,c>
b,b>
c,c>
}是自反的,是反对称的,是传递的。
()
4.在每个图中,所有顶点的度数之和等于边数的两倍。
5.树是不包含回路的连通图,在(n,m)树中必有m=n+1()。
三、填空题(10小题,每题2分,共20分)
1.已知命题公式,则G的析取范式为。
2.设A={2,3,4,5},若A上的关系为R={<
x,y>
|(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Í
B B.A-B=AÛ
B=Æ
C.A-B=Æ
Û
AÍ
B D.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={<
<
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,4>
2,2>
<
2,3>
},S={<
3,2>
3,3>
},则R°
S是()
} B.{<
C.{<
} D.{<
19.设R={<
},则R[{2}]是()
B.{<
C.{1,2,3}
D.{2,4}
20.列集合的基数互为相等的是()
}}和{1,{Æ
,1,2}} B.Æ
}}和{1,{1,2},3} D.{1,1,{1,2,3}}和{1,{1,2},3}
21.设X={Æ
},Y=P(Æ
}),下列命题为假的是()
A.XÌ
Y B.X=Y
C.{X}Î
Y D.{X}Í
Y
22.设A={1,2,3},B={1,2},那么下列不是从A到B的二元关系的是()
23.设R={<
a,b>
b,c>
d,b>
d,c>
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.下列关系中哪个能构成函数?
()
|x,y∈N,x+y<
10}
B.{<
|x,y∈N,x+y=20}
|x,y∈R,|x|=y}
D.{<
|x,y∈Z,x=|y|}
25.设无向图如图所示,则()是一条哈密顿回路
A.gabcdefgB.abcdefgC.cfabcdegD.efgabcd
26.设G为n阶m条边的无向连通图,则下列()是不可能的。
Am<
n-1Bm=n-1Cm=nDm=n+1
27.设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,3>
},则R的对称闭包是()
2,2>
3,1>
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.公式Ø
()
12.设a、b各不相同,{{a},{b}}={{a,b}}。
()
13.空集是所有集合的子集。
()
14.设R为二元关系,则R既可能不是对称的,也可能不是反对称的。
()
15.函数f:
NN,f(x)=(x)mod3,x除以3的余数,是满射,不是单射()
16.设T是n阶非平凡的无向树,则T中至少有两片树叶。
()
17.如果函数f:
X→Y是满射函数,而且是一对一函数,那么f:
X→Y一定存在逆函数。
18.如果函数f:
X→Y是一一对应函数,那么f:
19.设R是整数集Z上的一个关系,R={<
x,y>
|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.(Ø
(B®
C)为假言三段论。
13.设F(x):
x是人,G(x):
x喜欢共享单车,则“有人不喜欢共享单车”符号化形式为。
14.在一阶逻辑中将命题符号化时,若没有指明个体域,则使用。
15.公式Ø
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,x+1>
|x∈R},该逆函数为:
19.连通无回路的无向图称为_______。
20.一个无向树的边数是27,则它的顶点有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 复习 提纲 2018