《离散数学》期末考试试题

第第3页（共3页）第第2页（共3页）第第1页(共3页)《离散数学》期末考试试题一、填空题(每空2分，合计20分).设个体域为D={—2,3,6},F(x):x<3,G(x):x>0。则在此解释下公式(Vx)(F(x)△G(x))的真值为。.设p：我是大学生，q：我喜欢数学。命题“我是喜欢数学的大学生"为可符合化为。.设A={1,2,3,4},B={2,4,6}，则A—B=,A㊉B=。.合式公式-<0—P)八P是永式。5。给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={<1,3>,<3,4>,<2,2>}，S={<4,2>,<3,1>,<2,3>}，贝IR°S=，SoR=。6。设e是群G上的幺元，若aeG且a2=e，则a-1=—,a-2=。.公式」(PvQ)△(Pv-(Q△-S))的对偶公式为..设A={2,3,6,12},Y是A上的整除关系，则偏序集<A,Y>的最大元是 ,极小元是.9。一棵有6个叶结点的完全二叉树，有个内点;而若一棵树有2个结点度数为2,一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有 个叶结点.10。设图G10。设图G=<丫,E>,V={V1,v2,V3,v4}，若G的邻接矩阵A=0111101011100，000贝Udeg-(v1)=,deg+(v4)=二、选择题(每题2分,合计20分).下列各式中哪个不成立().A、Vx(P(x)vQ(x))oVxP(x)vVxQ(x)；B、3x(P(x)vQ(x))o3xP(x)v3xQ(x)；C、Vx(P(x)△Q(x))oVxP(x)aVxQ(x)；D、Vx(P(x)aQ)oVxP(x)aQ..谓词公式V武P(x)v3yR(y))-Q(x)中的x是()。人、自由变元； B、约束变元；C、既是自由变元又是约束变元;D、既不是自由变元又不是约束变元。．．．.集合的以下运算律不成立的是( )。A.AQB^B^A b.AUB^B]JACA㊉B=B㊉A D.A-B=B-A.公式VxVy(P(x,y)vQ(y,工))a3xP(x,y)换名()。VxVu(P(x,u)vQ(u,z))a3xP(x,y)VxVy(P(x,u)vQ(u,z))a3xP(x,u)VxVy(P(x,y)vQ(y,z))a3xP(x,u)VuVy(P(u,y)vQ(y,z))a3uP(u,y).5。设集合A,B是有穷集合，且囿二m,|B|=n，则从A到B有()个不同的双射函数.A、n；B、m；C、n!; D、m!。.设A={a,b,c,d},A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>},则对应于R的A的划分是()A.{{a},{b,c},{d}} B.{{a,b},{c},{d}}C.{{a},{b},{c},{d}} D.{{a,b},{c,d}}.设A={1,2,3,4}，则A上的二元关系有()个。A.24 B。42 C.2公4D.42x2.下面集合()关于减法运算是封闭的.A、N;B、{2x|xeI}；C、{2x+11xeI}； d、{x|x是质数}。。设集合X={0,1,2,3},R是X上的二元关系，R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3>},则R的关系矩阵Mr是R( )

A.Co10101010B.000110100101A.Co10101010B.0001101001011110Do1110001100011010.一个连通的无向图G,如果它的所有结点的度数都是偶数，那么它具有一条（ ）A.汉密尔顿回路 Bo欧拉回路 C.汉密尔顿通路 D.初级回路三、计算题（每题8分合计40分）.写出命题公式「5-幻的真值表..集合A={2,3,6,12,24,36}上的偏序关系I为整除关系。设5二{6,12},。二{2,3,6},试画出〈A,|＞的哈斯图，并求集合5和。中关于|的极大元、最大元、下界和下确界。3o求命题公式「（尸a。）。」（「尸'R）的主析取范式。4O求下图所示的边赋权图的一棵最小生成树。5。已知某有向图的邻接矩阵如下:V1V2v5。已知某有向图的邻接矩阵如下:V1V2v3V4001110、110111)试求：V3到V1的长度为4的有向路径的条数。四证明题（每题10分，合计20分）.设论域D为全总个体域，谓词G（x）：x是研究生,T（x）:x是推荐免试者，K（x）：x是统考选拔者。在谓词逻辑中符号化下列各命题,推证结论的有效性。“所有的研究生或者是推荐免试者或者是统考