南昌大学 离散数学 期末试卷

《南昌大学 离散数学 期末试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2004～2005第一学期考试卷《离散数学》课程闭卷　课程类别：必修考试时间　序号一二三四五六七八九十总　分得分评卷人一、单项选择题(本大题共10小题，每小题2分，共20分)1.下列不是命题的是[C]。A.7能被3整除.B.5是素数当且仅当太阳从西边升起.C.x加7小于0.D.华东交通大学位于南昌北区. 2.设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为[  A]。    A.p→q                  B.Øp→qC.Øq→p                D.q→p 3.下面4个推理定律

2、中，不正确的为[  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.下列四个命题中哪一个为真？  [的]。    A.Æ∈Æ  B.Æ∈{a}C.Æ∈{

3、{Æ}}  D.ÆÍÆ 6.设S={a,b,c,d}，R={,,}，则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.设集合关于普通数的乘法，不正确的有[]。A.结合律成立B.有幺元C.任意元素有逆元D.交换律成立9.设A是非空集合，P(A)是A的幂集，∩是集合交运算，则代数系统〈P(A),∩〉

4、的幺元是[A]。A.P(A)B.φC.AD.E10.下列四组数据中，不能成为任何4阶无向简单图的度数序列的为[B  ]。  A.2,2,2,2                B.1,1,1,3    C.  1,1,2,3             D.1,2,2,3二、填空题（本题共10小题，每小题2分，共20分）1.命题公式p→q的真值为假，当且仅当___p=1,q=0______________。2.公式p→(q→r)在联结词全功能集{Ø，Ù，Ú}中等值形式之一为____________________。3.谓词公式Ø"xF(x)®$yG(y)的前束范

5、式为。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”的真值为____1_______。9.无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为_

6、____偶数_______。10.设树T有m个顶点，n条边，则T中顶点与边的关系为_____m-n=1__________。三、证明下式（6×2=12分）1、判断下面推理是否正确。如果你学习，那么你离散数学不会不及格。如果你不热衷于玩游戏，那么你将学习。但你离散数学不及格。因此你热衷于玩游戏。2、在一阶谓词逻辑中构造下面推理的证明。  前提：$xF(x),"x(F(x)∨G(x)→H(x))  结论：$xH(x)四、用等值演算法求公式((p∨q)∧(p→q))↔(q→p)的主合取范式与主析取范式。（10分）五、设R1和R2是集合X={0,1,2,3,4}上的

7、关系，R1={

8、y=2x}，R2={

9、x=y+1}写出R1、R2，写出R2的关系矩阵，并求出R1°R2。（8分）六、设集合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有。证明：是一个群。（10分）八、平面图G有两个连通分支，其顶点数为12，边数为34，问G有多少个面？（6分）九、对下图，（1

10、）求其邻接矩阵；（2）长度小于3的通路和回路的总数。