《离散数学(第三版)》方世昌 的期末复习知识点总结复习进程

（a） （b）

（c） （d） （e）

连接5个城市的造价最低的铁路网总造价为24（百万元）。

（四）证明题 1、

证明：

(?P?(?Q?R))?(Q?R)?(P?R)?(?P?(?Q?R))?((Q?P)?R)?((?P??Q)?R)?((Q?P)?R) ?((?P??Q)?(Q?P))?R?(?(P?Q)?(P?Q))?R?1?R?R2、证明：

（1）S?T 规则P （2）?T 规则P

（3）?S 规则Q，根据（1）、（2）和基本蕴涵式（12）

（4）?S?R 规则P

（5）R 规则Q，根据（3）、（4）和基本蕴涵式（11） （6）P??R 规则P

（7）?P 规则Q，根据（5）、（6）和基本蕴涵式（12） （8）P?Q 规则P

（9）Q 规则Q，根据（7）、（8）和基本蕴涵式（10） 3、证明：

（A?B）?C=（A?~B）?~C = A?（~B?~C） = A?~（B?C） = A?（B?C） 4、证明：

?x?y（F（x）?G（y））=?x（F（x）??y G（y）） = ?x（?F（x）??y G（y）） = ?x（?F（x））??y G（y） = ??xF（x）??y G（y） = ?xF（x）??yG（y）