* *
1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。
2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。
3、理解用解释的方法证明等价式和蕴涵式。 4、掌握求公式前束范式的方法。 [本章重点习题]
P120，1，2； P125~126，1，3； P137，1。 [疑难解析]
1、谓词与量词
反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则。
2、公式与解释
能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释I中的数值代入公式，求出真值。
3、前束范式
在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶逻辑中），将给定公式中量词提到母式之前称为首标。 [典型例题]
例1 设I是如下一个解释：D??2,3?
F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3) 3 2 0 1 1 1 0 1
* *
求?x?y?P?x??Q?F?x?,y??的真值。 解
?x?y?P?x??Q?F?x?,y????x??P?x??Q?F?x?,2????P?x??Q?F?x?,3??????P?2??Q?F?2?,2????P?2??Q?F?2?,3??????P?3??Q?F?3?,2????P?3??Q?F?3?,3??????0?0???0?1?????1?1???1?1???0?1?1
例2 试将一阶逻辑公式化成前束范式。 解
G??x??yP?x,y?????yQ?y??R?x?????x??yP?x,y????y?Q?y??R?x???
??x??yP?x,y???z?Q?z??R?x????x?y?z?P?x,y???Q?z??R?x??
第五章 图论
[复习知识点]
1、图、完全图、子图、母图、支撑子图、图的同构 2、关联矩阵、相邻矩阵
3、权图、路、最短路径，迪克斯特拉算法（Dijkstra） 4、树、支撑树、二叉树
5、权图中的最小树，克鲁斯卡尔算法（Kruskal） 6、有向图、有向树
本章重点内容： 权图的最短路、二叉树的遍历、权图中的最优支撑树 [复习要求]
1、理解图的有关概念：图、完全图、子图、母图、支撑子图、图的同构。 2、掌握图的矩阵表示（关联矩阵、相邻矩阵）。
* *
3、理解权图、路的概念，掌握用Dijkstra算法求权图中最短路的方法。
4、理解树、二叉树与支撑树的有关概念；掌握二叉树的三种遍历方法，用Kruskal算法求权图中最小树的方法。 5、理解有向图与有向树的概念。 [本章重点习题]
P221，2；P225，1；P231，2，3；P239，5；P242，1，2。 [疑难解析]
1.本章的概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简单路、回路等，这些都是图的基本概念，今后将在数据结构、数据库、计算机网络等课程中用到。
2、权图中的最短路
严格执行迪克斯特拉（Dijkstra）算法步骤，从起点起，到每一点求出最短路，然后进行仔细比较，最后到达终点，算出最小权和。
3、权图中的最优支撑树
权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔（Kruskal）算法。 [典型例题]
例1 在具有n个顶点的完全图Kn中删去多少条边才能得到树？ 解：n个顶点的完全图Kn中共有n?（n-1）/2条边，
n个顶点的树应有n-1条边，
于是，删去的边有：n?（n-1）/2-（n-1）=（n-1）?（n-2）/2
例2 求下面有限图中点u到各点间的最短路。（图上数字见教材P231，第3题。）
* *
解 u?u1 ， d(u, u1)=1, 路(u, u1)
u? u2 , d(u, u2)=9, 路(u, u4, u3, u7, u2)
u? u3 , d(u, u3)=5, 路(u, u4, u3 ,) u? u4 , d(u, u4)=3, 路(u, u4 )
u? u5 , d(u, u5)=11, 路(u, u1, u5)或路 (u, u4, u3 , u7 , u2 , u5) u? u6 , d(u, u6)=13, 路(u, u1, u5, u6) u? u7 , d(u, u7)=8, 路(u, u4 , u3 , u7) u? u8 , d(u, u8)=11, 路(u, u4, u8)
u?v, d(u, v)=15, 路(u, u1, u5 , u6 ,v) 或路(u, u4 , u3 , u7 , u6 ,v)
二、考核说明
本课程的考核实行形成性考核和终结性考核的形式。形成性考核占总成绩的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），
《离散数学(第三版)》方世昌的期末深刻复习知识点归纳含例题
