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