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

2、设A={a，b，c，d}，R1，R2是A上的关系，其中R1={（a，a），（a，b），（b，a），（b，b），（c，c），（c，d），（d，c），（d，d）}，R2={（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）}。 （1） （2）

画出R1和R2的关系图；

判断它们是否为等价关系，是等价关系的求A中各元素的等价

类。

3、用真值表判断下列公式是恒真？恒假？可满足？

（1）（P??P）?Q （2）?（P?Q）?Q

（3）（（P?Q）?（Q?R））?（P?R） 4、设解释I为：

（1） （2）

定义域D={-2，3，6}； F（x）：x?3；

G（x）：x?5。

在解释I下求公式?x（F（x）?G（x））的真值。

5、求下图所示权图中从u到v的最短路，画出最短路并计算它们的权值。

V1 7 V3 1

U 2 5 3 V

4

V2 1 V4

6、化简下式：

（（A?B?C）?（A?B））?（（A?（B?C））?A）

7、已知A={1，2，3，4，5}，B={1，2，3}，R是A到B的二元关系，并且R={（x，y）|x?A且y?B且2? x+y ?4}，画出R的关系图，并写出关系矩阵。

8、画出下面偏序集（A，?）的哈斯图，并指出集合A的最小元、最大元、极大元和极小元。其中A={a，b，c，d，e}，?={（a，b），（a，c），（a，d），（a，e），（b，e），（c，e），（d，e）}?IA。 9、求命题公式?（P?Q）?（P?Q）的析取范式与合取范式。 10、给定解释I如下：

定义域D={2，3}；

f（2） f（3） F（2，2） F（2，3） F（3，2） F（3，3）

3 2 0 0 1 1

求?x?y（F（x，y）?F（f（x），f（y）））。

11、设有5个城市v1，v2，v3，v4，v5，任意两城市之间铁路造价如下：（以百万元为单位）

6 2 w（v1，v2）=4， w（v1，v3）=7， w（v1，v4）=16， w（v1，v5）=10， w（v2，v3）=13， w（v2，v4）=8， w（v2，v5）=17， w（v3，v4）=3， w（v3，v5，）=10， w（v4，v5）=12 试求出连接5个城市的且造价最低的铁路网。 （四）证明题

1、证明等价式(?P?(?Q?R))?(Q?R)?(P?R)?R。

2、利用形式演绎法证明：{P?Q,P??R,S?T,?S?R,?T}蕴涵Q。

3、A，B，C为任意的集合，证明：

（A?B）?C=A?（B?C）

4、利用一阶逻辑的基本等价式，证明：

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

练习解答

（一）填空题

1、列举；描述；A={4，5，6，7}或A={x|3?x?7} 2、{5}；{{5}，{2，5}，{3，5}，{2，3，5}}；8

3、?1={（a，1），（b，1）}；?2={（a，2），（b，2）}；?3={（a，1），（b，2）}；?4={（a，2），（b，1）} 4、（1，0，1）； （1，1，1）； （1，0，0） 5、28； 7

6、{5}；{?，{5}}；{1，3，4}

7、笛卡尔积（或直乘积）；{（x，y）|x?A且y?B}；二元关系

8、并且（或合取）；或者（或析取）；蕴涵

9、（L（a，a）?L（a，b）?L（a，c））?（L（b，a）?L（b，b）?L（b，

c））?（L（c，a）?L（c，b）?L（c，c））

10、点；连接某些不同点对的边；一对不同点之间最多有一条边 （二）单项选择题（选择一个正确答案的代号，填入括号中） 1、C 2、A 3、C 4、A 5、C 6、A 7、B 8、D 9、C 10、A （三）计算题 1、解：（1）

?1?0MR???0??0010?010??,001??000??0?0MS???0??0100?011?? 000??001?（2）R?S={（1，2），（3，4）}

R?S={（1，1），（1，2），（1，3），（2，3），（2，4）， （3，4），（4，4）}

R?1={（1，1），（3，1），（3，2），（4，3）} S?1?R?1={（2，1），（4，3）} 2、解：

R1和R2的关系图略。

由关系图可知，R1是等价关系。R1不同的等价类有两个，即{a，b}和{c，d}。

由于R2不是自反的，所以R2不是等价关系。 3、解 ：