江西农业大学《离散数学》课程试卷
适用专业：计算机 考试日期：2012/6/20 闭卷 所需时间：120分钟 总分：100分
一. 单项选择题。

（共20分，每题2分）
1.设命题公式G=(P ∧ Q)→ P,则G 是( D ).
A.恒假的. .B 析取范式. C. 可满足的. D.恒真的 2.下列度数列不可图化的是（ B ） 254
A. （3，3，3，1）
B. （5，5，4，4，2，1）
C. （5，4，3，2，2）
D. （4，4，3，3，2，2）
3.设集合A ＝{1,2,3,4},A 上的关系R ＝{(1,1), (2,3), (2,4), (3,4)},则R 具有（ B ）114
A.自反性；B ．传递性；C ．对称性；D ．以上答案都不对. 4.设 （ B ）闭包.116 A. 自反；B ．对称；C ．传递；D ．以上都不是.
5、设X ，Y 为集合，当（ D ）时，X －Y ＝Y .93 A.X=Y; B. ; C. ; D.
6、设G 是群，G 中有（ D ）个元素，则不能肯定G 是交换群。

203 A. 1 B. 2 C. 3 D. 6
7、设G 是有6个元素的循环群,a 是生成元素,则G 的子集( C )是子群. A. {a}; B. {a, e}; C. {e, a3}; D. {e, a, a2}; 8、下面的图是 （ C ）
A. 完全图； B . 平面图；278 C.哈密顿图； D. 欧拉图 9、G 是连通的平面图，有5个顶点，6个面，则G 的边数为（ D ）。

A 、6；
B. 5；
C. 11；
D. 9。

10、若复合映射τσ⋅是满射，则 ( )。

143
A τ是满射
B σ 是满射
C τ是单射
D σ是单射 二．填空题 (共20分，每空2分)
2、设p 、q 为命题变项，则（⌝p ↔q ）的成真赋值为 /0,1/ 。

12 ∪∪
3、设A 与B 是两个有限集合，则包含排斥定理|A ∪B|=|A|+|B|-|A ∩
B| ___.
∪4、设集合A ＝{a, b, c, d},A 上的关系R ＝{(a, a),(a, c),(b, d)},
则关系
＝___ {(a,a),(a,c),(b,d)} ________. 5、设G 是由12个元素构成的循环群,a 是G 的一个生成元素,则G 有 个子群；G 的生成元素集合是 . 6、一个结点为n 的无向完全图，其边的数目为 n(n-1)/2 。

7、设集合A ＝{a, b, c, d, e},A 上的偏序关系R 的哈斯图下图所示，则A 的极大元为_____a ______,极小元为_____c,d
_____.13/
8．设A={a,b},,则P(A)= $ ,{a},{b},{a,b} 。

注释:P(A)为幂集
9． A={2，3，5}，A 上的关系R={（2，3），（2，2）}，R 的自反闭包为 {(2,3),(2,2),(3,3),(5,5)} 三、计算题和证明题（60分）
1、求命题公式G 的主析取范式,其中G=﹁ (P →﹁Q ∨﹁R) ∨﹁((P ∨Q) ∧(Q ∨R)).（8分）
2、构造下面推理的证明(10分)37
若数a 是实数，则它不是有理数就是无理数。

若a 不能表示成分数，则它不是有理数。

a 是实数且它不能表示成分数，所以a 是无理数。

3、无向图G 有8条边，1个1度顶点，2个2度顶点，1个5度顶点，其余顶点的度数均为3，求G 中3度顶点的个数。

（8分)
4、设集合A ＝{1, 2, 3}，R 和S 是A 上的两个关系，它们的关系矩阵为：(10分)
110111111001.101000R S M M ⎡⎤⎡⎤
⎢⎥⎢⎥==⎢⎥⎢⎥
⎢⎥⎢⎥⎣⎦⎣⎦
(1) 写出关系R 和S 的集合表达式，(2) 画出R 和S 的关系图，11/ 5 设A,B 为任意集合，证明：B ∪ ~((~A ∪ B) ∩ A) = E .（8分）
6 证明等价式：((A ∧B)→C)∧(B →(D ∨C))⇔(B ∧(D →A))→C 。

（8分） 7．集合S={a,b,c}上的二元运算*的运算表如下，求出它的幺元、零元及
所有可逆元素的逆元(如果存在的话)。

（8分）
* a b c
a a a a
b a b
c c a c c
院系：—————— 专业班级：——————— 姓名：——————— 学号：—————
—
上的两个关系，其中＝是集合}4,3,2,1{A ,21R R )}4,4(),32(),22(),11{(R 1，，，＝的
是则122R )}.4,4(),2,3(),3,2(),2,2(),1,1{(R R =Y X ⊆Y X ⊇.
φ==Y X
2R。