科学网 › 标签 › 离散结构

标签: 离散结构

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

「离散数学」是一门什么样的学科: 热度 5 saif 2020-7-10 05:18; 写这篇文章的动机是想探讨从离散数学开始入门数理逻辑的路径以及离散数学与数理逻辑之间的关系。以学习数理逻辑为目的学习离散数学，和一般的以学习计算机为目的的学习还是有相当的不同，最大的不同就是：以数理逻辑为目的的学习，应当以「证明」—— 形式证明为目的，这其中包括了关于形式证明的理论 — — 一阶理论的句法和语义，以及关于形式证明的实践 — — 证明框架和策略。学习的中心内容有两个：「语言」 — — 「一阶语言」；「结构」以及数学中关于「结构」的思想、概念、种类、实例以及「结构」和「语言」的关系。一、离散数学是一门什么样的学科？与数学的主流分支不同，离散数学看上去似乎没有一个确定的中心话题，内容很庞杂。我曾做过一个粗略的统计，离散数学的内容涉及大约43个左右大大小小不同的话题，从集合、函数、关系、命题逻辑、谓词逻辑，到算法、计数、数据结构、递归、图论、概率、数论、形式语言与自动机，布尔代数、向量与矩阵，线性规划、抽象代数，编码理论、信息论，博弈论、运筹学、理论计算机科学等，真是那句俗话，XXXX是个筐，什么都可以往里装。由于离散数学的内容包括面很广，一本通常意义上的教科书不可能全部涵盖，因此我们看到的教科书基本是上述内容集合的不同子集。那么到底应当如何定义「离散数学」这门学科呢？如果我们使用集合的语言表达就是：（1）离散数学 = { x∈数学 | 离散结构(x) } 其中，「离散数学」是「数学」的一个子集，「离散结构」是一个谓词，x代表任意数学对象。现在来详细考察一下这个「离散数学」的定义式。我们的考察，从为什么会出现这样一个学科开始。首先，离散数学和其它数学分支不同，它并没有开辟数学的新领域，而是在既有的数学领域划出一个范围，以「离散结构」这个性质为标准，若某个数学对象具有「离散结构」的属性就划入。那为什么会出现「离散数学」这门学科呢？回答是 — — 是因为计算机的出现！！！因为计算机只能处理「离散」对象。生活中「离散」对象和「连续」对象的例子是大米和水，前者是离散的，后者是连续的，因为米粒是可列举的、可数的，英语属于可数名词，中文可以用单位量词「粒」等表示，水是无法列举的、也是不可数的，因而在英语中属于不可数名词，中文则不可直接用单位量词表示。形象地说，计算机可以处理像米粒这样的离散对象而无法直接处理像水这样的连续对象。例如，我们在计算机屏幕上看到一条光滑的曲线。按照微积分定义，一条光滑曲线如在某个区间连续，则一定可以确定区间内任意一点的极限。换句话说，在这个区间内你是无法确定一个离散点的确切位置的，因为在这个区间内，所有的点都是无穷小，而这些无穷小的点的数量是无穷多。但是在计算机的屏幕上就不是那么回事了，一条曲线无论看上去多么精细、平滑，一定是由一组固定的、确定的、有限数量的「点」（像素）构成的，否则要是按照极限定义，那条曲线是永远画不出来的。也就是说，如果我们要在计算机上处理、表达连续性数据，必须先要把它「离散化」— — 把无穷小量变成有固定、确定的数值，把连续变成可列举的、把无穷数量的元素转换成有限数量的元素。仍然拿「水」作例子，我们需要把「水」这个连续对象变成像「水滴」这样的离散对象。如果你是个程序员，那我们把上述的思想变成一个编程任务：在一个实数直角坐标系的闭区间上定义一条处处连续的曲线，你的任务是写一段代码，列举该区间内所有点的坐标值，亦即，列举下列集合的所有元素（2）{ ( x, y ) ∈ R 2 | 2 ≤ x ≤ 3 ∧ y ∈ R } 你将如何做呢？当然是先确定一个循环，从实数2.0到实数3.0。然后找到递增的台阶。这时你遇到了麻烦，下一个点是什么？为什么？当你脑子里冒出「下一个」的念头时，你已经输了，因为根据极限定义连续曲线根本就没有「下一个」这个概念，因为我永远可以在你设定的「下一个」之前找到离当前数更近的「下一个」使得你定义的那个「下一个」不再是「下一个」。为什么你会有「下一个」这样的概念，是因为计算机给你「洗脑」了。你编写这段代码的另一个困难是不知道这个循环什么时候结束，因为在区间内，有无穷多个实数，换句话说，你的这个循环体永远不会结束。你的幸运在于你所给定的实数区间是闭区间，如果是开区间，你连从哪里开始到哪里结束都无法确定，理由一样，我永远可以找到一个比你设定的开始的那个实数更靠近2.0、比你设定的结束的那个实数更靠近3.0的实数。这个任务是无法完成的，因为这不是一个「可计算的」任务。问题的根源，就在于「离散」与「连续」的矛盾 — — 你试图用离散的手段解决连续的问题，用有穷的方法解决无穷的问题；其中「无穷」（无穷小量与无穷大的个数）这个概念是阻碍你解决这个问题的「元凶」。我们知道，历史上许多数学悖论都是因「无穷」这样的概念而引发的，因此，希尔伯特曾试图在自己公理系统中排除「无穷」的概念，而代之以所谓 “finitary”【注1】的概念，亦即用一个有穷输入的概念代替「无穷」这个概念，以便在公理系统中彻底排除悖论的干扰，并将基于这个理念建立的数学公理体系称作 “finitary mathematics”。这是将数学中连续对象离散化的首次理论尝试，也是「离散数学」这个概念产生的最基本动机。上世纪1930年代，布尔巴基学派将整个数学理论进行了重构和形式化，并试图以「结构」这个概念统一所有的数学分支。自此，「什么是数学」的定义发生了变化，数学的本质就是对「结构」的研究，而「数」与「形」不过是「结构」概念下的两个实例而已。到了现代由于计算机的出现，「离散」的概念从学术走向现实，从科学走向技术，数学对象的离散化成为刻不容缓的任务。数学家对这一新挑战的回答是：第一、将现有数学对象根据「结构」的概念以「离散结构」为标准一分为二，将具有「离散结构」的对象合称为「离散数学」；第二、将划分的另一半，不属于「离散结构」的数学对象离散化，由此而产生了一个新的数学分支— — 计算数学（又称「数值计算方法」）—— 一门专门研究如何将非离散结构的数学对象离散化的学科。那么，什么样的数学对象是「离散结构」呢？按照我们直观的理解，自然数、整数当然是，除此之外，函数、多项式、向量与矩阵等众多数学对象也是离散结构，个中缘由当你掌握了离散数学中的相关内容自然理解。通过上面的讨论，我们就可以大致了解（1）的真正含义：在「结构」这个概念下，我们对所有数学对象进行分类，属于离散结构的数学对象就划为「离散数学」。因此，「离散数学」并不是一个独立的数学分支，而是对数学对象「横切」、提取公因式所得的一个数学对象集合。这些数学对象本来分属于它们各自的数学分支，只是由于都具有「离散结构」这个属性才走到了一起。由此可知，「离散数学」是个开放集，任何具有「离散结构」属性的数学对象都可以归为「离散数学」。有了上面讨论的铺垫，我们现在心里对「离散数学到底是什么」这个问题应当有了明确的答案 — — 研究「离散结构」数学对象的学科。那到底什么是「结构」？为什么所有数学学科都可以统一在「结构」这个概念下？这就是代数特别是抽象代数要讨论的问题。如果你浏览过一些数学著作、特别是国外出版的数学著作就会发现，许多严肃的作者都会把群、环、域放在其正文内容的前面，根本原因，是使读者建立「结构」的概念。因为只有理解了「结构」的概念，才能理解所有数学对象的共性。因此从理论上说，学习离散数学应当从什么是数学结构开始，因为这个概念不仅是统御离散数学而且是理解所有数学内容的总纲。但是要理解什么是数学结构，就要先理解描述数学结构的语言— — 逻辑、集合、函数、关系。从数理逻辑的角度看，整个数学是由两个部分组成：数学知识的形式化表示 — — 数学结构，与表达数学命题、数学证明的标准语言 — — 一阶语言；而表达数学结构、一阶语言的基本构件就是集合、函数、关系、命题逻辑与谓词逻辑语言。用这些构件描述「结构」的基本框架是这样的： 1. 给出一个数学对象的【集合】，通常是元素数量【有限】的、元素是【可数】的集合，并描述这个【集合】的基本性质； 2. 定义在这个集合之上元素之间的【关系】，对这些【关系】的表达既可以使用集合意义上的「有序元组」(ordered tuple) 也可以使用逻辑的「谓词」(predicate)； 3. 定义在这个集合上的【运算】以及参加【运算】的元素的个数（又称作「元」：ary），这就是函数； 4. 定义陈述这个结构公理、定义、定理的【语言】，这就是【一阶语言】；因此我们从「离散数学」入门数理逻辑的中心概念就是：【结构】、【语言】，而学习的最基础内容是【逻辑】、【集合】、【关系】、【函数】。数学的标准语言是一阶语言，而一阶语言本身，也可以当做具有离散结构的数学对象，这就是我们在任何一本离散数学教科书中看到的「命题逻辑」和「谓词逻辑」的真实面貌。换句话说，离散数学中的逻辑，不是研究推理论证，而是这个逻辑形式化后（弗雷格、罗素）的数学形式。这样的逻辑，我们关注的不是什么「思维能力的提高」，而是作为一种离散的数学结构、它与其它具有离散结构的数学对象的异同，我们都可以用群环域的概念对这种结构进行研究。作为初学者，我们所学到的，不是什么推理论证，而是逻辑式的代数属性、性质和特征。因此，我们获得的知识，是纯形式化的知识，没有语义、只有句法、只有代数。学到这样的逻辑当然不完整，充其量就是和我们在中学所学的关于自然数、整数和有理数运算规律基本相同的另一种代数，只不过运算对象不再是数而是命题真值而已。因此归纳而言，离散数学的内容，大致可以分为三类：语言类、理论类、实例类。集合、函数、关系、逻辑属于语言类，因为这些内容相当数学元语言的基本构件 — — 它们提供了描述数学对象的基本词汇和语法。群环域相当于理论归纳，我们通过这部分内容认识、熟悉、掌握关于「结构」 — —「数学结构」 ——「代数结构」的概念。由此理解为什么所有的数学对象，自己已知的、未知的，都可以用「结构」的概念归纳，形式化。在这个过程中，所有数学对象都可以用逻辑、集合、函数、关系这四个工具在「结构」的概念下得到统一，所有的数学对象、数学分支都不过是「结构」的概念下的具体实例。因此离散数学教科书中的其它内容，都是在讲「结构」这个概念下各种不同的实例。对这部分你完全有取舍的自由，可根据你对需要进行选择。把上面这些归纳一下，离散数学的主要内容包括： * 语言类：逻辑、集合、关系、函数 * 理论类：代数结构，群、环、域，同构、同态 * 实例类：剩余的其它内容。不过需要注意的是，语言类的内容同样也是代数结构的实例，亦即，描述数学的语言，亦可以用被描述的数学描述，大部分数学悖论往往产生于这种【元语言】与【对象语言】的混乱中。二、如何从离散数学入门数理逻辑？从离散数学开始入门数理逻辑，学习的的重点就是本文一开始提到的：一个中心，两个重点。（3）一个中心：学习如何规范化地做数学证明，在这个过程中培养提高自己的逻辑思维能力；（4）两个重点： i. 语言：一阶语言、集合、函数、关系，这是描述所有数学对象的语言，是数学的「元语言」 ii. 结构：代数结构 — — 数学结构 — — 结构；群、环、域和同构、同态。在此基础上，熟悉和理解教科书中所列举的其它数学结构的实例。在上面列举的学习重点中，语言的学习主要就是集合语言（包括集合、关系、函数）、一阶语言（命题逻辑、谓词逻辑）的的学习，这个学习过程当然包括了理解定义、做习题等内容，但更重要的是运用 — — 通过学习数学证明进一步理解一阶语言在数学中的作用，使自己成为这种语言的熟练使用者。从数理逻辑的角度，数理逻辑的本质就是从理论的高度研究证明，它的句法、语义、演算规则。而在离散数学的阶段，主要是在初步掌握了一阶语言后大量的实践。学会做证明题的一大标志是，可以自如地将证明题分别用自然语言（中英语）和一阶语言写出，并可以自如地在二者之间相互翻译。只有当你充分理解、完全掌握、自如运用一阶语言写出数学证明，你才真正达到了数学的成熟。「证明」、「语言」、「结构」是学习离散数学的中心内容。明确了学习的大方向，现在谈谈学习方法。不过我这里所说的学习方法并不是常规意义上的如何学习，而是一个原则，那就是：你的学习需要两种指南：第一种指南：用非「元语言」式的语言告诉你，你现在学的到底是什么东西。意思是，不是用数学的语言解释你所要学的数学对象是什么。假定你现在要学的是线性代数，那么什么是线性代数？这个解释不应当只是告诉你线性代数就是解线性方程组的学科、是研究线性转换的学科、是研究向量空间的学科，而是从更高的认知维度、套用一个现在流行术语就是「降维」解释这个数学对象是什么。只有通过这样的指南，你才能获得你所要学习内容的真正理解。因为只有在这个维度理解了学习对象，你才能知道所学内容对你认识这个世界有什么帮助。这种理解是哲学式的、认知式的理解。真正好的指南，是让我对这个世界、而不仅仅是对数学知识有更深刻的认识和理解，尤其是学习数学，更应当如此。第二种指南我称作工作手册（workbook）或技术手册 — — 我们的大多数教科书都属于这个类型 — — 提供技术细节的讲解以及相应的练习，学习者通过这样的指南获得实际技能的掌握和理解，认识新的技术领域。不过在现实中，很难找到第一种那样的指南，尤其是中文资源。这就需要读者去在各种著作中主动发现，或者在阅读中自己感悟— — 要在阅读中多思考，从过去自己的经验、从自己知道的别人的经验中思考。这种思考，不应当仅仅是本学科的，应当是跨学科的，要善于从别的不相关的学科知识、生活经验感悟目前学习对象的真实「认知」意义。当学完一个学习对象要问自己的就是，通过对这部分知识的学习，我对这个「世界」的哪个部分又有了新的了解，而不应当仅仅是我学会了矩阵运算，我弄懂了哥德尔定理。在「豆瓣」本人的阅读书单上，列举了一些类似第一指南的英语书籍，也是我近年来关注数学著作的主要基准。在前面的笔记我曾经说过，数理逻辑实际上是数学哲学的形式化表达— — 用一阶语言的符号表达数学对数学自身的理解。有人说，数学就是一种工具，用来解决现实世界的其它问题。其实，用数学解决其它问题包括了两个方面：将要解决的问题从自然语言描述翻译成数学语言，这个过程我们称之「建模」，利用数学提供的工具、方法解决问题 — — 我们称之「算法」。而数理逻辑是用来解决数学本身的问题，为此而建立的模型就是【代数结构】，利用这个模型提供的工具方法解决问题，我们称之为「证明论」【注2】。而离散数学则向我们提供了解决离散结构数学问题的工具和方法。我们学习离散数学作为数理逻辑的入门，应当要有这样的觉悟，而不仅仅停留在知识表面技术细节的理解和掌握。那么，应当如何学习？应当说，我们现在所处的时代是信息过剩、过剩，而不是信息缺乏。我们的问题不是无书可选，而是可选的资源太多而无法决定。因此，我们的学习策略就要适应这样的时代。我个人的学习方式是：不再以教科书为单位进行学习，而是以内容、话题为单位学习。假定我目前正在学习集合论，我就从所有我可以得到的资源中学习，既可以是教科书，也可以是视频教程、还可以是博客、笔记、社交媒体等等。在这个过程中，我得到的不是一家之言，而是所有人— — 所有我所及之作者的众家之言，每个人可能都说了一部分，但是众家的合集就可以使我得到一个比一家之言更全面的知识和认识，其中我更有可能得到上面所说的第一种指南。另外需要注意的是，离散数学不是单独的数学分科，而是各个数学学科的合集，我们选择学习材料时，切忌只选择带「离散数学」标题的，只要你理解了离散数学的本质，你就会发现所有的数学教科书中都有可能包含离散数学的内容，例如大部分数学分析，代数的教科书的前面都包含一些集合，函数，关系和逻辑的内容。因此以主题、话题为中心，你就可以打破界限利用更多的资源进行学习。学习的重点是有两个：理解概念，多做证明。概念的理解，重点应当是上面提到的第一指南意义上的理解，但是如果无法找到这样的指南，自己也无法体悟，那就要作为未解决的问题，在继续进行下一步学习的同时时时关注前一问题的概念性理解。只有在这个层面上理解学习才算真正完成。三、目标学到什么程度才算是入门？第一，可以用一阶语言读写的定义、定理、证明并可以在自然语言与一阶语言之间互译；第二，对结构的概念、群环域等结构类有深入的理解，熟悉一些典型的离散结构，如、自然数、整数，向量等，对于未知的数学对象能够用结构的观点迅速得到其要旨。达到这个程度，现在市面上的所有的任何程度的数学教科书、数理逻辑教科书对你来说已不再是「天书」，因为这些书本质上都是用直译成自然语言的一阶语言写成的关于某个数学结构实例的技术手册。学习数理逻辑的终极目的，是使你成为一个「数学思想者」，数学对你不再是一堆拉丁希腊字母和特殊符号，也不再是一个公式连着另一个公式的推导证明，它是就你的世界观，数学是你表达哲学理念的最恰当方式。（完）【注1】 “finitary”是希尔伯特公理化理论的专用术语，是指一个运算/操作/函数，其输入值/运算子/参数的数量是可以用一个自然数表达的。从构词法上分析，finit- 表示有限，而 -ary，则是像 binary、unary、ternary等，表示谓词/函数所需的「项」、「参数」，数学、计算机术语是「元」，元组(tuple)的「元」，因此 finitary 直译应当是「有限元」，但是又和中文的「有限元分析」相冲突，故索性不译，直接放在这里。这种细微而重要的差别，你在读中文文献时很难得到，或者是译者不具备这样的素养，或者没有用准确的中文表达出来。本人亦因才疏学浅无法用准确的中文表达finitary的原意，故有此注解。【注2】用数学工具方法解决数学自身的问题，旧称【元数学】，【元数学】大部分内容后被归入到「证明论」。而对数学本身问题的研究，其实是被称作「数学基础」的学科。「数理逻辑」是「数学基础」的形式化表述语言，而对其不涉及技术细节只关注基本理念的研究，称作「数学哲学」——例如历史上著名的三大学派和思想运动：逻辑主义、形式主义和直觉主义。因此，「数理逻辑」、「数学基础」和「数学哲学」是研究数学本身问题密切相关、表里相间的三大学科。; 个人分类: 计算|20153 次阅读|19 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 离散结构

相关帖子

相关日志

关闭安全验证