离散数学练习题答案修改

2016注意事项：1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。2、第二遍复习按照考试大纲的总结把重点内容再做复习。另外，把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。3、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。离散数学综合练习题一、选择题1．令:今天下雪了，:路滑，r:他迟到了。则命题“下雪路滑，他迟到了”可符号化为（A）。A. B.C. D.2.设:是整数，:的绝对值，：大于等于；命题“所有整数的绝对值大于等于0”可符号化为（B）。A. B.C. D.3.设:是人，:犯错误，命题“没有不犯错误的人”符号化为（D）。A． B．C． D．*4.下列命题公式不是永真式的是（A）。A. B.C. D.5．设p：我们划船，q：我们跳舞，命题“我们不能既划船又跳舞”符号化正确的是（B）。A. B.C. D.6．设:x为有理数；:x为实数。命题“任何有理数都是实数”的符号化为（A）A． B．C． D．7.设个体域，与公式等价的命题公式是(C)A． B．C． D．8．无向图G有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点，则G一共有（C）个顶点。 *9.设集合A={c,{c}}，下列命题是假命题的为（C）。A.B.C. D.10.设X=，则下列陈述正确的是（C）。A. B.C. D.11.有向图D是连通图，当且仅当（D）。A.图D中至少有一条通路B.图D中有通过每个顶点至少一次的通路C.图D的连通分支数为一D.图D中有通过每个顶点至少一次的回路12.设A={a,b,c}，则下列是集合A的划分的是(B)A. B.C. D.13.下列谓词公式中是前束范式的是（D）。A． B．C． D．14.设简单图G所有结点的度数之和为50，则G的边数为（B）。A.50 B.25C.10 D.515.设集合,上的等价关系，则对应于的划分是（A）。A. B.C. D.16.设，则是(C)。A．从X到Y的双射B．从X到Y的满射，但不是单射C．从X到Y的单射，但不是满射D．从X到Y的二元关系，但不是从X到Y的映射17.下列图是欧拉图的是（D）。18.给定一个有n个结点的无向树，下列陈述不正确的是（A）。A．所有结点的度数≥2 B．无回路但若增加一条新边就会变成回路C．连通且，其中e是边数，v是结点数D．无回路的连通图19．若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是（C）。A.(1,2,2,3,4,5) B.(1,2,3,4,5,5)C.(1,1,1,2,3) D.(2,3,3,4,5,6)20.设则其幂集的元素总个数为（C）。A.3 B.4C.8 D.1621.设简单图G所有结点的度数之和为48，则G的边数为(B)A.48 B.24C.16 D.1222．下面既是哈密顿图又是欧拉图的图形是（B）。23.下列必为欧拉图的是（D）A.有回路的连通图 B.不可以一笔画的图C.有1个奇数度结点的连通图 D.无奇数度结点的连通图24.二部图是（B）。A.欧拉图 B.哈密顿图C.平面图 D.完全图25．下列所示的哈斯图所对应的偏序集中能构成格的是（C）。A. B.C. D.26.设集合，A上的关系，则R是（B）A．自反的 B．对称的C．传递的 D．反对称的27．设是集合上的两个关系，其中，，则是的（B）闭包。A．自反 B．对称C．传递 D．自反、对称且传递闭包28.下列公式是前束范式的是（A）。A． B．C． D．29.设R为实数集，函数，，则是（D）。A．单射而非满射 B．满射而非单射C．双射 D．既不是单射，也不是满射30．下列各图中既是欧拉图，又是汉密尔顿图的是（C）。A．B．C．D．12.设，则方程的解为（B）。A．M∩N B．M∪NC．MNC．M-N13.设是群，则下列陈述不正确的是（C）。A. B.C. D.二、填空题1．命题公式的成真指派为000111,成假指派为_10__。2．公式约束变元为x,y，自由变元为x,z。3．设，，则,，{{a,b}}。4．设，上的关系，则对称闭包，传递闭包。5.一棵无向树的顶点数与边数的关系是n-1。6阶无向连通图至多有6棵不同构的生成树。6．设，，则复合函数=,=。7.是一个群，其中，，则当=6时，在中，2的阶为__3____,3的阶为_2。8．设<A，≤>是格，其中A={1,3,4，6，8，12，24}，≤为整除关系，则1的补元是___24__，3的补元是__8__。9．设A=｛<1，3>，<3，5>，<4，4>｝，B=｛<1,3>,<4,5>,<5,5>｝,那么={1,3,4,5}ran={3}_。10.设A={l,2,3,4},A上的二元关系R={<1,2>,<2,3>,<3,2>}，S={<l,3>,<2,3>，<4，3>}，则{<1,3>,<3,3>},{<3,1>,<3,3>}。11．设复合函数gf是从A到C的函数，如果gf是满射，那么__g___必是满射，如果gf是单射，那么__f_必是单射。12．给出A={l，2}上的一个等价关系，并给出其对应的划分。13．设，上的二元关系，则的自反闭包，传递闭包R14．设个体域是实数集，命题的真值为1；命题的真值为0。15.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数,。16．设为模6加群，其中，则2-3=0，4-2=4。17．一个结点为n的无向完全图，其边的数目为n(n-1)/2，顶点的度为n-1。18.已知阶无向简单图有条边，则的补图中有n(n-1)/2-m条边。19.设是个顶点的完全图，则K5有_10____条边，每个顶点的度数为___4___。20.一个班有40个人，在第一次考试中有26人得优秀，在第二次考试中有21人得优秀，如果两次考试都得优秀的有17人，两次考试都没有得优秀的人数为10，至少有一次得优秀的人数为30。三、计算题（仅给出部分题目的解题思路，未给出答案自己完成）1.已知命题公式（1）构造真值表；（2）用等值演算法求公式的主析取范式。解：（1）真值表pqr00000110010101010101101111001001100101110011011001111100（2）主析取范式2．求公式的主合取范式及主析取范式。3.设，,，其中表示实数集。（1）求函数，；（2）哪些函数有反函数如果有，求出这些反函数。解：（1）（2）和有反函数，；4.设，为整除关系。（1）画出偏序集<A,>的哈斯图；（2）求A中的极大元；（3）求子集B=｛3,6,9｝的上确界与下确界。解：（1）哈斯图（2）A中的极大元为24，54；极小元为1；最大元：无；最小元：1（3）求子集B=｛3,6,9｝的上确界为54，下确界为3。5.设有向图如图所示，用邻接矩阵计算到长度小于或等于3的通路数。解：有向图的邻接矩阵为，，v1到v3长度小于或等于3的通路数为6．设，给出模6加运算的运算的运算表。解：运算的运算表为012345001234511234502234501334501244501235501234参看教材P197-198例与7.设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{（2，1>，<2，5），<2，4>，<3，4)，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。解：r(R)=R∪IAs(R)=R∪R-1t(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>,（2,2>,<5,5>}8.一棵（无向）树有2结点的度为2，1个结点的度为3，3个结点的度为4,其余都是叶结点，问该树有几个叶结点解：在一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。根据这两点，可知树中各结点的度数总和=2*（树中点数-1），设树叶有x个，于是，2*2+3+3*4+x=2*（2+1+3+x-1）

得x=9。四、简答题1.设是A=上的二元关系。（1）画出R的关系图；（2）写出R的关系矩阵；（3）讨论R的性质。（4）R是否为函数解：（1）R的关系图（2）R的关系矩阵（3）R非自反、非反自传、对称、非反对称、非传递的（4）R不是函数，不满足函数单值性的要求。2.设集合上的关系（1）画出的关系图，并写出的关系矩阵；（2）是否为等价关系若是，写出的所有等价类。解：（1）R的关系图为（2）R的关系矩阵由关系图可以看出是等价关系。等价类为：或写为：A/R={{1,3,6},{2,5},{4}}3．判断下图是否为二部图若是，找出它的互补结点子集。它是否为哈密顿图若是，找出一条哈密顿回路。四、证明题1．设为正整数，在上定义二元关系如下：当且仅当。证明：是一个等价关系。证明：任取所以R自反的。任取所以R是对称的。任取所以R是传递的。因此，R是等价关系。2．设为正整数，在上定义二元关系如下：当且仅当。证明：是一个等价关系。证明：任取所以R自反的。任取所以R是对称的。任取所以R是传递的。因此，R是等价关系。3.用一阶逻辑的推理理论证明：4．设代数系统，，为模6加法。证明：关于运算构成群。证明：集合显然非空。(1),,从而集合关于运算是封闭的。(2),有，故运算是可结合的。(3),,故0是中的幺元。(4),因为,因此是的逆元由此上知是群5．设A是集合，P(A)是A的幂集合，是对称差运算，证明<P(A),>构成群。五、应用题（未给出参考答案的自己完成）1.构造下列推理的证明。如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则不考英语。今天是星期一，英语老师有会，所以进行离散数学考试。（给答案）2.构造下列推理的证明。小王是理科学生，则他的数学成绩很好。如果小王不是文科学生，则他一定是理科学生。小王的数学成绩不好,所以小王是文科学生。3.用一阶逻辑推理证明前提：，，结论：证明：（1）前提引入（2）（1）（3）前提引入（4）（3）（5）（2）（4）析取三段论（6）前提引入（7）（6）（8）（5）（7）假言推理（9）（8）4．今有于7个人，已知下列事实：a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和