离 散 数 学 教 程 ( 集 合 论 与 图 论 ) 离 散 数 学 : 计 算 机 科 学 与 技 术 的 数 学 基 础 课 内 容 : 集 合 论, 图 论, 组 合 数 学, 代 数 结 构, 数 理 逻 辑 集 合 论 :( 第 1-4 章 ) 组 合 数 学 初 步 :( 第 5-7 章 ) 图 论 :( 第 8-11 章 )
教 师 介 绍 教 师 : 吴 永 辉 博 士 副 教 授 简 历 : 1984-1988 上 海 科 技 大 学 计 算 机 系 本 科 1988-1991 复 旦 大 学 计 算 机 系 硕 士 1991-2003 华 东 师 范 大 学 计 算 机 系 工 作 1998-2001 复 旦 大 学 计 算 机 系 博 士 2003- 复 旦 大 学 计 算 机 系 工 作 答 疑 E-mail: yhwu@fudan.edu.cn
集 合 论 与 图 论 课 件 制 作 软 件 Microsoft PowerPoint MathType Equation
集 合 论 与 图 论 课 程 大 纲 课 程 性 质 与 目 的 教 学 内 容 与 要 求 使 用 教 材 参 考 书 籍 命 题 说 明 和 题 型
课 程 性 质 目 的 与 基 本 要 求 课 程 性 质 本 课 程 讲 授 计 算 机 科 学 与 技 术 的 数 学 基 础 课 离 散 数 学 的 部 分 主 要 内 容 : 集 合 论 图 论 与 组 合 数 学 初 步, 是 计 算 机 专 业 的 主 干 课 程 之 一 本 课 程 前 行 课 程 为 线 性 代 数, 数 学 分 析 ( 上 ) 课 程 目 的 使 学 生 掌 握 集 合 论 图 论 与 组 合 数 学 初 步 的 基 本 内 容, 并 对 证 明 的 思 想 和 方 法 深 入 理 解 和 体 会, 初 步 培 养 学 生 的 思 维 过 程 的 数 学 化
基 本 要 求 : 掌 握 集 合 论 组 合 学 和 图 论 的 基 本 概 念, 清 楚 了 解 引 入 基 本 概 念 的 实 际 背 景 各 概 念 间 相 互 关 系 ; 掌 握 基 本 定 理 以 及 有 关 理 论 题 的 证 明 技 巧 ; 掌 握 解 决 计 数 问 题 的 基 本 方 法 和 技 巧 ; 掌 握 图 论 中 各 算 法 设 计 的 思 想 正 确 性 证 明 以 及 算 法 的 应 用 为 进 一 步 学 习 计 算 机 其 他 课 程 打 下 坚 实 的 基 础
教 学 方 式 本 课 程 以 课 堂 讲 授 为 主
考 核 方 式 平 时 作 业 ; 集 合 论 组 合 数 学 和 图 论 3 次 课 堂 练 习 ; 期 中, 期 末 的 两 次 笔 试 考 试
教 学 内 容 与 要 求 ---- 集 合 论 第 一 章 集 合 的 基 本 概 念 掌 握 : 集 合 的 基 本 概 念, 集 合 的 运 算 了 解 : 集 合 论 的 悖 论 掌 握 证 明 两 个 集 合 相 等 的 基 本 法 和 公 式 法 第 二 章 关 系 掌 握 : 关 系 的 性 质 运 算 和 关 系 的 闭 包, 以 及 等 价 关 系 和 偏 序 关 系 了 解 : 关 系 在 关 系 数 据 库 中 的 应 用 掌 握 证 明 的 类 型
第 三 章 函 数 掌 握 : 函 数 的 基 本 概 念, 复 合 函 数 和 逆 函 数 了 解 : 集 合 的 特 征 函 数 第 四 章 无 限 集 掌 握 : 基 数 及 基 数 的 比 较, 判 断 可 列 集 与 不 可 列 集 的 方 法 了 解 : 集 合 的 递 归 定 义
教 学 内 容 与 要 求 ---- 组 合 数 学 初 步 第 五 章 鸽 笼 原 理 掌 握 : 利 用 鸽 笼 原 理 解 决 组 合 数 学 中 一 些 存 在 性 问 题 的 技 巧 第 六 章 排 列 与 组 合 掌 握 : 集 合 的 排 列 与 组 合, 多 重 集 的 排 列 与 组 合 等 计 数 方 法, 有 序 划 分 和 无 序 划 分 第 七 章 生 成 函 数 与 递 推 关 系 掌 握 : 用 生 成 函 数 和 递 推 关 系 解 决 组 合 计 数 问 题 的 方 法, 以 及 求 解 递 推 关 系 的 生 成 函 数 方 法 了 解 : 求 解 递 推 关 系 的 特 征 根 方 法
教 学 内 容 与 要 求 ---- 图 论 第 八 章 图 的 基 本 概 念 掌 握 : 图 的 基 本 术 语, 路 回 路 和 连 通 的 基 本 概 念, 求 最 短 路 的 算 法 及 算 法 正 确 性 证 明, 欧 拉 图 和 哈 密 顿 图 的 基 本 概 念 判 别 方 法 以 及 有 关 定 理 第 九 章 平 面 图 与 图 的 着 色 掌 握 : 平 面 图 的 基 本 概 念 平 面 图 的 特 征 和 欧 拉 公 式, 掌 握 图 的 点 着 色 和 平 面 图 的 面 着 色 概 念 了 解 : 图 的 边 着 色 概 念 树 掌 握 : 树 的 基 本 性 质 和 生 成 树 割 集 有 根 树 的 概 念, 求 最 小 生 成 树 和 最 优 树 的 算 法 及 算 法 的 正 确 性 证 明 了 第 十 章 解 : 树 的 计 数 问 题
教 学 内 容 与 要 求 ---- 图 论 第 十 一 章 连 通 度 网 络 与 匹 配 教 学 时 间 :10 学 时 ; 掌 握 : 点 连 通 度 和 边 连 通 度 的 基 本 概 念, 掌 握 最 大 网 络 流 算 法 及 算 法 正 确 性 证 明, 掌 握 匹 配 的 基 本 概 念 和 判 别 方 法, 掌 握 独 立 集 和 覆 盖 的 基 本 概 念 和 有 关 定 理 及 证 明 方 法 了 解 : 佩 特 里 网 及 其 图 的 表 示
使 用 教 材 离 散 数 学, 赵 一 鸣, 阚 海 斌, 吴 永 辉 编 著 人 民 邮 电 出 版 社,2011
参 考 书 籍 一 基 础 [1] Bernard Kolman, etc.. Discrete Mathematical Structure, Third Edition. 1997. 清 华 大 学 出 版 社, Prentice Hall. ( 中 英 文 版 ) [2] 左 孝 凌, 李 为 槛, 刘 永 才. 离 散 数 学 理 论 分 析 题 解 1988, 上 海 科 技 文 献 出 版 社 [3] 左 孝 凌, 李 为 槛, 刘 永 才. 离 散 数 学 1988, 上 海 科 技 文 献 出 版 社
二 提 高 [4] Kenneth H. Rosen. Discrete Mathematics and its Applications. (4th, 5th Edition). 机 械 工 业 出 版 社, McGraw-Hill. ( 中 英 文 版 ) [5] 吴 永 辉, 王 建 德 数 据 结 构 编 程 实 验 : 大 学 程 序 设 计 课 程 与 竞 赛 训 练 教 材 ( 附 光 盘 ) 机 械 工 业 出 版 社 2012
参 考 课 件 [1] Discrete Mathematics and Its Applications 课 件
在 线 学 习 网 站 [1] 北 京 大 学 计 算 机 系 离 散 数 学 教 程 网 上 教 室 http://necweb.neu.edu.cn/ncourse/lssx/index.htm [2] 北 京 邮 电 大 学 离 散 数 学 在 线 课 件 http://www.pris.edu.cn/lesson/dis-math/content.htm [3] 国 立 交 通 大 学 离 散 数 学 电 脑 辅 助 教 学 CAI ( 台 湾 ) http://www.cis.nctu.edu.tw/~is83039/discre t/discrete.html
在 线 计 算 机 和 数 学 类 书 库 计 算 机 和 数 学 类 书 库 http://www.infoxa.com/asp/book/cx.asp 吉 林 大 学 的 藏 经 阁 elmo 站 : http://elmo.jlu.edu.cn/
理 论 计 算 机 科 学 经 典 网 站 国 内 : http://algorithm.lzu.edu.cn 国 际 : http://robotics.stanford.edu/~suresh/theory/the ory-home.html
命 题 说 明 和 题 型 1 填 空 题 : 基 本 概 念 的 理 解 和 掌 握 2 判 断 题 : 概 念 的 掌 握 与 应 用 3 计 算 证 明 题 : 概 念 的 综 合 应 用, 数 学 方 法 的 运 用
集 合 论 集 合 论 是 现 代 数 学 的 基 础, 它 已 深 入 到 各 种 科 学 和 技 术 领 域 中, 被 广 泛 应 用 到 数 学 和 计 算 机 科 学 的 各 分 支 中 去 集 合 论 的 创 始 人 : 康 托 尔 (Cantor,1845--1918), 1874 年, 关 于 所 有 实 代 数 数 所 成 集 合 的 一 个 性 质 的 论 文 理 论 中 出 现 了 悖 论 为 解 决 悖 论, 在 20 世 纪 初 开 始 了 集 合 论 公 理 学 方 向 的 研 究, 它 是 数 理 逻 辑 的 中 心 问 题 之 一 ( 本 书 避 免 用 集 合 的 公 理 化 方 法, 直 观 地 介 绍 朴 素 集 合 论 )
集 合 论 部 分 提 高 参 考 书 籍 沈 恩 绍 集 论 与 逻 辑 ---- 面 向 计 算 机 科 学 科 学 出 版 社 集 合 论 部 分 内 容 与 常 规 教 材 相 似, 强 调 公 理 化
图 论 图 论 提 供 了 一 个 自 然 的 结 构, 由 此 产 生 的 数 学 模 型 几 乎 适 合 于 所 有 科 学 ( 自 然 科 学 与 社 会 科 学 ) 领 域, 只 要 这 个 领 域 研 究 的 主 题 是 对 象 与 对 象 之 间 的 关 系
图 论 部 分 提 高 参 考 书 籍 Bela Bollobas. Modern Graph Theory ( 现 代 图 论 ). 科 学 出 版 社 & Springer. 2001.
组 合 数 学 1666 年 莱 布 尼 兹 所 著 组 合 学 论 文 一 书 问 世, 这 是 组 合 数 学 的 第 一 部 专 著 书 中 首 次 使 用 了 组 合 论 (Combinatorics) 一 词 组 合 数 学 的 蓬 勃 发 展 则 是 在 计 算 机 问 世 和 普 遍 应 用 之 后 由 于 组 合 数 学 涉 及 面 广, 内 容 庞 杂, 并 且 仍 在 很 快 地 发 展 着, 因 而 还 没 有 一 个 统 一 而 有 效 的 理 论 体 系 这 与 数 学 分 析 形 成 了 对 照
组 合 数 学 部 分 提 高 参 考 书 籍 Richard A.Brualdi. Introductory Combinatorics (3E),( 组 合 数 学 ( 第 3 版 ), ( 冯 舜 玺 等 译 )), 机 械 工 业 出 版 社, 2002.
第 一 章 集 合 的 基 本 概 念 1.1 集 合 的 表 示 1.2 集 合 的 子 集 1.3 笛 卡 尔 积 1.4 集 合 的 运 算 1.5 罗 素 悖 论
引 言 : 什 么 是 集 合? 一 些 自 行 车 在 计 算 机 系 车 棚 内 的 自 行 车
一 些 自 行 车 不 是 集 合, 无 法 确 定 范 围 和 性 质 在 计 算 机 系 车 棚 内 的 自 行 车 是 集 合, 可 以 确 定 范 围 和 性 质
1.1 集 合 的 表 示 一 集 合 的 定 义 <1> 集 合 : 具 有 共 同 性 质 的 一 些 东 西 汇 集 成 一 个 整 体 例 : 复 旦 大 学 教 师 <2> 元 素 : 构 成 一 个 集 合 中 的 那 些 对 象 a A a 是 A 的 元 素,a 属 于 A a A a 不 是 A 的 元 素,a 不 属 于 A 例 : 吴 永 辉 复 旦 大 学 教 师, 沈 恩 绍 复 旦 大 学 教 师 常 用 大 写 字 母 表 示 集 合, 小 写 字 母 或 数 字 表 示 元 素
1.1 集 合 的 表 示 二 集 合 的 表 示 <1> 列 出 集 合 中 的 元 素 :A={1,3,5,7,9} <2> 描 述 集 合 中 元 素 具 有 的 共 同 性 质 2 { x p(x) }: A { x x 1 0} <3> 通 过 某 规 则 的 计 算 来 定 义 集 合 中 的 元 素
1.1 集 合 的 表 示 三 术 语 <1> 空 集 : 不 含 任 何 元 素 的 集 合, 记 为 <2> 有 / 无 限 集 : 集 合 中 有 有 限 个 元 素 / 否 则.. 有 限 集 A 的 元 素 个 数 称 为 集 合 A 的 基 数, 记 为 A 集 合 中 元 素 之 间 的 次 序 是 无 关 紧 要 的 <3> 多 重 集 : 集 合 中 元 素 可 以 重 复 出 现 <4> 集 合 族 : 以 集 合 为 元 素 组 成 的 集 合 <5> 与 { } 是 不 同 的 : { } 表 示 以 为 元 素 的 集 合
例 : 设 A, B, C 是 任 意 3 个 集 合, 如 果 A B, B C, 则 A C 可 能 吗? A C 常 真 吗? 举 例 说 明 /* 集 合 论 题 集, 经 典 习 题, 集 合 基 础 */
1.2 集 合 的 子 集 一 文 氏 图 : 用 平 面 上 封 闭 曲 线 包 围 点 集 的 图 形 来 表 示 集 合 图 1.1, 图 1. 2
二 定 义 1.1( 子 集 ) 集 合 A, B,A 的 每 一 元 素 都 是 B 的 元 素, 则 A 是 B 的 子 集 A B 或 B A 特 别 :A A 此 外, 若 存 在 元 素 a A, 但 a B, 则 A 不 是 B 的 子 集.
三 定 义 1.2( 集 合 相 等 与 不 相 等 ): 集 合 A 和 B 的 元 素 全 相 同, 则 称 A 和 B 相 等,A=B; 否 则 称 A 和 B 不 相 等,A B
定 理 1.1 A=B A B 并 且 B A
1.2 集 合 的 子 集 证 明 的 方 法 定 理 1.1: A=B A B 并 且 B A 当 且 仅 当 : 证 明 由 两 部 分 组 成 : 1) 由 条 件 证 明 结 论 A=B A B 并 且 B A 2) 由 结 论 证 明 条 件 A B 并 且 B A A=B
证 明 : A=B A B 并 且 B A 因 为 A=B, 由 定 义 A 中 的 每 个 元 素 是 在 B 中, 所 以 A B, 同 理 B 中 的 每 个 元 素 是 在 A 中, 所 以 B A A B 并 且 B A A=B 反 证, 如 果 A B, 则 A 中 至 少 有 一 个 元 素 不 在 B 中, 与 A B 矛 盾 ; 或 者 B 中 至 少 有 一 个 元 素 不 在 A 中, 与 B A 矛 盾 所 以 A B 不 可 能 成 立 所 以 A=B
四 定 义 1.3( 真 子 集 ):A B 并 且 A B, 则 A B ( 和 不 同 : 元 素 集 合 ; 集 合 集 合 )
例 : 设 A, B, C 是 集 合, 判 断 下 列 命 题 真 假, 如 果 为 真, 给 出 证 明 ; 如 果 为 假, 给 出 反 例 : 1) A B, B C A C; 2) A B, B C A C; 3) A B, B C A C; 4) A B, B C A C; 5) a A, A B a B. /* 集 合 论 题 集, 经 典 习 题, 集 合 基 础 */
五 定 义 1.4( 全 集 ): 在 取 定 一 个 集 合 U 以 后, 对 于 U 的 任 何 子 集 而 言, 称 U 为 全 集
定 理 1.2: (1) A (2) A A (3) A U
1.2 集 合 的 子 集 证 明 的 方 法 证 明 :(1) A (2) A A (3) A U (1) 反 证 法 : 假 设 结 论 不 成 立, 导 出 矛 盾 结 果 不 是 A 的 子 集, 导 致 矛 盾 (2,3) 基 本 法 : 由 子 集 定 义 x 左 x 右, 则 左 右
证 明 :(1) A 假 设 不 是 A 的 子 集, 则 至 少 有 一 个 元 素 x, 使 得 x 且 x A 又 因 为 是 空 集, 它 没 有 元 素, 所 以 对 任 何 x, 必 有 x, 导 致 矛 盾 因 此 是 集 合 A 的 子 集
反 证 法 的 证 明 步 骤 (1) 假 设 命 题 的 结 论 不 成 立 ; (2) 进 行 一 系 列 的 推 理 ; (3) 推 理 过 程 中 出 现 下 列 情 况 中 的 一 种 : 1) 与 已 知 条 件 矛 盾 ; 2) 与 公 理 矛 盾 ; 3) 与 已 知 定 理 矛 盾 ; (4) 由 于 上 述 矛 盾 的 出 现, 可 以 断 言, 原 来 的 假 定 结 论 不 成 立 是 错 误 的 (5) 肯 定 原 来 命 题 是 正 确 的
反 证 法 的 思 想 / 思 维 过 程 结 论 不 成 立 与 结 论 成 立 必 有 一 个 正 确 结 论 不 成 立 会 导 致 出 现 错 误, 推 理 过 程 已 知 条 件 公 理 和 已 知 定 理 没 有 错 误, 惟 一 有 错 误 的 是 一 开 始 接 假 定 的 结 论 不 成 立, 所 以 结 论 不 可 能 不 成 立, 即 结 论 成 立
1.2 集 合 的 子 集 六 定 义 1.5( 幂 集 ): A 的 所 有 子 集 组 成 的 集 合 称 为 A 的 幂 集 记 为 P(A) 例 1.1( 已 知 A, 求 幂 集 ) 定 理 1.3 P(A) =2 A 证 明 方 法 : 组 合 的 方 法
求 幂 集 代 数 法 P13 习 题 1.13 设 A={a, {a}}, 问 : (1) {a} P(A)? {a} P(A)? (2) {{a}} P(A)? {{a}} P(A)? (3) 又 设 A={a, {b}}, 重 复 (1) (2) 解 : (1, 2) 首 先 求 P(A), 代 数 法 : 代 入 : 设 x={a}, 则 A={a, x}; P(A)={, {a}, {x}, {a, x}}; 回 代 : P(A)={, {a}, {{a}}, {a, {a}}}
P(A)={, {a}, {{a}}, {a, {a}}} (1) {a} P(A) {a} P(A) (2) {{a}} P(A) {{a}} P(A) (3) 同 理, 用 代 入 法, 设 x={b}, 则 A={a, x}; 回 代 : P(A)={, {a}, {{b} }, {a, {b}}}, 则 {a} P(A),{a} P(A), {{a}} P(A),{{a}} P(A)
1.3 笛 卡 尔 积 一 定 义 1.6( 有 序 对 ) 两 个 对 象 按 一 定 次 序 组 成 一 对, 称 为 有 序 对 (a, b) (a, b)=(c, d) a=c 和 b=d
二 定 义 1.7( 有 序 n 元 组 ) n 个 对 象 的 序 列 a 1, a 2,,a n 组 成 一 组 称 为 有 序 n 元 组, 记 为 (a 1, a 2,,a n ), 其 中 a i 称 为 第 i 个 分 量 两 个 有 序 n 元 组 相 等 每 个 对 应 分 量 相 等
1.3 笛 卡 尔 积 三 定 义 1.8( 直 积 ) 两 个 集 合 A 和 B, 定 义 A 和 B 的 笛 卡 尔 积 为 A B={(a, b) a A, b B}, 又 称 A B 为 A 和 B 的 直 积
1.3 笛 卡 尔 积 四 定 义 1.9( 笛 卡 尔 积 ) n 个 集 合 A 1, A 2,, A n, A 1 A 2 A n ={(a 1, a 2,,a n ) a i A i, i=1,, n} 若 对 所 有 i,a i =A, 则 A 1 A 2 A n 记 为 A n
1.4 集 合 的 运 算 一 定 义 1.10 ( 并, 交, 差, 补, 对 称 差 ) (1) A B={x x A 或 x B} (2) A B={x x A 且 x B} (3) A-B={x x A 且 x B} (4) Ã=U-A (5) A B=(A-B) (B-A)
例 集 合 运 算 :A={1,2,3,4,5}, B={1,2,4,6}, C={7,8}, U={1,2,3,4,5,6, 7,8,9,10} A B={1,2,3,4,5,6}, A B={1,2,4}, A C=, A-B={3,5}, A-C=A
A { 6,7,8,9,10}, B {3,5,7,8,9,10}
1.4 集 合 的 运 算 证 明 两 个 集 合 相 等, 可 用 如 下 办 法 : <1> 基 本 法 集 合 相 等 的 充 要 条 件 是 两 个 集 合 互 为 子 集 ; 即, 左 式 右 式, 右 式 左 式 所 以 证 明 : x 左 式 x 右 式 ;x 右 式 x 左 式 经 典 实 例 : 例 1.4, 例 1.5, 例 1.6 证 明 理 论 基 础 : 定 理 1.1 和 定 义 1.1, 1.2 <2> 公 式 法 由 集 合 运 算 的 基 本 性 质, 通 过 推 演, 进 行 证 明 经 典 实 例 : 例 1.7, 例 1.8 证 明 理 论 基 础 : 定 理 1.4 和 定 义 1.10
基 本 法 例 1.4 A (B C)=(A B) (A C) 证 明 : 1)A (B C) (A B) (A C) 任 一 x A (B C) x (A B) (A C) 2)(A B) (A C) A (B C) 任 一 x (A B) (A C) x A (B C)
基 本 法 例 1.5 若 A B, 则 (A B)=A, A B=B. 证 明 : 1) 证 (A B)=A 思 想 : (A B) A; A (A B) 2) 证 A B=B 思 想 : A B B; B A B
例 1.6 证 明 : B A B A B A B A : 首 先 证 明 B, A x 有, B A x 对, B x A x 或 故 B, x A x 或 即 A B A B 因 此 有 B A x 因 此 有 B A B A 然 后 证 明 : B, x A x 或 有, B A x 对, B x A x 或 故 B A x 即, B A x 因 此 有 B A B A 所 以 B A B A
1.4 集 合 的 运 算 三 定 理 1.4 ( 集 合 运 算 的 基 本 性 质 ) (1) 幂 等 律 A A=A A A=A (2) 交 换 律 A B=B A A B=B A (3) 结 合 律 A (B C)=(A B) C A (B C)=(A B) C (4) 分 配 律 A (B C)=(A B) (A C) A (B C)=(A B) (A C)
1.4 集 合 的 运 算 (5) 恒 等 律 A U=U A U=A A =A A = (6) 取 补 律 U U A A U A A
1.4 集 合 的 运 算 (7) 双 重 补 A A
1.4 集 合 的 运 算 (8) 狄 摩 根 律 A B A B A B A B
证 明 类 似 于 例 1.4, 例 1.5, 例 1.6 证 明
判 断 题, 为 真 给 出 证 明, 为 假 给 出 反 例 : 若 A B=A C, 则 B=C /* 北 京 大 学 1994 考 研 */
解 : 错 误 如 果 A 为 空 集, 则 有 A B=A C, 即 使 B C, 原 式 成 立
公 式 法 原 则 : 1) 根 据 集 合 运 算 的 定 义, 将 集 合 运 算 表 达 式 中 - 和 转 换 为 和 ; A B A B ; A B ( A B ) ( B A ) 2) 将 补 运 算 作 用 到 单 一 集 合 上 ; 3) 左 式 右 式 ; 右 式 左 式 ; 左 式 中 间 式, 右 式 中 间 式 ; 4) 根 据 定 义 1.10 和 定 理 1.4 转 换
例 :(A B)-C=(A-C) (B-C) C B A C B A ) ( ) ( : 证 明 左 ) )( ) ( ) ( 分 配 律 C B C A ) ( ) ( C B C A
例 1.7 证 明 (A B)-(A C)=A (B-C) 证 明 思 想 : 将 集 合 运 算 表 达 式 中 - 转 换
例 1.8 证 明 A B=(A B)-(A B) 证 明 思 想 : 将 集 合 运 算 表 达 式 中 - 和 转 换
P( { })=. /* 北 京 理 工 大 学 1999 考 研 */
判 断 题, 为 真 给 出 证 明, 为 假 给 出 反 例 : (1){ } {x}-{{x}} (2)(A B) C= (A C) (B C) /*(1) 北 京 大 学 1994 考 研, (2) 上 海 交 通 大 学 2001 考 研 */
解 : 错 误 {x}-{{x}}={x} 显 然,{ } {x} 不 成 立
幂 集 证 明 基 本 法 幂 集 的 定 义 证 明 :P(A) P(B) P(A B), 并 说 明 等 号 成 立 的 条 件 /* 上 海 交 通 大 学 1999 考 研 */
判 断 下 式 是 否 成 立, 如 果 成 立, 则 证 明 ; 否 则 举 出 反 例 P(A) P(B)=P(A B) /* 上 海 交 通 大 学 2001 考 研 */
1.4 集 合 的 运 算 四 定 义 1.11 ( 多 个 集 合 的 并 和 交 ) 设 集 合 A 1,, A n, 定 义 : A 1 A n ={ x 至 少 有 某 个 i,1 i n, x A i }, 称 为 A 1,, A n 的 并 ; A 1 A n ={ x x A i, 对 一 切 i=1,,n 成 立 }, 称 为 A 1,, A n 的 交
1.4 集 合 的 运 算 五 多 个 集 合 的 运 算, 除 对 并 ( 交 ) 的 结 合 律 交 换 律 成 立 以 外, 还 有 (1) 分 配 律 B (A 1 A 2 A n )=(B A 1 ) (B A 2 ) (B A n ) B (A 1 A 2 A n )= (B A 1 ) (B A 2 ) (B A n ) (2) 狄 摩 根 律 A A n n i 1 i i 1 i A A n n i 1 i i 1 i
1.4 集 合 的 运 算 六 广 义 并 广 义 交 1. 定 义 ( 广 义 并 ) 设 Ǽ 为 一 个 集 合 族, 称 由 Ǽ 中 全 体 元 素 的 元 素 组 成 的 集 合 成 为 的 Ǽ 广 义 并 集, 记 作 Ǽ, 称 为 广 义 并 运 算 符, 读 作 大 并 Ǽ={x z (z Ǽ 并 且 x z)} 例 :Ǽ={{a, b}, {c, d}, {d, e, f}} Ǽ={a, b, c, d, e, f}.
1.4 集 合 的 运 算 2. 定 义 ( 广 义 交 ) 设 Ǽ 为 一 个 非 空 集 合 族, 称 由 Ǽ 中 全 体 元 素 的 公 共 元 素 组 成 的 集 合 成 为 的 Ǽ 广 义 交 集, 记 作 Ǽ, 称 为 广 义 交 运 算 符, 读 作 大 交 Ǽ={x z ( 如 果 z Ǽ, 则 x z)} 例 : 设 Ǽ={{1, 2, 3}, {1, a, b}, {1, 6, 7}} Ǽ={1}
3. 在 广 义 并 与 广 义 交 的 运 算 中, 集 合 族 中 的 元 素 仍 看 成 集 合 族 例, 给 出 下 列 集 合 族 : Ǽ 1 ={a, b, {c, d}}, Ǽ 2 ={{a, b}}, Ǽ 3 ={a}, Ǽ 4 ={, { }}, Ǽ 5 =a (a ), Ǽ 6 = Ǽ 1 =a b {c, d}, Ǽ 1 =a b {c, d}, Ǽ 2 ={a, b}, Ǽ 2 ={a, b}, Ǽ 3 =a, Ǽ 3 =a, Ǽ 4 ={ }, Ǽ 4 =, Ǽ 5 = a, Ǽ 5 = a, Ǽ 6 =, Ǽ 6 无 意 义.
设, 为 集 合 族, 试 证 明 : (1) 若, 则 ; (2) 若, 则 ; (3) 若, 且, 则 ; (4) 若, 则 ; (5) 若, 则.
证 明 : (1) 对 于 任 意 的 x, x, 则 存 在 A, A 并 且 x A, 所 以 A, 则 x. 所 以. /* 证 明 方 法 : 基 本 法 */
(2) 因 为, 由 广 义 并 集 定 义,.
(3) 由 于, 所 以, 故 与 均 有 意 义. 对 于 任 意 的 x, x 当 且 仅 当 对 于 任 意 的 y, 如 果 y, 则 x y. 所 以, 如 果 y, 则 x y. 所 以 x. 所 以.
(4), (5) 的 证 明 比 较 简 单, 请 自 行 完 成.
1.5 罗 素 悖 论 命 题 : 能 区 别 真 假 的 陈 述 语 句 例 : 我 是 学 生 今 天 不 下 雨 上 述 两 个 都 是 命 题 因 为 它 们 都 能 判 别 真 假 例 : 祝 你 一 帆 风 顺! 你 明 天 下 午 出 去 吗? 上 述 两 个 都 不 是 命 题
1.5 罗 素 悖 论 一 悖 论 一 个 命 题 Q, 如 果 从 Q 为 真, 可 以 推 导 出 Q 为 假 ; 又 从 Q 为 非 真 推 导 出 Q 为 真, 命 题 Q 是 一 个 悖 论
二 说 谎 悖 论 和 理 发 师 悖 论 1, 说 谎 悖 论 我 正 在 说 谎 我 们 要 问 : 这 个 人 是 在 说 谎 还 是 在 讲 真 话?
如 果 他 在 说 谎, 这 表 明 他 的 断 言 我 正 在 说 谎 是 谎 话, 也 就 是 说 他 在 讲 真 话 即 他 说 谎, 推 出 他 是 讲 真 话 ( 即 没 有 说 谎 ) 另 一 方 面, 如 果 他 讲 真 话, 这 表 明 他 的 断 言 我 正 在 说 谎 是 真 话, 也 就 是 说 他 正 说 谎 话, 即 他 讲 真 话, 推 出 他 在 说 谎 ( 即 没 有 讲 真 话 ) 通 过 以 上 分 析 让 我 们 看 到, 以 命 题 出 现 的 断 言 我 正 在 说 谎 就 是 一 个 悖 论, 因 为 我 们 无 法 断 言 它 的 真 伪
2 理 发 师 悖 论 一 个 村 上, 有 一 个 理 发 师 宣 布 他 给 而 且 只 给 所 有 自 己 不 替 自 己 理 发 的 人 理 发 现 在 要 问 : 谁 给 这 个 理 发 师 理 发?
如 果 理 发 师 的 头 由 别 人 给 他 理, 也 就 是 说 理 发 师 自 己 不 替 自 己 理 发, 那 么 按 照 规 定, 这 位 理 发 师 应 该 给 自 己 理 发 另 一 方 面, 如 果 理 发 师 的 头 由 自 己 理, 那 么 按 照 规 定, 理 发 师 不 能 给 自 己 理 发 因 此 上 述 也 是 一 个 悖 论 : 理 发 师 的 头 由 别 人 来 理, 不 行 ; 理 发 师 的 头 由 自 己 理, 也 不 行
理 发 师 悖 论 的 数 学 化 表 示 : 设 S={ 自 己 给 自 己 理 发 的 人 } 若 理 发 师 S, 即 理 发 师 是 自 己 给 自 己 理 发 的 人, 但 由 理 发 师 所 宣 布 的, 他 不 该 给 自 己 理 发, 则 理 发 师 S; 若 理 发 师 S, 即 理 发 师 不 是 自 己 给 自 己 理 发 的 人, 但 由 理 发 师 所 宣 布 的, 他 应 该 给 自 己 理 发, 则 理 发 师 S;
罗 素 将 理 发 师 悖 论 表 示 为 数 学 悖 论 罗 素 将 理 发 师 悖 论 表 示 为 数 学 悖 论 : 设 S={ 集 合 A A A}, 问 S S 还 是 S S? 显 然 S
3 悖 论 欣 赏 古 希 腊 哲 学 问 题 : 鳄 鱼 两 难 中 国 民 间 故 事 : 师 徒 打 官 司 柏 拉 图 与 苏 格 拉 底 悖 论
古 希 腊 哲 学 问 题 : 鳄 鱼 两 难 一 条 鳄 鱼 从 一 位 母 亲 手 中 抢 走 了 一 个 小 孩 鳄 鱼 对 孩 子 的 母 亲 说 : 请 你 回 答, 我 会 不 会 吃 掉 你 的 孩 子, 答 对 了, 我 就 把 孩 子 不 加 伤 害 地 还 给 你 ; 否 则, 就 别 怪 我 不 客 气 了! 孩 子 的 母 亲 回 答 : 你 是 要 吃 掉 我 的 孩 子 的 鳄 鱼 是 否 将 孩 子 还 给 母 亲?
中 国 民 间 故 事 : 师 徒 打 官 司 一 位 律 师 收 徒 弟, 协 议 规 定 : 学 成 之 后, 打 赢 一 场 官 司 交 给 律 师 一 两 银 子, 打 输 一 场 官 司 就 不 交 弟 子 满 师 后, 打 赢 官 司 却 一 直 不 交 钱 给 老 律 师, 老 律 师 告 到 县 衙, 和 弟 子 打 官 司 这 场 官 司 该 如 何 裁 决?
柏 拉 图 与 苏 格 拉 底 悖 论 柏 拉 图 说 : 苏 格 拉 底 老 师 下 面 的 话 是 假 话 苏 格 拉 底 说 : 柏 拉 图 上 面 的 话 是 对 的 柏 拉 图 苏 格 拉 底 二 人 的 话 是 真 话 还 是 假 话?
4 何 谓 集 合? 1897 年, 康 托 尔 : 一 个 集 合 就 是 指 我 们 观 察 到 的 或 者 在 我 们 思 维 中 的 一 些 确 定 的 不 同 事 物 的 总 体 ; 这 些 事 物 称 为 该 集 合 的 元 素
1) 某 些 集 合 是 集 合 自 身 的 元 素 如 : 所 有 不 是 苹 果 的 东 西 的 集 合 /* 它 本 身 就 不 是 苹 果, 它 必 须 是 此 集 合 自 身 的 元 素 */ 2) 问 题 : 一 个 由 一 切 不 是 集 合 本 身 的 元 素 组 成 的 集 合, 这 个 集 合 是 它 本 身 的 元 素 吗?
1.5 罗 素 悖 论 三 罗 素 悖 论 1) 罗 素 将 集 合 分 成 两 类 : 一 类 是 集 合 A 本 身 是 A 的 一 个 元 素, 即 A A; 如 上 例 ; 另 一 类 是 集 合 A 本 身 不 是 A 的 一 个 元 素, 即 A A; 例 如 26 个 英 语 字 母 组 成 的 集 合 A, 由 于 A 本 身 不 是 一 个 字 母, 所 以 A A
2) 构 造 一 个 集 合 S:S={A A A}}, 即,S 是 由 满 足 条 件 A A 的 那 些 A 组 成 的 一 个 新 的 集 合 问 : S 是 不 是 它 自 己 的 一 个 元 素? 即 S S, 还 是 S S?
分 析 : 如 果 S S, 因 为 集 合 S 由 所 有 满 足 条 件 A A 的 集 合 组 成, 由 于 S S, 所 以 S 满 足 对 于 集 合 S 中 元 素 的 定 义, 即 S 是 集 合 S 的 元 素, 也 就 是 说 S S 如 果 S S, 因 为 S 中 任 一 元 素 A 都 有 A A, 又 由 于 S S, 根 据 集 合 S 的 规 定, 知 S 不 是 集 合 S 的 元 素, 也 就 是 说 S S
2) 罗 素 悖 论 既 不 是 S S, 也 不 是 S S
罗 素 悖 论 的 出 现, 说 明 朴 素 集 合 论 有 问 题, 从 而 使 数 学 的 基 础 发 生 了 动 摇 ( 第 3 次 数 学 危 机 ), 引 起 了 一 些 著 名 数 学 家 的 极 大 重 视
在 现 代 数 学 中 为 了 防 止 这 类 悖 论 的 出 现, 产 生 各 种 公 理 化 的 集 合 论 和 不 同 的 学 派 : 1) 蔡 梅 罗 (Zermelo) 创 立 集 合 论 的 一 个 公 理 系 统 ; 经 过 费 兰 克 尔 (A. Fraenkel) 改 进, 形 成 著 名 的 ZF 系 统 ; 2) 罗 素 也 发 表 了 他 的 集 合 论 公 理 系 统 类 型 论 ; 3) 以 后,John von Nenmann, P. Bernays, Godel 等 相 继 建 立 了 其 他 类 型 的 公 理 系 统 ;
沈 恩 绍 集 论 与 逻 辑 科 学 出 版 社
经 典 例 题 之 一 集 合 运 算 1. 某 学 院 学 生 选 课 情 况 如 下 :260 人 选 艺 术 课,208 人 选 生 物 课,160 选 计 算 机 课,76 人 选 艺 术 与 生 物 课,48 人 选 艺 术 与 计 算 机 课,62 人 选 生 物 与 计 算 机 课,30 人 三 门 全 选,150 人 三 门 都 不 选 问 1) 共 有 多 少 名 学 生? 2) 有 多 少 学 生 选 艺 术 与 生 物 课, 但 不 选 计 算 机 课? 3) 有 多 少 学 生 选 艺 术 与 计 算 机 课, 但 不 选 生 物 课?
经 典 例 题 之 一 集 合 运 算 4) 有 多 少 学 生 选 生 物 与 计 算 机 课, 但 不 选 艺 术 课? 5) 有 多 少 学 生 选 艺 术 课, 但 不 选 生 物 或 计 算 机 课? 6) 有 多 少 学 生 选 生 物 课, 但 不 选 艺 术 或 计 算 机 课? 7) 有 多 少 学 生 选 计 算 机 课, 但 不 选 艺 术 或 生 物 课?
集 合 运 算 解 题 思 想 容 斥 原 理 : 1) 设 A 1, A 2 为 有 限 集, 则 A 1 A 2 = A 1 + A 2 - A 1 A 2 2) 设 A 1, A 2,,A n 为 有 限 集, 则 A A... A A A A A A A 1 2 n 1... ( 1) 1 2... A A A n n i i j i j k i 1 i, j i, j, k n
3) 设 U 为 全 集,A 1, A 2,,A n 为 U 的 有 限 子 集, 则 A A... A 1 2 U A A... A 1 2 n n
集 合 运 算 解 题 思 想 容 斥 原 理 ( 包 含 排 斥 ) 应 用 1) 讨 论 的 范 围 是 什 么? 即 那 些 是 全 集 中 的 元 素?---- 某 学 院 的 学 生 全 体 构 成 全 集 ; 2) 将 全 集 中 的 元 素 进 行 分 类 ---- 按 学 生 选 课 的 情 况 进 行 分 类 : 选 修 艺 术 课 为 具 有 性 质 P A, 选 修 生 物 课 为 具 有 性 质 P B, 选 修 计 算 机 课 为 具 有 性 质 P C, 具 有 上 述 性 质 的 集 合 记 为 A, B, C; 3) 列 出 计 算 公 式 ; 4) 用 文 氏 图 辅 助 运 算
求 解 ---- 按 题 意 给 出 已 知 条 件 解 : 设 A={ 选 修 艺 术 课 学 生 },B={ 选 修 生 物 课 学 生 },C={ 选 修 计 算 机 课 学 生 } 则 A =260, B =208, C =160, A B =76, A C =48, B C =62, A B C =30, A B C 150
求 解 ----a) 学 生 总 数 N A B C A B C A B C A B A C B C A B C A B C
求 解 ---- 答 案 答 案 a) 622 b) 46 c) 18 d) 32 e) 166 f) 100 g) 80
2. 求 1 到 250 这 250 个 整 数 中, 至 少 能 被 2,3,5 之 一 整 除 的 数 的 个 数
解 : 设 A, B, C 表 示 1 到 250 这 250 个 整 数 中, 能 分 别 被 2,3,5 整 除 的 数 的 集 合 则 有 : A =125, B =83, C =50 A B =41, A C =25, B C =16, A B C =8, 那 么, A B C = A + B + C - A B - A C - B C + A B C =184
3. 75 名 儿 童 到 游 乐 场 去 玩 他 们 可 以 骑 旋 转 木 马, 坐 滑 行 铁 道, 乘 宇 宙 飞 船 已 知 其 中 20 人 这 3 种 东 西 都 玩 过, 其 中 55 人 至 少 乘 坐 过 其 中 的 两 种 若 每 样 乘 坐 一 次 的 费 用 是 0.5 元, 游 乐 场 总 共 收 入 70 元, 试 用 容 斥 原 理 确 定, 在 75 名 儿 童 中 有 多 少 儿 童 没 有 乘 坐 其 中 任 何 一 种
经 典 例 题 之 二 证 明 方 法 反 证 法 引 用 已 知 的 结 论 来 简 化 证 明 步 骤 证 明 两 个 集 合 相 等 常 用 的 方 法
证 明 方 法 1 1) 反 证 法 设 A 为 一 个 集 合,B 为 A 的 补 集 合, 则 A B= 证 明 : 设 A B, 则 存 在 非 空 元 素 x A B, 故 x A 且 x B, 此 与 B 为 A 的 补 集 合 矛 盾 所 以 A B=
证 明 方 法 2 2) 引 用 已 知 的 结 论 来 简 化 证 明 步 骤 对 任 意 的 集 合 A, A 证 明 : 反 证 法, 假 设 存 在 一 个 集 合 A, 使 得 A 即 存 在 元 素 x, 但 x A 这 与 是 空 集 矛 盾 空 集 合 是 唯 一 的 证 明 : 设 1 和 2 都 是 空 集 合, 由 上 题, 1 2 且 2 1, 则 1 = 2
证 明 方 法 3 3) 证 明 两 个 集 合 相 等 常 用 的 方 法 基 本 法, 公 式 法 习 题 1.3 基 本 法 习 题 1.11 公 式 法
证 明 方 法 练 习 1) 设 A 为 一 个 集 合,B 为 A 的 补 集, 则 A B= 证 明 : 反 证 法 设 A B, 则 存 在 x A B, 所 以 x A, 并 且 x B, 矛 盾
证 明 方 法 练 习 2) 证 明 A B=B A 证 明 : 分 两 部 分 证 明 首 先 证 明 左 式 是 右 式 的 子 集, 然 后 证 明 右 式 是 左 式 的 子 集 若 两 个 集 合 互 为 子 集 时, 必 然 相 等 设 任 意 x A B x A 或 者 x B x B A 设 任 意 x B A x A 或 者 x B x A B
经 典 例 题 之 三 是 非 判 断 判 断 命 题 是 否 正 确, 并 说 明 理 由 习 题 1.4, 1.9.
习 题 1.4 (1) A B, C D, (A C) (B D), 基 本 法 证 明 ; (A C) (B D), 基 本 法 证 明 ; (2) W X, Y Z, (W Y) (X Z), 反 例 :W={1, 2}, Y={1, 3}, X={1, 2, 3}, Z={1, 3, 2}; 则 (W Y)={1, 2, 3}, (X Z)={1, 2, 3}; (W Y) (X Z), 反 例 :W={1, 2}, Y={1, 3}, X={1, 2, 4}, Z={1, 3, 5}; 则 (W Y)={1}, (X Z)={1}
学 生 练 习 习 题 1.9
经 典 例 题 之 四 幂 集 习 题 1.12 代 数 法 设 A={ }, B=P(P(A)), 问 : (1) B? B? (2){ } B? { } B? (3){{ }} B? {{ }} B? /* 重 庆 大 学 1998 研 究 生 入 学 考 试 试 题 */
解 : 设 x=, 则 P(A)={, {x}}={, { }}; 设 x=, y={ }, 则 P(A)={x, y}; 所 以,P(P(A))={, {x}, {y}, {x, y}}; 回 代,P(P(A))={, { }, {{ }}, {, { }}}.
B=P(P(A))={, { }, {{ }}, {, { }}}. (1) B, B; (2) { } B, { } B; (3) {{ }} B, {{ }} B.
例 : 设 A 和 B 为 两 个 集 合, 则 P(A) P(B)=P(A B) 证 明 思 想 : 幂 集 定 义 和 基 本 法
证 明 : 先 证 P(A) P(B) P(A B); 对 任 意 X P(A) P(B), 有 X P(A) 且 X P(B), 所 以 X A 且 X B, 即 X A B, 因 此 X P(A B); 所 以 P(A) P(B) P(A B); 再 证 P(A B) P(A) P(B); 对 任 意 X P(A B), 有 X A B, 即 X A 且 X B, 所 以 X P(A) 且 X P(B), 因 此 X P(A) P(B); 所 以 P(A B) P(A) P(B) 所 以,P(A) P(B)=P(A B)
思 考 练 习 题 幂 集 性 质 的 证 明 1. 对 于 任 意 的 集 合 A 和 B, (1) A B P(A) P(B). (2) A=B P(A)=P(B). /* 幂 集 定 义 和 基 本 法 */
2. 对 于 任 意 的 集 合 A 和 B, P(A) P(B) A B.
3. 对 于 任 意 的 集 合 A 和 B, (1) P(A) P(B)= P(A B) (2) P(A) P(B) P(A B)
4. 对 于 任 意 的 集 合 A 和 B, P(A-B) (P(A)- P(B)) { }.
作 业 习 题 1.1, 1.2, 1.3, 1.4, 1.7, 1.9(1),(3),(5), 1.11(1),(2), 1.12, 1.13