《离散数学》试题及答案

(2) B无上界，也无最小上界。下界1, 3; 最大下界是3. (3) A无最大元，最小元是1，极大元8, 12, 90+; 极小元是1. 2.R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.

(1) 1 4

2 3 ??1000?(2)M1100?R????1110??

?1111??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) 812 4 6

2—

1 精选文库

5

精选文库

(2) 无最大元，最小元1，极大元8, 12; 极小元是1. (3) B无上界，无最小上界。下界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)关系图:

－

abr(R)dcabs(R)dabt(R)dc c11. 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)

—

6

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

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

?101010???00010??13. (1)M001R????0001?? MS??00?0000????0?000(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) ?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)

— 0?1?0??

1??精选文库

7

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

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

= (A∪B)∩~B = (A∩~B)∪(B∩~B) = (A∩~B)∪? = A－B

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

— 精选文库

8