集合論與離散數(shù)學(xué)各部分內(nèi)容的關(guān)系,離散數(shù)學(xué)論文

集合論與離散數(shù)學(xué)各部分內(nèi)容的關(guān)系,離散數(shù)學(xué)論文摘要：在(離散數(shù)學(xué)〕課程中,集合論絕不像外表顯現(xiàn)的那么簡(jiǎn)單,相反地,它可謂一根主線貫穿了整個(gè)(離散數(shù)學(xué)〕課程,在該課程的數(shù)理邏輯、關(guān)系、圖論、代數(shù)系統(tǒng)等部分均發(fā)揮著表示出工具或內(nèi)容支撐的作用.在本文中,我們就集合論在(離散數(shù)學(xué)〕各部分內(nèi)容中的作用進(jìn)行了探尋求索,希望所得結(jié)論能引起各位(離散數(shù)學(xué)〕授課老師的重視.本文關(guān)鍵詞語(yǔ)：離散數(shù)學(xué);集合論;數(shù)理邏輯;圖論;代數(shù)系統(tǒng);Abstract：InthemoduleofDiscreteMathematics,settheoryisbynomeansassimpleasitlookslike.Onthecontrary,Itappearsthroughoutthismoduleandplaysrolesasexpressiontoolandcontentinotherpartsofthismodulesuchasmathematicallogic,relation,graphtheory,algebraicsystemandsoon.Inthispaper,wewilldiscusstheapplicationofsettheoryinvariouschaptersofDiscreteMathematicsandconcludetheimportanceofsettheoryinlearningthismodule.WehopeitcanattracttheattentionofteachersofDiscreteMathematics.Keyword：discretemathematics;settheory;graphtheory;mathematicallogic;algebraicsystem;1、引言當(dāng)前,幾乎國(guó)內(nèi)外所有大學(xué)均將(離散數(shù)學(xué)〕作為計(jì)算機(jī)相關(guān)專業(yè)的核心課程[1].(離散數(shù)學(xué)〕教學(xué)不是簡(jiǎn)單地教授給學(xué)生(離散數(shù)學(xué)〕知識(shí),更重要的是能夠培養(yǎng)學(xué)生的數(shù)學(xué)思維能力和動(dòng)手能力[2].(離散數(shù)學(xué)〕的主要內(nèi)容包括數(shù)理邏輯、集合論、數(shù)論、抽象代數(shù)和圖論等.計(jì)算機(jī)的發(fā)展與(離散數(shù)學(xué)〕各部分均有非常密切的聯(lián)絡(luò),能夠講計(jì)算機(jī)離不開(kāi)(離散數(shù)學(xué)〕,(離散數(shù)學(xué)〕在計(jì)算機(jī)相關(guān)專業(yè)中有著十分重要的作用[3].經(jīng)過(guò)本門課程,學(xué)生學(xué)習(xí)與計(jì)算機(jī)相關(guān)的研究離散量的數(shù)學(xué)知識(shí),為后續(xù)學(xué)習(xí)專業(yè)課程打下夯實(shí)的數(shù)學(xué)基礎(chǔ).(離散數(shù)學(xué)〕的內(nèi)容,在不同教學(xué)資料中,所包含內(nèi)容不完全一致[4].比方,在左孝凌所著(離散數(shù)學(xué)〕中,共分為五個(gè)部分:數(shù)理邏輯、集合論、代數(shù)系統(tǒng)、圖論以及計(jì)算機(jī)科學(xué)中的應(yīng)用[5].在耿素云等所著(離散數(shù)學(xué)〕教學(xué)資料中,共分六部分:數(shù)理邏輯、集合論、圖論、代數(shù)構(gòu)造、組合分析初步以及形式語(yǔ)言與自動(dòng)機(jī)初步[1].固然不同教學(xué)資料各有側(cè)重,但是集合論在華而不實(shí)地位不可動(dòng)搖,均占據(jù)了大分量篇幅.集合論部分對(duì)學(xué)生而言,既熟悉又陌生,也恰是這種既有模糊認(rèn)識(shí),但又沒(méi)有能準(zhǔn)確且全面把握與集合論相關(guān)內(nèi)容的現(xiàn)實(shí)情況,導(dǎo)致學(xué)生在初學(xué)集合論時(shí),掉以輕心,沒(méi)有能準(zhǔn)確把握其相關(guān)概念,以致于在學(xué)習(xí)后續(xù)關(guān)系內(nèi)容時(shí),顯得很是吃力.不單單是學(xué)生對(duì)集合論的基礎(chǔ)知識(shí)沒(méi)有能上心,部分授課老師也沒(méi)有能重視該部分基礎(chǔ)知識(shí)的重要性,授課時(shí)串講而過(guò),只是羅列與集合相關(guān)概念,比方元素、子集、空集、全集等.繼而使得在開(kāi)講集合上的二元關(guān)系或者笛卡爾積集內(nèi)容時(shí),學(xué)生聽(tīng)得一頭霧水,似懂非懂,需要回頭復(fù)習(xí)集合論相關(guān)內(nèi)容.這種現(xiàn)在狀況與集合論在整個(gè)(離散數(shù)學(xué)〕課程中的重要地位是不符的.縱觀整個(gè)(離散數(shù)學(xué)〕課程,大家會(huì)發(fā)現(xiàn)集合論在整個(gè)課程中占據(jù)著至關(guān)重要的地位,能夠講從數(shù)理邏輯,到關(guān)系,再到圖論,最后到代數(shù)系統(tǒng),一直都有集合論的身影,只是在不同地方以不同的形式出現(xiàn).下面我們將分節(jié)逐一具體介紹集合論與各部分內(nèi)容的關(guān)系.2、集合論是表示工具2.1、數(shù)理邏輯與集合論在討論命題公式的類型時(shí),命題公式的類型與使得其值為真的集合直接關(guān)聯(lián)(見(jiàn)表1).設(shè)A為一個(gè)命題公式,若A在所有賦值下取值均為真,則稱A為永真式或重言式.從集合論的角度而言,若將所有的賦值看做一個(gè)全集E,也即便得A成真的賦值為全集,成假的賦值為空集.若A在所有賦值下取值均為假,則稱A為矛盾式或永假式.也即便得A成真的賦值為空集,成假的賦值為全集.若A至少存在一組成真賦值,則稱A是可知足式.也即便得A成真的賦值E為的一個(gè)非空子集X,成假的賦值為其補(bǔ)集.關(guān)于命題公式的類型,換個(gè)角度從主析取范式來(lái)講明.具有n個(gè)命題變?cè)暮鲜焦?共有2n個(gè)極小項(xiàng),不同的n元合式公式的主析取范式,本質(zhì)上是若干極小項(xiàng)的組合,若將所有極小項(xiàng)看做一個(gè)全集E,那么任何一個(gè)n元合式公式均由的一個(gè)子集構(gòu)成.若主析取范式包含了所有的極小項(xiàng),則是永真式;若為空則為矛盾式;若為非空子集,則為可知足式.主合取范式與集合的關(guān)系可類似講明.表1命題公式類型與集合的關(guān)系討論謂詞命題所必需的論域本質(zhì)即為集合,尤其在證明謂詞公式的等值性時(shí),該論域均被設(shè)定為有限集合,并采用羅列方式方法列出其元素.比方,在講明全稱量詞?和存在量詞?時(shí),一般設(shè)定定義域?yàn)镈={a1,a2,,an},對(duì)于任意的謂詞A(x),在該定義域下,為闡述命題公式與謂詞公式的關(guān)系時(shí),需用到如下兩個(gè)公式:xA(x)?A(a1)A(a2)A(an);(1)xA(x)?A(a1)A(a2)A(an).(2)對(duì)于論域的同樣處理方式還出如今對(duì)量詞否認(rèn)等值式、量詞轄域收縮與擴(kuò)張等值式、量詞分配等值式的證明中.2.2、圖論與集合論圖的定義離不開(kāi)集合論知識(shí).圖論中的圖是對(duì)現(xiàn)實(shí)問(wèn)題的抽象化,抽象圖包含了兩個(gè)相關(guān)聯(lián)的集合,頂點(diǎn)集和邊集.如需借助計(jì)算機(jī)處理與該圖相關(guān)的問(wèn)題,則需借助集合論工具,以集合為單位,先后提供頂點(diǎn)信息、邊信息甚至邊上的權(quán)重信息.進(jìn)一步而言,若假設(shè)G=V,E,則空?qǐng)D、零圖、平凡圖、子圖、真子圖、生成子圖等均等價(jià)于與子集相關(guān)的某種關(guān)系(見(jiàn)表2),對(duì)于圖G上的子圖G1、真子圖G2、生成子圖G3、頂點(diǎn)導(dǎo)出子圖G4、邊導(dǎo)出子圖G5間還存在如下關(guān)系:G1?G,G2?G1,G3?G1,G2G3?,G4?G1,G5?G1等.表2各類子圖與集合的關(guān)系3、集合論是討論關(guān)系的根基關(guān)系,始于集合中元素,產(chǎn)生于元素之間,本身即定義在集合之上.只要在正確理解集合、元素概念的基礎(chǔ)上,才能準(zhǔn)確地認(rèn)識(shí)關(guān)系.數(shù)字或者字母能夠作為集合的元素,但絕不僅限于此.集合的元素能夠是任何類型的事物,一個(gè)集合可以以作為另外一個(gè)集合的元素,表3所示實(shí)例充分地講明了集合的元素類型,華而不實(shí)a為{a}的元素,{{a}}為{{{a}}}的元素.從這個(gè)特殊實(shí)例出發(fā),讓學(xué)生領(lǐng)悟集合與元素的關(guān)系,以及一個(gè)集合是怎樣成為另外一個(gè)集合的元素的.表3元素實(shí)例定義在集合基礎(chǔ)之上的冪集,充分講明了集合何時(shí)為集合、何時(shí)為元素.對(duì)于任一有限集合A,子集A面對(duì)集合A時(shí)為一集合,且與A存在包含關(guān)系A(chǔ)?A,面對(duì)A的冪集P(A)時(shí),搖身一變成為一元素,與P(A)存在屬于關(guān)系A(chǔ)P(A).另外,關(guān)系和等價(jià)關(guān)系的定義也同樣闡述了同樣的內(nèi)在聯(lián)絡(luò).關(guān)系是笛卡爾積的一個(gè)子集.每一個(gè)子集代表一個(gè)關(guān)系.若為空集,則是空關(guān)系.若為全集,則為全域關(guān)系.特殊地,若考慮有限集合A上的二元關(guān)系R,則R為全域關(guān)系A(chǔ)A的一個(gè)子集(R?AA),亦為笛卡爾積AA的冪集的一個(gè)元素(RP(AA)).冪集較為恰當(dāng)?shù)爻洚?dāng)了集合與關(guān)系的橋梁.冪集產(chǎn)生于集合之上,服務(wù)于關(guān)系的定義.等價(jià)關(guān)系也存在將集合變?yōu)槠渌系脑氐墓δ?定義在集合A上的R可將集合A分為若干不相交的子集,這里的每一子集對(duì)于商集A/R而言,均為華而不實(shí)一元素.4、集合論是代數(shù)系統(tǒng)的應(yīng)用實(shí)例在代數(shù)系統(tǒng)中,集合以及集合間的運(yùn)算是以代數(shù)系統(tǒng)的一個(gè)應(yīng)用實(shí)例形式而存在的.在代數(shù)系統(tǒng)中,集合論的作用不再是表示出的工具,而是內(nèi)容的支撐,這是兩者間的獨(dú)特關(guān)系.例如,集合A的、、?運(yùn)算為冪集P(A)上的二元運(yùn)算,這些運(yùn)算均具有可交換性和可結(jié)合性質(zhì);、運(yùn)算具有冪等律、吸收律、相互可分配性質(zhì)、在冪集P(A)上均存在單位元和零元;?運(yùn)算知足消去律;P(A),,,～為代數(shù)系統(tǒng),P(A),?為可交換半群和獨(dú)異點(diǎn),P(A),,,?,～,A為布爾代數(shù)[1].5、結(jié)語(yǔ)筆者在實(shí)際教學(xué)中,經(jīng)過(guò)屢次授課(離散數(shù)學(xué)〕課程,深入體會(huì)到集合論在整個(gè)(離散數(shù)學(xué)〕課程體系中的重要作用.能夠講,集合論貫徹了整個(gè)(離散數(shù)學(xué)〕的始終.(離散數(shù)學(xué)〕各個(gè)篇章也不是所謂的是各自獨(dú)立的,而是在散亂的表象下,有著一條或多條貫徹始終的主線.也正由于集合論的重要性,才需授課老師以及學(xué)生增加對(duì)其的重視.當(dāng)然,對(duì)于授課老師而言,我們?cè)谶@里提出集合論的重要性,絕不是建議簡(jiǎn)單地直接增加該部分內(nèi)容的授課學(xué)時(shí).而是應(yīng)該一方面加深學(xué)生對(duì)集合論初步知識(shí)以及相關(guān)概念的理解和把握,另一方面,在其它部分使用到集合論知識(shí)時(shí),通過(guò)詳細(xì)內(nèi)容引導(dǎo)出集合論的詳細(xì)使用方式方法.以下為參考文獻(xiàn)[1]耿素云,屈婉玲,張立昂.離散數(shù)學(xué)[M].3版.北京:清華大學(xué)出版社,2020.[2]鄭艷梅,李建江,蘆碧波,