2016离散数学知识点总结.doc

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