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

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

1、《离散数学》期末考试试题一、填空题（每空2分，合计20分）1.设个体域为,，。则在此解释下公式的真值为______。2.设我是大学生，我喜欢数学。命题“我是喜欢数学的大学生”为可符合化为。3.设，，则=________，=________。4.合式公式是永______式。5.给定集合，在集合上定义两种关系：,，则，。6.设是群上的幺元，若且,则=____,=__________。7．公式的对偶公式为。8.设,是上的整除关系，则偏序集的最大元是________，极小元是__。9.一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其

2、余是叶结点，则该树有_____个叶结点。10.设图,，若G的邻接矩阵，则=________,=____________。二、选择题（每题2分，合计20分）1．下列各式中哪个不成立（）。A、；B、；C、；D、。2．谓词公式中的x是（）。A、自由变元；B、约束变元；C、既是自由变元又是约束变元；D、既不是自由变元又不是约束变元。3．集合的以下运算律不成立的是()。A．B．C．D．4.公式换名（）。A.B.C.D.。5.设集合，是有穷集合，且，则从到有（）个不同的双射函数。A、；B、；C、；D、。6．设，上的等价关系，则对应于的的划分是（　　　）A．B．C．D．7.设，则上的二元关系有（）个。A．B

3、.C．D．8．下面集合（）关于减法运算是封闭的。A、N；B、；C、；D、。9.设集合，是上的二元关系，，则的关系矩阵MR是()A．　B.C.D.10．一个连通的无向图，如果它的所有结点的度数都是偶数，那么它具有一条()A.汉密尔顿回路B.欧拉回路C.汉密尔顿通路D.初级回路三、计算题（每题8分合计40分）1．写出命题公式的真值表。2．集合上的偏序关系

4、为整除关系。设，，试画出

5、>的哈斯图，并求集合B和C中关于

6、的极大元、最大元、下界和下确界。3.求命题公式的主析取范式。4.求下图所示的边赋权图的一棵最小生成树。5.已知某有向图的邻接矩阵如下：试求：到的长度为4的有向路径的条数。四证明题（

7、每题10分，合计20分）1.设论域D为全总个体域，谓词G(x)：x是研究生，T(x)：x是推荐免试者，K(x)：x是统考选拔者。在谓词逻辑中符号化下列各命题，推证结论的有效性。“所有的研究生或者是推荐免试者或者是统考选拔者；并非所有的研究生都是推荐免试者。结论：有些研究生是统考选拔者。”2.是一个群,，定义中的运算“”为，对任意，求证：也是个群。