南 京 理 工 大 学 课 程 考 试 试 卷 答 案 及 评 分 标 准 课程名称： 离散数学 学分： 4.5 教学大纲编号： 试卷编号： A 考试方式： 闭卷 满分分值： 100 考试时间： 120 分钟 一、逻辑学（每小题 6 分，共 18 分） 1. 把下列知识表达为谓词演算公式 (7) ) ……3 分 ……3 分 2. 已知知识： 试用归结原理证明之。 答：（1）∀x(Gx →∃y Ny ∨Sx ∧Ax,y (2)∀x( Px ∧A 我,x →Ax, 我) ∀( →) 结论：∀(∀ ∧, →∃ ∧, ) 证明：（1）¬∨ （2） （3）,1 (4)¬2 ∨¬,2 (5)¬2 {2/1} {x/2} (6)¬ {x/} 3. 把函数ℎ1,2,3,5 =(3,4,11,2,25,3)化为(4,4)迭置。 答：ℎ1,2,3,5 =(43,441,141,42,244,341) 1,2,3,5 4．（8 分）已知集合A= {} ，B={1, ∅}。试求： （1）2={∅,1, ∅ ,B} ∅ , , , } （2）2×={∅, , 1, , 5. （8 分）已知 3 个任意的集合,,，试证明(∪)−(∪)⊑−。反之成立吗？如果不 证明：对于任意的∈(∪)−(∪),则x∈ ∪ 但x∉(∪),于是x∉且x∉。因为x∈ ∪ 得x∈或x∈，由上x∉知，x∈且x∉，于是x∈−.所以(∪)−(∪)⊑− 。 反之不成立，例如，X= 1,2,Y= 2,3,Z= 1, 于是X−Y= 1 ⊈ X∪Z − Y∪Z =∅. 二、集合与关系（共 30 分） ……4 分 ……4 分 成立，举反例说明之。 ……3 分 ……6 分 ……4 分 ……3 分 （2）反对称性 证明：（1）自反性 6. （6 分）已知1,2均为上的偏序关系，证明1∩2也为上的偏序关系。 对于任意的∀x∈A,因为1,2 均为上的自反关系，所以(x,x)∈1,(x,x)∈2,从而有 (x,x)∈1∩2。 对 于 任 意 的 (x,y)∈1∩2 , (y,x)∈1∩2 ， 从 而 有(x,y)∈1,(x,y)∈2 ,(y,x)∈ 1,(y,x)∈2,因为1,2均为上的反对称关系，所以由(x,y)∈1,(y,x)∈1得x=y； (x,y)∈2,(y,x)∈2得 x=y。 答：（1）∅ （2）{ 微信, 微信 , 百度, 百度, 百度, 百度 , 百度, 百度, 1,1, ∅,∅}……4 分 三、图结构（共 32 分） 8. （8 分）证明：设G 中所有顶点的度数小于等于 14，则根据握手定理知 （3）传递性（略） ……2 分 ……2 分 7. （8 分） ……2 分 ……4 分 2E = ≤13+14+14−2 =14−1<14 ,矛盾。故G 中至少有一个顶 是一个无回路且连通的简单无向图。试证明： ,( EVG  ) 是一个无回路，所以所有回路长度为 0，由二部图的充要条件 点的度数大于 14。 9. （8 分）设 （1）证明：因为 知，G 为二部图。 ,( EVG  ) （2）设2中所有顶点的度数均大于等于 2，因为 2E = dv =22 + 2||,矛盾。故则2中存在一个度数为 1 的顶点。 向图，所以 G 为一棵树。根据二部图的定义、握手定理及树的性质知 22 ≤21 +22 =2 1 +22 −1 +2=2+2< 10(6 分)证明：2n 个人为 2n 个顶点，两个人对战过王者荣耀游戏，形成一条边，构造出 ,( EVG  ) 是一个无回路且连通的简单无 图 G=（V，E）。因为这 2n 个人中，每个人至少与其余 n 个人对战过王者荣耀游戏，则每 个顶点的度数n，任意两个顶点 u 和 v，d(u)+d(v)2n，因此图 G 存在哈密尔顿圈。 沿 哈密尔顿圈就座，能使每个人左、右邻人对战过王者荣耀游戏. 注：本题为基本题，考核哈密尔顿图的充分条件。 11.（6 分）证明：令V =n,E =m.设所有顶点的度数均大于等于５，则根据握手定理知 2m= ()≥5 m≤3n−6，于是5n≤2m=6n−12,从而有n≥12。矛盾，故 ,因为 m<30,所以n<12。又因为 是一个简单平面图，所以 ,( EVG  4)( vd Vv  ，使得 。……6 分 ) ……6 分 

课程名称： 离散数学 学分： 3 教学大纲编号： 第 1 页 共 2 页 试卷编号： 12. （4 分） A 考试方式： 闭卷 满分分值： 100 考试时间： 120 分钟 ……3 分 14. （8 分） 证明：（1）闭运算 四、函数与群（共 20 分） 13. （6 分） 证明：因为平面图 G 的对偶图同构于 G，所以 n=r,根据欧拉公式 n-m+r=2 知=2(−1)。 证明：（1）单射：对于任意的1,2,若1 =2 ，则∆1∆−1=∆2∆−1,因为(,∆)是 一个群，满足左右消去律，所以1=2。 （ 2 ） 满 射 ： 对 于 任 意 的∈ , 因 为(,∆) 为 群 ， 所 以∃=−1∆∆ , 使 得 = ∆−1∆∆∆−1=y. 对于任意的∀,∈, 因为G,∗ 是一个群，所以∆=∗∗∈。 （2）结合律：对于任意的∀,,z∈, 因为G,∗ 是一个群,所以∆∆ =∆∗∗ =∗ ∗ ∗∗ = ∗∗ ∗∗=(∆0)∆。 （3）幺元为−1（证略） （4）对于任意的x，其逆元为−1∗−1∗−1(证略) 15．(6 分)设G,∙ 是一个群，A,∙ 是G,∙ 的子群，若C={x∈G|x∙A=A∙x},试证明C,∙ 是G,∙ 证明：（1）因为A,∙ 是G,∙ 的子群，e 为幺元，所以e∙A=A∙e,从而有e∈A≠∅且A⊆G。 （2）对于任意的,∈,由 C 的定义知a∙A=A∙a,b∙A=A∙b。因为A,∙ 是G,∙ 的子群， 所 以A∙b−1=b−1∙ b∙A ∙b−1=b−1∙ A∙b ∙b−1=b−1∙A , 于 是 a∙b−1 ∙A=a∙ b−1∙ A =a∙ A∙b−1 =(∙A)∙b−1=∙(a∙b−1),于是 a∙b−1 ∈， 由子群的判定定理知，C,∙ 是G,∙ 的子群。 ……2 分 ……2 分 ……2 分 ……3 分 ……2 分 ……4 分 的子群。 ……2 分 南 京 理 工 大 学 课 程 考 试 试 卷 答 案 及 评 分 标 准 

第 2 页 共 2 页