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

第1页（共3页）《离散数学》期末考试试题一、填空题（每空2分，合计20分）1.设个体域为{2,3,6}D,():3Fxx，():0Gxx。则在此解释下公式()(()())xFxGx的真值为______。2.设:p我是大学生，:q我喜欢数学。命题“我是喜欢数学的大学生”为可符合化为。3.设{1,2,3,4}A，{2,4,6}B，则AB=________，AB=________。4.合式公式()QPP是永______式。5.给定集合{1,2,3,4,5}A，在集合A上定义两种关系：{1,3,3,4,2,2}R,{4,2,3,1,2,3}S，则_______________SR，_______________RS。6.设e是群G上的幺元，若aG且2ae,则1a=____,2a=__________。7．公式))(()(SQPQP的对偶公式为。8.设{2,3,6,12}A,是A上的整除关系，则偏序集,A的最大元是________，极小元是__。9.一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。10.设图,GVE,1234{v,v,v,v}V，若G的邻接矩阵0001001111011010A，则1()degv=________,4()degv=____________。二、选择题（每题2分，合计20分）1．下列各式中哪个不成立（）。A、)()())()((xxQxxPxQxPx；B、)()())()((xxQxxPxQxPx；C、)()())()((xxQxxPxQxPx；D、QxxPQxPx)())((。第2页（共3页）2．谓词公式)())()((xQyyRxPx中的x是（）。A、自由变元；B、约束变元；C、既是自由变元又是约束变元；D、既不是自由变元又不是约束变元。3．集合的以下运算律不成立．．．的是()。A．ABBAB．ABBAC．ABBAD．ABBA4.公式),()),(),((yxxPzyQyxPyx换名（）。A.),()),(),((yxxPzuQuxPuxB.),()),(),((uxxPzuQuxPyxC.),()),(),((uxxPzyQyxPyxD.),()),(),((yuuPzyQyuPyu。5.设集合A，B是有穷集合，且nBmA,，则从A到B有（）个不同的双射函数。A、n；B、m；C、!n；D、!m。6．设{,,,}Aabcd，A上的等价关系{,,,,,,,}Rabbacddc，则对应于R的A的划分是（）A．{{},{,},{}}abcdB．{{,},{},{}}abcdC．{{},{},{},{}}abcdD．{{,},{,}}abcd7.设{1,2,3,4}A，则A上的二元关系有（）个。A．42B.24C．442D．2248．下面集合（）关于减法运算是封闭的。A、N；B、}2{Ixx；C、}12{Ixx；D、}{是质数xx。9.设集合{0,1,2,3}X，R是X上的二元关系，{0,0,0,2,1,2,1,3,2,0,2,1,3,3}R，则R的关系矩阵MR是()第3页（共3页）A．1100100000110101B.1000001111000101C.0111101001011000D.010110001100011110．一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条()A.汉密尔顿回路B.欧拉回路C.汉密尔顿通路D.初级回路三、计算题（每题8分合计40分）1．写出命题公式()()pqpq的真值表。2．集合}36,24,12,6,3,2{A上的偏序关系|为整除关系。设}12,6{B，}6,3,2{C，试画出A,|的哈斯图，并求集合B和C中关于|的极大元、最大元、下界和下确界。3.求命题公式()()PQPR的主析取范式。4.求下图所示的边赋权图的一棵最小生成树。5.已知某有向图的邻接矩阵如下：12340010001111010111vvAvv试求：3v到1v的长度为4的有向路径的条数。四证明题（每题10分，合计20分）1.设论域D为全总个体域，谓词G(x)：x是研究生，T(x)：x是推荐免试者，K(x)：x是统考选拔者。在谓词逻辑中符号化下列各命题，推证结论的有效性。“所有的研究生或者是推荐免试者或者是统考选拔者；并非所有的研究生都是推荐免试者。结论：有些研究生是统考选拔者。”2.,*G是一个群,uG，定义G中的运算“”为*1*abaub，对任意,abG，求证：,G也是个群。