2022年2022年离散数学期末考试题 .pdf

1 一、单项选择题2.设集合 A=1 ， 2，3 ，下列关系R 中不是等价关系的是（D ）A.R=,；B.R=,；C. R=,；D. R=,. 3在公式（x）F（x，y）（y）G（x，y）中变元x 是（B ）A自由变元；(前面无?或?量词 ) B既是自由变元，又是约束变元；C约束变元；(前面有?或?量词 )D既不是自由变元，又不是约束变元. 4设 A=1 ，2，3 ， 4 ，5 ，6，7，8 ，下列选项正确的是（C）A 1A；B 1 ，2，3A；C4 ，5A；DA. 5.设论域为 l ，2 ，与公式)()(xAx等价的是 ( A) A.A(1)A(2)；B. A(1)A(2)；C.A(1)A(2)；D. A(2)A(1). 6.一棵树有5 个 3 度结点， 2 个 2 度结点，其它的都是l 度结点，那么这棵树的结点数是( B ) A.13 ；B.14 ；C.16 ；D.17 . /设一度结点数为n,则有： 5 3+2 2+n=2(5+2+n)-1 解得： n=7, 所以这棵树的结点数为：m=5+2+7=14. 7设 A 是偶数集合，下列说法正确的是（A）A 是群；B是群；C是群；D, ,都不是群。8下列图是欧拉图的是（D ）10.下面不满足结合律的运算是( C) A.),min(baba；B.),max(baba； C.)( 2baba；D.abba2二、填空题12.设 fR R,f(x)=x+3,gRR,g(x)=2x+1,则复合函数)(g(fx42x , )x)(f(g72x/)(g(fxf(g(x)=f(2x+1)=(2x+1)+3=2x+4 /)(f(gx=g(f(x)=g(x+3)=2(x+3)+1=2x+7 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 2 /备注： fg=fg(x)=g(f(x) 13设 S 是非空有限集，代数系统中，其中P（S）为集合S 的幂集，则P（ S）对运算的单位元是，零元是S 。14设是格，其中 A=1 ，2，3，4，6，8，12，24 ，为整除关系，则 3 的补元 是8 。/（注：什么是格？即任意两个元素有最小上界和最大下界的偏序）15.命题公式)(QPP的成真指派 为 00，01，11 ，成假指派 为 10 。16.设 A= ，, ，B= ，, ，那么 dom(AB)= 3 , ran(AB)= 2,3,4,5 / 关系 R 的定义域： domR=?x|y(R), 即 R中所有有序对的第一元素构成的集合。关系 R 的值域： ranR=?y|x( R), 即 R 中所有有序对的第二元素构成的集合。关系 R 的域： fldR=domR ranR 17.在根树中， 若每一个结点的出度最多为（或）m,则称这棵树为m 叉树。如果每一个结点的出度都为（ 或=）m 或 0，则称这棵树为完全m 叉树。如果这棵树的叶都在同一层，那么称为正则m 叉树。18是一个群，其中Zn=0,1,2, ,n-1 ，nyxyxmod)(，则在中，1的阶是6 ，4 的阶是3 。/单位元是e=0 19. n 点完全图记为Kn，那么当n 4时， Kn是平面图，当n 5 时， Kn是非平面图。20.若图中存在回路 ，它经过图中所有的结点恰好一次 ，则称该图为 汉密尔顿图 (哈密顿图 ) 。 / 欧拉图三、计算题21.求命题公式)()(PQQP的主析取范式。解：)()(PQQP)()(PQQP)()(PQQP)()(PQQP)()()(QQPQPPQP)()()()()(QPQPQPQPQP)()()(QPQPQP=111000mmm=)3 , 2, 0(22. 设 A=1,2,3,4 ，给A上的二元关系R=,，求 R 的传递闭包。解：由 R=,，得0000100001010010RM，从而00000000101001012MR，00000000010110103MR，00000000101001014MR，于是名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 3 2R=,，3R=,，4R =,=2R，故432)(RRRRRt=,， ， ， 23.设 A=1 ，2，3，4，6，8，12，24 ，R 为 A 上的整除关系，试画的哈斯图 ，并求 A 中的最大元、最小元、极大元、极小元。解： 的哈斯图如右图所示：A 中的最大元为 24、最小元为 1、极大元为 24、极小元为 1。24.求下图所示 格的所有 5 元子格 。解：所有 5 元子格如下：26.用矩阵的方法求右图中结点v1，v3之间长度为2 的路径的数目。/教材 P289、290所以，图中结点v1，v3之间长度为2 的路径的数目有3 条。/备注：邻接矩阵中所有元素之和等于边数。通路（v1-v1,v2,v3,v4 ）与回路（ v1-v1,v2-v2,v-v3 ）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 4 四、证明题27.在整数集 Z 上定义：Z,1bababa，证明： 是一个群。证明： （1）对于Zba,，有Z1baba，所以运算是封闭的。（2）对于Zcba,，有2cba1c1bac)1()(bacba，2cba11cba)1()(cbacba，即)()(cbacba，故运算是可结合的。（3）1是单位元，因为Za，aaa11)1(，aaa11)1(. （4）Za，由112)2(aaaa，112)2(aaaa，可知a2是a的逆元。综上所述， 是一个群。28.设 R 为 NN 上的二元关系，NNdcba,，dbdcRba,，证明 R 为等价关系。证明：因为NNba,，bb，所以baRba,，故 R 具有自反性。NNdcba,，若dcRba,，则db，即bd，故baRdc,，所以 R 具有对称性。NNfedcba,，若dcRba,，feRdc,，则db，fd从而fb，故feRba,，所以 R 具有对称性。综上所述，R 为等价关系。五、综合应用题29在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果没有人获得知识就没有人在学校读书。 （个体域：所有人的集合）证明：设 S（x）:x 是在学校读书的人，G（x） ：x 是获得知识的人。前提： （x）)()(xGxS；结论：)()(xGx)()(xSx推理过程如下：（1） （x）)()(xGxSP （2）)()(cGcSUS（1）（3）)()(xGxP（附加前提）（4）)()(xGxT(3)E (5) )(cGUS(4) (6) )(cST(2)(5)I (7) )()(xSxUG(6) (8) )()(xSxT(7)E 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -