A. 结合律
B. 交换律
C. 有幺元
D. 幂等律
8、对于集合 A＝｛0、1、2、3、4、5、6、7、8、9、10｝，不封闭的二元运算是[
B]
A x*y=max(x,y)
B x*y=x－y
C x*y=(x+y)mod 9
D x*y=min(x,y)
二、填空题(本大题共 10 小题，每空 3 分，共 24 分) 9、含 n 个命题变项的重言式的主合取范式为__________无_______________。 10、设个体域为整数集合 Z，命题 Vx ヨ y(x+y=3)的真值为_______1____。 11、以 1，1，1，2，2，3 为度数序列的非同构的无向树共有______2_____棵。 12、已知 n 阶无向简单图 G 有 m 条边，则 G 的补图 G 有___OK_______条边。 13、设 R={<{1}, 1>，<1, {1}>，<2, {3}>，<{3}, {2}>}，则 domR⊕ranR=_________OK__ 写成集合的形式__________。 14. 设 A={1, 2, 3, 4}，则 A 上有______24______个不同的双射函数。 15. 设σ=(1345)(2678)是 8 元置换，则σ-1=____*_______。 16、集合 A＝｛1、2、3、4｝上的恒等关系是_______OK__________________。
C. VxVyF(x,y)
D. ┐ヨ x ヨ yF(x,y)
3、设 R1、R2 为集合 A 上的任意关系，下列命题为真的是 Ａ 若 R1、R2 反自反，则 R1 R2 反自反 B 若 R1、R2 传递，则 R1 R2 传递 C 若 R1、R2 自反，则 R1 R2 自反 D 若 R1、R2 对称，则 R1 R2 对称
姓 名：
线
学 号：
订
广东工业大学考试试卷 ( A )
课程名称:
离散数学
考试时间: 2007 年 1 月 26 日 (第 21 周 星期五 )
题 号 一 二 三 四 五 六 七 八 九 十 总分
评卷得分 评卷签名 复核得分 复核签名
一、单项选择题(本大题共 8 小题，每小题 2 分，共 16 分)
1、设 p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘
广东工业大学试卷用纸，共 2 页，第 1 页
专 业：
装
学 院：
+-
6、下面等式中唯一的恒等式是
[D]
A. (A∪B∪C)-(A∪B)=C
B. A⊕A=A
C. A-(B×C)=(A-B)×(A-C)
D. A×(B-C)=(A×B)-(A×C)
7、设 R 为实数集，定义* 运算如下：a*b=|a+b+ab|，则 * 运算满足 [ B ]
公共汽车上班”的符号化形式为
[B]
A. p→q
B. q→p
C .p→┐q
D. ┐p→q
2、设解释 I 如下，个体域 D={a,b}, F(a,a)= F (b,b)=0, F(a,b)=F(b,a)=1，在
解释 I 下Vx ヨ yF(x,y)
B. ヨ xVyF(x,y)
2)指出偏序集的极大元、极小元、最大元、最小元
20、(10 分)设 Z 为整数集，在 Z 上定义二元运算*如下： x，yZ，x*y＝x＋y－2
请证明（Z，*） 是群。
21、(10 分)在命题逻辑中构造下面推理的证明。
前提：p→s，q→r，┐s，p∨q 结论：r
第 19 题图
22、(10 分) 用狄克斯特洛算法求下图中从 a 到 f 的最短
三、 简答及证明(本大题共 6 小题，每小题 10 分，共 60 分)
17、(10 分)设 G 为 n(n≥3)阶无向简单图，证明 G 或 G 的补图必连通。
18、(10 分)设 A，B，C 为集合，证明：
A∩(B－C)=(A－C)∩(B－C)
19、(10 分)右图是偏序图<X，≤>的哈斯图
1)X 和≤的集合表达式
通路。（写出求解过程）
6
b
c
3
3
a
13
f
2
5
d
1 e
6
广东工业大学试卷用纸，共 2 页，第 2 页
[C ]
4、设 G 为完全二部图 K2,3，下面命题中为真的是
[C ]
A. G 为欧拉图
B. G 为哈密尔顿图
C. G 为平面图
D. G 为正则图
5、对于任意集合 X, Y, Z，则 D] A. X∩Y=X∩Z =>Y=Z
C. X－Y=X－Z =>Y=Z
[
B. X∪Y=X∪Z =>Y=Z D. X⊕Y=X⊕Z =>Y=Z