= (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. (9分)设一阶逻辑公式：G = (?xP(x)∨?yQ(y))→?xR(x)，把G化成前束范式. G = (?xP(x)∨?yQ(y))→?xR(x)

9. 设R是集合A = {a, b, c, d}. R是A上的二元关系, R = {(a,b), (b,a), (b,c), (c,d)},

(1) 求出r(R), s(R), t(R)； (2) 画出r(R), s(R), t(R)的关系图.

(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)关系图:

－

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

abr(R)dcabs(R)dabt(R)dc c11. 通过求主析取范式判断下列命题公式是否等价：

(1) G = (P∧Q)∨(?P∧Q∧R)

(2) H = (P∨(Q∧R))∧(Q∨(?P∧R)) 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.

13. 设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)},

S＝{(a, b),(b, c),(b, d),(d, d)}. (1) 试写出R和S的关系矩阵； (2) 计算R?S, R∪S, R1, S1?R1.

－

－

－

?1?0(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。 证明：{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

P Q(1) P Q(2)(3) Q(4) P

－

－

－

(7) ?Q→S Q(5)(6) (8) Q∨S

Q(7)

2. 设A,B为任意集合，证明：(A-B)-C = A-(B∪C). 证明：(A-B)-C = (A∩~B)∩~C = A∩(~B∩~C) = A∩~(B∪C)

= A-(B∪C)

3. (本题10分)利用形式演绎法证明：{?A∨B, ?C→?B, 证明：{?A∨B, ?C→?B, C→D}蕴涵A→D

(1) A

D(附加) (2) ?A∨B P (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∩(~A∪~B) ＝(A∩~A)∪(A∩~B) ＝?∪(A∩~B) ＝(A∩~B)

C→D}蕴涵A→D。 ＝A－B 而 (A∪B)－B

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

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

参考答案

一、填空题

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

n27. ?1= {(a,1), (b,1)}, ?2= {(a,2), (b,2)},?3= {(a,1), (b,2)}, ?4= {(a,2), (b,1)}; ?3, ?4. 8. (P∧?Q∧R). 9. 12, 3.

10. {4}, {1, 2, 3, 4}, {1, 2}. 11. 自反性；对称性；传递性. 12. (1, 0, 0), (1, 0, 1), (1, 1, 0).