離散最后總結(jié)

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

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

3、構(gòu)成的合取范式例如，n=3命題變項(xiàng)為pqr時(shí)，(?p??q?r)?(?p?q?r)?m1?m3——主析取范式(?p??q??r)?(p?q??r)?M7?M1——主合取范式練習(xí)：證明p?(q?r)?(p?q)?r3.命題邏輯推理理論：推理定律的考察P45P46。重要的推理定律A?(A?B)附加律(A?B)?A化簡(jiǎn)律(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)等價(jià)三段論(A?B)?(C?D)?(A?C)?(B?D)構(gòu)造性二難(A?B)?(?A?B)?(A??A)?B構(gòu)造性二難（特殊形式）(A?B)?(C?D)?(?B??D)?(?A??C)破壞性二難例子：構(gòu)造證明設(shè)p：明天是星期一，q：明天是星期三，r：我有課，s：我備課形式結(jié)構(gòu)前提：(p?q)?rr?s?s結(jié)論：?p??q證明①r?s前提引入②?s前提引入3i設(shè)G是群，H是G的非空子集，則H是G的子群

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

6、判斷，看第六章的PPt和PPT上的習(xí)題，書(shū)上的例題。①分配律對(duì)任何集合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.二元關(guān)系自反、對(duì)稱(chēng)、傳遞的判定，關(guān)系的矩陣表示法。給定一個(gè)關(guān)系R的關(guān)系圖，要會(huì)計(jì)算Rn，能用集合表示Rn，能計(jì)算)()()(RtRsRr17.判定給定的圖是否為二部圖。能將圖分為兩個(gè)頂點(diǎn)集V1，V2，圖的邊一個(gè)頂點(diǎn)在V1中，一個(gè)在V2中的圖就叫做二部圖18.18.最小生成樹(shù)的相關(guān)算法的復(fù)雜度判定。最小生成樹(shù)的相關(guān)算法的復(fù)雜度判定。19.無(wú)向樹(shù)的非同構(gòu)樹(shù)要會(huì)畫(huà)出。例：P309P3107個(gè)頂點(diǎn)的無(wú)向樹(shù)的非同構(gòu)圖要知道就行了