【计算机】南理工《离散数学》A卷(附答案)(2).docx

南京理工大学课程考试试卷（学生考试用） 课程名称：离散数学A 学分：4.5 大纲编号 试卷编号： 考试方式：闭卷 满分分值：100 考试时间：120 分钟 组卷日期：20XX 年 1 月 2 日 组卷教师（签字）朱保平 审定人（签字） 金忠 学生班级：计算机学院 09 级 1．（6 分）试把下列语句翻译为谓词演算公式 某些人喜欢所有明星； 并非“所有人均喜欢电脑游戏”。 2．（6 分）把下列数论语句化为特征函数 x 为平方数且 x 为偶数； x 是 y 的倍数或 x 小于等于 y 。 3．（6 分）已知公理：（A） (P ? Q) ? P （B） (P ? Q) ? Q （C） (P ? (Q ? (P ? Q)) （D） ??P ? P 及分离规则和代入规则。 试用假设推理证明下面公式为本系统中的定理 (P ? Q) ? ((??P ? R) ? (Q ? R)) 4.（8 分）试把函数h(x , x 1 2 , x , x 3 5 ) ? f ( g 1 (x , b), x , g 1 5 2 (x , x 2 3 ),4) （其中b 为自然数）化为 (m, n) 标准迭置。 5．（6 分）已知知识的符号表示 （1） ?x(P(x) ? ?y(D( y) ? L(x, y))) （2） ?x(P(x) ? ?y(Q( y) ? ?L(x, y))) 结论： ?x(D(x) ? ?Q(x)) 试用霍恩子句逻辑程序证明之。 6．（8 分）已知： A ? {{?},{1}}， B ? {{a}}。试求 （1） 2 A ； （2） B ? 2 A 。 7．（6 分）已知 A, B, C 是三个非空集合， f 为 A 到 B 的映射， g 为 B 到C 的映射。证明：如果 g f 是 A 到C 的双射，则 f 为 A 到 B 的单射， g 为 B 到C 的满射。 8．（6 分） (G, ?) 是群， (H , ?) 是(G, ?) 的子群，~是G 上的二元关系，对于任意的a,b ? G ， a ~ b ? b?1 ? a ? H 。试证明 ~为G 上的等价关系； 对于?a ? G ，有[a] ? a ? H 。 ~ 9．（8 分）已知Q* ? Q ?{0} ， Q 是有理数集， ?m, n ? Z , n * m ? 1 nm ，证明(Q* ,*) 是群。 7 10．（6 分） G ? (V , E) 是一个简单连通图。且 G 是一个二部图（偶图），相应地顶点分类为 {V ,V 1 2 }，且| V 1 |?| V 2 | 。证明G 不是哈密尔顿图。 11．（8 分） 画一个 10 个顶点欧拉图但非哈密尔顿图，它是简单无向图，有奇数条边； 画一个 10 个顶点哈密尔顿图但不是欧拉图，它是简单无向图，有偶数条边。 12．（6 分）设G ? (V , E) 是连通图，且e ? E 。证明： e 为G 的割边（即拿去此边后，G 变成不连通的两部分）当且仅当e 在G 的每棵生成树中。 13．（6 分）设(H ,*) 是群(G,*) 的子群，如果 A ? {x | x ? G, x * H ? H * x} ，证明( A,*) 是(G,*) 的子群。 14．（8 分） （1） T 是一棵树。试证明T 为二部图； 若G ? (V , E) 是二部图，且| V |? n,| E |? m ， 试证明m ? n2 。 4 15．（6 分） G ? (V , E) 是一个简单无向图。若| V |? 11 ，则G 或G 是非平面图。 南京理工大学课程考试试卷答案及评分标准 课程名称： 离散数学 学分 4.5 分 教学大纲编号：试卷编号：考试方式： 闭卷 满分分值： 100 考试时间： 120 分钟 1.(共 6 分，每小题 3 分) 解（1） ?x(P(x) ?（?y(S (y) ? L(x，y)))) 3 分 （2） ??x(P(x) ?（?y(G(y) ? L(x，y)))) 或??x(P(x) ?（?y(G(y) ? L(x，y)))) 3 分 注：本大题为基本题，考核自然语言的谓词表示方法。 2.（共 6 分，每小题 3 分） （1） N 2 (N 2 (x [ x ]2 ) ? N 2 rs(x,2)) 3 分 （2） N 2 rs(x, y) ? (N 2 (x y) ? min(N 2 rs(x, y), N 2 (x y)) 3 分 注：本大题为基本题，考核特征函数的表示方法。 3.（共 6 分） 证明： P ? Q 前提假设 ??P ? R 前提假设 （3） (??P ? R) ? ??P 公理（A） （4） (??P ? R) ? R 公理（B） （5） ?? P （