发布时间 : 星期六 文章《离散数学》试题及答案更新完毕开始阅读
= = (
((x)∨(x)∧
(y))∨(y))∨
(x) (x)
= (x =
P(x)∧yQ(y))∨(z)
xyz((P(x)∧Q(y))∨R(z))
9. 设R是集合A = {a, b, c, d}. R是A上的二元关系, R = {(), (), (), ()},
(1) 求出r(R), s(R), t(R)； (2) 画出r(R), s(R), t(R)的关系图. 解：（1）
r(R)＝R∪＝{(), (), (), (), (), (), (), ()},
s(R)＝R∪R＝{(), (), (), () (), ()},
t(R)＝R∪R∪R∪R＝{(), (), (), (), (), (), (), (), ()}；
(2)关系图:
11. 通过求主析取范式判断下列命题公式是否等价：
abr(R)dcabs(R)dabt(R)2
3
4
－1
dcc (1) G = (P∧Q)∨(P∧Q∧R)
P∧R))
(2) H = (P∨(Q∧R))∧(Q∨(解： G＝(P∧Q)∨(
＝(P∧Q∧
P∧Q∧R)
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∧(
P∧Q∧R) ＝(P∧Q∧＝m6∨m3∨m7
的主析取范式相同，所以G = H.
13. 设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a,
R)∨(
P∧Q∧R)∨(P∧Q∧R)
P∧Q∧R)
P∧Q∧R)∨(P∧Q∧R)∨
R)∨(P∧Q∧R)∨(
a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}.
(1) 试写出R和S的关系矩阵； (2) 计算R?S, R∪S, R, S?R. 解：
－1
－1
－1
(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)}.
四、证明题
1. 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。 解：
(1) P∨R P (2)
R→P Q(1)
(3) P→Q P (4) (5)
R→Q Q(2)(3) Q→R Q(4)
(6) R→S P (7)
Q→S Q(5)(6)
(8) Q∨S Q(7)
2. 设为任意集合，证明：() = (B∪C). 解： () =
3. (本题10分)利用形式演绎法证明：{→D}蕴涵A→D。 解：
(1) A D(附加) (2)
A∨B P
A∨B, C→B, C
(3) B Q(1)(2) (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. (本题10分)A, B为两个任意集合，求证： A－(A∩B) = (A∪B)－B . 解： 4. A－(A∩B)
= A∩~(A∩B) ＝A∩(∪)