大学离散数学期末重点知识点总结考试专用.doc

第 2 页
p∧(P→Q)=>Q 假言推论
┐Q∧(P→Q)=>┐P 拒取式
┐p∧(P∨Q)=>Q 析取三段式
(P→Q) ∧(
上确界：最小的上界(假设存在就一定唯一)；
下确界：最大的下界(假设存在就一定唯一)；
假设,那么从X到Y有种不同的关系，有种不同的函数；
在一个有n个元素的集合上，可以有2n2种不同的关系，有种不同的函数，有n!种不同的双射；
假设，且m<，那么从X到Y有 种不同的单射；
单射：，对任意,属于X,且≠，假设f()≠f()；
满射：，对值域中任意一个元素y在前域中都有一个或多个元素对应；
双射：，假设f既是单射又是满射，那么f是双射；
复合函数：fº(f(x));
设函数，，那么
①如果都是单射，那么fºg也是单射；
②如果都是满射，那么fºg也是满射；
③如果都是双射，那么fºg也是双射；
④如果fºg是双射，那么f是单射，g是满射；
二元运算：集合A上的二元运算就是到A的映射；
集合A上可定义的二元运算个数就是从A×A到A上的映射的个数，即从从A×A到A上函数的个数，假设2,那么集合A上的二元运算的个数为16种；
判断二元运算的性质方法：
①封闭性：运算表内只有所给元素；
②交换律：主对角线两边元素对称相等；
③幂等律：主对角线上每个元素及所在行列表头元素一样；
④有幺元：元素所对应的行与列的元素依次及运算表的行与列一样；
⑤有零元：元素所对应的行与列的元素都及该元素一样；
同态映射：<A,*>,<B,^>,满足f(a*b)(a)^f(b),那么f为由<A,*>到<B,^>的同态映射；假设f是双射，那么称为同构；
广群的性质：封闭性；
半群的性质：封闭性，结合律；
含幺半群(独异点)：封闭性，结合律，有幺元；
群的性质：封闭性，结合律，有幺元，有逆元；
群没有零元；
阿贝尔群(交换群)：封闭性，结合律，有幺元，有逆元，交换律；
循环群中幺元不能是生成元；
任何一个循环群必定是阿贝尔群；
格：偏序集合A中任意两个元素都有上、下确界；
格的根本性质：
1) 自反性a≤a 对偶: a≥a
2) 反对称性a≤b ^ b≥a =>
对偶≥b ^ b≤a =>
3) 传递性a≤b ^ b≤c => a≤c
对偶≥b ^ b≥c => a≥c
4) 最大下界描述之一a^b≤a 对偶 ≥a
A^b≤b 对偶 ≥b
5〕最大下界描述之二c≤≤b => c≤a^b
对偶c≥≥b =>Þc≥
6) 结合律a^(b^c)=(a^b)^c
对偶 ()=()
7)   等幂律a^ 对偶
8) 吸收律a^() 对偶 (a^b)
9)    a≤b <=> a^
10) a≤≤d => a^b≤c^d ≤
11) 保序性b≤c => a^b≤a^c ≤
12〕 分配不等式(b^c)≤()^()