离散数学考试说明

《离散数学考试说明》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《离散数学》考试说明内容指要一、集合论空集的性质，集合之间的并、交、差、补和对称差运算二、数理逻辑1、命题的概念；2、5种基本的联结词（乛，∧，∨，→，↔）的含义；3、全称量词(x)，存在量词(x)的含义；4、如何求给定命题公式的主析取、主合取范式及其成真的赋值；5、如何使用P规则，T规则，CP规则对命题逻辑推理的证明；三、关系1、关系的概念；2、关系的三种表示方法：集合，矩阵，关系图；3、关系的五种性质：1）R是A上自反的Û("x)(x∈A→∈R)2）R是A上反自反的Û("x)(x∈A→ÏR)3）R是A上对称的Û("x)("y)(((x∈A)∧(

2、y∈A)∧(∈R))→(∈R))4）R是A上反对称的Û("x)("y)(((x∈A)∧(y∈A)∧(∈R)∧(∈R))→(x=y))5）R是A上传递的Û("x)("y)("z)(((x∈A)∧(y∈A)∧(z∈A)∧(∈R)∧(∈R))→(∈R))4、等价关系的概念；偏序关系的概念，如何画哈斯图，如何确定最小元、最大元、极大元和极小元5、如何求自反闭包，对称闭包；6、能通过集合，矩阵，关系图来判断关系具有的性质；7、掌握关系性质的证明8、函数的概念，函数的分类（单射、双射、满射），如何判断是那一类函

3、数；四、图论1、完全图的概念；2、简单通路，基本通路，简单回路，基本回路的概念；3、欧拉图的概念及判断方法；4、平面图的概念，如何计算面的次数；5、树的概念与性质；如何求带权图的最小生成树；五、代数系统1、代数系统的概念；如何判定是否为一个代数系统；2、二元基本运算律与特异元素的定义，如何判断代数系统中运算满足什么运算律，如何找一个代数系统中的零元、幺元；3、半群、群、子群、循环群、元素周期的概念；如何判断一个代数系统的类型，如何判断是否为子群。4、格的概念，如何判定一个代数系统是否为格；5、布尔代数的概念；各部分占分比率内容比率集合论约10%数理逻辑约25%关系约2

4、5%图论约20%代数系统约20%试卷结构题型比率选择题约20%填空题约20%应用题约30%证明题约30%《离散数学》期末考试样卷一、选择题（共20分，每题2分）1．设A，B为任意集合，下面命题中不恒为真的是(　)A．{x}∈{x，{x}}　　　　　　　　B．{x}{x，{x}}C．A－{}＝A　　　　　　　　　D．A－B＝BA＝B＝2．下列语句中为命题的是（　　　）A．这朵花是谁的？B．这朵花真美丽啊！C．这朵花是你的吗？D．这朵花是他的。3．设论域D={a,b}，与公式等价的命题公式是（　　　）A．A（a）∧A（b）B．A（a）→A（b）C．A（a）∨A（b）D．A

5、（b）→A（a）4．设集合S＝{1，2，3}，则S上不同的二元关系有(　)　　A．8个　　　B．16个　　C．256个　　　　　　　D．512个5．设R为实数集，函数f：R→R，f(x)=2x，则f是（）A．满射函数B．单射函数C．双射函数D．非单射非满射6．下列各图是无向完全图的是（　　　）7．结点数为奇数且所有结点的度数也为奇数的连通图必定是（）A．欧拉图B．哈密尔顿图C．非平面图D．不存在的8．平面图(如下)的三个面的次数分别是（　　　）A．11，3，4B．11，3，5C．12，3，6D．10，4，39．设R为实数集，对于任意a，b∈R，a*b＝a＋b＋ab，则

6、下述结论中正确的是(　)　　A．不构成代数系统　　B．构成半群，但不构成含幺半群　　C．构成含幺半群，但不构成群　　D．构成群10．下列整数集对于整除关系都构成偏序集，而能构成格的是（）A．{l，2，3，4，5}B．{1，2，3，6，12}C．{2，3，7}D．{l，2，3，7}一、填空题（共20分，每题2分）1．公式┐pq的成真赋值有________________个．2．设个体域为D={-2,3,6},F(x):x3,G(x):x>5.则在此解释下公式(x)(F(x)∧G(x))的真值为______.3．设A＝{1，2，3，

7、4，5，6}，B＝{x｜x＝n2＋1，n为自然数，x<20}，则A∩B＝________________．4．设A＝1，2，3，4，则划分B＝{{1，2，3}，{4}}对应的A上的等价关系R＝________________．5．设R为A上的关系，则R的自反闭包r(R)=，对称闭包s(R)=。6．若一条路中，所有边均不相同，则此路称作____________；若一条路中所有的结点均不相同，则称此路为____________。7．一个______________且______________的无向图称为树。8．代数系统，其中A为命题公式集合，