admin 管理员组文章数量: 1086019
2024年3月20日发(作者：无主之地2狂人)
三、计算证明题
1.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。
(1) 画出半序集(A,R)的哈斯图；
(2) 写出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界；
(3) 写出A的最大元，最小元，极大元，极小元。
2. 设集合A＝{1, 2, 3, 4}，A上的关系R＝{(x,y) | x, yA 且 x y}, 求
(1) 画出R的关系图；
(2) 写出R的关系矩阵.
3. 设R是实数集合，,,是R上的三个映射，(x) = x+3, (x) = 2x, (x) ＝ x/4,试求复合
映射•，•, •, •，••.
4. 设I是如下一个解释：D = {2, 3},
a
3
b
2
f (2)
3
f (3)
2
P(2, 2)
0
P(2, 3)
0
P(3, 2)
1
P(3, 3)
1
试求 (1) P(a, f (a))∧P(b, f (b));
(2) xy P (y, x).
5. 设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。
(1) 画出半序集(A,R)的哈斯图；
(2) 写出A的最大元，最小元，极大元，极小元；
(3) 写出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.
6. 设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。
7. (9分)设一阶逻辑公式：G = (xP(x)∨yQ(y))→xR(x)，把G化成前束范式.
8. 对于下面二叉树的点，求先根遍历次序、中根遍历次序、后根遍历次序。
A
B
D
F
I
C
E
G
H
K
M
L
J
9. 设R是集合A = {a, b, c, d}. R是A上的二元关系, R = {(a,b), (b,a), (b,c), (c,d)},
(1) 求出r(R), s(R), t(R)；
(2) 画出r(R), s(R), t(R)的关系图.
10. 试用克鲁斯卡尔算法求出如下权图的最优支撑树。
5
2
3
2
2
2
1
3
5
3
3
2
3
4
2
2
11. 通过求主析取范式判断下列命题公式是否等价：
(1) G = (P∧Q)∨(P∧Q∧R)
(2) H = (P∨(Q∧R))∧(Q∨(P∧R))
12. 用迪克斯特拉算法求下面有限权图中从A到B的最短路(要求用图示给出求解过程)，并
计算它们的权值。
B
1
A
4
F
6
2
5
4
7
3
1
G
E
C
8
9
2
D
13. 设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)},
S＝{(a, b),(b, c),(b, d),(d, d)}.
(1) 试写出R和S的关系矩阵；
(2) 计算R•S, R∪S, R
1
, S
1
•R
1
.
四、证明题
1. 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。
2. 设A,B为任意集合，证明：(A-B)-C = A-(B∪C).
3. (本题10分)利用形式演绎法证明：{A∨B, C→B, C→D}蕴涵A→D。
4. (本题10分)A, B为两个任意集合，求证：
A－(A∩B) = (A∪B)－B .
－－－
参考答案
三、计算证明题
1.
(1)
8
4
2
1
12
6
3
9
(2) B无上界，也无最小上界。下界1, 3; 最大下界是3.
(3) A无最大元，最小元是1，极大元8, 12, 90+; 极小元是1.
版权声明：本文标题：《离散数学》大题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1710948361a580965.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论