《离散数学》试题及答案

得到树.

(A)6 (B)5 (C)10 (D)4. 15. 设图G的相邻矩阵为

，则G的顶点数与边数分别

为( D ).

(A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8. 三、计算证明题

1.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。 (1) (2)

画出半序集()的哈斯图；

写出A的子集B = {3,6,9,12}的上界，下界，最小上

界，最大下界； (3)

写出A的最大元，最小元，极大元，极小元。

解：（1）

（2） B无上界，也无最小上界。下界1, 3; 最大下界是3 （3） A无最大元，最小元是1，极大元8, 12, 9; 极小元是1

2. 设集合A＝{1, 2, 3, 4}，A上的关系R＝{() | x, y

y}, 求

A 且 x

(1) (2)

画出R的关系图； 写出R的关系矩阵.

解：（1） （2）

3. 设R是实数集合，,,是R上的三个映射，(x) = 3, (x) = 2x, ?，解： (1)?＝(2)?＝(3)?＝(4)?＝(5)?

(

(x))＝

(x)+3＝23＝23. (x)+3＝(3)+3＝6, (x)+3＝4+3, (x)/4＝24 = 2,)＝

?

(x) ＝ 4,试求复合映射?

?.

?，?, ?,

((x))＝((x))＝((x))＝?(

?

?＝+3＝24+3＝2+3.

▲4. 设I是如下一个解释：D = {2, 3},

a b f (2) f (3) P(2, P(2, P(3, P(3,

2)

3) 0

2) 1

3) 1

3 2 3 2 0

试求 (1) P(a, f (a))∧P(b, f (b));

(2)

xy P (y, x).

解：

(1) P(a, f (a))∧P(b, f (b)) = P(3, f (3))∧P(2, f (2)) = P(3, 2)∧P(2, 3) = 1∧0 = 0. (2)

xy P (y, x) = x (P (2, x)∨P (3, x))

= (P (2, 2)∨P (3, 2))∧(P (2, 3)∨P (3, 3)) = (0∨1)∧(0∨1) = 1∧1 = 1.

5. 设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。 (1) (2) (3)

画出半序集()的哈斯图；

写出A的最大元，最小元，极大元，极小元； 写出A的子集B = {4, 6, 8, 12}的上界，下界，最小

上界，最大下界.

解：(1) (2)无最大元，最小元1，极大元8, 12; 极小元是1.

(3) B无上界，无最小上界。下界1, 2; 最大下界2.

6. 设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。 解： G = =

(P→Q)∨(Q∧(P→R)) (P∨Q)∨(Q∧(P∨R))

Q)∨(Q∧(P∨R)) Q)∨(Q∧P)∨(Q∧R) Q∧R)∨(P∧

Q∧

R)∨(P∧Q∧R)∨(P∧Q∧

R)

= (P∧ = (P∧ = (P∧

∨(P∧Q∧R)∨(P∧Q∧R) = (P∧

Q∧R)∨(P∧

Q∧

R)∨(P∧Q∧R)∨(P∧Q∧

R)

∨(P∧Q∧R)

= m3∨m4∨m5∨m6∨m7 =

7. (9分)设一阶逻辑公式：G = ((x)∨化成前束范式. 解： G = (

(x)∨

(y))→

(x)

(y))→

(x)，把G(3, 4, 5, 6, 7).