《离散数学》试题及答案

= = (

((x)∨(x)∧

(y))∨(y))∨

(x) (x)

= (x =

P(x)∧yQ(y))∨(z)

xyz((P(x)∧Q(y))∨R(z))

9. 设R是集合A = {a, b, c, d}. R是A上的二元关系, R = {(), (), (), ()},

(1) 求出r(R), s(R), t(R)； (2) 画出r(R), s(R), t(R)的关系图. 解：（1）

r(R)＝R∪＝{(), (), (), (), (), (), (), ()},

s(R)＝R∪R＝{(), (), (), () (), ()},

t(R)＝R∪R∪R∪R＝{(), (), (), (), (), (), (), (), ()}；

(2)关系图:

11. 通过求主析取范式判断下列命题公式是否等价：

abr(R)dcabs(R)dabt(R)2

3

4

－1

dcc (1) G = (P∧Q)∨(P∧Q∧R)

P∧R))

(2) H = (P∨(Q∧R))∧(Q∨(解： G＝(P∧Q)∨(

＝(P∧Q∧

P∧Q∧R)

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

＝m6∨m7∨m3 ＝

(3, 6, 7)

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

P∧Q∧R) ＝(P∧Q∧＝m6∨m3∨m7

的主析取范式相同，所以G = H.

13. 设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a,

R)∨(

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

P∧Q∧R)

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

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

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, S?R. 解：

－1

－1

－1

(1)

(2)R?S＝{(a, b),(c, d)},

R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)},

R－1＝{(a, a),(c, a),(c, b),(d, c)}, S－1?R－1＝{(b, a),(d, c)}.

四、证明题

1. 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。 解：

(1) P∨R P (2)

R→P Q(1)

(3) P→Q P (4) (5)

R→Q Q(2)(3) Q→R Q(4)

(6) R→S P (7)

Q→S Q(5)(6)

(8) Q∨S Q(7)

2. 设为任意集合，证明：() = (B∪C). 解： () =

3. (本题10分)利用形式演绎法证明：{→D}蕴涵A→D。 解：

(1) A D(附加) (2)

A∨B P

A∨B, C→B, C

(3) B Q(1)(2) (4)

C→

B P

(5) B→C Q(4) (6) C Q(3)(5) (7) C→D P (8) D Q(6)(7) (9) A→D D(1)(8) 所以 {

A∨B,

C→

B, C→D}蕴涵A→D.

4. (本题10分)A, B为两个任意集合，求证： A－(A∩B) = (A∪B)－B . 解： 4. A－(A∩B)

= A∩~(A∩B) ＝A∩(∪)