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

D: Q?(P?Q) E: (P?Q)?(Q?P) 及分离规则和代入规则。

试证明（1）P?P为定理

（2）(P?P)?(R??R)为定理。 证明

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

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

(R??R)?(P?P) 分（9）（8）（7）

（10）(P?Q)?(Q?P) 公理E （11）((R??R)?(P?P))?((P?P)?(R??R))

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

（12）(P?P)?(R??R) 分（11）（9） 2.3 用假设推理系统证明下列公式

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

P?Q 假设 （1）

（2）P??Q 假设

16

（3）??P 后件的否定 （4）??P?P 公理15 （5）P 分（4）（3） （6）（1）（5） Q 分（7）?Q 分（2）（5） （6）（7）矛盾

由反证法推理定理知

P?Q，P??Q├?P

由推理定理知

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

（2）(P?(Q?R))?((P?Q)?(P?R)) 证明

（1）P?(Q?R) （2）P?Q （3）P （4）Q?R （5）Q （6）R 由假设推理过程的定义知

P?(Q?R)，P?Q，P├R

由推理定理知

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

（3）((P?Q)?R))?(P?(Q?R)) 证明

（1）(P?Q)?R （2）P （3）Q （4）P?(Q?(P?Q)) （5）Q?(P?Q) 假设 假设 假设 分（1）（3） 分（2）（3） 分（4）（5） 假设

假设 假设 公理10 分（4）（2）

17

（6）P?Q 分（5）（3） （7）R 分（1）（6） 由假设推理过程的定义知

(P?Q)?R)，P，Q├R

由推理定理知

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

（4）((P?Q)?((P?R)?(Q?S)))?(S?R) 证明

（1）(P?Q)?((P?R)?(Q?S)) 假设 （2）(P?Q)?P 公理8 （3）(P?Q)?Q 公理9 （4）((P?Q)?((P?R)?(Q?S)))?(P?Q)

（2）式中P用P?Q代入，Q用(P?R)?(Q?S)代入

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

（3）式中P用P?Q代入，Q用(P?R)?(Q?S)代入

（6）P?Q 分（4）（1）

(P?R)?(Q?S) 分（7）（5）（1）

（8）P 分（2）（6） （9）（3）（6） Q 分（10）((P?R)?(Q?S))?(P?R)（2）式中P用P?R，Q用Q?S代入 （11）((P?R)?(Q?S))?(Q?S)（3）式中P用P?R，Q用Q?S代入 （12）P?R 分（10）（7） （13）Q?S 分（11）（7） （14）R 分（12）（8） （15）S 分（13）（9） （16）P?(Q?(P?Q)) 公理10

18

（17）R?(S?(R?S)) P用R，Q用S代入 （18）S?(R?S) 分（17）（14） （19）（18）（15） R?S 分由假设推理过程的定义知

(P?Q)?((P?R)?(Q?S))├R?S

由推理定理知

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

2.4 用归结原理证明下列公式

（1）((P?Q)?((P?R)?(Q?S)))?(S?R) 证明

化为合取范式：

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

=((P?Q)?((?P?R)?(?Q?S)))?(?S??R) =P?Q?(?P?R)?(?Q?S)?(?S??R) 建立子句集 （1）P （2）Q

（3）?P?R （4）?Q?S

（5）?S??R

（6）R （7）?S （8）?Q （9）? （2）(P?Q)?((P??Q)??P) 证明

化为合取范式：

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

1）（3）归结 5）（6）归结 4）（7）归结 2）（8）归结 19

（ （ （ （

建立子句集： （1）?P?Q （2）?P??Q （3）??P

（4）Q （1）（3）归结 （5）?Q （2）（3）归结 （6）? （3）?(P??Q)?(?Q?R)??R??P 证明

化为合取范式：

?(P??Q)?(?Q?R)??R???P =(?P?Q)?(?Q?R)??R???P 建立子句集： （1）?P?Q （2）?Q?R

（3）?R （4）??P

（5）Q …… 此处隐藏：249字，全部文档内容请下载后查看。喜欢就下载吧 ……