离散数学是计算机学科的重要数学基础 课之 离散数学是以离散(即非连续)对象的数 量和空间关系为研究内容的数学若干个 分支的总称。 包括数理逻辑、近世代数、古典概率、 组合学、图论、集合论、数论、自动机 和形式语言、可计算性和可判定性、离 散几何等
离散数学是计算机学科的重要数学基础 课之一 离散数学是以离散(即非连续)对象的数 量和空间关系为研究内容的数学若干个 分支的总称。 包括数理逻辑、近世代数、古典概率、 组合学、图论、集合论、数论、自动机 和形式语言、可计算性和可判定性、离 散几何等
18世纪以前,数学基本上是研究离散对 象的数量和空间关系的科学, 之后,因天文学,物理学的发展,如行星轨 道,牛顿三大力学定律等研究,极大地推 动了连续数学(以微积分,数学物理方程, 实、复变函数论为代表)的发展。 离散对象的研究则处于停滞状态
18世纪以前, 数学基本上是研究离散对 象的数量和空间关系的科学, 之后,因天文学,物理学的发展,如行星轨 道,牛顿三大力学定律等研究,极大地推 动了连续数学(以微积分,数学物理方程, 实、复变函数论为代表)的发展。 离散对象的研究则处于停滞状态
20 0世纪30年代,图灵提出计算机的理论模 型图灵机。 这种模型早于实际制造计算机十多年, 现实的计算机的计算能力,本质上和图灵 机的计算能力一样。 这是理论指导实际的典型范例。 由于在计算机内,机器字长总是有限的 它代表离散的数或其它离散对象。 因此随着计算机科学和技术的迅猛发展, 离散数学就显得重要
20世纪30年代, 图灵提出计算机的理论模 型——图灵机。 这种模型早于实际制造计算机十多年, 现实的计算机的计算能力, 本质上和图灵 机的计算能力一样。 这是理论指导实际的典型范例。 由于在计算机内,机器字长总是有限的, 它代表离散的数或其它离散对象。 因此随着计算机科学和技术的迅猛发展, 离散数学就显得重要
离散数学是学习数据结构与算法、数据 库、编译原理、算法设计与分析、计算 机网络等课程的主要基础 对开发大型软件、研究信息安全和密码 学、开展计算机理论研究以及开发新型 计算机都提供了不可缺少的基础知识。 本课程是离散数学的一部分包括: 集合论 组合学 图论
离散数学是学习数据结构与算法、数据 库、编译原理、算法设计与分析、计算 机网络等课程的主要基础 对开发大型软件、研究信息安全和密码 学、开展计算机理论研究以及开发新型 计算机都提供了不可缺少的基础知识。 本课程是离散数学的一部分,包括： 集合论 组合学 图论
1集合论初步 集合论是现代数学的基础,它已深入到各种科 学和技术领域中被广泛应用到数学和计算机 科学的各分支中去。在开关理论、形式语言、 数据库等领域得到了卓有成效的应用。 集合论的创始人康托尔( Cantor,1845-1918) 德国著名数学家 在1874年,发表了题为“关于所有实代数数所 成集合的一个性质”的论文,开创了现代集 合论的研究,为现代数学奠定了基础
Ⅰ集合论初步 集合论是现代数学的基础,它已深入到各种科 学和技术领域中,被广泛应用到数学和计算机 科学的各分支中去。在开关理论、形式语言、 数据库等领域得到了卓有成效的应用。 集合论的创始人康托尔(Cantor,1845--1918), 德国著名数学家 在1874年,发表了题为“关于所有实代数数所 成集合的一个性质”的论文，开创了现代集 合论的研究，为现代数学奠定了基础
集合理论中出现了悖论。 为了解决集合论的悖论,上世纪初开始 了集合论公理学方向的研究,它是数理逻 辑的中心问题之一。 从集合的基本概念和例子着手,对关系、 函数、基数等进行讨论,并简单介绍集合 论的悖论
集合理论中出现了悖论。 为了解决集合论的悖论, 上世纪初开始 了集合论公理学方向的研究,它是数理逻 辑的中心问题之一。 从集合的基本概念和例子着手,对关系、 函数、基数等进行讨论,并简单介绍集合 论的悖论
第一章集合的基本概念 1.1集合的表示 所谓集合是指具有共同性质的一些东西(对象) 汇集成一个整体。 用大写英文字母表示,例如S,A等 构成一个集合中的那些对象称为该集合的元素 用小写英文字母或数字等表示。 a∈A表示a是集合A的元素。 agA表示a不是集合A的元素
第一章 集合的基本概念 1.1 集合的表示 所谓集合是指具有共同性质的一些东西(对象) 汇集成一个整体。 用大写英文字母表示,例如S,A等。 构成一个集合中的那些对象称为该集合的元素, 用小写英文字母或数字等表示。 aA表示a是集合A的元素。 aA表示a不是集合A的元素
例:所有整数全体构成的集合,记为Z, 则3∈Z,8∈Z,6.5∈Z, 今后我们将用 I或Z表示整数集; I(Z+)表示正整数集; Q表示有理数集; Q表示正有理数集; Q表示负有理数集 R表示实数集; R表示正实数集
例：所有整数全体构成的集合，记为Z, 则3Z,-8Z,6.5Z, 今后我们将用 I或Z表示整数集; I + (Z+ )表示正整数集; Q表示有理数集; Q+表示正有理数集; Q-表示负有理数集; R表示实数集; R+表示正实数集
集合中的元素可以是具体的事物也可以 是抽象的符号 一、集合的表示方法 (1)列举法:列出集合中的所有元素来表 示一个集合。 例:集合A的元素为1,3,5,7,9, 则A可表示为A={1,3,5,7,9} B={x1,X2X3}也是采用了列举法
集合中的元素可以是具体的事物,也可以 是抽象的符号 一、集合的表示方法 (1)列举法：列出集合中的所有元素来表 示一个集合。 例：集合A的元素为1, 3, 5, 7, 9, 则A可表示为A={1, 3, 5, 7, 9}。 B={x1 ,x2 ,x3 }也是采用了列举法
(2) 特性刻画法(描述法):描述集合中元素具有 共同性质的方法来表示某个集合。 我们用P(A)表示元素a满足特性P,则 A={aP(a)}就表示集合A是所有使P(a)成立的元 素所构成的集合。 例:C={xx=y3,y∈Z} D={x-1<x<2} E={xx为年龄小于20岁的人} 列举法用于元素个数较少的情况, 描述法用于元素个数较多或无限且各对象具 有共同性质的情况
(2)特性刻画法(描述法)：描述集合中元素具有 共同性质的方法来表示某个集合。 我们用 P(A) 表示元素 a 满 足 特 性 P， 则 A={a|P(a)}就表示集合A是所有使P(a)成立的元 素所构成的集合。 例：C={x|x=y3 ,yZ+ } D={x|-1<x<2} E={x|x为年龄小于20岁的人} 列举法用于元素个数较少的情况, 描述法用于元素个数较多(或无限),且各对象具 有共同性质的情况