离散数学复习题参考带答案

一、选择题：（每题2’）1、下列语句中不是命题的有（）。A．离散数学是计算机专业的一门必修课。B．鸡有三只脚。C．太阳系以外的星球上有生物。D．你打算考硕士研究生吗?2、命题公式A与B是等价的，是指（）。A．A与B有相同的原子变元B．A与B都是可满足的C．当A的真值为真时，B的真值也为真D．A与B有相同的真值3、所有使命题公式P∨(Q∧¬R)为真的赋值为（）。A．010，100，101，110，111B．010，100，101，111C．全体赋值D．不存在4、合式公式(P∧Q)R的主析取范式中含极小项的个数为（）。A．2B．3C．5D．05、一个公式在等价意义下，下面哪个写法是唯一的（）。A．析取范式B．合取范式C．主析取范式D．以上答案都不对6、下述公式中是重言式的有（）。A．(P∧Q)(P∨Q)B．(PQ)((PQ)∧(QP))C．(PQ)∧QD．P(P∧Q)7、命题公式(PQ)(Q∨P)中极小项的个数为（），成真赋值的个数为（）。A．0B．1C．2D．38、若公式(P∧Q)∨(P∧R)的主析取范式为m001∨m011∨m110∨m111则它的主合取范式为（）。A．m001∧m011∧m110∧m111B．M000∧M010∧M100∧M101C．M001∧M011∧M110∧M111D．m000∧m010∧m100∧m1019、下列公式中正确的等价式是（）。A．(x)A(x)(x)A(x)B．(x)(y)A(x,y)(y)(x)A(x,y)C．(x)A(x)(x)A(x)D．(x)(A(x)∧B(x))(x)A(x)∨(x)B(x)10、下列等价关系正确的是（）。A．x(P(x)∨Q(x))xP(x)∨xQ(x)B．x(P(x)∨Q(x))xP(x)∨xQ(x)C．x(P(x)Q)xP(x)QD．x(P(x)Q)xP(x)Q11、设个体域为整数集，下列真值为真的公式是（）。A．xy（x·y=1）B．xy（x·y=0）C．xy（x·y=y）D．xy（x+y=2y）12、设S={,{1},{1,2}}，则有（）S。A．{{1,2}}B．{1,2}C．{1}D．{2}13、下列是真命题的有（）。A．{a}{{a}}B．{{}}{,{}}C．{,{}}D．{}{,{}}14、设S={,{1},{1,2}}，则2S有（）个元素。A．3B．6C．7D．815、已知幂集的基数|(A)|=2048，则集合A的基数|A|为（）。A．11B．12C．10D．916、设A={1，2，3}，则A上的二元关系有（）个。A．23B．32C．233D．32217、设A={a,b,c,d}，A上的等价关系R={a,b,b,a,c,d,d,c}∪IA，则对应于R的A的划分是（）。A．{{a},{b,c},{d}}B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}}D．{{a,b},{c,d}}18、设R，S是集合A上的关系，则下列说法正确的是（）。A．若R、S是自反的，则RS是自反的B．若R、S是反自反的，则RS是反自反的C．若R、S是对称的，则RS是对称的D．若R、S是传递的，则RS是传递的19、集合A上的相容关系R的关系矩阵M(R)的对角线元素（）。A．全是1B．全是0C．有的是1，有的是0D．有的是220、设集合A={1，2，3}，A上的关系R={1,1，1,2，2,2，3,3，3,2}，则R不具备（）。A．自反性B．传递性C．对称性D．反对称性21、设}3,2,1{S，S上关系R的关系图为（如图所示），则R具有（）性质。A．自反性、对称性、传递性B．反自反性、反对称性C．反自反性、反对称性、传递性D．自反性22、设S={1，2，3}，R为S上的关系，其关系图为则R具有（）的性质。A．自反、对称、传递B．什么性质也没有C．反自反、反对称、传递D．自反、对称、反对称、传递23、设A={1,2,3}，B={a,b}，下列各二元关系中是A到B的函数的是（）。A．R={1,a,2,a,3,a}B．R={1,a,2,a,2,b,3,a}C．R={1,a,2,b}D．R={2,a,2,b}24、设R为实数集，映射f：RR，f(x)=-x2+2x-1，则f是（）。A．单射而非满射B．满射而非单射C．双射D．既不是单射，也不是满射25、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（）。A．B．C．D．26、N是自然数集合，定义f：NN，f(x)=xmod3（即x除以3的余数），则f是（）。A．满射不是单射B．单射不是满射C．双射D．不是单射也不是满射27、设S={,{1},{1,2}}，则有（）S。A．{{1,2}}B．{1,2}C．{1}D．{2}28、集合A={x|x=2n∧nN}对（）运算封闭。A．加法B．减法C．乘法D．|x－y|29、设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（）。A．xA，有x*Z=Z*x=ZB．ZA，且xA有x*Z=Z*x=ZC．ZA，且xA有x*Z=Z*x=xD．ZA，且xA有x*Z=Z*x=Z30、下面偏序集（）能构成格。31、在（）中，补元是唯一的。A．有界格B．有补格C．分配格D．有补分配格。32、下面四组数能构成无向简单图的度数序列的有（）。A．(2,2,2,2,2)B．(1,1,2,2,3)C．(1,1,2,2,2)D．(1,1,3,3,3)33、无向图结点之间的连通性，是结点集之间的一个（）。A．连通关系B．偏序关系C．等价关系D．函数关系34、已知图G的相邻矩阵为：则G有（）。A．5点，8边B．6点，7边C．5点，7边D．6点，8边35、下列四组数为结点度序列，能构成无向图的是（）。A．2,3,4,5,6,7B．1,2,2,3,4C．2,1,1,1,2D．3,3,5,6,036、下列几个图是简单图的有（）。A．G1=(V1,E1)，其中V1={a,b,c,d,e}，E1={(a,b),(b,e),(e,b),(a,e),(d,e)}B．G2=(V2,E2)，其中V2=V1，E2={a,b,b,c,c,a,a,d,d,a,d,e}C．G3=(V3,E3)，其中V3=V1，E3={(a,b),(b,e),(e,d),(c,c)}D．G4=(V4,E4)，其中V4=V1，E4={a,a,a,b,b,c,e,c,e,d}37、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4度结点。A．1B．2C．3D．438、一棵树有2个4度结点，3个3数度结点，其余是树叶，则该树中树叶的个数是（）。A．8B．9C．10D．1139、设图G是有6个顶点的连通图，总度数为20，则从G中删去（）边后使之变成树。A．10B．5C．3D．240、下面那一个图可一笔画出（）。41、在如下各图中（）欧拉图。42、下图中既不是欧拉图，也不是哈密尔顿图的是（）。43、在如下的有向图中，从V1到V4长度为3的道路有（）条。A．1B．2C．3D．444、图中从v1到v3长度为3的通路有（）条。A．0B．1C．2D．3二、判断题（每题1分）1．)()())()((xxBxxAxBxAx。（Y）2．设A，B，C是任意三个集合。（1）若AB且BC，则AC。（Y）（2）若AB且BC，则AC。（N）（3）若AB且BC，则AC。（N）（4）(AB)C=(A×C)(B×C)。（Y）（5）A∪(BC)=(A∪B)(A∪C)。（N）3．A，B，C为任意集合，若A∪B=A∪C，则B=C。（N）4．可能有某种关系，既不是自反的，也不是反自反的。（Y）5．可能有某种关系，既是对称的，又是反对称的。（Y）6．设R是实数集，R上的关系S={x,y||x-y|＜2∧x,yR}，S是相容关系。（Y）7．若集合A上的关系R是对称的，则Rc也是对称的。（Y）8．数集合上的不等关系（≠）可确定A的一个划分（N）9．设集合A、B、C为任意集合，若A×B=A×C，则B=C。（N）10．函数的复合运算“”满足结合律。（Y）11．集合A上的恒等关系是一个双射函数。（Y）12．任何一个循环群必定是阿贝尔群。（Y）13．任何循环群必定是阿贝尔群，反之亦真。（N）14．设A，≤是偏序集，BA，则B的极大元bB且唯一。（N）15．群是每个元素都有逆元的半群。（N）16．在代数系统S,中，若一个元素的逆元是唯一的，其运算必是可结合的。（N）17．每一个有限整环一定是域，反之也对。（N）18．设A,∧,∨是布尔代数，则A,∧,∨一定为有补分配格。（Y）19．若平面图共有v个结点，e条边和r个面，则v–e+r=2。（N）20．任何有向图中各结点入度之和等于边数。（Y）21．若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（N）22．一个图是平面图，当且仅当它包含与Ｋ3,3或Ｋ5在２度结点内同构的子图。（N）23．有割点的连通图可能是哈密尔顿图。（N）24．无多重边的图是简单图。（N）25．根树中最长路径的端点都是叶子。（N）26．在完全二叉树中，若有t片叶子，则边的总数e=2t－1。（N）27．群中可以有零元（对阶数大于1的群）。（N）28．任何循环群必定是阿贝尔群，反之亦真。（N）29．每一个链都是分配格。（Y）30．不可能有偶数个结点，奇数条边的欧拉图。（N）31．集合A上的恒等关系是一个双射函数。（Y）32．设Q为有理数集，Q上运算*定义为),max(baba，则，Q是半群。（Y）33．在完全二元树中，若有t片叶子，则边的总数12te。（N）34．能一笔画出的图不一定是欧拉图。（Y）35．根树中最长路径的端点都是叶子。（N）36．命题公式(A∧(AB))B是一个矛盾式。（N）37．设R是实数集，R上的关系F={x,y||x-y|2∧x,yR}，则F是相容关系。（Y）38．设A，≤是偏序集，BA，则B的极大元bB且唯一。（N）39．无多重边的图是简单图。（N）40．谓词公式xP(x)xQ(x)∨yR(y)的前束范式是xzy(P(x)Q(z)∨R(y))。（Y）三、解答题（本题分4小题，共计35分）1、试求))()((PQQPP的主析取范式。2、用真值表判断下列公式是永真式？永假式？可满足式？（1）(P∧P)Q（2）(PQ)∧Q（3）((PQ)∧(QR))(PR)解：（1）真值表：PQPP∧P(P∧P)Q00101011001000111000因此公式（1）为可满足。（2）真值表PQPQ（PQ）(PQ)∧Q00100011001001011100因此公式（2）为永假式。（3）真值表PQRPQQRPR（（PQ）∧（QR））（PR）00011110011111010101101111111000101101011111010011111111因此公式（3）为永真式。3、设个体域是D={2，3，6}，F(x):x≤3，G(x):x5，消去公式x(F(x)∧yG(y))中的量词，并讨论其真值。解：x(F(x)∧yG(y))x(F(x))∧yG(y)(F(2)∧F(3)∧F(6))∧(G(2)∨G(3)∨G(6))F∧TF4、求下列公式的前束范式：(1)xF(x)∧﹁xG(x)(2)(xF(x,y)→yG(y))→xH(x,y)5、通过求主析取范式判断下列命题公式是否等值：(P∨Q)∧(P∨Q∨R)与(P∧(Q∨R))∨(Q∧(P∨R))。解：(P∨Q)∧(P∨Q∨R