离散数学章节总结.doc

《离散数学章节总结.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、离散数学章节总结第一章[1.1命题逻辑]1.逻辑运算1.否定:Negation¬NOT2.交:ConjunctionÙAND3.并:DisjunctionÚOR4.蕴含:Implication®IMPLIES5.Biconditional↔IFF6.Exclusive-OrÅXOR2.逆/否/逆否1.逆:converse2.否:inverse3.逆否:conytrapositive3.问题的一致性[1.2逻辑等价]1.p→q等价于¬pÚq等价于¬q→¬p2.pÚq等价于¬p→qpÙq等价于¬(p→¬q)3.(p→q)Ù(p→r)等价于p→(qÙr)(p→r)Ù(q→r)等价于

2、(pÚq)→r(p→r)Ú(q→r)等价于(pÙq)→r4.证明等价:真值表逻辑符号证明找反例(假设左为假右必为假假设右为假左必为假)[1.31.4谓词逻辑]1.量词存在任意量词顺序不能随机改变不全为真:Ø(p1Ùp2Ù…Ùpn)Û(Øp1ÚØp2Ú…ÚØpn)Ø"xP(x)Û$xØP(x)没有一个为真:Ø(p1Úp2Ú…Úpn)Û(Øp1ÙØp2Ù…ÙØpn)Ø$xP(x)Û"xØP(x)[1.5推理][1.61.7证明]1.证明方法:直接证明间接证明反证列举证明(列举所有情况)构造证明(构造出满足结论的元素)2.证明步骤:正向证明反向证明第二章[2.12.2集合及运算]1

3、.特殊集合:RQZ无穷/有限集2.集合表述方法:列举法描述法图表法3.集合运算:交/并/补/差/取子集P(S)/元素数

4、S

5、/乘积P×Q/容斥原理4.证明集合相等:1.证明互为子集2.从属表3.逻辑证明[2.3函数]1.函数的定义2.术语：定义域，值域，象，原象，范围，3.f(a)/f(A)第五章[5.1序、归纳]1.序：在某种关系下存在最小元素则为well-ordered2.第一数学归纳法：basicstepP(C)成立andinductivestepP(k)→P(k+1)3.第二数学归纳法:basicstep:P(c)成立andinductivestep:任意k小于等于n

6、P(k)成立→P(n+1)[5.2递归]1.递归：以相同形式用小的项来定义的大的项不能一直递归下去（存在初始项）必须存在可以直接解决问题的一项①basicstep:原有元素②recursivestep:原有元素如何产生新元素2.字符串的定义：空字符，回文3.结构归纳：用于证明递归结构对所有元素都成立：①basicstep:原有元素成立②recursivestep:用递归式导出的新元素成立[5.3递归算法]1.定义：把问题转化为相同形式但值更小的算法2.递归算法有初始步骤（是可终止的）并且递归时至少改变一个参数值使之向初始步骤靠拢3.递归时间复杂度高，可以用非递归（loop或s

7、tack）来代替[5.4程序的正确性]1.测试与证明：证明更有说服力2.证明：①程序会终止②（部分正确）程序只要可以终止得出的结论都是正确的正确的程序：对任意可能的输入都有正确的输出部分正确，完全正确3.Hoaretriple：P{S}QP:preconditionS:assertionQ:postcondition??P{S}Q:当PQ正确时为部分正确当证明了S的可终止性为完全正确4.程序的基本语句：赋值，命题，条件，循环5.弱化结论：P{S}RR→Q：P{S}Q强化条件Q→RR{S}P：Q{S}P复合：P{S1}RR{S2}Q:P{S1;S2}Q第六章[6.1加法乘法原理

8、]1.加法乘法原理：方法不重复，互不影响，做1or2m+n做1and2mn2.容斥原理：方法有重叠：

9、AÈB

10、=

11、A

12、+

13、B

14、-

15、AÇB

16、3.包含条件的问题。[6.2分类原理]1.抽屉原理。2.抽屉原理推论：n插入k个抽屉：至少有一个抽屉含有[n/k]个元素（上取整）[6.3排列组合]1.排列：选择的元素只出现一次r-permutationofSP(n,r)=n(n−1)…(n−r+1)=n!/(n−r)!2.组合：[6.4二项式系数]1.杨辉三角：C(n+1,k)=C(n,k-1)+C(n,k)第九章[9.1关系]1.关系：函数的推广2.二元关系：①.定义：Abinaryr

17、elationfromAtoBisasetRwhereaRbdenotes(a,b)R包含于AXB.aissaidtoberelatedtobbyR.②.数量：with

18、A

19、=mand

20、B

21、=n共有2mnrelationsfromAtoB,includingtheemptyrelationaswellastherelationAXB.3.关系图4.自身关系：AonA：A×ArelationonA5.反身关系：reflexive：aA(a,a)RReflexiverelations:含有所有(a,a)元素