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. 15. D 三、计算证明题 1. (1)
842112639 (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)
2 3 1 4 ?1?1(2)MR???1??1000?100??
110??111?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.
6 / 17第 6 页 共 17 页
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无
6. G = ?(P→Q)∨(Q∧(?P→R)) 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 / 17第 7 页 共 17 页
8412621元，最小元1，极大元8, 12; 极小元是1.
上界，无最小上界。下界1, 2; 最大下界2.
= ?(?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∧
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)关系图:
br(R)cadabs(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
8 / 17第 8 页 共 17 页
＝? (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)}, R1＝{(a, a),(c, a),(c, b),(d, c)}, S1?R1＝{(b, a),(d, c)}. 四 证明题
1. 证明：{P→Q, R→S, P∨R}蕴涵Q∨S
(1) P∨R
P
－
－
－
(2) ?R→P (3) P→Q
Q(1)
P
(4) ?R→Q (5) ?Q→R (6) R→S
Q(2)(3) Q(4)
P
(7) ?Q→S (8) Q∨S
Q(5)(6)
Q(7)
2. 证明：(A-B)-C = (A∩~B)∩~C
= A∩(~B∩~C) = A∩~(B∪C) = A-(B∪C)
9 / 17第 9 页 共 17 页
3. 证明：{?A∨B, ?C→?B, C→D}蕴涵A→D
(1) A
D(附加) P Q(1)(2)
P Q(4)
(2) ?A∨B (3) B
(4) ?C→?B (5) B→C (6) C
Q(3)(5)
P
(7) C→D (8) D
Q(6)(7)
D(1)(8)
(9) A→D
所以 {?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
10 / 17第 10 页 共 17 页
离散数学试题及答案
