离散试题与答案

考生注意：
1．学号、姓名、专 业班级等应填写准 确。 2．考试作弊者，责 令停考，成绩作废。
广西民族大学课程考试试卷
（2009 -2010 学年度第 一 学期期考） 课程名称：离散数学参考答案 考核方式：闭卷 考核时长： 120 分
A. f 是从 X 到 Y 的二元关系,但不是从 X 到 Y 的函数. B. f 是从 X 到 Y 的函数,但不是满射,也不是单射. C. f 是从 X 到 Y 的满射,但不是单射. D. f 是从 X 到 Y 的双射.
二、(10 分) 填空题(每空 1 分,共 10 分) 1.设代数系统 V Z 6 , ，其中 为模 6 乘法，那么 V 中的幂等元是
0, 1 , 3, 4 。
答 ((( p q) p) q) r ((( p p) (q p)) q) r
B. q p
C. p q
D.p q
A. 1 Z B. 2 Z C. 3 Z D. 4 Z 3.下列关系中具有自反性和对称性的关系是( A, C ). A. R1 是自然数集合 N 上的关系,且 xR1 y 当且仅当 x y 是偶数.
8．若 n 阶无向简单图 G 的 n 1, 则 G 为（ A, D
x( F ( x) g ( x)) x( F ( x) H ( x)) 。
5． R 为自然数集 N 上的关系， x, y N , xRy 2 | ( x y), 则 R 引起的 N 的 划分是 {A，N-A| A 为偶数集} 。 1,3,7,11,13,17,19 。
）
A. 无向完全图 K n D. 无向正则图 K n
B. 有向完全图 K n
C . 有向正则图 K n
二级学院主 管领导签字
B. R 2 是自然数集合 N 上的关系,且 xR2 y 当且仅当 x y 或 y x.
C. R3 是自然数集合 N 上的关系,且 xR3 y 当且仅当 | x | | y | 3.
3
答 ( F ( f ( x)) G( x, f ( x))) (F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3)))
姓
名
(n-1)!
条不同的哈密顿回路。
4．令 F ( x) : x 是人， G( x) : x 喜欢吃馒头， H ( x) : x 喜欢吃米饭。命题“虽 然有人不喜欢吃馒头，但也不是所有的人都喜欢吃米饭”的符号化形式为 专业班级
08 信计、软件
( B, C, E).A.命题教师 周永权
{0,1} (0,1) [0,1] Q
B. {0,1} [0,1] E.
{0,1} Z
C. (0,1) [0,1]
a b D. G { | a, b 为实数且 a 2 b 2 0} 关于矩阵的乘法. b a
(3). D 上特定的函数 f ( x) : f (2) 3; f (3) 2. (4). D 上特定的谓词 F ( x) : F (2) 0, F (3) 1; G ( x, y ) : G (2,2) G (2,3) G (3,2) 1.
G (3,3) 0; 求一阶公式: ( F ( f ( x)) G( x, f ( x))) 在 I 下的真值
7. 令 p : 天下大雨, q : 小王迟到,命题“除非天下大雨，否则小王不迟到”的符号化形 式是（ B ）
D.
2. 设 X , Y , Z 为任意集合 , 且 X Y {1,2,3}, X Z {2,3,4}, 若 2 Y , 则一定有
教研室主任 签 字
( B ).
A. p q
R2={<2,
时，完全图 K n 既是欧拉图，又是哈密顿图。
n 阶无向完全图 K n
{<2, 3>, <3, 2>}∪IA，{<1, 3>, <3, 1>}∪IA， {<1, 2>, <2, 1>}∪IA。
8． n 阶竞赛图的基图为
。 512 个。
4.无向图 G 有 11 条边,4 个 3 度顶点,其余顶点均为 5 度顶点,求 G 的阶数 n.
答 由握手定理有 211=43+5(n-4) 解得 n=5.
9．设 S {1,2,3} ，则 S 上不同的二元运算有
10． 设 Z 为整数集合， 为 Z 上的二元运算，x y x y 3. 则 Z 关于 的 运算构成群。已知 5 x 4. 则 x 2 。
三、计算题： （4 小题，每小题 5 分，共 20 分） 1．用等值演算法求下面公式的主析取范式：
2．给定解释 I 如下：(1).个体域 D {2,3}. (2). D 中特定元素 a 2.
2．设有以下四个命题，其中 p : 循环群是 Abel 群。q : 循环群有有限个生成
学 号
元。 r : 无限循环群的子群都是无限循环群。 s : n 阶循环群有惟一的 d 阶子 群，其中 d 是 n 的正因子。其中不正确的命题是 r 。 3．顶点标定顺序的无向完全图 K n (n 3) 中，在定义意义下共含有
((( p p) (q p)) q) r ((q p) q) r ((q p) q) r (q p q) r r ( p q r ) ( p q r ) (p q r ) (p q r )
(F(3)∧G(2,3))∨(F(2)∧G(3,2)) (1∧1)∨(0∧1) 1 3. 给出 A {1,2,3} 上所有的等价关系.
答
6．循环群 G Z 20 , 的生成元是 7．当 n 为 奇数
A {1,2,3} 上所有的等价关系为: 全域关系 EA，恒等关系 IA ，
五、证明题： （2 小题，每小题 10 分，共 20 分） 1.在一阶逻辑自然推理系统 F 中构造下面推理的证明. 不存在不能表示成分数的有理数 .无理数都不能表示成分数 .所以,无理数都不是 有理数. 答：设 F(x): x 为无理数；G(x): x 为有理数；H(x)：x 能表示成分数。 前提：┐x(F(x)∧H(x)), x(G(x)→H(x)) 结论：x(G(x)→ ┐F(x)) 证明：① ┐x(F(x)∧H(x)) 前提引入 ② x(┐F(x)∨┐H(x)) ①置换 ③ x(H(x)→┐F(x) ) ②置换 ④ H(y)→┐F(y) ③UI 规则 ⑤ x(G(x)→H(x)) 前提引入 ⑥ G(y)→H(y) ⑤UI 规则 ⑦ G(y)→┐F(y) ⑥④假言三段论 ⑧ x(G(x)→┐F(x)) ⑦UG 规则 2.设 G 是 n 阶 n 1 条边的无向图,证明 G 中存在顶点 v ,使得 d (v) 3 . 证明 反证，假设任意的顶点 v ，均有 d (v) 3 ，即 d (v) 2 ，那么由握手定理得
1
B. xy((F ( x) F ( y) L( x, y)) H ( x, y)) C. xy((F ( x) F ( y) L( x, y)) H ( x, y)) D. xy((F ( x) F ( y) L( x, y)) H ( x, y))
( A B) ( A C ) A
答: ( A B) ( A C ) A
A (B C) A A (B C) A B C .
六、应用题（10 分） 在某次国际会议的预备会议中，共有 8 人参加，他们来自不同的国家。已知他们 中任意两个无共同语言的人，与其余有共同语言的人数之和大于或等于 8，试证明能 将这 8 个人排在圆桌旁，使其任何人与两边的人交谈？ 答: 作无向图 G=<V,E>, 其中 V={v|v 为与会者}， E={(u,v) | u,vV, u 与 v 有共同语言, 且 uv}. 则 G 为简单图. 根据条件, u,vV, u,v 不相邻有 d(u)+d(v)8, 由定理可知 G 为哈密顿图. 那么服务员在 G 中找一条哈密顿回路 C，按 C 中相邻关系安排座位即可.
9．设 T 为 n(n 2) 阶， m 条边的无向连通图 G 的生成树，若 T 无弦，则 G 为（ A ）
卷别
B
D. R 4 是有理数集合 Q 上的关系,且 xR4 y 当且仅当 y x 2.
E. R5 是自然数集合 N 上的关系,且 xR5 y 当且仅当 x y 4.
4.设 X {a, b, c},Y {1,2,3}, f { a,1 , b,2 , c,3 }, 下列命题中惟一正确 的是( D ).
A. 实数集合 R 关于 运算,其中 a b 2(a b). B. 非零实数集合 R 关于 运算,其中 a b 2ab. C. 所有实数对 a, b 构成的集合关于 运算,其中 a, b c, d a c, b d .
专业班级
((( p q) p) q) r
2
四、简答题： （2 小题，每小题 15 分，共 30 分） 1.设 G Z 2 , 是模 2 加群 (1) 给出直积 G G 的运算表? (2)说明 G G 与哪个 4 阶群同构. 解 （1） <0,0> <0,1> <1,0> <0,0> <0,1> <1,0> <1,1>
学
号
题 得
号 分
一
二
三
四
五
六
总
分
5. 设 Z 为整数集, a, b Z , a b a b 1, a Z .a 的逆元 a 1 是(
B
).
A. 2 a
B. 2 a
C. 2
C ).