贵州大学信息学院计算机专业2004级《离散数学》试卷A

贵州大学信息学院计算机专业2004级《离散数学》试卷A姓名学号班级得分一、判断题（每题1分，共10分）1、在命题逻辑中，任何公式都存在与之等值的主合取和主析取范式，并且是唯一。（）2、设G,是交换群，则G的所有子群是正规子群。（）3、设P,≤为偏序集，SP，若S有上界，则S必有上确界。4、设R为二元关系，A是集合，则R在A上的限制是R的子关系。（）5、图G是树则G是连通的且G中任意两顶之间有不只一条路径。（）6、对于任意非空集合A，P(A)—是A的一个划分。（）7、任给函数F，它的逆F-1一定是函数。（）8、不是封闭公式在任何解释下都变成命题。（）9、R=nZ，，〉是模n的整数环，R是整环当且仅当n是素数。（）10、非负整数列（4，4，3，3，2，2）可简单图画。（）二、填空题（每小题2分，共30分）1、设集合A={，a}，则P（A）A=。2、公式xF（x,y）→xG（x,y）等值的前束范式为。3、R是集合A上的等价关系，A={a,b,c,d}，R={a,bb,a,c,d,d,c}AI,g是集合A到集合A/R的自然映射，即g：AA/R。则g（a）=，g（d）=。4、在全总个体域中，设F（x）：x是人，G（x，y）：x与y一样高，命题“所有人都不一样高”符号化：。5、有一公式为：)qp()qp(,该公式的类型_________________。6、已知n阶无向简单图G有m条边，则G的补图G有__________条边。7、设σ=(1345)(2678)是8元置换，则σ-1=___________。8、n阶零图G的连通分支数P(G)=。9、已知f:RR,f(x)=2x+1,g:RR,g(x)=x2+3x+1,则fg=_____________;gf=_______________________。10、设代数系统V=(Q,*)，其中Q是有理数集合，*表示对x，y∈Q有x*y=x+y-xy，则Q上关于*的幺元(或称单位元)是_________。11、含n个命题变项的重言式的主合取范式为________________________。12、在命题逻辑中，设p:小明从筐中拿一个苹果，q:小明从筐中拿一个梨子，r:我去书店，则命题“如果小明只能从筐中拿一个苹果或一个梨子，那么我就去书店”的符号化形式为_______________。13、设G={e,a,b,c}是Klein四元群，H={e,b}是G的子群，则H的所有的右陪集是：。14、彼得松图（10阶3-正侧图）中，边数m=。15、根树T中，有一个顶点的入度为，其余的顶点的入度为。三、解答计算题1、求公式（（pq）批）r的主析取范式和主合取范式，并给出公式的成真赋值和成假赋值（6分）2、构造一棵权为2,2,3,4,5,6,6,7的最优二叉树并计算树的权W（T）。3、设G=a是12阶循环群。求出(1)G的所有生成元。（2）G的所有子群。4、如图示，是偏序集A,《的哈斯图。（1）该偏序集是否是格，为什么？（2）分别给出集合A和偏序关系《的集合表达式。（3）求集合A和A的子集B={a,d,e,f}的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界。（10分）5、设A={a,b,c,d,e,f}，R={a,b,a,d,e,f}是A上的关系,(1)求R′=tsr(R)。(2)R′是A上的等价关系,求A/R。（3）给出R′的关系矩阵和关系图。6、无向树T有8片树叶，2个3度的分支点，其余的分支点都是4度顶点。（1）问T有几个顶点？（2）根据T的度数列，画出2棵非同构的无向树。7、判断下列一阶公式的公式类型。)())()(()2())()((x)1(yyGyyGxxFxGxF8、设代数系统V=Z6,，Z6={0,1,...,5}，为模6乘法。(1)给出运算的运算表。(2)求出所有可逆元素关于运算的逆元。(3)说明V构成什么代数系统。（6分）四.证明题（共12分）1、在自然推理系统F中构造推理的证明：(8分)前提：))()((xHxQx，))()((xHxWx结论：))()((xQxWx2、设(G,)为循环群，生成元为a，设(A,)和(B,)均为(G,)的子群，而ai和aj分别为(A,)和(B,)的生成元。①证明(A∩B,)是(G,)的子群。②请问：(A∩B)是否为循环群。如果是，请给出其生成元。