文档介绍：《离散数学》复习题
、填空题(每小题1分，共10分)
1、P：你努力，Q：你失败。”除非你努力，否则你将失败”的翻译为
2、一阶逻辑公式 x F x G x y F y G y 的类型是<
3、设个体域为整数集合，命题 x yx y证明：A B C D , D E F A F
3。
2、证明：在6个结点12条边的连通平面简单图中，每个面的面度数都是
一、填空题(每空2分，共30分)
(1)设A为任意的公式，B为重言式，则 A B的类型为 .
(2)无向图G是欧拉图的充分必要条件是 .
(3) ( A B) A 为假言推理定律.
(4)在一阶逻辑中将命题符号化时，若没指明个体域，则使用 个体域.
(5)若R既是、、则称R是整环；
(6)设[0,1]和(0,1)分别表示实数集上的闭区间和开区间，则下列命题中为真的是 ；
A. {0,1} (0,1) B. {0,1} [0,1] C. (0,1) [0,1]
D. [0,1] Q E. {0,1} Z
(7)已知R A人且A={a,b,c}, R的关系矩阵
0 0
M(R)= 0 1 1
0 1 1
则传递闭包t(R)的关系矩阵M(t(R))=.;
(8)设 R 为实数集合，f: R R, f(x)=x2 x+2, g： R R, g(x)=x 3,则 f g(x)=;
(9)设 Z 为整数集， a,b Z, a b = a+b 1, a Z, a 的逆元 a 1 =；
(10)设G=<a>是24阶循环群，则 G的生成元为 ;
(11)设L为钻石格，则 L有 个2元子格；
n阶k-正则图 G的边数 m=;
(13)在完全图K2k (k>2)上至少加 条边，才能使所得图为欧拉图；
6阶无向连通图至多有 棵不同构的生成树；
，一，、，“ ， ,、3
(15)在环中计算(a b)；
二、在自然推理系统P中，用直接证明法构造下面推理的证明(10分)
前提： (p q), q一 r, r
结论：p
三、证明题(每题10分共30分)
.设 E={1,2,...,12} , A={1,3,5,7,9,11}, B={2,3,5,7,11} , C={2,3,6,12}, D={2,4,8},计算：A B, A C, C (A B), A B, C D, B D.
.设Z18为模18整数加群，求所有元素的阶.
.求带权为 5,5,6,7,10,15,20,30的最优树 T,并求 W(T).
四、应用题(每题10分共20分)
.判断正整数集合 z+和下面的每个二元运算是否构成代数系统 .如果是，则说明这个运算是否适合
交换律、结合律和哥等律，并求出单位元和零元 ^
a b = max(a,b), a? b = min(a,b), a?D = ab, aOb = (a/b)+(b/a)
.计算机系张、王、李、赵 4位教授下学期要承担他们都熟悉的 4门课程：数据结构、操作系统、 C
语言和JAVA.
(1)试讨论学院安排他们授课的方案数；
(2)在上述各方案中，有多少种是完全不同的方案 (即，每位教授所授课程都不相同的方案数 )?
五、判断解答(10分)
判断正整数集合 Z+和下面的每个二元运算是否构成代数系统 .如果是，则说明这个运算是否适合交
换律、结合律和哥等律，并求出单位元和零元 ^
a b = max(a,b), a? b = min( a,b), a?D = ab, aOb = (a/b)+(b/a)
答案
、填空
矛盾式
G连通且无奇度顶点.
_B
全总
交换环、含幺环、无零因子环
B,C,E
M(R)
x2 x-1
2 a
5 7 11 13 17 19 23
a,a ,a ,a ,a ,a ,a ,a
kn
一 2
13. k
（每题9分共27分）
.设 E={1,2,...,12} , A={1,3,5,7,9,11}, B={2,3,5,7,11} , C={2,3,6,12}, D={2,4,8},计算：A B, A C, C (A B), A B, C D, B D.
A B {1,2,3,5,7,9,11}
A B {3}
C (A B) {6,12}
A B {1,9}
C D {3,6,12}
B D {3,4,5,7,8,11}
. |0| = 1, |9| = 2, |6| = |12| = 3, |3| = |15| = 6,
|2| = |4| = |8| = |10| = |14| = |16| = 9, |1| = |5| = |7| = |11|