离散数学的研究对象

1、离散数学的研究对象 由于数字电子计算机是一个离散结构 它只 能处理离散的或离散化了的数量关系 因此 无论计算机科学本身 还是与计算机科学 及其应用密切相关的现代科学研究领域 都 面临着如何对离散结构建立相应的数学模型 又如何将已用连续数量关系建立起来的数 学模型离散化 从而可由计算机加以处理 离散数学 Discrete Mathematics 是计算机专业 的一门重要基础课 它所研究的对象是离散 数量关系和离散结构数学结构模型 离散数学的主要内容 到目前为止 离散数学所研究的精确范围并 没有严格的定义 它和其它许多纯粹数学以 及应用数学分支之间有着广泛的交叉和相互 渗透 但是作为给计算机专业本科生开设的 一门专业基础课 其内容相对来说较为明确 主要包括数理逻辑 集合论 代数系统以 及图论等几部分 离散数学是数字电路 编译原理 数据结构 操作系统 数据库系统 算法的分析与设 计 人工智能 计算机网络等专业课程的基 础 数理逻辑 数理逻辑是用数学的方法研究关于推理 证 明等问题的学科 也叫做符号逻辑 它的本 质是研究如何通过利用纯粹的公理系统和符 号演算以及推理方法来代替人们思维中的逻 辑

2、推理过程 并由此将整个的数学建立在这 样一个逻辑基础之上 历史上诸多数学家的努力和推动 尤其是莱 布尼茨 布尔 希尔伯特 罗素 图灵 哥 德尔等人的工作 部分地实现了这一形式化 数学的梦想 但同时也发现了数学基础本身 存在的巨大困难 集合论 集合论是德国著名数学家康托尔于19世纪末 创立的 康托对于无穷集元素个数问题进行 了卓越的研究 引领数学研究进入了一个全 新的领域 他提出用一一对应准则来比较无 穷集元素的个数 将元素间能建立一一对应 的集合称为个数相同 也称作等势 并证 明了无穷集的势之间存在着差别 有着不同 的数量级 可分为不同的层次 问题 试判断自然数集合 x x 1 2 3 和奇 数集合 x x 1 3 5 哪个集合的元素个数多 图论 图论 是数学的一个分支 它以图为研究对 象 图论中的图是由若干给定的点及连接两 点的线所构成的图形 这种图形通常用来描 述某些事物之间的某种特定关系 用点代表 事物 用连接两点的线表示相应两个事物间 具有这种关系 图论起源于著名的柯尼斯堡七桥问题 欧拉 在1736年解决了这个问题 他用抽象分析法 将这个问题化为第一个图论问题 欧拉证明 了柯尼

3、斯堡七桥问题是无解的 并推广了这 个问题 给出了对于一个给定的图可以某种 方式走遍的判定法则 这使得欧拉成为图论 及拓扑学 的创始人 学习离散数学的方法 概念定理多 首先要精确严格地掌握好概念 和术语 正确理解他们的内涵和外延 因为 公理 定理或定律的基石都是概念 只有正 确地理解了概念 才能把握定理的实质 熟 练地将公理 定理应用于解决问题 抽象思维多 完全的 精确的掌握一个概念 的好主意是首先要深刻理解概念的内涵 然 后举一些属于和不属于该概念外延的正反两 方面的实例 如果对一些似是而非的例子也 能辨别的话 应该说这个概念正真理理解了 只需要中学数学基础 第一部分 数理逻辑 先看著名物理学家爱因斯坦出过的一道题 一个土耳其商人想找一个十分聪明的助手协助他经商 有两 人前来应聘 这个商人为了试试哪个更聪明些 就把两个人带 进一间漆黑的屋子里 他打开灯后说 这张桌子上有五顶帽 子 两顶是红色的 三顶是黑色的 现在 我把灯关掉 而且 把帽子摆的位置弄乱 然后我们三个人每人摸一顶帽子戴在自 己头上 在我开灯后 请你们尽快说出自己头上戴的帽子是什 么颜色的 说完后 商人将电灯关掉 然后三人都

4、摸了一顶 帽子戴在头上 同时商人将余下的两顶帽子藏了起来 接着把 灯打开 这时 那两个应试者看到商人头上戴的是一顶红帽子 其中一个人便喊道 我戴的是黑帽子 请问这个人说得对吗 他是怎么推导出来的呢 要回答这样的问题 实际上就是看由一些诸如 商人戴的 是红帽子 这样的前提能否推出 猜出答案的应试者戴的是 黑帽子 这样的结论来 这又需要经历如下过程 1 什么是前提 有哪些前提 2 结论是什么 3 根据什么进行推理 4 怎么进行推理 下面的第一章 第二章回答第一个问题 第三章回答第 二 三个问题 下图给出了逻辑部分的知识体系 例1 1 判断下列句子是否为命题 1 4是素数 2 是无理数 3 x大于y 4 月球上有冰 5 2100年元旦是晴天 6 大于吗 7 请不要吸烟 8 这朵花真美丽啊 9 我正在说假话 能判定真假的陈述句称为命题 作为命题的陈述句所表达的判断结果称为命题的真值 真 值只取两个值 真或假 真值为真的命题称为真命题 真 值为假的命题称为假命题 任何命题的真值都是唯一的 判断给定句子是否为命题 应该分两步 首先判定它是否 为陈述句 其次判断它是否有唯一的真值 解 本题的 9 个

5、句子中 6 是疑问句 7 是祈使句 8 是感 叹句 因而这3个句子都不是命题 剩下的6个句子都是陈述 句 但 3 无确定的真值 根据x y的不同取值情况它可真可 假 即无唯一的真值 因而不是命题 若 9 的真值为真 即 我正在说假话 为真 也就是 我正在说真话 则又推出 9 的真值应为假 反之 若 9 的真值为假 即 我正在说假话 为假 也就是 我正在说假话 则又推出 9 的真值应为真 于是 9 既不为真又不为假 因此它不是命题 像 9 这样由 真推出假 又由假推出真的陈述句称为悖论 凡是悖论都不 是命题 本例中 只有 1 2 4 5 是命题 1 为假命 题 2 为真命题 虽然今天我们不知道 4 5 的真值 但 它们的真值客观存在 而且是唯一的 将来总会知道 4 的真 值 到2100年元旦 5 的真值就真相大白了 罗素悖论 一天 萨维尔村理发师挂出一块招牌 村里 所有不自己理发的男人都由我给他们理发 我也只给这些人理发 于是有人问他 您 的头发由谁理呢 理发师顿时哑口无言 因为 如果他给自己理发 那么他就属于自 己给自己理发的那类人 但是 招牌上说明 他不给这类人理发 因此他不能自己理

6、 如 果由另外一个人给他理发 他就是不给自己 理发的人 而招牌上明明说他要给所有不自 己理发的男人理发 因此 他应该自己理 由此可见 不管怎样的推论 理发师所说的 话总是自相矛盾的 有趣的对话 甲对乙说 你会回答我 不对 对不对 请用 对 或 不对 来回 答 例1 2 是有理数是不对的 2是偶素数 2或4是素数 如 果2是素数 则3也是素数 2是素数当且仅当3也是素数 全是命题 定义1 1 设p为命题 复合命题 非p 或 p的否定 称为p的否 定式 记作 p 符号 称作否定联结词 并规定 p为真当且 仅当p为假 定义1 2 设p q为二命题 复合命题 p并且q 或 p与q 称为p 与q的合取式 记作p q 称作合取联结词 并规定p q 为真当且仅当p与q同时为真 定义1 3 设p q为二命题 复合命题 p或q 称作p与q的析取 式 记作p q 称作析取联结词 并规定p q为假当且仅 当p与q同时为假 注意 按定义1 3在析取式p q中 若p q都为真 则p q 为真 或 还有另外一种用法 当p q都为真时 析取起来 为假 前者称为相容或 后者称为排斥或 排异或 例1 3 将下列命题符号

7、化 1 张晓静爱唱歌或爱听音乐 2 张晓静是江西人或安徽人 3 张晓静只能挑选202或203房间 解 在解题时 先将原子命题符号化 1 p 张晓静爱唱歌 q 张晓静爱听音乐 显然 1 中 或 为相容或 即p与q可以同时为真 符号化为 p q 2 r 张晓静是江西人 s 张晓静是安徽人 易知 2 中 或 应为排斥或 但r与s不能同时为真 因而 也可以符号化为r s 3 t 张晓静挑选202房间 u 张晓静挑选203房间 由题意可知 3 中 或 应为排斥或 t u的联合取值情况 有四种 同真 同假 一真一假 两种情况 如果也符号化 为t u 张晓静就可能同时得到两个房间 这违背题意 因 而不能符号化为t u 如何达到只能挑一个房间的要求呢 可 以使用多个联结词 符号化为 t u t u 定义1 4 设p q为二命题 复合命题 如果p 则q 称作p与q 的蕴涵式 记作p q 称作蕴涵联结词 并规定p q为假 当且仅当p为真q为假 注意 在使用联结词 时 要特别注意以下几点 1 在自然语言里 特别是在数学中 q是p的必要条件有许多不同的叙 述方式 例如 只要p 就q 因为p 所以q p仅当q

8、只有q才p 除非q才p 除非q 否则非p 等等 以上各种叙述方式表面看来有 所不同 但都表达的是q是p的必要条件 因而所用联结词均应符号化为 上述各种叙述方式都应符号化为p q 2 在自然语言中 如果p 则q 中的前件p与后件q往往具有某种内在 联系 而在数理逻辑中 p与q可以无任何内在联系 3 在数学或其它自然科学中 如果p 则q 往往表达的是前件p为真 后件q也为真的推理关系 但在数理逻辑中 作为一种规定 当p为假 时 无论q是真是假 p q均为真 也就是说 只有p为真q为假这一种情 况使得复合命题p q为假 定义1 5 设p q为二命题 复合命题 p当且仅当q 称作p与q 的等价式 记作p q 称作等价联结词 并规定p q为真 当且仅当p与q同时为真或同时为假 以上定义了五种最基本 最常用 也是最重要的联结词 将它们组成一个集合 称为一个联结词集 其中 为一元联结词 其余的都是 二元联结词 通常用1表示真 用0表示假 复合命题的真假值如表1 1 表1 1 基本复合命题的真值 联结词可以嵌套使用 在嵌套使用时 规定如下优先顺序 对于同一优先级的联结词 先 出现者先运算 例1 7 令 p 北京比天津人口多 q 2 2 4 r 乌鸦是白色的 求下列复合命题的真值 1 p q p q r 2 q r p r 3 p r p r 解 p q r的真值分别为1 1 0 容易算出 1 2 3 的 真值分别为1 1 0

《离散数学的研究对象》由会员简****9分享，可在线阅读，更多相关《离散数学的研究对象》请在金锄头文库上搜索。