南昌大学《离散数学》考试试卷

-1-南昌大学科技学院2011～2012学年第一学期期末考试试卷2.考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、填空题(每小题3分，本题共15分)1设R是集合A上的相容关系，则R所具有的关系的二个特性是_______________________________________________________.2.设命题公式(()())()GPQQRPR，则公式G的类型为_______________。3.设A,B是集合，且A={0,1,2},B={a,b}，则A到B上的全域关系AB=_____________________________________________________.4.有限图G是树的一个等价定义是：______________________________________.5.设K6是有6个点的完全图，则K6有____________条边。二、选择题(每小题3分，本题共15分)1在由3个元素组成的集合上，它的幂集有()个元素。(A)3(B)8(C)9(D)5122设R为实数集合，映射:,RR()21,xx则是().(A)入射而非满射(B)满射而非入射(C)双射(D)既不是入射也不是满射.试卷编号：(B)卷课程编号：课程名称：离散数学考试形式：闭卷适用班级：姓名：学号：班级：学院：专业：考试日期：题号一二三四五六七八九十总分累分人签名题分15154822100得分考生注意事项：1.本试卷共5页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。-2-3设命题公式()GPQ，HQP，则G与H的关系是()。(A)GH(B)HG(C)GH(D)以上都不是.4已知命题()GPQR，则所有使G取真值为1的解释是()。(A)(0,0,0),(0,0,1),(1,0,0);(B)(0,1,0),(1,0,1),(1,1,0);(C)(1,0,0),(1,0,1),(1,1,0);(D)(1,1,0),(1,0,1),(1,1,1).5设I是如下一个解释：D={a,b}，(,)(,)(,)(,)1010PaaPabPbaPbb，则在解释I下取真值的公式是().(A)(,)xyPxy.(B)(,)xyPxy.(C)(,)xPxx.(D)(,)xyPxy.三、计算题(共4*12分)1.设集合A＝{1,2,3}，A上的关系R＝{(1,1),(1,2),(1,3),(2,2),(3,2),(3,3)},(1)画出R的关系图；(2)写出Rc的关系矩阵.(3)求关系R的传递闭包t(R)。2.画出下图G的最小生成树；将图G中所有边的权值改成1得到的图记为0G，求0G的邻接矩阵。A142241631892BCDEFG-3-3.求A=(pq)r的主析取范式和主合取范式.4.设一阶逻辑公式()()(()((,)(,))()(,,)).Gxyzpxzpyzuqxyu试将G化成与其等价的前束范式。四证明题(共22分)1、(本题10分)若XXYY，则.XY2、(本题12分)甲、乙、丙、丁四人参加拳击比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以如果丙获胜，则丁不失败。请用推理方法，证明有效结-4-2004～2005第一学期考试卷《离散数学》课程闭卷课程类别：必修考试时间序号一二三四五六七八九十总分得分评卷人一、单项选择题(本大题共10小题，每小题2分，共20分)1.下列不是命题的是[]。A.7能被3整除.B.5是素数当且仅当太阳从西边升起.C.x加7小于0.D.华东交通大学位于南昌北区.2.设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为[]。A.p→qB.p→qC.q→pD.q→p3.下面4个推理定律中，不正确的为[]。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.xyF(x,y)B.xyF(x,y)C.xyF(x,y)D.xyF(x,y)5.下列四个命题中哪一个为真？[]。专业班级学号-5-A.∈B.∈{a}C.∈{{}}D.6.设S={a,b,c,d}，R={a,a,b,b,d,d}，则R的性质是[]。A.自反、对称、传递的B.对称、反对称、传递的C.自反、对称、反对称的D.只有对称性7.设A={a,b,c}，则下列是集合A的划分的是[]。A.{{b,c},{c}}B.{{a,b},{a,c}}C.{{a,b},c}D.{{a},{b,c}}8.设集合}),2{)2(QbabaQ关于普通数的乘法，不正确的有[]。A.结合律成立B.有幺元C.任意元素有逆元D.交换律成立9.设A是非空集合，P(A)是A的幂集，∩是集合交运算，则代数系统〈P(A),∩〉的幺元是[]。A.P(A)B.φC.AD.E10.下列四组数据中，不能成为任何4阶无向简单图的度数序列的为[]。A.2,2,2,2B.1,1,1,3C.1,1,2,3D.1,2,2,3二、填空题（本题共10小题，每小题2分，共20分）1.命题公式p→q的真值为假，当且仅当_________________。2.公式p→(q→r)在联结词全功能集{，，}中等值形式之一为____________________。G(y)的前束范式为。4.设集合A={1，4}，B={2，4}，则P(A)-P(B)=________________。5.R是非空集合上的偏序关系，当且仅当R具有___________。6.设函数f(x)=x+1,g(x)=2x2,则fog=____________________。7.设σ=(134)(256)，τ=(25)(1643)，则στ=____________________。8.命题“设G为任意的n阶简单的哈密尔图，则u，v∈V(G)，均有d(u)+d(v)≥n”的真值为___________。9.无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为____________。10.设树T有m个顶点，n条边，则T中顶点与边的关系为_______________。-6-三、证明下式（6×2=12分）1、判断下面推理是否正确。如果你学习，那么你离散数学不会不及格。如果你不热衷于玩游戏，那么你将学习。但你离散数学不及格。因此你热衷于玩游戏。2、在一阶谓词逻辑中构造下面推理的证明。前提：xF(x),x(F(x)∨G(x)→H(x))结论：xH(x)3.谓词公式xF(x)y四、用等值演算法求公式((p∨q)∧(p→q))↔(q→p)的主合取范式与主析取范式。（10分）五、设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分）-7-六、设集合A={2,3,4,6,8,12,24}，R为A上的整除关系，(1)画出偏序集（A，R）的哈斯图；(2)出集合A中的最大元、最小元、极大元、极小元；（3）写出A的子集B={2,3,6,12}的上界、下界、最小上界、最大下界。（8分）七、设Z为整数集合，在Z上定义二元运算*，x,y∈Z有2*yxyx。证明：Z，*是一个群。（10分）八、平面图G有两个连通分支，其顶点数为12，边数为34，问G有多少个面？（6分）九、对下图，（1）求其邻接矩阵；（2）长度小于3的通路和回路的总数。(6分)V2v1v5v3v4-8-2004～2005第二学期补考试卷《离散数学》课程闭卷课程类别：必修考试时间序号一二三四五六七八九十总分得分评卷人一、单项选择题(本大题共10小题，每小题2分，共20分)1.下列不是命题的是[]。A.学生要努力学习.B.5是素数当且仅当太阳从西边升起.C.x－70.D.7能被3整除.2.与命题p∨(q∧p)等值的公式是[]。A.pB.qC.p∨qD.p∧q3.使命题公式p→(p∧q)为假的赋值是p，q分别为[]。A.(0,0)B.(0,1)C.(1,0)D.(1,1)4.在命题逻辑中，任何命题公式的主析取范式都[]。A.存在且唯一B.存在但不唯一C.不一定存在D.不存在5.对于任意集合A、B，A包含于B当且仅当A-B=Φ是[]。A.假命题B.真命题C.是一阶公式但不是命题D.均不属于A、B、C6.设S={1,2,3,4}，R={1,1,2,2,3,3}，则R的性质是[]A.自反、对称、传递的B.自反、对称、反对称的C.对称、反对称、传递的D.只有对称性-9-7.设A={a,b,c}，则下列是集合A的划分的是[]。A.{{b,c},{c}}B.{{a,c},{b,c}}C.{{a,c},b}D.{{a,c},{b}}8.下述*运算为实数集上的运算，其中可交换且可结合的运算是[]A.a*b=a+2bB.a*b=a+b-abC.a*b=aD.a*b=|a+b|9.无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为[]。A.不同B.C.奇数D.偶数10.下列四组数据中，不能成为任何4阶无向简单图的度数序列的为[]。A.2,2,2,2B.2,2,2,3C.1,1,1,3D.1,2,2,3二、将下列命题符号化（4*2=8分）1、除非你认真复习，否则你将不及格2、张三和李四都是学生三、证明下面的式子（8×2=16分）1.用附加前提证明法证明下面的推理。前提：p，qr，q→(p→s)结论：r→s2、在一阶谓词逻辑中构造下面推理的证明。前提：x(G(x)∨F(x)→M(x)),xG(x)结论：xM(x)-10-四、A,B,C是集合，证明A∩(B－C)=(A－C)∩(B－C)（10分）五、求公式(xF(x,y)yG(y))xH(x,y)的前束范式。（6分）六、设R1和R2是集合X={0,1,2,3,4}上的关系，R1={x,y|y=x+1}，R2={x,y|y=x2}写出R1、R2，写出R2的关系矩阵，并求出R1R2。（10分）七、集合{a,b,c,d}上的二元运算*的运算表如下：*abcdaabcdbbbbbccbcaddbaa(1)判断*是否是可结合的、可交换的？(2)指出关于*的幺元、零元、幂等元。(3)哪些元素有逆元？逆元是什么？（12分）八、设×是实数的乘法运算，Z为整数集合，x,y∈Z，在Z上定义二元运算*：x*y=x+y-2，利用群的定义证明：Z，*是一个群。（10分）九、已知平面图G有三个连通分支，其顶点数为21，边数为33，问G有多少个面？（8分）-11-2004—2005学年第1学期试卷离散数学课程课程类别：必、限、任闭卷、开卷(范围)：题号一二三四五六七八九十总分分数评卷人一、判断题：（10分，在括号内划“√”或“×”）（）1．“如果太阳从西边出来，则2+2=4”，此命题值为假。（）2．(1,3,3,3)可以成为无向简单图的度数序列。（）3．有一个函数f：XY，若f具有反函数，则f一定是单射。（）4．（PQ）（PQ）是永真式。（）5．在某集合上二元运算中，若某元素存在左右逆元，则该元素逆元唯一。（）6．命题公式的主析取范式为0，则其主合取范式为1。（）7．有向图的关联矩阵中所有元素之和为该图度之和。（）8．初级回路一定是简单回路。（）9．若关系R具有自反性，则一定不具有反自反性。（）10．x(A(x)yH(x,y))在具体的解释中其值是确定的。二、填空（共30分）1．设A={1，2}，P(A)表示A的幂集，,则P(A)A=_____________________。2．在一阶逻辑中符号化命题:“所有的人都是要死