R?1={（1，1），（3，1），（3，2），（4，3）} S2、解：
R1和R2的关系图略。
由关系图可知，R1是等价关系。R1不同的等价类有两个，即{a，b}和{c，d}。 由于R2不是自反的，所以R2不是等价关系。 3、解 ：
（1）真值表
P Q 0 0 0 1 1 0 1 1 ?P P??P （P??P）?Q 1 0 1 1 0 0 0 0 1 0 0 0 ?1?R?1={（2，1），（4，3）}
因此公式（1）为可满足。 （2）真值表
P Q 0 0 0 1 1 0 1 1 P?Q ?（P?Q） ?（P?Q）?Q 1 0 0 1 0 0 0 1 0 1 0 0 因此公式（2）为恒假。 （3）真值表
P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 P?Q Q?R P?R （（P?Q）?（Q?R））?（P?R） 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 21
1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 因此公式（3）为恒真。 4. 解：
?x（F（x）?G（x））
? （F（-2）?G（-2））?（F（3）?G（3））?（F（6）?G（6）） ? （1?0）?（1?0）?（0?1） ? 1 5. 解：
V1 V3 1 2 ① ② ④ ⑤ U 2 3 V V2 ③ 1 V4 从U到V的最短路为U→V1→V2→V4→V3→V。最短路权值为9。 图中圆圈中的数字为使用迪克斯特拉算法添加边的次序。 6、解：
（（A?B?C）?（A?B））?（（A?（B?C））?A） =（A?B）? A （利用两次吸收律） =（A?B）?~ A
=（A?~ A）?（B?~ A） = ??（B?~ A） = B? A 7、解：
R={（1，1），（1，2），（1，3），（2，1），（2，2），（3，1）} R的关系图为
22
1 1 2 2
3
3
4 5
关系矩阵MR= 1 1 1
1 1 0 1 0 0 0 0 0 0 0 0
1、解：
（A，?）的哈斯图为：
e
b c d
a
a为A的极小元，也是最小元； e为A的极大元，也是最大元。 9、解：
?（P?Q）?（P?Q）
?（?（P?Q）?（P?Q））?（（P?Q）??（P?Q）） ?（（P?Q）?（P?Q））?（（?P??Q）?（?P??Q）））
23
?（P?Q）?（?P??Q） 上面结果为合取范式。
利用?对?分配得：（P?Q）?（?P??Q）
?（P??P）?（P??Q）?（Q??P）?（Q??Q） ?（P??Q）?（Q??P） 上面结果为析取范式。 10、解：
?x?y（F（x，y）?F（f（x），f（y）））
? ?x（（F（x，2）?F（f（x），f（2）））?（F（x，3）?F（f（x），f（3）））） ? （F（2，2）?F（f（2），f（2）））?（F（2，3）?F（f（2），f（3）））?（F（3，2）?F（f（3），f（2）））?（F（3，3）?F（f（3），f（3）））
?（0?1）?（0?1）?（1?0）?（1?0） ? 0
11、解：首先将本题用权图来描述，于是求解此题便成为求权图中的最优支撑树问题， 按克鲁斯卡尔算法，下图为求解最优支撑树的过程：
（a） （b）
（c） （d） （e） 连接5个城市的造价最低的铁路网总造价为24（百万元）。
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）
25
《离散数学(第三版)》方世昌-的期末复习知识点总结(吐血推荐)
