《离散数学》大题

2024年3月27日发(作者：初中数学试卷宁夏中考真题)

三、计算证明题

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, yA 且 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) xy 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.