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

　　摘    要：　在《离散数学》课程中, 集合论绝不像表面显现的那么简单, 相反地, 它可谓一根主线贯穿了整个《离散数学》课程, 在该课程的数理逻辑、关系、图论、代数系统等部分均发挥着表达工具或内容支撑的作用.在本文中, 我们就集合论在《离散数学》各部分内容中的作用进行了探索, 希望所得结论能引起各位《离散数学》授课教师的重视.

　　关键词：　离散数学; 集合论; 数理逻辑; 图论; 代数系统;

　　Abstract：　In the module of Discrete Mathematics, set theory is by no means as simple as it looks like. On the contrary, It appears throughout this module and plays roles as expression tool and content in other parts of this module such as mathematical logic, relation, graph theory, algebraic system and so on. In this paper, we will discuss the application of set theory in various chapters of Discrete Mathematics and conclude the importance of set theory in learning this module. We hope it can attract the attention of teachers of Discrete Mathematics.

　　Keyword：　discrete mathematics; set theory; graph theory; mathematical logic; algebraic system;

　　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, G2∩G3≠?, G4?G1, G5?G1等.

　　表2 各类子图与集合的关系

　　3、 集合论是讨论关系的根基

　　关系, 始于集合中元素, 产生于元素之间, 本身即定义在集合之上.只有在正确理解集合、元素概念的基础上, 才能准确地认识关系.数字或者字母可以作为集合的元素, 但绝不仅限于此.集合的元素可以是任何类型的事物, 一个集合也可以作为另外一个集合的元素, 表3所示实例充分地说明了集合的元素类型, 其中a为{a}的元素, {{a}}为{{{a}}}的元素.从这个特殊实例出发, 让学生领悟集合与元素的关系, 以及一个集合是如何成为另外一个集合的元素的.

　　表3 元素实例

　　定义在集合基础之上的幂集, 充分说明了集合何时为集合、何时为元素.对于任一有限集合A, 子集A′面对集合A时为一集合, 且与A存在包含关系A′?A, 面对A的幂集P (A) 时, 摇身一变成为一元素, 与P (A) 存在属于关系A′∈P (A) .

　　另外, 关系和等价关系的定义也同样阐述了同样的内在联系.关系是笛卡尔积的一个子集.每一个子集代表一个关系.若为空集, 则是空关系.若为全集, 则为全域关系.特殊地, 若考虑有限集合A上的二元关系R, 则R为全域关系A×A的一个子集 (R?A×A) , 亦为笛卡尔积A×A的幂集的一个元素 (R∈P (A×A) ) .幂集较为恰当地充当了集合与关系的桥梁.幂集产生于集合之上, 服务于关系的定义.

　　等价关系也存在将集合变为其它集合的元素的功能, 定义在集合A上的R可将集合A分为若干不相交的子集, 这里的每一子集对于商集A/R而言, 均为其中一元素.

　　4、 集合论是代数系统的应用实例

　　在代数系统中, 集合以及集合间的运算是以代数系统的一个应用实例形式而存在的.在代数系统中, 集合论的作用不再是表达的工具, 而是内容的支撑, 这是两者间的独特关系.例如, 集合A的∪、∩、?运算为幂集P (A) 上的二元运算, 这些运算均具有可交换性和可结合性质;∪、∩运算具有幂等律、吸收律、互相可分配性质、在幂集P (A) 上均存在单位元和零元;?运算满足消去律;<P (A) , ∪, ∩, ～>为代数系统, <P (A) , ?>为可交换半群和独异点, <P (A) , ∪, ∩, ?, ～, A>为布尔代数[1].

　　5 、结 语

　　笔者在实际教学中, 经由多次授课《离散数学》课程, 深刻体会到集合论在整个《离散数学》课程体系中的重要作用.可以说, 集合论贯彻了整个《离散数学》的始终.《离散数学》各个篇章也不是所谓的是各自独立的, 而是在散乱的表象下, 有着一条或多条贯彻始终的主线.也正因为集合论的重要性, 才需授课教师以及学生增加对其的重视.

　　当然, 对于授课教师而言, 我们在此提出集合论的重要性, 绝不是建议简单地直接增加该部分内容的授课学时.而是应该一方面加深学生对集合论初步知识以及相关概念的理解和把握, 另一方面, 在其它部分使用到集合论知识时, 通过具体内容引导出集合论的具体使用方法.

　　参考文献

　　[1] 耿素云, 屈婉玲, 张立昂.离散数学[M].3版.北京:清华大学出版社, 2013.
　　[2] 郑艳梅, 李建江, 芦碧波, 等.不同学期的离散数学课程教法[J].计算机教育, 2016, 256 (4) :136-138.
　　[3] 陈振洲.《离散数学》教学改革探讨[J].现代计算机 (专业版) , 2008 (1) :80-81.
　　[4] 郑艳梅.国内外离散数学教材内容比较分析[J].计算机教育, 2017 (2) :149-152.
　　[5] 左孝凌, 李为监, 刘永才.离散数学[M].上海:上海科学技术文献出版社, 1982.