离散数学课后习题合集(3)

=?(?) =

?(0,1,2,3)

=(?P??Q)?(?P?Q)?(P??Q)?(P?Q) 1.9 用把公式化为主范式的方法判断下列各题中两式是否等价

（1）(P?Q)?(P?Q),(?P?Q)?(Q?P) 解

（1）(P?Q)?(P?Q)

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

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

?(2,3)

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

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

=(?P?Q??Q)?(?P?Q?P) =F?F =F =

?(?)

由此可见两公式的主析取范式不相等，因此，两公式不等价。 （2）(P?R)?(Q?R),(P?Q)?R 解

(P?R)?(Q?R)

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

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

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

?(2,4,6)

11

(P?Q)?R

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

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

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

?(2,4,6)

由此可见两公式的主合取范式相等，因此，两公式等价。 12

第二章 命题演算的推理理论

2.1 用永真公理系统证明下列公式

（1）P?(P?P)

证明

（1）P?P 公理1 （2）(P?R)?((Q?R)?((P?Q)?R)) 公理13 （3）(P?P)?((P?P)?((P?P)?P)) Q,R用P代入 （4）（3）（1） (P?P)?((P?P)?P) 分（5）（4）（1） (P?P)?P 分（6）P?(P?Q) 公理11 （7）P?(P?P) Q用P代入 （8）(P?Q)?((Q?P)?(P?Q)) 公理7 （9）(P?(P?P))?(((P?P)?P)?(P?(P?P))) Q用P?P代入 （10）((P?P)?P)?(P?(P?P)) 分（9）（7） （11）P?(P?P) 分（10）（5） （2）(?P?Q)?(?Q?P) 证明

（1）(P??Q)?(Q??P) 公理14 （2）(?P???Q)?(?Q???P) P用?P代入，Q用?Q代入 （3）??P?P 公理15 （4）(P?Q)?((R?P)?(R?Q)) 定理 （5）(??P?P)?((?Q???P)?(?Q?P))

P用??P代入，Q用P代入，R 用?Q代入

13

（6）(?Q???P)?(?Q?P) 分（5）（3） （7）(P?Q)?((Q?R)?(P?R)) 公理3 （8）((?P???Q)?(?Q???P))?(((?Q???P)?(?Q?P)) ?((?P???Q)?(?Q?P)))

P用?P???Q代入，Q用?Q???P代入，R用?Q?P代入

（9）（8）（2） ((?Q???P)?(?Q?P))?((?P???Q)?(?Q?P)) 分（10）(?P???Q)?(?Q?P) 分（9）（6） （11）Q???Q 定理 （12）(Q???Q)?((?P?Q)?(?P???Q))

（4）式中P用Q代入，Q用??Q代入，R用?P代入

（13）（12）（11） (?P?Q)?(?P???Q) 分（14）((?P?Q)?(?P???Q))?(((?P???Q)?(?Q?P))? ((?P?Q)?(?Q?P)))

（7）式中P用?P?Q代入，Q用?P???Q代入，R用?Q?P代入

((?P???Q)?(?Q?P))?((?P?Q)?(?Q?P)) 分（15）（14）（13） (?P?Q)?(?Q?P) 分（16）（15）（10）

（3）P??P 证明

P?(P?Q) 公理11 （1）

（2）P?(P??P) Q用?P代入 （3）(P?Q)?(?Q??P) 定理

(P?(P??P))?(?(P??P)??P) Q用P??P代入 （4）

（5）?(P??P)??P 分（4）（3）

14

（6）Q?(P?Q) 公理12 （7）?P?(P??P) Q用?P代入 （8）(P?Q)?((Q?R)?(P?R)) 公理3 （9）(?(P??P)??P)?((?P?(P??P))?(?(P??P)?(P??P)))

P用?(P??P)代入，Q用?P代入，R用P??P代入

（10）(?P?(P??P))?(?(P??P)?(P??P)) 分（9）（5） （11）（10）（7） ?(P??P)?(P??P) 分（12）(?P?P)?P 定理 （13）(?(P??P)?(P??P))?(P??P) P用P??P代入 （14）（13）（11） P??P 分（4）((P?Q)??R)?((P???Q)??R)

证明

（1）??P?P 公理1 （2）??Q?Q P用Q代入 （3）(P?Q)?((R?P)?(R?Q)) 定理 （4）(??Q?Q)?((P???Q)?(P?Q)) P用??Q代入，R用P代入 （5）(P???Q)?(P?Q) 分（4）（2） （6）(P?Q)?((Q?R)?(P?R)) 公理3 （7）((P???Q)?(P?Q))?(((P?Q)??R)?((P???Q)??R))

P用P???Q代入，Q用P?Q，R用?R代入

（8）((P?Q)??R)?((P???Q)??R) 分（7）（5） 2.2 已知公理：A: P?(Q?P)

B: (Q?R)?((P?Q)?(P?R)) C: (P?P)?P

15