離散復(fù)習(xí)材料

1、1. 命題及其表示1) 判斷哪些是命題（悖論，真值不能確定的，非陳述句）a) 我正在說(shuō)假話(huà)！b) X=2c) 今天天氣真好??！2) 分清簡(jiǎn)單命題與復(fù)合命題a) 藍(lán)色和黃色可以調(diào)配成綠色。b) 藍(lán)色和黃色是常用的顏色。3) 區(qū)別相容或與排斥或a) 李和平是山西人或陜西人。b) 李冰選學(xué)英語(yǔ)或法語(yǔ)。4) 蘊(yùn)涵式的邏輯關(guān)系，準(zhǔn)確地找出蘊(yùn)涵式的前件與后件（只有才，除非否則非，除非才，僅當(dāng)）a) 除非4是奇數(shù)，否則5不是奇數(shù)。b) 只有4是偶數(shù)，則5才是偶數(shù)。c) 5是偶數(shù)僅當(dāng)4是奇數(shù)。2. 求復(fù)合公式的成真賦值，成假賦值，類(lèi)型以及真值。（真值表法）3. 等值式與基本等值式4. 等值演算，置換規(guī)則5.

2、重言式與矛盾式的判別法A為重言式當(dāng)且僅當(dāng), A為矛盾式當(dāng)且僅當(dāng)6. 主析取范式與主合取范式1) 求公式A的主析取范式的方法與步驟a) 等值演算法 1）求公式的析取范式； （1）消去除，以外公式中出現(xiàn)的所有邏輯聯(lián)結(jié)詞。（2）將否定聯(lián)結(jié)詞消去或內(nèi)移到各命題變?cè)?。如，；。?）利用分配律、結(jié)合律將公式轉(zhuǎn)化為合取范式或析取范式。如，；。2）除去中所有永假的析取項(xiàng)；3） 若的某個(gè)簡(jiǎn)單合取式中不含有某個(gè)命題變?cè)?，也不含，則將展成形式4）將重復(fù)出現(xiàn)的命題變?cè)?、矛盾式及重?fù)出現(xiàn)的極小項(xiàng)都消去。5）將極小項(xiàng)按順序排列。b) 真值表法c) 由主合取范式求析取范式主析取范式的用途1. 求公式的成真賦值與成假賦值

3、2. 判斷公式的類(lèi)型3. 判斷公式A與B是否等值。4. 解實(shí)際問(wèn)題7. 推理的形式結(jié)構(gòu)（）8. 判斷推理是否正確的方法1) 真值表法2) 等值演算法3) 主析取范式法9. 推理定律（9條）10. 在自然推理系統(tǒng)P中構(gòu)造證明直接證明法附加前提證明法歸謬法11. 一階邏輯命題的符號(hào)化a) “D中所有x都有性質(zhì)F”，符號(hào)化為b) “D中有的x有性質(zhì)F”，符號(hào)化為c) “對(duì)D中所有x而言，如果有性質(zhì)F，x就有性質(zhì)G”，符號(hào)化為d) “對(duì)D中有的x有性質(zhì)F且有性質(zhì)G”，符號(hào)化為e) “對(duì)于D中所有x,y而言，若x有性質(zhì)F，y有性質(zhì)G，則x與y就有關(guān)系H”,符號(hào)化為f) “對(duì)于D中所有x而言，若x有性質(zhì)F

4、，就存在y有性質(zhì)G，使得x與y有關(guān)系H”，符號(hào)化為g) “存在著D中x有性質(zhì)F，并且對(duì)D中所有y而言，如果y有性質(zhì)G，則x與y就有關(guān)系H”，符號(hào)化為12. 一階邏輯公式及解釋13. 一階邏輯等值式與置換規(guī)則1) 等值式2) 基本的等值式a) 命題邏輯中基本等值式的代換實(shí)例。b) 一階邏輯中重要的等值式14. 求一階邏輯前束范式15. 約束變?cè)c自由變?cè)?6. 一階邏輯的推理理論（）17. 一階邏輯中重要的推理定律18. 自然推理系統(tǒng)F第二部分1. 集合的基本概念2. 集合的基本運(yùn)算3. 有窮集合元素的計(jì)數(shù)（文氏圖或包含排斥原理）4. 鴿籠原理的應(yīng)用5. 集合恒等式（基本證明方法）a) 命題演算

5、法b) 利用包含哦傳遞性c) 反證法命題演算證明法的書(shū)寫(xiě)規(guī)范 (以下的X和Y代表集合公式)（1）證XÍY 任取x， xÎX Þ Þ xÎY （2）證X=Y 方法一 分別證明XÍY和YÍX 方法二 任取x， xÎX Û Û xÎY注意：在使用方法二的格式時(shí)，必須保證每步推理都是充分必要的6. 有序?qū)εc笛卡爾積7. 二元關(guān)系8. 關(guān)系的表示（關(guān)系矩陣，關(guān)系圖）9. 關(guān)系的性質(zhì)（自反，反自反，對(duì)稱(chēng)，反對(duì)稱(chēng)，傳遞）表格（1） 若"x(xA<x,x>ÎR), 則稱(chēng)

6、R在A上是自反的（2） 若"x(xA<x,x>ÏR), 則稱(chēng)R在A上是反自反的.（3） 若"x"y(x,yA<x,y>R<y,x>R), 則稱(chēng)R為A上對(duì)稱(chēng)的關(guān)系.（4） 若"x"y(x,yA<x,y>R<y,x>Rx=y), 則稱(chēng)R為A上的反對(duì)稱(chēng)關(guān)系.（5） "x"y"z(x,y,zA<x,y>R<y,z>R<x,z>R), 則稱(chēng)R是A上的傳遞關(guān)系.。證明：R在A上自反 任取x，有 xA Þ 

7、2;<x,x>ÎR 前提 推理過(guò)程 結(jié)論 R在A上對(duì)稱(chēng) 任取<x,y>，有 <x,y>ÎR Þ Þ<y,x>ÎRR在A上反對(duì)稱(chēng) 任取<x,y>，有 <x,y>ÎR <y,x>ÎR Þ Þ x=yR在A上傳遞 任取<x,y>，<y,z>有 <x,y>ÎR <y,z>ÎR Þ Þ <x,z>ÎR10. 關(guān)系運(yùn)算的定義（定義域，值域，域，逆，右復(fù)合，限制，像，冪，自反閉包，對(duì)稱(chēng)閉包，傳遞閉包及其構(gòu)造）11. 關(guān)系運(yùn)算的性質(zhì)12. 等價(jià)關(guān)系與劃分（等價(jià)關(guān)系證明，等價(jià)類(lèi)，等價(jià)類(lèi)的性質(zhì)，商集，集合A的劃分，一一對(duì)應(yīng)）13. 偏序關(guān)系與偏序集（哈斯圖，特殊元素）14. 函數(shù)（滿(mǎn)射，單射，雙射第四部分1. 圖的定義（平凡圖，零圖，完全圖，子圖，補(bǔ)圖等）2