9．设G=<V,E>是一无向图，|V|＝6,|E|＝16，则G一定是（D）
A.完全图B.零图C.简单图D.多重图
注：1.命题纸上一般不留答题位置，试题请用小四、宋体打印且不出框。
2.命题教师和审题教师姓名应在试卷存档时填写。共3页第1页
西北工业大学命题专用纸
班
级
：
学
号
：
姓
名
：
10．任何无向图中结点间的连通关系是一个（D）。
一、选择题（每小题1分，共10分）
1．设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为（）
A.P→Q B. Q→PC. PQ D.PQ
2．下面哪个是命题“2是偶数或－3是负数”的否定？（）
A.2不是偶数或－3不是负数B.2是奇数或－3不是负数
C.2是奇数且－3不是负数D.2不是偶数且－3不是负数
6．（7分）设<Zn,+>为模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是否可以一笔画？
A.偏序关系B.相容关系C.拟序关系D.等价关系
二、判断题（每小题1分，共10分）
1．命题“王兰和王英是姐妹”是一个复合命题。（）
2．并不是所有人都是男人与存在一个人不是男人是等价的。（）
3．同一个谓词公式在任何论域上的真值都是相同的。（）
4．A,B是集合，则命题 不可能同时成立。（）
5．R是集合A上的二元关系，R要么是自反的，要么是反自反的（）
诚信
保证
班
级
：
学
号
：
姓
名
：
装
订
线
编号：
成绩
西北工业大学考试试题（卷）
2006－2007学年第一学期
开课学院计算机学院课程离散数学学时
考试日期考试时间小时考试形式：闭卷
本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。本人签名：
注意：请将第一、二大题的答案填写在第4页的表格内。
共3页第3页
第一题答题表
题号
1
2
3
4
5
6
7
8
9
10
A
○
○
○
○
○
○
○
○
○
○
B
○
○
○
○
○
○
○
○
○
○
C
○
○
○
○
○
○
○
○
○
○
D
○
○
○
○
○
○
○
○
○
○
第二题答题表
题号
1
2
3
4
5
67Leabharlann 8910Y
○
○
○
○
○
○
○
○
○
○
N
○
○
○
○
○
○
○
○
○
○
4．（8分）设h是群<G,*>到群<H,>的群同态，证明：G在h下的同态象<h(G),>j是群<H,>的子群.
5．（8分）设<G,*>是一个偶数阶的群，H是G的子群，且|H|＝|G|/2,证明：H是G的正规子群。
6．（8分）设无向图G中有n个结点，n-1边，用归纳法于n,证明G是连通图则G中无回路。
A.自反性B.对称性C.传递性及对称性D.反自反性及传递性
7．设Z是整数集合，函数f:ZZ定义为f(x)=|x|-2x，则f是（B）。
A.满射B.单射C.双射D.既不是单射也不是满射
8．设Z是整数集，＋是算术加法，则下面函数中哪个不是群<Z,＋>的自同态？（）
A.f(x)=2x B. f(x)=1000x C.f(x)=|x| D.f(x)=0
4．（7分）设A={1,2,3,4,6,12}，RA2，且R={<a,b>| a整除b}。
a)证明R是偏序的；
b)画出R的哈斯图；
c)给出集合{3,4,6}的极小元、极大元、最小上界、最大下界。
5．（7分）N是自然数集合，f,g,h是从N到N的函数，其中：
给出fºf, fºg, gºf, hºf, hºg, (fºg)ºh。（注：º是函数的复合运算）
3．谓词公式 中变元x是（）
A．自由变量B.约束变量
C．既不是自由变量也不是约束变量
D．既是自由变量也是约束变量
4．设A＝{a,{a}},下面选项中错误的是（）
5．设 则 的解为（）
A. MNB. MN C.MND. M－N
6．设R是集合A＝{1,2,。。。,10}上的二元关系，R＝{<x,y>|x+y=10}则R满足（）
2．（8分）设A={1,2,3}×{1,2,3,4}, A上的二元关系R定义为：<x,y>R<u,v>当且仅当|x-y|=|u-v|，证明R是等价关系，并给出R对A的划分。
3．（8分）设（A,*）是一个代数系统，*是A上的二元运算，且a,b,cA：(a*b)*(b*c)=b证明：a,b,cA:a*((a*b)*c)=a*b。
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分）求公式(PQ)(R→Q）的主析取范式和主合取范式。
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分）
共3页第2页
西北工业大学命题专用纸
班
级
：
学
号
：
姓
名
：
四、证明题（共40分。以下六小题每题8分，考生可以任选做其中五题。若六题全做，按前五题计分）
1．（8分）理发师都教育自己的孩子成为理发师，有一个人教育他的孩子成为教师，用形式演绎法证明：这个人不是理发师。(要说教孩子成为教师与不教孩子成为理发师是等价的,)