离散数学知识点总结 6675.docx

离散数学知识点总结
前言
广理期末考试即将打响，离散数学苦坏了信息技术学院的靓仔靓女们，当
然作为文科生的凉城也是一天发量比一天少，小编呕心沥血从各大文库、
教材等途径整理了离散数学知识点可能不唯一 ) ；
上确界：最小的上界 ( 若存在就一定唯一 )；
下确界：最大的下界 ( 若存在就一定唯一 )；

B 的下界

(若
第六章 函数
若 |X|=m,|Y|=n, 则从 X 到 Y 有种不同的关系，有种不同的函数；
在一个有 n 个元素的集合上，可以有种不同的关系，有种不同的函数，有 n! 种不同的双射；
3. 若 |X|=m,|Y|=n ，且 m<=n ，则从 X 到 Y 有种不同的单射；
单射： f:X-Y ，对任意 ,属于 X,且≠，若 f() ≠f() ；
满射：f:X-Y ，对值域中任意一个元素
y 在前域中都有一个或多个元素对应；
双射： f:X-Y ，若 f 既是单射又是满射，则
f 是双射；
5.
复合函数： f og=g(f(x));
6.
设函数 f:A-B ， g:B-C ，那么
①如果 f,g 都是单射，则
f og 也是单射；
②如果 f,g 都是满射，则
f og 也是满射；
③如果 f,g 都是双射，则
f og 也是双射；
④如果 fog 是双射，则
f 是单射， g 是满射；
第七章 代数系统
1. 二元运算：集合 A 上的二元运算就是到 A 的映射；
2. 集合 A 上可定义的二元运算个数就是从 A ×A 到 A 上的映射的个数，即
从从 A ×A 到 A 上函数的个数，若 |A|=2, 则集合 A 上的二元运算的个数为
==16 种；
判断二元运算的性质方法：①封闭性：运算表内只有所给元素；②交换律：主对角线两边元素对称相等；③幂等律：主对角线上每个元素与所在行列表头元素相同；④有幺元：元素所对应的行和列的元素依次与运算表的行和列相同；⑤有零元：元素所对应的行和列的元素都与该元素相同；
4. 同态映射： <A,*>,<B,^>, 满足 f(a*b)=f(a)^f(b), 则 f 为由 <A,*> 到 <B,^>
的同态映射；若 f 是双射，则称为同构；
第八章 群
广群的性质：封闭性；
半群的性质：封闭性，结合律；
含幺半群 (独异点 ) ：封闭性，结合律，有幺元；群的性质：封闭性，结合律，有幺元，有逆元；
群没有零元；
阿贝尔群 ( 交换群 )：封闭性，结合律，有幺元，有逆元，交换律；
循环群中幺元不能是生成元；
任何一个循环群必定是阿贝尔群；
第十章 格与布尔代数
格：偏序集合 A 中任意两个元素都有上、下确界；
格的基本性质：
自反性
a ≤a 对偶 : a ≥a
反对称性
a ≤b ^ b ≥a => a=b
对偶 :a ≥b ^ b ≤a
=> a=b
3)
传递性
a ≤b ^ b ≤c =>
a ≤c
对偶 :a ≥b ^ b ≥c
=> a ≥c
4)
最大下界描述之一
a^b ≤a 对偶 avb ≥a
A^b ≤b 对偶 avb ≥b
）最大下界描述之二
c ≤a,c ≤b => c ≤a^b
对偶 c ≥a,c ≥b =>Tc ≥avb
6) 结合律
a^(b^c)=(a^b)^c
对偶 av(bvc)=(avb)vc
等幂律
a^a=a 对偶 ava=a
吸收律
a^(avb)=a
对偶
av(a^b)=a
9)
a ≤b <=>
a^b=aavb=b
10)
a ≤c,b ≤d
=>
a^b ≤c^d avb ≤cvd
保序性
b ≤c => a^b ≤a^c avb ≤avc
12 ） 分配不等式
av(b^c) ≤(avb)^(avc)
对偶 a^(bvc) ≥(a