历年离散数学试卷选编(参考答案)

历年离散数学试卷选编（参考答案）目录试卷一..................................................................................................................1试卷二..................................................................................................................5试卷三.................................................................................................................10试卷四.................................................................................................................16试卷五.................................................................................................................19试卷六.................................................................................................................24试卷七.................................................................................................................27试卷八.................................................................................................................31试卷一一、单项选择题(本大题共10小题，每小题2分，共20分)1.下列不是命题的是[C]。A.7能被3整除.B.5是素数当且仅当太阳从西边升起.C.x加7小于0.D.华东交通大学位于南昌北区.2.设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为[D]。A.p→qB.p→qC.q→pD.q→p读书是掌握知识的捷径，勤奋是开启知识大门的钥匙，思考是理解知识的利器，练习是巩固知识的方法，讨论是理解知识的妙招，探求是创新知识的途径。3.下面4个推理定律中，不正确的为[D]。A.A=(A∨B)(附加律)B.(A∨B)∧A=B(析取三段论)C.(A→B)∧A=B(假言推理)D.(A→B)∧B=A(拒取式)4.设解释I如下，个体域D={1,2},F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1，在解释I下，下列公式中真值为1的是[A]。A.xyF(x,y)B.xyF(x,y)C.xyF(x,y)D.xyF(x,y)5.下列四个命题中哪一个为真？[D]。A.∈B.∈{a}C.∈{{}}D.6.设S={a,b,c,d}，R={a,a,b,b,d,d}，则R的性质是[B]。A.自反、对称、传递的B.对称、反对称、传递的C.自反、对称、反对称的D.只有对称性7.设A={a,b,c}，则下列是集合A的划分的是[D]。A.{{b,c},{c}}B.{{a,b},{a,c}}C.{{a,b},c}D.{{a},{b,c}}8.设集合}),2{)2(QbabaQ关于普通数的乘法，不正确的有[C]。A.结合律成立B.有幺元C.任意元素有逆元D.交换律成立9.设A是非空集合，P(A)是A的幂集，∩是集合交运算，则代数系统〈P(A),∩〉的幺元是[C]。A.P(A)B.φC.AD.E10.下列四组数据中，不能成为任何4阶无向简单图的度数序列的为[C]。A.2,2,2,2B.1,1,1,3C.1,1,2,3D.1,2,2,3二、填空题（本题共10小题，每小题2分，共20分）1.命题公式p→q的真值为假，当且仅当_p=1,q=0__。2.公式p→(q→r)在联结词全功能集{，，}中等值形式之一为pqr。3.谓词公式xF(x)xG(x)的前束范式为xy(F(x)G(y))。4.设集合A={1，4}，B={2，4}，则P(A)-P(B)={{1},{1,4}}。5.R是非空集合上的偏序关系，当且仅当R具有自反性、反对称性、传递性。6.设函数f(x)=x+1,g(x)=2x2,则fog=2x2_+1_。7.设σ=(134)(256)，τ=(25)(1643)，则στ=(1)(2)(3)(465)。8.命题“设G为任意的n阶简单的哈密尔图，则u，v∈V(G)，均有d(u)+d(v)≥n”的真值为__0__。9.无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为__偶数___。10.设树T有m个顶点，n条边，则T中顶点与边的关系为__m=n+1__。三、证明下式（6×2=12分）1、判断下面推理是否正确。如果你学习，那么你离散数学不会不及格。如果你不热衷于玩游戏，那么你将学习。但你离散数学不及格。因此你热衷于玩游戏。设p:你学习，q:你离散数学及格，r:你热衷于玩游戏，则前提：pq，rp，q结论：r证明：①pq前提引入②q前提引入③p①②拒取式④rp前提引入⑤(r)③④拒取式⑥r⑤置换2、在一阶谓词逻辑中构造下面推理的证明。前提：xF(x),x(F(x)∨G(x)→H(x))结论：xH(x)证明：①xF(x)前提引入②F(a)①-③x(F(x)∨G(x)→H(x))前提引入④F(a)∨G(a)→H(a)③-⑤F(a)∨G(a)②附加⑥H(a)④⑤假言推理⑦xH(x)⑥+四、用等值演算法求公式((p∨q)∧(p→q))↔(q→p)的主合取范式与主析取范式。（10分）解：原式((p∨q)∧(p∨q))↔(q→p)((p∧p)∨q)↔(q→p)q↔(q→p)(q→(q→p))∧((q→p)→q)(q∨(q∨p))∧((q∨p)∨q)(q∨p)∧((q∧p)∨q)(q∨p)∧qp∧q(3)--------------主合取范式(0,1,2)--------------主析取范式五、设R1和R2是集合X={0,1,2,3,4}上的关系，R1={x,y|y=2x}，R2={x,y|x=y+1}写出R1、R2，写出R2的关系矩阵，并求出R1R2。（8分）解：R1={0,0,1,2,2,4},R2={1,0,1,2,2,3,3,4},R2的关系矩阵：（略）R1R2={x,y|y=2(x-1)}六、设集合A={2,3,4,6,8,12,24}，R为A上的整除关系，(1)画出偏序集A，R的哈斯图；(2)出集合A中的最大元、最小元、极大元、极小元；（3）写出A的子集B={2,3,6,12}的上界、下界、最小上界、最大下界。（8分）解：(1)哈斯图：(2)A中的最大元：24，最小元：无，极大元：24，极小元：2、3(3)B={2,3,6,12}的上界：12、24，下界：无，最小上界：12，最大下界：无七、设Z为整数集合，在Z上定义二元运算*，x,y∈Z有2*yxyx。证明：Z，*是一个群。（10分）证明：显然，二元运算*满足交换律。(1)封闭性：x,y∈Z，显然2*yxyx∈Z。(2)结合律：x,y,z∈Z,342681224(x*y)*z=(x+y-2)*z=x+y-2+z-2=x+y+z-4x*(y*z)=x*(y+z-2)=x+y+z-2-2=x+y+z-4(x*y)*z=x*(y*z)故二元运算*满足结合律。(3)设e∈Z,x∈Z，使得x*e=x，即x+e-2=x,e=2，故幺元e=2.(4)x∈Z,设y∈Z，使得x*y=e，即x+y-2=2，y=4-x，故x-1=4-x。综上所述，Z，*是一个群。八、平面图G有两个连通分支，其顶点数为12，边数为34，问G有多少个面？（6分）解：设有x个面，根据欧拉公式：12-34+x=2+1，即x=25所以，G有25个面。九、对下图，（1）求其邻接矩阵；（2）（2）长度小于3的通路和回路的总数。(6分)V2v1v5v3v4解题思路：先写出邻接矩阵A，然后求A2，则矩阵A+A2中元素之和，即为长度小于3的通路条数【10条】；而A+A2对角线上元素之和，即为长度小于3的回路条数【0条】。大学是一个人的精神账户，你一辈子都要不断回来提款的。试卷二一、单项选择题（2分×10=20分）1、下列语句是命题的有[B]。A.122yx；B.2010年的国庆节是晴天；C.青年学生多么朝气蓬勃呀！D.学生不准吸烟!2、在命题逻辑中，任何命题公式的主合取范式都[C]。A.不一定存在;B.不存在；C.存在且唯一;D.存在但不唯一.3、设S={1,2,3,4}，R={1,1,3,3,4,4}，则R满足的性质是[C]A.自反、对称、传递的;B.自反、对称、反对称的;C.对称、反对称、传递的;D.只有对称性.4.与命题p∧(p∨q)等值的公式是[A]。A.p；B.q；C.p∨q；D.p∧q.5.设M={a,b,c}，M上的等价关系R={a,a,b,b,c,c,b,c,c,b}确定的集合M的划分是[D]。A.{{a},{b},{c}}B.{{a,c},{b,c}}C.{{a,c},{b}}D.{{a},{b,c}}6.设D：全总个体域，F（x）：x是花，M(x)：x是人，H(x,y)：x喜欢y，则命题“每个人都喜欢某种花”的逻辑符号化为[C]。A.)),()(()((yxHyFyxMx；B.)),()(()((yxHyFyxMx；C.)),()(()((yxHyFyxMx；D.)),()(()((yxHyFyxMx.7.下列图中，不是哈密顿图的为[A]。ABCD8.下列四组数据中，能作为某个4阶无向简单图的度序列的为[D]。A.1,2,3,4；B.2,2,2,3；C.1,1,2,3；D.1,1,1,3.9.一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有[C]片树叶。A.3；B.4；C.5；D.6.10.下面偏序集[B]能构成格。ABCD二、填空题（2分×10=20分）1.当p=0,q=0时，命题公式p→(p∧q)的真值为1。2.设p:我努力学习，q:我取得好成绩，命题“除非我努力学习，否则我不能取得好成绩。”的符号化形式为q→p。3.设解释I如下，个体域D={1,2},F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1，在解释I下，xF(x,2)的真值为1。4.谓词公式xF(x)∧xG(x)的前束范式为xy(F(x)∧G(y))。5.设树T有n个顶点，m条边，则T中n与m的关系为m=__n-1__。6.等价关系满足自反性、对称性和传递性三个性质。7.设函数f(x)=2x，g(x)=x2+1,则fog=___2x2+_2__。8.无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为偶数。9.设|A|=3，则A上有29个二元关系。10.设A为非空有限集，则代数系统),(AP中的幺元为。三、综合题（第1、2、4题10分，第3、5、7每题8分，第6题6分，共60分）1.构造下面推理的证明：（10分）前提：p→(qr)，s→r，p