《离散数学》试题及答案(4)

1 1

(2)MR

1 1

01110011

0 0 0 1

3. (1) ＝ ( (x))＝ (x)+3＝2x+3＝2x+3.

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

(5) ＝ ( )＝ +3＝2x/4+3＝x/2+3. 4. (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) x y 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. (1)

(2) 无最大(3) B无上

元，最小元1，极大元8, 12; 极小元是1.

界，无最小上界。下界1, 2; 最大下界2.

6. G = (P→Q)∨(Q∧( P→R))

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

= (P∧ Q∧R)∨(P∧ Q∧ R)∨(P∧Q∧R)∨(P∧Q∧ R)∨(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 = (3, 4, 5, 6, 7).

7. G = ( xP(x)∨ yQ(y))→ xR(x)

= ( xP(x)∨ yQ(y))∨ xR(x) = ( xP(x)∧ yQ(y))∨ xR(x) = ( x P(x)∧ y Q(y))∨ zR(z) = x y z(( P(x)∧ Q(y))∨R(z))

9. (1) r(R)＝R∪IA＝{(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d)},

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

－

t(R)＝R∪R2∪R3∪R4＝{(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)}； (2)关系图:

11. G＝(P∧Q)∨( P∧Q∧R)

＝(P∧Q∧ 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∧R)

＝(P∧Q∧ R)∨(P∧Q∧R)∨( P∧Q∧R)∨(P∧Q∧R)∨( P∧Q∧R) ＝(P∧Q∧ R)∨( P∧Q∧R)∨(P∧Q∧R) ＝m6∨m3∨m7 ＝ (3, 6, 7)

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

1 0

13. (1)MR

00110 0

00

MS 1

0010 1 0001 00 0

00

000 0

00

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)}.

四 证明题

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

3. (本题10分)利用形式演绎法证明：{ A∨B, C→ B, 4. (本题10分)A, B为两个任意集合，求证：

A－(A∩B) = (A∪B)－B .

1. 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。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) (5) Q→R Q(4) (6) R→S P (7) Q→S Q(5)(6) (8) Q∨S

Q(7)

2. 证明：(A-B)-C = (A∩~B)∩~C = A∩(~B∩~C) = A∩~(B∪C)

= A-(B∪C)

3. 证明：{ A∨B, C→ B, C→D}蕴涵A→D

(1) A

D(附加) (2) A∨B P (3) B

Q(1)(2)

C→D}蕴涵A→D。