集合论与离散数学各部分内容的关系,离散数学论文

集合论与离散数学各部分内容的关系,离散数学论文摘要：在(离散数学〕课程中,集合论绝不像外表显现的那么简单,相反地,它可谓一根主线贯穿了整个(离散数学〕课程,在该课程的数理逻辑、关系、图论、代数系统等部分均发挥着表示出工具或内容支撑的作用.在本文中,我们就集合论在(离散数学〕各部分内容中的作用进行了探寻求索,希望所得结论能引起各位(离散数学〕授课老师的重视.本文关键词语：离散数学;集合论;数理逻辑;图论;代数系统;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]郑艳梅,李建江,芦碧波,