離散最后總結(jié)

1、1主要內(nèi)容：1.命題符號化：命題邏輯和謂詞邏輯都有考察。否定式與否定聯(lián)結(jié)詞“”“非p”?合取式與合取聯(lián)結(jié)詞“∧”“p并且q”析取式與析取聯(lián)結(jié)詞“∨”“p或q”蘊涵式與蘊涵聯(lián)結(jié)詞“”“如果p則q”相同的表達為“若p，就q”“只要p，就q”?“p僅當q”“只有q才p”“除非q才p”“除非q，否則非p”練習：如果交通不阻塞，他就不會遲到；除非交通阻塞，否則他不會遲到.2.判斷兩個命題公式是否等值，判斷公式的類型（重言式，矛盾式，可滿足式）：會

2、用真值表和等值演算或主析取范式法（主合取范式）。若等價式AB是重言式，則稱A與B等值，記作AB，并稱A與B是等值式??判斷公式類型：重言式，矛盾式，可滿足式；主要用真值表和等值演算或主析取范式法幾個常用的等值演算蘊涵等值式：A?B??A?B等價等值式：A?B?(A?B)?(B?A)假言易位：A?B??B??A等價否定等值式：A?B??A??B歸謬論：(A?B)?(A??B)??A主析取范式——由極小項構成的析取范式主合取范式——由極大項

3、構成的合取范式例如，n=3命題變項為pqr時，(?p??q?r)?(?p?q?r)?m1?m3——主析取范式(?p??q??r)?(p?q??r)?M7?M1——主合取范式練習：證明p?(q?r)?(p?q)?r3.命題邏輯推理理論：推理定律的考察P45P46。重要的推理定律A?(A?B)附加律(A?B)?A化簡律(A?B)?A?B假言推理(A?B)??B??A拒取式(A?B)??B?A析取三段論(A?B)?(B?C)?(A?C)假言三

4、段論(A?B)?(B?C)?(A?C)等價三段論(A?B)?(C?D)?(A?C)?(B?D)構造性二難(A?B)?(?A?B)?(A??A)?B構造性二難（特殊形式）(A?B)?(C?D)?(?B??D)?(?A??C)破壞性二難例子：構造證明設p：明天是星期一，q：明天是星期三，r：我有課，s：我備課形式結(jié)構前提：(p?q)?rr?s?s結(jié)論：?p??q證明①r?s前提引入②?s前提引入3i設G是群，H是G的非空子集，則H是G的子群

5、的充要條件是：（1）?ab∈H有ab∈H.（2）?a∈H有∈H.1a?II設G為群，H是G的非空子集.H是G的子群當且僅當?ab∈H有∈H.1ab?iii設G為群，H是G的非空有窮子集，則H是G的子群當且僅當?ab∈H有ab∈H.13.群：給定一個群，計算其中元素的“階”例：定理11.4G為群，a∈G且|a|=r.設k是整數(shù)，則（1）ak=e當且僅當r|k（2）||=|a|1a14.集合計數(shù)（包含排斥原理），集合的元素與集合的關系

6、判斷，看第六章的PPt和PPT上的習題，書上的例題。①分配律對任何集合A、B、C，有A∩(B∪C)=(A∩B)∪(A∩C)；A∪(B∩C)=(A∪B)∩(A∪C)。15.集合恒等式的證明：P93德摩根（6.17~6.22），參考例題的證明方式。A?(B?C)=(A?B)?(A?C)（6.17）A?(B?C)=(A?B)?(A?C)（6.18）?(B?C)=?B??C（6.19）?(B?C)=?B??C（6.20）例題：（6.17）（6.

7、18）的證明16.二元關系自反、對稱、傳遞的判定，關系的矩陣表示法。給定一個關系R的關系圖，要會計算Rn，能用集合表示Rn，能計算)()()(RtRsRr17.判定給定的圖是否為二部圖。能將圖分為兩個頂點集V1，V2，圖的邊一個頂點在V1中，一個在V2中的圖就叫做二部圖18.18.最小生成樹的相關算法的復雜度判定。最小生成樹的相關算法的復雜度判定。19.無向樹的非同構樹要會畫出。例：P309P3107個頂點的無向樹的非同構圖要知道就行了