离散数学章节总结.doc

离散数学章节总结第一章[] :Negation¬NOT :ConjunctionÙAND :DisjunctionÚOR :Implication®IMPLIES ↔IFF -OrÅ :converse :inverse :[]→q等价于¬pÚq等价于¬q→¬Úq等价于¬p→qpÙq等价于¬(p→¬q)3.(p→q)Ù(p→r)等价于p→(qÙr)(p→r)Ù(q→r)等价于(pÚq)→r(p→r)Ú(q→r)等价于(pÙq)→:真值表逻辑符号证明找反例(假设左为假右必为假假设右为假左必为假)[]∃存在 ∀任意量词顺序不能随机改变不全为真:Ø(p1Ùp2Ù…Ùpn)Û(Øp1ÚØp2Ú…ÚØpn)Ø"xP(x)Û$xØP(x)没有一个为真:Ø(p1Úp2Ú…Úpn)Û(Øp1ÙØp2Ù…ÙØpn)Ø$xP(x)Û"xØP(x)[][]:直接证明间接证明反证列举证明(列举所有情况)构造证明(构造出满足结论的元素):正向证明反向证明第二章[]:RQZ无穷/::交/并/补/差/取子集P(S)/元素数|S|/乘积P×Q/:[]:定义域,值域,象,原象,范围,(a)/f(A) 第五章 [、归纳]:在某种关系下存在最小元素则为well-:basicstepP(C)成立andinductivestepP(k)→P(k+1):basicstep:P(c)成立andinductivestep:任意k小于等于nP(k) 成立→P(n+1)[]:以相同形式用小的项来定义的大的项不能一直递归下去(存在初始项)必须存在可以直接解决问题的一项basicstep:原有元素②recursivestep::空字符,:用于证明递归结构对所有元素都成立:①basicstep:原有元素成立②recursivestep:用递归式导出的新元素成立[]:(是可终止的),可以用非递归(loop或stack)来代替[]::①程序会终止②(部分正确)程序只要可以终止得出的结论都是正确的正确的程序:对任意可能的输入都有正确的输出部分正确,:P{S}Q P:preconditionS:assertionQ:postcondition?? P{S}Q::赋值,命题,条件,