《离散数学》练习题和参考答案

?(?P?Q)?(?P?R)

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

它们有一样的主合取范式，所以它们等价。 20、(P→Q)?证明、 设(P→Q)??(Q?R) ??P

?(Q?R)为T，则P→Q和?(Q?R)都为T。即P→Q和?Q??R都为T。故P→Q，?Q和?R)都为T，即

?(Q?R) ??P

P→Q为T，Q和R都为F。从而P也为F，即?P为T。从而(P→Q)?21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效? 前提: (1) 若A队得第一，则B队或C队获亚军; 若C队获亚军，则A队不能获冠军; 若D队获亚军，则B队不能获亚军; A 队获第一;

结论: (5) D队不是亚军。 证明、

设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A?（B?C），C??A，D??B，A；结论符号化为 ?D。

本题即证明 A?（B?C），C??A，D??B，A??D。 （1） A 前提 （2） A?（B?C）前提 （3） B?C （1），（2） （4） C??A 前提 （5） ?C （1），（4） （6） B （3），（5） （7） D??B 前提 （8） ?D （6），（7）

22、用推理规则证明P?Q, ?(Q?R),P?R不能同时为真。 证明、

(1) P?R 前提 (2) P (1) (3) P?Q 前提 (4) Q (2),(3) (5) ?(Q?R) 前提

17

(6) ?Q??R (5) (7) ?Q (6) (8) ?Q?Q (4),(7)

(集合论部分)

四、设Ａ，Ｂ，Ｃ是三个集合，证明： 1、A? (B－C)＝(A?B)－(A?C) 证明：

(A?B)－(A?C)= (A?B) ?A?C=(A?B) ?（A?C） =(A?B?A)?(A?B?C)= A?B?C=A?（B?C） =A?（B-C）

2、(A－B)?(A－C)=A－(B?C) 证明：

(A-B)?(A-C)=(A?B)?(A?C) =A? (B?C) =A?B?C= A-(B?C)

3、A?B=A?C，A?B=A?C，则C=B 证明：

B=B?(A?A)=(B?A)? (B?A) =(C?A)? (C?A)=C?(A?A)=C 4、A?B=A?(B-A) 证明：

A?(B-A)=A?(B?A)=(A?B)?(A?A) =(A?B)?U= A?B 5、A=B ? A?B=? 证明：

?设A=B，则A?B=（A-B）?（B-A）=???=?。

?设A?B=?，则A?B=（A-B）?（B-A）=?。故A-B=?，B-A=?，从而A?B，B?A，故A=B。

6、A?B = A?C，A?B=A?C，则C=B 证明：

B=B?(A?B)= B?(A?C)= (B?A)?(B?C) = (A?C)?(B∩C)= C?(A?B) = C?(A?C) =C

18

7、A?B=A?C，A?B=A?C，则C=B 证明：

B=B?(A?A)=(B?A)?(B?A) =(C?A)?(C?A)=C?(A?A) =C

8、A－(B?C)＝(A－B)－C 证明：

A－(B?C)= A?B?C =A?(B?C)=(A?B)?C =(A-B)?C=(A-B)-C

9、(A－B)?(A－C)=A－(B?C) 证明： (A-B)?(A－C) =(A?B)?(A?C) =(A?A)?(B?C) =A?B?C=A－(B?C) 10、A-B=B，则A=B=? 证明：

因为B=A-B，所以B=B?B=（A-B）?B=?。从而A=A-B=B=?。 11、A=(A-B)?(A-C)?A?B?C=? 证明：

? 因为(A-B)?(A-C) =(A?B)?(A?C) =A?(B?C)

=A?B?C= A-(B?C)，且A=(A-B)?(A-C)， 所以A= A-(B?C)，故A?B?C=?。

? 因为A?B?C=?，所以A-(B?C)=A。而A-(B?C)= (A-B)?(A-C)，

所以A=(A-B)?(A-C)。 12、(A-B)?(A-C)=??A?B?C 证明：

? 因为(A-B)?(A-C) =(A?B)?(A?C) =A?(B?C)

=A?B?C= A-(B?C)，且(A-B)?(A-C)=?， 所以?= A-(B?C)，故A?B?C。

19

? 因为A?B?C，所以A-(B?C)=A。而A-(B?C)= (A-B)?(A-C)，

所以A=(A-B)?(A-C)。 13、(A-B)?(B-A)=A ? B=? 证明：

? 因为(A-B)?(B-A)=A，所以B-A?A。但(B-A)?A=?，故B-A=?。

即B?A，从而B=?（否则A-B?A，从而与(A-B)?(B-A)=A矛盾）。

? 因为B=?，所以A-B=A且B-A=?。从而(A-B)?(B-A)=A。

14、(A-B)-C?A-(B-C) 证明：

?x?(A-B)-C，有x?A-B且x?C，即x?A，x?B且x?C。

从而x?A，x?B-C，故x?A-(B-C)。从而(A-B)-C?A-(B-C) 15、P(A)?P(B)?P(A?B) （P(S)表示S的幂集） 证明：

?S?P(A)?P(B)，有S?P(A)或S?P(B)，所以S?A或S?B。

从而S?A?B，故S?P(A?B)。即P(A)?P(B)?P(A?B) 16、P(A)?P(B)=P(A?B) （P(S)表示S的幂集） 证明：

?S?P(A)?P(B)，有S?P(A)且S?P(B)，所以S?A且S?B。

从而S?A?B，故S?P(A?B)。即P(A)?P(B)?P(A?B)。

?S?P(A?B)，有S?A?B，所以S?A且S?B。

从而S?P(A)且S?P(B)，故S?P(A)?P(B)。即P(A?B)?P(A)?P(B)。 故P(A?B)=P(A)?P(B)

17、（A-B）?B=（A?B）-B当且仅当B=?。 证明：

? 当B=?时，因为（A-B）?B=（A-?）??=A，（A?B）-B=（A??）-? =A，所以（A-B）?B=（A?B）-B。 ? 用反证法证明。假设B??，则存在b?B。因为b?B且b? A?B，所以b?（A?B）-B。而显然b?（A-B）?B。

故这与已知（A-B）?B=（A?B）-B矛盾。

五、证明或解答：

（数理逻辑、集合论与二元关系部分）

1、设个体域是自然数，将下列各式翻译成自然语言： (1) ?x?y（xy=1）; (2) ?x?y(xy=1); (3) ?x?y (xy=0); (4) ?x?y（xy=0）;

20