离散数学章节总结.doc

.
实用文档.
离散数学章节总结
第一章
[命题逻辑]

:Negation ¬ NOT
:Conjunction Ù AND
:Disjunction Ú OR
:Implication ® IMPLIES
5. Biconditional ↔ IFF
-Or Å XOR
:converse
:inverse
:conytrapositive
的一致性
[逻辑等价]
→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
: 真值表 逻辑符号证明 找反例(假设左为假 右必为假 假设右为假 左必为假)
[ 谓词逻辑]
∃存在
∀任意
量词顺序不能随机改变
不全为真:Ø(p1Ùp2Ù…Ùpn) Û (Øp1ÚØp2Ú…ÚØpn)
Ø "x P(x ) Û $x ØP(x )
没有一个为真:Ø(p1Úp2Ú…Úpn) Û (Øp1ÙØp2Ù…ÙØpn)
Ø $x P(x ) Û "x ØP(x )
[ 推理]
.
实用文档.
[ 证明]
方法:直接证明 间接证明 反证 列举证明(列举所有情况) 构造证明(构造出满足结论的元素)
步骤:正向证明 反向证明
.
实用文档.
第二章
[ 集合及运算]
: R Q Z 无穷/有限集
表述方法: 列举法 描述法 图表法
运算: 交/并/补/差/取子集P(S)/元素数|S|/乘积P×Q/
容斥原理
集合相等: 2.
[ 函数]
的定义
：定义域，值域，象，原象，范围，
(a)/f(A)

.
实用文档.
第五章
[、归纳]
：在某种关系下存在最小元素那么为well-ordered
数学归纳法：basic step P(C)成立and inductive step P(k)→P(k+1)
:basic step:P(c)成立 and inductive step: 任意k小于等于nP(k) 成立→P(n+1)
[递归]
：以相同形式用小的项来定义的大的项
不能一直递归下去〔存在初始项〕必须存在可以直接解决问题的一项
basic step:原有元素
② recursive step:原有元素如何产生新元素
的定义：空字符，回文
归纳：用于证明递归结构对所有元素都成立：
①basic step:原有元素成立
②recursive step:用递归式导出的新元素成立
[算法]
：把问题转化为相同形式但值更小的算法