离散数学--期末复习.doc

离散数学知识要点总结
第1章 命题逻辑
1、会判断一个语句是否为命题（如P31-习题1.1题）
练习：判断下列语句是否为命题。

(1).3+8=13；
(2).离散数学是计算机系的一门必修课；
(3).太阳系以外的星球上有生物；
(4).你打算考硕士研究生吗？
(5).9+512 ；
(6). 天上有三个月亮。
(7).x+5 > 6；
(8).一定要努力学习！
(9).2是素数；
(10).x+5 > 6；
(11).我正在说谎；
(12).x=13.
(13).这朵花多好看呀！
(14).7能被2整除.
(15).我用的计算机CPU主频是1G吗？
(16).蓝色和黄色可以调成绿色；
(17). 雪是黑色的.
(18). 明天会下雨吗？；
(19).我能进来吗？ (20).这个男孩真勇敢呀！
(21).蓝色和黄色可以调成绿色；
(22).x≤3；
(23)地球饶着太阳转. (24)青年人多么朝气蓬发呀！
(25).5能被2整除.
(26).嫦娥一号太棒了！
(27).台湾是中国的一部分；
(29) 你下午有会吗？若无会，请到我这儿来！
(30).请不要讲话！
(31) 5是奇数；
(32).

2、注意五个命题联结词的使用，会将命题进行符号化（如P32-1.3，1.4，1.5题的题型）或在判断体现逻辑联结词的逻辑有关系等。
练习：将以下命题符号化

(1)如果你不去逛街，那么我也不去逛街。
(2)小李边吃饭边看电视。
(3)林芳学过英语或日语。
(4)张辉与王丽都是三好生.
(5)小王住在101室或102室。
(6).2+2≠4当且仅当王红没努力学习离散数学。
(7)4或6是素数.
(8).王晓聪明，但是他不用功.
(9)如果今天是1号，则明天是5号。
(10).小潘不能既跳舞又唱歌。

(11)如果你来了，他就唱歌而且陪你跳舞。
(12).或者雪是黑色的，或者太阳从东方升起。
(13).王晓既用功又聪明。
(14)2 + 2 ≠ 4 当且仅当美国位于非洲。
(15)小李学过英语或法语。
(16）如果石头会说话，那么月亮上就会出现海洋。
(17）.如果天气寒冷，小梅就不去游泳 。
（18）小红喜欢看书和画画。

p q
p ∧q
p∨q
p→q

0 0
0
0
1
1
0 1
0
1
1
0
1 0
0
1
0
0
1 1
1
1
1
1

3、会求命题公式的真值表，当一个命题公式中的命题变项被指定具体某组真值时，能求整个公式的真值。
练习：请回答下列问题。
（1）设p，q 的真值为0，r，s的真值为1，则公式的真值是？

（2）设p，q的真值为1，r，s的真值为0，则公式的真值是？
（3）设p，q 的真值为0，r，s的真值为1,则公式的真值是？
（4）设p，q 的真值为0，r，s的真值为1,则公式的真值是？
（5）设p，q 的真值为0，r，s的真值为1,则公式的真值是？
在画真值表时注意的知识点：一个命题公式中含有n个原子命题，则对其所有可能赋值有 2n 种。

4、会判断一个命题公式的类型（包括：重言式（永真式），矛盾式（永假式），可满足式）,(如P33-1.7，1.9题，方法可以用真值表，也可以用等值演算，但是如果指定方法，必须按指定方法做。)
练习：判断下列公式的类型

（1）；
（2）；（3）； (4)
（5）．； （6）．；（7）．
(8)（9）．；（10）．；（11）．；(12)（13）（14）．；（15）．；（16

5、掌握基本等值式，并会运用基本等值式，会证明等值式，会判断公式的类型：方法一，真值表法，方法二，等值演算法。（如P34-1.8，1.9题题型）
练习：证明下列等值式。
（1） （2）
（3） （4）
6、关于主析取范式与主合取范式的求法及应用。（例1.14,习题1.12题型。）
要求：会判断什么是极小项与极大项，并会求主析取范式与主合取范式，可以通知所求式子判断成真赋值与成假赋值，及判断命题公式类型。

（1）、
（2）、(p∨(q∧r))→(p∨q∨r)
（3）、
（4）、
（5）、
（6）、﹁(p∧q) ↔﹁(﹁p→r)
（7）、(﹁q∨﹁p)→r
（8）、

7、命题逻辑推理
掌握基本理论，基本推理定律规则。见课本与课堂的练习题
（1）如果教练教得好而且我努力练习，那么我就一定能学好轮滑。我努力练习了，但我还是没有学好轮滑。所以是教练教得不好。
（2）如果今天我没有课，则我去机房上机或去图书馆查资料。若机房没有空机器，则我没法去上机。今天我没课，机房也没有空机器。所以我去图书馆查资料。
（3）或者C++程序设计难学，或者学生喜欢C++程序设计。如果编程语言容易学，那么C++程序设计并不难学。因此，如果学生不喜欢C++程序设计，那么编程语言并不容易学。
（4）今天或者天晴或者下雨。如果天晴，我去看电影。若我去看电影，我就不看书。我今天在看书。所以今天下雨。
（5）若星期天不下雪且能买到票，我就去体育馆看球。我买到票了，但是我没有去体育馆看球。所以星期天下雪了。
（6）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以小赵喜欢数学。
(7)如果今天是星期五，那么我会有离散数学或数字逻辑考试。如果离散数学老师有事，那么没有离散数学考试。今天是星期五且离散数学老师有事。所以我有一次数字逻辑考试。
（8）若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以，明天不是星期一和星期三.

8、一些综合知识的认知。
练习：判断下列语句是否正确。

（1）、矛盾式一定不是可满足式，可满足式也一定不是矛盾式。
（2）、的逻辑关系是：是的充分必要条件。
（3）、若A至少存在一种赋值是成假赋值，则称A为矛盾式。
（4）、若A至少存在一种赋值是成真赋值，则称A为重言式。
（5）、一般地说，排斥或不能用的方式表示.
（6）、的逻辑关系是：是的必要条件。
（7）在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的.
（8）、矛盾式一定不是可满足式，但可满足式可能是矛盾式。
（9）、含有联结词“和”的命题一定是复合命题。
（10）五个基本联结词的运算顺序是：Ø，Ú，Ù，«，®。

第2章 一阶逻辑
1、一阶逻辑中的命题符号化问题（要求：注意区分全称量词与存在量词的提取，注意命题的个体域（若题目没有特别指明时，均指全总个体域），如何引入特性谓词。例2.2—2.5，P52—习题2.1，2.3）在引入特性量词后，使用全称量词与存在量词符号化的形式是不同的，则有全称量词时，“所有的……是……”应表示为："x(A(x)®B(x))，存在量词时，“存在……是……”应表示为：$x(A(x)ÙB(x))。

练习：
（1）没有不爱看电影的人。
（2）并非所有的人都喜欢吃辣椒。
（3）素数不全是奇数。
（4）没有一个人不爱美。
（5）没有不吃饭的人。
（6）没有不呼吸的人。
（7）在北京工作的人未必都是北京人。
(8)每个兔子都比某些乌龟跑得快。
(9)任何人都喜欢某些花。

2、解释：要求在给定解释下求公式的真值。（如P44-例2.7，2.8）
练习：论域D={1，2，3}，特定元素a=1，指定谓词P为如下表，则公式的的真值为？
P (1,1)
P (1,2)
P (1,3)
P (2,1)
P (2,2)
P (2,3)
P (3,1)
P (3,2)
P (3,3)
1
0
1
0
1
0
1
0
1

3、求公式的前束范式。（注意：代替规则与换名规则的使用，等值式、基本等值式、量词否定等值式、量词辖域收缩与扩张等值式（只有遇到®B时量词才互换）、量词分配等值式，P48-例题2.11，P54-习题2.14，2.15）
练习：（1）"x(F(x,y) ®$y(G(x,y)ÙH(x,z))) （2）
（3） （4）
3、一些基本概念：变量的约束出现、变量的自由出现、闭式、解释，逻辑有效式，矛盾式，可满足式，代换实例。

第3章 集合的基本概念和运算
1、集合的相关概念：空集、子集、幂集、基数
设A为一有限集合，|A|=n，那么A的子集个数为 。
练习：（1）设A={1,2,3}，B=P(A)，则|P(B)|=（ ）
（2）设，则 P(P(S)) 有（ ）个元素
（3）设A={} ，B=Р(Р(A))，则P(B)有( )个元素。

2、注意集合中元素与集合的关系及集合与集合的关系的表示。例如：
（1）下列关系式正确的是（ ）。

（2）下列关系式正确的有（ ）
A）φÍφ且φÍ{φ}， B)φÍφ且φ∈{φ}， C)φ∈φ且φ∈{φ} D）φ∈φ且φÍ{φ}

3、有关集合的计数问题，特别是对两个基本事件与三个基本事件的情形（P73-3.5，3.6，课堂练习）

练习：
（1）设集合A的基数｜A｜=4，集合B的基数|B|=5，且集合A与集合B有3个相同的元素，则（ ）
（2）某幼儿园大班一共有28个小朋友，其中有15人学钢琴，12人学围棋，有5人兼学钢琴和围棋，那么有多少人没有学钢琴也没有学围棋？
（3）如练习3.6中从1到300的整数中，有多少个不能被3也不能被5整除的数。
4、本章节中特别一些基本概念的准确性认知。
练习：判断下列语句是否正确。
（1）如果集合A有6个元素，则A的子集最多有5个元素。
（2）任何集合都至少含有一个元素。
（3）任何一个集合都不可以是另一个集合的元素。

第4章 二元关系与函数
1、笛卡尔积的定义与计算及相关性质：
（1）语句“A，B，C为任意集合，若，则。”是否正确？
（2）设A、B、C为任意的三个集合，则笛卡尔积：A×(B×C)=A×(B×C)。是否正确？
2、二元关系的定义与表示：
练习：（1），，则A至B的笛卡尔积？从A到B有多少个不同的二元关系，A上的有多少个不同的二元关系?

3、表示二元关系的方法：描述、关系矩阵、关系图。（注意几种方法表示关系是一一对应，给出其中一个都要能表示出其他，例如给出关系矩阵，要能写出表达式中的具体元素，能画出关系图。）
练习：设A={2，3，4，5，6}上的二元关系，，则R的表达式为？关系矩阵为?关系图为？

4、关系的运算：关系的定义域、值域、域，逆、合成、F在A上的限制、A在F下的像，会求关系的幂。（课本练习题与留过的作业，P107——例4.28重点）
练习：P107—例4.28一共有十六种不同的情形：设R和S是P上的关系，P是所有人的集合，，，则
（1）表示
（2）表示
（3）表示 。
（4）表示关系。
（5）表示.
（6）表示。
（7）表示.
（8）表示.
（9）表示.
(10) 表示.
（11）表示.
(12) 表示.
(13)表示
(14) 表示。
(15) 表示
(16) 均表示 。

5、关系的性质的讨论（自反性、对称性、反对称性、传递性）（注意从关系图观察更方便）（P114页—4.4）
（1）自反关系的关系图中每一个结点都有环。
（2）对称关系的关系图中，如果两个结点间有有向边，则必成对出现。
（3）反对称关系的关系图中，如果两个结点间有有向边，则必不是成对出现的。
（4）传递关系的关系图中，如果有从结点a到结点b的有向边，同时又有从结点b到结点c的有向边，则必定有从结点a到结点c的有向边。
练习：（1）判断下列关系的所具有的性质。

（2）设集合A={a，b，c}，A上的关系R={< a，a >，< a，b >，< b，b >，< c，c >，< c，b >}，则R具备什么性质？不具备什么性质？
特别注意:(1) 一个关系可以既不是对称的，也不是反对称的。
(2) 一个关系可以既是对称的，也是反对称的。
一些特殊关系的性质如下：
（1）空关系是对称的、反对称的和传递的。
（2）全关系是自反的、对称的和传递的。
（3）恒等关系是自反的、对称的、反对称的和传递的。

6、会求关系的闭包（自反闭包，对称闭包，传递闭包）。
练习：（1）设，A上的关系 ，
a)求出的关系矩阵。b)画出的关系图。c)求出自反闭包对称闭包传递闭包.
(2) 设集合上的二元关系R的关系矩阵,
a)求出关系R的表示式，b)画出R的关系图，c) R具有哪些性质？ d) 求出的表达式。

7、关于等价关系：（要求会从定义上判断一个关系是否为等价关系，会求等价类，商集，理解等价关系的商集与集合的划分是一一对应的。）
定义：设R是集合A上的二元关系，如果关系R同时具有自反性、对称性和传递性，则称R是等价关系。
练习：
（1）前面6中的练习（2）加一问e) 它是一个等价关系吗？为什么？
(2):设，A上的关，要求：（a）请画出关系R的关系矩阵与关系图；（b）R是否为等价关系，请说明理由；
（c）若R是等价关系，请求出关系R的所有等价类与求商集A/R。
(3) 设集合A={1，2，3，4，5，6}，A上的关系R满足：R={<x,y>|x,y∈A∧x≡y(mod)2}，(或R={<x,y>|x,y∈A∧x≡y(mod)3}，)
（a）请写出关系R的元素，画出关系R的关系矩阵与关系图； （b）R是否为等价关系，请说明理由；
（c）若R是等价关系，请求出关系R的所有等价类与求商集A/R。
（4）试判断下列关系到是否为等价关系.

1）在一群人所组成的集合上定义的“同姓”关系；
2）在一群人所组成的集合上定义的“朋友”关系；
3）整数集上的“小于”关系；
4）整数集上的“等于”关系；
5）直线间的“平行”关系；
6）幂集上的“Í”关系。

8、关于偏序关系：（会定义，会画偏序关系的哈斯图，会根据哈斯图写出关系的表达式）。
定义：设R是集合A上的二元关系，如果关系R同时具有自反性、反对称性和传递性，则称R是偏序关系。
练习：设A={1，2，3，4}，其上偏序关系R的
1
2
3
4
1
2
3
4
哈斯图如右图所示，则关系R的表达式为？

第5章 图的基本概念
1、掌握图的基本概念：图，环，平行边，平凡图(只有一个顶点的零图，实际上是只有一个孤立点的图)，简单图，顶点的度
练习：求下列各图中指定点的度
（1）设图G = < V，E >，如右图所示，则b的入度= ， a的度= ，b的出度= ，d的度= 。
（2）设图G = < V，E >，如右图所示，则v1的入度= ，v1的出度= .
（3）设图G = < V，E >，如右图所示，v2的
= 。（4）v3的度= 。
2、理解“握手定理”及其推理的定理内容，并能熟练应用定理。
握手定理：任意无向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所有顶点入度之和等于出度之和等于边数.
握手定理推论 在任何无向图和有向图中，奇度顶点的个数必为偶数.所以不存在有5个度数为奇数的顶点。
练习：请回答下列各题。
（1）、设一个图有20个顶点，且所有顶点的度数都为3，则这个图中有多少条边？
（2）、已知图G有10条边, 4个3度顶点, 其余顶点的度数均为2度,则这个图中有多少个顶点？
（3）、已知图G有16条边, 每个顶点的度数均为2度,，则这个图中有多少个顶点？
（4）、已知图G有12条边, 其中有3个4度点，其余的顶点的度数均为3度,，则这个图中有多少个顶点？
（5）、已知图G有28条边, 其中有4个3度点，其余的顶点的度数均为4度,，则这个图中有多少个顶点？
（6）存在有5个度数为奇数的顶点吗？

3、会判断一组数组是否为图的度数列。
练习：给定下列序列，可以构成无向图的结点度数的序列有：（ ），
能构成无向简单图的结点度数序列的有：（ ）。
（1）、（1，1，2，2，3）；（2）、（1，1，2，2，2）；（3）、（5, 5, 4, 4, 2, 1）；（4）、（1，3，4，4，5）；
（5）、（1，3，2，2，3）；（6）、（1，3，2，2，2）；（7）、（3, 5, 4, 2, 2, 1）；（8）、（2，2，2，2，2）；
（9）、（1，1，2，5，2）；（10）、（1，1，3，3，3）；（11）（3，2，2，4，2）；（12）（1，4，2，2，3）；
（13）、（1，3，2，5，2）；（14）、（2，3，2，2，2）；（15）、（3，3，3，3，3）。
4、会求一个图的补图：设G=<V,E>为n阶无向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图. 练习：求下列图的补图。

5、会判断图的连通性（有向图与无向图）
特别是对于有向图有：一个有向图，如果它是强连通图，那么它一定是单向连通图，也一定是弱连通图。但是反之不然。

6、会求矩阵的邻接矩阵和关联矩阵，可达矩阵。（课本例题）
练习：求下列矩阵的邻接矩阵

（1） （2） （3） （4） （5）

练习：有向图G，如上图（1）所示，a) 求的邻接矩阵;b) 中v1到v3长度为3的路径有几条？分别是什么路径？c) 中v1到自身长度为3的回路有几条？d)求出G的可达矩阵P。

第6章 一些特殊的图
会判断一图是否为欧拉图或说是否可以一笔画，或是否为哈密顿图。
例如：下面那一个图可一笔画出（欧拉图）（无向图是欧拉图的充要条件是图连通且无奇度的顶点。）一笔画出：连通的无向图G若度数为奇数的结点个数为0个或2个则可一笔画出。

第7章 树
1、无向树的基本定义与性质：（P157-定理7.1）
无向树：连通且不含回路的无向图称为无向树，简称树。
重要性质：树是连通且无回路的无向图，则顶点个数n与边数m之间有m=n-1.
结合树的定义与性质和握手定理有一些重要的应用计算。（可以演变很多个题，注意知识点）
练习：(1)在一棵树中有7片树叶，3个3度顶点，其余都是4度顶点，则该树有多少个4度顶点？
（2）一棵树有2个4度顶点，3个3度顶点，其余顶点都是树叶，则该树有多少片树叶？
（3）一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有多少片树叶？
（4）在一棵树中有8片树叶，2个3度结点，其余都是4度结点，则该树有多少个4度结点？
（5）一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为多少？
(6) 设G是有6个顶点的完全图，则从G中删去多少条边可以得到树？

2、最优生成树的求法（课堂练习与课本-7.8题）