《离散数学》期末复习提要.docx
《《离散数学》期末复习提要.docx》由会员分享，可在线阅读，更多相关《《离散数学》期末复习提要.docx（17页珍藏版）》请在冰点文库上搜索。
《离散数学》期末复习提要
《离散数学》期末复习提要
课程的主要内容
1、集合论部分（集合的基本概念和运算、二元关系和函数）；
2、数理逻辑部分（命题逻辑、谓词逻辑）；
3、图论部分（图的基本概念、特殊的图，树及其性质）。
一、各章复习要求与重点
第一章 命题逻辑
[复习知识点]
１、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题
２、命题公式与解释，真值表，公式分类（永真、矛盾、可满足），公式的等价
３、析取范式、合取范式，极小（大）项，主析取范式、主合取范式
４、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法）
５、全功能集
６、推理理论
本章重点内容：
命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、推理理论
[复习要求]
１、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。
２、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，公式在解释下的真值。
３、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值表将公式化为主析取（合取）范式的方法。
４、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法。
掌握24个重要等值式。
５、掌握推理理论，会写出推理的证明，掌握附加前提证明法和归谬发。
[本章重点习题]
习题P31-36:
1.1,1.7-1.9,1.12,1.18,1.19，1.15
[疑难解析]
1、公式恒真性的判定
判定公式的恒真性，包括判定公式是恒真的或是恒假的。
具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），若不全为0，则为可满足的。
二是推导法，即利用基本等价式推导出结果为1，或者利用恒真（恒假）判定定理：
公式G是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定。
这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。
2、范式
求范式，包括求析取范式、合取范式、主析取范式和主合取范式。
关键有两点：
一是准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个。
3、推理理论
掌握构造证明法，一是要理解并掌握8个推理定理，二是会使用常用的推理规则，附加前提证明法和归谬法，需要进行一定的练习。
[例题分析]
例1求
的主析取范式与主合取范式。
解
（1）求主析取范式，
方法1：
利用真值表求解
G
000
001
010
011
100
101
110
111
0
0
0
0
0
0
1
1
1
0
1
0
1
0
1
1
0
1
0
1
1
1
1
1
因此
方法2：
推导法
（2）求主合取范式
方法1：
利用上面的真值表
为0的有两行，它们对应的极大项分别为
因此，
方法2：
利用已求出的主析取范式求主合取范式
已用去6个极小项，尚有2个极小项，即
与
于是
例2试证明公式
为恒真公式。
证法一：
G=（（PQ）（QR））（PR）
=（PQ）（QR）PR
=（（（PQ）（PR）（QQ）（QR））P）R
=（（PQP）（PRP）（QRP））R
=（1（QRP））R
=QRPR
=1
故G为恒真公式。
例3构造下面的推理证明
前提：
p（q∨r）,sr,p∧s
结论：
q
证明：
①p∧s前提引入
②p①化简
③p（q∨r）前提引入
④q∨r②③假言推理
⑤s①化简
⑥sr前提引入
⑦r⑤⑥假言推理
⑧q④⑦析取三段论
推理正确。
第二章一阶逻辑
[复习知识点]
1、谓词、量词、个体词、个体域、变元（约束变元与自由变元）
2、一阶逻辑公式与解释，谓词公式的类型（永真、矛盾、可满足）
3、一阶逻辑公式等值式
4、前束范式
本章重点内容：
谓词与量词、公式与解释、前束范式
[复习要求]
1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。
2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。
3、证明等值式。
4、掌握求公式前束范式的方法。
[本章重点习题]
习题P52-55：
2.3，2.12,2.13,2.14,2.15
[疑难解析]
1、谓词与量词
反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与换名规则。
2、公式与解释
能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释I中的数值代入公式，求出真值。
3、前束范式
在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶逻辑中），将给定公式中量词提到母式之前称为首标。
[典型例题]
例1设I是如下一个解释：
F
（2）F（3）P
（2）P（3）Q（2,2）Q（2,3）Q（3,2）Q（3,3）
32011101
求
的真值。
解
例2试将一阶逻辑公式化成前束范式。
解
第三章集合的基本概念和运算
[复习知识点]
1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集
2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、对偶律等），文氏图
3、集合的计数
本章重点内容：
集合的概念、集合的运算性质、集合恒等式的证明，集合的计数
[复习要求]
1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。
2、掌握集合的表示法和集合的交、并、差、补等基本运算。
3、掌握集合运算基本规律，证明集合等式的方法。
4、掌握集合的计数。
[疑难解析]
1、集合的概念
重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。
2、集合恒等式的证明
重视吸收律和重要等价式在
证明中的特殊作用。
习题P71-75:
3.8，3.9，3.16，3.17，3.18
[例题分析]
例1设A，B是两个集合，A={1，2，3}，B={1，2}，则
。
解
于是
例2设
，试求：
（1）
；
（2）
；（3）
；
（4）
；（5）
；（6）
。
解
（1）
（2）
（3）
（4）
（5）
（6）
例3试证明
证明
第四章二元关系和函数
[复习知识点]
1、笛卡尔积，关系、关系矩阵
2、复合关系与逆关系
3、关系的性质（自反性、对称性、反对称性、传递性）
4、关系的闭包（自反闭包、对称闭包、传递闭包）
5、等价关系与等价类
6、偏序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界
7、函数及其性质（单射、满射、双射）
8、复合函数与反函数
本章重点内容：
二元关系的概念、关系的性质、关系的闭包、等价关系、映射的概念
[复习要求]
1、理解关系的概念：
二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。
2、掌握求复合关系与逆关系的方法。
3、理解关系的性质（自反性、反自反性，对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图）。
4、掌握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法。
5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元、上/下界、最小上界、最大下界的求法。
6、理解函数概念：
函数、函数相等、复合函数和反函数。
7、理解单射、满射、双射等概念，掌握其判别方法。
[疑难解析]
1、关系的概念
理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。
2、关系的性质及其判定
关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、偏序关系的基础。
要会判断关系的性质。
３、关系的闭包
在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。
关键是熟记三个定理的结论：
；定理3，
；定理4，推论
。
４、半序关系及半序集中特殊元素的确定
理解与掌握半序关系与半序集概念的关键是哈斯图。
哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。
这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。
５、映射的概念与映射种类的判定
映射的种类主要指单射、满射、双射与非单非满射。
判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。
习题P112-116:
4.4，4.25
[例题分析]
例1设集合
，判定下列关系，哪些是自反的，对称的，反对称的和传递的：
解：
均不是自反的；R4是对称的；R1,R2,R3,R4,R5是反对称的；R1,R2,R3,R4,R5是传递的。
例2、设集合
上的关系
，求出它的自反闭包，对称闭包和传递闭包。
解：
第五-七章图论
[复习知识点]
1、无向图、有向图，通路，回路，连通分支
2、关联矩阵、邻接矩阵，可达矩阵
3、二部图，欧拉图，哈密顿图，平面图
4、树
本章重点内容：
图的基本概念，特殊图的判定
[复习要求]
1、理解图的有关概念：
图、完全图、子图、图的同构。
2、掌握图的矩阵表示（关联矩阵、邻接矩阵）。
3、学会判断特殊的图。
4、理解无向树与有向树的概念。
[疑难解析]
本章的概念较多，学习时需要认真比较各概念的含义，如：
图、子图、有向图；路、简单路、回路；连通分支；二部图，欧拉图，哈密顿图，平面图；树等。
[典型例题]
例1在具有n个顶点的完全图Kn中删去多少条边才能得到树？
解：
n个顶点的完全图Kn中共有n（n-1）/2条边，
n个顶点的树应有n-1条边，
于是，删去的边有：
n（n-1）/2-（n-1）=（n-1）（n-2）/2
二、考核说明
本课程的考核按平时成绩30%期末考试70%的分配进行考核。
期末考试实行统一闭卷考核，试卷满分为100。
（考试时间为110分钟）。
1、试题类型
试题类型有选择题（分数占5%）、填空题（分数占15%）、计算题（分数占21%），证明题（分数占28%）和解答题（分数占21%）。
2、考核试卷题量分配
试卷题量在各部分的分配是：
集合论约占40%，数理逻辑约占50%，图论约占10%。
综合练习及解答
（一）填空题
1、请把“大于3而小于或等于7的整数集合”用任一种集合的表示方法表示出来A={}。
2、A，B是两个集合，A={1，2，3，4}，B={2，3，5}，则B-A=，（B）（A）=，（B）的元素个数为。
3、设
，则从A到B的所有映射。
4、设命题公式
，则使公式G为假的解释是、
和。
5、全集E={1，2，3，4，5}，A={1，5}，B={1，2，3，4}，C={2，5}，求AB=，（A）（C）=，
C=。
6、表达式xyL（x，y）中谓词的定义域是{a，b，c}，将其中的量词消除，写成与之等价的命题公式为。
（二）单项选择题（选择一个正确答案的代号，填入括号中）
1.设命题公式
，则G是（）。
A.永真的B.永假的C.可满足的D.析取范式
2、设集合
，A上的关系
，则
=（）。
3、一个公式在等价意义下，下面哪个写法是唯一的（）。
A．析取范式B．合取范式C．主析取范式D．以上答案都不对
4、设命题公式G=（PQ），H=P（QP），则G与H的关系是（）。
A．GHB．HGC．G=HD．以上都不是
5、下列命题正确的是（）。
A．{}=B．{}=C．{a}{a，b，c}D．{a，b，c}
6、设集合A={a，b，c}，A上的关系R={（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c）}，则R具有关系的（）性质。
A．自反B．对称C．传递D．反对称
7、设R为实数集，映射=RR，（x）=-x2+2x-1，则是（）。
A．单射而非满射B．满射而非单射C．双射D．既不是单射，也不是满射
8、下列语句中，（）是命题。
A．下午有会吗？
B．这朵花多好看呀！
C．2是常数。
D．请把门关上。
9、下面给出的一阶逻辑等价式中，（）是错的。
A．x（A（x）B（x））=xA（x）xB（x）
B．AxB（x）=x（AB（x））
C．x（A（x）B（x））=xA（x）xB（x）
D．xA（x）=x（A（x））
（三）计算题
1、设R和S是集合
上的关系，其中
，试求：
（1）写出R和S的关系矩阵；
（2）计算
。
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）画出R1和R2的关系图；
（2）判断它们是否为等价关系，是等价关系的求A中各元素的等价类。
3、用真值表判断下列公式是恒真？
恒假？
可满足？
（1）（PP）Q
（3）（PQ）Q
（3）（（PQ）（QR））（PR）
4.设解释I为：
（1）定义域D={-2，3，6}；
（2）F（x）：
x3；
G（x）：
x5。
在解释I下求公式x（F（x）G（x））的真值。
5、化简下式：
（（ABC）（AB））（（A（BC））A）
6、已知A={1，2，3，4，5}，B={1，2，3}，R是A到B的二元关系，并且R={（x，y）|xA且yB且2x+y4}，画出R的关系图，并写出关系矩阵。
7、求命题公式（PQ）（PQ）的析取范式与合取范式。
（四）证明题
1、证明等价式
。
2、构造推理证明：
蕴涵Q。
3、A，B，C为任意的集合，证明：
（AB）C=A（BC）
4、利用一阶逻辑的基本等价式，证明：
xy（F（x）G（y））=xF（x）yG（y）
5有向图
如图所示。
（1）求
的邻接矩阵
；
（2）
中
到
长度为4的路径有几条？
（3）
中
到自身长度为3的回路有几条？
（4）
是哪类连通图？
升级会员 