離散數(shù)學(xué)的教學(xué)案

...wd......wd......wd...滁州學(xué)院計(jì)算機(jī)與信息工程學(xué)院課程教案課程名稱：離散數(shù)學(xué)授課教師：趙歡歡授課對(duì)象：11級(jí)網(wǎng)絡(luò)工程專業(yè)3、4班授課時(shí)間：2012年9月-2012年12月滁州學(xué)院計(jì)算機(jī)科學(xué)與信息工程學(xué)院2012年8月《離散數(shù)學(xué)》教學(xué)大綱〔DiscreteMathematic〕課程代碼：學(xué)時(shí)：48學(xué)分：3一、課程簡(jiǎn)介本大綱根據(jù)2009版應(yīng)用型人才培養(yǎng)方案制訂。〔一〕教學(xué)對(duì)象：網(wǎng)絡(luò)工程、計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科學(xué)生〔二〕開(kāi)課學(xué)期：第三學(xué)期〔三〕課程類別：專業(yè)根基課〔四〕考核方式：考試〔五〕參考教材：《離散數(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ù)構(gòu)造、數(shù)據(jù)庫(kù)原理及應(yīng)用、操作系統(tǒng)、數(shù)字邏輯、人工智能、算法分析與設(shè)計(jì)等。二、教學(xué)基本要求與內(nèi)容安排〔一〕教學(xué)目的與要求離散數(shù)學(xué)是研究離散量的構(gòu)造及其相互關(guān)系的學(xué)科,它在各學(xué)科領(lǐng)域特別在計(jì)算機(jī)科學(xué)領(lǐng)域有著廣泛的應(yīng)用，同時(shí)離散數(shù)學(xué)也是計(jì)算機(jī)專業(yè)的許多專業(yè)課程必不可少的先行課程。本課程的教學(xué)目的旨在通過(guò)對(duì)離散數(shù)學(xué)的教學(xué)，讓學(xué)生不但可以掌握處理如集合、代數(shù)構(gòu)造和圖等離散構(gòu)造的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且為學(xué)生今后提高專業(yè)理論水平，從事計(jì)算機(jī)行業(yè)的實(shí)際工作提供必備的抽象思維和嚴(yán)格的邏輯推理能力，為將來(lái)參與創(chuàng)新性的研究和開(kāi)發(fā)工作打下堅(jiān)實(shí)的根基。〔二〕教學(xué)內(nèi)容安排教學(xué)內(nèi)容教學(xué)要求教學(xué)方法重點(diǎn)(☆)難點(diǎn)(Δ)學(xué)時(shí)分配備注講課實(shí)驗(yàn)上機(jī)其他第一局部數(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推理的形式構(gòu)造A☆13.2自然推理系統(tǒng)PBΔ14一階邏輯基本概念24.1一階邏輯命題符號(hào)化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ù)構(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最短路問(wèn)題與貨郎擔(dān)問(wèn)題CΔ13樹(shù)1.53.1無(wú)向樹(shù)及其性質(zhì)A☆0.53.2生成樹(shù)A☆0.53.3根樹(shù)及其應(yīng)用B0.54平面圖34.1平面圖的基本概念B0.54.2歐拉公式B☆0.54.3平面圖的判斷B14.4平面圖的對(duì)偶圖C15圖論在計(jì)算機(jī)中的應(yīng)用3〔教學(xué)要求：A—熟練掌握；B—掌握；C—了解〕三、實(shí)驗(yàn)內(nèi)容本課程無(wú)實(shí)驗(yàn)制訂人〔簽字〕：審核人〔簽字〕：教學(xué)進(jìn)度2012～2013學(xué)年第1學(xué)期周數(shù)周數(shù)16周方案學(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ò)工程班級(jí)2011級(jí)課程名稱離散數(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集合的對(duì)等理論：集合的并、交、差、補(bǔ)、對(duì)稱差等基本運(yùn)算，集合的劃分與覆蓋、集合對(duì)等、可數(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ó)慶放假第七講關(guān)系〔三〕2.3關(guān)系的性質(zhì)2.4關(guān)系的閉包理論：關(guān)系的性質(zhì)：自反性、反自反性、對(duì)稱性、反對(duì)稱性、傳遞性；自反閉包r(R)、對(duì)稱閉包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命題公式及其真值表理論：命題公式的定義、命題的符號(hào)化、命題公式的真值表、命題公式的類型第八周10月22日22第十一講命題邏輯〔三〕3.4邏輯等值的命題公式理論：邏輯等值的定義、基本等值式、等值演算法、對(duì)偶原理第九周10月29日44第十二講命題邏輯〔四〕3.5命題公式的范式理論：命題公式的析取范式和合取范式的定義域求法命題公式的主析取范式及主合取范式的定義和求法第十三講命題邏輯〔五〕3.7命題邏輯中的推理理論：推理形式有效性的定義；基本推理規(guī)則；命題邏輯的自然推理系統(tǒng)第十周11月522第十四講謂詞邏輯〔一〕4.1個(gè)體、謂詞、量詞和函詞理論：謂詞邏輯概念，謂詞的概念與表示，量詞的概念與表示，個(gè)體域，轄域，約束變?cè)妥杂勺冊(cè)暮x第十一周11月144第十五講謂詞邏輯〔二〕4.2謂詞公式及命題的符號(hào)化4.3謂詞公式的解釋及類型理論：謂詞公式的定義，將命題用用符號(hào)〔個(gè)體，量詞，謂詞〕來(lái)表示，消去量詞的邏輯等值式，永真式，科滿足式，永假式及中性式的概念第十六講謂詞邏輯〔三〕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ǎn)單圖，節(jié)點(diǎn)的度數(shù)，子圖第十三周11月2644第十八講圖論〔二〕6.4路與回路6.5圖的連通性理論內(nèi)容：路，回路，無(wú)向圖的連通性，無(wú)向連通圖的點(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)概念，歐拉定理，中國(guó)郵遞員問(wèn)題、Hamilton圖第十五周12月844第二十一講圖論〔五〕7.2無(wú)向樹(shù)7.3有向樹(shù)理論內(nèi)容：樹(shù)的基本概念，最小生成樹(shù)，二叉樹(shù)的遍歷與表達(dá)式的計(jì)算第二十二講代數(shù)構(gòu)造〔一〕5.1代數(shù)構(gòu)造簡(jiǎn)介理論內(nèi)容：代數(shù)構(gòu)造的定義，半群及獨(dú)異點(diǎn)，子代數(shù)，代數(shù)構(gòu)造的同態(tài)與同構(gòu)第十六周12月1722第二十三講代數(shù)構(gòu)造〔二〕5.2群的定義及性質(zhì)理論內(nèi)容：群的有關(guān)概念，子群，群的同態(tài)第十七周12月2422第二十四講總復(fù)習(xí)系主任簽名：院長(zhǎng)簽名：年月日年月日說(shuō)明：1．本教學(xué)進(jìn)度表由主講教師負(fù)責(zé)填寫，于每學(xué)期開(kāi)學(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é)過(guò)程1.進(jìn)展自我介紹〔5分鐘〕姓名，聯(lián)系方式，專業(yè)方向。建議學(xué)生用電子郵件方式聯(lián)系。2.進(jìn)展課程簡(jiǎn)介〔10分鐘〕離散數(shù)學(xué)是研究離散量的構(gòu)造及相互之間關(guān)系的學(xué)科是一門專業(yè)根基課，是數(shù)據(jù)構(gòu)造、操作系統(tǒng)、計(jì)算機(jī)組成原理、數(shù)據(jù)庫(kù)原理等課程的數(shù)學(xué)根基。特點(diǎn)：知識(shí)點(diǎn)集中，概念，定理多；方法性強(qiáng)；學(xué)數(shù)學(xué)就要做數(shù)學(xué)成績(jī)?cè)u(píng)定：平時(shí)成績(jī)(到課情況，書面作業(yè)，平時(shí)測(cè)驗(yàn))占30%,期末考試占70%3.進(jìn)入主題，開(kāi)場(chǎng)第一講(1)集合的有關(guān)概念(20分鐘)①集合定義：集合是具有某種特定性質(zhì)的對(duì)象聚集成的一個(gè)整體，通常用大寫字母A,B,C,D表示。例如：滁州學(xué)院全體學(xué)生計(jì)算機(jī)與信息工程學(xué)院所有女生常見(jiàn)的數(shù)的集合：N,N+,Z,Q,R,C②元素集合中的每一個(gè)對(duì)象稱為該集合的元素，通常用小寫字母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(chóng)∈A或|A|表示集合A中的元素個(gè)數(shù)注意：集合中的元素可以是集合，如A={a,{a,b},b,c},|A|=4,{a,b}∈A注：集合中的元素?zé)o順序；集合中無(wú)重復(fù)元素例：指出以下哪些是集合，哪些不是集合中國(guó)人的集合；百貨商店里好看的花布的集合；1000以內(nèi)的素?cái)?shù)的集合；26個(gè)英文字母組成的集合；這個(gè)班里高個(gè)子學(xué)生的集合；直線y＝2x-5上的點(diǎn)的集合。(2)集合之間的關(guān)系①子集〔15分鐘〕定義：假設(shè)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注：假設(shè)|X|=n,P(x)的元素有：；由一個(gè)元素構(gòu)成的子集；由兩個(gè)元素構(gòu)成的子集；…由n個(gè)元素構(gòu)成的子集計(jì)數(shù)的基本原理：加法原理：圖示乘法原理：圖示定理1-4：假設(shè)|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ù)構(gòu)造中是一個(gè)表有序?qū)?，序偶?元組注：(x,y)≠(y,x)④笛卡爾積〔10分鐘〕定義：設(shè)是集合，稱為A1,A2,…An的笛卡爾積〔直積，叉積〕，記為：例：A={a,b},B={1,2}，例1-4注：一般來(lái)說(shuō)，定理1-5：假設(shè)|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è)：無(wú)第二講：集合、映射和運(yùn)算〔二〕一、教學(xué)目標(biāo)1.掌握映射的概念與表示2.理解映射的三種性質(zhì)：?jiǎn)紊?、滿射、雙射，會(huì)判斷某個(gè)具體映射是否具有這些性質(zhì)3.掌握逆映射的含義，復(fù)合映射的定義及性質(zhì)二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：理解和判斷映射的三種性質(zhì)，逆映射，復(fù)合映射2.難點(diǎn)：映射三種性質(zhì)的判斷，復(fù)合映射的性質(zhì)三、教學(xué)內(nèi)容與教學(xué)過(guò)程1.習(xí)題講解〔10分鐘〕2.上講內(nèi)容回憶〔3分鐘〕集合的概念：集合、元素、集合的表示方法集合間的關(guān)系：子集、冪集、n元組、笛卡爾積(1)映射的定義〔15分鐘〕定義：對(duì)于A,B,假設(shè)存在對(duì)應(yīng)法則f，對(duì)于，唯一的與它對(duì)應(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ì)①單射(一對(duì)一映射)〔10分鐘〕定義：，可推出x1=x2或，假設(shè)x1≠x2，可得出例1-6：設(shè)則f是N到N的單射，試證明之。證：對(duì)于，由得出，進(jìn)而x1=x2(使用定義證明)②滿射〔10分鐘〕定義：對(duì)于，使得y=f(x)充要條件：=B例1-7：設(shè)，則f是Z到N的滿射，試證明之。證：對(duì)于取,顯然有〔使用定義證明〕③雙射〔一一對(duì)應(yīng)〕〔5分鐘〕定義:既單射又滿射例1-8例1-9：建設(shè)一個(gè)〔0,1〕到R的一一對(duì)應(yīng)解：置換：A到A的雙射(3)逆映射〔逆函數(shù)，反函數(shù)〕〔10分鐘〕定義：f:A→B，將f的方向逆轉(zhuǎn)后，得到的集合B到集合A的映射定理1-7：f的逆映射存在的充要條件是f是雙射〔加以說(shuō)明解釋〕注：假設(shè)f是雙射，則也是雙射，且例1-11：判斷所給出的映射是否有逆射，假設(shè)有，求出其逆映射①②解：①∵f(2)=f(-2)=4,∴根據(jù)單射定義知f不是單射，進(jìn)而其不是雙射，根據(jù)定理1-7知其不存在逆映射②顯然g是雙射，其逆映射為(4)復(fù)合映射〔20分鐘〕定義:設(shè)對(duì)于，令，則h是A到C的映射，h為f和g的復(fù)合映射或復(fù)合函數(shù)，記為〔圖示〕注：條件:例1-12例1-13注：一般來(lái)說(shuō)即使和都有意義，也不能保證成立恒等映射(IA)：定理1-9：假設(shè)是雙射，則假設(shè)是雙射，則定理1-10：假設(shè)f和g是單射，則是單射〔證明〕假設(shè)f和g是滿射，則是滿射〔證明〕假設(shè)f和g是雙射，則是雙射且定理1-11：設(shè)假設(shè)是單射，則f是單射，但g不一定〔證明〕假設(shè)是滿射，則g是滿射，而f不一定〔證明〕定理1-12設(shè)，則4.教學(xué)小結(jié)〔5分鐘〕本講首先介紹了映射〔函數(shù)〕的定義及定義域、值域、像、原像等相關(guān)概念；接著介紹了映射的三種性質(zhì)：?jiǎn)紊?，滿射，雙射；最后介紹了逆映射的定義及復(fù)合映射的定義及其具有的相關(guān)性質(zhì)。四、作業(yè)與實(shí)驗(yàn)〔2分鐘〕1.書面作業(yè)：習(xí)題1.21、2、6、11、14.2.上機(jī)作業(yè)：無(wú)第三講：集合、映射和運(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é)過(guò)程1.習(xí)題講解〔5分鐘〕2.上講內(nèi)容回憶〔5分鐘〕映射的定義映射的性質(zhì)：?jiǎn)紊?，滿射，雙射逆映射復(fù)合映射3.進(jìn)入主題，開(kāi)場(chǎng)第二講。本講知識(shí)點(diǎn)概括(1)運(yùn)算的定義〔25分鐘〕①定義:設(shè)和B是集合，假設(shè)，稱f為到B的n元運(yùn)算。A到B的n元運(yùn)算，或A上的n元運(yùn)算：A上的n元封閉運(yùn)算〔代數(shù)運(yùn)算〕：，有例：判定取絕對(duì)值運(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ù)假設(shè)d|m且d|n,則d是m,n的公約數(shù)，用gcd(m,n)表示m,n的最大公約數(shù)假設(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ù)分解：〔對(duì)于大于1的正整數(shù)n都可以分解成一些素?cái)?shù)乘積〕Euclid算法例1-19假設(shè)gcd(m,n)=1,稱m和n互素。歐拉函數(shù)：表示小于等于n且與n互素的正整數(shù)的個(gè)數(shù)④運(yùn)算表給定集合A，則集合A上的1元或2元運(yùn)算可以用運(yùn)算表來(lái)表示例：A={a,b,c},**abcabcababccbca思考：A上的封閉的1元，2元，3元運(yùn)算的個(gè)數(shù)是多少3339327(2)運(yùn)算的性質(zhì)①對(duì)合性〔5分鐘〕定義：設(shè)*是A上的一元代數(shù)運(yùn)算，例：②冪等性〔5分鐘〕冪等元：定義：A中的每個(gè)元素對(duì)于*都是冪等元例：*123112322323313例：③交換性〔5分鐘〕定義：對(duì)于A上的二元運(yùn)算*,,均有例：R上的+具有交換性R上的-，映射的復(fù)合運(yùn)算?④結(jié)合性〔5分鐘〕定義：例:映射的復(fù)合運(yùn)算具有結(jié)合性R上的+具有結(jié)合性R上的-⑤單位元素〔幺元素〕〔5分鐘〕定義：對(duì)于A上的二元運(yùn)算*，，使得對(duì)于例：R關(guān)于加法運(yùn)算+的單位元素是0R關(guān)于乘法運(yùn)算的單位元素是1R關(guān)于減法運(yùn)算-的單位元素是定理1-3：假設(shè)A關(guān)于*有單位元素，則單位元素是唯一的證明：設(shè)e1,e2是A關(guān)于*的單位元素，則e1=e1*e2=e2⑥零元素〔5分鐘〕定義：對(duì)于A上的二元運(yùn)算*，，使得對(duì)于例:R關(guān)于乘法運(yùn)算的零元素是0R關(guān)于減法運(yùn)算-的零元素是R關(guān)于加法運(yùn)算的零元素是定理1-4：假設(shè)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)算：注：逆元不一定存在，存在不一定唯一，參見(jiàn)表1-5定理1-5：假設(shè)A關(guān)于*運(yùn)算有單位元素為e且*運(yùn)算滿足結(jié)合律，假設(shè)對(duì)于A中的x有左逆元y與右逆元z，則y=z,此逆元唯一證明：y*x=e,x*z=ey=y*e=y*(x*z)=(y*x)*z=e*z=z⑧消去性〔分鐘〕定義：假設(shè)A關(guān)于*有零元，則記為，對(duì)于，假設(shè)例1-31Z上的加法運(yùn)算+和乘法運(yùn)算均滿足消去律.⑨分配性〔5分鐘〕定義：是A上的兩個(gè)二元運(yùn)算，對(duì)于則稱*關(guān)于是可分配的⑩吸收性〔2分鐘〕定義：是A上的兩個(gè)二元運(yùn)算，對(duì)于則稱*關(guān)于是可吸收的eq\o\ac(○,⒒)德摩根律〔3分鐘〕定義：是A上的一元運(yùn)算，是A上的兩個(gè)二元運(yùn)算，對(duì)于4.教學(xué)小結(jié)〔3分鐘〕本講首先介紹了運(yùn)算的定義并介紹了幾種常用的運(yùn)算，接著介紹了運(yùn)算的性質(zhì)：對(duì)合性、冪等性、交換性、結(jié)合性、單位元素、零元素、逆元素、消去性、分配性、吸收性、德·摩根律，并結(jié)合之前所學(xué)知識(shí)講解運(yùn)算的性質(zhì)。四、作業(yè)與實(shí)驗(yàn)〔2分鐘〕書面作業(yè)：習(xí)題1.3：1、3、5、6、82.上機(jī)作業(yè)：無(wú)第四講：集合、映射和運(yùn)算〔四〕一、教學(xué)目標(biāo)1.掌握集合的各種運(yùn)算2.理解各種集合運(yùn)算所滿足的性質(zhì)3.掌握集合的劃分與覆蓋的概念4.了解集合的對(duì)等，集合的基數(shù)，可數(shù)集合等概念二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：集合的運(yùn)算——并、交、補(bǔ)、差、對(duì)稱差集合運(yùn)算性質(zhì)2.難點(diǎn)：集合運(yùn)算等值式的證明，集合的對(duì)等、基數(shù)三、教學(xué)內(nèi)容與教學(xué)過(guò)程1.上講內(nèi)容回憶〔5分鐘〕運(yùn)算的定義運(yùn)算的性質(zhì)：對(duì)合性、冪等性、交換性、結(jié)合性、單位元素、零元素、逆元素、消去性、分配性、吸收性、德·摩根律2.進(jìn)入主題、開(kāi)場(chǎng)第四講本講知識(shí)點(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:AB,X,YA,則證明：證明：②交運(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：⑤對(duì)稱差運(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|AB|=1000/lcm(5,6)=1000/33=33〔2〕集合的劃分與覆蓋〔12分鐘〕①劃分定義：其中：例1-53：設(shè)A={a,b,c},則A的所有不同的劃分分別為:②覆蓋設(shè)A是集合,由A的假設(shè)干非空子集構(gòu)成的集合稱為A的覆蓋,如果這些非空子集的并等于A.〔3〕集合的對(duì)等〔10分鐘〕定義：A～B存在雙射f:AB.例：(0,1)～R集合的基數(shù)：無(wú)限集合A假設(shè)集合A和B對(duì)等,則稱這兩個(gè)集合的基數(shù)一樣.例：可數(shù)集合：能與自然數(shù)集合N對(duì)等的集合3.教學(xué)小結(jié)〔2分鐘〕本講首先介紹了集合的各種運(yùn)算〔并，交，補(bǔ)，差，對(duì)稱差〕及其滿足的性質(zhì)，接著介紹了集合的劃分與覆蓋的概念；最后介紹了集合對(duì)等、集合的基數(shù)及可數(shù)集合。四、作業(yè)與實(shí)驗(yàn)〔1分鐘〕1.書面作業(yè)：習(xí)題1.45、8、10、13.習(xí)題1.5：1、72.上機(jī)作業(yè)：無(wú)第五講：關(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é)過(guò)程1.習(xí)題講解〔15分鐘〕2.上章內(nèi)容回憶〔5分鐘〕集合的有關(guān)概念映射的有關(guān)概念運(yùn)算的定義與性質(zhì)集合的運(yùn)算、集合的劃分與覆蓋、集合的對(duì)等3.進(jìn)入主題，開(kāi)場(chǎng)第五講本講知識(shí)點(diǎn)介紹(1)關(guān)系的定義①關(guān)系的概念〔15分鐘〕引例：A={張三,李四,王五};B={英語(yǔ),C語(yǔ)言,離散數(shù)學(xué),數(shù)據(jù)構(gòu)造,匯編語(yǔ)言};C={優(yōu),良,合格,不合格}.A與B之間的關(guān)系R={(張三,離散數(shù)學(xué)),(張三,數(shù)據(jù)構(gòu)造),(張三,英語(yǔ)),(李四,數(shù)據(jù)構(gòu)造),(王五,C語(yǔ)言),(王五,匯編語(yǔ)言)}AB.A,B與C之間的關(guān)系S={(張三,離散數(shù)學(xué),優(yōu)),(張三,數(shù)據(jù)構(gòu)造,良),(張三,英語(yǔ),優(yōu)),(李四,數(shù)據(jù)構(gòu)造,優(yōu)),(王五,C語(yǔ)言,合格),(王五,匯編語(yǔ)言,良)}ABC.定義：是集合，，則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：假設(shè)，則A到B的關(guān)系有假設(shè)，則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(chǔ)上的全關(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)系符號(hào)〔10分鐘〕定義：假設(shè)(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è)RAB,ranR={y|yB,存在xA,使得(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)部的元素全部列舉出來(lái)描述法：把關(guān)系內(nèi)部成員的性質(zhì)描述出來(lái)〔同集合〕②關(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:AB,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è)：無(wú)第六講：關(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é)過(guò)程1.習(xí)題講解〔10分鐘〕2.上講內(nèi)容回憶〔5分鐘〕N元關(guān)系的定義2元關(guān)系關(guān)系的定義域與值域關(guān)系的表示函數(shù)的關(guān)系定義3.進(jìn)入主題，開(kāi)場(chǎng)第六講。(1)關(guān)系的集合運(yùn)算〔15分鐘〕關(guān)系的幾種常見(jiàn)集合運(yùn)算:注：解：例2-17(2)關(guān)系的逆運(yùn)算〔20分鐘〕為何考慮關(guān)系的逆運(yùn)算?假設(shè)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：〔對(duì)合律〕定理2-3：逆運(yùn)算與關(guān)系的集合運(yùn)算并,交,補(bǔ)的關(guān)系證明：〔〕：(3)關(guān)系的復(fù)合運(yùn)算〔35分鐘〕為何考慮關(guān)系的復(fù)合運(yùn)算?假設(shè)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?SS?R.例：R={(x,y)|x,yA,y=x+1或y=x/2}S={(x,y)|x,yA,x=y+2}≠定理2-4：證明思路：定理2-5：定理2-6：證明：注：本性質(zhì)與矩陣的有關(guān)運(yùn)算性質(zhì)類似,請(qǐng)注意順序定理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:AB,g:BC,函數(shù)f與函數(shù)g的復(fù)合記為f?g:假設(shè)f(x)=y且g(y)=z,則(f?g)(x)=g(f(x))=z.由于fAB,gBC,關(guān)系f與關(guān)系g的復(fù)合記為f?g:假設(shè)(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)算，并且對(duì)復(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è)：無(wú)第七講：關(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)：自反性、反自反性、對(duì)稱性、反對(duì)稱性、傳遞性概念的理解，閉包的理解與構(gòu)造2.難點(diǎn)：同上三、教學(xué)內(nèi)容與教學(xué)過(guò)程1.上講內(nèi)容回憶〔5分鐘〕關(guān)系的集合運(yùn)算關(guān)系的逆運(yùn)算關(guān)系的復(fù)合運(yùn)算2.進(jìn)入主題，開(kāi)場(chǎng)第七講本講知識(shí)點(diǎn)概括(1)關(guān)系的性質(zhì)自反性〔10分鐘〕定義：對(duì)于集合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)系矩陣：對(duì)角線元素都為1關(guān)系圖：結(jié)點(diǎn)含有環(huán)反自反性〔10分鐘〕定義：設(shè)RAA,假設(shè)對(duì)于任意xA,均有(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)系矩陣：對(duì)角線元素全為0關(guān)系圖：結(jié)點(diǎn)沒(méi)有環(huán)思考：A上的自反關(guān)系與反自反關(guān)系的區(qū)別與聯(lián)系?對(duì)稱性〔10分鐘〕定義：設(shè)RAA,對(duì)于任意x,yA,假設(shè)(x,y)R,則(y,x)R,則稱R是A上的對(duì)稱關(guān)系,或稱R是對(duì)稱的,或稱R具有對(duì)稱性例2-28：A={a,b,c,d},R={(b,a),(a,b),(b,b),(d,c),(c,d)}?注：Z上的整除關(guān)系|不是對(duì)稱的;P(X)上的包含關(guān)系(一般來(lái)說(shuō))不是對(duì)稱的;R上的小于等于關(guān)系不是對(duì)稱的;R上的小于關(guān)系<不是對(duì)稱的;三角形之間的相似關(guān)系~是對(duì)稱的;Z上的模k同余關(guān)系k是對(duì)稱的.定理2-11：R對(duì)稱R=R-1關(guān)系矩陣：關(guān)于對(duì)角線對(duì)稱圖關(guān)系圖：要么有雙向環(huán)、要么沒(méi)有反對(duì)稱性〔10分鐘〕定義：設(shè)RAA,對(duì)于任意x,yA,假設(shè)(x,y)R且(y,x)R,一定有x=y,則稱R是A上的反對(duì)稱關(guān)系,或稱R具有反對(duì)稱性.例2-29：A={a,b,c,d},R={(a,a),(a,b),(b,b),(b,c),(d,c)}?注：Z上的整除關(guān)系|不是反對(duì)稱的,因?yàn)?|-2且-2|2;P(X)上的包含關(guān)系是反對(duì)稱的;R上的小于等于關(guān)系是反對(duì)稱的;R上的小于關(guān)系<是反對(duì)稱的.定理2-12：R反對(duì)稱關(guān)系矩陣:關(guān)于主對(duì)角線對(duì)稱的元素不能同時(shí)為1關(guān)系圖:兩點(diǎn)之間要么無(wú)邊，要么只有一條邊思考：反對(duì)稱性與對(duì)稱性之間的區(qū)別與聯(lián)系傳遞性〔10分鐘〕定義：設(shè)RAA,對(duì)于任意x,y,zA,假設(shè)(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?RR.證明:()設(shè)(x,z)R?R,則存在yA,使得(x,y)R,(y,z)R.因?yàn)镽傳遞,所以(x,z)R.()對(duì)于任意x,y,zA,假設(shè)(x,y)R且(y,z)R,則(x,z)R?RR,(x,z)R.例2-33:A={a,b,c,d},R1={(a,b),(a,c)}傳遞,R2={(a,b)}也傳遞?,傳遞性的關(guān)系圖:定理2-13:R傳遞R?RR.(2)關(guān)系的閉包①自反閉包r(R)〔10分鐘〕定義：設(shè)RAA,稱最小的包含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)系矩陣的變化：把對(duì)角線上是0的元素全部改成1②對(duì)稱閉包s(R)〔10分鐘〕定義：設(shè)RAA,稱最小的包含R的對(duì)稱關(guān)系為R的對(duì)稱閉包,記為s(R).滿足3個(gè)條件:包含R；對(duì)稱性；最小性.例2-15：解：定理2-15：生成對(duì)稱閉包關(guān)系圖的變化：只有一邊的添加一邊生成對(duì)稱閉包關(guān)系矩陣的變化：關(guān)于對(duì)角線對(duì)稱的元素相等③傳遞閉包r(R)〔10分鐘〕定義：設(shè)RAA,稱最小的包含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：假設(shè)|A|=n1,RAA,則傳遞閉包的關(guān)系圖:從a到b的邊存在，從b到c的邊存在，那么添加從a到c的邊3.教學(xué)小結(jié)〔3分鐘〕本講重點(diǎn)介紹了關(guān)系的幾個(gè)性質(zhì)：自反性、反自反性、對(duì)稱性、反對(duì)稱性、傳遞性的定義、及他們的關(guān)系矩陣、關(guān)系圖；接著介紹了自反閉包，對(duì)稱閉包，傳遞閉包的定義及構(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è)：無(wú)第八講：關(guān)系〔四〕一、教學(xué)目標(biāo)1.掌握等價(jià)關(guān)系，等價(jià)類及商集的概念2.了解相容關(guān)系的概念3.掌握偏序關(guān)系，哈斯圖的畫法，會(huì)求偏序集上的特殊元素二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：等價(jià)關(guān)系、等價(jià)類、偏序集、哈斯圖2.難點(diǎn)：偏序關(guān)系三、教學(xué)內(nèi)容與教學(xué)過(guò)程1.習(xí)題講解〔5分鐘〕2.上講內(nèi)容回憶〔5分鐘〕關(guān)系的性質(zhì)：自反性；反自反性；對(duì)稱性；反對(duì)稱性；傳遞性關(guān)系的閉包：自反閉包；對(duì)稱閉包；傳遞閉包3.進(jìn)入主題，開(kāi)場(chǎng)第八講。(1)等價(jià)關(guān)系〔25分鐘〕①等價(jià)關(guān)系：設(shè)RAA,假設(shè)R具有自反性、對(duì)稱性以及傳遞性,則稱R為A上的等價(jià)關(guān)系.例2-47：設(shè)A={a,b,c},R={(a,a),(b,b),(c,c),(b,c),(c,b)},則R具有自反性、對(duì)稱性以及傳遞性,因此R為A上的等價(jià)關(guān)系.例：Z上的模3同余關(guān)系是Z上的等價(jià)關(guān)系。定理2-21：設(shè)R和S為A上的等價(jià)關(guān)系,則R-1及RS為A上的等價(jià)關(guān)系.②等價(jià)類：定義：例：Z上的模3同余關(guān)系R：定理2-22：設(shè)R為A上的等價(jià)關(guān)系,對(duì)于任意x,yA,則證明：定理2-23：設(shè)R為A上的等價(jià)關(guān)系,對(duì)于任意x,yA.證明：③商集：例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},={{a},{b,c}},則R={(a,a),(b,b),(c,c),(b,c),(c,b)},它是A上的一個(gè)等價(jià)關(guān)系..注：(x,y)Rx和y在劃分的同一個(gè)塊中定理2-25：對(duì)于任意集合A,集合A上的所有劃分組成的集合X與其上的所有等價(jià)關(guān)系組成的集合Y是對(duì)等的.(2)相容關(guān)系〔10分鐘〕相容關(guān)系：設(shè)RAA,假設(shè)R具有自反性、對(duì)稱性，則稱R為A上的相容關(guān)系.等價(jià)關(guān)系相容關(guān)系,但相容關(guān)系不一定是等價(jià)關(guān)系(3)偏序關(guān)系①偏序關(guān)系定義〔10分鐘〕設(shè)RAA,假設(shè)R具有自反性、反對(duì)稱性和傳遞性,則稱R為A上的偏序.借用數(shù)的表示偏序,可讀作“小于等于〞,(A,)稱為偏序集.例：R,?P(X),?N+,|?線性序：設(shè)是A上的偏序,假設(shè)對(duì)任意x,yA,有xy或yx,則稱是線性序關(guān)系,簡(jiǎ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,yA且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)系的自反、反對(duì)稱、傳遞性進(jìn)展簡(jiǎn)化的關(guān)系圖哈斯圖特點(diǎn)：a.每個(gè)結(jié)點(diǎn)沒(méi)有環(huán)b.兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過(guò)結(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.最小元、最大元、極小元、極大元假設(shè)x(x∈B→y?x)成立,則稱y為B的最小元假設(shè)x(x∈B→x?y)成立,則稱y為B的最大元假設(shè)x(x∈B∧x?y→x=y)成立,則稱y為B的極小元假設(shè)x(x∈B∧y?x→x=y)成立,則稱y為B的極大元b.上界、下界、上確界、下確界假設(shè)x(x∈B→x?y)成立,則稱y為B的上界假設(shè)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；沒(méi)有最小元與最大元.B的下界和最大下界都不存在；上界有d和f,最小上界為d.4.教學(xué)小結(jié)〔3分鐘〕本講介紹了幾種常見(jiàn)關(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è)：無(wú)第九講：命題邏輯〔一〕一、教學(xué)目標(biāo)掌握命題的概念〔真假命題〕掌握命題邏輯的表示方式〔對(duì)象語(yǔ)言與元語(yǔ)言〕掌握連接詞符號(hào)的表示以及真假的判定二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：對(duì)命題概念的理解以及對(duì)象語(yǔ)言、元語(yǔ)言的區(qū)別，幾種連接詞的表示以及判定真假的方法2.難點(diǎn)：對(duì)命題概念的理解以及對(duì)蘊(yùn)含詞符號(hào)的理解三、教學(xué)內(nèi)容與教學(xué)過(guò)程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)入主題，開(kāi)場(chǎng)第九講(1)命題的有關(guān)概念〔25分鐘〕計(jì)算機(jī)的計(jì)算過(guò)程就是推理過(guò)程,而每一步推理離不開(kāi)判斷,判斷的對(duì)象就是命題.①命題定義：能判斷出真假的語(yǔ)句注：a,命題必須是一個(gè)完整的句子,包括用數(shù)學(xué)式子如代表的語(yǔ)句.這一點(diǎn)在后面的命題符號(hào)化時(shí)要注意;b,所給語(yǔ)句具有真假意義,即有是否符合客觀實(shí)際或是否合理之分.一般來(lái)說(shuō),只有陳述句才具有真假意義,祈使句、疑問(wèn)句和感慨句不具有真假意義;c,能判斷出真假,不過(guò),要是將來(lái)某時(shí)候能判斷出真假也行例：你媽喊你回家吃飯.《建國(guó)大業(yè)》里面有很多大腕兒.x>3.(不是命題)立正！(不是命題)這朵花真漂亮！(不是命題)你喜歡網(wǎng)絡(luò)游戲嗎?(不是命題)火星上有生物.我說(shuō)的都是假話.(不是命題)小王和小李是同學(xué).你只有刻苦學(xué)習(xí),才能取得好成績(jī)我不去游泳僅當(dāng)你走，我留下值班②命題的真值命題的真值就是命題的邏輯取值經(jīng)典邏輯值只有兩個(gè):1和0,它們是表示事物狀態(tài)的兩個(gè)量。實(shí)際上在數(shù)理邏輯中,更多時(shí)候邏輯真是用T(True)或t,邏輯假用F(False)或f表示的③命題的表示a.對(duì)象語(yǔ)言的描述b.命題獨(dú)享語(yǔ)言的描述：原子命題是不包含有更小的命題的命題，通常用小寫英文字母p,q,r,s,…或帶下標(biāo)p1,p2,p3,…等來(lái)表示原子命題,如用p:2+3=5,q:今天我們上課.復(fù)合命題是由原子命題和聯(lián)接詞構(gòu)成的命題，聯(lián)接詞類似于自然語(yǔ)言中的連詞。注：“小王和小李是同學(xué)〞是原子命題。例：“僅當(dāng)你走，我留下值班〞：p:你走，q:我留下值班“我不去游泳〞：p：我去游泳命題常量、命題變量把1和0稱為邏輯常量；在邏輯表達(dá)式中出現(xiàn)的p,q,r或p1,p2,p3等稱為命題變?cè)蜻壿嬜兞?(2)連接詞符號(hào)〔55分鐘〕①否認(rèn)聯(lián)接詞：p〔5分鐘〕p:2+3=5,p:2+35.pp1001真值表：例：p:下周開(kāi)運(yùn)動(dòng)會(huì)，p：下周不開(kāi)運(yùn)動(dòng)會(huì)注：p是數(shù)理邏輯中的標(biāo)準(zhǔn)符號(hào),也可記為~p,C語(yǔ)言!p,在計(jì)算機(jī)其他課程中用,對(duì)應(yīng)于邏輯門電路中的“非門〞.②合取聯(lián)接詞:pq〔10分鐘〕p:小李能歌,q:小李善舞.pq:小李能歌且善舞.合取“〞相當(dāng)于“并且〞,“和〞,“與〞,“以及〞等.pqpq111100010000真值表：注意：“小王和小李是同學(xué)〞中的“和〞沒(méi)有合取之意.在數(shù)理邏輯中,合取聯(lián)結(jié)詞可以將任意兩個(gè)命題聯(lián)結(jié)起來(lái)以構(gòu)造出新的命題,如用p:2+3=5,q:今天上課,則pq:2+3=5且今天上課.注：pq:p&q,p&&q,pq=pq,對(duì)應(yīng)于“與門〞.③析取聯(lián)接詞:pq〔5分鐘〕p:這學(xué)期我選修人工智能課程,q:這學(xué)期我選修模式識(shí)別課程.pq:這學(xué)期我選修人工智能課程或者模式識(shí)別課程.析取“〞相當(dāng)于“或者〞.p|q,p||q,p+q(“或門〞).pqpq111101011000真值表：④異或聯(lián)接詞:pq〔10分鐘〕自然語(yǔ)言中的“或〞:“可兼或〞(inclusiveor),它表示兩者可同時(shí)為真,用析取表示即可；“不可兼或〞,它表示兩者不能同時(shí)為真,換句話說(shuō),兩者同時(shí)為真是假命題.這就需要異或聯(lián)結(jié)詞.p:明天去深圳的飛機(jī)是上午八點(diǎn)起飛,q:明天去深圳的飛機(jī)是上午八點(diǎn)半起飛.pq:明天去深圳的飛機(jī)是上午八點(diǎn)或上午八點(diǎn)半起飛.pqpq110101011000真值表：注：與異或聯(lián)結(jié)詞對(duì)應(yīng)的門電路為“異或門〞.對(duì)于自然語(yǔ)言中的“或〞用還是需要仔細(xì)分析,一般來(lái)說(shuō),只要不是非常明顯的不兼就使用.⑤條件聯(lián)接詞:pq〔10分鐘〕p:我有時(shí)間,q:我去看望我的父母.pq:如果我有時(shí)間,那么我去看望我的父母.“〞相當(dāng)于“如果…那么…〞,“假設(shè)…則…〞,等.pq可讀作“(假設(shè))p則q〞.pqpq111100011001真值表：在pq中,p稱為前件,q稱為后件.當(dāng)p=1,q=1時(shí)pq=1;當(dāng)p=1,q=0時(shí)pq=0,這是對(duì)比好理解的兩種情形.由于我們現(xiàn)在討論的是實(shí)質(zhì)蘊(yùn)涵,規(guī)定當(dāng)p=0,q=1時(shí)pq=1;當(dāng)p=0,q=0時(shí)pq=1.規(guī)定的合理性見(jiàn)下面的例子.a.如果太陽(yáng)從西邊出來(lái),那么2+3=5.b.如果太陽(yáng)從西邊出來(lái),那么2+3=4.⑥雙條件聯(lián)接詞:pq〔10分鐘〕p:四邊形是平行四邊形,q:四邊形的對(duì)邊平行.pq:四邊形是平行四邊形當(dāng)且僅當(dāng)四邊形的對(duì)邊平行.pq:可讀作“p當(dāng)且僅當(dāng)q〞.雙條件聯(lián)結(jié)詞“〞相當(dāng)于自然語(yǔ)言中的“當(dāng)且僅當(dāng)〞“p當(dāng)且僅當(dāng)q〞有兩層含義：(1)“p當(dāng)q〞是指qp.(2)“p僅當(dāng)q〞是指pq.正因?yàn)榇?等價(jià)聯(lián)結(jié)詞又可以稱為雙蘊(yùn)涵聯(lián)結(jié)詞或雙條件聯(lián)結(jié)詞.pqpq111100010001真值表：注：在數(shù)字邏輯等課程中,等價(jià)聯(lián)結(jié)詞稱為“同〞,并用“⊙〞符號(hào)表示⑦與非聯(lián)接詞:pq〔2分鐘〕pqpq110101011001真值表：⑧或非聯(lián)接詞:pq〔2分鐘〕pqpq110100010001真值表：⑨條件否認(rèn)聯(lián)接詞：〔1分鐘〕真值表：pq

1101010100004.教學(xué)小結(jié)〔3分鐘〕本講首先介紹了命題的概念及其表示方式，然后依次介紹了九種聯(lián)接詞，其中重點(diǎn)需要掌握否認(rè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è)：無(wú)第十講：命題邏輯〔二〕一、教學(xué)目標(biāo)1.理解命題公式的概念2.掌握命題公式的組成符號(hào)、組成原則3.掌握變?cè)嬷抵概傻暮x及命題公式的真值表4.理解命題公式的類型，掌握命題公式類型判斷的方法二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：命題公式的概念，命題公式的真值表，命題公式類型的判斷2.難點(diǎn)：命題公式類型的判斷三、教學(xué)內(nèi)容與教學(xué)過(guò)程1.習(xí)題講解〔10分鐘〕2.上講內(nèi)容回憶〔5分鐘〕命題的概念〔真假命題〕命題邏輯的表示方式〔對(duì)象語(yǔ)言與元語(yǔ)言〕連接詞符號(hào)的表示以及真假的判定3.進(jìn)入主題，開(kāi)場(chǎng)第十講本講知識(shí)點(diǎn)概括(1)命題公式〔15分鐘〕①命題公式的概念命題公式是由命題常量、命題變?cè)?、邏輯?lián)結(jié)詞、左圓括號(hào)(及由圓括號(hào))構(gòu)成的有意義(well-formed)的符號(hào)串,其嚴(yán)格定義需借助于遞歸定義方式給出.a.1,0,p,q,r,…b.A(A)c.A,Bd.有限次應(yīng)用(1)(2)(3)所得到的符號(hào)串是僅有的命題公式.例:命題公式可稱為合式公式或簡(jiǎn)稱為公式,其全稱為命題合式公式.這兒的公式實(shí)際上是書寫正確、含義清楚的表達(dá)式或者說(shuō)符號(hào)串可以省略括號(hào)的約定:a.最外層的括號(hào)可以省略.在形成最終的命題公式時(shí),所有的中間過(guò)程得到的命題公式,包含其本身,都稱為該命題公式的子公式.b.9個(gè)聯(lián)結(jié)詞運(yùn)算的優(yōu)先順序依次為:符合本約定的有些括號(hào)可以不寫.如命題公式注：這種規(guī)定不是唯一的.c.同級(jí)運(yùn)算從左至右依次進(jìn)展.如實(shí)際上,在對(duì)命題進(jìn)展符號(hào)化時(shí),只要書寫正確的邏輯函數(shù)都是命題公式.(2)命題的符號(hào)化〔15分鐘〕命題的符號(hào)化就是使用符號(hào)—命題變?cè)?、邏輯?lián)結(jié)詞和括號(hào)將所給出的命題表示出來(lái).一方面說(shuō)明,符號(hào)體系來(lái)源于實(shí)際問(wèn)題,另一方面也是給出進(jìn)一步學(xué)習(xí)邏輯演算系統(tǒng)的語(yǔ)義解釋時(shí)的一種標(biāo)準(zhǔn)模型.命題的符號(hào)化的步驟:Step1找出所給命題的所有原子命題,并用小寫英文字母或帶下標(biāo)表示；Step2確定應(yīng)使用的聯(lián)結(jié)詞,進(jìn)而將原命題用符號(hào)表示出來(lái).例3-7(P86)將以下命題符號(hào)化.a.天氣很好或很熱.b.如果張三和李四都不去,那么我就去.c.僅當(dāng)你走,我留下.e.我今天進(jìn)城,除非天下雨.d.你只有刻苦學(xué)習(xí),才能取得好成績(jī).解：a.或?b.“張三不去〞是復(fù)合命題.c.p:你走,q:我留下,僅當(dāng)?d.p:我今天進(jìn)城,q:天下雨.除非=如果不.e.p:你刻苦學(xué)習(xí),q:你取得好成績(jī).只有p,才q?(3)命題公式的真值表〔20分鐘〕對(duì)于命題公式,假設(shè)對(duì)中出現(xiàn)的每個(gè)命題變?cè)贾付ㄒ粋€(gè)真值1或者0,就對(duì)命題公式A進(jìn)展了一種真值指派或一個(gè)解釋,而在該指派下會(huì)求出公式A的一個(gè)真值.將A的所有可能的真值指派以及在每一個(gè)真值指派下的取值列成一個(gè)表,就得到命題公式A的真值表.例3-8寫出命題公式A=的真值表.pqrppq(pq)r111011110010101001100001011111010110001111000110例：B＝(qp)qppqqp(qp)q(qp)qp00011011101100011111例：C＝(pq)qpqppq(pq)(pq)q000110111100110100100000注：由表知,含3個(gè)命題變?cè)拿}公式有8=23種不同的真值指派.很顯然,含2個(gè)命題變?cè)拿}公式有4=22種不同的真值指派.一般來(lái)說(shuō),含n個(gè)命題變?cè)拿}公式的不同的真值指派有2n種.〔4〕命題公式的類型〔20分鐘〕a.在任何指派下均取真的命題公式稱為永真式或重言式；b.在任何指派下均取假的命題公式稱為永假式或矛盾式；c.至少有一種指派使其為真的命題公式稱為可滿足式；d.至少有一種指派使其為真同時(shí)至少有一種指派使其為假的命題公式稱為中性式.判斷公式種類的方法：①真值表法(求出公式的所有指派,判斷公式的類型)例3-9pqpqpq111101011001②取值法：例：由A=1可推出B=1,則AB永真.由B=0可推出A=0,則AB永真.例：用真值表判斷下面公式的類型(1)pr(qp)(2)((pq)(qp))r(3)(pq)(pr)pqrqp(qp)pr(qp)000001010011100101110111110011110011000000000000定理3-1(永真式的代入定理)若何使用4.教學(xué)小結(jié)〔3分鐘〕本講首先介紹了命題公式的概念以及命題的符號(hào)化，接著介紹了命題公式的真值表及命題公式的類型，最后重點(diǎn)介紹了若何利用真值表法和取值法判斷命題公式的類型。四、作業(yè)與實(shí)驗(yàn)〔2分鐘〕1.書面作業(yè)：習(xí)題3.31(雙),2(雙),3(雙),4,5,6(雙).2.上機(jī)作業(yè)：無(wú)第十一講：命題邏輯〔三〕一、教學(xué)目標(biāo)1.理解命題公式的邏輯等值的概念2.理解并掌握基本等值式及其他重要等值式3.掌握等值演算法及其應(yīng)用二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：基本等值式，等值演算法2.難點(diǎn)：應(yīng)用等值演算法三、教學(xué)內(nèi)容與教學(xué)過(guò)程1.習(xí)題講解〔5分鐘〕2.上講內(nèi)容回憶〔5分鐘〕命題公式的定義命題的符號(hào)化命題公式的真值表命題公式的類型3.進(jìn)入主題，開(kāi)場(chǎng)第十一講本講知識(shí)點(diǎn)概括(1)邏輯等值定義：給定兩個(gè)命題公式A和B,假設(shè)在任何真值指派下A和B的真值都一樣,則稱命題公式A和B邏輯等價(jià)或邏輯等值或簡(jiǎn)稱為等值或相等,記為A=B.注：AB與A=B(AB)是不同的.A=B(AB)中的=是關(guān)系符號(hào)，A=B是等值式，是運(yùn)算符號(hào)，AB是命題公式，運(yùn)算結(jié)果可真可假。定理3-2：A=B的充要條件是AB永真.證明：例3-11證明pqP→qppq11101100000111100111②模運(yùn)算定理3-3：例如：定理3-4：邏輯等值是命題公式間的等價(jià)關(guān)系:(1)A=A〔自反性〕(2)假設(shè)A=B，則B=A〔對(duì)稱性〕(3)假設(shè)A=B且B=C，則A=C〔傳遞性〕.(2)基本等值式①與,,有關(guān)的等值式定理3-5：〔對(duì)合律〕〔冪等律〕〔交換律〕〔結(jié)合律〕〔吸收律〕注：與集合的有關(guān)性質(zhì)類似.每條性質(zhì)均可證明.例3-12：證明對(duì)于任意命題公式A和B，有證明：只需證pq1111100101000000②其他重要等值式設(shè)A,B是任意的命題公式，則注：基本等值式有很多用途,如化簡(jiǎn)命題公式、判斷命題公式的類型、證明等值式、計(jì)算命題公式的范式、命題邏輯中的推理等,要求大家要熟記,特別是定理3-5中的等值式.(3)等值演算法定理3-7〔等值置換定理〕：設(shè)C是命題公式A的子公式,假設(shè)C=D,則將A中的C局部或全部替換為D所得到的命題公式與A等值.利用基本等值式以及等值置換定理求解問(wèn)題的方法稱為“等值演算法〞.①化簡(jiǎn)命題公式例3-13(P92)化簡(jiǎn)以下命題公式并將最后結(jié)果用只含和表示.a.b.解：a.b.注：命題公式的化簡(jiǎn)是指將其化為一個(gè)與其等值的滿足條件的含“聯(lián)接詞最少〞的命題公式。②判斷命題公式的類型例3-14：設(shè)A,B,C是任意的命題公式,判斷以下命題公式的類型:解：故是中性式③證明命題公式等值例3-15：設(shè)A,B,C是任意的命題公式,證明以下等值式.a.b.證明：a.b.(4)對(duì)偶原理定義：設(shè)命題公式A中只含有3個(gè)邏輯聯(lián)結(jié)詞,,,將A中的換成；A中的換成；A中的1換成0；A中的0換成1,所得到的命題公式稱為是A的對(duì)偶式,記為A*.例：對(duì)偶原理：設(shè)A和B是命題公式,假設(shè)A=B,則A*=B*.4.教學(xué)小結(jié)〔3分鐘〕本講首先介紹了命題公式等值的概念，然后介紹了基本等值式及其他重要等值式，在此根基上又介紹了等值演算法，并舉例說(shuō)明若何用等值演算法化簡(jiǎn)命題公式、判斷命題公式類型、證明命題公式等值。最后介紹了命題公式的對(duì)偶原理。四、作業(yè)與實(shí)驗(yàn)〔2分鐘〕1.書面作業(yè)：習(xí)題3.45(雙),6,9(雙),10,112.上機(jī)作業(yè)：無(wú)第十二講：命題邏輯〔四〕一、教學(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é)過(guò)程1.上講內(nèi)容回憶〔5分鐘〕邏輯等值的定義基本等值式等值演算法對(duì)偶原理2.進(jìn)入主題，開(kāi)場(chǎng)第十二講本講知識(shí)點(diǎn)概括命題公式的析取范式〔20分鐘〕①定義：設(shè)A是命題公式,假設(shè)A=A1A2…An(n1),其中Ai(1in)是由命題變?cè)蚱浞裾J(rèn)組成的合取式,則稱A1A2…An注：Ai=pqr,pq,qr,q,r?n=1?如A=pqr=(pqr).②求法Step1使用等值式,將命題公式中的聯(lián)結(jié)詞歸約為,,；Step2利用DeMorgan律將移到命題變?cè)那懊妫籗tep3根據(jù)分配律得到命題公式的析取范式及合取范式：A(BC)=(AB)(AC).例3-17：設(shè)p,q和r是命題變?cè)?求命題公式A=(pq)r的析取范式.解：命題公式的合取范式〔10分鐘〕①定義：設(shè)A是命題公式,假設(shè)A=A1A2…An(n1),其中Ai(1in)是由命題變?cè)蚱浞裾J(rèn)組成的析取式,則稱A1A2…注：Ai=pqr,pq,qr,q,r?n=1?如A=pqr=(pqr).假設(shè)A=pqr,則pqr也是A的析取范式.②求法Step1使用等值式,將命題公式中的聯(lián)結(jié)詞歸約為,,；Step2利用DeMorgan律將移到命題變?cè)那懊妫籗tep3根據(jù)分配律得到命題公式的析取范式及合取范式：A(BC)=(AB)(AC)例3-17：設(shè)p,q和r是命題變?cè)?求命題公式A=(pq)r的析取范式.解：析取范式及合取范式的應(yīng)用〔20分鐘〕根據(jù)命題公式的析取范式及合取范式可分別得出該命題公式取真、假的指派.例：例3-18：從p,q,r,s四人中選派2人出差,求滿足以下3個(gè)條件的選派方法有哪幾種.a.假設(shè)p去,則r和s中只去1人；b.q和r不能都去；c.假設(shè)r去,則s不能去.解:p:p去出差,q:q去出差,r:r去出差,s:s去出差,則則：(a)p,s去;(b)q,s去;(c)p,r去.(4)命題公式的主析取范式〔10分鐘〕①最小項(xiàng)：對(duì)于給定的命題變?cè)?假設(shè)由命題變?cè)蚱浞裾J(rèn)組成的合取式滿足(1)每個(gè)命題變?cè)蚱浞裾J(rèn)二者之一只出現(xiàn)一次；(2)按字典順序或按下標(biāo)從小到大順序出現(xiàn)。注：對(duì)于每一個(gè)最小項(xiàng)只有一種指派使其取1.②定義：對(duì)于命題公式A,假設(shè)A等值于由A中所有命題變?cè)a(chǎn)生的假設(shè)干個(gè)最小項(xiàng)的析取,則把后者稱為A的主析取范式例：③主析取范式的求法〔20分鐘〕a.等值演算法.計(jì)算步驟為:Step1求出A的析取范式；Step2利用分配律補(bǔ)充所缺少的命題變?cè)?例：b.真值表法步驟為：Step1寫出命題公式A的真值表；Step2對(duì)于使A取1的指派,寫出對(duì)應(yīng)的最小項(xiàng),使該最小項(xiàng)在該指派下也為1；Step3(可以證明)A等值于所有這樣寫出的最小項(xiàng)的析取.例3-20：設(shè)p,q和r是命題變?cè)?求命題公式(pq)r的主析取范式.pqrpq(pq)r1111111010101111001001111010100010100001(4)命題公式的主范式的應(yīng)用〔10分鐘〕例3-23：設(shè)p和q是命題變?cè)?利用主范式判斷命題公式p(pq)的類型.解：例3-24例3-254.教學(xué)小結(jié)〔3分鐘〕本講首先介紹了命題公式的析取范式和合取范式的定義及求法，接著介紹了析取范式，合取范式的應(yīng)用，然后介紹了主析取范式、主合取范式的概念及求法，最后介紹了命題公式的主范式的應(yīng)用。四、作業(yè)與實(shí)驗(yàn)〔2分鐘〕1.書面作業(yè)：習(xí)題3.5：1(雙),4,5(雙),6,7(2),8.2.上機(jī)作業(yè)：無(wú)第十三講：命題邏輯〔五〕一、教學(xué)目標(biāo)1.理解命題邏輯空間中推理有效性的定義2.掌握基本推理有效式I3.掌握證明推理有效性的方法二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：推理有效性的證明2.難點(diǎn)：同上三、教學(xué)內(nèi)容與教學(xué)過(guò)程1.習(xí)題講解〔5分鐘〕2.上講內(nèi)容回憶〔5分鐘〕命題公式的析取范式、合取范式的定義、求法命題公式的主析取范式、主合取范式命題公式的范式的應(yīng)用3.進(jìn)入主題，開(kāi)場(chǎng)第十三講〔1〕引例〔5分鐘〕例如,下面兩個(gè)不同的推理(a)假設(shè)兩直線平行,則同位角相等,這兩直線是平行的,所以,同位角相等.(b)假設(shè)兩個(gè)三角形全等,則其對(duì)應(yīng)邊相等,這兩個(gè)三角形全等,所以,它們的對(duì)應(yīng)邊相等.都具有如下的推理形式:由pq,p得出q.〔2〕推理有效性定義〔10分鐘〕所謂推理形式的有效性是指,如果前提全為真,那么所得結(jié)論必然真,而不考慮前提和結(jié)論的真實(shí)含義。記為:定理：的充要條件是注：“〞又是“永真蘊(yùn)涵〞或“邏輯蘊(yùn)涵〞符號(hào),它與聯(lián)結(jié)詞蘊(yùn)涵“〞是不同的.“〞是關(guān)系符號(hào)，“〞是運(yùn)算符號(hào)，運(yùn)算結(jié)果是邏輯值。〔3〕基本推理規(guī)則〔10分鐘〕例3-29設(shè)A和B是命題公式,證明:AB,AB.分析:(pq)pq永真?Proof1真值表法.Proof2取值法—一種簡(jiǎn)易的真值表法.(pq)p=1,q=1?Proof3等值演算法.(pq)pq=1?Proof4主范式法.主析取范式:主合取范式:1.基本推理規(guī)則或基本蘊(yùn)涵式I(P110).(1)(2)(3)(4)(5)(6)(7)(8)基本等值式E:表3-24(P111)〔4〕推理有效性證明——構(gòu)造法〔15分鐘〕例3-30(P111)使用構(gòu)造法證明:證明:(1)psP(2)pT(1)I(3)sT(1)I(4)p(qr)P(5)qrT(2)(4)I(6)sqP(7)qT(3)(6)I(8)rT(5)(7)I注：以上證明過(guò)程中，第一局部是編號(hào),說(shuō)明它是證明的第幾步；第二局部?jī)H寫一個(gè)命題公式,實(shí)