= 1.
5. (1)
(2) 无最大(3) B无上
841262元，最小元1，极大元8, 12; 极小元是1.
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)关系图:
－
abr(R)dcabs(R)6
dabt(R)dc c
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?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 (2) ?R→P (3) P→Q (4) ?R→Q (5) ?Q→R (6) R→S (7) ?Q→S (8) Q∨S
P Q(1) P Q(2)(3) Q(4) P Q(5)(6) Q(7)
－
－
－
2. 证明：(A-B)-C = (A∩~B)∩~C
7
= A∩(~B∩~C) = A∩~(B∪C) = A-(B∪C)
3. 证明：{?A∨B, ?C→?B, C→D}蕴涵A→D
(1) A
D(附加) P Q(1)(2) P Q(4) Q(3)(5) P Q(6)(7) D(1)(8)
(2) ?A∨B (3) B
(4) ?C→?B (5) B→C (6) C
(7) C→D (8) D
(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
所以：A－(A∩B) = (A∪B)－B.
8
电大《离散数学》模拟试题及答案
