集合论即其与计算机相关的问题.doc

集合论1、集合论的历史。集合论是一门研究数学基础的学科。集合论是现代数学的基础，是数学不可或缺的基本描述工具。可以这样讲，现代数学与离散数学的“大厦”是建立在集合论的基础之上的。21世纪数学中最为深刻的活动，就是关于数学基础的探讨。这不仅涉及到数学的本性，也涉及到演绎数学的正确性。数学中若干悖论的发现，引发了数学史上的第三次危机，而这种悖论在集合论中尤为突出。集合论是德国著名数学家康托尔(G.Cantor)于19世纪末创立的。十七世纪数学中出现了一门新的分支：微积分。在之后的一二百年中这一崭新学科获得了飞速发展并结出了丰硕成果。其推进速度之快使人来不及检查和巩固它的理论基础。十九世纪初，许多迫切问题得到解决后，出现了一场重建数学基础的运动。正是在这场运动中，康托尔开始探讨了前人从未碰过的实数点集，这是集合论研究的开端。1874年，德国数学家康托尔在著名的克雷尔数学杂志上发表了关于无穷集合论的第一章革命性文章。从1874年到1884年，康托尔的一系列关于集合的文章，奠定了集合论的基础。他对集合所下的定义是：把若干确定的、有区别的（不论是具体的或抽象的）事物合并起来，看作一个整体，其中各事物称为该集合的元素。没想到集合论一诞生就遭到了许多数学家的激烈反对，当时的权威数学家克罗内克(Kronecker)非常敌视康托尔的集合论思想，时间达整整十年之久，法国数学大家庞加莱(Poincare)则预测后一代人将把集合论当作一种疾病。在猛烈的攻击下与过度的用脑思考中，康托尔本人一度成为这一激烈论争的牺牲品，他得了精神分裂症，几次陷于精神崩溃。然而乌云遮不住太阳，经历二十余年后，集合论最终获得了世界公认。到二十世纪初集合论已得到数学家们的赞同。数学家们乐观地认为从算术公理系统出发，只要借助集合论的概念，便可以建造起整个数学的大厦。在1900年第二次国际数学大会上，著名数学家庞加莱就曾兴高采烈地宣布“数学已被算术化了。我们可以说，现在数学已经达到了绝对的严格。”然而这种自得的情绪并没能持续多久。英国哲学家罗素(Russell)就很怀疑数学的这种严密性，他经过三年的苦思冥想，于1902年找到了一个能证明自己观点的简单明确的“罗素悖论”。不久，集合论是有漏洞的消息迅速就传遍了数学界。 罗素构造了一个所有不属于自身（即不包含自身作为元素）的集合R。现在问R是否属于R？如果R属于R，则R满足R的定义，因此R不应属于自身，即R不属于R；另一方面，如果R不属于R，则R不满足R的定义，因此R应属于自身，即R属于R。这样，不论何种情况都存在着矛盾（为了使罗素悖论更加通俗易懂，罗素本人在1919年将其改写为“理发师悖论”）。这一仅涉及集合与属于两个最基本概念的悖论如此简单明了以致根本留不下为集合论漏洞辩解的余地。号称“天衣无缝”、“绝对严密”的数学陷入了自相矛盾之中。从此整个数学的基础被动摇了，由此引发了数学史上的第三次数学危机。危机产生后，众多数学家投入到解决危机的工作中去。1908年，德国数学家策梅罗(E.Zermelo)提出公理化集合论，试图把集合论公理化的方法来消除悖论。他认为悖论的出现是由于康托尔沒有把集合的概念加以限制，康托尔对集合的定义是含混的策梅罗希望简洁的公理能使集合的定义及其具有的性質更为显然。策梅罗的公理化集合论后来演变成ZF或ZFS公理系统。从此原本直观的集合概念被建立在严格的公理基础之上，从而避免了悖论的出现。这就是集合论发展的第二个阶段：公理化集合论。与此相对应，在1908年以前由康托尔创立的集合论被称为朴素集合论。公理化集合论是对朴素集合论的严格处理。它保留了朴素集合论的有价值的成果并消除了其可能存在的悖论，因而较圆满地解决了第三次数学危机。公理化集合论的建立，标志着著名数学家希耳伯特所表述的一种激情的胜利，他大声疾呼：没有人能把我们从康托尔为我们创造的乐园中赶出去。2、集合论在计算科学中的应用。起初，集合论主要是对分析数学中的“数集”或几何学中的“点集”进行研究。但是随着科学的发展，集合论的概念已经深入到现代各个方面，成为表达各种严谨科学概念必不可少的数学语言。随着计算机时代的到来，集合的元素已由传统的“数集”和“点集”拓展成包含文字、符号、图形、图表和声音等多媒体信息，构成了各种数据类型的集合。集合不仅可以用来表示数及其运算，更可以用来表示和处理非数值信息。数据的增加、删除、修改、排序以及数据间关系的描述等这些很难用传统的数值计算操作，可以很方便地用集合运算来处理。从而集合论在编译原理、开关理论、信息检索、形式语言、数据库和知识库、CAD、CAM、CAI及AI等各个领域得到了广泛的应用，而且还得到了发展，如扎德(Zadeh)的模糊集理论和保拉克(Pawlak)的粗糙集理论等等。集合论的方法已经成为计算科学工作者不可缺少的数学基础知识。3、公理化方法及其作用。在计算科学的发展中，公理化方法曾在一些分支学科的发展中得到广泛应用并产生重要的影响。例如，在形式语义学和程序理论的研究中，公理语义学一直占有重要的地位。一些软件开发工具也是用到了这种思想。那么什么是公理化方法呢？所谓公理化方法，就是从尽可能少的无需定义的原始概念（基本概念）和尽可能少的一组不加证明的原始命题（基本公理、公设）出发，应用严格的逻辑推理规则，用演绎推理来对一门学科进行研究的方法。公理系统有一定的要求：无矛盾性、完备性和独立性。显然，在构建一门完整的科学理论体系时，所建立的公理系统必须无矛盾性，即在该系统中不能推出自相矛盾的结论。另外，完备性要求所建立的公理系统应尽可能多地推出这门科学中已经客观存在的结论，最好是能推出全部的结论（但哥德尔(Godel)业已证明完备的公理系统是不存在的）。独立性要求基本公理不多不少，任何一条公理都不能从其他公理中推出来。对一门科学公理化的目的是在于把该门学科表述为一个演绎系统，并通过对基本概念的选取、公理的设计，以及严格的演绎推理过程的研究，揭示这门学科深刻的内在规律，确保这门学科的表述更加严谨、准确。公理化方法主要有如下的作用：（1）分析和总结学科知识的作用；（2）把学科的基础搞清楚的作用，从而有助于在学科的深层次比较和统一不同的子学科，启发、促进和推动新理论的 创立；（3）在科学方法论上有示范作用，它对各门学科新建立 具有很好的借鉴作用。4、关系在关系数据库中的应用。数据库是计算机管理数据的一种机构。它由两部分组成：一部分是存储数据的存储空间，另一部分是管理数据的一组程序，即数据库管理系统，简称DBMS。用户通过DBMS提供的语言对数据库中的数据进行处理：数据的检索、数据的插入、数据的修改和数据的删除。用户使用数据库中数据的速度取决于数据存储的方式。数据库目前有三种上结构模型：层次模型、网络模型和关系模型。关系模型是基于关系理论的模型，而采用关系模型作为结构模型的数据库就叫关系数据库。在关系数据库中，数据库就是一个n元关系，在计算机中存放在一个二维数组中。一个二维数组可以有m行和n列，其中每一行的分量组成一个n元组，它是一条记录，代表一个完整的数据，它的分量称为记录的域。对应的实体可以有m条记录（m个数据）。用户使用关系数据库就是对一些二维数组进行检索、插入、修改和删除等操作。为此DBMS必须向用户提供使用数据库的语言，即数据子语言。这种语言目前是以关系代数或谓词逻辑等方法表示的，即它是以关系代数或谓词逻辑为其数学基础。由于引入了数学方法，使得关系数据库具有比其他几种数据库更优越，从而关系数据库这几年得到了迅猛的发展，日前已代替其他类型的数据库。当今流行的各种大型网络数据库如Oracle、Foxpro、Sybasc等都是关系型数据库。它已经成为数据库中最有实用价值和理论价值的数据库。5、关系在计算科学中的应用。关系这一概念对计算科学的理论和应用是非常重要的。像链表、树等复合的数据结构中的数据都是由元素之间的关系来联系的。另外由于关系是数学模型的一部分，故它常常在数据结构内隐含地体现出来。数值应用、信息检索、网络问题等也是关系的应用领域。在这些领域中关系作为问题描述的一部分出现，因而为了解决问题，关系的运算和处理是重要的。关系在包括程序结构和算法分析的计算理论方面也有重要的作用，如主程序和子程序的调用关系、高级语言编程中经常用到的函数（对应关系）、程序的输入与输出关系、计算机语言中的字符关系、OOP编程中的类继承关系等等。6、划分（等价关系）在信息检索中的应用。在日常生活中或在科学研究中，我们常常需要对一些事物按照某种方式进行分类。如将全中国人分成两类：男公民和女公民；将所有参赛的运动员分成不同的重量级别进行举重比赛；将所有的整数按模10同余关系分成10类：如果两个整数的差是10的倍数，则这两个整数属于同一个类。抽象地讲，就是需要对某个集合中的元素按照某种方式进行分类（集合的划分）。集合的划分与等价关系密切相关。而对信息和数据进行分类正是计算机的重要处理之一。分类的目的在于研究每一类中对象的共性。在信息检索系统中，根据一个主码进行检索，可把全体信息分成两个划分块（划分）。不同的主码对应的分类是不同的。指定一个主码，在对应的划分的每个划分块里按指定第二个主码进行分类，则可以得到全体信息的新的更细的划分（有4 个划分块），这相当于在检索中在两个主码之间使用了逻辑联结词AND，得到的4个划分块中的每个块类分别是两个主码对应的划分中划分块的交。若在两个主码之间使用了逻辑联结词OR，则得到的4个类中的每个类分别是两个主码对应的划分中划分块的并（这4个类不是两两不相交的，故不构成全体信息的一个划分）。7、序关系在计算科学中的应用。 集合元素间的序关系与元素间的等价关系一样也是一种重要的关系。根据等价关系可以将集合中的元素进行划分，而根据序关系 则可以将集合中的元素进行排序。只有有了一定的序关系，才能对数据库中的“信息”与“数据”进行存储、加工和传输。序关系对于情报检索、数据处理、信息传输、程序运行等都是极为重要的。如计算机程序执行时往往是“串行”的，这就涉及到了序关系（程序执行的先后问题；即使是“并行”处理，也不可避免地存在瞬间的先后问题。另外面向对象编程中的类继承关系、结构化程序设计中的函数或子程序调用关系都是序关系的应用实例。8、集合论中的悖论。所谓悖论就是逻辑矛盾：如果假定语句所指为真，那么会推出语句所指为假；反之，如果假定语句所指为假，又会推出语句所指为真。真是说它对也不是，不对也不是，让人左右为难。古今中外有不少著名的悖论，它们震撼了逻辑和数学的基础，激发了人们求知和精密的思考，吸引了古往今来许多思想家和爱好者的注意力。解决悖论难题需要创造性的思考，因此悖论的解决往往可以给人带来全新的观念，从而悖论的出现和解决往往成为数学发展的一种内在动力。 1) 理发师悖论：在萨维尔村，理发师挂出一块招牌：“我只给村里所有那些不给自己理发的人理发。”有人问他：“你给不给自己理发？”理发师顿时无言以对。因为这是一个矛盾推理：如果理发师不给自己理发，他就属于招牌上的那一类人。有言在先，他应该给自己理发。反之，如果这个理发师给他自己理发，根据招牌所言，他只给村中不给自己理发的人理发，他不能给自己理发。因此，无论这个理发师怎么回答，都不能排除内在的矛盾。这个悖论是罗素给出的对一九二年提出来的集合论悖论-“罗素悖论”所作的一个通俗的、有故事情节的表述。2）由“自指”引发的悖论：有人说“我在说慌”。如果他在说谎，那么“我在说谎”就是一个谎，因此他说的是实话；但是如果这是实话，他又在说谎。矛盾不可避免。它的一个翻版是：“这句话是错的”。这类悖论的一个标准形式是：如果事件发生，则推导出非，非发生则推导出，这是一个自相矛盾的无限逻辑循环。3）集合论悖论“罗素悖论”：“是所有不包含自身的集合的集合。” 这是罗素(B. Russell)由于怀疑数学基础的严密性，于1902年找到的悖论。用集合的描述性定义方式可定义为R=S|SS。于是就产生了这样的逻辑矛盾：若R包含R本身，则根据R的定义，RR，即R不属于R。若R不包含R本身，即RR，则根据R的定义，RR，即R包含R。4）书目悖论：一个图书馆编纂了一本书名词典，它列出这个图书馆里所有不列出自己书名的书。那么它列不列出自己的书名？这个悖论与理发师悖论基本一致。5）最大集合论悖论：存在一个最大的集合，它是包含一切集合的集合。若设这个最大的集合是A，现在问：A是否包含它自己？如果A包含它自己，那么A就是A所包含的元素，于是A就不是最大的集合，与定义矛盾；而如果A不包含A，那么A就不是包含一切集合的集合，也与定义矛盾。无论A是否是最大的集合都会推出矛盾，这就是最大集合悖论。 这也和“罗素悖论”类似。9、悖论对数学发展的积极作用。悖论并非一无是处。虽然他们的出现会直接导致“数学危机”的产生，但是悖论的出现逼迫数学家投入最大的热情去解决它们。而在解决悖论的过程中，数学本身也得到了发展。第二次数学危机导源于微积分工具的使用。微积分这一锐利无比的数学工具问世。许许多多疑难问题运用这一工具后变得易如翻掌，从而显示出了它的非凡威力。但是不管是牛顿、还是莱布尼兹所创立的微积分理论都是不严格的。两人的理论都建立在无穷小分析之上，但他们对作为基本概念的无穷小量的理解与运用却是混乱的。因而，微积分一诞生就遭到了一些人的反对与攻击。其中攻击最猛烈的是英国大主教贝克莱。贝克莱对牛顿的理论进行了攻击。他提出的问题在数学史上称为“贝克莱悖论”。笼统地说，贝克莱悖论可以表述为“无穷小量究竟是否为0”的问题。就无穷小量在当时的实际应用而言，它必须既是0，又不是0。但从形式逻辑而言，这无疑是一个矛盾。另外古希腊的大诡辩家芝诺(Zeno)的几个悖论阿基里斯悖论、二分法悖论（运动不存在）、“飞矢不动”悖论也反映出了有限与无限、无穷小与零、零与非零的逻辑矛盾。这些悖论在当时的数学界引起了一定的混乱，导致了第二次数学危机的产生。为解决这一悖论，无数人投入了大量的劳动。法国数学家柯西首先给出了极限的定义；“若代表某变量的一串数值无限地趋向于某一数值时，其差可任意小，则该固定值称为这一串数值的极限”。柯西之后，魏尔斯特拉斯、戴德金、康托尔各自经过自己独立深入的研究，都将分析基础归结为实数理论，各自建立了自己完整的实数体系。由此，沿柯西开辟的道路建立起来的严谨的极限理论与实数理论，完成了分析学的逻辑奠基工作。数学分析的无矛盾性问题归纳为实数论的无矛盾性，从而使微积分学这座人类数学史上空前雄伟的大厦建在了牢固可靠的基础之上。重建微积分学基础，这项重要而困难的工作就这样经过许多杰出学者的努力而胜利完成了。微积分学坚实牢固基础的建立，结束了数学中暂时的混乱局面，同时也宣布了第二次数学危机的彻底解决。同样，以“罗素悖论”为代表的一系列悖论的出现导致了第三次数学危机。为了消除悖论，数学家纷纷提出自己的解决方案。1908年，策梅罗提出第一个公理化集合论体系，后来经其他数学家改进，称为ZF系统。这一公理化集合系统很大程度上弥补了康托尔朴素集合论的缺陷。除ZF系统外，集合论的公理系统还有多种，如诺伊曼等人提出的NBG系统等。公理化集合系统的建立，成功排除了集合论中出现的悖论，从而比较圆满地解决了第三次数学危机。同时，罗素悖论对数学而言有着更为深刻的影响。它使得数学基础问题第一次以最迫切的需要的姿态摆到数学家面前，导致了数学家对数学基础的研究。而这方面的进一步发展又极其深刻地影响了整个数学。如围绕着数学基础之争，形成了现代数学史上著名的三大数学流派：逻辑主义学派、形式主义学派和直觉主义学派，而各派的工作又都促进了数学的大发展。数理逻辑也取得了大发展，证明论、模型论、递归论、多值逻辑、非标准逻辑等相继问世。第一次数学危机促成了公理几何与逻辑的诞生；第二次数学危机促成了分析基础理论的完善与集合论的创立；第三次数学危机促成了数理逻辑的发展与一批现代数学的产生。数学由此获得了蓬勃发展，这或许就是数学悖论重要意义之所在吧。10、聪明的囚徒。古希腊有个国王，处死囚徒总是用两种方式：砍头或绞刑。他自恃聪明地做出了这样一种规定，让囚徒自己选择死的方式：囚徒可以说一句话，并且这句话是马上可以验证其真假的。如果囚徒说的是真话，那么处以绞刑；如果囚徒说的是假话，那么处以砍头。许多囚徒或者是因为说了假话而被砍头或者因为说了真话而被处以绞刑。有一位极其聪明的囚徒，当轮到他来选择处死方法时，他说出了一句巧妙的话，结果使这个国王不管按照哪种方法处死他，都违背自己的决定，最后只得将他放了。试问：这囚徒说的是句什么话？答：在日常语言中，凡是可以决定真假的陈述句叫做命题。但是有一类陈述句却就无法判定其真假。这就是所谓的悖论：一个语句Q，如果从Q为真，可以推出Q为假；而从Q为假，可以推出Q为真。聪明的囚徒所说的话，就应该是这样的悖论，使得国王无论怎么处置他都会带来矛盾。这句话就是“国王决定砍我的头”。如果国王决定砍他的头，则他说的是真话，因此按国王规定的处死方法（讲真话应处以绞刑），他应该受绞刑。这样就造成了国王的规定同国王决定的处死方法相矛盾。同样如果国王决定让受绞刑，则他说的是假话，因此按国王规定的处死方法（讲假话应砍头），他应该砍头。这样也造成了国王的规定同国王决定的处死方法相矛盾。无论如何，国王都将处于进退维谷的处境，因此只好免这个囚徒一死，将他放掉。代数结构1、为什么要研究代数系统？答：代数是专门研究离散对象的数学，是对符号的操作。它是现代数学的三大支柱之一（另两个为分析与几何）。代数从19世纪以来有惊人的发展，带动了整个数学的现代化。随着信息时代的到来，计算机、信息都是数字（离散化）的，甚至电视机摄像机、照相机都在数字化。知识经济有人也称为数字经济。这一切的背后的科学基础，就是数学，尤其是专门研究离散对象的代数。代数发端于“用符号代替数”，后来发展到以符号代替各种事物。在一个非空集合上，确定了某些运算以及这些运算满足的规律，于是该非空集合中的元素就说是有了一种代数结构。现实世界中可以有许多具体的不相同的代数系统。但事实上，不同的代数系统可以有一些共同的性质。正因为此，我们要研究抽象的代数系统，并假设它具有某一类具体代数系统共同拥有的性质。任何在这个抽象系统中成立的结论，均可适用于那一类代数系统中的任何一个。2、代数的历史。代数学历史悠久。代数的发展可分成两个阶段。19世纪之前的代数称为古典代数，19世纪至今的代数称为近世代数（抽象代数）。远在古希腊时期，人们就知道可以用符号代表所解问题中的未知数，并且这些符号可以像数一样进行运算，直到获得问题的解。古典代数的基本研究对象是方程，它是以讨论方程的解法为中心。在古典代数中，每一个符号代表的总是一个数，但这个数可以是整数也可以是实数。古典代数的主要目标是用代数运算解一元多次方程。它成功地解决了一元二次、一元三次和一元四次方程的求解问题。19世纪初，人们逐渐认识到，符号不仅可以代表数，而且可以代表任何事物。在这种思想认识的支配下，人们开始将任意集合上所进行的代数运算作为研究的对象，从而出现了近世代数体系和方法。19世纪30年代，在寻找一元五次方程根式求解方法的过程中，年青的法国数学家伽罗瓦(E. Galois)首次得出了群的概念用置换群的方法彻底证明了高于四次的代数方程的根式不可解性。起初他的奇思妙想和巧妙方法虽然并不被当时人接受和理解，却发展出了一门新的学科-抽象代数学。抽象代数学的研究对象是抽象的，它不是以某一具体事物为研究对象，而是以一大类具有共同性质的事物为研究对象。因此其研究成果适用于这一类事物中的每一个，从而收到事半功倍之效。抽象代数学的主要内容是研究各种各样的代数系统。它把一些形式上很不相同的代数系统，用统一的方法描述、研究和推理，从而得到反映出它们共性的一些本质的结论，然后再把这些结论应用到具体的代数系统中。从而抽象产生了广泛的应用。3、抽象代数学在计算机中的应用。100多年来，随着科学的发展，抽象代数越来越显示出它在数学的各个分支、物理学、化学、力学、生物学等科学领域的重要作用。抽象代数的概念和方法也是研究计算科学的重要数学工具。有经验和成熟的计算科学家都知道，除了数理逻辑外，对计算科学最有用的数学分支学就是代数，特别是抽象代数。抽象代数是关于运算的学问，是关于计算规则的学问。在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构，而抽象代数研究的中心问题就是一种很重要的数学结构-代数系统：半群、群、格与布尔代数等等。计算科学的研究也离不开抽象代数的应用：半群理论在自动机理论和形式语言中发挥了重要作用；有限域理论是编码理论的数学基础，在通讯中起过重要的作用；至于格和布尔代数则更不用说了，是电子线路设计、电子计算机硬件设计和通讯系统设计的重要工具。另外描述机器可计算的函数、研究算术计算的复杂性、刻画抽象数据结构、描述作为程序设计基础的形式语义学，都需要抽象代数知识。4、布尔代数在逻辑线路中的应用。19世纪50年代，只受过初级数学教育、自学成才的英国人乔治.布尔（George Boole）先后发表了逻辑之数学分析(The Mathematical Analysis of Logic)和思维规律(The Laws of Thought)这两部杰作。他创造出了一套符号系统，利用符号来表示逻辑中的各种概念。并且建立了一系列的运算法则，利用代数方法研究逻辑问题，初步奠定了数理逻辑的基础。布尔代数从此问世，数学史上树起了一座新的里程碑。布尔将逻辑推理过程简化成极为容易和简单的一种代数运算。他规定在布尔代数中：1所有可能出现的数只有0和1两个；2基本运算只有“与”、“或”、“非”三种；在布尔代数中用等式表示命题，把推理过程看作等式的变换。这种变换只依赖于基本运算的性质。在其诞生100多年后才发现其应用和价值。虽然在布尔代数刚刚问世的时间里并没有受到人们应有的重视，但布尔仍然坚信自己的研究会对后世有相当大的帮助。随着布尔的去世，人们对布尔代数的了解也越来越少，直到20世纪初罗素在自己的数学原理中重新提到了布尔代数的名称才引起了世人足够的关注。但是，此时距布尔去世早已相隔多年。对计算科学而言，布尔代数的重要性是不言而喻的。布尔代数也确实是在其诞生100多年后才在计算机的发展中找到了它的用武之地，它为电子数字计算机开关电路设计提供了最重要的数学方法。1938年，美国数学家、信息论创始人香农(C. Shannon)发表了著名的论文继电器和开关电路的符号分析(A Symbolic Analysis of Relay and Switching Circuits)，首次用布尔代数进行开关电路分析。由于布尔代数只有0和1两个值，恰好与二进制数对应，香农把它运用于以脉冲方式处理信息的继电器开关。并证明布尔代数的逻辑运算，可以通过继电器电路来实现，明确地给出了实现加、减、乘、除等运算的电子电路的设计方法，从而从理论到技术彻底改变了数字电路的设计方向。这篇论文成为开关电路理论的开端，在现代电子数字计算机史上具有划时代的意义。香农在贝尔实验室工作中进一步证明，可以采用能实现布尔代数运算的继电器或电子元件来制造计算机。香农的理论还为计算机逻辑功能的设计奠定了基础，从而使电子计算机既能用于数值计算，又具有各种非数值应用功能，使得以后的计算机在几乎任何领域中，都得到广泛应用。今天，所有的电子计算机芯片里使用的成千上万个微小的逻辑部件，都是由各种布尔逻辑元件逻辑门和触发器组成的。由逻辑元件可以组成各种逻辑网络，这样任何复杂的逻辑关系都可以由逻辑元件经过相应的组合来实现，使其具有复杂的逻辑判断功能。5、半群与文法及形式语言。计算机可以完成很多任务。但是给定一个任务，我们面临的第一个问题是：它是否可以用计算机来解决？若可以的话，我们就要考虑第二个问题：如何解决。这些问题的回答都和计算模型有关。一般有三种类型的计算模型：文法(Grammars)、有限状态机(Finite-state Machines)和图灵机(Turing Machines)。其中文法是用来生成一门语言的所有词汇和判断一个词汇是否在一门语言中。文法产生形式语言，而形式语言既为象英语这样的自然语言提供了模型，又为像PASCAL，C，PROLOG和JAVA这样的编程语言提供了模型。在编译原理和汇编程序的创造中，文法有着不可替代的作用。设是一个非空有限集合，称为字母表，由中有限个字母组成的有序集合（即字符串）称为上的一个字，串中的字母个数m称为字长，m=0时，称为空字，记为。表示上的字的集合，上的连接运算定义为，=，则是一个代数系统，而且是一个独异点。的任一子集就称为语言。我们将利用文法来给定一门语言。一个文法给出了一个字母表（用来产生语言中词的符号集合），和一个产生词的规则集。一个文法是一个四元组G=（，T，s，P），其中是字母表，T是的子集，它的元素是终止符（它不能再被中其它字符代替），s是的一个元素，它是初始符，P是所谓生成规则的集合（生成规则实质上就是语言的短语构成规则，它们决定中的一个字符串可以被中的哪个符号串替换）。N=-T中的元素称为非终止符（它能被中其它字符代替），P中的每个产生式的左端至少要有一非终止符。定义了一门语言的文法后，利用产生式，我们就可以从初始符号s出发演绎出一个一个词，从而确定由该文法产生出来的语言。设G=（，T，s，P）是一个文法，则由G产生的语言L（G）就是能由初始符号s演绎出来的所有字符串的集合，即L（G）=T | s。6、纠错码中的群码。 由于在计算机中和通讯系统中信号传递非常频繁与广泛，因此如何防止传输错误是一件很重要的事情。当然，要解决这个问题可以有不同的途径。其中的一个途径就是采用纠错码(Error Correcting Code)，即从编码上下功夫，使得二进制数码一旦在传递过程中出错，接收端的纠错码装置就能立即发现错误，并将其纠正。当二进制信号串从发送端发出时，需要按规定生成具有干扰能力的纠错码，然后才能发送出去。在接收端，当接收到二进制信号串后立即对收到的纠错码进行检查，检查是否失真，若失真则要负责纠正。这就是在计算机和数据通讯系统中被广泛采用的方法。我们先举一个日常生活中的实例。如果你发出一个通知：“明天14：00-16：00开会”，但在通知过程中由于某种原因产生了错误，变成“明天10：00-16：00开会”。别人收到这个错误通知后由于无法判断其正确与否，就会按这个错误时间去行动。为了使收者能判断正误，可以在发通知内容中增加“下午”两个字，即改为：“明天下午14:00-16:00开会”，这时，如果仍错为：“明天下午10:00-16:00开