离散数学期末考试试题(配答案)

广东工业师范大学模拟试题主题：离散数学考试形式：闭卷考试时间： 120分钟部门、班级：姓名：学生编号：一、填空(每题2分，共10分)1.谓词公式的前束范式是_ _ xyp(x)q(y)_ _ _ _ _ _ _ _ _。2.设置完整的集合规则A ; B=_ 2 _，_ 4，5 _，_ 1，3，4，5 _3.假设，然后_ _ c、a，c、b，c、a，b，c _ _ _ _ _ _ _、_ _ _ _ _ _ _ _ _ _ _。4.在代数系统(n)中，单位元素是0，只有_ 1 _ _有逆元素。5.如果一个平面连通图G有一个顶点和一条边，那么G有_ _ _ E2-N _ _ _个面。二。选择题(每题2分，共10分)1.这个公式等价于命题公式是()(甲)(乙)(丙)(丁)2.建立一个集合，A上的二元关系不具有关系()的性质(甲)(甲)传递性(乙)反对称性(丙)对称性(丁)自反性3.在图中，节点的总度数和边数之间的关系是()(甲)(乙)(丙)(丁)4.假设D是一个有N个节点的有向完全图，那么图D的边数是()(甲)(乙)(丙)(丁)5.无向图G是欧拉图，当且仅当()(a)g的所有节点的度是偶数(b)g的所有节点的度是奇数G是连通的，所有节点的度数都是偶数；G是连通的，所有节点的度数都是奇数。三。计算题(共43分)1.寻找命题公式的主合取范式和主析取范式。(6分)解决方案：主连接模式：pqr(pqr)pqr)pqr=0 . 2 . 4主析取范式：pqr(pqr)(pqr)(pqr)(pqr)(pqr)=1 . 3 . 5 . 6 . 72.将集合上二元关系R的关系矩阵设置为的关系矩阵，并画出关系图。(10分)3-无向图G有12条边，G中有6个3度节点，其他节点的度小于3。G中有多少个节点？(10分)解：g (v，E)，| E |=V，d(Vi)3，假设至少有x个节点。根据握手定理：212=d(Vi)63 (x-6)32(x-6)= x8因此，G至少有9个节点。4找到下面两幅图的最小生成树。(12分)5.试着判断它是否合格？给出理由。(5分)解决方案：(Z，)是一个格，原因如下：对于任何aZ，aa成立并满足自反性；对于任何aZ，bZ，如果ab且ba，则a=b满足反对称；对于任意a，b，cZ，如果ab，bc，ac满足传递性；对于任何a，bZ，ab，b是最小上界，a是最大下界，所以(Z，)是一个格。(注意：什么是格子？)四.证明(共37分)1.用推理规则证明。(10分)证据：数字公式基础(1)(bc)c前提(2)BC，C(1)(3)B(2)(4)AB(3)(5)甲(3)(4)(6)前提(7)AD(6)(8)D(5)(6)2.让R是一组实数。验证：所有都是完整的镜头，但不是单个镜头。(10分)证明了如果F是满射的，即Y R，则存在(x1，x2)RR，因此f(x1，x2)=y，f(x1，x2)=x1 x2，x1=0，x2=y，然后证明了。重新证明g是满射的，即y r，都存在(x1，x2)RR，因此g(x1，x2)=y，而g(x1，x2)=x1x2，x1=1，x2=y，是证明。最后的证明是f不是单射，f(x1，x2)=f(x2，x1)通过取x1x2来证明。类似地，证明了g(x1，x2)=g(x2，x1)和x1x2。3.无向图G有9个节点，每个节点的度数为5或6。验证：G至少有5个6度节点或6个5度节点。(10分)证明了如果G至多有4个6度节点和5个5度节点，d(Vi)=49甚至不是，因此，它不是一个数字或矛盾。(以下仅供参考，个人答案)4.让飞机上有100个点。如果周期中任意两点之间的距离至少为1，则300点之间的距离最多正好为1。(7分)证明：如果任意两