离散数学考试说明

《离散数学考试说明》由会员分享，可在线阅读，更多相关《离散数学考试说明（7页珍藏版）》请在金锄头文库上搜索。

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

2、)(xA)(yA)(R)(R) 4） R 是 A 上反对称的 (x)(y)(xA)(yA)(R)(R)(x=y) 5） R 是 A 上传递的 (x)(y)(z)(xA)(yA)(zA)(R)(R)(R) 4、 等价关系的概念；偏序关系的概念，如何画哈斯图，如何确定最小元、最大元、极大 元和极小元 5、 如何求自反闭包，对称闭包； 6、 能通过集合，矩阵，关系图来判断关系具有的性质； 7、 掌握关系性质的证明 8、 函数的概念，函数的分类（单射、双射、满射） ，如何判断是那一类函数； 四、图论 1、 完全图的概念； 2、 简单通路，基本通路，简单回路，基本回路的概念； 3、 欧拉图的概念及判断方

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

4、选择题约 20%填空题约 20%应用题约 30%证明题约 30%离散数学离散数学期末考试样卷期末考试样卷一、一、选择题（共选择题（共 2020 分，每题分，每题 2 2 分）分）1设 A，B 为任意集合，下面命题中不不恒为真的是( )Axx，x Bxx，xCAA DABBAB2下列语句中为命题的是（ ）A这朵花是谁的？B这朵花真美丽啊！C这朵花是你的吗？D这朵花是他的。 3设论域 D=a,b，与公式等价的命题公式是（ ）)()(xAxAA（a）A（b）BA（a）A（b）CA（a）A（b）DA（b）A（a） 4设集合 S1，2，3，则 S 上不不同的二元关系有( )A8 个 B16 个 C256

5、 个 D512 个5设 R 为实数集，函数 f：RR，f(x)=2x，则 f 是（ ） A满射函数B单射函数 C双射函数D非单射非满射 6下列各图是无向完全图的是（ ）7结点数为奇数且所有结点的度数也为奇数的连通图必定是（ ）A欧拉图B哈密尔顿图C非平面图D不存在的8平面图(如下)的三个面的次数分别是（ ）A11，3，4B11，3，5C12，3，6D10，4，39设 R 为实数集，对于任意 a，bR，a*babab，则下述结论中正确的是( )A不构成代数系统B构成半群，但不构成含幺半群C构成含幺半群，但不构成群D构成群10下列整数集对于整除关系都构成偏序集，而能构成格的是（ ）Al，2，3，4

6、，5B1，2，3，6，12C2，3，7Dl，2，3，7二、填空题（共填空题（共 2020 分，每题分，每题 2 2 分）分）1公式pq 的成真赋值有_个2设个体域为 D=-2,3,6,F(x):x3,G(x):x5.则在此解释下公式(x)(F(x)G(x)的真值 为_.3设 A1，2，3，4，5，6，Bxxn21，n 为自然数，x，其中 A 为命题公式集合， 。为析取运算，则中零元素是_，幺元是_。9设a,bG，则（a-1）-1= ， （a b）-1= 。,G是群10一个格称为布尔代数，如果它是_格和_格.三、应用题（共三、应用题（共 3030 分，每题分，每题 1010 分）分）1求命题公式

7、(PQ)(QP)的主析取范式，并求成真赋值。 2设 A=a，b，c，R 是 A 幂集上的包含关系。（1） 画出偏序集的哈斯图； ),(AP（2）设 B=a,c,b,c，求 B 极大元、极小元、最大元、最小元。 3用克鲁斯克尔算法求以下赋权图的最小生成树（画出其生成过程） 。四、证明题（共四、证明题（共 3030 分，每题分，每题 1010 分）分）1构造下列推理的证明。 前提： (AB)(PQ)，P，(BA)P A 结论：A2已知 R 和 S 是非空集合 A 上的等价关系，试证：（1）RS 是 A 上的等价关系；（2）对。SRSRaaaAa ,II3设是一个群.C=aaG,对任意的 xG 有

8、a*x=x*a,证明是的一个子 群.离散数学离散数学期末考试样卷期末考试样卷试题答案及评分参考试题答案及评分参考一、选择题（共一、选择题（共 3030 分，每题分，每题 2 2 分）分）12345CDCDB678910CDACB二、填空题（共二、填空题（共 2020 分，每题分，每题 2 2 分）分） 12 2假（0，F） 31，2，5v1v2v3v4v5v60.51 234562.5 3.51.54,5,AIRU1RR U6简单通路，基本通路 7连通，不含回路 81，0 9A, b-1*a-1 10有补，分配 三、应用题（共三、应用题（共 3030 分，每题分，每题 1010 分）分） 1

9、解：(PQ)(QP)(PQ)(QP)(PQ)(QP)(PQ)QPQP(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) m0m2m3 7 分成真赋值为：00、10、11。 3 分2 解： （1）6 分 （2） 最大元：无；最小元：无；级大元：a,b,c级小元：a,c 4 分3 解： 每步骤 2 分, ,a b c,a b,a c,b c a b cv1v20.5v1v2v30.51v1v2v3v60.511.5v1v2v3v4v60.512.51.5四、证明四、证明题（共题（共 2020 分，每题分，每题 1010 分）分） 1 证明：(1)(AB)(PQ) P(2)(PQ)(AB)

10、 T(1)，E(3)P P(4)AB T(2)(3)，I(5)(BA)P P(6)BA T(3)(5)，I(7)AB T(6)，E(8)(AB)(AB) T(4)(7)，I(9)A(BB) T(8)，E(10)A T(9)，E2 证明：（1）1）自反性：xA，因为 R 和 S 是自反关系，所以R、S，因而RS，故 RS 是自反的。 2分2）对称性：x、yA，若RS，则R、S，因为 R 和 S 是对称关系，所以因R、S，因而RS，故 RS 是对称的。 2 分3）传递性：x、y、zA，若RS 且RS，则R、S且R、S，因为 R 和 S 是传递的，所以因R、S，因而v1v2v3v4v60.512.5

11、1.5v53.5RS，故 RS 是传递的。即 RS 是等价关系。 2 分（2）因为 xaRSRSRS xaRxaS xaRaS所以aRS=aRaS。 4 分3 证明：1）非空性 因为群中单位元素 e 满足 e*x=x*e=x 所以 eC,C 非空. 3 分 2）封闭性 设 aC, bC,则对任意 xG 有 a*x=x*a,b*x=x*b.于是,根据乘法结合律(a*b)*x=a*(b*x)=a*(x*b)=(a*x)*b=(x*a)*b=x*(a*b) 所以 a*bC. 3 分 3）可逆性 设 aC,则对任意 xG,有a*x=x*a 在上式两端左乘 a-1,右乘 a-1得a-1 (a(a*x)* a-1= a-1*(x*a)* a-1 根据乘法结合律,群中逆元素与单位元素性质x*a-1= a-1*x 所以 a-1C. 4 分