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

1、- -南昌大学科技学院20112012学年第一学期期末考试试卷试卷编号：(B)卷课程编号：课程名称：离散数学考试形式:闭卷适用班级：姓名：学号：班级：学院：专业：考试日期：题号-一一-二二三四五六七八九十总分累分人题名得分考生注意事项：1.本试卷共旦页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2.考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、填空题(每小题3分，本题共15分)1设R是集合A上的相容关系，则R所具有的关系的二个特性是设命题公式G=(PTQ),(QTR)T(PTR)，则公式G的类型为。设A,B是集合，且A=0,1,2,B=a,b，

2、则A到B上的全域关系AxB=有限图G是树的一个等价定义是：.设K6是有6个点的完全图，则K6有条边。二、选择题(每小题3分，本题共15分)1在由3个元素组成的集合上，它的幂集有()个元素。(A)3(B)8(C)9(D)5122设R为实数集合，映射：RTR,(x)=2x+h则Q是().(A)入射而非满射(B)满射而非入射(C)双射(D)既不是入射也不是满射.3设命题公式G=(P,Q),HQ,p，则G与H的关系是()。(A)GnH(B)HnG(C)G=H(D)以上都不是.4已知命题GP(QR)，则所有使G取真值为1的解释是()。(A)(0,0,0),(0,0,1),(1,0,0);(B)(0,1,

3、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，卩(aa)卩b)卩(ba)卩(bb)，则在解释I1010下取真值的公式是().(A)3xVyP(x,y).(B)VxVyP(x,y).(C)VxP(x,x).(D)Vx3yP(x,y).三、计算题(共4*12分)设集合A=1,2,3，A上的关系R=(1,1),(1,2),(1,3),(2,2),(3,2),(3,3),画出R的关系图；写出Rc的关系矩阵.求关系R的传递闭包t(R)。画出下图G的最小生成树；将图G中所有

4、边的权值改成1得到的图记为G，0求G的邻接矩阵。3.求A=(pq)r的主析取范式和主合取范式.设一阶逻辑公式G，(Vx)(Vy)(z)(p(x,z)p(y,z)(u)q(x,y,u).试将G化成与其等价的前束范式。四证明题(共22分)1、(本题10分)若XxX，YxY，则X二Y.2、(本题12分)甲、乙、丙、丁四人参加拳击比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以如果丙获胜，则丁不失败。请用推理方法，证明有效结20042005第一学期考试卷离散数学课程闭卷课程类别：必修考试时间序号一一二三四五六七八九十总分得分评卷人、单项选择题(本大题共10小题，每小题

5、2分，共20分)1.下列不是命题的是。A.7能被3整除.5是素数当且仅当太阳从西边升起.x加7小于0.D.华东交通大学位于南昌北区.设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为。A.pqB.pqC.qpD.qp下面4个推理定律中，不正确的为。A.A=(AVB)(附加律)B(AVB)AA=B(析取三段论)C(AB)AA=B(假言推理)D(AB)AB=A(拒取式)设解释I如下，个体域D=1,2,F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1在解释I下,下列公式中真值为1的是。A.Vx,yF(x,y)B.,xVyF(x,y)C.V

6、xVyF(x,y)D.,x,yF(x,y)下列四个命题中哪一个为真？。- - -A.eB.$aC.$D.匸设S=a,b,c,d,R=va,a,vb,b,vd,d,则R的性质是。A自反、对称、传递的B.对称、反对称、传递的C自反、对称、反对称的D.只有对称性设A=a,b,c,贝V下列是集合A的划分的是。A.b,c,cBa,b,a,cC.a,b,cDa,b,c8设集合(2)a+b2a,b,Q)关于普通数的乘法，不正确的有。A.结合律成立B.有幺元C任意元素有逆元D.交换律成立设A是非空集合,P(A)是A的幂集，G是集合交运算，则代数系统P(A),G的幺元是。AP(A)BCAD.E10下列四组数据中

7、，不能成为任何4阶无向简单图的度数序列的为。A2,2,2,2B.1,1,1,3C1,1,2,3D.1,2,2,3二、填空题(本题共10小题，每小题2分，共20分)TOC o 1-5 h z命题公式pq的真值为假，当且仅当。公式pf(qr)在联结词全功能集，a，中等值形式之一为。G(y)的前束范式为。设集合A=1，4，B=2，4，则P(A)-P(B)=。R是非空集合上的偏序关系，当且仅当R具有。6设函数f(x)=x+1,g(x)=2x2,贝Vfog=。7.设=(134)(256),t=(25)(1643),则ot=。8命题“设G为任意的n阶简单的哈密尔图，贝OVu,veV(G),均有d(u)+d

8、(v)2n”的真值为无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为设树T有m个顶点，n条边，则T中顶点与边的关系为。三、证明下式(6X2=12分)1、判断下面推理是否正确。如果你学习，那么你离散数学不会不及格。如果你不热衷于玩游戏，那么你将学习。但你离散数学不及格。因此你热衷于玩游戏2、在一阶谓词逻辑中构造下面推理的证明。前提：xF(x)，Vx(F(x)VG(x)H(x)结论：xH(x)3.谓词公式，VxF(x)Ty四、用等值演算法求公式(pVq)人(pq)(qp)的主合取范式与主析取范式。(10分)五、设R1和R2是集合X=0,1,2,3,4上的关系，R1=|y=2x，R2=|x=y

9、+1写出叫、R2，写出R2的关系矩阵，并求出R1R2o(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，yZ有x*y=x,y-2。证明：vZ,*是一个群。（10分）八、平面图G有两个连通分支，其顶点数为12,边数为34,问G有多少个面?（6分）九、对下图,1）求其邻接矩阵；（2）长度小于3的通路和回路的总数。（6分）v520042005第一学期补考试卷离散数学课程

10、闭卷课程类别：必修考试时间序号一一二三四五六七八九十总分得分评卷人一、单项选择题(本大题共10小题，每小题2分，共20分)1.下列不是命题的是。学生要努力学习.5是素数当且仅当太阳从西边升起.x70.D.7能被3整除.2.与命题pV(qAp)等值的公式是。A.pB.qC.pVqD.pAq3使命题公式pf(pAq)为假的赋值是p,q分别为。A.(0,0)B.(0,1)C.(1,0)D.(1,1)在命题逻辑中,任何命题公式的主析取范式都。A.存在且唯一B.存在但不唯一C.不一定存在D.不存在对于任意集合A、B,A包含于B当且仅当A-B=0是。A假命题B真命题C是一阶公式但不是命题D.均不属于A、B

11、、C设S=1,2,3,4,R=v1,1,v2,2,v3,3,则R的性质是A自反、对称、传递的B自反、对称、反对称的C对称、反对称、传递的D.只有对称性- - -7设A=a,b,c，则下列是集合A的划分的是。A.b,c,cBa,c,b,cC.a,c,bDa,c,b下述*运算为实数集上的运算，其中可交换且可结合的运算是Aa*b=a+2bBa*b=a+b-abCa*b=aDa*b=la+bl无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为。A不同B.相同C.奇数D.偶数10下列四组数据中，不能成为任何4阶无向简单图的度数序列的为。A.2,2,2,2B.2,2,2,3C.1,1,1,3D.1,2

12、,2,3二、将下列命题符号化(4*2=8分)1、除非你认真复习，否则你将不及格2、张三和李四都是学生三、证明下面的式子(8X2=16分)1.用附加前提证明法证明下面的推理。前提：p，qr，q(ps)结论：rs2、在一阶谓词逻辑中构造下面推理的证明。前提：Vx(G(x)VF(x)M(x)，,xG(x)结论：,xM(x)四、A，B，C是集合，证明An（B-C）=（A-C）n（B-C）（10分）五、求公式（xF（x，y）T,yG（y）TxH（x，y）的前束范式。（6分）六、设R和R2是集合X=0,1,2,3,4上的关系，R1=|y=x+1，R2=|y=x2写出叫、R2，写出R2的关系矩阵，并求出R1

13、R2o（10分）七、集合a,b,c,d上的二元运算*的运算表如下：*abcdaabcdbbbbbccbcaddbaa（1）判断*是否是可结合的、可交换的？（2）指出关于*的幺元、零元、幂等元。（3）哪些元素有逆元？逆元是什么？（12分）八、设X是实数的乘法运算，Z为整数集合，x,yeZ，在Z上定义二元运算*：x*y=x+y-2，利用群的定义证明：vZ,*是一个群。（10分）九、已知平面图G有三个连通分支，其顶点数为21，边数为33,问G有多少个面？（8分）20042005学年第1学期试卷一、判断题：(10分，在括号内划“丿”或“X”)()1“如果太阳从西边出来，则2+2=4”，此命题值为假。(

14、)2(1,3,3,3)可以成为无向简单图的度数序列。()3.有一个函数f：XtY,若f具有反函数，则f一定是单射。()4.(PaQ)(P,Q)是永真式。()5在某集合上二元运算中，若某元素存在左右逆元，则该元素逆元唯()6.命题公式的主析取范式为0，则其主合取范式为1。()7.有向图的关联矩阵中所有元素之和为该图度之和。()8.初级回路一定是简单回路。()9若关系R具有自反性，则一定不具有反自反性。()10.Vx(A(x)yH(x,y)在具体的解释中其值是确定的。二、填空(共30分)TOC o 1-5 h z设A=1,2,P(A)表示A的幂集，则P(A)A=。在一阶逻辑中符号化命题:“所有的人

15、都是要死的”(只能用存在量词)P(x)VyR(x,y)的前束范式是：n阶有向完全图中所有顶点的度数之和为已知从A至【A/R的函数g:AtA/R为自然映射，A=1,2,3,R=EA,则g(1)=。设函数f(x)=2x+1,g(x)=x2-2,贝Ufog=。Klein四元群的运算表如下，其有个子群。TOC o 1-5 h zeabceeabcaaecbbbceaccbae8R,+为代数系统，给定bez,令函数f：RfR,且f(x)=bx,当b满足时，f是R,+的自同构。9.若IP(AUB)I=256,IP(A)I=64,IB1=3,贝VIABl=。10下图为无向图，并且是平面图，画出它的一种平面嵌

16、入。V2V3V4三、(6分)设A、B、C为任意集合，证明：(AUBUC)n(AUB)-(AU(B-C)HA)=B-A四、(8分)求(，pAq)Tr的主合取范式、主析取范式以及成假赋值。五、(8分)设Z为整数，在Z上定义二元运算，对任意的x,yeZ,定义:xAy二x+y+10证明：Z,是群。六、（8分）在一阶逻辑自然推理系统中，构造下面推理的证明。个体域是人的集合。“每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车，有的人不喜欢骑自行车。因而有的人不喜欢步行。”七、（10分）设集合A=1,2,3,4上的二元关系R1与R2定义如下:R1=,，R2=,，1）写出R1的关系矩阵，并判断R1具有哪些性质？2）求出R1oR23）画出t（R2）的关系图。