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

二、考核说明

本课程的考核实行形成性考核和终结性考核的形式。形成性考核占总成绩的20%，以课程作业的形式进行（共三次，由中央电大统一布置）；终结性考核即期末考试，占总成绩的80%。总成绩为100分，60分及格。

期末考试实行全国统一闭卷考核，试卷满分为100。由中央电大统一命题，统一评分标准，统一考试时间（考试时间为120分钟）。

1、试题类型

试题类型有填空题（分数约占20%）、单项选择题（分数约占14%）、计算题（分数约占50%）和证明题（分数约占16%）。

填空题和单项选择题主要涉及基本概念、基本理论，重要性质和结论、公式及其简单计算。计算题主要考核学生的基本运算技能，要求书写计算、推论过程或理由。证明题主要考查应用概念、性质、定理及主要结论进行逻辑推理的能力，要求写出推理过程。

2、考核试卷题量分配

试卷题量在各部分的分配是：集合论约占40%，数理逻辑约占40%，图论约占20%。

具体课程考核情况见课程考核说明。

附录：试题类型及规范解答举例 [填空题] 1. 设R

是集合A上的二元关系，如果关系R同时具有 性、对称性和

性，则称R是等价关系。

2. 命题公式G=（P?Q）?R，则G共有 个不同的解释；把G在其所有

解释下所取真值列成一个表，称为G的 ；解释（?P，Q，?R）或（0，1，0）使G的真值为 。

3. 设G=（P，L）是图，如果G是连通的，并且 ，则G是树。如果根

树T的每个点v最多有两棵子树，则称T为 。 [单项选择题]（选择一个正确答案的代号，填入括号中） 1. 由集合运算定义，下列各式正确的有（ ）。

A．

X?X?Y B.X?X?Y C.X?X?Y D.Y?X?Y

2. 设R1，R2是集合A={a，b，c，d}上的两个关系，其中R1={（a，a），

（b，b），（b，c），（d，d）}，R2={（a，a），（b，b），（b，c），（c，b），（d，d）}，则R2是R1的（ ）闭包。 A．自反 B．对称 C．传递 D．以上都不是

3. 设G是由5个顶点组成的完全图，则从G中删去（ ）条边可以得到

树。

A．4 B．5 C．6 D．10 [计算题] 1. 化简下式：

（A?B?C）?（（A?B）?C）?（A?B?C）?（A?B?C） 2. 通过求主析取范式判断下列命题公式是否等值。

（1）（P?Q）?（?P?Q?R）；

（2）（P?（Q?R））?（Q?（?P?R））；

3. 求图中A到其余各顶点的最短路径，并写出它们的权。

B 7 C 1 2

6

A 2 5 3 D 4 E 1 F [证明题]

1. 利用基本等价式证明下面命题公式为恒真公式。

（（P?Q）?（Q?R））?（P?R）

2. 用形式演绎法证明：{P?Q， R?S，P?R }蕴涵Q?S。 试题答案及评分标准 [填空题] 1、 2、 3、

自反；传递 8；真值表；1 无回路；二叉树

[单项选择题]（选择一个正确答案的代号，填入括号中） 1、 A 2、 B 3、C [计算题] 1. 解：

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

=（（A?~B）?E）?（（A?B）?E） E为全集 =（A?~B）?（A?B） = A?（~B?B） = A?E = A 2. 解：

（P?Q）?（?P?Q?R）

?（P?Q?（?R?R））?（?P?Q?R） ?（P?Q??R）?（P?Q?R）?（?P?Q?R） ? m6?m7?m3 ? m3?m6?m7

（P?（Q?R））?（Q?（?P?R））

?（P?Q） ?（Q?R）?（P??P?R）?（?P? Q ?R） （分配律） ?（P?Q?（?R?R）） ?（（?P?P）?Q?R）?（?P? Q ?R） ?（P?Q??R） ?（P?Q?R） ?（?P?Q?R）?（P?Q?R）?（?P? Q ?R）

? m6?m7?m3?m7?m3 ? m3?m6?m7

由此可见 （P?Q）?（?P?Q?R）? （P?（Q?R））?（Q?（?P?R）） 3. 解：

A到B的最短路径为AB，权为1； A到E的最短路径为ABE，权为3； A到F的最短路径为ABEF，权为4； A到C的最短路径为ABEFC，权为7；