(A)若 R 和 S 是自反的，则 R S 是自反的。
(B)若 R 和 S 是对称的，则 R S 是对称的。
(C)若 R 和 S 是反对称的，则 R S 是反对称的。
(D)若 R 和 S 是传递的，则 R S 是传递的。
3. 设集合 A = {1, 2, 3, 4, 5}上的关系 R = {(x, y)|x, y A 且 x + y = 6}，则 R 的性质是
七、(10 分) 用构造法证明： x(P(x) (Q( y) R(x))) ， xP(x) Q( y) x(P(x) R(x)) .
八、(10 分) 用哈夫曼算法求带权为 1,3,5,7，8,11,12 的最优二元树并计算此最优树的权。
广东工业大学试卷用纸，共 5 页，第 2 页
5. 不同构的 5 阶无向树有( 3 )棵，不同构的 5 阶根树有( 9 )棵。
三、(10 分) 设集合 A={a,b,c}, P(A)是集合 A 的幂集,试画出偏序集 P(A) , 的哈斯图,
并指出子集{{a},{b}}的极大元、极小元、最大元、最小元、上界、下界、最小上界和最大下界。
20
47 27
9
15
11 12
4
5
78
1
3
权 W (T ) (1 2) 2 122
（1 分） （3 分） （5 分）
（7 分） （9 分） （10 分）
（8 分） （10 分）
广东工业大学试卷用纸，共 5 页，第 5 页
(
).
(A) 自反的. (B) 对称的. (C) 对称的、传递的. (D) 反自反的、传递的。
4．下列次序集不是偏序集和全序集的是（ ）。
A． N , B． Z , C． P({a}), D． P(N ),
5. 4 阶完全无向图 K 4 中含 3 条边的不同构的生成子图有
1. 幂集 P(P(P())) 为(
)
(A) {{}, {, {}}}.
(B) {, {, {}}, {}}.
(C) { , {, {}}, {{}}, {}} (D) { , {, {}}}.
2. 设 R A A，S A A，则下述结论正确的是(
).
（4 分）
( p (q q) r) (( p p) q r)
（7 分）
( p q r) ( p q r) (p q r) （10 分）
五、证明： 由于 R 和 S 是对称的，所以 R 1 R, S 1 S . ()因为 R S S R ，两边取逆得 (R S )1 (S R)1 ，而
US(3)
(5) Q( y) R(c)
(6)Q(y) (7)R(c)
(8) P(c) R(c)
T(2)(4)I
T(5)I T(5)I T(2)(7)I
(9) x(P(x) R(x))
UG(8)
(10) Q( y) x(P(x) R(x)) T(6)(9)I
八、（10 分）解：
3. x(Z (x) O(x)) .
4. 3, 2, 2 5. 3 , 9
三、（10 分）解：
{a,b,c}
{}
{a,b}
{a,c}
{b,c}
{b}
{a}
{c}
{Ø}
（4 分）
极大元{a}, {b} ，极小元{a},{b}，没有最大元和最小元，上界是{a,b} ,{a,b,c}，下
界是 ，最小上界是广{东a,b工}业，大最学大试下卷界用是纸，共。5 页，第 3 页
姓 名：
广东工业大学考试 答题纸
课程名称:
离散数学
试卷满分 100 分
考试时间: 2015 年 1 月 12 日 ( 第 19 周 星期 一 )
题 号 一 二 三 四 五 六 七 八 九 十 总分
评卷得分 评卷签名 复核得分 复核签名
一、单项选择题(本大题共 5 小题，每小题 4 分，共 20 分)
（8 分）
学 院：
极大元{a}, {b} ，极小元{a},{b}，没有最大元和最小元，上界是{a,b} ,{a,b,c}，下界
是 ，最小上界是{a,b}，最大下界是 。
（10 分）
四、解 ： ( p q) r (p q) r (p q) r
（2 分）
( p q) r ( p r) (q r)
(S R)1 R 1 S 1 R S . 所以 (R S )1 R S ，因此 R S 是对称关系. ()由于 R S 对称，所以 (R S )1 R S .
而 (R S )1 S 1 R 1 S R ，因而 R S S R .
(9) q s
T(4)(5)I T(1)(6)I T(3)(7)I CP
广东工业大学试卷用纸，共 5 页，第 4 页
（1 分）
（3 分）
（7 分） （8 分） （10 分）
七、证明
(1) xP(x)
P
(2)P(c)
US(1)
(3) x(P(x) (Q( y) R(x))) P
(4) P(c) (Q( y) R(c))
学 号：
线
班级
订
专 业：
装
1
2 345
C A BDA
二、填空题(本大题共 5 小题，每小题 4 分，共 20 分)
1. {(a,a),(b,b), (c,c),(d,d), (e,e),(a,d), (d,a),(c,e), (e,c)} 2. {(1,5), (3, 2), (2, 5)}, {(4, 2), (3, 2), (1, 4)}, {(1, 2), (2, 2)}.
(
)。
0 1 0 1
4.
设有向图 G = (V, E)，V =
{v1，v2，v3，v4}，若
G
的邻接矩阵
A=
1 1
0 1
1 0
1 0
,
则 v1 的出度
1 0 0 1
deg+(v1) =______2__, v1 的入度 deg-(v1) =_____3___, 从 v2 到 v4 长度为 2 的路有_____2___条。
四、(10 分) 设 p, q, r 为命题变元，用等值演算法计算(p→q)→r 的主合取范式。 五、(10 分) 设 R 和 S 是集合 A 上的对称关系，证明 R S 对称的充要条件是 R S S R .
六、(10 分)用 CP 规则证明下列推理. p (q r), q (r s), p q s .
(A)3
(B)4
(C)5
(D)2
班级
订
专 业：
装
学 院：
广东工业大学试卷用纸，共 5 页，第 1 页
二、填空题(本大题共 5 小题，每小题 4 分，共 20 分)
1.设集合 A={ a , b , c , d , e}上的的划分 S ={{a，d}，{b}，{c，e}}，则由划分 S 所确定
的 A 上的等价关系 R =
。
2. 设 A = {1, 2, 3, 4, 5}上的关系 R = {(1, 2), (3, 4), (2, 2)}, S = {(4, 2), (2, 5), (3, 1), (1, 3)}, 则
R S {
}, S R {
}, R R {
}。
3. 令 Z(x): x 是 整 数 ， O(x): x 是 奇 数 ， 则 “ 不 是 所 有 整 数 都 是 奇 数 ” 符 号 化 为
姓 名：
学 号：
线
广东工业大学考试试卷 ( A 卷)
课程名称:
离散数学
试卷满分 100 分
考试时间: 2015 年 1 月 12 日 ( 第 19 周 星期 一 )
题 号 一 二 三 四 五 六 七 八 九 十 总分
评卷得分 评卷签名 复核得分 复核签名
一、单项选择题(本大题共 5 小题，每小题 4 分，共 20 分)
（1 分） （2 分）
（6 分） （8 分） （10 分）
六、证明 p (q r), q (r s), p q s
(1)q
(2) q (r s)
P(附加) P
(3) r s
(4)p
(5) p (q r)
T(1)(2)I P
P
(6) q r
(7)r (8)s