离散数学--期末复习.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).x3；(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+24当且仅当王红没努力学习离散数学。(7)4或6是素数.(8).王晓聪明，但是他不用功.(9)如果今天是1号，则明天是5号。(10).小潘不能既跳舞又唱歌。(11)如果你来了，他就唱歌而且陪你跳舞。(12).或者雪是黑色的，或者太阳从东方升起。(13).王晓既用功又聪明。 (14)2 + 2 4 当且仅当美国位于非洲。(15)小李学过英语或法语。 (16）如果石头会说话，那么月亮上就会出现海洋。(17）.如果天气寒冷，小梅就不去游泳 。（18）小红喜欢看书和画画。p qp qpqpq0 000110 101101 001001 111113、会求命题公式的真值表，当一个命题公式中的命题变项被指定具体某组真值时，能求整个公式的真值。 练习：请回答下列问题。（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(qr)(pqr)（3）、（4）、（5）、（6）、(pq) (pr) （7）、(qp)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.22.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)1010101013、求公式的前束范式。（注意：代替规则与换名规则的使用，等值式、基本等值式、量词否定等值式、量词辖域收缩与扩张等值式（只有遇到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(BC)=A(BC)。是否正确？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=，则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,yAxy(mod)2，(或R=|x,yAxy(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的12341234哈斯图如右图所示，则关系R的表达式为？第5章 图的基本概念1、掌握图的基本概念：图，环，平行边，平凡图(只有一个顶点的零图，实际上是只有一个孤立点的图)，简单图，顶点的度练习：求下列各图中指定点的度（1）设图G = ，如右图所示，则b的入度= ， a的度= ，b的出度= ，d的度= 。（2）设图G = ，如右图所示，则v1的入度= ，v1的出度= .（3）设图G = ，如右图所示，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=为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题）