离散数学必备知识点总结.doc

-
. z
总结 离散数学知识点
命题逻辑
→，前键为真，后键为假才为假；<—>，一样为真，不同为假；
主析取式fºg是双射，则f是单射，g是满射；
代数系统
二元运算：集合A上的二元运算就是到A的映射；
集合A上可定义的二元运算个数就是从A×A到A上的映射的个数，即从从A×A到A上函数的个数，假设|A|=2,则集合A上的二元运算的个数为==16种；
判断二元运算的性质方法：
①封闭性：运算表只有所给元素；
②交换律：主对角线两边元素对称相等；
③幂等律：主对角线上每个元素与所在行列表头元素一样；
④有幺元：元素所对应的行和列的元素依次与运算表的行和列一样；
⑤有零元：元素所对应的行和列的元素都与该元素一样；
同态映射：<A,*>,<B,^>,满足f(a*b)=f(a)^f(b),则f为由<A,*>到<B,^>的同态映射；假设f是双射，则称为同构；
-
. z
群
广群的性质：封闭性；
半群的性质：封闭性，结合律；
含幺半群(独异点)：封闭性，结合律，有幺元；
群的性质：封闭性，结合律，有幺元，有逆元；
群没有零元；
阿贝尔群(交换群)：封闭性，结合律，有幺元，有逆元，交换律；
循环群中幺元不能是生成元；
任何一个循环群必定是阿贝尔群；
格与布尔代数
格：偏序集合A中任意两个元素都有上、下确界；
格的根本性质：
1) 自反性
a≤a 对偶: a≥a
2) 反对称性
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
-
. z
≤a 对偶 avb≥a
A^b≤b 对偶 avb≥b
5〕最大下界描述之二
c≤a,c≤b => c≤a^b
对偶c≥a,c≥b =>Þc≥avb
6) 结合律
a^(b^c)=(a^b)^c
对偶 av(bvc)=(avb)vc
7) 等幂律
a^a=a 对偶 ava=a
8) 吸收律
a^(avb)=a 对偶 av(a^b)=a
9) a≤b <=> a^b=a avb=b
10) a≤c,b≤d => a^b≤c^d avb≤cvd
11) 保序性
b≤c => a^b≤a^c avb≤avc
12〕 分配不等式
av(b^c)≤(avb)^(avc)
对偶 a^(bvc)≥(a^b)v(a^c)
13〕模不等式
a≤c <=>Û av(b^c)≤(avb)^c
分配格：满足a^(bvc)=(a^b)v(a^c)和av(b^c)=(avb)^(avc)；
-
. z
分配格的充要条件：该格没有任何子格与钻石格或五环格同构；
，分配格必定是模格；
全上界：集合A中的*个元素a大于等于该集合中的任何元素，则称a为格<A,<=>的全上界，记为1；(假设存在则唯一)
全下界：集合A中的*个元素b小于等于该集合中的任何元素，则称b为格<A,<=>的全下界，记为0；(假设存在则唯一)
有界格：有全上界和全下界的格称为有界格，即有0和1的格；
补元：在有界格，如果a^b=0,avb=1，则a和b互为补元；
有补格：在有界格，每个元素都至少有一个补元；
有补分配格(布尔格)：既是有补格，又是分配格；
布尔代数：一个有补分配格称为布尔代数；
图论
邻接：两点之间有边连接，则点与点邻接；
关联：两点之间有边连接，则这两点与边关联；
平凡图：只有一个孤立点构成的图；
简单图：不含平行边和环的图；
无向完全图：n个节点任意两个节点之间都有边相连的简单无向图；