西工大离散数学2006-07统考题

诚信 保证 本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。本人签名： 班 级 ： 学 号 ： 装 订 姓 名 ： 线 编号： 西北工业大学考试试题（卷） 2006－2007学年第一学期 成 绩 开课学院 计算机学院 课程 离散数学 学时 考试日期 考试时间 小时 考试形式：闭卷 注意：请将第一、二大题的答案填写在第4页的表格内。 一、 选择题（每小题1分，共10分） 1．设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为（ ） A. P→Q B. Q→P C. P?Q D. ?P??Q 2．下面哪个是命题 “2是偶数或－3是负数”的否定？（ ） A.2不是偶数或－3不是负数 B.2是奇数或－3不是负数 C.2是奇数且－3不是负数 D.2不是偶数且－3不是负数 3．谓词公式?x(P(x)??yR(y))?Q(x)中变元x 是（ ） A．自由变量 B. 约束变量 C．既不是自由变量也不是约束变量 D．既是自由变量也是约束变量 4．设A＝{a,{a}},下面选项中错误的是（ ） A.{a}??(A)B.{a}??(A)C.{{a}}??(A)D.{{a}}??(A) 5．设M?{x|f1(x)?0},N?{x|f2(x)?0}则f1(x)?f2(x)?0的解为（ ） A. M?N B. M?N C.M? N D. M－N 6．设R是集合A＝{1,2,。。。,10}上的二元关系，R＝{|x+y=10}则R满足（ ） A.自反性 B. 对称性 C.传递性及对称性 D. 反自反性及传递性 7．设Z是整数集合，函数f:Z?Z定义为f(x)=|x|-2x，则f是（B ）。 A.满射 B. 单射 C.双射 D.既不是单射也不是满射 8．设Z是整数集，＋是算术加法，则下面函数中哪个不是群的自同态？（ ） A.f(x)=2x B. f(x)=1000x C.f(x)=|x| D.f(x)=0 9．设G=是一无向图，|V|＝6,|E|＝16，则G一定是（ D ） A.完全图 B.零图 C.简单图 D. 多重图 注：1. 命题纸上一般不留答题位置，试题请用小四、宋体打印且不出框。 2. 命题教师和审题教师姓名应在试卷存档时填写。 共3页 第1页

西北工业大学命题专用纸

10． 任何无向图中结点间的连通关系是一个（ D ）。 A. 偏序关系 B. 相容关系 C. 拟序关系 D.等价关系

二、 判断题（每小题1分，共10分）

班 1．命题“王兰和王英是姐妹”是一个复合命题。 （ ） 级 2．并不是所有人都是男人与存在一个人不是男人是等价的。 （ ） ： 3．同一个谓词公式在任何论域上的真值都是相同的 。 （ ） A?B,A?B不可能同时成立。 4．A,B是集合，则命题 （ ）

5．R是集合A上的二元关系，R要么是自反的，要么是反自反的 （ ）

6．A是有限集，f：A→A是满射函数，则f是双射的。 （ ）

7．满足消去律的有限含幺半群一定是群。 （ 对 ）

8．若偏序集A的任意子集B中含有极大元，则B中一定有最大元（ ）

学 9．f是群G到群H的同态映射，若G是交换群，则H也是交换群（ ） 号 10． 若有向图G是个欧拉图，则G是一个强连通图 （ ） ： 三、 演算题（共40分，以下第1.、2.、3.小题每题6分，考生可任选其中两题，若三题均做，则按每题4分计分；第4.-7.题是必答题，每题7分）

1．（6分）设G(x):x是金子，F(x):x是闪光的。将“金子是闪光的，但闪光的不

一定是金子”符号化。

2．（6分）设集合A = {1,2,3}, A上的关系R = {(1, 1), (1, 2), (2, 3), (3, 3)},

a) 写出R的关系矩阵；

b) 计算r(R),s(R),t(R) .

3． （6分）求公式 ? (P?Q)?(R→?Q） 的主析取范式和主合取范式。

4．（7分）设A={1,2,3,4,6,12}，R?A2，且R={| a整除b}。 姓

a) 证明R是偏序的； 名

b) 画出R的哈斯图； ：

c) 给出集合{3,4,6}的极小元、极大元、最小上界、最大下界。 5．（7分）N是自然数集合，f,g,h是从N到N的函数，其中： ?0n是偶数 f(n)?n?2,g(n)?3n,h(n)??1n是奇数?给出fof, fog, gof, hof, hog, (fog) oh。（注：o是函数的复合运算） 6．（7分）设 为模n加群，f:Z12→Z4，f(x)=(x mod 4)，则f为同态映射。 a) 验证f是否为单同态和满同态。 b) 令K={x|f(x)=0}，计算K。 7．（7分）已知无向图G有13条边，1度顶点有4个，2度、5度顶点各2个，其余顶点度数均为4，求4度顶点的个数，并判断G是否可以一笔画？ 共3页 第2页

西北工业大学命题专用纸

四、 证明题（共40分。以下六小题每题8分，考生可以任选做其中五题。若六题全做，按前五题计分）

1． （8分）理发师都教育自己的孩子成为理发师，有一个人教育他的孩子成为教

班 师，用形式演绎法证明：这个人不是理发师。(要说教孩子成为教师与不教孩子级 成为理发师是等价的,) ： 2．（8分）设A={1,2,3}×{1,2,3,4}, A上的二元关系R定义为：R当且仅当|x-y|=|u-v|，证明R是等价关系，并给出R对A的划分。

3． （8分）设（A,*）是一个代数系统，*是A上的二元运算，且?a,b,c?A：

(a*b)*(b*c)=b 证明：?a,b,c?A: a*((a*b)*c)=a*b。

4． （8分）设h是群到群的群同态，证明：G在h下的同态象j

是群的子群.

5．（8分）设是一个偶数阶的群，H是G的子群，且|H|＝|G|/2,证明：H是

学 G的正规子群。 号 6． （8分）设无向图G中有n个结点，n-1边，用归纳法于n,证明G是连通图则： G中无回路。 姓 名 ：

共3页 第3页

第一题答题表 2 题号 1 A ○ ○ B ○ ○ C ○ ○ D ○ ○ 第二题答题表 2 题号 1 Y ○ ○ N ○ ○ 3 ○ ○ ○ ○ 4 ○ ○ ○ ○ 5 ○ ○ ○ ○ 6 ○ ○ ○ ○ 7 ○ ○ ○ ○ 7 ○ ○

8 ○ ○ ○ ○ 9 ○ ○ ○ ○ 10 ○ ○ ○ ○ 3 ○ ○ 4 ○ ○ 5 ○ ○ 6 ○ ○ 8 ○ ○ 9 ○ ○ 10 ○ ○