离散数学知识点.doc

离散数学知识点整理
→r)
假言三段论
q→r
p→r
?q
(?q∧(p→q))→?p
取拒式
p→q
?p
p∨q
((p∨q)∧?p)→q
析取三段论
?p
q
p
p→(p∨q)
附加律
p∨q
p∧q
(p∧q)→p
化简律
p
p
（p∧q）→（p∧q）
合取律
q
4
p∧q
p∨q(p∨q)∧(?p∨r)→(q∨r)消解律
?p∨r
q∨r
量化推理规则
?xP(x)全称实例
P(c)
P(c)，随意c全称引入
?P(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也是可数的。
5
如果存在一对一函数f从A到B和一对一函数g从B到A，那么A和B之间是一一对应的。
求和公式：
23nn+1
a+ar+ar+ar+...+ar=(ar-a)/(r-1)
222
1+2+3+...+n=n(n+1)(2n+1)/6
33322
1+2+3+...+n=n(n+1