发布时间 : 星期一 文章《离散数学(第三版)》方世昌 的期末复习知识点总结复习进程更新完毕开始阅读ec44dac703020740be1e650e52ea551811a6c97c
（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）为可满足。 （2）
真值表 P Q 0 0 0 1 1 0 1 1 因此公式（2）为恒假。 （3）
真值表 P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 P?Q Q?R P?R （（P?Q）?（Q?R））?（P?R） P?Q ?（P?Q） ?（P?Q）?Q 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 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到U 2 3 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，R的关系图为
）} 1 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））） ?（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、解：首先将本题用权图来描述，于是求解此题便成为求权图中的最优支撑树问题，
按克鲁斯卡尔算法，下图为求解最优支撑树的过程：