离散数学

三者是并列关系，属于数学中的不同一级学科。数学史，是讲数学历史文化的，属于科学史性质，比较偏文科。初等数论，是研究数论中比较经典的初等问题（注意，初等数论不代表理解起来初级简单，许多理论反而相当深奥）离散数学，是与计算机等联系最紧密的学科，知识概念一般都属于具体离散型（相对于连续数学而言）。

一般定义　　程序调用自身的编程技巧称为递归（ recursion）。 　　一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 　　注意： 　　(1) 递归就是在过程或函数里调用自身； 　　(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。其它定义　　递归的另一种定义： 　　递归，就是用自己的简单情况，定义自己。 　　在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。 　　例如，下列为某人祖先的递归定义： 　　某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波那契数列是典型的递归案例： 　　Fib(0) = 0 [基本情况] Fib(1) = 1 [基本情况] 对所有n > 1的整数：Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义] 尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如： 　　阶乘（1) = 1 [基本情况] 对所有n > 1的整数：阶乘（n) = (n * 阶乘（n-1)) [递归定义] 一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这是你已经知道该怎么做的。 　　如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。 德罗斯特效应　　德罗斯特效应是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片，进而小图片中还有更小的一幅她手持同一物体的图片，依此类推。 　　又例如，我们在两面相对的镜子之间放一根正在燃烧的蜡烛，我们会从其中一面镜子里看到一根蜡烛，蜡烛后面又有一面镜子，镜子里里又有一根蜡烛……这也是递归的表现。

你看看这个行不？　【摘要】离散数学是计算机科学基础理论的核心,本文介绍了离散数学在人工智能、数据结构、数据库等方面的应用,显示了离散数学在计算机科学中的重要性。 　　【关键词】人工智能 二叉树的遍历 数据库 　　　　 　　1 引言 　　离散数学是计算机专业的核心基础课,它在计算机科学中有着重要的应用。它是计算机专业课《数据结构》、《操作系统》、《编译原理》、《数据库系统原理》和《数字逻辑》等课的必备基础,因此离散数学是掌握计算机科学理论基础的重要数学工具。本文正是从这一角度出发,介绍离散数学在计算机科学中的重要应用。 　　 　　2 离散数学在计算机学科中的应用 　　2.1 数理逻辑在人工智能中的应用 　　人工智能是计算机学科中一个非常重要的方向,离散数学在人工智能中的应用主要是数理逻辑部分在人工智能中的应用。数理逻辑包括命题逻辑和谓词逻辑,命题逻辑就是研究以命题为单位进行前提与结论之间的推理,而谓词逻辑就是研究句子内在的联系。大家都知道,人工智能共有两个流派,连接主义流派和符号主义流派。其中在符号主义流派里,他们认为现实世界的各种事物可以用符号的形式表示出来,其中最主要的就是人类的自然语言可以用符号进行表示。语言的符号化就是数理逻辑研究的基本内容,计算机智能化的前提就是将人类的语言符号化成机器可以识别的符号,这样计算机才能进行推理,才能具有智能。由此可见数理逻辑中重要的思想、方法及内容贯穿到人工智能的整个学科。 　　2.2 图论在数据结构中的应用 　　离散数学在数据结构中的应用主要是图论部分在数据结构中的应用,树在图论中占着重要的地位。树是一种非线性数据结构,在现实生活中可以用树来表示某一家族的家谱或某公司的组织结构,也可以用它来表示计算机中文件的组织结构,树中二叉树在计算机科学中有着重要的应用。二叉树共有三种遍历方法:前序遍历法、中序遍历法和后序遍历法。 　　2.2.1 前序遍历法:如果二叉树为空,则返回。否则(1)访问根节点(2)前序遍历左子树(3)前序遍历右子树,得到前序序列。 　　2.2.2 中序遍历法:如果二叉树为空,则返回。否则(1)中序遍历左子树(2)访问根节点(3)中序遍历右子树,得到中序序列。 　　2.2.3 后序遍历法:如果二叉树为空,则返回。否则(1)后序遍历左子树(2)后序遍历右子树(3)访问根节点,得到后序序列。 　　通过访问不同的遍历序列,可以得到不同的节点序列,通常在计算机中利用不同的遍历方法读出代数表达式,以便在计算机中对代数表达式进行操作。 　　2.3 集合论在数据库系统理论中的应用 　　集合论是离散数学中极其重要的一部分,它在数据库中有着广泛的应用。我们可以利用关系理论使数据库从网络型、层次型转变成关系型,这样使数据库中的数据容易表示,并且易于存储和处理,使逻辑结构简单、数据独立性强、数据共享、数据冗余可控和操作简单。当数据库中记录较多时,集合中的笛卡儿积方便了记录的查询、插入、删除和修改。 　　2.4 代数系统在通信方面的应用 　　代数系统在计算机中的应用广泛,例如有限机,开关线路的计数等方面。但最常用的是在纠错码方面的应用。在计算机和数据通信中,经常需要将二进制数字信号进行传递,这种传递常常距离很远,所以难免会出现错误。通常采用纠错码来避免这种错误的发生,而设计的这种纠错码的数学基础就是代数系统。纠错码中的一致校验矩阵就是根据代数系统中的群概念来进行设计的,另外在群码的校正中,也用到了代数系统中的陪集。 　　2.5 离散数学在生物信息学中的应用 　　生物信息学是现代计算机科学中一个崭新的分支,它是计算机科学与生物学相结合的产物。目前,在美国有一个国家实验室Sandia国家实验室,主要进行组合编码理论和密码学的研究,该机构在美国和国际学术界有很高的地位。另外,由于DNA是离散数学中的序列结构,美国科学院院士,近代离散数学的奠基人Rota教授预言,生物学中的组合问题将成为离散数学的一个前沿领域。而且,IBM公司也将成立一个生物信息学研究中心。在1994年美国计算机科学家阿德勒曼公布了DNA计算机的理论,并成功地运用DNA计算机解决了一个有向哈密尔顿路径问题,这一成果迅速在国际产生了巨大的反响,同时也引起了国内学者的关注。DNA计算机的基本思想是:以DNA碱基序列作为信息编码的载体,利用现代分子生物学技术,在试管内控制酶作用下的DNA序列反应,作为实现运算的过程;这样,以反应前DNA序列作为输入的数据,反应后的DNA序列作为运算的结果,DNA计算机几乎能够解决所有的NP完全问题。 　　 　　3 结论 　　现在我国每一所大学的计算机专业都开设离散数学课程,正因为离散数学在计算机科学中的重要应用,可以说没有离散数学就没有计算机理论,也就没有计算机科学。所以,应努力学习离散数学,推动离散数学的研究,使它在计算机中有着更为广泛的应用。 　　 　　参考文献 　　[1] 耿素云,屈婉玲,离散数学[M].北京:高等教育出版社<1998. 　　[2] 左孝凌,李永监,刘永才编著.离散数学[M].上海:上海科学技术文献出版社,2004. 　　[3] 朱一清.离散数学[M].北京:电子工业出版社,2004

二元关系是指两个集合间的关系

A =｛x |1<=x <=3｝，R为实数集笛卡儿积AX R ={(a,b) |1<=a<=3，b属于任意实数}R XA ={(a,b) |a属于任意实数，1<=b<=3}

　　AxR={<x, y>|x∈A并且y∈R}，RxA={<x, y>|x∈R并且y∈A}　　在平面上表示就是，在平面上画一个数轴，在x=1的图像与x=3图像之间的所有部分就是AxR的图像，在在y=1的图像与y=3的图像之间的所有部分就是RxA的图像.

1.设x属于A,则(x,x)属于A×A,则(x,x)属于B×B,则x属于B,因此A包含于B同理,B包含于A故,A=B2.命题不正确设A={1,2,3},B={1},C={2}A×A={(11)(12)(13)(21)(22)(23)(31)(32)(33)}B×C={(12)}(A×A)-(B×C)={(11)(13)(21)(22)(23)(31)(32)(33)}(A-B)×(A-C)={{2,3}×{1,3}}={(21)(23)(31)(33)}显然不相等