離散數(shù)學(xué)教案設(shè)計(jì)

PAGEPAGE210滁州學(xué)院計(jì)算機(jī)與信息工程學(xué)院課程教案課程名稱：離散數(shù)學(xué)授課教師：授課對象：授課時(shí)間：

《離散數(shù)學(xué)》教學(xué)大綱（DiscreteMathematic）課程代碼：學(xué)時(shí)：48學(xué)分：3一、課程簡介 本大綱根據(jù)2009版應(yīng)用型人才培養(yǎng)方案制訂。（一）教學(xué)對象：網(wǎng)絡(luò)工程、計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科學(xué)生（二）開課學(xué)期：第三學(xué)期（三）課程類別：專業(yè)基礎(chǔ)課（四）考核方式：考試（五）參考教材：《離散數(shù)學(xué)》第2版鄧輝文清華大學(xué)出版社2010.主要參考書目：[1]邵學(xué)才,葉秀明.離散數(shù)學(xué)[M].北京電子工業(yè)出版社，2009.[2]邵志清,虞慧群.離散數(shù)學(xué)[M].北京電子工業(yè)出版社，2003.[3]屈婉玲.離散數(shù)學(xué)習(xí)題解析[M].北京大學(xué)出版社，2008.本課程的先修課程是高等數(shù)學(xué)、線性代數(shù)，后續(xù)課程包含數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫原理及應(yīng)用、操作系統(tǒng)、數(shù)字邏輯、人工智能、算法分析與設(shè)計(jì)等。二、教學(xué)基本要求與內(nèi)容安排（一）教學(xué)目的與要求離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的學(xué)科,它在各學(xué)科領(lǐng)域特別在計(jì)算機(jī)科學(xué)領(lǐng)域有著廣泛的應(yīng)用，同時(shí)離散數(shù)學(xué)也是計(jì)算機(jī)專業(yè)的許多專業(yè)課程必不可少的先行課程。本課程的教學(xué)目的旨在通過對離散數(shù)學(xué)的教學(xué)，讓學(xué)生不但可以掌握處理如集合、代數(shù)結(jié)構(gòu)和圖等離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且為學(xué)生今后提高專業(yè)理論水平，從事計(jì)算機(jī)行業(yè)的實(shí)際工作提供必備的抽象思維和嚴(yán)格的邏輯推理能力，為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅(jiān)實(shí)的基礎(chǔ)。（二）教學(xué)內(nèi)容安排教學(xué)內(nèi)容教學(xué)要求教學(xué)方法重點(diǎn)(☆)難點(diǎn)(Δ)學(xué)時(shí)分配備注講課實(shí)驗(yàn)上機(jī)其他第一部分?jǐn)?shù)理邏輯講授15.51命題邏輯的基本概念21.1命題與聯(lián)接詞B☆11.2命題公式及其賦值A(chǔ)☆Δ12命題邏輯等值演算3.52.1等值式B☆12.2析取范式與合取范式A☆Δ12.3聯(lián)接詞的完備集C0.52.4可滿足性與消解法B13命題邏輯的推理理論23.1推理的形式結(jié)構(gòu)A☆13.2自然推理系統(tǒng)PBΔ14一階邏輯基本概念24.1一階邏輯命題符號化A☆14.2一階邏輯公式及解釋A☆Δ15一階邏輯等值演算與推理35.1一階邏輯等值式與置換規(guī)則A☆15.2一階邏輯前束范式A☆15.3一階邏輯的推理理論A☆Δ16數(shù)理邏輯在計(jì)算機(jī)中的應(yīng)用3第二部分集合論講授131集合代數(shù)21.1集合的基本概念B0.51.2集合的運(yùn)算A☆0.51.3有窮集的計(jì)數(shù)C0.51.4集合恒等式A☆0.52二元關(guān)系62.1有序?qū)εc笛卡爾積A☆12.2二元關(guān)系A(chǔ)☆12.3關(guān)系的運(yùn)算A☆12.4關(guān)系的性質(zhì)A☆Δ12.5關(guān)系的閉包A☆12.6等價(jià)關(guān)系與劃分A☆Δ13函數(shù)33.1函數(shù)的定義與性質(zhì)A☆0.53.2函數(shù)的復(fù)合與反函數(shù)A☆0.53.3雙射函數(shù)與集合的基數(shù)CΔ13.4一個(gè)電話系統(tǒng)的描述實(shí)例CΔ14集合論在計(jì)算機(jī)中的應(yīng)用2第三部分代數(shù)結(jié)構(gòu)講授61.51代數(shù)系統(tǒng)31.1二元運(yùn)算及其性質(zhì)A☆11.2代數(shù)系統(tǒng)A☆11.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu)BΔ12群與環(huán)32.1群的定義及其性質(zhì)A☆12.2循環(huán)群與置換群A☆Δ2第四部分圖論講授121圖的基本概念2.51.1圖A☆0.51.2連通與回路A☆0.51.3圖的連通性A☆0.51.4圖的矩陣表示A☆0.51.5圖的運(yùn)算A☆Δ0.52歐拉圖與哈密頓圖22.1歐拉圖A☆0.52.2哈密頓圖A☆0.52.3最短路問題與貨郎擔(dān)問題CΔ13樹1.53.1無向樹及其性質(zhì)A☆0.53.2生成樹A☆0.53.3根樹及其應(yīng)用B0.54平面圖34.1平面圖的基本概念B0.54.2歐拉公式B☆0.54.3平面圖的判斷B14.4平面圖的對偶圖C15圖論在計(jì)算機(jī)中的應(yīng)用3（教學(xué)要求：A—熟練掌握；B—掌握；C—了解）三、實(shí)驗(yàn)內(nèi)容本課程無實(shí)驗(yàn)制訂人（簽字）：審核人（簽字）：教學(xué)進(jìn)度2012～2013學(xué)年第1學(xué)期周數(shù)周數(shù)16周計(jì)劃學(xué)時(shí)48學(xué)時(shí)講課48學(xué)時(shí)課堂討論0學(xué)時(shí)實(shí)驗(yàn)課0學(xué)時(shí)習(xí)題課0學(xué)時(shí)其他環(huán)節(jié)0學(xué)時(shí)授課教師姓名趙歡歡職稱助教授課專業(yè)網(wǎng)絡(luò)工程班級2011級課程名稱離散數(shù)學(xué)教材名稱離散數(shù)學(xué)出版社清華大學(xué)出版社周次日期周學(xué)時(shí)其中教學(xué)內(nèi)容摘要（章節(jié)名稱、講述的內(nèi)容提要、實(shí)驗(yàn)的名稱、課堂討論的題目等）講課實(shí)驗(yàn)課習(xí)題課課堂討論其他環(huán)節(jié)第一周9月344第一講集合、映射與運(yùn)算（一）1.1集合的基本概念理論：集合、子集、冪集、n元組、笛卡爾積第二講集合、映射與運(yùn)算（二）1.2映射的有關(guān)概念理論：映射的定義、映射的性質(zhì)、逆映射、復(fù)合映射第二周9月1022第三講集合、映射與運(yùn)算（三）1.3運(yùn)算的定義和性質(zhì)理論：運(yùn)算的定義、運(yùn)算的性質(zhì)第三周9月144第四講集合、映射與運(yùn)算（四）1.4集合的運(yùn)算1.5集合的劃分1.6集合的對等理論：集合的并、交、差、補(bǔ)、對稱差等基本運(yùn)算，集合的劃分與覆蓋、集合對等、可數(shù)集合、不可數(shù)集合第五講關(guān)系（一）2.1關(guān)系的概念理論：n元關(guān)系的定義、2元關(guān)系、關(guān)系的定義域和值域、關(guān)系的表示、函數(shù)的關(guān)系定義第四周9月222第六講關(guān)系（二）2.1關(guān)系的運(yùn)算理論：關(guān)系的集合運(yùn)算、逆運(yùn)算、復(fù)合運(yùn)算、關(guān)系的其他運(yùn)算第五周10月1日44國慶放假第七講關(guān)系（三）2.3關(guān)系的性質(zhì)2.4關(guān)系的閉包理論：關(guān)系的性質(zhì)：自反性、反自反性、對稱性、反對稱性、傳遞性；自反閉包r(R)、對稱閉包s(R)、傳遞閉包t(R)第六周10月822第八講關(guān)系（四）2.5等價(jià)關(guān)系2.6相容關(guān)系2.7偏序關(guān)系理論：等價(jià)關(guān)系的定義、等價(jià)類；相容關(guān)系的定義；偏序關(guān)系的定義、哈斯圖的、偏序集中的特殊元素第七周10月1544第九講命題邏輯（一）3.1命題的有關(guān)概念3.2邏輯聯(lián)接詞理論：命題的定義與真值、原子命題和復(fù)合命題、各種邏輯連接詞的含義，真假的判斷第十講命題邏輯（二）3.3命題公式及其真值表理論：命題公式的定義、命題的符號化、命題公式的真值表、命題公式的類型第八周10月22日22第十一講命題邏輯（三）3.4邏輯等值的命題公式理論：邏輯等值的定義、基本等值式、等值演算法、對偶原理第九周10月29日44第十二講命題邏輯（四）3.5命題公式的范式理論：命題公式的析取范式和合取范式的定義域求法命題公式的主析取范式及主合取范式的定義和求法第十三講命題邏輯（五）3.7命題邏輯中的推理理論：推理形式有效性的定義；基本推理規(guī)則；命題邏輯的自然推理系統(tǒng)第十周11月522第十四講謂詞邏輯（一）4.1個(gè)體、謂詞、量詞和函詞理論：謂詞邏輯概念，謂詞的概念與表示，量詞的概念與表示，個(gè)體域，轄域，約束變元和自由變元的含義第十一周11月144第十五講謂詞邏輯（二）4.2謂詞公式及命題的符號化4.3謂詞公式的解釋及類型理論：謂詞公式的定義，將命題用用符號（個(gè)體，量詞，謂詞）來表示，消去量詞的邏輯等值式，永真式，科滿足式，永假式及中性式的概念第十六講謂詞邏輯（三）4.4邏輯等值的謂詞公式4.5謂詞公式的前束范式理論：謂詞公式等值的定義，基本等值式，前束范式第十二周11月1922第十七講圖論（一）6.1圖的基本概念6.2節(jié)點(diǎn)的度數(shù)6.3子圖，圖的運(yùn)算和圖同構(gòu)理論：圖的定義，鄰接，關(guān)聯(lián)，簡單圖，節(jié)點(diǎn)的度數(shù)，子圖第十三周11月2644第十八講圖論（二）6.4路與回路6.5圖的連通性理論內(nèi)容：路，回路，無向圖的連通性，無向連通圖的點(diǎn)連通度與邊連通度，有向圖的連通性第十九講圖論（三）6.6圖的矩陣表示6.7賦權(quán)圖及最短路徑理論內(nèi)容：圖的鄰接矩陣，可達(dá)矩陣，關(guān)聯(lián)矩陣，賦權(quán)圖，最短路徑第十四周12月322第二十講圖論（四）7.1歐拉圖理論內(nèi)容：歐拉圖的有關(guān)概念，歐拉定理，中國郵遞員問題、Hamilton圖第十五周12月844第二十一講圖論（五）7.2無向樹7.3有向樹理論內(nèi)容：樹的基本概念，最小生成樹，二叉樹的遍歷與表達(dá)式的計(jì)算第二十二講代數(shù)結(jié)構(gòu)（一）5.1代數(shù)結(jié)構(gòu)簡介理論內(nèi)容：代數(shù)結(jié)構(gòu)的定義，半群及獨(dú)異點(diǎn)，子代數(shù)，代數(shù)結(jié)構(gòu)的同態(tài)與同構(gòu)第十六周12月1722第二十三講代數(shù)結(jié)構(gòu)（二）5.2群的定義及性質(zhì)理論內(nèi)容：群的有關(guān)概念，子群，群的同態(tài)第十七周12月2422第二十四講總復(fù)習(xí)系主任簽名：院長簽名：年月日年月日說明：1．本教學(xué)進(jìn)度表由主講教師負(fù)責(zé)填寫，于每學(xué)期開學(xué)第一周內(nèi)送交教師所在系，經(jīng)領(lǐng)導(dǎo)審定、簽字后備查。2．此表一式三份，其中，任課教師一份，教師所在系一份，教務(wù)處一份。第一講：集合、映射和運(yùn)算（一）一、教學(xué)目標(biāo)1.掌握集合的概念與表示2.理解子集、冪集、n元組與笛卡兒積的概念3.掌握子集，冪集，笛卡爾積的求法二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：集合的概念，子集，冪集，笛卡爾積的概念及求法2.難點(diǎn)：冪集三、教學(xué)內(nèi)容與教學(xué)過程1.進(jìn)行自我介紹（5分鐘）姓名，聯(lián)系方式，專業(yè)方向。建議學(xué)生用電子郵件方式聯(lián)系。2.進(jìn)行課程簡介（10分鐘）離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及相互之間關(guān)系的學(xué)科是一門專業(yè)基礎(chǔ)課，是數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計(jì)算機(jī)組成原理、數(shù)據(jù)庫原理等課程的數(shù)學(xué)基礎(chǔ)。特點(diǎn)：知識點(diǎn)集中，概念，定理多；方法性強(qiáng)；學(xué)數(shù)學(xué)就要做數(shù)學(xué)成績評定：平時(shí)成績(到課情況，書面作業(yè)，平時(shí)測驗(yàn))占30%,期末考試占70%3.進(jìn)入主題，開始第一講(1)集合的有關(guān)概念(20分鐘)①集合定義：集合是具有某種特定性質(zhì)的對象匯集成的一個(gè)整體，通常用大寫字母A,B,C,D表示。例如：滁州學(xué)院全體學(xué)生計(jì)算機(jī)與信息工程學(xué)院所有女生常見的數(shù)的集合：N,N+,Z,Q,R,C②元素集合中的每一個(gè)對象稱為該集合的元素，通常用小寫字母a,b,c,d,x,等表示例如：滁州學(xué)院的每個(gè)學(xué)生計(jì)算機(jī)與信息工程學(xué)院的每個(gè)女生N：0、1、2、3…③集合的表示方法列舉法：Z={…,-2,-1,0,1,2,…}描述法：{x|x是自然數(shù)且x小于10}遞歸法文氏圖：特殊集合：全集U,空集④元素與集合x∈A或|A|表示集合A中的元素個(gè)數(shù)注意：集合中的元素可以是集合，如A={a,{a,b},b,c},|A|=4,{a,b}∈A注：集合中的元素?zé)o順序；集合中無重復(fù)元素例：指出下列哪些是集合，哪些不是集合？中國人的集合；百貨商店里好看的花布的集合；1000以內(nèi)的素?cái)?shù)的集合；26個(gè)英文字母組成的集合；這個(gè)班里高個(gè)子學(xué)生的集合；直線y＝2x-5上的點(diǎn)的集合。(2)集合之間的關(guān)系 ①子集（15分鐘）定義：若A中的任意元素都屬于B，則A是B的子集，稱A包含于B或B包含A，，包括的兩層含義：包含與真包含（A≠B），，A是B的真子集注意：屬于（元素與集合的關(guān)系）與包含于（集合與集合的關(guān)系）的區(qū)別例：A={1,2,3,4}，B={2,4}或定理1-1：A定理1-2：（自反性）則A=B則（傳遞性）用定義進(jìn)行證明定理1-3：A=B的充要條件是注：該定理是證明兩個(gè)集合相等的基本方法該定理與定理1-2中的(2)的區(qū)別例1-2注：A中有一個(gè)元素不屬于C，則，反證法是一種很好的方法②冪集（15分鐘）定義：由X的所有子集組成的集合，例：x={1,2}，Y={a,b,c}例1-3 注：若|X|=n,P(x)的元素有：；由一個(gè)元素構(gòu)成的子集；由兩個(gè)元素構(gòu)成的子集；…由n個(gè)元素構(gòu)成的子集計(jì)數(shù)的基本原理：加法原理：圖示乘法原理：圖示定理1-4：若|X|=n,|P(X)|=2n證明：加法原理：二項(xiàng)式定理：乘法原理：注：每個(gè)元素的參與與否構(gòu)成不同的子集③n元組（5分鐘）定義：論域U中選取的n個(gè)元素按照一定的順序排列，得到n元有序組，稱n元組，記為：(x1,x2,x3,…,xn)或<x1,x2,x3,…,xn>例：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)是2元組；空間直角坐標(biāo)系中點(diǎn)的坐標(biāo)是3元組；n元組在數(shù)據(jù)結(jié)構(gòu)中是一個(gè)表有序?qū)?，序偶?元組注：(x,y)≠(y,x)④笛卡爾積（10分鐘）定義：設(shè)是集合，稱為A1,A2,…An的笛卡爾積（直積，叉積），記為：例：A={a,b},B={1,2}，例1-4注：一般來說，定理1-5：若|A|=m,|B|=n,則||=m×n4.教學(xué)小結(jié)（5分鐘）本講首先介紹了集合的概念與表示方法，接著介紹了集合之間的關(guān)系——子集與冪集，n元組，笛卡爾積的概念及相關(guān)定理。四、作業(yè)與實(shí)驗(yàn)（5分鐘）1.書面作業(yè)：習(xí)題1.11、2、3、7、102.上機(jī)作業(yè)：無

第二講：集合、映射和運(yùn)算（二）一、教學(xué)目標(biāo)1.掌握映射的概念與表示2.理解映射的三種性質(zhì)：單射、滿射、雙射，會判斷某個(gè)具體映射是否具有這些性質(zhì)3.掌握逆映射的含義，復(fù)合映射的定義及性質(zhì)二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：理解和判斷映射的三種性質(zhì)，逆映射，復(fù)合映射2.難點(diǎn)：映射三種性質(zhì)的判斷，復(fù)合映射的性質(zhì)三、教學(xué)內(nèi)容與教學(xué)過程1.習(xí)題講解（10分鐘）2.上講內(nèi)容回顧（3分鐘）集合的概念：集合、元素、集合的表示方法集合間的關(guān)系：子集、冪集、n元組、笛卡爾積(1)映射的定義（15分鐘）定義：對于A,B,若存在對應(yīng)法則f，對于，唯一的與它對應(yīng)，稱f是A到B的一個(gè)映射或一個(gè)函數(shù)。記為：f:A→B（圖示）例：CeilingfunctionFloorfunction取整函數(shù)定義域：自變量x的取值范圍值域：函數(shù)值y的取值范圍像：為X在映射f下的像原像：為Y在映射f下的原像注：全函數(shù)即=A；為x在映射f下的像：A到B的所有映射組成的集合定理1-6：|A|=m,|B|=n,則（證明）(2)映射的性質(zhì)①單射(一對一映射)（10分鐘）定義：，可推出x1=x2或，若x1≠x2，可得出例1-6：設(shè)則f是N到N的單射，試證明之。證：對于，由得出，進(jìn)而x1=x2(使用定義證明)②滿射（10分鐘）定義：對于，使得y=f(x)充要條件：=B例1-7：設(shè)，則f是Z到N的滿射，試證明之。證：對于取,顯然有（使用定義證明）③雙射（一一對應(yīng)）（5分鐘）定義:既單射又滿射例1-8例1-9：建立一個(gè)（0,1）到R的一一對應(yīng)解：置換：A到A的雙射(3)逆映射（逆函數(shù)，反函數(shù)）（10分鐘）定義：f:A→B，將f的方向逆轉(zhuǎn)后，得到的集合B到集合A的映射定理1-7：f的逆映射存在的充要條件是f是雙射（加以說明解釋）注：若f是雙射，則也是雙射，且例1-11：判斷所給出的映射是否有逆射，若有，求出其逆映射①②解：①∵f(2)=f(-2)=4,∴根據(jù)單射定義知f不是單射，進(jìn)而其不是雙射，根據(jù)定理1-7知其不存在逆映射②顯然g是雙射，其逆映射為(4)復(fù)合映射（20分鐘）定義:設(shè)對于，令，則h是A到C的映射，h為f和g的復(fù)合映射或復(fù)合函數(shù)，記為（圖示）注：條件:例1-12例1-13注：一般來說即使和都有意義，也不能保證成立恒等映射(IA)：定理1-9：若是雙射，則若是雙射，則定理1-10：若f和g是單射，則是單射（證明）若f和g是滿射，則是滿射（證明）若f和g是雙射，則是雙射且定理1-11：設(shè)若是單射，則f是單射，但g不一定（證明）若是滿射，則g是滿射，而f不一定（證明）定理1-12設(shè)，則4.教學(xué)小結(jié)（5分鐘）本講首先介紹了映射（函數(shù)）的定義及定義域、值域、像、原像等相關(guān)概念；接著介紹了映射的三種性質(zhì)：單射，滿射，雙射；最后介紹了逆映射的定義及復(fù)合映射的定義及其具有的相關(guān)性質(zhì)。四、作業(yè)與實(shí)驗(yàn)（2分鐘）1.書面作業(yè)：習(xí)題1.21、2、6、11、14.2.上機(jī)作業(yè)：無第三講：集合、映射和運(yùn)算（三）一、教學(xué)目標(biāo) 1.理解運(yùn)算的定義2.掌握運(yùn)算的表示及常用運(yùn)算3.理解運(yùn)算的性質(zhì)并能判斷具體運(yùn)算是否具有某些性質(zhì)二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：運(yùn)算的定義，運(yùn)算的性質(zhì)2.難點(diǎn)：運(yùn)算性質(zhì)的判定三、教學(xué)內(nèi)容與教學(xué)過程1.習(xí)題講解（5分鐘）2.上講內(nèi)容回顧（5分鐘）映射的定義映射的性質(zhì)：單射，滿射，雙射逆映射復(fù)合映射3.進(jìn)入主題，開始第二講。本講知識點(diǎn)概括(1)運(yùn)算的定義（25分鐘）①定義:設(shè)和B是集合，若，稱f為到B的n元運(yùn)算。A到B的n元運(yùn)算，或A上的n元運(yùn)算：A上的n元封閉運(yùn)算（代數(shù)運(yùn)算）：，有例：判定取絕對值運(yùn)算||、加法運(yùn)算+、取大運(yùn)算max是否是自然數(shù)集合N(Z)上的代數(shù)運(yùn)算。解：例：判定減法運(yùn)算-,取小運(yùn)算min是否是自然數(shù)集合N上的代數(shù)運(yùn)算。解：例：判斷數(shù)的加法運(yùn)算是否是集合A={2n|n∈N}上的代數(shù)運(yùn)算？解：例：將十進(jìn)制數(shù)273轉(zhuǎn)換成八進(jìn)制解：273=,,②模運(yùn)算定義：，是使成立的整數(shù)r,即x除以m的余數(shù)。例：16(mod3)、-8(mod5)、9(mod2)模m加法，模m乘法例：m=5,③最大公約數(shù)，最小公倍數(shù)若d|m且d|n,則d是m,n的公約數(shù)，用gcd(m,n)表示m,n的最大公約數(shù)若m|d且n|d，則d是m,n的公倍數(shù)，用lcm(m,n)表示m,n的最小公倍數(shù)。注：Gcd與lcm分別記為[,]和（，）gcd(m,n)=gcd(|m|,|n|)且lcm(m,n)=lcm(|m|,|n|)素因數(shù)分解：（對于大于1的正整數(shù)n都可以分解成一些素?cái)?shù)乘積）Euclid算法例1-19若gcd(m,n)=1,稱m和n互素。歐拉函數(shù)：表示小于等于n且與n互素的正整數(shù)的個(gè)數(shù)④運(yùn)算表給定集合A，則集合A上的1元或2元運(yùn)算可以用運(yùn)算表來表示例：A={a,b,c},**abcabcababccbca思考：A上的封閉的1元，2元，3元運(yùn)算的個(gè)數(shù)是多少？3339327(2)運(yùn)算的性質(zhì)①對合性（5分鐘）定義：設(shè)*是A上的一元代數(shù)運(yùn)算，例：？②冪等性（5分鐘）冪等元：定義：A中的每個(gè)元素對于*都是冪等元例：*123112322323313例：③交換性（5分鐘）定義：對于A上的二元運(yùn)算*,,均有例：R上的+具有交換性R上的-，映射的復(fù)合運(yùn)算?④結(jié)合性（5分鐘）定義：例:映射的復(fù)合運(yùn)算具有結(jié)合性R上的+具有結(jié)合性R上的-？⑤單位元素（幺元素）（5分鐘）定義：對于A上的二元運(yùn)算*，，使得對于例：R關(guān)于加法運(yùn)算+的單位元素是0R關(guān)于乘法運(yùn)算的單位元素是1R關(guān)于減法運(yùn)算-的單位元素是？定理1-3：若A關(guān)于*有單位元素，則單位元素是唯一的證明：設(shè)e1,e2是A關(guān)于*的單位元素，則e1=e1*e2=e2⑥零元素（5分鐘）定義：對于A上的二元運(yùn)算*，，使得對于例:R關(guān)于乘法運(yùn)算的零元素是0R關(guān)于減法運(yùn)算-的零元素是？R關(guān)于加法運(yùn)算的零元素是？定理1-4：若A關(guān)于*有零元素，則零元素是唯一的證明：設(shè)e1,e2是A關(guān)于*的零元素，則e1=e1*e2=e2⑦逆元素（5分鐘）前提：A關(guān)于二元運(yùn)算*有單位元素e定義：，使得：例：R上的加法運(yùn)算+：x+(-x)=0=(-x)+xR上的乘法運(yùn)算：注：逆元不一定存在，存在不一定唯一，參見表1-5定理1-5：若A關(guān)于*運(yùn)算有單位元素為e且*運(yùn)算滿足結(jié)合律，若對于A中的x有左逆元y與右逆元z，則y=z,此逆元唯一證明：y*x=e,x*z=ey=y*e=y*(x*z)=(y*x)*z=e*z=z⑧消去性（分鐘）定義：若A關(guān)于*有零元，則記為，對于，若例1-31Z上的加法運(yùn)算+和乘法運(yùn)算×均滿足消去律.⑨分配性（5分鐘）定義：是A上的兩個(gè)二元運(yùn)算，對于則稱*關(guān)于是可分配的⑩吸收性（2分鐘）定義：是A上的兩個(gè)二元運(yùn)算，對于則稱*關(guān)于是可吸收的eq\o\ac(○,⒒)德摩根律（3分鐘）定義：是A上的一元運(yùn)算，是A上的兩個(gè)二元運(yùn)算，對于4.教學(xué)小結(jié)（3分鐘）本講首先介紹了運(yùn)算的定義并介紹了幾種常用的運(yùn)算，接著介紹了運(yùn)算的性質(zhì)：對合性、冪等性、交換性、結(jié)合性、單位元素、零元素、逆元素、消去性、分配性、吸收性、德·摩根律，并結(jié)合之前所學(xué)知識講解運(yùn)算的性質(zhì)。四、作業(yè)與實(shí)驗(yàn)（2分鐘）書面作業(yè)：習(xí)題1.3：1、3、5、6、82.上機(jī)作業(yè)：無

第四講：集合、映射和運(yùn)算（四）一、教學(xué)目標(biāo)1.掌握集合的各種運(yùn)算2.理解各種集合運(yùn)算所滿足的性質(zhì)3.掌握集合的劃分與覆蓋的概念4.了解集合的對等，集合的基數(shù)，可數(shù)集合等概念二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：集合的運(yùn)算——并、交、補(bǔ)、差、對稱差集合運(yùn)算性質(zhì)2.難點(diǎn)：集合運(yùn)算等值式的證明，集合的對等、基數(shù)三、教學(xué)內(nèi)容與教學(xué)過程1.上講內(nèi)容回顧（5分鐘）運(yùn)算的定義運(yùn)算的性質(zhì)：對合性、冪等性、交換性、結(jié)合性、單位元素、零元素、逆元素、消去性、分配性、吸收性、德·摩根律2.進(jìn)入主題、開始第四講本講知識點(diǎn)概括(1)集合的運(yùn)算 ①并運(yùn)算（15分鐘）定義：定理1-16：是包含A和B的最小集合定理1-17：并運(yùn)算滿足的性質(zhì)：（交換律）（結(jié)合律）（冪等律）（是∪運(yùn)算的單位元素）（是∪運(yùn)算的零元素）例1-38:設(shè)f:A?B,X,YíA,則證明：證明：②交運(yùn)算（15分鐘）定義：定理1-18：是包含在A和B的最大集合定理1-19：交運(yùn)算滿足的性質(zhì)：（冪等律）（交換律）（結(jié)合律）（是運(yùn)算的零元素） （U是運(yùn)算的單位元素）例：定理1-20：并運(yùn)算與交運(yùn)算之間滿足的性質(zhì)：

例1-41：證：③補(bǔ)運(yùn)算（10分鐘）定義：例1-42：（A的補(bǔ)集依賴于全集U的選取）A={a,b,c}U={a,b,c,d}定理1-21：定理1-22：德·摩根律：P25：④差運(yùn)算（10分鐘）定義：例1-43：定理1-23：證明：例1-45：證明：證：例1-46：例1-47：⑤對稱差運(yùn)算（10分鐘）定義：例定理1-24：容斥原理形式：或：例：求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除數(shù)有多少個(gè)？解：|S|=1000|A|=?1000/5?=200,|B|=?1000/6?=166|A?B|=?1000/lcm(5,6)?=?1000/33?=33（2）集合的劃分與覆蓋（12分鐘）①劃分定義：其中：例1-53：設(shè)A={a,b,c},則A的所有不同的劃分分別為:②覆蓋設(shè)A是集合,由A的若干非空子集構(gòu)成的集合稱為A的覆蓋,如果這些非空子集的并等于A.（3）集合的對等（10分鐘）定義：A～B存在雙射f:A?B.例：(0,1)～R集合的基數(shù)：無限集合A若集合A和B對等,則稱這兩個(gè)集合的基數(shù)相同.例：可數(shù)集合：能與自然數(shù)集合N對等的集合3.教學(xué)小結(jié)（2分鐘）本講首先介紹了集合的各種運(yùn)算（并，交，補(bǔ)，差，對稱差）及其滿足的性質(zhì)，接著介紹了集合的劃分與覆蓋的概念；最后介紹了集合對等、集合的基數(shù)及可數(shù)集合。四、作業(yè)與實(shí)驗(yàn)（1分鐘）1.書面作業(yè)：習(xí)題1.45、8、10、13.習(xí)題1.5：1、72.上機(jī)作業(yè)：無第五講：關(guān)系（一）一、教學(xué)目標(biāo)1.掌握關(guān)系的概念尤其是二元關(guān)系的概念2.掌握關(guān)系的定義域和值域3.掌握關(guān)系的三種表示方法4.理解函數(shù)的關(guān)系定義二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：二元關(guān)系概念、關(guān)系的三種表示方式、函數(shù)的關(guān)系定義2.難點(diǎn)：關(guān)系的概念三、教學(xué)內(nèi)容與教學(xué)過程1.習(xí)題講解（15分鐘）2.上章內(nèi)容回顧（5分鐘）集合的有關(guān)概念映射的有關(guān)概念運(yùn)算的定義與性質(zhì)集合的運(yùn)算、集合的劃分與覆蓋、集合的對等3.進(jìn)入主題，開始第五講本講知識點(diǎn)介紹(1)關(guān)系的定義①關(guān)系的概念（15分鐘）引例：A={張三,李四,王五};B={英語,C語言,離散數(shù)學(xué),數(shù)據(jù)結(jié)構(gòu),匯編語言};C={優(yōu),良,合格,不合格}.A與B之間的關(guān)系R={(張三,離散數(shù)學(xué)),(張三,數(shù)據(jù)結(jié)構(gòu)),(張三,英語),(李四,數(shù)據(jù)結(jié)構(gòu)),(王五,C語言),(王五,匯編語言)}íA′B.A,B與C之間的關(guān)系S={(張三,離散數(shù)學(xué),優(yōu)),(張三,數(shù)據(jù)結(jié)構(gòu),良),(張三,英語,優(yōu)),(李四,數(shù)據(jù)結(jié)構(gòu),優(yōu)),(王五,C語言,合格),(王五,匯編語言,良)}íA′B′C.定義：是集合，，則R為間的n元關(guān)系特別的為A上的n元關(guān)系注（兩層含義）：集合、關(guān)系例：A={王，李，張，黃}，B={100米，400米，鉛球，跳遠(yuǎn)}，C={第一名，第二名，第三名，優(yōu)秀獎(jiǎng)}R={(王，100米，第二名)，（李，鉛球，優(yōu)秀獎(jiǎng)），（張，100米，第一名），（黃，跳遠(yuǎn)，第二名）}二元關(guān)系的定義：兩個(gè)集合A和B（可以相同）之間的關(guān)系稱為二元關(guān)系A(chǔ)到B的關(guān)系：A上的關(guān)系：例：A={甲，乙，丙}R={(乙，甲)，（乙，丙），（甲，丙）}注：(x,y)表示x勝y例：A={張三，李四，王五}，B={教師，輔導(dǎo)員，導(dǎo)師}R={（張三，輔導(dǎo)員），（張三，教師），（李四，教師），（王五，導(dǎo)師），（王五，教師）}例2-1：例：A={a,b},R是P(A)上的包含關(guān)系，R={(x,y)|x,y∈P(A)且}P(A)=注意：關(guān)系的次序 定理2-1：若，則A到B的關(guān)系有若，則A上的關(guān)系有注：A到B的關(guān)系是A×B的子集②三種特殊的關(guān)系（5分鐘）空關(guān)系：A到B的空關(guān)系A(chǔ)上的空關(guān)系全關(guān)系：A到B的全關(guān)系 A上的全關(guān)系恒等關(guān)系：例：A={0,1,2}={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)}IA={(0,0),(1,1),(2,2)}③關(guān)系符號（10分鐘）定義：若(x,y),則可記為例：實(shí)數(shù)集合R上的大于“>”關(guān)系：例：整數(shù)集Z上的整除關(guān)系“|”整除性質(zhì)：例：模m同余關(guān)系性質(zhì)：④關(guān)系的定義域和值域（5分鐘）定義域:設(shè),,即R中所有有序?qū)χ械谝晃恢迷亟M成的集合,它顯然是A的子集.值域：設(shè)RíA′B,ranR={y|y?B,存在x?A,使得(x,y)?R},即R中所有有序?qū)χ械诙恢迷亟M成的集合,它是B的子集.：R={(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)},則domR={1,2,3,4}，ranR={1,2,3,4}.(2)關(guān)系的表示（20分鐘）①集合表示法列舉法：把關(guān)系內(nèi)部的元素全部列舉出來描述法：把關(guān)系內(nèi)部成員的性質(zhì)描述出來（同集合）②關(guān)系圖表示法情形1R是A到B的關(guān)系A(chǔ)={a,b,c,d},B={1,2,3},R={(a,2),(a,3),(c,2),(d,2)}.情形2R是A上的關(guān)系A(chǔ)={a,b,c,d}，注：有向邊③關(guān)系矩陣表示法定義：例2-13:A={a,b,c,d},B={1,2,3},R={(a,2),(a,3),(c,2),(d,2)}.例：A={a,b,c},(3)函數(shù)的關(guān)系定義（5分鐘）①函數(shù)到關(guān)系的轉(zhuǎn)換例：A={a,b,c},B={1,2,3},f:A?B,f(a)=2,f(b)=3,f(c)=3.②關(guān)系能夠轉(zhuǎn)換成函數(shù)的條件例：，不能轉(zhuǎn)換成函數(shù)。例2-164.教學(xué)小結(jié)（3分鐘）本講首先講解關(guān)系的概念與表示，特別介紹了二元關(guān)系，同時(shí)描述了三種特殊的關(guān)系：空關(guān)系、全關(guān)系、恒等關(guān)系，然后講解了關(guān)系的三種表示方式：集合表示法、關(guān)系圖表示法、關(guān)系矩陣表示法，接著講解了關(guān)系與函數(shù)的區(qū)別與聯(lián)系及它們間的轉(zhuǎn)換。四、作業(yè)與實(shí)驗(yàn)（2分鐘）1.書面作業(yè)：習(xí)題2.1：2、4(2)(4)(5)、13、14.上機(jī)作業(yè)：無 第六講：關(guān)系（二）一、教學(xué)目標(biāo)1.掌握關(guān)系的集合運(yùn)算2.掌握關(guān)系的逆運(yùn)算，逆關(guān)系的關(guān)系矩陣、關(guān)系圖及逆關(guān)系的定理3.掌握復(fù)合關(guān)系、復(fù)合關(guān)系相關(guān)定理4.了解函數(shù)的復(fù)合運(yùn)算二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：復(fù)合關(guān)系、逆關(guān)系的概念及相關(guān)性質(zhì)2.難點(diǎn)：復(fù)合關(guān)系、逆關(guān)系的性質(zhì)三、教學(xué)內(nèi)容與教學(xué)過程1.習(xí)題講解（10分鐘）2.上講內(nèi)容回顧（5分鐘）N元關(guān)系的定義2元關(guān)系關(guān)系的定義域與值域關(guān)系的表示函數(shù)的關(guān)系定義3.進(jìn)入主題，開始第六講。(1)關(guān)系的集合運(yùn)算（15分鐘）關(guān)系的幾種常見集合運(yùn)算:注：解：例2-17(2)關(guān)系的逆運(yùn)算（20分鐘）為何考慮關(guān)系的逆運(yùn)算?若x是y的老師,則y是x的學(xué)生,…①定義：注：就是將所有R中的有序?qū)χ械膬蓚€(gè)元素交換次序，例2-18：A={a,b,c,d},B={1,2,3},R={(a,3),(c,2),(a,2),(b,2)}.則②逆關(guān)系的關(guān)系圖有向線條反向（圖示例2-18）③逆關(guān)系的關(guān)系矩陣原關(guān)系的關(guān)系矩陣的轉(zhuǎn)置（示例2-18）④逆運(yùn)算的性質(zhì)：定理2-2：（對合律）定理2-3：逆運(yùn)算與關(guān)系的集合運(yùn)算并,交,補(bǔ)的關(guān)系證明：（）：(3)關(guān)系的復(fù)合運(yùn)算（35分鐘）為何考慮關(guān)系的復(fù)合運(yùn)算?若x是y的母親,y是z的妻子,則x是z的岳母,…①關(guān)系R到關(guān)系S的復(fù)合運(yùn)算（10分鐘）例：，則：例2-19：借助關(guān)系圖理解復(fù)合運(yùn)算：關(guān)系矩陣：②復(fù)合關(guān)系的性質(zhì)（10分鐘）R?S1S?R.例：R={(x,y)|x,y?A,y=x+1或y=x/2}S={(x,y)|x,y?A,x=y+2}≠定理2-4：證明思路：定理2-5：定理2-6：證明：注：本性質(zhì)與矩陣的有關(guān)運(yùn)算性質(zhì)類似,請注意順序定理2-7：③冪運(yùn)算（10分鐘）冪的表示方式：例2-23：設(shè)A={a,b,c},集合A上的關(guān)系R={(a,b),(b,c),(c,a)},試計(jì)算冪運(yùn)算的性質(zhì)：④函數(shù)的復(fù)合運(yùn)算（5分鐘）設(shè)f:A?B,g:B?C,函數(shù)f與函數(shù)g的復(fù)合記為f?g:若f(x)=y且g(y)=z,則(f?g)(x)=g(f(x))=z.由于fíA′B,gíB′C,關(guān)系f與關(guān)系g的復(fù)合記為f?g:若(x,y)?f且(y,z)?g,則(x,z)?f?g.注：函數(shù)f與函數(shù)g的復(fù)合f?g與將其看作關(guān)系時(shí)關(guān)系f與關(guān)系g的復(fù)合是一致的4.教學(xué)小結(jié)（3分鐘）本講分別介紹了關(guān)系的集合運(yùn)算、逆運(yùn)算，復(fù)合運(yùn)算，并且對復(fù)合關(guān)系、逆關(guān)系的定義、表示方式、相應(yīng)的關(guān)系矩陣進(jìn)行了講解，還介紹了它們之間滿足的相關(guān)性質(zhì)，最后介紹了函數(shù)的復(fù)合運(yùn)算。四、作業(yè)與實(shí)驗(yàn)（2分鐘）1.書面作業(yè)：習(xí)題2.21、3、6、8、12(選).2.上機(jī)作業(yè)：無 第七講：關(guān)系（三）一、教學(xué)目標(biāo)1.理解關(guān)系的各種性質(zhì)2.掌握滿足各種性質(zhì)的關(guān)系的關(guān)系矩陣和關(guān)系圖3.理解閉包的含義4.掌握閉包的幾個(gè)關(guān)鍵5.掌握閉包的構(gòu)造二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：自反性、反自反性、對稱性、反對稱性、傳遞性概念的理解，閉包的理解與構(gòu)造2.難點(diǎn)：同上三、教學(xué)內(nèi)容與教學(xué)過程1.上講內(nèi)容回顧（5分鐘）關(guān)系的集合運(yùn)算關(guān)系的逆運(yùn)算關(guān)系的復(fù)合運(yùn)算2.進(jìn)入主題，開始第七講本講知識點(diǎn)概括(1)關(guān)系的性質(zhì)自反性（10分鐘）定義：對于集合A上的元素a屬于A，有(a,a)屬于R,那么R就是一個(gè)自反關(guān)系例2-25：A={a,b,c,d},R={(a,a),(a,b),(b,b),(c,c),(c,a),(d,d)}?注：Z上的整除關(guān)系|是自反的;P(X)上的包含關(guān)系í是自反的;R上的小于等于關(guān)系￡是自反的;R上的小于關(guān)系<不是自反的.定理：R自反?注：空關(guān)系?是空集?上的自反關(guān)系.關(guān)系矩陣：對角線元素都為1關(guān)系圖：結(jié)點(diǎn)含有環(huán)反自反性（10分鐘）定義：設(shè)RíA′A,若對于任意x?A,均有(x,x)?R,則稱R是A上的反自反關(guān)系,或稱R具有反自反性.例2-26：A={a,b,c,d},R={(b,a),(a,b),(b,c),(c,d),(c,a)}?注：Z上的整除關(guān)系|不是反自反的;P(X)上的包含關(guān)系í不是反自反的;R上的小于等于關(guān)系￡不是反自反的;R上的小于關(guān)系<是反自反的.定理：R反自反?注：空關(guān)系?是空集?上的反自反關(guān)系.關(guān)系矩陣：對角線元素全為0關(guān)系圖：結(jié)點(diǎn)沒有環(huán)思考：A上的自反關(guān)系與反自反關(guān)系的區(qū)別與聯(lián)系?對稱性（10分鐘） 定義：設(shè)RíA′A,對于任意x,y?A,若(x,y)?R,則(y,x)?R,則稱R是A上的對稱關(guān)系,或稱R是對稱的,或稱R具有對稱性例2-28：A={a,b,c,d},R={(b,a),(a,b),(b,b),(d,c),(c,d)}?注：Z上的整除關(guān)系|不是對稱的;P(X)上的包含關(guān)系í(一般來說)不是對稱的;R上的小于等于關(guān)系￡不是對稱的;R上的小于關(guān)系<不是對稱的;三角形之間的相似關(guān)系~是對稱的;Z上的模k同余關(guān)系ok是對稱的.定理2-11：R對稱?R=R-1 關(guān)系矩陣：關(guān)于對角線對稱圖關(guān)系圖：要么有雙向環(huán)、要么沒有反對稱性（10分鐘）定義：設(shè)RíA′A,對于任意x,y?A,若(x,y)?R且(y,x)?R,一定有x=y,則稱R是A上的反對稱關(guān)系,或稱R具有反對稱性.例2-29：A={a,b,c,d},R={(a,a),(a,b),(b,b),(b,c),(d,c)}?注：Z上的整除關(guān)系|不是反對稱的,因?yàn)?|-2且-2|2;P(X)上的包含關(guān)系í是反對稱的;R上的小于等于關(guān)系￡是反對稱的;R上的小于關(guān)系<是反對稱的.定理2-12：R反對稱?關(guān)系矩陣:關(guān)于主對角線對稱的元素不能同時(shí)為1關(guān)系圖:兩點(diǎn)之間要么無邊，要么只有一條邊思考：反對稱性與對稱性之間的區(qū)別與聯(lián)系傳遞性（10分鐘）定義：設(shè)RíA′A,對于任意x,y,z?A,若(x,y)?R且(y,z)?R,均有(x,z)?R,則稱R是A上的傳遞關(guān)系,或稱R具有傳遞性.例2-31：A={a,b,c,d},R=(a,a),(a,b),(b,b),(b,c),(a,c),(c,a)}?注：Z上的整除關(guān)系|是傳遞的;P(X)上的包含關(guān)系í是傳遞的;R上的小于等于關(guān)系￡是傳遞的;R上的小于關(guān)系<是傳遞的.定理2-13：R傳遞?R?RíR.證明:(T)設(shè)(x,z)?R?R,則存在y?A,使得(x,y)?R,(y,z)?R.因?yàn)镽傳遞,所以(x,z)?R.(ü)對于任意x,y,z?A,若(x,y)?R且(y,z)?R,則(x,z)?R?RíR,(x,z)?R.例2-33:A={a,b,c,d},R1={(a,b),(a,c)}傳遞,R2={(a,b)}也傳遞?,傳遞性的關(guān)系圖:定理2-13:R傳遞?R?RíR.(2)關(guān)系的閉包 ①自反閉包r(R)（10分鐘）定義：設(shè)RíA′A,稱最小的包含R的自反關(guān)系為R的自反閉包,記為r(R).滿足3個(gè)條件:包含R；自反性；最小性.例2-38：設(shè)A={a,b,c},R={(a,a),(b,a),(b,c),(c,a),(a,c)},求出R的自反閉包.解：r(R)=Rè{(b,b),(c,c)}定理2-14:生成自反閉包關(guān)系圖的變化：R中不含環(huán)的添加環(huán)生成自反閉包關(guān)系矩陣的變化：把對角線上是0的元素全部改成1 ②對稱閉包s(R)（10分鐘）定義：設(shè)RíA′A,稱最小的包含R的對稱關(guān)系為R的對稱閉包,記為s(R).滿足3個(gè)條件:包含R；對稱性；最小性.例2-15：解：定理2-15： 生成對稱閉包關(guān)系圖的變化：只有一邊的添加一邊生成對稱閉包關(guān)系矩陣的變化：關(guān)于對角線對稱的元素相等③傳遞閉包r(R)（10分鐘）定義：設(shè)RíA′A,稱最小的包含R的傳遞關(guān)系為R的傳遞閉包,記為t(R).滿足3個(gè)條件:包含R；傳遞性；最小性.例：設(shè)A={a,b,c},R={(a,b),(b,c),(b,a)},求t(R).解：t(R)={(a,b),(b,c),(b,a),(a,c),(a,a),(b,b)}.例:A={a,b,c,d}R={(a,b),(b,c),(c,d)}t(R)={(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)}定理2-16：定理2-17：若|A|=n31,RíA′A,則傳遞閉包的關(guān)系圖:從a到b的邊存在，從b到c的邊存在，那么添加從a到c的邊3.教學(xué)小結(jié)（3分鐘）本講重點(diǎn)介紹了關(guān)系的幾個(gè)性質(zhì)：自反性、反自反性、對稱性、反對稱性、傳遞性的定義、及他們的關(guān)系矩陣、關(guān)系圖；接著介紹了自反閉包，對稱閉包，傳遞閉包的定義及構(gòu)造。四、作業(yè)與實(shí)驗(yàn)（2分鐘）1.書面作業(yè)：習(xí)題2.3：3、5、8、9習(xí)題2.4：2、3、9、102.上機(jī)作業(yè)：無第八講：關(guān)系（四）一、教學(xué)目標(biāo)1.掌握等價(jià)關(guān)系，等價(jià)類及商集的概念2.了解相容關(guān)系的概念3.掌握偏序關(guān)系，哈斯圖的畫法，會求偏序集上的特殊元素二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：等價(jià)關(guān)系、等價(jià)類、偏序集、哈斯圖2.難點(diǎn)：偏序關(guān)系三、教學(xué)內(nèi)容與教學(xué)過程1.習(xí)題講解（5分鐘）2.上講內(nèi)容回顧（5分鐘）關(guān)系的性質(zhì)：自反性；反自反性；對稱性；反對稱性；傳遞性關(guān)系的閉包：自反閉包；對稱閉包；傳遞閉包3.進(jìn)入主題，開始第八講。(1)等價(jià)關(guān)系（25分鐘）①等價(jià)關(guān)系：設(shè)RíA′A,若R具有自反性、對稱性以及傳遞性,則稱R為A上的等價(jià)關(guān)系.例2-47：設(shè)A={a,b,c},R={(a,a),(b,b),(c,c),(b,c),(c,b)},則R具有自反性、對稱性以及傳遞性,因此R為A上的等價(jià)關(guān)系.例：Z上的模3同余關(guān)系是Z上的等價(jià)關(guān)系。定理2-21：設(shè)R和S為A上的等價(jià)關(guān)系,則R-1及R?S為A上的等價(jià)關(guān)系.②等價(jià)類：定義：例：Z上的模3同余關(guān)系R：定理2-22：設(shè)R為A上的等價(jià)關(guān)系,對于任意x,y?A,則證明：定理2-23：設(shè)R為A上的等價(jià)關(guān)系,對于任意x,y?A?.證明：③商集：例2-47:A/R={{a},{b,c}}定理2-24：設(shè)R是集合A上的等價(jià)關(guān)系，則A關(guān)于R的商集A/R是集合A的劃分.例2-51：設(shè)A={a,b,c},p={{a},{b,c}},則R={(a,a),(b,b),(c,c),(b,c),(c,b)},它是A上的一個(gè)等價(jià)關(guān)系..注：(x,y)?R?x和y在劃分p的同一個(gè)塊中定理2-25：對于任意集合A,集合A上的所有劃分組成的集合X與其上的所有等價(jià)關(guān)系組成的集合Y是對等的.(2)相容關(guān)系（10分鐘）相容關(guān)系：設(shè)RíA′A,若R具有自反性、對稱性，則稱R為A上的相容關(guān)系.等價(jià)關(guān)系T相容關(guān)系,但相容關(guān)系不一定是等價(jià)關(guān)系(3)偏序關(guān)系①偏序關(guān)系定義（10分鐘）設(shè)RíA′A,若R具有自反性、反對稱性和傳遞性,則稱R為A上的偏序.借用數(shù)的￡表示偏序,可讀作“小于等于”,(A,￡)稱為偏序集.例：R,￡?P(X),í?N+,|?線性序：設(shè)￡是A上的偏序,若對任意x,y?A,有x￡y或y￡x,則稱￡是線性序關(guān)系,簡稱線性序或全序。實(shí)數(shù)集R上的數(shù)的小于等于關(guān)系￡是線性序.整除關(guān)系不是正整數(shù)集合上的全序關(guān)系.②偏序集的哈斯圖（20分鐘）覆蓋：x,y∈A,如果x?y且不存在z∈A使得x?z?y,則稱y覆蓋x.COV(A)={(x,y)|x,y?A且y覆蓋x}.例：{1,2,4,6}集合上的整除關(guān)系：R={(1,2)(1,4),(1,6),(2,4),(2,6)}則2覆蓋1,4和6覆蓋2,4不覆蓋1.例2-62:設(shè)A={a,b},則P(A)={?,{a},,{a,b}},則P(X)上的包含關(guān)系“í”是其上的偏序關(guān)系,求COV(A).解：根據(jù)定義知,{a}蓋住?,蓋住?,{a,b}蓋住{a},{a,b}蓋住.因此COV(A)={(?,{a}),(?,),({a},{a,b}),(,{a,b})}.哈斯圖：利用偏序關(guān)系的自反、反對稱、傳遞性進(jìn)行簡化的關(guān)系圖哈斯圖特點(diǎn)：a.每個(gè)結(jié)點(diǎn)沒有環(huán) b.兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低表示，位置低的元素的順序在前c.具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊哈斯圖的畫法：a.用黑點(diǎn)代表A中元素;b.y蓋住x,y畫在x的上方且用一條線段連接x和y.例：偏序集<{1,2,3,4,5,6,7,8,9},R整除>和<P({a,b,c}),Rí>的哈斯圖.③偏序集中的特殊元素：（10分鐘）a.最小元、最大元、極小元、極大元若"x(x∈B→y?x)成立,則稱y為B的最小元若"x(x∈B→x?y)成立,則稱y為B的最大元若"x(x∈B∧x?y→x=y)成立,則稱y為B的極小元若"x(x∈B∧y?x→x=y)成立,則稱y為B的極大元b.上界、下界、上確界、下確界若"x(x∈B→x?y)成立,則稱y為B的上界若"x(x∈B→y?x)成立,則稱y為B的下界令C＝{y|y為B的上界},C的最小元為B的最小上界或上確界令D＝{y|y為B的下界},D的最大元為B的最大下界或下確界例：設(shè)偏序集(A,?)，求A的極小元、最小元、極大元、最大元，設(shè)B＝{b,c,d},求B的下界、上界、下確界、上確界.解：極小元：a,b,c,g；極大元：a,f,h；沒有最小元與最大元.B的下界和最大下界都不存在；上界有d和f,最小上界為d.4.教學(xué)小結(jié)（3分鐘）本講介紹了幾種常見關(guān)系：等價(jià)關(guān)系，相容關(guān)系，偏序關(guān)系。與等價(jià)關(guān)系相關(guān)的介紹了等價(jià)關(guān)系，等價(jià)類，商集等；與相容關(guān)系相關(guān)的介紹了相容關(guān)系，相容類；與偏序關(guān)系相關(guān)的介紹了偏序關(guān)系，哈斯圖，偏序集，以及特殊元素。四、作業(yè)與實(shí)驗(yàn)（2分鐘）1.書面作業(yè)：習(xí)題2.5：1、2、3習(xí)題2.7：2、82.上機(jī)作業(yè)：無第九講：命題邏輯（一）一、教學(xué)目標(biāo)掌握命題的概念（真假命題）掌握命題邏輯的表示方式（對象語言與元語言）掌握連接詞符號的表示以及真假的判定二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：對命題概念的理解以及對象語言、元語言的區(qū)別，幾種連接詞的表示以及判定真假的方法2.難點(diǎn)：對命題概念的理解以及對蘊(yùn)含詞符號的理解三、教學(xué)內(nèi)容與教學(xué)過程1.上章內(nèi)容回顧（5分鐘）2.1關(guān)系的概念2.2關(guān)系的運(yùn)算2.3關(guān)系的性質(zhì)2.4關(guān)系的閉包2.5等價(jià)關(guān)系2.7偏序關(guān)系2.進(jìn)入主題，開始第九講(1)命題的有關(guān)概念（25分鐘）計(jì)算機(jī)的計(jì)算過程就是推理過程,而每一步推理離不開判斷,判斷的對象就是命題.①命題定義：能判斷出真假的語句注：a,命題必須是一個(gè)完整的句子,包括用數(shù)學(xué)式子如代表的語句.這一點(diǎn)在后面的命題符號化時(shí)要注意;b,所給語句具有真假意義,即有是否符合客觀實(shí)際或是否合理之分.一般來說,只有陳述句才具有真假意義,祈使句、疑問句和感嘆句不具有真假意義;c,能判斷出真假,不過,要是將來某時(shí)候能判斷出真假也行例：你媽喊你回家吃飯.《建國大業(yè)》里面有很多大腕兒.x>3.(不是命題)立正！(不是命題)這朵花真漂亮！(不是命題)你喜歡網(wǎng)絡(luò)游戲嗎?(不是命題)火星上有生物.我說的都是假話.(不是命題)小王和小李是同學(xué).你只有刻苦學(xué)習(xí),才能取得好成績我不去游泳僅當(dāng)你走，我留下值班②命題的真值命題的真值就是命題的邏輯取值經(jīng)典邏輯值只有兩個(gè):1和0,它們是表示事物狀態(tài)的兩個(gè)量。實(shí)際上在數(shù)理邏輯中,更多時(shí)候邏輯真是用T(True)或t,邏輯假用F(False)或f表示的③命題的表示a.對象語言的描述b.命題獨(dú)享語言的描述：原子命題是不包含有更小的命題的命題，通常用小寫英文字母p,q,r,s,…或帶下標(biāo)p1,p2,p3,…等來表示原子命題,如用p:2+3=5,q:今天我們上課.復(fù)合命題是由原子命題和聯(lián)接詞構(gòu)成的命題，聯(lián)接詞類似于自然語言中的連詞。注：“小王和小李是同學(xué)”是原子命題。例：“僅當(dāng)你走，我留下值班”：p:你走，q:我留下值班“我不去游泳”：p：我去游泳命題常量、命題變量把1和0稱為邏輯常量；在邏輯表達(dá)式中出現(xiàn)的p,q,r或p1,p2,p3等稱為命題變元或邏輯變量.(2)連接詞符號（55分鐘）①否定聯(lián)接詞?：?p （5分鐘）p:2+3=5,?p:2+315.p?p1001真值表：

例：p:下周開運(yùn)動(dòng)會，?p：下周不開運(yùn)動(dòng)會注：?p是數(shù)理邏輯中的標(biāo)準(zhǔn)符號,也可記為~p,C語言!p,在計(jì)算機(jī)其他課程中用,對應(yīng)于邏輯門電路中的“非門”.②合取聯(lián)接詞ù:pùq（10分鐘）p:小李能歌,q:小李善舞.pùq:小李能歌且善舞.合取“ù”相當(dāng)于“并且”,“和”,“與”,“以及”等.pqpùq111100010000真值表：注意：“小王和小李是同學(xué)”中的“和”沒有合取之意.在數(shù)理邏輯中,合取聯(lián)結(jié)詞可以將任意兩個(gè)命題聯(lián)結(jié)起來以構(gòu)造出新的命題,如用p:2+3=5,q:今天上課,則pùq:2+3=5且今天上課.注：pùq:p&q,p&&q,p×q=pq,對應(yīng)于“與門”.③析取聯(lián)接詞ú:púq（5分鐘）p:這學(xué)期我選修人工智能課程,q:這學(xué)期我選修模式識別課程.púq:這學(xué)期我選修人工智能課程或者模式識別課程.析取“ú”相當(dāng)于“或者”.p|q,p||q,p+q(“或門”).pqpúq111101011000真值表：

④異或聯(lián)接詞?:p?q（10分鐘）自然語言中的“或”:“可兼或”(inclusiveor),它表示兩者可同時(shí)為真,用析取表示即可；“不可兼或”,它表示兩者不能同時(shí)為真,換句話說,兩者同時(shí)為真是假命題.這就需要異或聯(lián)結(jié)詞.p:明天去深圳的飛機(jī)是上午八點(diǎn)起飛,q:明天去深圳的飛機(jī)是上午八點(diǎn)半起飛.p?q:明天去深圳的飛機(jī)是上午八點(diǎn)或上午八點(diǎn)半起飛.pqp?q110101011000真值表：

注：與異或聯(lián)結(jié)詞對應(yīng)的門電路為“異或門”.對于自然語言中的“或”用還是需要仔細(xì)分析,一般來說,只要不是非常明顯的不兼就使用ú.⑤條件聯(lián)接詞?:p?q（10分鐘）p:我有時(shí)間,q:我去看望我的父母.p?q:如果我有時(shí)間,那么我去看望我的父母.“?”相當(dāng)于“如果…那么…”,“若…則…”,等.p?q可讀作“(若)p則q”.pqp?q111100011001真值表：

在p?q中,p稱為前件,q稱為后件.當(dāng)p=1,q=1時(shí)p?q=1;當(dāng)p=1,q=0時(shí)p?q=0,這是比較好理解的兩種情形.由于我們現(xiàn)在討論的是實(shí)質(zhì)蘊(yùn)涵,規(guī)定當(dāng)p=0,q=1時(shí)p?q=1;當(dāng)p=0,q=0時(shí)p?q=1.規(guī)定的合理性見下面的例子.a.如果太陽從西邊出來,那么2+3=5.b.如果太陽從西邊出來,那么2+3=4.⑥雙條件聯(lián)接詞?:p?q（10分鐘）p:四邊形是平行四邊形,q:四邊形的對邊平行.p?q:四邊形是平行四邊形當(dāng)且僅當(dāng)四邊形的對邊平行.p?q:可讀作“p當(dāng)且僅當(dāng)q”.雙條件聯(lián)結(jié)詞“?”相當(dāng)于自然語言中的“當(dāng)且僅當(dāng)”“p當(dāng)且僅當(dāng)q”有兩層含義：(1)“p當(dāng)q”是指q?p.(2)“p僅當(dāng)q”是指p?q.正因?yàn)榇?等價(jià)聯(lián)結(jié)詞又可以稱為雙蘊(yùn)涵聯(lián)結(jié)詞或雙條件聯(lián)結(jié)詞.pqp?q111100010001真值表：注：在數(shù)字邏輯等課程中,等價(jià)聯(lián)結(jié)詞稱為“同”,并用“⊙”符號表示⑦與非聯(lián)接詞-:p-q（2分鐘）pqp-q110101011001

真值表：⑧或非聯(lián)接詞ˉ:pˉq（2分鐘）pqpˉq110100010001真值表：⑨條件否定聯(lián)接詞：（1分鐘）真值表：pq

1101010100004.教學(xué)小結(jié)（3分鐘）本講首先介紹了命題的概念及其表示方式，然后依次介紹了九種聯(lián)接詞，其中重點(diǎn)需要掌握否定聯(lián)接詞、合取聯(lián)接詞、析取聯(lián)接詞、異或聯(lián)接詞、條件聯(lián)接詞、雙條件聯(lián)接詞等，重點(diǎn)注意條件聯(lián)接詞的表達(dá)方式。四、作業(yè)與實(shí)驗(yàn)（2分鐘）書面作業(yè)：習(xí)題3.21、2、3、4、5、6.2.上機(jī)作業(yè)：無第十講：命題邏輯（二）一、教學(xué)目標(biāo)1.理解命題公式的概念2.掌握命題公式的組成符號、組成原則3.掌握變元真值指派的含義及命題公式的真值表4.理解命題公式的類型，掌握命題公式類型判斷的方法二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：命題公式的概念，命題公式的真值表，命題公式類型的判斷2.難點(diǎn)：命題公式類型的判斷三、教學(xué)內(nèi)容與教學(xué)過程1.習(xí)題講解（10分鐘）2.上講內(nèi)容回顧（5分鐘）命題的概念（真假命題）命題邏輯的表示方式（對象語言與元語言）連接詞符號的表示以及真假的判定3.進(jìn)入主題，開始第十講本講知識點(diǎn)概括(1)命題公式（15分鐘）①命題公式的概念命題公式是由命題常量、命題變元、邏輯聯(lián)結(jié)詞、左圓括號(及由圓括號)構(gòu)成的有意義(well-formed)的符號串,其嚴(yán)格定義需借助于遞歸定義方式給出.a.1,0,p,q,r,…b.AT(?A)c.A,BTd.有限次應(yīng)用(1)(2)(3)所得到的符號串是僅有的命題公式.例:命題公式可稱為合式公式或簡稱為公式,其全稱為命題合式公式.這兒的公式實(shí)際上是書寫正確、含義清楚的表達(dá)式或者說符號串可以省略括號的約定:a.最外層的括號可以省略.在形成最終的命題公式時(shí),所有的中間過程得到的命題公式,包含其本身,都稱為該命題公式的子公式.b.9個(gè)聯(lián)結(jié)詞運(yùn)算的優(yōu)先順序依次為:符合本約定的有些括號可以不寫.如命題公式注：這種規(guī)定不是唯一的.c.同級運(yùn)算從左至右依次進(jìn)行.如實(shí)際上,在對命題進(jìn)行符號化時(shí),只要書寫正確的邏輯函數(shù)都是命題公式.(2)命題的符號化（15分鐘）命題的符號化就是使用符號—命題變元、邏輯聯(lián)結(jié)詞和括號將所給出的命題表示出來.一方面說明,符號體系來源于實(shí)際問題,另一方面也是給出進(jìn)一步學(xué)習(xí)邏輯演算系統(tǒng)的語義解釋時(shí)的一種標(biāo)準(zhǔn)模型.命題的符號化的步驟:Step1找出所給命題的所有原子命題,并用小寫英文字母或帶下標(biāo)表示；Step2確定應(yīng)使用的聯(lián)結(jié)詞,進(jìn)而將原命題用符號表示出來.例3-7(P86)將下列命題符號化.a.天氣很好或很熱.b.如果張三和李四都不去,那么我就去.c.僅當(dāng)你走,我留下.e.我今天進(jìn)城,除非天下雨.d.你只有刻苦學(xué)習(xí),才能取得好成績.解：a.或?b.“張三不去”是復(fù)合命題.c.p:你走,q:我留下,僅當(dāng)?d.p:我今天進(jìn)城,q:天下雨.除非=如果不.e.p:你刻苦學(xué)習(xí),q:你取得好成績.只有p,才q?(3)命題公式的真值表（20分鐘）對于命題公式,若對中出現(xiàn)的每個(gè)命題變元都指定一個(gè)真值1或者0,就對命題公式A進(jìn)行了一種真值指派或一個(gè)解釋,而在該指派下會求出公式A的一個(gè)真值.將A的所有可能的真值指派以及在每一個(gè)真值指派下的取值列成一個(gè)表,就得到命題公式A的真值表.例3-8寫出命題公式A=的真值表.pqr?p?púq(?púq)?r111011110010101001100001011111010110001111000110例：B＝(q?p)ùq?ppqq?p(q?p)ùq(q?p)ùq?p00011011101100011111例：C＝?(?púq)ùqpq?p?púq?(?púq)?(?púq)ùq000110111100110100100000注：由表知,含3個(gè)命題變元的命題公式有8=23種不同的真值指派.很顯然,含2個(gè)命題變元的命題公式有4=22種不同的真值指派.一般來說,含n個(gè)命題變元的命題公式的不同的真值指派有2n種.（4）命題公式的類型（20分鐘）a.在任何指派下均取真的命題公式稱為永真式或重言式；b.在任何指派下均取假的命題公式稱為永假式或矛盾式；c.至少有一種指派使其為真的命題公式稱為可滿足式；d.至少有一種指派使其為真同時(shí)至少有一種指派使其為假的命題公式稱為中性式.判斷公式種類的方法：①真值表法(求出公式的所有指派,判斷公式的類型)例3-9pqp?q?púq111101011001②取值法：例：由A=1可推出B=1,則A?B永真.由B=0可推出A=0,則A?B永真.例：用真值表判斷下面公式的類型(1)pùr?ù(q?p)(2)((p?q)?(?q??p))úr(3)(p?q)?(p?r)pqrq?p?(q?p)pùr?ù(q?p)000001010011100101110111110011110011000000000000定理3-1(永真式的代入定理)如何使用？4.教學(xué)小結(jié)（3分鐘）本講首先介紹了命題公式的概念以及命題的符號化，接著介紹了命題公式的真值表及命題公式的類型，最后重點(diǎn)介紹了如何利用真值表法和取值法判斷命題公式的類型。四、作業(yè)與實(shí)驗(yàn)（2分鐘）1.書面作業(yè)：習(xí)題3.31(雙),2(雙),3(雙),4,5,6(雙).2.上機(jī)作業(yè)：無第十一講：命題邏輯（三）一、教學(xué)目標(biāo) 1.理解命題公式的邏輯等值的概念2.理解并掌握基本等值式及其他重要等值式3.掌握等值演算法及其應(yīng)用二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：基本等值式，等值演算法2.難點(diǎn)：應(yīng)用等值演算法三、教學(xué)內(nèi)容與教學(xué)過程1.習(xí)題講解（5分鐘）2.上講內(nèi)容回顧（5分鐘）命題公式的定義命題的符號化命題公式的真值表命題公式的類型3.進(jìn)入主題，開始第十一講本講知識點(diǎn)概括(1)邏輯等值定義：給定兩個(gè)命題公式A和B,若在任何真值指派下A和B的真值都相同,則稱命題公式A和B邏輯等價(jià)或邏輯等值或簡稱為等值或相等,記為A=B.注：A?B與A=B(A?B)是不同的.A=B(A?B)中的=是關(guān)系符號，A=B是等值式，?是運(yùn)算符號，A?B是命題公式，運(yùn)算結(jié)果可真可假。定理3-2：A=B的充要條件是A?B永真.證明：例3-11證明pqP→q?p?púq11101100000111100111

②模運(yùn)算定理3-3：例如：定理3-4：邏輯等值是命題公式間的等價(jià)關(guān)系:(1)A=A（自反性）(2)若A=B，則B=A（對稱性）(3)若A=B且B=C，則A=C（傳遞性）.(2)基本等值式①與?,ù,ú有關(guān)的等值式定理3-5：（對合律）（冪等律）（交換律）（結(jié)合律）（吸收律）注：與集合的有關(guān)性質(zhì)類似.每條性質(zhì)均可證明. 例3-12：證明對于任意命題公式A和B，有證明：只需證pq1111100101000000②其他重要等值式設(shè)A,B是任意的命題公式，則注：基本等值式有很多用途,如化簡命題公式、判斷命題公式的類型、證明等值式、計(jì)算命題公式的范式、命題邏輯中的推理等,要求大家要熟記,特別是定理3-5中的等值式.(3)等值演算法定理3-7（等值置換定理）：設(shè)C是命題公式A的子公式,若C=D,則將A中的C部分或全部替換為D所得到的命題公式與A等值.利用基本等值式以及等值置換定理求解問題的方法稱為“等值演算法”.①化簡命題公式例3-13(P92)化簡下列命題公式并將最后結(jié)果用只含?和ú表示.a.b.解：a.b.注：命題公式的化簡是指將其化為一個(gè)與其等值的滿足條件的含“聯(lián)接詞最少”的命題公式。②判斷命題公式的類型例3-14：設(shè)A,B,C是任意的命題公式,判斷下列命題公式的類型:解：故是中性式③證明命題公式等值例3-15：設(shè)A,B,C是任意的命題公式,證明下列等值式.a.b.證明：a.b.(4)對偶原理定義：設(shè)命題公式A中只含有3個(gè)邏輯聯(lián)結(jié)詞?,ù,ú,將A中的ù換成ú；A中的ú換成ù；A中的1換成0；A中的0換成1,所得到的命題公式稱為是A的對偶式,記為A*.例：對偶原理：設(shè)A和B是命題公式,若A=B,則A*=B*.4.教學(xué)小結(jié)（3分鐘）本講首先介紹了命題公式等值的概念，然后介紹了基本等值式及其他重要等值式，在此基礎(chǔ)上又介紹了等值演算法，并舉例說明如何用等值演算法化簡命題公式、判斷命題公式類型、證明命題公式等值。最后介紹了命題公式的對偶原理。四、作業(yè)與實(shí)驗(yàn)（2分鐘）1.書面作業(yè)：習(xí)題3.45(雙),6,9(雙),10,112.上機(jī)作業(yè)：無第十二講：命題邏輯（四）一、教學(xué)目標(biāo)1.理解命題公式的析取范式、合取范式、主析取范式、主合取范式、2.掌握命題公式的范式及主范式的求法3.掌握命題公式的范式的應(yīng)用：求出真假指派4.掌握命題公式的主范式的應(yīng)用：判斷命題公式的類型、判斷命題公式等值、由真值表求命題公式二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：命題公式的范式的求法，范式的應(yīng)用2.難點(diǎn)：同上三、教學(xué)內(nèi)容與教學(xué)過程1.上講內(nèi)容回顧（5分鐘）邏輯等值的定義基本等值式等值演算法對偶原理2.進(jìn)入主題，開始第十二講本講知識點(diǎn)概括命題公式的析取范式（20分鐘）①定義：設(shè)A是命題公式,若A=A1úA2ú…úAn(n31),其中Ai(1￡i￡n)是由命題變元或其否定組成的合取式,則稱A1úA2ú…úAn注：Ai=?pù?qùr,pù?q,?qùr,q,?r?n=1?如A=?pù?qùr=(?pù?qùr).②求法Step1使用等值式,將命題公式中的聯(lián)結(jié)詞歸約為?,ù,ú；Step2利用DeMorgan律將?移到命題變元的前面；Step3根據(jù)分配律得到命題公式的析取范式及合取范式：Aù(BúC)=(AùB)ú(AùC).例3-17：設(shè)p,q和r是命題變元,求命題公式A=(p?q)?r的析取范式.解： 命題公式的合取范式（10分鐘）①定義：設(shè)A是命題公式,若A=A1ùA2ù…ùAn(n31),其中Ai(1￡i￡n)是由命題變元或其否定組成的析取式,則稱A1ùA2ù…ùAn注：Ai=?pú?qúr,pú?q,?qúr,q,?r?n=1?如A=?pú?qúr=(?pú?qúr).若A=?pú?qúr,則?pú?qúr也是A的析取范式.②求法Step1使用等值式,將命題公式中的聯(lián)結(jié)詞歸約為?,ù,ú；Step2利用DeMorgan律將?移到命題變元的前面；Step3根據(jù)分配律得到命題公式的析取范式及合取范式：Aú(BùC)=(AúB)ù(AúC)例3-17：設(shè)p,q和r是命題變元,求命題公式A=(p?q)?r的析取范式.解： 析取范式及合取范式的應(yīng)用（20分鐘）根據(jù)命題公式的析取范式及合取范式可分別得出該命題公式取真、假的指派.例：例3-18：從p,q,r,s四人中選派2人出差,求滿足下列3個(gè)條件的選派方法有哪幾種.a.若p去,則r和s中只去1人；b.q和r不能都去；c.若r去,則s不能去.解:p:p去出差,q:q去出差,r:r去出差,s:s去出差,則則：(a)p,s去;(b)q,s去;(c)p,r去.(4)命題公式的主析取范式（10分鐘）①最小項(xiàng)：對于給定的命題變元,若由命題變元或其否定組成的合取式滿足(1)每個(gè)命題變元或其否定二者之一只出現(xiàn)一次；(2)按字典順序或按下標(biāo)從小到大順序出現(xiàn)。注：對于每一個(gè)最小項(xiàng)只有一種指派使