《离散数学》题库及答案

（8） S （2），（7） （9） Q→S CP，（2），（8） （10） P→(Q→S) CP，（1），（9）

8、P→?Q，?P→R，R→?S =>S→?Q

证明：

（1） S 附加前提 （2） R→?S 前提 （3） ?R （1），（2） （4） ?P→R 前提 （5） P （3），（4） （6） P→?Q 前提 （7） ?Q (5），（6） （8） S→?Q CP，（1），（7）

9、P→(Q→R) => (P→Q)→(P→R)

证明：

(1) P→Q 附加前提 (2) P 附加前提 (3) Q (1),(2) (4) P→(Q→R) 前提 (5) Q→R (2),(4) (6) R (3),(5) (7) P→R CP,(2),(6)

25

(8) (P→Q) →(P→R) CP,(1),(7)

10、P→(?Q→?R)，Q→?P,S→R,P =>?S

证明：

（1） P 前提 （2） P→(?Q→?R) 前提 （3） ?Q→?R (1)，(2) （4） Q→?P 前提 （5） ?Q (1)，(4) （6） ?R (3),(5) （7） S→R 前提 （8） ?S (6)，(7)

11、A，A→B， A→C， B→(D→?C) => ?D

证明：

（1） A 前提 （2） A→B 前提 （3） B (1)，(2) （4） A→C 前提 （5） C (1)，(4) （6） B→(D→?C) 前提 （7） D→?C (3)，(6) （8） ?D (5)，(7)

12、A→(C?B)，B→?A，D→?C => A→?D

26

证明：

（1） A 附加前提 (2) A→(C?B) 前提 (3) C?B （1），（2）

(4) B→?A 前提 (5) ?B （1），（4） (6) C （3），（5） (7) D→?C 前提 (8) ?D （6），（7） (9) A→?D CP，（1），（8）

13、(P?Q)?(R?Q) ?（P?R）?Q

证明、

(P?Q)?(R?Q)

?(?P?Q)?(?R?Q) ?(?P??R)?Q ??（P?R）?Q

?(P?R)?Q

14、P?(Q?P)??P?(P??Q)

证明、 P?(Q?P)

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

27

??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) 前提 ?P （2），(3)

（4）

(5) S?P 前提 (6) S (4),(5)

16、P??Q，Q??R，R??S? ?P

证明、

(1) P 附加前提

（2） P? （3）

?Q 前提

?Q （1），（2）

?R 前提

（4） Q? (5)

?R （3），（4）

(6 ) R??S 前提

（7） R （6） （8） R??R （5），（7）

17、用真值表法证明Ｐ?Ｑ? (Ｐ?Ｑ)?(Ｑ?Ｐ)

证明、

列出两个公式的真值表：

28