《离散数学》试题及答案

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

Q∧R)∨(P∧

Q∧

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

∨(P∧Q∧R)

= m3∨m4∨m5∨m6∨m7 = (3, 4, 5, 6, 7). 7. G = ((x)∨(y))→(x) = ((x)∨(y))∨(x) = ((x)∧

(y))∨

(x)

= (xP(x)∧yQ(y))∨(z)

=

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

9. (1) r(R)＝R∪＝{(), (), (), (), (), (), (), ()},

s(R)＝R∪R－1

＝{(), (), (), () (), ()},

t(R)＝R∪R2

∪R3

∪R4

＝{(), (), (), (), (), (), (), ()}； (2)关系图: adadad bcbcbc r(R)s(R)t(R)

11. G＝(P∧Q)∨(

P∧Q∧R)

＝(P∧Q∧

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

＝m6∨m7∨m3

R)

(), ＝ (3, 6, 7)

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

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

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

(

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

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

＝m6∨m3∨m7 ＝

(3, 6, 7)

的主析取范式相同，所以G = H. 13. (1)

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

R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, 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)

R→Q Q(2)(3)

),(c, ),(d, dd(5) Q→R Q(4)

(6) R→S P (7)

Q→S Q(5)(6)

(8) Q∨S Q(7) 2. 证明：() = (A∩)∩ = A∩(∩) = A∩~(B∪C) = (B∪C) 3. 证明：{A∨B,

C→

B, C(1) A D(附加) (2)

A∨B P

(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, C5. 证明：A－(A∩B)

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

→D}蕴涵A→D

→D}蕴涵A→D.

＝(A∩)∪(A∩) ＝

∪(A∩)

＝(A∩) ＝A－B 而 (A∪B)－B = (A∪B)∩ = (A∩)∪(B∩) = (A∩)∪= A－B

所以：A－(A∩B) = (A∪B)－B.