离散数学-(-第2次-)

第2次作业一、单项选择题（本大题共60分，共20小题，每小题3分）1.表达式F∧(P∨(Q∧┐S))的对偶式为。A.F∨(P∧(Q∨┐S))B.T→(P∨(Q∨┐S))C.T∨(P∧(Q∨┐S))D.T∨(P∧(Q∧S))2.设R^+,∙是正实数乘法群，R,+是实数加法群。令f：R^+→R,f(x)→log⁡(x)，则（）A.f是R^+,∙到R,+的满同态映射B.f是R^+,∙到R,+的单一同态映射C.f是R^+,∙到R,+的同构映射D.f是R^+,∙到R,+的自同构映射3.对任意的公式P、Q、R，若P⇒Q、Q⇒R，则有。A.R⇒PB.P⇒RC.Q⇒PD.R⇒Q4.设有33盏灯，拟公用一个电源，则至少需要（）个5插头的接线板?A.4B.6C.8D.105.下列关系中哪些能构成函数？（）A.{〈x,y〉|x,y∈N,x+y10}B.{〈x,y〉|x,y∈N,x+y=10}C.{〈x,y〉|x,y∈R,|x|=y}D.{〈x,y〉|x,y∈R,x=|y|}6.设集合A={1,{2},a,4,3}，下面命题为真是（）。A.2∈A；B.1∈A；C.5∈AD.{2}7.在一个具有n个节点的图中，则任何基本路的长度均不大于______。A.nB.n-1C.n+1D.2n8.下列说法不正确的是（）。A.实数集R上的普通减法是代数运算B.整数集Z上的普通减法是代数运算C.自然数集N上的普通减法是代数运算D.有理数集Q上的普通减法是代数运算9.下面关于广群，半群，独异点，群的关系正确的是（）A.{群}{独异点}{半群}{广群}B.{广群}{半群}{独异点}{群}C.{半群}{独异点}{群}{广群}D.{群}{半群}{独异点}{广群}10.下列命题公式与┐(A∨B)等价的是。A.┐A∧┐BB.┐A∨BC.┐A∨┐BD.A∧B11.令S={a，b}，S上有4个二元运算：*，°，∙，∆分别由表5.2.2-1、表5.2.2-2、表5.2.2-3和表5.2.2-4确定。表5.2.2-1表5.2.2-2表5.2.2-3表5.2.2-4下面说法正确的是A.运算*的幺元是a，无零元B.运算°的幺元是a，无零元C.运算∙的幺元是a，无零元D.运算∆的幺元是a，无零元12.对于公式∃x（¬∃yP(x,y)→(∃zQ(z)→R(x)的前束范式，下列各式中，哪式是正确的（）。A.∃x∃y∀z（P(x,y)∨¬Q(z)∨R(x))B.∃x∃y∃z（P(x,y)∨¬Q(z)∨R(x))C.∃x∃y∀z（P(x,y)∨Q(z)∨R(x))D.∃x∃y∀z（P(x)∨¬Q(z)∨R(x))13.如果小王和小张都不去，则小李去。设P：小王去。Q：小张去。R：小李去。则命题符号化为。A.┐Q∧┐P∨RB.(Q→P)∧RC.(┐P∧┐Q)→RD.(P∧Q)→R14.没有不犯错误的人。M(x)：x为人。F（x）：x犯错误。则命题可表示为（）。A.(∀x)(M(x)→F(x)B.(∃x)(M(x)⋀F(x)C.（∀x）(M(x)⋀F(x))D.(∃x)(M(x)→F(x)15.命题公式(P→Q∧┐P)的类型是。A.重言式B.矛盾式C.可满足式D.永真式16.设完全图Kn有n个结点（n2），m条边，当（）时，Kn中存在欧拉回路。A.m为奇数B.n为偶数C.n为奇数D.m为偶数17.关于半群的性质，下面说法不正确的是（）A.若S,*S且*在B上是封闭的，那么是一个半群，BB,*也是一个半群。B.若S,*是一个半群，如果S是一个有限集，则必有a∈S,使得a*a=a。C.若•表示普通的乘法运算，那么[0,1],•、[0,1),•和I,•都是R,•的子半群D.18.下列推理步骤错在（）(1)∀x(F(x)→G(x))P(2)F(y)→G(y)US(1)(3)∃xF(x)P(4)F(y)ES(3)(5)G(y)T(2)(4)I(6)∃xG(x)EG(5)A.(2)B.(4)C.(5)D.(6)19.已知图G的邻接矩阵为则G有（）。A.5点，8边B.6点，7边C.6点，8点D.5点，7边20.谓词公式F(x,y,z)→∀x∃yG(x,y,z)中的变元x()A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元二、判断题（本大题共12分，共6小题，每小题2分）1.设G是平面图。将G嵌入平面后，由G的边G将所在的平面划分为若干个区域，每个区域称为G的一个面。2.任何一棵二叉树的树叶可对应一个前缀码。3.判断该句是否为命题。是大学生。4.若A和B均为重言式，则A∨B也为重言式。5.给出下图的三种遍历结果前根：a,b,d,g,e,h,i,c,f中根：g,d,b,g,e,i,a,c,f后根：g,d,h,i,e,b,f,c,a6.设R是集合A上的二元关系，若R是传递的，则r(R)也是传递的，而s(R)不一定是传递的。（）三、填空题（本大题共28分，共7小题，每小题4分）1.在一阶逻辑中，将命题“没有不能表示成分数的有理数”符号化为________(设F(x):x是有理数；G(x):x能表示成分数。)2.判断下列命题的正确性：(1)全集合U的幂集上的“⊆”关系也是一个偏序关系。()(2)正整数集上的整除关系是偏序关系。()(3)实数集R上的“＜”关系是偏序关系。()(4)真包含关系“⊂”也不是偏序关系。()3.给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素，则该序列集合构成前缀码．4.判断以下集合是否为集合A的覆盖？其中A={a,b,c,d,e,f}（1）S_1={ϕ,{a,b},{c,d},{f}}（）（2）S_2={{a,b},{c,d},{f,g}}（）（3）S_3={{a,b},{c,d},{f}}（）（4）S_4={{a,b},{c,d,e},{e,f}}（）5.判断下列命题的对错：（1）数的相等关系是任何数集上的等价关系。（）（2）一群人的集合中姓氏相同的关系也是等价关系。（）（3）父子关系是等价关系。（）6.设X={a,b,c},Y={0,1},X×Y={a,0,b,0,c,0,a,1,b,1,c,1，X×Y有（）个可能的子集，其中有（）个子集为从X到Y的映射，从Y到X有（）个不同的映射。7.若┐P→┐Q的值为0，则P的值为，Q的值为。答案：一、单项选择题（60分，共20题，每小题3分）1.C2.C3.B4.C5.C6.A7.B8.C9.A10.A11.B12.A13.C14.A15.C16.C17.D18.B19.D20.C二、判断题（12分，共6题，每小题2分）1.√2.√3.×4.√5.√6.√三、填空题（28分，共7题，每小题4分）1.参考答案：¬∃x(F(x)∧¬G(x))或∀x(F(x)→G(x))解题方案：评分标准：2.参考答案：正确正确不正确正确解题方案：评分标准：3.参考答案：1解题方案：评分标准：4.参考答案：（1）不是（2）不是（3）不是（4）是解题方案：评分标准：5.参考答案：（1）正确（2）正确（3）错误解题方案：父子关系不是等价关系，因为它不可传递。评分标准：6.参考答案：2^62^33^2解题方案：评分标准：7.参考答案：01解题方案：评分标准：