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

（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、解：首先将本题用权图来描述，于是求解此题便成为求权图中的最优支撑树问题，

按克鲁斯卡尔算法，下图为求解最优支撑树的过程：