理工類(lèi)專(zhuān)業(yè)課復(fù)習(xí)資料-離散數(shù)學(xué)考點(diǎn)精講及復(fù)習(xí)思路

第一章命題邏輯 ()7第二章謂詞邏輯 ()15第三章二元關(guān)系 ()23第四章圖論 ()51第五章代數(shù)系統(tǒng) ()86《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路學(xué)》考研分析作者:左孝凌,李為鑒,劉永才,出版社:上海科學(xué)技術(shù)出版社其他參考書(shū)目《離散數(shù)學(xué)》耿素云、屈婉玲等,清華大學(xué)出版社《離散數(shù)學(xué)》方世昌,西安電子科技大學(xué)出版社《離散數(shù)學(xué)》洪帆,華中科技大學(xué)出版社《離散數(shù)學(xué)及其應(yīng)用》.傅彥等.高等教育出版社《離散數(shù)學(xué)及其應(yīng)用》,KennethH.Rosen著,袁崇義等譯,機(jī)械工業(yè)出版社1.考試形式①單考離散數(shù)學(xué):基礎(chǔ)題約占60%,綜合題約占40%②計(jì)算機(jī)類(lèi)一張卷子合考時(shí):離散數(shù)學(xué)一般占總分的40-60%,側(cè)重于基礎(chǔ)知識(shí)點(diǎn)及對(duì)知識(shí)點(diǎn)靈活運(yùn)用的考核,大題為主③復(fù)試中?？脊P試科目2.常見(jiàn)的考試題型題型一般分兩類(lèi):基礎(chǔ)題主要考察對(duì)各種基本概念的掌握程度,以及各種定理的證明和基本應(yīng)用。例如:證明等價(jià)關(guān)系:即證明關(guān)系有自反、對(duì)稱(chēng)、傳遞的性質(zhì)。-1-考試點(diǎn)()名師精品課程電話(huà):400-6885-365證明偏序關(guān)系:即證明關(guān)系有自反、反對(duì)稱(chēng)、傳遞的性質(zhì)。證明群:即要證明代數(shù)系統(tǒng)封閉、可結(jié)合、有幺元和逆元。2)綜合題:內(nèi)容涵蓋若干章或融合多個(gè)知識(shí)點(diǎn)的考題,或者是結(jié)合應(yīng)用背景形成的綜合應(yīng)用題。3.考試內(nèi)容涉及的知識(shí)點(diǎn)分布第一部分?jǐn)?shù)理邏輯(1)命題邏輯:知識(shí)點(diǎn):1)命題的概念、表示、分類(lèi);五種基本聯(lián)結(jié)詞的邏輯意義。2)命題公式的遞歸定義,自然語(yǔ)言翻譯成命題公式3)真值表的構(gòu)造、命題公式等價(jià)的概念。4)重言式與蘊(yùn)涵式的定義、邏輯意義,邏輯等價(jià)與邏輯蘊(yùn)涵的意義和證明方法。常用的邏輯等價(jià)公式和邏輯蘊(yùn)涵公式。的方法,公式類(lèi)型與主范式之間的關(guān)系。6)命題邏輯的推理理論,主要的推理方法:真值表法、直接證明法、間接證明法。常用推理規(guī)則:P重點(diǎn):蘊(yùn)涵式的理解,命題的符號(hào)化,命題邏輯推理,計(jì)算范式、主析取(合取)范式等。(2)謂詞邏輯:知識(shí)點(diǎn):1)謂詞的概念與表示方法,量詞、個(gè)體域和個(gè)體的概念2)謂詞邏輯的合式公式與自然語(yǔ)言的翻譯4)謂詞邏輯的等價(jià)式和蘊(yùn)含式5)前束范式的概念及求解方法CP規(guī)則;重點(diǎn):謂詞公式的符號(hào)化,謂詞邏輯的推理等-2-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路第二部分集合與關(guān)系(1)集合與關(guān)系:知識(shí)點(diǎn):1)集合的基本概念與表示方法;3)序偶與笛卡爾積;矩陣、關(guān)系圖;5)關(guān)系的性質(zhì),復(fù)合關(guān)系、逆關(guān)系;6)關(guān)系的閉包運(yùn)算:r(R),s(R),t(R);重點(diǎn):冪集的計(jì)算,關(guān)于關(guān)系性質(zhì)的證明,關(guān)系的閉包計(jì)算(2)特殊關(guān)系:知識(shí)點(diǎn):2)集合劃分的定義,等價(jià)關(guān)系與集合劃分的關(guān)系關(guān)系、全序關(guān)系和良序關(guān)系的定義4)偏序關(guān)系的哈斯圖表示,偏序關(guān)系的八個(gè)特殊元。重點(diǎn):等價(jià)關(guān)系的證明、等價(jià)類(lèi)商集的計(jì)算、等價(jià)關(guān)系與集合劃分的關(guān)系、偏序關(guān)系的證明以及特殊元的計(jì)算等(3)函數(shù):知識(shí)點(diǎn):1)函數(shù)的概念,定義域、值域等基本概念,單射函數(shù)、滿(mǎn)射函數(shù)、雙射函數(shù)。2)復(fù)合函數(shù)、逆函數(shù)的概念,復(fù)合函數(shù)與關(guān)系復(fù)合的聯(lián)系與區(qū)別,逆函數(shù)與逆關(guān)系的聯(lián)系與區(qū)別。重點(diǎn):單、滿(mǎn)、雙函數(shù)的證明,復(fù)合函數(shù)、逆函數(shù)等相關(guān)的證明第三部分圖論(1)圖:知識(shí)點(diǎn):1)圖的基本概念:圖的定義、表示、操作、分類(lèi)以及鄰接點(diǎn)與鄰接邊定義;成子圖、導(dǎo)出子圖的概念;3)通路與回路:簡(jiǎn)單(基本)通路與簡(jiǎn)單(基本)回路、通路與回路長(zhǎng)度、結(jié)點(diǎn)的距離、可達(dá)性判定及矩陣表示4)圖的連通性:無(wú)向連通圖與連通分支、強(qiáng)(單向、弱)連通圖及其對(duì)應(yīng)的連通分支定義等;重點(diǎn):連通圖(證明),與結(jié)點(diǎn)度數(shù)相關(guān)的證明或計(jì)算等(2)樹(shù):知識(shí)點(diǎn):-3-考試點(diǎn)()名師精品課程電話(huà):400-6885-3652)樹(shù)的基本性質(zhì):m=n-1重點(diǎn):樹(shù)的基本概念相關(guān)計(jì)算和證明,最小生成樹(shù)構(gòu)造,哈夫曼編碼等等(3)特殊圖知識(shí)點(diǎn):圖2)幾個(gè)特殊圖的判定方法第四部分代數(shù)系統(tǒng)(1)代數(shù)結(jié)構(gòu)知識(shí)點(diǎn):1)代數(shù)運(yùn)算的定義,代數(shù)運(yùn)算的封閉性,代數(shù)系統(tǒng)的概念,子代樹(shù)的概念3)代數(shù)系統(tǒng)中的特殊元素:幺元(單位元)、零元、逆元、冪等元的一些基本性質(zhì)4)同態(tài)與同構(gòu)的概念、基本性質(zhì)以及判定7)交換群、循環(huán)群等特殊群的概念及性質(zhì)8)陪集和拉格朗日定理9)正規(guī)子群和商群的概念和性質(zhì)重點(diǎn):代數(shù)結(jié)構(gòu)中特殊元素的識(shí)別和計(jì)算;半群、含幺半群、群、Abel群的運(yùn)算性質(zhì);半群、含幺半(2)格與布爾代數(shù)知識(shí)點(diǎn):1)格的概念,偏序格與代數(shù)格的等價(jià)關(guān)系2)各種特殊格、布爾代數(shù)的概念與判斷3)格的性質(zhì)與運(yùn)算律,對(duì)偶原理,保序定理4)子格與子布爾代數(shù)、格同態(tài)與布爾同態(tài)的概念與證明5)布爾表達(dá)式及其簡(jiǎn)化與標(biāo)準(zhǔn)形式重點(diǎn):格與布爾代數(shù)的性質(zhì)、證明以及應(yīng)用-4-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路4.考試題型及題型考核點(diǎn)分析題型考核點(diǎn)涉及章節(jié)備注選擇題填空題判斷題問(wèn)答題主要是概念、原理內(nèi)容準(zhǔn)確性和理解深度的考核全書(shū)所有章節(jié)證明題命題邏輯、謂詞邏輯的形式化及公式之間的等價(jià)關(guān)系的證明,,1-1-61-2-,,1-1-61-2-6,集合相等的判定,關(guān)系性質(zhì)的證明(等價(jià)、偏序、全序、良序等),關(guān)系運(yùn)算律的證明。,,2-1-52-2-,,2-1-52-2-1,,2-2-3函數(shù)的性質(zhì)(單、滿(mǎn)、雙)的判定和證明2-3-1圖的同構(gòu)、結(jié)點(diǎn)的度數(shù)等的證明,,3-2-23-2-,,3-2-23-2-3,樹(shù)及其性質(zhì)的判定和證明3-2幾種特殊圖的判定,3-3-13-3-2,代數(shù)系統(tǒng)中特殊元唯一性證明,特殊元的性質(zhì)證明,代數(shù)系統(tǒng)的同態(tài)與同構(gòu)證明及其性質(zhì)證明等,,4-1-34-1-,,4-2-4定,元素的周期性證明,有限群的一些性質(zhì)證明,環(huán)和域的性質(zhì)證明,,4-1-74-1-,,4-1-74-1-10,格與布爾代數(shù)的性質(zhì)及判定4-2計(jì)算題主合取范式、主析取范式的求取,,1-2-41-2-,,1-2-41-2-5,2-1-2運(yùn)算的計(jì)算,關(guān)系的閉包運(yùn)算,,2-1-42-1-,,2-1-6,2-2-12-2-2,對(duì)給定函數(shù)做復(fù)合運(yùn)算,求逆運(yùn)算,對(duì)給定置換函數(shù)做復(fù)合運(yùn)算、求逆運(yùn)算等2-3-2結(jié)點(diǎn)的度數(shù)、連通分支、通路數(shù)目等;樹(shù)(回)路、漢密爾頓通(回)路、匹配方第三部分圖論代數(shù)系統(tǒng)中特殊元(幺元、逆元、零元、,4-1-34-1-6,循環(huán)群的生成元、有限群的子群、元素,,4-1-64-1-,,4-1-8-5-考試點(diǎn)()名師精品課程電話(huà):400-6885-365題型考核點(diǎn)涉及章節(jié)備注綜合應(yīng)用題數(shù)理邏輯中,給出命題的自然語(yǔ)言描述,要求進(jìn)行符號(hào)化,然后進(jìn)行結(jié)論的有效性證明第一部分?jǐn)?shù)理邏輯二元關(guān)系中基于集合劃分與等價(jià)關(guān)系的計(jì)算等價(jià)類(lèi)或者商集的的綜合應(yīng)用第二部集合與關(guān)系結(jié)合具體的應(yīng)用場(chǎng)景,運(yùn)用圖論中各種定理和判定方法的綜合應(yīng)用題第三部分圖論網(wǎng)絡(luò)環(huán)境下構(gòu)造組化中哈夫曼編碼的應(yīng)用等基于群論里面的陪集、拉格朗日定理、正規(guī)子群、商群的綜合應(yīng)用題第四部分代數(shù)系統(tǒng)結(jié)合具體背景,采用格或者布爾代數(shù)進(jìn)行求解的綜合應(yīng)用題第四部分代數(shù)系統(tǒng)信息安全中的訪(fǎng)問(wèn)電路設(shè)計(jì)等如何復(fù)習(xí):1.強(qiáng)化概念定義的理解。離散數(shù)學(xué)是建立在大量概念之上的邏輯推理學(xué)科,概念的理解是我們學(xué)習(xí)這門(mén)學(xué)科的核心。掌握、理解和運(yùn)用這些概念和定理是復(fù)習(xí)好這門(mén)課的關(guān)鍵。要特別注意概念之間的聯(lián)系,而描述這些聯(lián)系的則是定理和性質(zhì)。2.善于歸納解題的方法。離散數(shù)學(xué)的證明題多,不同的題型會(huì)需要不同的證明方法(如直接證明法、反證法、歸納法、構(gòu)造性證明法),同一個(gè)題也可能有幾種方法。但是《離散數(shù)學(xué)》證明題的方法性是很強(qiáng)的,如果拿到一道題,立即能夠看出它所屬的類(lèi)型及關(guān)聯(lián)的知識(shí)點(diǎn),就不難選用正確的方法將其解決,反之則事倍功半。由此可見(jiàn),在平常學(xué)習(xí)中,要善于總結(jié)和歸納,仔細(xì)體會(huì)題目類(lèi)型和此類(lèi)題目的解題套路。3.及時(shí)補(bǔ)充應(yīng)用的背景。離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)。也稱(chēng)為計(jì)算機(jī)數(shù)學(xué)。因而補(bǔ)充離散數(shù)學(xué)應(yīng)用的相關(guān)背景知識(shí),對(duì)考題中的綜合應(yīng)用題的求解會(huì)有很大的幫助。-6-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路第一章命題邏輯1.命題的概念、表示、分類(lèi);五種基本聯(lián)結(jié)詞的邏輯意義。2.命題公式的遞歸定義,自然語(yǔ)言翻譯成命題公式3.真值表的構(gòu)造、命題公式等價(jià)的概念。4.重言式與蘊(yùn)涵式的定義、邏輯意義,邏輯等價(jià)與邏輯蘊(yùn)涵的意義和證明方法。常用的邏輯等價(jià)公式和邏輯蘊(yùn)涵公式。的方法,公式類(lèi)型與主范式之間的關(guān)系。6.命題邏輯的推理理論,主要的推理方法:真值表法、直接證明法、間接證明法。常用推理規(guī)則:P知識(shí)點(diǎn)1命題與命題聯(lián)結(jié)詞命題定義:具具有確切真值的陳述句稱(chēng)為命題真值只有"真"和"假"兩種"T"(或"1")和"F"(或"0")表示。注意:一切沒(méi)有判斷內(nèi)容的句子都不能作為命題,如命令句、感嘆句、疑問(wèn)句、祈使句、二義性的陳命題一定是陳述句,但并非一切陳述句都是命題。 命題的真值有時(shí)可明確給出,有時(shí)還需要依靠環(huán)境、條件、實(shí)際情況時(shí)間才能確定其真值。一般來(lái)說(shuō),命題可分兩種類(lèi)型:1)原子命題(簡(jiǎn)單命題):不能再分解為更為簡(jiǎn)單命題的命題。2)復(fù)合命題:可以分解為更為簡(jiǎn)單命題的命題。而且這些簡(jiǎn)單命題之間是通過(guò)如"或者"、"并且"、"不"、"如果……則……"、"當(dāng)且僅當(dāng)"等這樣的關(guān)聯(lián)詞和標(biāo)點(diǎn)符號(hào)復(fù)合而構(gòu)成一個(gè)復(fù)合命題。五個(gè)基本聯(lián)結(jié)詞聯(lián)結(jié)詞A既……又……、不僅……而且……、雖然……但是……、并且、和、與,等等→◆Ⅴ相容(可兼)的或-7-考試點(diǎn)()名師精品課程電話(huà):400-6885-365注意:①聯(lián)結(jié)詞是句子與句子之間的聯(lián)結(jié),而非單純的名詞、形容詞、數(shù)詞等地聯(lián)結(jié);②聯(lián)結(jié)詞是兩個(gè)句子真值之間的聯(lián)結(jié),而非句子的具體含義的聯(lián)結(jié),兩個(gè)句子之間可以無(wú)任何地內(nèi)在聯(lián)系;③聯(lián)結(jié)詞與自然語(yǔ)言之間的對(duì)應(yīng)并非一一對(duì)應(yīng);④弄清楚蘊(yùn)涵式P→Q的邏輯關(guān)系及其真值,這里Q是P的必要條件。無(wú)論蘊(yùn)涵關(guān)系如何表述,都要仔細(xì)地區(qū)分出蘊(yùn)涵式的前件和后件。例"→"的理解設(shè)P:雪是白色的;Q:2+2=4。將下列命題符號(hào)化:(1)因?yàn)檠┦前咨?所以2+2=4;P→Q(2)如果2+2=4,則雪是白色的;Q→P(3)只有雪是白色的,才有2+2=4;Q→P(4)只有2+2=4,雪才是白色的;P→Q(5)只要雪不是白色的,就有2+2=4;IP→Q(6)除非雪是白色的,否則2+2≠4;IP→IQ或Q→P(7)雪是白色的當(dāng)且僅當(dāng)2+2=4;P◆Q例設(shè)命題P:明天上午七點(diǎn)下雨;Q:明天上午七點(diǎn)下雪;R:我將去學(xué)校。符號(hào)化下述語(yǔ)句:(1)如果明天上午七點(diǎn)不是雨夾雪,則我將去學(xué)校(2)如果明天上午七點(diǎn)不下雨并且不下雪,則我將去學(xué)校(3)如果明天上午七點(diǎn)下雨或下雪,則我將不去學(xué)校(4)明天上午我將雨雪無(wú)阻一定去學(xué)校解:解(1)可符號(hào)化為:I(PAQ)→R。(2)可符號(hào)化為:(IPAIQ)→R。(3)可符號(hào)化為:(PⅤQ)→IR。(4)可符號(hào)化為:(PAQAR)Ⅴ(IPAQAR)Ⅴ(PAIQAR)Ⅴ(IPAIQAR)?；?(PAQ)Ⅴ(IPAQ)Ⅴ(PAIQ)Ⅴ(IPAIQ))AR。式、解釋與真值表定義:一個(gè)特定的命題是一個(gè)常值命題,它不是具有值"T"("1"),就是具有值"F"("0")。-8-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路而一個(gè)任意的沒(méi)有賦予具體內(nèi)容的原子命題是一個(gè)變量命題,常稱(chēng)它為命題變量(或命題變?cè)?,該命題變量無(wú)具體的真值,它的變域是集合|T,F|(或|0,1|)注意:(1)復(fù)合命題為命題變?cè)?函數(shù)"(真值函數(shù)),其函數(shù)值仍為"真"或"假"值。((2)真值函數(shù)或命題公式,沒(méi)有確切真值。命題公式的遞歸定義2.如G是公式,則(IG)也是公式;3.如G,H是公式,則(GAH)、(GⅤH)、(G→H)、(G◆H)也是公式;公式的解釋與真值表真值稱(chēng)為G的一個(gè)解釋。如果公式G在解釋I下是真的,則稱(chēng)I滿(mǎn)足G;如果G在解釋I下是假的,則IG。一般來(lái)說(shuō),若有n個(gè)命題變?cè)?則應(yīng)有2n個(gè)不同的解釋。定義:將公式G在其所有可能解釋下的真值情況列成的表,稱(chēng)為G的真值表。例下面這組公式的真值表:1001001001101.公式G稱(chēng)為永真公式(重言式),如果在它的所有解釋之下都為"真"。2.公式G稱(chēng)為永假公式(矛盾式),如果在它的所有解釋之下都為"假"。3.公式G稱(chēng)為可滿(mǎn)足的,如果它不是永假的。知識(shí)點(diǎn)3十六個(gè)基毒等價(jià)公式設(shè)G,H,S是任何的公式,則:2)E3:GⅤH=HⅤGE4:GAH=HAG(交換律)-9-考試點(diǎn)()名師精品課程電話(huà):400-6885-3653)E5:GⅤ(HⅤS)=(GⅤH)ⅤSE6:GA(HAS)=(GAH)AS(結(jié)合律)4)E7:GⅤ(GAH)=GE8:GA(GⅤH)=G(吸收律)5)E9:GⅤ(HAS)=(GⅤH)A(GⅤS)E10:GA(HⅤS)=(GAH)Ⅴ(GAS)(分配律)6)E11:GⅤ0=GE12:GA1=G(同一律)EGE14:GA0=0(零律)8)E15:GⅤIG=1(排中律)9)E16:GAIG=0(矛盾律)10)E17:I(IG)=G(雙重否定律)11)E18:I(GⅤH)=IGAIH(DeMorGan定律)E19:I(GAH)=IGⅤIH12)E20:(G◆H)=(G→H)A(H→G)(等價(jià))13)E21:(G→H)=(IGⅤH)(蘊(yùn)涵)14)E22:G→H=IH→IG(假言易位)15)E23:G◆H=IG◆IH。(等價(jià)否定等式)16)E24:(G→(H)A(G→IH)=IG(歸謬論)知識(shí)點(diǎn)4范式析取范式和合取范式((1)命題變?cè)蛎}變?cè)姆穸ǚQ(chēng)為文字(2)有限個(gè)文字的析取稱(chēng)為析取式(也稱(chēng)為子句)(3)有限個(gè)文字的合取稱(chēng)為合取式(也稱(chēng)為短語(yǔ))(4)P與IP稱(chēng)為互補(bǔ)對(duì)。有限個(gè)合取式的析取式稱(chēng)為析取范式有限個(gè)析取式的合取式稱(chēng)為合取范式范式的求解方范式的求解方法轉(zhuǎn)換方法:(1)利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的→、◆用聯(lián)結(jié)詞I、A、Ⅴ來(lái)取代,這可利用如下等價(jià)關(guān)系:(G→H)=(IGⅤH);(G◆H)=(G→H)A(H→G)=(IGⅤH)A(IHⅤG)。(2)重復(fù)使用德!摩根定律將否定號(hào)移到各個(gè)命題變?cè)那岸?并消去多余的否定號(hào),這可利用如下等價(jià)關(guān)系:I(IG)=G;I(GⅤH)=IGAIH;I(GAH)=IGⅤIH。-10-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路(3)重復(fù)利用分配律,可將公式化成一些合取式的析取,或化成一些析取式的合取,這可利用如下等價(jià)關(guān)系:GⅤ(HAS)=(GⅤH)A(GⅤS);GA(HⅤS)=(GAH)Ⅴ(GAS)。 極小項(xiàng)和極大項(xiàng)定義:n個(gè)命題變?cè)狿1、P2、P3、…、Pn的短語(yǔ)或子句中,若每個(gè)命題變?cè)c其否定不同時(shí)存在,但短語(yǔ)或子句為關(guān)于P1、P2、P3、…、Pn的一個(gè)極小項(xiàng)或極大項(xiàng)。對(duì)于n個(gè)命題變?cè)?可構(gòu)成2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)例三個(gè)命題變?cè)臉O小項(xiàng)和極大項(xiàng)POR極小項(xiàng)極大項(xiàng)000m0=IPAIOAIRMPⅤOⅤR001m1=IPAIOARM1=PⅤOⅤIR010m2=IPAOAIRM2=PⅤIOⅤR011m3=IPAOARM3=PⅤIOⅤIR100m4=PAIOAIRM4=IPⅤOⅤR101m5=PAIOARM5=IPⅤOⅤIR110m6=PAOAIRM6=IPⅤIOⅤR111m7=PAOARM7=IPⅤIOⅤIR極小項(xiàng)和極大項(xiàng)的性質(zhì):任任意兩個(gè)極小項(xiàng)的合取必為假;miAmj=0任意兩個(gè)極大項(xiàng)的析取必為真;MiⅤMj=1極大項(xiàng)的否定是極小項(xiàng);IMi=mi極小項(xiàng)的否定是極大項(xiàng);Mi=Imi所有極小項(xiàng)的析取為永真公式;所有極大項(xiàng)的合取是永假公式。2n-1Ⅴmi=1i=02n-1AMi=0i=0主析取范式和主合取范式:(1)在給定的析取范式中,每一個(gè)合取式都是極小項(xiàng),則稱(chēng)該范式為主析取范式(2)在給定的合取范式中,每一個(gè)析取式都是極大項(xiàng),則稱(chēng)該范式為主合取范式(3)如果一個(gè)主析取范式不包含任何極小項(xiàng),則稱(chēng)該主析取范式為"空";如果一個(gè)主合取范式不包含任何極大項(xiàng),則稱(chēng)主合取范式為"空"。求主析取范式和主合取范式的方法-11-考試點(diǎn)()名師精品課程電話(huà):400-6885-365需要說(shuō)明:求任何一個(gè)公式的主析取范式和主合取范式不僅要取決于該公式,而且取決于該公式所包含的命題變?cè)?。如公?G1=(P→O)AO,G2(P,O,R)=(P→O)AO。前者是依賴(lài)于兩個(gè)命題變?cè)?后者應(yīng)依賴(lài)于三個(gè)命題變?cè)?。知識(shí)點(diǎn)5命題邏精的推理理論推理的基本概念:設(shè)G,H是公式,對(duì)任意解釋I,如果I滿(mǎn)足G,那么I滿(mǎn)足H,則稱(chēng)H是G的邏輯結(jié)果(或稱(chēng)G蘊(yùn)涵H),記為G→H,此時(shí)稱(chēng)G為前提,H為結(jié)論。推廣:設(shè)G1,G2,…,Gn,H是公式,稱(chēng)H是G1,G2,…,Gn的邏輯結(jié)果(G1,G2,…,Gn共同蘊(yùn)涵H),當(dāng)且僅當(dāng)(G1AG2A…AGn)→H為永真式,記為G1,G2,…,Gn→H,稱(chēng)G1,G2,…,Gn稱(chēng)為一組前提,用集合I來(lái)表示,記I=|G1,G2,…,Gn|。H稱(chēng)為結(jié)論,則可簡(jiǎn)記記為I→H推理定律:設(shè)G,H,I,J是任意的命題公式,則有:1)I1:GAH→GI2:GAH→H(簡(jiǎn)化規(guī)則)2)I3:G→GⅤHI4:H→GⅤH(添加規(guī)則)3)I5:IG→G→HI6:H→G→H4)I7:I(G→H)→GI8:I(G→H)→IH5)I9:G,H→GAH6)I10:IG,GⅤH→HI11:IG,GH→H(選言三段論)7)I12:G,G→H→H(分離規(guī)則)8)I13:IH,G→H→IG(否定后件式)9)I14:G→H,H→I→G→I(假言三段論)10)I15:GⅤH,G→I,H→I→I(二難推論)推理規(guī)則:①規(guī)則P(稱(chēng)為前提引用規(guī)則):在推導(dǎo)的過(guò)程中,可隨時(shí)引人前提集合中的任意一個(gè)前提;②規(guī)則T(邏輯結(jié)果引用規(guī)則):在推導(dǎo)的過(guò)程中,可以隨時(shí)引人公式S,該公式S是由其前的一個(gè)-12-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路或多個(gè)公式推導(dǎo)出來(lái)的邏輯結(jié)果。③規(guī)則CP(附加前提規(guī)則):如果能從給定的前提集合I與公式P推導(dǎo)出S,則能從此前提集合I推導(dǎo)出P→S。推理方法:①真值表法:采用真值表②基本等價(jià)公式:即判斷(G1AG2A…AGm)→C是否為重言式。③主析取范式法:即判斷(G1AG2A…AGm)→C是否為所有極小項(xiàng)的析取。④直接證明法:由前提出發(fā),利用已知等價(jià)式、重言蘊(yùn)涵式及有關(guān)推理規(guī)則推出結(jié)論,主要應(yīng)用P和T規(guī)則。⑤CP規(guī)則證明法:即欲證(G1AG2A…AGm)→(B→C),只要證(G1AG2A…AGm→B)→C⑥反證法:將結(jié)論的否定式作為前提,然后推理出矛盾式命題邏輯推理的難點(diǎn):1.弄清楚蘊(yùn)涵式P→O的邏輯關(guān)系及其真值,這里O是P的必要條件。無(wú)論蘊(yùn)涵關(guān)系如何表述,都要仔細(xì)地區(qū)分出蘊(yùn)涵式的前件和后件。2.推理過(guò)程中推理規(guī)則、基本等值式和邏輯蘊(yùn)涵式的引用要適當(dāng),邏輯思維要清晰。3.弄清楚幾種推理方法的區(qū)別與聯(lián)系,對(duì)于命題邏輯推理而言,針對(duì)不同的問(wèn)題選用不同的推理方法。一般而言,對(duì)于結(jié)論是蘊(yùn)涵式或析取式的,大多可以采取帶CP規(guī)則的直接證明方法。1.命題"如果1+2=5,則雪是黑的"的真值為。1.設(shè)P:我去上街,O:天在下雨.命題"我去上街,除非天在下雨"符號(hào)化為()A.P→IOB.IO→PC.P→OD.P◆O(p→q)A(q→r)的主合取范式與主析取范式。四、符號(hào)化下述語(yǔ)句,并進(jìn)行推理證明。"如果馬會(huì)飛或羊吃草,則母雞就會(huì)是飛鳥(niǎo);如果母雞是飛鳥(niǎo),那么烤熟的鴨子還會(huì)跑;烤熟的鴨子不會(huì)跑。所以羊不吃草。"分析:令P:馬會(huì)飛;O:羊吃草;R:母雞是飛鳥(niǎo);S:烤熟的鴨子還會(huì)跑。符號(hào)化上述語(yǔ)句為:I=|PⅤO→R,R→S,IS|,G=IO。-13-考試點(diǎn)()名師精品課程電話(huà):400-6885-365證明I→G。本講主要講解了命題與聯(lián)結(jié)詞、命題公式與真值表、十六個(gè)基本等價(jià)公式、范式及其主范式的求解方法以及推理理論的基本概念;重點(diǎn)講解了命題符號(hào)化以及推理方法、主范式的求解過(guò)程;應(yīng)試方法主要是熟記并深刻理解上述知識(shí)點(diǎn)的概念,并在習(xí)題演練中歸納解題方法。-14-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路第二章謂詞邏輯1.謂詞的概念與表示方法,量詞、個(gè)體域和個(gè)體的概念2.謂詞邏輯的合式公式與自然語(yǔ)言的翻譯4.謂詞邏輯的等價(jià)式和蘊(yùn)含式5.前束范式的概念及求解方法知識(shí)點(diǎn)1謂詞邏精中的基毒概舍與表示1.謂詞的概念與表示在謂詞邏輯中,原子命題分解成個(gè)體詞和謂詞.·個(gè)體詞是可以獨(dú)立存在的客體,它可以是具體事物或抽象的概念個(gè)體詞分個(gè)體常量(用a,b,c,…表示)和個(gè)體變量(用x,y,z,…表示);·謂詞是用來(lái)刻劃個(gè)體詞的性質(zhì)或事物之間關(guān)系的詞.含n個(gè)個(gè)體詞的謂詞稱(chēng)n元謂詞。2.命題函數(shù)與量詞·(簡(jiǎn)單)命題函數(shù)即"謂詞(若干客體變項(xiàng))"?！?fù)合命題函數(shù)·量詞量詞有兩類(lèi):(1)全稱(chēng)量詞(V),表示"所有的"或"每一個(gè)";(2)存在量詞(3),表示"存在某個(gè)"或"至少有一個(gè)".在謂詞邏輯中,使用量詞應(yīng)注意以下幾點(diǎn):①在不同個(gè)體域中,命題符號(hào)化的形式可能不同,命題的真值也可能會(huì)改變.②在考慮命題符號(hào)化時(shí),如果對(duì)個(gè)體域未作說(shuō)明,一律使用全總個(gè)體域.-15-考試點(diǎn)()名師精品課程電話(huà):400-6885-365應(yīng)個(gè)體域的特性謂詞作為合取式之合取項(xiàng)加人應(yīng)個(gè)體域的特性謂詞作為合取式之合取項(xiàng)加人③多個(gè)量詞出現(xiàn)時(shí),不能隨意顛倒它們的順序,否則可能會(huì)改變命題的含義.④在謂詞邏輯中,命題符號(hào)化必須明確個(gè)體域,無(wú)特別說(shuō)明認(rèn)為是全總個(gè)體域。一般地,對(duì)于全稱(chēng)稱(chēng)量詞(Vx),刻劃其對(duì)應(yīng)個(gè)體域的特性謂詞作為蘊(yùn)涵式之前件加人,對(duì)于存在量詞(3x),刻劃其對(duì)例用謂詞邏輯符號(hào)化下述語(yǔ)句:(1)天下烏鴉一般黑;(2)在美國(guó)留學(xué)的學(xué)生未必都是亞洲人;(3)每個(gè)實(shí)數(shù)都存在比它大的另外的實(shí)數(shù);(4)盡管有人很聰明,但未必一切人都聰明;解:(1)天下烏鴉一般黑設(shè)F(x):x是烏鴉;G(x,y):x與y一般黑,則:(Vx)(Vy)(F(x)AF(y)→G(x,y))或者I(3x)(3y)(F(x)AF(y)AIG(x,y));(2)在美國(guó)留學(xué)的學(xué)生未必都是亞洲人設(shè)A(x):x是亞洲人;H(x):x是在美國(guó)留學(xué)的學(xué)生,則:I(Vx)(H(x)→A(x))或者(3x)(H(x)AIA(x));(3)每個(gè)實(shí)數(shù)都存在比它大的另外的實(shí)數(shù)設(shè)R(x):x是實(shí)數(shù);L(x,y):x小于y,則:(Vx)(R(x)→(3y)(R(y)AL(x,y))(4)盡管有人很聰明,但未必一切人都聰明設(shè)M(x):x是人;C(x):x很聰明,則:(3x)(M(x)AC(x))AI(Vx)(M(x)→C(x))知識(shí)點(diǎn)2謂詞公式與解釋、變?cè)臑槭?.謂詞公式與解釋·原子公式若P(x1,x2,…,xn)是n元謂詞,t1,t2,…,tn是項(xiàng),則稱(chēng)P(t1,t2,…,tn)為原子謂詞公式,簡(jiǎn)稱(chēng)原子公式;·謂詞公式滿(mǎn)足下列條件的表達(dá)式,稱(chēng)為合式公式,簡(jiǎn)稱(chēng)公式。①原子公式是合式公式;②若G,H是合式公式,則(IG)、(IH)、(GⅤH),(GAH)、(G→H)、(G◆H)也是合式公式;③若G是合式公式,x是個(gè)體變量,則(Vx)G、(3x)G也是合式公式;④僅僅由①-③產(chǎn)生的表達(dá)式才是合式公式。-16-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路·解釋謂詞邏輯中公式G的每一個(gè)解釋I(Expl-anation)由如下四部分組成:(1)非空的個(gè)體域集合D;(2)G中的每個(gè)常量符號(hào),指定D中的某個(gè)特定的元素;(3)G中的每個(gè)n元函數(shù)符號(hào),指定Dn到D中的某個(gè)特定的函數(shù)(4)G中的每個(gè)n元謂詞符號(hào),指定Dn到|0,1|中的某個(gè)特定的謂詞。注意:當(dāng)個(gè)體域D=|x0,x1,…xn|是有限集合時(shí)(Vx)G(x)=G(x0)AG(x1)A…AG(xn)(3x)G(x)=G(x0)ⅤG(x1)Ⅴ…ⅤG(xn)·謂詞公式分類(lèi)(1)公式G稱(chēng)為有效公式如果G在它所有的解釋I下都取值為"真";(2)公式G稱(chēng)為矛盾公式如果G在它所有的解釋I下都取值為"假"。(3)公式G稱(chēng)為可滿(mǎn)足公式如果至少有一種解釋I使得G取值為"真"。2.變?cè)募s束·變?cè)c轄域給定一個(gè)合適公式G,若變?cè)獂出現(xiàn)在使用變?cè)牧吭~的轄域之內(nèi),則稱(chēng)變?cè)獂的出現(xiàn)為約束出現(xiàn),此時(shí)的變?cè)獂稱(chēng)為約束變?cè)?。若x的出現(xiàn)不是約束出現(xiàn),則稱(chēng)它為自由出現(xiàn),此時(shí)的變?cè)獂稱(chēng)為自量詞轄域的確定方法:(1)若量詞后有括號(hào),則括號(hào)內(nèi)的子公式就是該量詞的轄域;(2)若量詞后無(wú)括號(hào),則與量詞鄰接的子公式為該量詞的轄域?！ぜs束變?cè)膿Q名規(guī)則 就是把公式中量詞的指導(dǎo)變?cè)捌漭犛蛑械脑撟冊(cè)獡Q成該公式中沒(méi)有出現(xiàn)的個(gè)體變?cè)?公式的 其余部分不變。·自由變?cè)拇艘?guī)則就是把公式中的某一自由變?cè)?用該公式中沒(méi)有出現(xiàn)的個(gè)體變?cè)?hào)替代,且要把該公式中所有的該自由變?cè)紦Q成新引人的這個(gè)符號(hào).知識(shí)點(diǎn)3謂詞演算的基毒等價(jià)式、常束范式1.謂詞演算的基本等價(jià)式與蘊(yùn)含式十二個(gè)等價(jià)式-17-考試點(diǎn)()名師精品課程電話(huà):400-6885-365(1)E25:(3x)G(x)=(3y)G(y);E26:(Vx)G(x)=(Vy)G(y);---(改名規(guī)則)(2)E27:I(3x)G(x)=(Vx)IG(x);E28:I(Vx)G(x)=(3x)IG(x);---(量詞轉(zhuǎn)換律/量詞否定等值式)(3)E29:(Vx)(G(x)ⅤS)=(Vx)G(x)ⅤS;E30:(Vx)(G(x)AS)=(Vx)G(x)AS;E31:(3x)(G(x)ⅤS)=(3x)G(x)ⅤS;E32:(3x)(G(x)AS)=(3x)G(x)AS;---(量詞轄域的擴(kuò)張與收律)(4)E33:(Vx)(G(x)AH(x))=(Vx)G(x)A(Vx)H(x);E34:(3x)(G(x)ⅤH(x))=(3x)G(x)ⅤH(x);---(量詞分配律)(5)E35:(Vx)G(x)Ⅴ(Vx)H(x)=(Vx)(Vy)(G(x)ⅤH(y));E36:(3x)G(x)A(3x)H(x)=(3x)(3y)(G(x)AH(y));2.前束范式·前束范式稱(chēng)公式G是一個(gè)前束范式,如果G中的一切量詞都位于該公式的最前端(不含否定詞)且這些量詞的轄域都延伸到公式的末端。其標(biāo)準(zhǔn)形式如下:(O1x1)(O2x2)…(Onxn)M(x1,x2,…,xn)其中Oi為量詞"V"或"3"(i=1,…,n),M稱(chēng)作公式G的母式(基式),M中不再有量詞?！ぶ^詞公式①消去聯(lián)結(jié)詞→、◆;②將聯(lián)結(jié)詞I移至原子謂詞公式之前;③利用換名或代人規(guī)則使所有約束變?cè)姆?hào)均不同,并且自由變?cè)c約束變?cè)姆?hào)也不同;④將Vx,3x移至整個(gè)公式最左邊;⑤得到公式的前束范式例求I((Vx)(3y)P(a,x,y)→(3x)(I(Vy)O(y,b)→R(x)))的前束范式。解:(1)消去聯(lián)結(jié)詞"◆",得:I(I(Vx)(3y)P(a,x,y)Ⅴ(3x)(II(Vy)O(y,b)ⅤR(x)))(2)I內(nèi)移,得:(Vx)(3y)P(a,x,y)AI(3x)((Vy)O(y,b)ⅤR(x))=(Vx)(3y)P(a,x,y)A(Vx)((3y)IO(y,b)AIR(x))-18-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路(3)量詞左移,得:(Vx)((3y)P(a,x,y)A(3y)IO(y,b)AIR(x))=(Vx)((3y)P(a,x,y)A(3z)IO(z,b)AIR(x))=(Vx)(3y)(3z)(P(a,x,y)AIO(z,b)AIR(x))=(Vx)(3y)(3z)S(a,b,x,y,z)即:(Vx)(3y)(3z)S(a,b,x,y,z)為原式的前束范式,這里S(a,b,x,y,z)是原公式的母式。知識(shí)點(diǎn)4謂詞邏精的推理理論謂詞演算的推理是命題演算推理的推廣和擴(kuò)充,命題演算中的基本等價(jià)公式,重言蘊(yùn)含式以及,,PTCP,,1.謂詞邏輯的推理定律(1)I16:(Vx)G(x)→(3x)G(x);(2)I17:(Vx)G(x)Ⅴ(Vx)H(x)→(Vx)(G(x)ⅤH(x));I18:(3x)(G(x)AH(x))→(3x)G(x)A(3x)H(x);(3)I19:(Vx)(G(x)→H(x))→(Vx)G(x)→(Vx)H(x);I20:(Vx)(G(x)→H(x))→(3x)G(x)→(3x)H(x);(4)I21:(3x)(Vy)G(x,y)→(Vy)(3x)G(x,y);I22:(Vx)(Vy)G(x,y)→(3y)(x)G(x,y);I23:(Vy)(Vx)G(x,y)→(3x)(Vy)G(x,y);I24:(3y)(Vx)G(x,y)→(Vx)(3y)G(x,y);I25:(Vx)(3y)G(x,y)→(3y)(3x)G(x,y);I26:(Vy)(3x)G(x,y)→(3x)(3y)G(x,y)。2.謂詞邏輯的推理規(guī)則①US(全稱(chēng)特指規(guī)則,UniversalSPecify):(Vx)G(x)→G(y)其中G(x)對(duì)y是自由的—→在G(x)中,x不出現(xiàn)在量詞(Vy)或(3y)的轄域之內(nèi)。推廣:(Vx)G(x)→G(c)其中c為任意個(gè)體常量②ES(存在特指規(guī)則,ExistentialSPecify):(3x)G(x)→G(c)其中c為使G(c)為真的特定個(gè)體常量;若G(x)中還有除x以外的自由變量時(shí),則必須用這些變量的函數(shù)符號(hào)來(lái)取代。UG推廣規(guī)則,UniversalGeneralize):G(y)→(Vx)G(x)其中G(y)對(duì)x是自由的且G(y)中無(wú)自由變量x-19-考試點(diǎn)()名師精品課程電話(huà):400-6885-365④EG(存在推廣規(guī)則,ExistentialGeneralize):其中G(c)對(duì)x是自由的且G(c)中無(wú)自由變量x推廣:G(y)→(3x)G(x)其中G(y)對(duì)x是自由的且G(y)中無(wú)自由變量x3.謂詞演算的綜合推理步驟①推導(dǎo)過(guò)程中可以引用命題演算中的規(guī)則P和規(guī)則T。②如果結(jié)論是以蘊(yùn)涵形式(或析取形式)給出,可以使用規(guī)則CP。③若需消去量詞,可以引用規(guī)則US和規(guī)則ES。④當(dāng)所要求的結(jié)論可能被定量時(shí),此時(shí)可引用規(guī)則UG和規(guī)則EG將其量詞加人。⑤證明時(shí)可采用如命題演算中的直接證明方法和間接證明方法。⑥在推導(dǎo)過(guò)程中,對(duì)消去量詞的公式或公式中不含量詞的子公式,完全可以引用命題演算中的基本等價(jià)公式和基本蘊(yùn)涵公式。⑦在推導(dǎo)過(guò)程中,對(duì)含有量詞的公式可以引用謂詞中的基本等價(jià)公式和基本蘊(yùn)涵公式。例:對(duì)下述語(yǔ)句進(jìn)行符號(hào)化,并進(jìn)行推理"每個(gè)喜歡步行的人都不喜歡坐汽車(chē);每個(gè)人或者喜歡坐汽車(chē)或者喜歡騎自行車(chē);有的人不喜歡騎自行車(chē)。因而有的人不喜歡步行"。設(shè):H(x):x是人;P(x):x喜歡坐汽車(chē);O(x):x喜歡騎自行車(chē);R(x):x喜歡步行。則上述語(yǔ)句可符號(hào)化為:(Vx)(H(x)AR(x)→IP(x)),(Vx)(H(x)→P(x)ⅤO(x)),(3x)(H(x)AIO(x))→(3x)(H(x)AIR(x))解:解(1)(3x)(H(x)AIO(x))P(2)H(c)AIO(c)ES,(1)(3)H(c)T,(2),I(4)IO(c)T,(2),I(5)(Vx)(H(x)→P(x)ⅤO(x))P(6)H(c)→P(c)ⅤO(c)US,(5)(7)P(c)ⅤO(c)T,(3),(6),I(8)P(c)T,(4),(7),I(9)(Vx)(H(x)AR(x)→IP(x))P(10)H(c)AR(c)→IP(c)US,(9)(11)I(H(c)AR(c))T,(8),(10),I-20-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路(12)IH(c)ⅤIR(c)T,(11),E(13)IR(c)T,(3),(12),I(14)H(c)AIR(c)T,(3),(13),I(15)(3x)(H(x)AIR(x))EG,(14)4.謂詞演算過(guò)程的難點(diǎn)①在推導(dǎo)過(guò)程中,如既要使用規(guī)則US又要使用規(guī)則ES消去公式中的量詞,而且選用的個(gè)體是同一個(gè)符號(hào),則必須先先使用規(guī)則ES,再使用規(guī)則US。然后再使用命題演算中的推理規(guī)則,最后使用規(guī)則UG或規(guī)則EG引人量詞,得到所要的結(jié)論。②如一個(gè)變量是用規(guī)則ES消去量詞,對(duì)該變量在添加量詞時(shí),則只能使用規(guī)則EG,而不能使用規(guī)則UG;如使用規(guī)則US消去量詞,對(duì)該變量在添加量詞時(shí),則可使用規(guī)則EG和規(guī)則UG。③如有兩個(gè)含有存在量詞的公式,當(dāng)用規(guī)則ES消去量詞時(shí),不能選用同樣的一個(gè)常量符號(hào)來(lái)取代兩個(gè)公式中的變?cè)?而應(yīng)用不同的常量符號(hào)來(lái)取代它們。④在用規(guī)則US和規(guī)則ES消去量詞、用規(guī)則UG和規(guī)則EG添加量詞時(shí),此量詞必須位于整個(gè)公式的最前端,并且它的轄域?yàn)槠浜蟮恼麄€(gè)公式。⑤在添加量詞(Vx)、(3x)時(shí),所選用的x不能在公式G(y)或G(c)中自由出現(xiàn)且G(y)或G(c)對(duì)x是自由的。⑥在使用規(guī)則EG引人存在量詞(3x)時(shí),此x不得僅為G(c)或G(y)中的函數(shù)變?cè)Ｔ谑褂靡?guī)則UG引人全稱(chēng)量詞(Vx)時(shí),此x不得為G(y)中的函數(shù)變?cè)?因該函數(shù)變?cè)坏米鳛樽杂勺冊(cè)?。⑦在使用規(guī)則UG引人全稱(chēng)量詞(Vx)時(shí),G(y)中不得出現(xiàn)在使用規(guī)則US引人y之后由規(guī)則ES引人的常量或函數(shù)。1.公式VxF(x)ⅤI3xG(x)的前束范式為Vx(F(x)ⅤIG(x)).()2.已知個(gè)體域?yàn)閨2,3|,如果L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,那么3yVxF(x)L(x,y)的真值為0.()二、把公式(Vx)(Vy)(3z)(P(x,z)AP(y,z)→(3u)O(x,y,u))轉(zhuǎn)化為前束范式三、符號(hào)化下述語(yǔ)句,并進(jìn)行推理證明."沒(méi)有不守信用的人是可以信賴(lài)的;有些可以信賴(lài)的人是受過(guò)教育的,因此,有些受過(guò)教育的人是"海關(guān)人員檢查每一個(gè)進(jìn)人本國(guó)的不重要人物;某些走私者進(jìn)人該國(guó)時(shí)僅僅被走私者所檢查;沒(méi)有一個(gè)走私者是重要人物;海關(guān)人員中的某些人士走私者。"提示:設(shè)個(gè)體域?yàn)槿薊(x):x進(jìn)人國(guó)境;V(x):x是重要人物;C(x):x是海關(guān)人員;P(x):x是走私者;S(x,y):y檢查x;-21-考試點(diǎn)()名師精品課程電話(huà):400-6885-365第一句話(huà):Vx(E(x)AIV(x)→3y(C(y)AS(x,y)))第二句話(huà):3x(P(x)AE(x)AVy(S(x,y)→P(y)))本講主要講解了謂詞的概念與表示、命題函數(shù)與量詞、謂詞公式與解釋、變?cè)s束、謂詞演算的基本等價(jià)式、前束范式以及謂詞推理理論;重點(diǎn)講解了自然語(yǔ)言的謂詞符號(hào)化、謂詞推理理論;應(yīng)試方法主要是熟記并深刻理解上述知識(shí)點(diǎn)的概念與定義,并在習(xí)題演練中歸納解題方法。-22-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路第三章二元關(guān)系第1講集合與關(guān)系的定義1)集合的基本概念與表示方法;2)子集與冪集,集合的運(yùn)算;3)序偶與笛卡爾積;矩陣、關(guān)系圖;知識(shí)點(diǎn)1集合的基毒概舍與表示方法:1.集合的概念由指定范圍內(nèi)的某些特定對(duì)象聚集在一起構(gòu)成。指定范圍內(nèi)的每一個(gè)對(duì)象稱(chēng)為這個(gè)集合的元素。2.集合的表示方法枚舉法A=|a,b,c,d|描述法P=|xIP(x)|例S=|xIx是整數(shù),并且x2+1=0|文氏圖法利用平面上點(diǎn)的集合作成的對(duì)集合的圖解3.集合與元素,集合與集合的關(guān)系集合與元素:a∈A或a生A兩者必居其一且僅居其一集合與集合:集合相等:A=B分A與B具有相同的元素,否則,A≠B。包含與真包含關(guān)系:BSA分對(duì)任意x,如x∈B,則x∈A-23-BSA分對(duì)任意x,如x∈B,則x∈A,并且,3y∈A,且y生B例設(shè)A=|a|是一個(gè)集合,B=||a|,||a|||,試問(wèn)|A|∈B和|A|SB同時(shí)成立嗎?解:|A|∈B和|A|SB同時(shí)成立。4.特殊集合空集:不含任何元素的集合,記作中空集是一切集合的子集空集是絕對(duì)唯一的全集:在一個(gè)相對(duì)固定的范圍內(nèi),包含此范圍內(nèi)所有元素的集合,稱(chēng)為全集或論集全集是相對(duì)唯一的有限集與無(wú)限集集合A中元素的數(shù)目稱(chēng)為集合A的基數(shù),記為IAI知識(shí)點(diǎn)23集與冪集,集合的運(yùn)算:1.子集與冪集序偶:如果一個(gè)集合A含有n個(gè)元素,則稱(chēng)集合A為n元集,稱(chēng)A的含有m個(gè)(0≤m≤n)元素一般來(lái)說(shuō),對(duì)于n元集A,它的m(0≤m≤n)元子集有C個(gè),所以不同的子集總數(shù)有冪集:設(shè)A為任意集合,把A的所有不同子集構(gòu)成的集合叫做A的冪集或論集,記為P(A)或2A。P(A)=|x|一切x∈A|,又稱(chēng)為集族。例求下列冪集(1)P(中);(2)P(|中|);(3)P(|a,|b,c||)。解:(1)P(中)=|中|;(2)P(|中|)=|中,|中||;顯然,若集合A有n個(gè)元素,則集合A共有2IAI個(gè)子集,即:IP(A)I=2IAI。2.集合的運(yùn)算并集AUB=|x|x∈A或x∈B|交集A∩B=|x|x∈A且x∈B|差集A-B=|x|x∈A且x生B|補(bǔ)集A=U-A=|x|x∈U且x生A|(A',~A,Ac)-24-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路對(duì)稱(chēng)差集A④B=|x|(x=A)且(x生B)或(x=B)且(x生A)|例在20個(gè)大學(xué)生中,有10人愛(ài)好音樂(lè),有8人愛(ài)好美術(shù),有6人既愛(ài)好音樂(lè)又愛(ài)好美術(shù)。問(wèn)不愛(ài)好音樂(lè)又不愛(ài)好美術(shù)的學(xué)生有多少個(gè)?知識(shí)點(diǎn)3序偶與笛卡爾積1.序偶與笛卡爾積序偶:由兩個(gè)元素x,y按照一定的次序組成的二元組稱(chēng)為有序偶對(duì)(序偶),記作<x,y>,其中稱(chēng)x為<x,y>的第一元素,y為<x,y>的第二元素。笛卡爾積設(shè)A,B是兩個(gè)集合,稱(chēng)集合A×B=|<x,y>|(x=A)A(y=B)|為集合A與B的笛卡爾積集合A與集合B的笛卡爾積A×B仍然是集合。序偶中的第一元素取自A,第二元素取自B。例設(shè)A=|a|,B=|b,c|,C=中,D=|1,2|,請(qǐng)分別寫(xiě)出下列笛卡兒積中的元素。(1)AxB,BxA;(2)AxC,CxA;(3)Ax(BxD),(AxB)xD。解:(1)AxB=|<a,b>,<a,c>|,BxA=|<b,a>,<c,a>|AxCCxA(3)因?yàn)锽xD=|<b,1>,<b,2>,<c,1>,<c,2>|,所以Ax(BxD)=|<a,<b,1>>,<a,<b,2>>,<a,<c,1>>,<a,<c,2>>|同理,(AxB)xD=|<<a,b>,1>,<<a,b>,2>,<<a,c>,1>,<<a,c>,2>|結(jié)論(1)笛卡兒積不滿(mǎn)足交換律;AxB中當(dāng)且僅當(dāng)A=中或者B=中;(3)笛卡兒積不滿(mǎn)足結(jié)合律;AIxIBI知識(shí)點(diǎn)4二元關(guān)系設(shè)A,B為兩個(gè)非空集合,稱(chēng)AxB的任何子集R為從A到B的二元關(guān)系,簡(jiǎn)稱(chēng)關(guān)系。如A=B,則稱(chēng)R為A上的二元關(guān)系。-25-考試點(diǎn)()名師精品課程電話(huà):400-6885-365這里,A稱(chēng)為R的前域,B稱(chēng)為R的后域。令C=|xI<x,y>∈R|SA,D=|yI<x,y>∈R|SB,稱(chēng)C為R的定義域,記為C=domR;稱(chēng)D為R的值域,記D=ranR;并稱(chēng)fIdR=DUC為R的域。當(dāng)R=中時(shí),稱(chēng)R為空關(guān)系(emptyrelation);當(dāng)R=AxB時(shí),則稱(chēng)R為全關(guān)系(TotalRelation)。設(shè)一有序?qū)?lt;x,y>:若<x,y>∈R,則記為xRy;若<x,y>生R,則記為xRy。例設(shè)A=|a,b|,B=|c,d|,試寫(xiě)出從A到B的所有不同關(guān)系。解:因?yàn)锳=|a,b|,B=|c,d|,所以AxB=|<a,c>,<a,d>,<b,c>,<b,d>|。于是AxB的所有不同子集為:0-元子集:中;1-元子集:|<a,c>|,|<a,d>|,|<b,c>|,|<b,d>|;2-元子集:|<a,c>,<a,d>|,|<a,c>,<b,c>|,|<a,c>,<b,d>|,|<a,d>,<b,d>|,|<a,d>,<b,d>|,|<b,c>,<b,d>|;3-元子集:|<a,c>,<a,d>,<b,c>|,|<a,c>,<a,d>,<b,d>|,|<a,c>,<b,c>,<b,d>|,|<a,d>,<b,c>,<b,d>|;4-元子集:|<a,c>,<a,d>,<b,c>,<b,d>|。注意:當(dāng)集合A,B都是有限集時(shí),AxB共有2IAI·IBI個(gè)不同的子集,即從A到B的不同關(guān)系共有2.關(guān)系的表示法①集合表示法(枚舉和敘述法)例如,設(shè)R上的"相等"關(guān)系為S,則有S=|<x,y>I(x,y∈R)A(x=y)|②關(guān)系圖法例如設(shè)A=|2,3,4|,B=|3,4,5,6|,則A到B之間的一種整除關(guān)系R1=|<2,4>,<2,6>,,<3,6>,<4,4>|-26-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路例如A=|1,2,3,4|,則A上的小于等于關(guān)系R2=|<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>|③關(guān)系矩陣設(shè)A=|a1,a2,…,an|,B=|b1,b2,…,bm|,R是從A到B的一個(gè)二元關(guān)系,稱(chēng)矩陣MR=(rij)nxm為關(guān)系R的關(guān)系矩陣,其中<ai,bj>∈R<ai,bj>生R(i=1,2,…,n,j=1,2,…,m)rix注意:B2.A中元素序號(hào)對(duì)應(yīng)矩陣元素的行下標(biāo)3.B中元素序號(hào)對(duì)應(yīng)矩陣元素的列下標(biāo)4.關(guān)系矩陣是0-1矩陣,稱(chēng)為布爾矩陣定義;重點(diǎn)講解了冪集的計(jì)算、二元關(guān)系;應(yīng)試方法主要是熟記并在題型演練中深化上述知識(shí)點(diǎn)的概念與定義。1.設(shè)A,B為任意集合,證明:ASB,則P(A)SP(B)。2.求從1到1000的整數(shù)中不能被5、6和8中任何一個(gè)數(shù)整除的整數(shù)個(gè)數(shù)。-27-考試點(diǎn)()名師精品課程電話(huà):400-6885-365第2講關(guān)系的性質(zhì)及運(yùn)算運(yùn)算、冪運(yùn)算2)關(guān)系的性質(zhì);3)關(guān)系的閉包運(yùn)算:r(R),s(R),t(R);知識(shí)點(diǎn)1關(guān)系的運(yùn)算1.關(guān)系的運(yùn)算設(shè)R,S都是從集合A到B的兩個(gè)關(guān)系,則:RUS=|<x,y>I(xRy)Ⅴ(xSy)|R∩S=|<x,y>I(xRy)A(xSy)|R-S=|<x,y>I(xRy)A(xSy)|R=|<x,y>I(xRy)|注意:AxB是相對(duì)于R的全集,所以有R=AxB-R,且RUR=AxB,R∩R=中。 ---R=R,SSR分RSS2.復(fù)合運(yùn)算設(shè)A,B,C是三個(gè)集合,R是從A到B的關(guān)系(R:A→B),S是從B到C的關(guān)系(S:B→C),則R與S的復(fù)合關(guān)系(合成關(guān)系)RoS是從A到C的關(guān)系,并且:RoS=|<x,z>Ix∈AAz∈CA(3y)(y∈BAxRyAySz)|運(yùn)算"o"稱(chēng)為復(fù)合運(yùn)算。1)R和S是可復(fù)合的分R的后域和S的前域完全相同;2)RoS的前域是R的前域A,后域是S的后域C;例試判斷下列關(guān)系是否是兩個(gè)關(guān)系的復(fù)合,如果是,請(qǐng)指出對(duì)應(yīng)的兩個(gè)關(guān)系。(1)"祖孫"關(guān)系;(2)"舅甥"關(guān)系;(3)"兄妹"關(guān)系。解:解(1)"祖孫"關(guān)系是"父女"關(guān)系和"母子"關(guān)系的復(fù)合;(2)"舅甥"關(guān)系是"兄妹"關(guān)系和"母子"關(guān)系的復(fù)合;(3)不是。-28-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路定理:設(shè)A、B、C和D是任意四個(gè)集合,R是從A到B的關(guān)系,S1,S2是從B到C的關(guān)系,T是從C到D的關(guān)系,則:1)Ro(S1US2)=(RoS1)U(RoS2)2)Ro(S1∩S2)(RoS1)∩(RoS2)3)(S1US2)oT=(S1oT)U(S2oT)4)(S1∩S2)oTS(S1oT)∩(S2oT)證明之。證明:對(duì)任意<b,d>∈(S1∩S2)oT,則由復(fù)合運(yùn)算知,至少存在c∈C。使得<b,c>∈(S1∩S2),T所以<b,d>∈(S1oT)∩(S2oT)即(S1∩S2)oT∈(S1oT)∩(S2oT)。3.關(guān)系的逆運(yùn)算設(shè)A,B是兩個(gè)集合,R是A到B的關(guān)系,則從B到A的關(guān)系R-1=|<b,a>I<a,b>∈R|稱(chēng)為R的逆關(guān)系,運(yùn)算"-1"稱(chēng)為逆運(yùn)算。注意:關(guān)系是一種集合,逆關(guān)系也是一種集合,因此,如果R是一種關(guān)系,則R-1和R都是關(guān)系,但R-1和R是完全不同的兩種關(guān)系,千萬(wàn)不要混淆。若RSA×B,R=A×B-RSA×B,R-1SB×A。由定義:(R-1)-1=R;中-1=中。定理:設(shè)A、B和C是任意三個(gè)集合,R,S分別是從A到B,B到C的二元關(guān)系,則證明:由"o"的定義知:則存在b∈B,使得:<a,b>∈R,<b,c>∈S,由"R-1"的定義知,<b,a>∈R-1,<c,b>∈S-1,從而有<c,a>∈S-1oR-1,即(RoS)-1SS-1oR-1。反之,任取<c,a>∈S-1oR-1,由"o"的定義知:則至少存一個(gè)b∈B,使得:<c,b>∈S-1和<b,a>∈R-1。由"R-1"的定義知,有<a,b>∈R,<b,c>∈S。a,c>∈RoS,即<c,a>∈(RoS)-1,即S-1oR-1S(RoS)-1。由集合的定義知:(RoS)-1=S-1oR-1。定理:設(shè)R,S是從集合A到集合B的關(guān)系,則有(RUS)-1=R-1US-1;(分配性)-29-考試點(diǎn)()名師精品課程電話(huà):400-6885-365(R∩S)-1=R-1∩S-1;(R-S)-1=R-1-S-1;(R)-1=(R-1);(可換性)(AxB)-1=(BxA);SSR分S-1SR-1;(單調(diào)性)3.關(guān)系的冪運(yùn)算設(shè)R是集合A上的關(guān)系,則R的n次冪,記為Rn,定義如下:R0=IA=|<a,a>Ia∈A|;R1=R;由于關(guān)系的復(fù)合運(yùn)算滿(mǎn)足結(jié)合律,Rn即為n個(gè)R的復(fù)合,也是A上的二元關(guān)系。顯然,RmoRn=Rm+n,(Rm)n=Rmn。定理:設(shè)A是有限集合,且IAI=n,R是A上的二元關(guān)系,則:nURi=URii=1i=1①冪集Rn的基數(shù)IRnI并非隨著n的增加而增加,而是呈遞減趨勢(shì);A②當(dāng)n≥IAI時(shí),則RnSURii=1知識(shí)點(diǎn)2關(guān)系的性質(zhì):如無(wú)特別聲明,都是假定其前域和后域相同。即都為定義在集合A上的關(guān)系,且A是非空集合。1.自反性與反自反設(shè)R是集合A上的關(guān)系,如果對(duì)任意x∈A,都有<x,x>∈R,那么稱(chēng)R在A上是自反的(Reflex-ive),或稱(chēng)R具有自反性(Reflexivity);例如:朋友關(guān)系。如果對(duì)任意x∈A,都有<x,x>生R,那么稱(chēng)R在A上是反自反的(Antireflexive),或稱(chēng)R具有反自反性(Antireflexivity)。例如:父子關(guān)系。R在A上是自反的分(Vx)((x∈A)→(<x,x>∈R))=1R在A上是反自反的分(Vx)((x∈A)→(<x,x>生R))=1R在A上不是自反的分(=x)((x∈A)A(<x,x>生R))=1R在A上不是反自反的分(=x)((x∈A)A(<x,x>∈R))=1設(shè)A=|1,2,3|,定義A上的關(guān)系R,S和T如下:(1)R=|<1,1>,<1,2>,<2,2>,<3,3>|;(2)S=|<1,2>,<2,3>,<3,1>|;(3)T=|<1,1>,<1,2>,<1,3>,<3,1>,<3,3>|。-30-《離散數(shù)學(xué)》考點(diǎn)精講及復(fù)習(xí)思路設(shè)R,S和T的關(guān)系矩陣分別為MR,MS和MT,則:11001011MR=010MS=001MT=00001100101)關(guān)系R是自反的→R不是反自反的2)存在既不是自反的也不是反自反的關(guān)系3)關(guān)系R是自反的分關(guān)系圖中每個(gè)結(jié)點(diǎn)都有環(huán)4)關(guān)系R是反自反的分關(guān)系圖中每個(gè)結(jié)點(diǎn)都無(wú)環(huán)5)關(guān)系R是自反的分關(guān)系矩陣的主對(duì)角線(xiàn)上全為16)關(guān)系R是反自反的分關(guān)系矩陣的主對(duì)角線(xiàn)上全為02.對(duì)稱(chēng)性與反對(duì)稱(chēng)性設(shè)R是集合A上的關(guān)系,對(duì)任意x,y=A,如果<x,y>=R,那么<y,x>=R,則稱(chēng)關(guān)系R是對(duì)稱(chēng)的(Symmetric),或稱(chēng)R具有對(duì)稱(chēng)性(Symmetry);對(duì)任意x,y=A,如果<x,y>=R且<y,x>=R,那么x=y(或者如果x≠y且<x,y>=R,那么<y,x>=R),則稱(chēng)關(guān)系R是反對(duì)稱(chēng)的(Antisymmetric),或稱(chēng)R具有反對(duì)稱(chēng)性(Antisymmetry)。R在A上是對(duì)稱(chēng)的分(Vx)(Vy)((x=A)A(y=A)A(<x,y>=R)→(<y,x>=R))=1R在A上是反對(duì)稱(chēng)的分(Vx)(Vy)((x=A)A(y=A)A(<x,y>=R)A(<y,x>=R)→(x=y))=1R在A上不是對(duì)稱(chēng)的分(3x)(3y)((x=A)A(y=A)A(<x,y>=R)A(<y,x>R)=1R在A上不是反對(duì)稱(chēng)的分(3x)(3y)((x=A)A(y=A)A(<x,y>=R)A(<y,x>=R))=1設(shè)A=|1,2,3,4|,定義A上的關(guān)系R,S,T和V如下:(1)R=|<1,1>,<1,3>,<3,1>,<4,4>|;(2)S=|<1,1>,<1,3>,<1,4>,<2,4>|;(3)T=|<1,1>,<1,2>,<1,3>,<3,1>,<1,4>|;(4)V=|<1,1>,<2,2>,<3,3>,<4,4>|設(shè)R,S和T的關(guān)系矩陣分別為MR,MS,MT和MV,則:-31-考試點(diǎn)()名師精品課程電話(huà):400-6885-365101010111111