離散復(fù)習(xí)提綱

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

A為重言式當(dāng)且僅當(dāng),A為矛盾式當(dāng)且僅當(dāng)主析取范式與主合取范式求公式A的主析取范式的方法與步驟等值演算法1）求公式的析取范式；（1）消去除，，以外公式中出現(xiàn)的所有邏輯聯(lián)結(jié)詞。（2）將否定聯(lián)結(jié)詞消去或內(nèi)移到各命題變元之前。如，；；。（3）利用分配律、結(jié)合律將公式轉(zhuǎn)化為合取范式或析取范式。如，；。2）除去中所有永假的析取項；3）若的某個簡單合取式中不含有某個命題變元，也不含，則將展成形式4）將重復(fù)出現(xiàn)的命題變元、矛盾式及重復(fù)出現(xiàn)的極小項都消去。5）將極小項按順序排列。真值表法由主合取范式求析取范式主析取范式的用途求公式的成真賦值與成假賦值判斷公式的類型判斷公式A與B是否等值。解實際問題推理的形式結(jié)構(gòu)（）判斷推理是否正確的方法真值表法等值演算法主析取范式法推理定律（9條）在自然推理系統(tǒng)P中構(gòu)造證明直接證明法附加前提證明法歸謬法一階邏輯命題的符號化“D中所有x都有性質(zhì)F”，符號化為“D中有的x有性質(zhì)F”，符號化為“對D中所有x而言，如果有性質(zhì)F，x就有性質(zhì)G”，符號化為“對D中有的x有性質(zhì)F且有性質(zhì)G”，符號化為“對于D中所有x,y而言，若x有性質(zhì)F，y有性質(zhì)G，則x與y就有關(guān)系H”,符號化為“對于D中所有x而言，若x有性質(zhì)F，就存在y有性質(zhì)G，使得x與y有關(guān)系H”，符號化為“存在著D中x有性質(zhì)F，并且對D中所有y而言，如果y有性質(zhì)G，則x與y就有關(guān)系H”，符號化為一階邏輯公式及解釋一階邏輯等值式與置換規(guī)則等值式基本的等值式命題邏輯中基本等值式的代換實例。一階邏輯中重要的等值式求一階邏輯前束范式約束變元與自由變元一階邏輯的推理理論（）一階邏輯中重要的推理定律自然推理系統(tǒng)F第二部分集合的基本概念集合的基本運算有窮集合元素的計數(shù)（文氏圖或包含排斥原理）鴿籠原理的應(yīng)用集合恒等式（基本證明方法）命題演算法利用包含哦傳遞性反證法命題演算證明法的書寫規(guī)范(以下的X和Y代表集合公式)（1）證XY任取x，xX…xY（2）證X=Y方法一分別證明XY和YX方法二任取x，xX…xY注意：在使用方法二的格式時，必須保證每步推理都是充分必要的有序?qū)εc笛卡爾積二元關(guān)系關(guān)系的表示（關(guān)系矩陣，關(guān)系圖）關(guān)系的性質(zhì)（自反，反自反，對稱，反對稱，傳遞）表格若x(x∈A→<x,x>R),則稱R在A上是自反的若x(x∈A→<x,x>R),則稱R在A上是反自反的.若xy(x,y∈A<x,y>∈R→<y,x>∈R),則稱R為A上對稱的關(guān)系.若xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),則稱R為A上的反對稱關(guān)系.xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),則稱R是A上的傳遞關(guān)系.。證明：R在A上自反

任取x，有

x∈A…<x,x>R

前提推理過程結(jié)論

R在A上對稱

任取<x,y>，有

<x,y>R…<y,x>R

R在A上反對稱

任取<x,y>，有

<x,y>R∧<y,x>R…x=y

R在A上傳遞

任取<x,y>，<y,z>有

<x,y>R∧<y,z>R…<x,z>R

關(guān)系運算的定義（定義域，值域，域，逆，復(fù)合，限制，像，冪，自反閉包，對稱閉包，傳遞閉包及其構(gòu)造）關(guān)系運算的性質(zhì)等價關(guān)系與劃分（等價關(guān)系證明，等價類，等價類的性質(zhì)，商集，集合A的劃分，一一對應(yīng)）偏序關(guān)系與偏序集（哈斯圖，特殊元素）*函數(shù)（滿射，單射，雙射第三部分（×）代數(shù)系統(tǒng)，運算規(guī)律，特殊元的概念及計算，半群，群概念及判別格的定義格的偏序集定義格的代數(shù)系統(tǒng)定義*格的性質(zhì)對偶原理格的運算性質(zhì)偏序與運算的關(guān)系保序性質(zhì)*子格與子格的判別

*子格判別：S非空，且S關(guān)于格L中的運算封閉。分配格，有界格，有補格的概念分配格的判別方法：根據(jù)定義判別：注意在證明L為分配格時，只須證明其中的一個等式即可設(shè)L是格，則L是分配個當(dāng)且僅當(dāng)L不含有與鉆石格或五角格同構(gòu)的子格。格L是分配格當(dāng)且僅當(dāng)?shù)谒牟糠謭D的定義（平凡圖，零圖，基圖，完全圖與競賽圖，子圖，補圖）圖的矩陣表示（關(guān)聯(lián)矩陣，鄰