?(P?R)?Q
14、P?(Q?P)??P?(P??Q)
证明、
P?(Q?P)
??P?(?Q?P) ??(?P)?(?P??Q) ??P?(P??Q)
15、（P?Q）?（P?R），?(Q?R)，S?P?S
证明、
(1) （P?Q）?（P?R） 前提
（2） P? (Q?R) (1) （3） ?(Q?R) 前提 （4） ?P （2），(3) (5) S?P 前提 (6) S (4),(5)
16、P??Q，Q??R，R??S? ?P
证明、
(1) P 附加前提
（2） P??Q 前提 ?R 前提 ?S 前提
（3） ?Q （1），（2） （4） Q? (5) ?R （3），（4） (6 ) R? （7） R （6） （8） R??R （5），（7）
17、用真值表法证明Ｐ?Ｑ? (Ｐ?Ｑ)?(Ｑ?Ｐ)
证明、
列出两个公式的真值表：
P Q P?Q （P?Q）?（Q?P） F F F T T F T T T T F F F F 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）) ?(?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队获亚军;
(2) 若C队获亚军，则A队不能获冠军; (3) 若D队获亚军，则B队不能获亚军; (4) 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) 前提 (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=?，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)
B-A=?，从而
= (A?C)?(B∩C)= C?(A?B) = C?(A?C) =C
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)，
离散数学复习题及答案
