离散数学章节总结.doc

离散数学章节总结
第一章
[1、1命题逻辑]
1、逻辑运算
1、否定:Negation ¬ NOT
2、交:Conjunction Ù AND
3、并:Disjunction Ú OR
4、蕴含:Implication ® IMPLIES
5、 Biconditional ↔ IFF
6、Exclusive-Or Å XOR
2、逆/否/逆否
1、逆:converse
2、否:inverse
3、逆否:conytrapositive
3、问题的一致性
[1、2逻辑等价]
1、p→q 等价于 ¬pÚq 等价于 ¬ q→¬p
2、 pÚq 等价于 ¬p→q
pÙq 等价于 ¬( p→¬q)
3、(p→q) Ù (p→r) 等价于p→(qÙr)
(p→r) Ù (q→r) 等价于(pÚq)→r
(p→r) Ú (q→r) 等价于(pÙq) →r
4、证明等价: 真值表 逻辑符号证明 找反例(假设左为假 右必为假 假设右为假 左必为假)
[1、3 1、4 谓词逻辑]
1、量词 ∃存在
∀任意
量词顺序不能随机改变
不全为真:Ø(p1Ùp2Ù…Ùpn) Û (Øp1ÚØp2Ú…ÚØpn)
Ø "x P(x ) Û $x ØP(x )
没有一个为真:Ø(p1Úp2Ú…Úpn) Û (Øp1ÙØp2Ù…ÙØpn)
Ø $x P(x ) Û "x ØP(x )
[1、5 推理]
[1、6 1、7 证明]
1、证明方法:直接证明 间接证明 反证 列举证明(列举所有情况) 构造证明(构造出满足结论的元素)
2、证明步骤:正向证明 反向证明
第二章
[2、1 2、2 集合及运算]
1、特殊集合: R Q Z 无穷/有限集
2、集合表述方法: 列举法 描述法 图表法
3、集合运算: 交/并/补/差/取子集P(S)/元素数|S|/乘积P×Q/
容斥原理
4、证明集合相等:1、证明互为子集 2、从属表 3、逻辑证明
[2、3 函数]
1、函数的定义
2、术语:定义域,值域,象,原象,范围,
3、f(a)/f(A)
第五章
[5、1序、归纳]
1、序:在某种关系下存在最小元素则为well-ordered
2、第一数学归纳法:basic step P(C)成立and inductive step P(k)→P(k+1)
3、第二数学归纳法:basic step:P(c)成立 and inductive step: 任意k小于等于nP(k) 成立→P(n+1)
[5、2递归]
1、递归:以相同形式用小的项来定义的大的项
不能一直递归下去(存在初始项)必须存在可以直接解决问题的一项
basic step:原有元素
② recursive step:原有元素如何产生新元素
2、字符串的定义:空字符,回文
3、结构归纳:用于证明递归结构对所有元素都成立:
①basic step:原有元素成立
②recursive step:用递归式导出的新元素成立
[5、3递归算法]
1、定义:把问题转化为相同形式但值更小的算法
2、递归算法有初始步骤(就是可终止的)并且递归时至少