下载文档原格式
第1章集合及其运算考核知识点1．集合，元素，集合的表示，全集，空集2．集合的包含、相等，子集，幂集3．集合的并、交、补、差、对称差等运算及其运算律4．容斥原理考核要求1．理解集合的概念，容斥原理．2．理解集合的包含、子集、相等和幂集等概念，熟练掌握集合的表示方法和集合的并、交、补、差和对称差等运算，会用文氏图表示集合的各种运算．3．掌握用集合运算基本规律证明集合恒等式的方法．4．掌握利用容斥原理进行计数的方法．第2章关系与函数考核知识点1．有序对和笛卡儿积2．关系及其运算性质3．二元关系的矩阵与图4．复合关系与逆关系5．二元关系的性质6．等价关系与等价类7．偏序关系、复盖集与哈斯图，极大(小)元，最大(小)元，上(下)界，最小上界，最大下界8．函数反函数复合函数单射满射和双射考核要求1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算．2．理解关系的概念：包括二元关系、空关系、全关系、恒等关系．掌握关系的集合表示、关系矩阵和关系图，掌握关系的运算．3．掌握求复合关系和逆关系的方法．4．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性)，掌握其判别方法．5．理解等价关系和偏序关系概念，掌握等价关系、偏序关系的判定，掌握等价类、复盖集的求法和作偏序关系哈斯图的方法．知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界．6．理解函数概念：函数(映射)，函数相等，复合函数和反函数．7．理解单射、满射和双射等概念，掌握其判别方法．第3章图的基本概念与性质考核知识点1．图的概念与表示，有向图，无向图，简单图，完全图，结点的度数，图的同构，子图、补图2．通路，通路的长度，初级通路，简单通路，回路，初级回路，简单回路3．图的连通性与连通度概念、判定，点割集与割点，边割集与割边4．图的矩阵表示、邻接矩阵、可达性矩阵及其计算5．最短路径考核要求1．理解图的基本概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、图的同构子图等，理解握手定理．2．了解通路与回路的概念：简单通路、初级通路和复杂通路，简单回路、初级回路和复杂回路，会求通路和回路的长度．3．了解无向图的连通性，会求无向图的连通分支．了解点割集、割点、边割集、割边、点连通度、边连通度等概念．4．了解有向图的强连通性、单向连通性、弱连通性；会判别有向图连通性的类型．5．理解图的矩阵表示法、邻接矩阵、可达性矩阵的概念，掌握邻接矩阵、可达性矩阵的有关计算．6．知道最短路径的概念，会最短路径的算法．第4章几种特殊图考核知识点1．欧拉通路(回路)，欧拉图2．哈密顿通路(回路)，哈密顿图3．平面图，欧拉公式4．对偶图及着色考核要求1．了解欧拉回路、欧拉图的概念及性质，掌握欧拉图的判别方法．2．了解汉密尔顿回路、汉密尔顿图的概念及性质，掌握汉密尔顿图的判别方法．3．了解平面图的概念：平面图、面、边界、面的次数和非平面图，掌握平面图的判别方法，掌握欧拉公式的应用．4．理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握着色算法；5．掌握图论中常用的证明方法．第5章树及其应用考核知识点1．树的定义及性质2．生成树与最小生成树的概念，最小生成树的Kruskal算法3．根树的概念及性质4．最优树的概念，最优树的Huffman算法，前缀码的求法考核要求1．了解无向树、树叶、分支点、平凡树、生成树和最小生成树等概念及性质，掌握最小生成树的Kruskal算法．2．了解有向树、根树、有序树、最优二元（叉）树等概念及性质，掌握最优树的Huffman 算法．3．掌握利用最优树产生前缀码的方法．第6章命题逻辑考核知识点1．命题与联结词(否定、析取、合取、蕴含、等价)，真值与真值表2．命题公式的解释3．命题公式的等值式与蕴涵式，等值演算4．析取范式、合取范式、极小(大)项，主析取范式、主合取范式的概念与求法5．命题逻辑的推理理论考核要求1．理解命题联结词概念，掌握命题公式的翻译（命题符号化）及判断语句是不是命题的方法．2．熟练掌握求给定公式真值表的方法．3．掌握基本等值式以及用真值表法和等值演算法判别公式类型和公式等值的方法．4．了解析取(合取)范式概念，理解极小(大)项的概念和主析取(合取)范式概念，熟练掌握用基本等值式或真值表将公式化为主析取(合取)范式的方法．5．掌握命题公式的的直接证明方法与间接证明方法．第7章谓词逻辑考核知识点1．谓词，量词，个体词，个体域，变元2．谓词公式的解释3．前束范式的概念与求法4．谓词公式的等值式与蕴涵式5．谓词逻辑的推理理论考核要求1．理解谓词、量词、个体词、个体域、全域、原子公式、谓词公式和变元等概念．掌握谓词公式的翻译．2．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．3．掌握谓词演算的等值式和重言蕴含式．4．了解前束范式的概念，会求谓词公式的前束范式的方法．5．了解谓词逻辑推理的规则，掌握谓词公式的证明与推导方法．。
方法、知识点总结（知识重点和考题重点）前三章重点内容（知识重点）：1、蕴含（条件）“→”的真值P→Q的真值为假，当且仅当P为真，Q为假。
2、重言(永真)蕴涵式证明方法<1>假设前件为真，推出后件也为真。
<2>假设后件为假，推出前件也为假。
易错3、等价公式和证明中运用4、重要公式重言蕴涵式：P∧Q => P or QP or Q => p∨QA->B =>(A∧or∨C)->(B∧or∨C)其他是在此基础上演变等价公式：幂等律P∧P=P P∨P=P吸收律P∧(P∨Q)=P P∨(P∧Q)=P同一律P∨F=P P∧T=PP∨T=T P∧F=FP <-> Q = (P->Q)∧(Q->P) = (P∧Q)∨(﹁P∧﹁Q)5、范式的写法（最方便就是真值表法）6、派遣人员、课表安排类算法：第一步：列出所有条件，写成符号公式第二步：用合取∧连接第三步：求上一步中的析取范式即可7、逻辑推理的写法直接推理论证：其中I公式是指重言蕴涵式那部分其中E公式是指等价公式部分条件论证: 形如~ , ~, ~ => R->SR P(附加条件)......S TR->S CP8、谓词基本内容注意：任意用—> 连接存在用∧连接量词的否定公式量词的辖域扩充公式量词分配公式其他公式9、带量词的公式在论域内的展开10、量词辖域的扩充公式11、前束范式的写法给定一个带有量词的谓词公式，1)消去公式中的联接词→和←→(为了便于量词辖域的扩充)；2)如果量词前有“﹁”，则用量词否定公式﹁”后移。
再用摩根定律或求公式的否定公式，将“﹁”后移到原子谓词公式之前；3)用约束变元的改名规则或自由变元的代入规则对变元换名(为量词辖域扩充作准备)；4)用量词辖域扩充公式提取量词，使之成为前束范式形式。
简要概括：1、去-> ，<-> 2、移﹁3、换元4、量词辖域扩充12、谓词演算的推理理论推理规则：P、T、CP、US、ES、EG、UG 的使用ES US 去量词EG UG 添量词★谨记：ES要在US之前,很重要添加量词注意事项：13、集合的幂集（用P表示，也常有花P表示）A是集合，由A的所有子集构成的集合，称之为A的幂集。
离散数学知识点总结 一、各章复习要求与重点第一章 集 合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求]1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。
2、掌握集合的表示法和集合的交、并、差、补等基本运算。
3、掌握集合运算基本规律，证明集合等式的方法。
4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。
[本章重点习题]P5~6，4、6； P14~15，3、6、7； P20，5、7。
[疑难解析] 1、集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。
2、集合恒等式的证明通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。
实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~⋂=-证明中的特殊作用。
[例题分析]例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。
解}}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A}}2,1{},2{},1{,{)(φρ=B于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ例2 设{}{}Φ=,,,,b a b a A ，试求：(1){}b a A ,-； (2)Φ-A ； (3){}Φ-A ； (4){}{}A b a -,； (5)A -Φ； (6){}A -Φ。
解 (1){}{}{}Φ=-,,,b a b a A (2)A A =Φ- (3){}{}{}b a b a A ,,,=Φ- (4){}{}Φ=-A b a , (5)Φ=-ΦA (6){}Φ=-ΦA 例3 试证明()()()()B A B A B A B A ~~~~⋂⋃⋂=⋃⋂⋃ 证明()()()()()()()()()()()()()()()()()()B A B A B A B A B B B A A B A A B B A A B A B A B A ~~~~~~~~~~~~~⋂⋃⋂=Φ⋃⋂⋃⋂⋃Φ=⋂⋃⋂⋃⋂⋃⋂=⋂⋃⋃⋂⋃=⋃⋂⋃第二章 二元关系[复习知识点]1、关系、关系矩阵与关系图2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse ）、极大/小元、最大/小元、上/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念 [复习要求]1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。
《离散数学》期末复习大纲（完整版）（含例题和考试说明)一、命题逻辑[复习知识点］1、命题与联结词(否定￢、析取∨、合取∧、蕴涵→、等价↔）,复合命题2、命题公式与赋值(成真、成假）,真值表,公式类型（重言、矛盾、可满足),公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论本章重点内容:命题与联结词、公式与解释、(主)析取范式与（主)合取范式、公式类型的判定、命题逻辑的推理［复习要求]1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法.2、理解公式与赋值的概念;掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。
3、了解析取(合取）范式的概念；理解极大（小）项的概念和主析取(合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取)范式的方法.4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。
5、掌握命题逻辑的推理理论。
[疑难解析］1、公式类型的判定判定公式的类型,包括判定公式是重言的、矛盾的或是可满足的。
具体方法有两种，一是真值表法,二是等值演算法。
2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。
关键有两点:一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律）,结果的前一步适当使用幂等律，使相同的短语(或子句）只保留一个.3、逻辑推理掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法(直接证明法、附加前提证明法和归谬法）. 例1.试求下列公式的主析取范式:(1）))()((P Q Q P P ⌝∨⌝⌝∧→→；（2）)))((R Q Q P P →⌝∨→⌝∨（))()(())()((:)1P Q Q P Q P P P Q Q P P ∧∧∨∧∧⌝∨⌝=∧∧∨⌝∨⌝=原式解Q P P P Q P P Q P ∨⌝=∨⌝∧∨⌝=∧∨⌝=)()()())(())((Q P P Q Q P ∧∨⌝∨∨⌝∧⌝=)()()(Q P Q P Q P ∧∨∧⌝∨⌝∧⌝=)))((()))(((:)2R Q Q P P R Q Q P P ∨∨∨∨=→⌝∨→⌝∨解)()()()(R Q P R Q P R Q P R Q P R Q P ∧⌝∧∨∧∧⌝∨⌝∧∧⌝∨∧⌝∧⌝=∨∨=)()()(R Q P R Q P R Q P ∧∧∨⌝∧∧∨⌝∧⌝∧∨）2．用真值表判断下列公式是恒真?恒假？可满足？（1)（PP ）Q （2)（P Q)Q （3）（（P Q)(Q R ））（P R) 解：（1） 真值表 P QP P P （P P)Q 0 01 0 1 0 11 0 0 1 00 0 1 1 1 0 0 0因此公式(1)为可满足.（2） 真值表P Q P Q （P Q) （P Q）Q0 0 1 0 00 1 1 0 01 00 1 01 1 1 0 0因此公式（2）为恒假。
第八章函数主要内容1. 函数的基本概念与性质（单射，满射，双射）2. 函数的合成与反函数学习要求1. 掌握：函数、A到B的函数、集合在函数下的像、集合在函数下的完全原像的概念及表示法；当A与B都是有穷集时，会求A到B的函数的个数2. 掌握：A到B的函数是单射、满射、和双射的定义及证明方法3. 掌握：常函数、恒等函数、单调函数、特征函数、自然映射等概念4. 掌握：合成函数的主要性质和求合成函数的方法5. 掌握：反函数的概念及主要性质8.1 函数的定义与性质一．函数和像函数是一种特殊的二元关系。
定义8.1设F为二元关系，若x∈domF都存在唯一的y∈ranF使xFy成立，则称F为函数(函数也可以称作映射)。
对于函数F，如果有xFy，则记作y=F(x)，并称y为F在x 的值。
例8.1设F1={<x1,y1>,<x2,y2>,<x3,y2>}F2={<x1,y1>,<x1,y2>}判断它们是否为函数。
解F1是函数，F2不是函数，因为对应于x1存在y1和y2满足x1F2y1和x1F2y2，与函数定义矛盾。
由于函数是集合，可以用集合相等来定义函数的相等。
定义8.2设F，G为函数，则F=G F G∧G F由以上定义可知，如果两个函数F和G相等，一定满足下面两个条件：1．domF=domG2．x∈domF=domG都有F(x)=G(x)例如函数F(x)=(x2-1)/(x+1)，G(x)=x-1是不相等的，因为domF={x|x∈R∧x≠-1} 而domG=R。
domF≠domG。
定义8.3设A，B为集合，如果f为函数，且domf=A，ranf B，则称f为从A到B的函数，记作f：A→B。
例如f：N→N，f(x)=2x是从N到N的函数，g：N→N，g(x)=2也是从N到N的函数。
定义8.4所有从A到B的函数的集合记作B A，读作“B上A”。
符号化表示为B A={f|f：A→B}例8.2设A={1,2,3}，B={a,b}，求B A。
解B A={f0,f1,…,f7}，其中f0={<1,a>,<2,a>,<3,a>}f1={<1,a>,<2,a>,<3,b>}f2={<1,a>,<2,b>,<3,a>}f3={<1,a>,<2,b>,<3,b>}f4={<1,b>,<2,a>,<3,a>}f5={<1,b>,<2,a>,<3,b>}f6={<1,b>,<2,b>,<3,a>}f7={<1,b>,<2,b>,<3,b>}由排列组合的知识不难证明：若|A|=m，|B|=n，且m,n>0,则|B A|=n m。
在例8.2中，|A|=3，|B|=2，而|B A|=23=8。
当A或B中至少有一个集合是空集时，可以分成下面三种情况：1. A=且B=，则B A=={}。
2. A=且B≠，则B A=B={}。
3. A≠且B=，则B A=A=。
定义8.5设函数f：A→B,A1A,B1B。
(1) 令f(A1)={f(x)|x∈A1}，称f(A1)为A1在f下的像。
特别的，当A1=A时称f(A)为函数的像。
(2) 令f-1(B1)={x|x∈A∧f(x)∈B1}，称f-1(B1)为B1在f下的完全原像。
在这里注意区别函数的值和像两个不同的概念。
函数值f(x)∈B，而像f(A1)B。
设B1B，显然B1在f下的完全原像f-1(B1)是A的子集，考虑A1A，那么f(A1)B。
f(A1)的完全原像就是f-1(f(A1))。
一般说来f-1(f(A1))≠A1，但是A1f-1(f(A1))。
例如函数f：{1,2,3}→{0,1}，满足f(1)=f(2)=0,f(3)=1令A1={1}，那么有f-1(f(A1))=f-1(f({1}))=f-1({0})={1,2}这时A 1f-1(f(A1))。
例8.3设f：N→N,且令A={0,1}，B={2}，那么有f(A)=f({0,1})={f(0),f(1)}={0,2}f-1(B)= f-1({2})={1,4}二．函数的性质下面讨论函数的性质。
定义8.6设f：A→B，(1)若ranf=B，则称f：A→B是满射的。
(2)若y∈ranf都存在唯一的x∈A使得f(x)=y，则称f：A→B是单射的。
(3)若f：A→B既是满射又是单射的，则称f：A→B是双射的(或一一映像)。
由定义不难看出，如果f：A→B是满射的，则对于任意的y∈B，都存在x∈A，使得f(x)=y。
如果f：A→B是单射的，则对于x1，x2∈A，x1≠x2，一定有f(x1)≠f(x2)。
换句话说，如果对于x1，x2∈A有f(x1)=f(x2)，则一定有x1=x2。
例8.4判断下面函数是否为单射，满射，双射的，为什么?(1) f：R→R，f(x)= -x2+2x-1(2) f：Z+→R，f(x)=lnx，Z+为正整数集(3) f：R→Z，f(x)=(4) f：R→R，f(x)=2x+1(5) f：R+→R+，f(x)=(x2+1)/x，其中R+为正实数集。
解(1) f：R→R，f(x)=-x2+2x-1是开口向下的抛物线，不是单调函数，并且在x=1点取得极大值0。
因此它既不是单射也不是满射的。
(2) f：Z+→R，f(x)=lnx是单调上升的，因此是单射的。
但不是满射的，因为ranf={ln1，ln2，…}R。
(3) f：R→Z，f(x)=是满射的，但不是单射的，例如f(1.5)=f(1.2)=1。
(4) f：R→R，f(x)=2x+1是满射，单射，双射的，因为它是单调函数并且ranf=R。
(5) f：R+→R+，f(x)=(x2+1)/x不是单射的，也不是满射的，当x→0时，f(x)→+∞；而当x→+∞时，f(x)→+∞。
在x=1处函数f(x)取得极小值f(1)=2。
所以该函数既不是单射的也不是满射的。
例8.5对于以下各题给定的A，B和f，判断是否构成函数f：A→B。
如果是，说明f：A→B是否为单射,满射,双射的。
并根据要求进行计算。
(1) A={1,2,3,4,5}，B={6,7,8,9,10}，f={<1,8>,<3,9>,<4,10>,<2,6>,<5,9>}。
(2) A,B同(1)，f={<1,7>,<2,6>,<4,5>,<1,9>,<5,10>}。
(3) A,B同(1)，f={<1,8>,<3,10>,<2,6>,<4,9>}。
(4) A=B=R，f(x)=x3。
(5) A=B=R+，f(x)=x/(x2+1)。
(6) A=B=R×R，f(<x,y>)=<x+y,x-y>，令L={<x,y>|x,y∈R∧y=x+1}，计算f(L)。
(7) A=N×N，B=N，f(<x,y>)=|x2-y2|。
计算f(N×{0}),f-1({0})。
解(1) 能构成f：A→B,但f：A→B既不是单射也不是满射，因为f(3)=f(5)=9，且7 ranf。
(2) 不能构成f：A→B，因为f不是函数。
<1,7>∈f且<1,9>∈f,与函数定义矛盾。
(3) 不能构成f：A→B，因为domf={1,2,3,4}≠A。
(4) 能构成f：A→B，且f：A→B是双射的。
(5) 能构成f：A→B，但是f：A→B既不是单射的也不是满射的。
因为该函数在x=1取得极大值f(1)=1/2。
函数不是单调的,且ranf≠R+。
(6) 能构成f：A→B，且f：A→B是双射的。
f(L)={<2x+1,-1>|x∈R}=R×{-1}(7) 能构成f：A→B，但是f：A→B既不是单射的也不是满射的。
因为f(<1,1>)=f(<2,2>)=0，且2ranf。
f(N×{0})={n2-02|n∈N}={n2|n∈N},f-1({0})={<n,n>|n∈N}。
例8.6对于给定的集合A和B构造双射函数f：A→B。
(1) A=P({1,2,3})，B={0,1}{1,2,3}(2) A=[0,1]，B=[1/4,1/2](3) A=Z，B=N(4) A=[π/2,3π/2]，B=[-1,1]解(1)A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}。
B={f0,f1,…,f7}，其中f0={<1,0>,<2,0>,<3,0>}，f1={<1,0>,<2,0>,<3,1>},f2={<1,0>,<2,1>,<3,0>}，f3={<1,0>,<2,1>,<3,1>},f4={<1,1>,<2,0>,<3,0>}，f5={<1,1>,<2,0>,<3,1>},f6={<1,1>,<2,1>,<3,0>}，f7={<1,1>,<2,1>,<3,1>}。
令f：A→B，使得f()=f0，f({1})=f1，f({2})=f2，f({3})=f3，f({1,2})=f4，f({1,3})=f5，f({2,3})=f6，f({1,2,3})=f7(2) 令f：[0,1]→[1/4,1/2]，f(x)=(x+1)/4.(3) 将Z种元素以下列顺序排列并与N种元素对应：Z：0-11-22-3 3 …↓↓↓↓↓↓↓N：0 1 2 3 4 5 6 …则这种对应所表示的函数是：f：Z→N(4) 令f：[π/2,3π/2]→[-1,1]f(x)=sinx三．常用函数下面定义一些常用的函数。
定义8.7(1) 设f：A→B，如果存在y∈B使得对所有的x∈A都有f(x)=y，则称f：A→B是常函数。
(2) 称A上的恒等关系I A为A上的恒等函数，对所有的x∈A都有I A(x)=x。
(3) 设<A,>，<B,>为偏序集，f：A→B，如果对任意的x1，x2∈A，x1x2，就有f(x 1)f(x2)，则称f为单调递增的；如果对任意的x1，x2∈A，x1x2，就有f(x1)f(x2)，则称f为严格单调递增的。
