离散数学知识点整理(共7页).doc

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
离散数学
逻辑和证明

x)
∃xP(x)
存在实例
P(c)，对某个c
P(c)，对某个c
存在引入
∃xP(x)
命题和量化命题的组合使用。
集合、函数、序列、与矩阵

∈说的是元素与集合的关系，⊆说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。
A和B相等当仅当∀x(x∈A↔x∈B)；A是B的子集当仅当∀x(x∈A→x∈B)；
A是B的真子集当仅当∀x(x∈A→x∈B)∧∃x(x∉A∧x∈B)。
幂集：集合元素的所有可能组合，肯定有∅何它自身。如∅的幂集就是{∅}，而{∅}的幂集是{∅，{∅}}。
笛卡尔积：A×B，结果是序偶，其中的一个子集叫一个关系。
带量词和集合符号如∀x∈R（x2>0）是真的，则所有真值构成真值集。
集合恒等式
名称
(A∪B)'=A'∩B' 
(A∩B)'=A'∪B'
德摩根律
A∪(A∩B)=A
A∩(A∪B)=A
吸收律

考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。
一对一或者单射：B可能有多余的元素，但不重复指向。
映上或者满射：B中没有多余的元素，但可能重复指向。
一一对应或者双射：符合上述两种情况的函数关系。
反函数：如果是一一对应的就有反函数，否则没有。
合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。

无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。
如果A和B是可数的，则A∪B也是可数的。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
如果存在一对一函数f从A到B和一对一函数g从B到A，那么A和B之间是一一对应的。
求和公式：
a+ar+ar2+ar3+...+arn = (arn+1-a)/(r-1)
1+2+3+...+n = n(n+1)/2
1+22+32+...+n2 = n(n+1)(2n+1)/6
1+23+33+...+n3 = n2(n+1)2/4

普通矩阵和、减、乘积，0-1矩阵还可以∧、∨、⊙（和相乘类似，用∨代替+，用∧代替×）
关系

设A和B是集合，从A到B的二元关系是A×B的子集。一个从A到B的二元关系是集合R，第一个元素取自A，第二个元素取自B，当(a,b)属于R时写作aRb。
集合A上的关系是A到A的关系，有n个元素就有n2个有序对，n2个有序对就有2n2个关系。
考虑集合A到A的关系R：
任意a∈A都有（a，a）∈R，则R是集合A上的自反关系。
任意a，b∈A，若（a，b）∈