下载文档原格式
离散数学p ∧ q∨ r的主合取范式离散数学是研究离散结构和离散量的数学科学。
在离散数学中，逻辑运算是一项重要内容。
主合取范式（Canonical Conjunctive Normal Form）是命题逻辑中一种常用的归一形式，也称为合取范式（Conjunctive Normal Form）。
本文将介绍离散数学中主合取范式的概念，并以p ∧ q∨ r为例进行详细解释，以帮助读者更好地理解。
首先，让我们了解一下离散数学中逻辑运算的基本概念。
在离散数学中有三种基本的逻辑运算：与（∧）、或（∨）和非（¬）。
与运算表示同时满足两个条件，或运算表示满足其中任何一个条件，非运算表示取反。
主合取范式是一种标准的命题形式，在主合取范式中，复合命题被表示为一个形如C₁ ∧ C₂ ∧ ... ∧ Cₙ的合取式，其中C₁、C₂、...、Cₙ是子句（Clause）的合取，而子句是一个形如L₁ ∨ L₂∨ ... ∨ Lₙ的析取式，其中L₁、L₂、...、Lₙ是文字（Literal）的析取。
合取式是由多个子句进行合取，而子句则是由多个文字进行析取构成的。
现在我们来解释题目中的p ∧ q∨ r在主合取范式下的转换过程。
首先，我们需要将命题p、q和r转换成文字的形式。
一个文字可以是一个命题或其否定形式，即p或¬p、q或¬q、r或¬r。
因此，p ∧ q∨ r可以转换为(p ∧ q∨ r) = (p ∧ q∨ r) ∨ (p ∧ ¬q∨ r)∨ (p ∧ q∨ ¬r) ∨ (p∧¬q∨¬r)。
接下来，我们需要将这个合式逻辑表达式转换为主合取范式。
这需要使用分配律来展开合取、析取运算。
分配律的定义如下：对于任意的命题p、q和r，有：1. p∧(q∨r) = (p∧q)∨(p∧r)；2. (p∨q)∧r = (p∧r)∨(q∧r)。
现在我们来将(p ∧ q∨ r) ∨ (p ∧ ¬q∨ r) ∨ (p ∧ q∨ ¬r) ∨ (p∧¬q∨¬r)转换为主合取范式。
离散数学的意义和作用摘要：1.引言2.离散数学的定义和基本概念3.离散数学的主要作用4.离散数学在计算机科学中的应用5.离散数学在其他学科中的应用6.离散数学的重要性7.结论正文：**离散数学的意义和作用****1.引言**在现代科学技术中，数学发挥着越来越重要的作用。
其中，离散数学作为数学的一个重要分支，具有广泛的应用前景。
本文将探讨离散数学的定义、作用及其在各个领域中的应用，以展示其重要性。
**2.离散数学的定义和基本概念**离散数学（Discrete Mathematics）是研究离散对象及其性质的数学分支。
它主要包括集合论、图论、组合数学、逻辑与布尔代数等研究领域。
离散数学中的基本概念包括集合、元素、关系、函数等，这些概念为研究离散对象提供了理论基础。
**3.离散数学的主要作用**离散数学在数学、计算机科学、通信工程等领域具有重要作用。
它为研究离散结构和离散现象提供了理论依据，有助于解决实际问题。
**4.离散数学在计算机科学中的应用**在计算机科学中，离散数学有着广泛的应用。
如：在算法设计与分析、数据库设计、编译原理、网络优化等方面，离散数学提供了有力的理论支持。
**5.离散数学在其他学科中的应用**离散数学不仅在计算机科学中有重要作用，在其他学科中也具有重要应用价值。
例如，在生物学中，离散数学可用于研究基因序列的匹配问题；在经济学中，离散数学可用于研究经济模型的优化问题等。
**6.离散数学的重要性**离散数学在各个领域的应用表明，它已成为现代科学技术发展的重要支柱。
离散数学的研究成果不仅有助于推动数学本身的进步，还有助于促进其他学科的发展。
**7.结论**总之，离散数学作为数学的一个重要分支，具有广泛的应用前景。
它不仅在计算机科学中有重要作用，在其他学科中也具有重要应用价值。
随着科学技术的不断发展，离散数学的研究和应用将越来越受到重视。
离散数学中的基本概念和原理概述离散数学是数学中一个重要的分支学科，它主要研究离散对象及其结构、性质和关系。
在计算机科学、信息技术等领域，离散数学具有重要的应用价值。
本文将对离散数学的基本概念和原理进行概述，并介绍其在实际应用中的意义。
1. 集合论在离散数学中，集合论是最基础的概念之一。
集合是指由确定的元素组成的整体，而元素即集合中的个体。
集合间可以进行并、交、差等操作，而对于集合中的元素，可以通过包含关系、等于关系等进行描述。
在实际应用中，集合论常被用于数据库的设计和查询、逻辑推理等领域。
2. 关系和图论关系是研究离散数学中的另一个基本概念。
关系可以描述元素之间的某种联系或者特定的性质。
图论则是研究图的结构、性质和算法的学科，图由节点和边组成，节点表示元素，边表示元素之间的关系。
关系和图论在计算机网络、社交网络、电路设计等领域有广泛的应用。
3. 逻辑和命题逻辑是离散数学中的重要分支，研究命题之间的关系和推理规则。
命题是对某个陈述的真假进行判断的语句，可以用真或假来表示，通过逻辑运算符如与、或、非等进行连接。
逻辑在计算机科学中有广泛的应用，例如布尔代数、编程语言的设计等。
4. 组合数学组合数学是研究离散结构中的组合问题的学科，主要研究排列、组合和选择等问题。
排列是指对一组元素进行有序排列，组合是指从一组元素中选择出若干个元素的集合，选择是指对一组元素中进行有序或无序的选择。
组合数学在密码学、图像压缩、排课等领域有着广泛的应用。
5. 图的连通性和树图的连通性研究的是图中节点之间是否存在某种路径使得它们可以相互到达。
连通性在网络设计、电路设计等领域有着重要的应用。
树是一种特殊的图，它没有回路且任意两个节点之间存在唯一的路径。
树在数据结构、优化算法等方面有着广泛的应用。
综上所述，离散数学中的基本概念和原理涵盖了集合论、关系和图论、逻辑和命题、组合数学以及图的连通性和树等多个方面。
这些概念和原理在计算机科学、信息技术等领域有着广泛的应用，为解决实际问题提供了数学工具和方法。
离散数学证明S-c:VMGSGMV范式的有效性：1 、范式回顾及S-c: VMGSGMV范式的提出学者乔·贝恩（Joe S. Bain）在1930年代，提出SCP(Structure->Conduct->Performance)范式，“结构-行为-绩效”范式。
其基本含义是，结构决定企业在市场中的行为，而企业行为又决定其在外部环境发生变化的情况下的经营绩效；学者艾尔佛雷德.D.钱德勒（Chandler,1962）在《战略与结构》一书中，提出SS(Strategy-Structure)范式，即“战略决定结构”范式，指出企业扩张战略必须有相应的结构变化跟随；学者理查德.罗梅尔特（Richard P. Rumelt,1974）在《战略，结构与经济绩效》一书中，提出SSP （Strategy-Structure-Performance）范式，即“战略决定结构，结构决定绩效”。
此后，SSP范式一直处于战略研究的中心。
进入21世纪后，陆续出现了一些关于对主流范式的批评.近年来，文化元素的重要作用更加引起学者们的广泛注意。
学者Gerard J. Tellis和Jaideep C. Prabhu(2009)通过对世界上17个主要经济体中的759家公司的调查和档案数据分析指出，根本性创新是国家及企业的增长、获得成功和财富的重要驱动因素，而企业文化是根本性创新的最强驱动因素[2]；学者Robert G. Eccles,Ioannis等（2011），通过对180家样本公司有关“可持续文化”对企业的影响的调查，发现那些在许多年前被称作为高可持续性的企业，具有独特的治理机制特质，其董事会更可能对可持续性负责，并且对最高管理层的激励更可能与可持续性指标挂钩，具有在更高层次、更深层次上利益相关者（员工、客户、非政府组织等）参与的有效机制，更强调外部环境和社会标准，披露公开信息方面更加透明[3]。
美国旧金山海湾地区公会经济研究所（2012），就该地区除了人才聚集、资本聚集以外，什么因素使得该地区一直处于产业创新的领导地位进行了研究，发现：一个共同的创新文化氛围，企业内部自上而下的战略互动，企业内部创新战略、业务战略、文化战略的紧密交织，资本及人力资源的自由流动，良好的创新基础设施（一流大学、政府研究机构、现代设施等）等元素的组合互动构成该地区持续成功的关键[4]。
离散数学范式随机知识点1.什么是随机现象？离散数学是对非连续（离散）的数学对象和结构进行研究的学科。
离散数学中主要涉及离散对象的表示、操作和分析，包括集合、关系、图论、组合数学和逻辑等。
在离散数学中，有不同的范式和方法，下面将分别介绍。
1.集合论范式集合论是离散数学的一个基础学科，它主要研究集合的基本概念、关系和操作。
在集合论范式中，我们主要研究由数学对象（元素）组成的集合，以及它们之间的关系和操作。
集合论最初是建立在自然数集合基础之上的，但后来逐渐发展为一种更一般的数学语言和方法，可用于描述任何类型的对象。
2.图论范式图论是离散数学的一个重要分支，主要研究图的结构、性质和算法。
图论范式中，我们主要关注由节点和边组成的图结构，以及它们之间的关系和操作。
图论可以用于许多领域，包括计算机科学、网络分析和社会网络分析等。
3.组合数学范式组合数学是离散数学的一个分支，主要研究离散结构的计数和组合问题。
组合数学范式中，我们主要关注由对象组成的集合的计数问题，以及这些对象之间的排列和组合问题。
组合数学可以用于各种领域，例如统计学、物理学和计算机科学等。
4.逻辑学范式逻辑学是离散数学的一个分支，主要研究逻辑语言和推理。
逻辑学范式中，我们主要关注命题、谓词和命题逻辑等基本概念，以及它们的语法和语义。
逻辑学可用于任何需要进行推理和推断的领域。
总之，离散数学范式是离散数学中的不同领域和方法，它们用于描述和分析离散对象和结构，包括集合、图论、组合数学和逻辑学等。
每个范式都有各自的特点和应用，因此在具体问题中需要根据需求选择合适的范式和方法。
离散数学知识点笔记离散数学是对数学理论与应用的整合，这里涉及到的知识点很多。
几乎涉及到数学中的涉及的任何一部分，每个知识点都有其特点，在此我们将介绍一些离散数学中常用的知识点。
一、定义、实例和性质定义、实例和性质是离散数学知识点的基本内容，也是学习离散数学的必备基础知识。
它们综合涵盖了数学中的定义、性质和实例的基本知识。
这些知识点是数学的基础，运用了数学中定义、证明和实例的相关方法，通过它们可以了解数学中丰富的定义、性质和实例。
二、集合基础集合基础是理解离散数学关系和操作的基本工具。
它涉及到集合的性质、运算、概念等，是离散数学中最基础的概念，并且可以用来解决很多实际问题。
因此，掌握和深入学习离散数学中的集合基础非常重要。
三、函数、逻辑和图论函数、逻辑和图论在离散数学中占据重要的地位，函数是表达数学关系的基本方式，逻辑是分析离散数学关系的基本方法，图论是表示离散数学关系的基本工具。
熟悉函数、逻辑和图论知识可以帮助我们更好地理解数学中的关系并解决相关问题。
四、数学归纳法数学归纳法是离散数学的经典方法，它包括逐步归纳和变量归纳，是归纳和证明离散数学性质的基本方法。
它可以用来解决复杂的离散数学问题，是离散数学的重要工具。
五、数据结构和算法数据结构和算法是离散数学的重要组成部分，是运用离散数学解决实际问题的基本方法。
它们可以帮助我们更好地理解离散数学中的概念，并且可以用来设计出有效的数据结构和算法，解决复杂的离散数学问题。
六、数学建模数学建模是运用离散数学解决问题的重要方法，它可以帮助我们更好地理解实际问题，并通过建模、分析和推理形成有效的解决方案。
它是一种基于离散数学方法的复杂思维，也是理解和应用离散数学概念的基础要求。
综上所述，离散数学涉及到了定义、实例和性质、集合基础、函数、逻辑和图论、数学归纳法、数据结构和算法以及数学建模等知识点。
这些知识点是离散数学的基础，掌握了这些知识点，我们就可以更好地理解和运用离散数学解决实际问题。
离散数学析取范式与合取范式离散数学是计算机科学的基础学科之一，离散数学中的逻辑运算是非常重要的内容之一。
逻辑运算可以通过表达式来描述，其中最常见的表达式形式是析取范式（DNF）和合取范式（CNF）。
本文将介绍离散数学中的析取范式与合取范式，并分析它们在逻辑运算中的应用。
一、析取范式（DNF）在逻辑运算中，析取是一种基本的逻辑联结词，用于将多个命题通过逻辑“或”关系进行组合。
由此构建的逻辑表达式可以称为析取范式（DNF）。
析取范式是一种逻辑表达式的标准形式，可以方便地描述逻辑运算中的复杂逻辑关系。
析取范式的形式如下：p1 ∧ p2 ∧ p3 ∧ ... ∧ pn其中p1、p2、p3等为命题变量或其否定形式。
析取范式是由多个命题变量及其否定形式通过逻辑“与”关系连接而成。
例如，一个构成析取范式的表达式可以是：(p1∨p2∨p3)∧(q1∨q2)∧(r1∨r2∨r3)，其中p1、p2、p3、q1、q2、r1、r2和r3为命题变量或其否定形式。
析取范式在逻辑运算中的应用主要体现在逻辑推理和逻辑设计中。
在逻辑推理中，通过分解析取范式，可以对给定的命题进行逻辑判断和推断。
在逻辑设计中，可以通过构建析取范式来描述逻辑电路的功能和行为。
二、合取范式（CNF）在逻辑运算中，合取是一种基本的逻辑联结词，用于将多个命题通过逻辑“与”关系进行组合。
由此构建的逻辑表达式可以称为合取范式（CNF）。
合取范式也是一种逻辑表达式的标准形式，用于描述逻辑运算中的复杂逻辑关系。
合取范式的形式如下：(p1 ∨ p2 ∨ p3 ∨ ... ∨ pn) ∧ (q1 ∨ q2) ∧ (r1 ∨ r2 ∨ r3)其中p1、p2、p3等为命题变量或其否定形式。
合取范式由多个命题变量及其否定形式通过逻辑“或”关系连接而成，而这些子表达式又通过逻辑“与”关系连接起来。
例如，一个构成合取范式的表达式可以是：(p1∧p2∧p3)∨(q1∧q2)∨(r1∧r2∧r3)，其中p1、p2、p3、q1、q2、r1、r2和r3为命题变量或其否定形式。
离散数学的认识在为期一学期离散数学学习后我发现离散数学是计算机科学的核心基础理论课程, 是现代数学的一个重要分支，主要研究具有离散特征的变量和结构及相互关系, 涉及的内容较广，充分描述了计算机科学离散性的特点。
通过本课程的学习，不仅能为学生学习计算机专业后续课程奠定理论基础，而且能培养学生抽象思维能力、严格的逻辑推理和创新能力，为将来从事的软、硬件应用开发和理论研究打下坚实的基础。
在学习过程中，我总结出离散数学的以下几项特点：1、定义和定理多离散数学是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。
在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。
在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用，因此要真正理解离散数学中所给出的每个基本概念的真正的含义。
比如，命题的定义、五个基本联结词、公式的主析取范式和主合取范式、三个推理规则以及反证法；集合的五种运算的定义；关系的定义和关系的四个性质；函数（映射）和几种特殊函数（映射）的定义；图、完全图、简单图、子图、补图的定义；图中简单路、基本路的定义以及两个图同构的定义；树与最小生成树的定义。
掌握和理解这些概念对于学好离散数学是至关重要的。
如：定理：设π和π’是非空集合A上的划分。
如果π’的每一块都包含在π的一块中，则说π’细分π，或说π’是π的细分。
如果π’细分π,且π≠π’，则说π’是π的真细分。
像这样的定理还有很多，还不好记，特别饶人！2、方法性强在离散数学的学习过程中，一定要注重和掌握离散数学处理问题的方法，在做题时，找到一个合适的解题思路和方法是极为重要的。
如果知道了一道题用怎样的方法去做或证明，就能很容易地做或证出来。
反之，则事倍功半。
在离散数学中，虽然各种各样的题种类繁多，但每类题的解法均有规律可循。
所以在听课和平时的复习中，要善于总结和归纳具有规律性的内容。
离散数学的基本概念和运算离散数学是数学的一个重要分支，它研究离散结构和离散对象之间的关系。
与连续数学不同，离散数学关注的是离散的、离散的事物，如整数、图形、逻辑、集合等。
在计算机科学、信息技术以及其他许多领域中，离散数学都担当着重要的角色。
本文将介绍离散数学的一些基本概念和运算，以帮助读者更好地理解和应用离散数学。
一、集合论集合论是离散数学的基石之一，它研究集合以及集合之间的关系和运算。
集合是指一组元素的事物的整体，元素可以是任何事物，比如数字、字母、人或其他对象。
常见的集合运算有并集、交集、差集和补集等。
并集表示两个或多个集合中的所有元素的集合，交集表示同时属于两个或多个集合的元素的集合，差集表示从一个集合中减去另一个集合的元素的集合，补集表示在给定参考集合中不属于某个特定集合的元素的集合。
二、逻辑逻辑是离散数学的另一个重要内容，它研究命题、逻辑运算和推理。
在离散数学中，命题是指能够判断真假的陈述句。
逻辑运算包括与、或、非、异或等。
与运算表示两个命题同时为真时结果为真，或运算表示两个命题中至少有一个为真时结果为真，非运算表示对命题的否定，异或运算表示两个命题中仅有一个为真时结果为真。
推理是利用逻辑规则从已知命题中得出新的结论的过程，常见的推理方法有直接证明、反证法和归纳法。
三、图论图论是离散数学中的一个重要分支，它研究由节点和边组成的图形结构。
图形是由节点（或顶点）和边组成的抽象化模型，节点表示某个对象，边表示节点之间的关系。
图论研究图形的性质、特征和算法。
常见的图形类型有无向图和有向图，无向图的边没有方向，有向图的边有方向。
图形的表示方法有邻接矩阵和邻接表等。
在计算机科学中，图论广泛应用于网络、路径规划、数据结构等领域。
四、代数系统代数系统是离散数学中的另一个重要概念，它研究运算规则和运算对象之间的关系。
代数系统包括集合、运算和运算规则。
常见的代数系统有代数结构、半群、群、环、域等。
代数结构是指由一组元素和一组运算构成的系统，运算可以是加法、乘法或其他操作。
离散数学主析取范式主合取范式主析取范式和主合取范式是离散数学中逻辑表达式的两种常见形式。
它们在逻辑推理、计算机科学和人工智能等领域具有重要的应用价值。
本文将介绍主析取范式和主合取范式的概念、特性以及如何通过布尔运算将任意逻辑表达式转化为主析取范式或主合取范式。
一、主析取范式（DNF）主析取范式是一个逻辑表达式的标准形式，它由多个子句的析取组成。
每个子句由多个文字的合取构成。
主析取范式的最简形式是由至少一个子句组成的合取。
例如，逻辑表达式(A ∧ B) ∨ (C ∧ D ∧ E)就是一个主析取范式。
其中，(A ∧ B) 和 (C ∧ D ∧ E) 是两个子句，分别由 A、B 和 C、D、E 构成。
主析取范式的特性：1. 每个子句中的文字可以是变量或其否定形式。
2. 主析取范式中的每个文字都是变量的析取或否定析取。
3. 主析取范式可以使用布尔运算来简化和优化。
如何得到主析取范式？可以通过真值表法或布尔代数的演算法来将任意逻辑表达式转化为主析取范式。
方法如下：2. 找到真值表中使得逻辑表达式为真的行。
3. 对每一行，在真值为真的列上取出对应的文字，并将它们合取起来构成一个子句。
4. 将所有子句析取起来得到主析取范式。
二、主合取范式（CNF）主合取范式是一个逻辑表达式的标准形式，它由多个子句的合取组成。
每个子句由多个文字的析取构成。
主合取范式的最简形式是由至少一个子句组成的析取。
例如，逻辑表达式(A ∨ B) ∧ (C ∨ D ∨ E)就是一个主合取范式。
其中，(A ∨ B) 和 (C ∨ D ∨ E) 是两个子句，分别由 A、B 和 C、D、E 构成。
主合取范式的特性：1. 每个子句中的文字可以是变量或其否定形式。
2. 主合取范式中的每个文字都是变量的合取或否定合取。
3. 主合取范式可以使用布尔运算来简化和优化。
如何得到主合取范式？可以通过真值表法或布尔代数的演算法来将任意逻辑表达式转化为主合取范式。
离散数学范式的特征及其价值摘要：20世纪中叶以来, 随着计算机的诞生及其对科学与社会日渐显现的影响力, 离散数学的思想和方法迅速发展, 展现出了更为多样和充满活力的知识形态。
离散数学的知识创新具有典型的数学范式革命性。
作为对微积分范式的一种突破, 离散数学超越了传统数学的知识界线, 展现出在数学本体论、认识论与方法论上的新的哲学特征。
与计算机与信息科学的发展相得益彰, 离散数学范式具有离散化、算法化、计算性、复杂性以及与科学更为紧密的交互性等显着的当代科学革命特征, 并显现出学科知识群与复杂性科学等独特的意蕴。
关键词：离散数学; 范式革命; 图灵计算; 量子计算; 计算复杂性;Abstract：Since the middle of 20 thcentury, with the birth of computer and its increase effect on science and society, the thought and method of discrete mathematics have developed rapidly and new forms of knowledge with more multiple, tensions and vigor were emerged. The knowledge innovation of discrete mathematics has representative paradigm revolutionary character. As a breakthrough and transcending of the paradigm of calculus, the discrete mathematics has gone beyond the bound of traditional mathematics and showed new philosophical features in ontology, epistemology and methodology of mathematics. Complement with the development of computer and informationscience each other, the discrete mathematics demonstrated the contemporary scientific revolution features such as discretization, algorithmization, complexity and more tightly interaction with science, as well as the unique implication of group of disciplinary knowledge and complex science.Keyword：discrete mathematics; paradigm revolution; turing machine; quantum computation; computational complexity;20世纪中叶以来, 随着计算机的迅猛发展, 核心数学呈现出新的迹象。
一种异于微积分的数学新范式———离散数学喷薄而出, 成为推动当代数学与科学发展的一种主导力量。
离散数学是数学研究范式的一次重大转向。
与20世纪的科学进步和革命相互辉映, 在离散数学领域中持续发生的数学知识创新与革命性突破书写了20世纪以来绚丽多彩、恢宏壮观的科学画卷, 成为当代科学革命的重要标志之一, 具有重要的科学里程碑意义。
1、离散数学的知识创造及其发展20世纪中叶以来, 数学的知识进步呈现出新的特征, 它从单纯的知识量的积累转变为产生一系列具有革命性意义的知识变革。
而突破传统的微积分范式的知识创造也正在悄然发生。
其中尤其是以离散数学的崛起和兴盛最具范式革命性意义。
离散数学是数学中若干分支的总称, 研究的对象是基于离散空间而不是连续空间的数学结构。
离散数学的基本内容包括集合与数据结构、代数结构、计数理论、数值分析、数理逻辑、图论、自动机理论、递归函数、数论、组合数学、离散概率、计算群论、计算组合学、计算图论等。
更一般地说, 离散数学可以被视为建立在可数集合之上的数学分支。
与连续型数学模型相比, 由于计算机的运算在本质上是离散型的, 因而直接从实际问题建立离散的数学模型, 比传统上先建立连续的模型再予以离散化更为便捷。
如此, 离散数学就创制了一种迥然不同于微积分连续数学的新范式———离散数学的知识范式。
1.1、离散数学的理论准备与计算机时代“算法”的涵义离散数学的异军突起与计算机的诞生密不可分。
计算机的发明是人类科技史上一次重大的创造。
受到计算机迅猛发展的影响, 20世纪后半叶以来, 数学发展开始从较为单一的微积分主线中分离出来, 离散数学的思想方法由于其与计算机的紧密联系而日益受到数学共同体的青睐。
因为无论是具有多么强大功能的计算机, 也只能进行有限的计算和处理有限的数据。
而不能完成实在无限的过程。
这样, 微积分的思想和理论就不能直接用于计算机, 而必须做离散化的处理, 才能发挥其效力。
离散数学的兴起, 是数学知识创新与当代科学发展交互作用的共同结果。
作为一种新的数学范式, 离散数学在知识构成中有两个必备的数学理论条件。
第一个是集合论的语言与方法。
19世纪末集合论的诞生, 使得数学研究对象获得了极大的扩展。
在微积分范式中, 实数系(最多到复数系) 构成了所有理论的基础性平台。
在复变函数范式中, 复数系构成了其知识建构的平台。
20世纪以来, 集合论替代了以前的各种平台, 成为几乎所有新的数学分支的主要平台。
“对20世纪数学的另一个重大影响, 是康托尔在19世纪末把无穷集引入数学词汇。
许多长期存在的问题, 可以用集论提供的丰富语言来重新描绘或重新解决”[1]。
任何抽象的对象所构成的集合, 只要满足一定的条件、关系、规则和法则, 都可以成为数学的研究对象。
因此, 集合论堪称数学知识范式的一场革命。
集合论在离散数学具有特别重要的基础地位。
第二个是理论计算机的科学基础, 特别是其数学基础的形成、发展与成熟。
值得注意的是, 计算机科学中许多重要的理论基础是从曾被认为是极为抽象和缺乏现实意义的数理逻辑和形式主义数学的研究中逐步发展起来的。
例如数理逻辑, 20世纪30年代后, 随着哥德尔定理的诞生, 数理逻辑等纯粹数学研究出现了一些与理论计算机的诞生紧密相关的新的语境。
其中一个重要的方向就是对“算法”的研究。
“算法”有许多不同的定义, 其最朴素的含义是“一步接一步的方法”[2]。
在计算机时代, “算法”特指的是与计算机的程序运行相关的计算方法1。
1.2、“计算”作为离散数学核心概念的革命性演进:从可计算到超级计算20世纪后半叶以来, 以计算机的理论发展和应用为平台的离散数学体系开始迅猛发展, 并对传统的以连续数学为核心的数学知识结构与体系造成了巨大的挑战。
由于计算机本质上是离散型的机器, 因此, 随着计算机的发明, 离散数学的思想、观念和方法的重要性开始在20世纪中叶以来的数学研究中日益显现出来。
数学的核心领域发生的持续的知识更新与创造可谓日新月异。
以下就以离散数学中最核心的概念之一———“计算”概念作为其知识范例, 对离散数学的革命性演进予以分析。
如果一个函数可以在规定的程序内通过有限步计算达到所需要的结果, 那么这样的函数就被称为“可计算”的。
在这方面, 英国数学家图灵(A.M.Turing) 的工作是开创性的和最为引人注目的。
1936年, 剑桥大学国王学院年仅23岁的图灵发表了影响深远的论文“论可计算数及其在判定问题中的应用” (on computable numbers, with an application to the Entscheidungsproblem) 在这篇论文中, 图灵首次定义了“可计算数”的概念:“‘可计算’数可以简要地描述为其小数表达式可以通过有限方法加以计算的实数”[3]。
图灵可计算性(Turing computability) 和图灵机(Turing machine) 的概念由此诞生2。
图灵所研究的“可计算性” (computability) 以及图灵机TM (是Turing’s machines的缩写) 概念, 作为假想的理想机器, 图灵机奠定了最终导致计算机发明的理论基础。
随着理论计算机科学的不断发展, 人们又提出了“超计算” (hypercomputation) 的概念。
所谓“超计算”是指“无法在图灵意义(即一个计算者用纸和笔在有限步骤里进行的有效计算) 上进行计算的函数和数的计算”[5]。
而以超级计算概念设计的超级计算机(hypercomputer) 则超越了图灵机的范围, 能够进行更多的函数、数、问题解决和任何任务的计算。
1.3、量子计算与量子计算机引领离散数学发展的新方向近数十年来, 量子计算和量子计算机的概念开始逐步成为理论计算机科学研究的一个前沿。
英国数学家阿迪亚(M.Atiyah) 在着名的“20世纪的数学”一文中曾预测说:“21世纪将会是怎样的?我已经说了21世纪将会是量子数学的时代。
……量子数学可能意味着我们能够尽我们所能地理解分析、几何、拓扑和各种各样的非线性函数空间的代数”[6]。
