（4） ?P （2），(3) (5) S?P 前提 (6) S (4),(5) 16、P??Q，Q??R，R??S? ?P 证明、
(1) P 附加前提 （2） P??Q 前提 （3） ?Q （1），（2） （4） Q??R 前提 (5) ?R （3），（4） (6 ) R??S 前提 （7） R （6） （8） R??R （5），（7）
17、用真值表法证明Ｐ?Ｑ? (Ｐ?Ｑ)?(Ｑ?Ｐ) 证明、
列出两个公式的真值表：
P Q P?Q （P?Q）?（Q?P） F F T T F T F F T F F F T T T T 由定义可知，这两个公式是等价的。 18、P→Q?P→(P?Q) 证明、
设P→(P?Q)为F，则P为T，P?Q为F。所以P为T，Q为F ，从而P→Q也为F。所以P→Q?P→(P?Q)。 19、用先求主范式的方法证明(P→Q)?(P→R) ? (P→（Q?R） 证明、
先求出左右两个公式 的主合取范式 (P→Q)?(P→R) ?(?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)
(P→（Q?R）) ?(?P?（Q?R）)
16
?(?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)??(Q?R) ??P 证明、
设(P→Q)??(Q?R)为T，则P→Q和?(Q?R)都为T。即P→Q和?Q??R都为T。故P→Q，?Q和?R)都为T，即P→Q为T，Q和R都为F。从而P也为F，即?P为T。从而(P→Q)??(Q?R) ??P 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