离散数学期末考试题(附答案和含解析3)

1一、单项选择题2.设集合A={1，2，3}，下列关系R中不．是等价关系的是（D）A.R={1,1,2,2,3,3}；B.R={1,1,2,2,3,3,3,2,2,3}；C.R={1,1,2,2,3,3,1,2,2,1,1,3,3,1,2,3,3,2}；D.R={1,1,2,2,3,3,1,2}.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．1∈A；B．{1，2，3}A；C．{{4，5}}A；D．∈A.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．A,+是群；B．A,×是群；C．A,÷是群；D．A,+,A,×,A,÷都不是群。8．下列图是欧拉图的是（D）10.下面不满足．．．结合律的运算是(C)A.),min(baba；B.),max(baba；C.)(2baba；D.abba2二、填空题12.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数))(g(fx42x,)x)(f(g72x//))(g(fxf(g(x))=f(2x+1)=(2x+1)+3=2x+4//))(f(gx=g(f(x))=g(x+3)=2(x+3)+1=2x+72//备注：fg=fg(x)=g(f(x))13．设S是非空有限集，代数系统P（S），∪中，其中P（S）为集合S的幂集，则P（S）对∪运算的单位元是，零元是S。14．设A，≤是格，其中A={1，2，3，4，6，8，12，24}，≤为整除关系，则3的补元是8。//（注：什么是格？即任意两个元素有最小上界和最大下界的偏序）15.命题公式)(QPP的成真指派为00，01，11，成假指派为10。16.设A={2,2，3,4,3,5}，B={1,3，2,5,3,4}，那么dom(A∩B)={3},ran(A∪B)={2,3,4,5}//关系R的定义域：domR={∃x|y(x,y∈R)},即R中所有有序对的第一元素构成的集合。关系R的值域：ranR={∃y|x(x,y∈R)},即R中所有有序对的第二元素构成的集合。关系R的域：fldR=domR∪ranR17.在根树中，若每一个结点的出度最多为（或≤）m,则称这棵树为m叉树。如果每一个结点的出度都为（或=）m或0，则称这棵树为完全m叉树。如果这棵树的叶都在同一层，那么称为正则m叉树。18．Zn,是一个群，其中Zn={0,1,2,……,n-1}，nyxyxmod)(，则在Z6,中，1的阶是6，4的阶是3。//单位元是e=019.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={1,2,2,1,2,3,3,4}，求R的传递闭包。解：由R={1,2,2,1,2,3,3,4}，得0000100001010010RM，从而00000000101001012MR，00000000010110103MR，00000000101001014MR，于是32R={1,1,1,3,2,2,2,4}，3R={1,2,1,4,2,1,2,3}，4R={1,1,1,3,2,2,2,4}=2R，故432)(RRRRRt=｛1,1,1,2,1,3,1,4,2,1,2,2，2,3，2,4，3,4}23.设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画A，R的哈斯图，并求A中的最大元、最小元、极大元、极小元。解：A，R的哈斯图如右图所示：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…）4四、证明题27.在整数集Z上定义：Z,,1bababa，证明：Z，是一个群。证明：（1）对于Zba,，有Z1baba，所以运算是封闭的。（2）对于Zcba,,，有2cba1c1bac)1()(bacba，2cba11cba)1()(cbacba，即)()(cbacba，故运算是可结合的。（3）1是单位元，因为Za，aaa11)1(，aaa11)1(.（4）Za，由112)2(aaaa，112)2(aaaa，可知a2是a的逆元。综上所述，Z，是一个群。28.设R为N×N上的二元关系，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）))()((xGxSP（2）)()(cGcSUS（1）（3）)()(xGxP（附加前提）（4）)()(xGxT(3)E(5))(cGUS(4)(6))(cST(2)(5)I(7))()(xSxUG(6)(8))()(xSxT(7)E