《离散数学》试题及答案

1. 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。 2. 设A,B为任意集合，证明：(A-B)-C = A-(B∪C).

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

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

参考答案

一、填空题

1. {3}; {{3},{1,3},{2,3},{1,2,3}}. 2. 2.

n23.

1

= {(a,1), (b,1)}, ,

4

2

= {(a,2), (b,2)},

3

= {(a,1), (b,2)},

4

= {(a,2), (b,1)};

3

.

4. (P∧Q∧R). 5. 12, 3.

6. {4}, {1, 2, 3, 4}, {1, 2}. 7. 自反性；对称性；传递性. 8. (1, 0, 0), (1, 0, 1), (1, 1, 0).

9. {(1,3),(2,2),(3,1)}; {(2,4),(3,3),(4,2)}; {(2,2),(3,3)}. 10. 2

m

n

.

11. {x | -1≤x < 0, xR}; {x | 1 < x < 2, xR}; {x | 0≤x≤1, xR}. 12. 12; 6.

13. {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}. 14. x(P(x)∨Q(x)). 15. 21.

16. (R(a)∧R(b))→(S(a)∨S(b)).

17. {(1, 3),(2, 2)}; {(1, 1),(1, 2),(1, 3)}. 二、选择题

1. C. 2. D. 3. B. 4. B. 5. D. 6. C. 7. C.

8. A. 9. D. 10. B. 11. B. 13. A. 14. A. 三、计算证明题 1. (1)

84211263915. D

(2) B无上界，也无最小上界。下界1, 3; 最大下界是3. (3) A无最大元，最小元是1，极大元8, 12, 90+; 极小元是1. = {(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 ?1?1(2)MR???1??13. (1)?

(2)?(3)?(4)?(5)?

000?100??

110??111?(x)+3＝2x+3＝2x+3.

＝((x))＝＝＝＝?

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

)＝?

+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) 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. (1)

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

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

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

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

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

Q∧

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

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

= 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)

xP(x)∧yQ(y))∨zR(z) xyz((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∪R＝{(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)},

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

2

3

4

－1

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) ＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) ＝m6∨m3∨m7 ＝

(3, 6, 7)

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

?1?013. (1)MR???0??0010??0?0010?? MS??001??0??000??0100?011??

000??001?(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)}.