(word完整版)离散数学必备知识点总结,推荐文档.doc

: .
总结 离散数学知识点
第二章 命题逻辑
1. 前键为真，后键为假才为假； ＜—＞，相同为真，不同为假；
2•主析取范式：极小项（m）之和；主合取范式：极大项（M）之积；
3. 求极小项时，命题变元的肯定为 1 ，否定为 0，求极大项时相反；
4. 求极大极小项时，每个变元或变元的否定只能出现一次，求极小项
时变元不够合取真，求极大项时变元不够析取假；
5. 求范式时，为保证编码不错， 命题变元最好按 P,Q,R 的顺序依次写；
6. 真值表中值为 1 的项为极小项，值为 0 的项为极大项；
7. n个变元共有2n个极小项或极大项，这2n为（0~2n-1）刚好为化简完 后的主析取加主合取；
8. 永真式没有主合取范式，永假式没有主析取范式；
9. 推证蕴含式的方法 （=＞）：真值表法； 分析法（假定前键为真推出后键 为真，假定前键为假推出后键也为假 ）
10. 命题逻辑的推理演算方法：P规则，T规则
① 真值表法；②直接证法；③归谬法；④附加前提法；
第三章 谓词逻辑
1. 一元谓词：谓词只有一个个体，一元谓词描述命题的性质；
多元谓词：谓词有 n 个个体，多元谓词描述个体之间的关系；
2. 全称量词用蕴含存在量词用合取“；
3. 既有存在又有全称量词时，先消存在量词，再消全称量词；
第四章 集合
1. N，表示自然数集，1,2,3……，不包括0;
2. 基：集合 A 中不同元素的个数， |A|；
3. 幕集：给定集合A,以集合A的所有子集为元素组成的集合，P(A);
4. 若集合A有n个元素，幕集P(A)有艺个元素，|P(A)|= 2|A|=2n ；
5. 集合的分划：(等价关系)
① 每一个分划都是由集合 A 的几个子集构成的集合;
② 这几个子集相交为空，相并为全(A)；
6. 集合的分划与覆盖的比较：
分划：每个元素均应出现且仅出现一次在子集中；
覆盖：只要求每个元素都出现，没有要求只出现一次；
第五章 关系
1. 若集合A有m个元素，集合B有n个元素，则笛卡尔AXB的基数 为mn , A到B上可以定义2mn种不同的关系；
2
2. 若集合A有n个元素，则|A X\|= n2, A上有2n个不同的关系；
3. 全关系的性质：自反性，对称性，传递性；
空关系的性质：反自反性，反对称性，传递性；
全封闭环的性质：自反性，对称性，反对称性，传递性；
4. 前域（domR）:所有元素x组成的集合；
后域（ranR）：所有元素y组成的集合；
5. 自反闭包: r（R）=RU Ix;
对称闭包： s（R）=RU R-1 ;
传递闭包：t（R）=RU R2U R3 U……
6. 等价关系：集合 A 上的二元关系 R 满足自反性，对称性和传递性， 则 R 称为等价关系；
7. 偏序关系：集合 A 上的关系 R 满足自反性，反对称性和传递性， 则称 R 是 A 上的一个偏序关系；
8. covA={<x,y>|x,y 属于 A，y 盖住 x}；
9. 极小元：集合 A 中没有比它更小的元素 （若存在可能不唯一 ）； 极大元：集合 A 中没有比它更大的元素 （若存在可能不唯一 ）； 最小元：比集合 A 中任何其他元素都小 （若存在就一定唯一 ）； 最大元：比集合 A 中任何其他元素都大 （若存在就一定唯一 ）；
10. 前提： B 是 A 的子集
上界： A 中的某个元素比 B 中任意元素都大，称这个元素是 B 的 上界 （若存在，可能不唯一 ）；
下界： A 中的某个元素比 B 中任意元素都小，称这个元素是 B 的 下界 （若存在，可能不唯一 ）；
上确界：最小的上界 （若存在就一定唯一 ）；
下确界：最大的下界 （若存在就一定唯一 ）；
第六章 函数
1. 若|X|=m,|Y|=n,则从X到Y有2mn种不同的关系，有nm种不同的函数；
2
2. 在一个有 n 个元素的集合上，可以有 2n2 种不同的关系，有 nn 种不 同的函数，有n!种不同的双射；
3. 若|X|=m,|Y|=n，且m＜二n，则从X到Y有a：种不同的单射；
4. 单射：f:X-Y，对任意洛心属于X,且xi念，若f(xj#(X2);
满射：f:X-Y,对值域中任意一个元素 y在前域中都有一个或多个
元素对应；
双射：f:X-Y，若f既是单射又是满射，则f是双射；
5. 复合函数： fog=g(f(x));
6. 设函数 f:A-B， g: