当前位置:首页 >> 数学 >>

离散数学


离散数学
Discrete Mathematics
主讲教师:欧阳丹彤
ouyd@jlu.edu.cn

助课教师:刘杰
liu_jie@jlu.edu.cn

计算机学院智能信息处理研究室

1、课程的性质
? 离散数学是现代数学的一个重要分支,也是计

r />算机科学与技术一级学科及其相关专业必修的 基础理论的核心课程。是学习后续专业课程不 可缺少的数学工具。《中国计算机科学与技术 学科教程》中将其列为计算机科学与技术专业 14个知识领域之一。
? 形成于七十年代初期,是随着计算机科学的发

展而逐步建立的。

1、课程的性质
? 研究对象:离散量结构及相互关系。

离散量:逻辑量、图、树、整数、布尔代数 连续量:温度、压力、体积、电压 —— 计算机中离散处理 可见,离散数学充分描述了计算机学科离散性的 特点。 ? 离散数学是一门理论性较强,应用性较广的课 程。

2、课程的目的
? 掌握离散数学的基本概念和基本原理

离散数学所涉及的概念、方法和理论,大量地出现在 “编译原理”、“数据结构”、“操作系统”、 “数据库系统”、“算法分析”、“定理机器证 明”、“人工智能”等众多领域,为学习这些课程 做了必要的知识准备 。 如:谓词逻辑成为程序的语义理论和程序的正确性证 明的重要研究工具;平面图的理论被用于印刷电路 板的设计;图论的概念和理论广泛用于AI、DS等; 布尔代数为开关理论的研究提供了分析工具,并导 致了数字逻辑理论的建立;代数系统的理论被用于 对数据结构的研究,产生了抽象数据类型的理论; 代数系统的理论成为编码理论的数学基础。

离散数学、数据结构、算法设计与分析、 组合数学和程序设计等课程紧密相关
以问题的求解步骤来具体说明5门课程的紧密相关性: ? 运用离散数学,组合数学等知识完成待解问题数学建模 ? 运用数据结构和算法设计的知识选择、构造恰当数据 结构,编写较好的计算机算法 ? 对算法的关键点,运用离散数学、组合数学知识进行 正确性证明(此步骤是可选择的) ? 运用算法分析、离散数学、组合数学等知识对算法进 行时空复杂性分析 ? 运用离散数学、算法设计、组合数学和运筹学等知识 对算法进行优化(此步骤是可选择的) ? (在算法基础上)使用程序设计技巧编写程序,使用程 序测试技术测试程序,在计算机上完成问题求解。

数据结构、离散数学、算法设计与分析、 组合数学和程序设计等课程紧密相关
数据结构、离散数学、算法、组合数学和汇编 语言程序是图灵奖获得者、著名计算机科学家、 数学家D.E.Knuth教授的旷世之作《计算机程 序设计艺术》的主要内容。

2、课程的目的
? 提供良好的数学训练

(1)提高逻辑思维、抽象思维能力

分析问题与
(2)提高严密的推理能力

解决问题 的能力

(3)提高数学语言描述能力

(4)提高判断对错能力—独立工作能力

3、课程的特点
?

定义与定理多 离散数学是建立在大量定义之上的逻辑推理学科, 因此对概念的理解是我们学习这门课程的核心。在 学习这些概念的基础上,要特别注意概念之间的联 系,而描述这些联系的实体则是大量的定理与性质。 ? 方法性强 离散数学的许多证明题中,方法性是非常强的,如 果掌握了题的证明方法,很容易就可以证出来,反 之则事倍功半。所以在学习该课程中要善于总结, 勤于思考,这也是培养分析问题、解决问题能力与 抽象思维能力的一个过程。

4、如何学好离散数学?
?掌握概念: 在模棱两可的地方多下功夫,弄懂、弄透。 ? 认真完成作业 一道题做完,还要提出如下几个问题: (1)是否肯定一定对。 (2)是否有更简洁的方法。 (3)推理是否严密。 (4)语言是否流畅。

5、离散数学教学内容
?第一章 集合论基础(集合论) ?第二章 命题逻辑 数理逻辑 离散Ⅰ ?第三章 谓词逻辑 ?第四章 图与网络 (图论) ?第五章 数论基础 (数论) ?六--八章 抽象代数 ----离散Ⅱ

第一章 集合论基础
?§1.1 集合的基本概念

?§1.2 关 系 ?§1.3 映 射

集合论发展史
?集合论(Set Theory)是现代数学的基础.它的 起源可追溯到16世纪末,主要是对数集进行卓 有成效的研究. ?集合论实际发展是由 19世纪 70年代德国数学 家康托尔(G Cantor) 在无穷序列和分析的有关 课题的理论研究中创立的.Cantor对具有任意 特性的无穷集合进行了深入的探讨,提出了关 于基数、序数、超穷数和良序集等理论,奠定 了集合论的深厚基础.因此, Cantor被誉为 集合论的创始人.他创立的集合论是实数理论, 以至整个微积分理论体系的基础。

集合论创始人 康托尔 德国数学家 (Georg Cantor 1845-1918)

? 1845年3月3日 出生于俄国的一个丹麦—犹太血统的家庭。 ? 1856年 与父母一起迁到德国的法兰克福。 ? 1863年 进入柏林大学,转到纯粹的数学。 ? 1866年 获得博士学位。 ? 1874年 在《数学杂志》上发表了关于无穷集合理论 的第一篇革命性文章。数学史上一般认为这篇文 章的发表标志着集合论的诞生。

Cantor 生平

? 1879年 任哈雷大学教授。 ? 1891年 组建德国数学家联合会,被选为第一任主席。 ? 1904年 被伦敦皇家学会授予当时数学界最高荣誉— —西尔威斯特(Sylvester)奖章。

? 1884年春天起
患了严重的忧郁症,极度沮丧,神态不安, 精神病时时发作,不得不经常住到精神病院 的疗养所去。变得很自卑,甚至怀疑自己的 工作是否可靠。他请求哈雷大学当局把他的 数学教授职位改为哲学教授职位。 1918年

在哈雷大学附属精神病院去世,享年73岁。

对Cantor的不同评价
克罗内克(L.Kronecker 1823-1891)
Cantor的老师,对Cantor表现出了 无微不至的关怀。他用各种用得上的尖刻 语言,粗暴地、连续不断地攻击Cantor达 十年之久。他甚至在柏林大学的学生面前 公开攻击Cantor 。横加阻挠Cantor在柏 林得到一个薪金较高、声望更大的教授职 位。使得Cantor想在柏林得到职位而改善 其地位的任何努力都遭到挫折。

法国数学家庞加莱 (H.Poincare 1854-1912): 我个人,而且还不只我一人,认为重要 之点在于,切勿引进一些不能用有限个 文字去完全定义好的东西。集合论是一 个有趣的“病理学的情形”,后一代将 把(Cantor)集合论当作一种疾病,而 人们已经从中恢复过来了。

德国数学家魏尔 (C.H.Hermann Weyl,1885-1955): 关于基数的等级观点是雾上之雾。
菲利克斯.克莱因

(F.Klein,1849-1925):
不赞成集合论的思想。 数学家H.A.施瓦兹—Cantor的好友

由于反对集合论而同Cantor断交。

这对我来说是最值得钦佩的数学理智之 花,也是在纯粹理性范畴中人类活动所 取得的最高成就之一。 没有人能把我们从康托尔为我们创造的乐园中驱 赶出去。 ——希尔伯特 超限算术是数学思想的最惊人的产物,在纯 粹理性的范畴中人类活动的最美的表现之 一。 —— 罗 素 由康托尔的工作所带来的哲学革命也许甚 至比数学本身还伟大。 —— 约 代 因

Cantor的主要研究成果
?通过一一对应关系建立了集合之间等势的概 念,奠定了无限集分类的基础。

最著名的著作--《超穷理论基础》:数学理论 必须肯定实无穷,因为很多最基本的数学性 质,例如一切正整数,圆周上的一切点等, 事实上都是实无穷性的概念。而且不能把有 穷所具有的性质强加于无穷。他的“一一对 应”的原理突破了传统的“整体大于部分” 的旧观念,例如全体正整数与(其部分)全 体正偶数一一对应,正整数集与正偶数集等 势。

Cantor的主要研究成果
?引进了可数集的概念,证明了有理数全体及 代数数(有理多项式的根)全体都是可数集 合。
?运用对角线方法证明了实数集是不可数集, 从而间接推导出超越数(非代数数的实数) 比代数数多,同时也说明了无限集可按大小 区分为不同的类。

Cantor的主要研究成果
?证明了n维空间与一维直线之间存在一 一对应。 ?系统研究了序数理论,提出了良序原理。 ?证明了集的幂集比原集有更大的基数。 ?提出了连续统假设。

集合论发展史(继续)

?随着集合论的发展,以及它与数学哲学密切联 系所作的讨论,1900年前后,出现了许多悖论, 有力冲击了或者说动摇了集合论的发展. (数学史上的三次危机 无理数的发现──第一次数学危机 无穷小是零吗?──第二次数学危机 悖论的产生——第三次数学危机)

著名的罗素悖论:1902年,受到“理发师悖论” 的启发而提出。 理发师悖论:“一个理发师宣称,他不给自己刮 脸的人刮脸,但给所有不自己刮脸的人刮脸。” 人们问:“理发师先生,您自己的脸谁刮?”
(悖论不是谬论,悖论中充满着令人惊奇的内容——悖论 可以推导出自相矛盾的结论,人们却难以指出悖论非法 的理由。公元前6世纪,希腊人伊比孟德说:

“我说这句话时正在说谎。”
伊翁问听众,他上面说的那句话是真话还是假话?该怎么 回答伊翁呢? “下面的句子是错的, 上面的句子是对的。”问“下面的句子是错的”为真还 是为假?)

伯特兰· 罗素(1872-1970) 英国著名哲学家、数学家、逻辑学家、 散文作家、社会活动家

罗素生平
?1872年5月,生于英国曼摩兹郡的特雷克,幼年 时父母双亡,是祖母将他抚育成人。 ?1890年进剑桥大学三一学院学习 ?1893年获数学荣誉学士学位一级。接着改学哲学 ?1894年获道德哲学荣誉学士学位一级 ?毕业后曾游学德国学经济,受马克思主义影响, 回国后,在伦敦大学政治和经济学院任讲师。 ?l903年发表《数学原理》一书,并以论文《几何 学基础》获三一学院研究员职位。 ?1908年当选为皇家学会会员。

? 1910年发表《哲学文集》;1917年发表《哲学的问题》。 ? 1914年加入工党。 ? 第一次世界大战期间,因参加和平主义者的活动,被处 罚金,革职入狱。在狱中,撰写了《数学哲学导论》 (1919)。 ? 1920年访问中国和苏联,著有《布尔什维主义的实践和 理论》。 1920年到北大担任客座教授,一年后离开,隔年写成 《中国问题》这本书。他看见:“中国文化正在发生急 遽的变化”,提出建议:“假如中国人能自由地吸收我 们文明中他们所需要的东西,而排斥那些他们觉得不好 的东西,那么他们将能够在其自身传统中获得一种有机 发展,并产生将我们的优点同他们自己的优点相结合起 来的辉煌成就。”

?1927年,罗素和夫人布拉克在英国彼得斯费尔 德市附近创办一所私立学校,实验他的教育理 论,是当时英国的进步主义学校之一。 1935年离婚后,布拉克独自办到1939年。他一 直主张“自由教育”和“爱的教育”。认为教 育的基本目的是品格的发展,而“活力、勇气、 敏感和智慧”是形成“理想品格”的基础;并 深信通过对儿童的身体、感情和智力上的“恰 当的处理”,可以使这些品质得到普遍的培养。

?1931年他继承为第三世罗素勋爵。 ?1949年获荣誉勋章。 ?1950年由于他“多产而重要的哲学 著作,并以此成为人道主义与自由 思想的代言人”而获得了该年度的 诺贝尔文学奖。

? 50年代因积极参加世界和平运动,反对核战争而获得
世界和平奖。

1955年2月,爱因斯坦收到了英国著名哲学家罗素的信,告诉他 由于制造核武器的竞赛,人类的前途实在令人担心,希望以爱因 斯坦为首团结几个著名的科学家发表宣言避免毁灭人类战争发生。 爱因斯坦在收到信后马上回信表示:“你熟悉这些组织的工作。 你是将军我是小兵。你只要发出命令,我就随后跟从。”于是出 现了著名的《罗素―爱因斯坦宣言》除了爱因斯坦在临终前签字 外,约里奥· 居里、汤川秀树和李诺· 鲍林等多位科学家都在宣言 上签字。 ? 1961年,89岁高龄的罗素参与一个核裁军的游行后被拘禁了7天。 他反对越南战争,和萨特一起于1967年5月成立了一个民间法庭 (后被称为“罗素法庭”),揭露美国的战争罪行。

? 1959年,罗素发表了《西方智慧》 后,开始了《罗素自传》的创作, 并在1967年95岁高龄之际完成了一 生最优秀的著作之一《罗素自 传》。 ?1970年2月2日去世,一生曾四次结 婚,三次离婚。

? 《罗素自传》序言 我为什么而活着 对爱情的渴望,对知识的追求,对人类苦难不可遏 制的同情心,这三种纯洁但无比强烈的激情支配着我的 一生。这三种激情就像飓风一样,在深深的苦海上,肆 意地把我吹来吹大,吹到濒临绝望的边缘。 我寻求爱情,首先因为爱情给我带来狂喜,它如此 强烈以致我经常愿意为了几小时的欢愉而牺牲生命中的 其它一切。我寻求爱情,其次是因为爱情解除孤寂—— 那是一颗震颤的心,在世界的边缘,俯瞰那冰冷死寂、 深不可测的深渊。我寻求爱情,最后是因为在爱情的结 合中,我看到圣徒和诗人们所想象的天堂景象的神秘缩 影。这就是我所寻求的,虽然它对人生似乎过于美好, 然而最终我还是得到了它。

我以同样的热情寻求知识,我希望了解人的心灵。 我希望知道星星为什么闪闪发光,我试图理解毕达哥 拉斯的思想威力,即数字支配着万物流转。这方面我 获得一些成就,然而并不多。 爱情和知识,尽其可能地把我引上天堂,但是同 情心总把我带回尘世。痛苦的呼号的回声在我心中回 荡,饥饿的儿童,被压迫者折磨的受害者,被儿女视 为可厌负担的无助的老人以及充满孤寂、贫穷和痛苦 的整个世界,都是对人类应有生活的嘲讽。我渴望减 轻这些不幸,但是我无能为力,而且我自己也深受其 害。 这就是我的一生,我觉得它值得活。如果有机会 的话,我还乐意再活—次。

The Prologue to Bertrand Russell's Autobiography What I Have Lived For
Three passions, simple but overwhelmingly strong, have governed my life: the longing for love, the search for knowledge, and unbearable pity for the suffering of mankind. These passions, like great winds, have blown me hither and thither, in a wayward course, over a great ocean of anguish, reaching to the very verge of despair.

I have sought love, first, because it brings ecstasy - ecstasy so great that I would often have sacrificed all the rest of life for a few hours of this joy. I have sought it, next, because it relieves loneliness--that terrible loneliness in which one shivering consciousness looks over the rim of the world into the cold unfathomable lifeless abyss. I have sought it finally, because in the union of love I have seen, in a mystic miniature, the prefiguring vision of the heaven that saints and poets have imagined. This is what I sought, and though it might seem too good for human life, this is what--at last--I have found.

With equal passion I have sought knowledge. I have wished to understand the hearts of men. I have wished to know why the stars shine. And I have tried to apprehend the Pythagorean power by which number holds sway above the flux. A little of this, but not much, I have achieved. Love and knowledge, so far as they were possible, led upward toward the heavens. But always pity brought me back to earth. Echoes of cries of pain reverberate in my heart. Children in famine, victims tortured by oppressors, helpless old people a burden to their sons, and the whole world of loneliness, poverty, and pain make a mockery of what human life should be. I long to alleviate this evil, but I cannot, and I too suffer. This has been my life. I have found it worth living, and would gladly live it again if the chance were offered me.

罗素谚语

? 许多人宁愿死,也不愿思考,事实上他们也确实至死都 没有思考。 ? 我的人生正是:使事业成为喜悦,使喜悦成为事业。 ? 一部分儿童有思考的习惯,而教育的目的在于铲除他们 的这种习惯。 ? 乞丐并不会妒忌百万富翁,但是他肯定会妒忌收入更高 的乞丐。 ? 即使真相并不令人愉快,也一定要做到诚实,因为掩盖 真相往往要费更大力气。 ? 不要为自己持独特看法而感到害怕,因为我们现在所接 受的常识都曾是独特看法。 ? 不用盲目地崇拜任何权威,因为你总能找到相反的权威。 ? 凡事不要抱绝对肯定的态度。

?由于Cantor所创立的朴素集合论产生了悖论, 促进了集合论公理化的工作。 ?具有代表性的工作有两个:
?

由德国数学家策梅洛(E.Zermelo)于1908年首先建立, 后来由以色列数学家弗兰克尔(A.A.Fraenkel),挪威 数学家斯科伦(T.Skolem)与冯?诺依曼(von Neumann) 等人于20世纪20年代加以改进的ZF公理集合论系统, 加入选择公理的系统成为ZFC。 ? von Neumann-Bernays-G? del公理系统,简称NBG 系统。

?教材主要介绍Cantor的朴素集合论的工作。

集合论在计算机科学、人工智能领域、 逻辑学及语言学等方面都有着重要的应 用.对于从事计算机科学的工作者来说, 集合论是不可缺少的理论知识,熟悉和 掌握它是十分必要的.

§1.1 集合的基本概念
一、基本概念

? 什么是集合(Set)?
“所要讨论的一类对象的整体”; “具有同一性质单元的集体” “所谓集合,是指我们无意中或思想中将一 些确定的,彼此完全不同的客体的总和而考虑

为的一个整体。这些客体叫做该集合的元素”
通常,用大写的英文字母A, B, C,……表示集合;

例如:
2、所有的自然数看成是一个集合;约定自 然数包括0 3、吉林大学软件学院2009级的本科学生 可以看成是一个集合; 4、这间教室中的所有座位可以看成是一个 集合。

1、二十六个英文字母可以看成是一个集合;

集合的元素(member或element)
组成一个集合的那些对象或单元称为 这个集合的元素。

通常,用小写的英文字母a, b, c,…表 示集合中的元素

属于(belong to)
设A是一个集合,a是集合A中的元素,记以 a?A,读作a属于A;若a不是集合A中的元素, 则记以a?A,读作a不属于A。 例如:A是正偶数集合,则2?A,8?A, 36?A;而 3?A,9?A,17?A

空集、全集
?约定,存在一个没有任何元素的集合,

称为空集(empty set) ,记为?,有时也用
{}来表示。 ?约定,所讨论的对象的全体称为全集

(universal set),记作E或U,我们所讨
论的集合都是全集的子集 。全集是相对

的。

有限集 、无限集
?包含有限个元素的集合,称为有限集或 有穷集(finite set);

?包含无限个元素的集合,称为无限集或
无穷集(infinite set )。

例:空集是有限集,所有英文字母组成
的集合是有限集,整数集合是无限集。

集合的元素数(基数)
?设A是有穷集合, A中元素的个数称为 集合A的元素数,记为?A?。

?例如,设A是所有小写英文字母组成的
集合,则?A?=26。

特别, | ? |=0,|{?}|=1

常用的集合表示法
? 列举法(外延法)
将集合中的元素一一列举,或列出足够多的 元素以反映集合中元素的特征,例如: V={a,e,i,o,u} 或B={1,4,9,16,25,36……}。 ? 描述法(内涵法)

通过描述集合中元素的共同特征来表示集合, 例如: V= {x|x是英语元音字母} , B= {x|x=a2 , a是非零整数}

? 文氏图(Venn Diagram) 英国数学家John Venn提出 用一个大的矩形表示全集,在矩形内画一些圆或 其它简单封闭曲线,用其内部来表示集合,可以 用一些点来表示集合中的特定元素。 ? 例如:集合V={a,e,i,o,u} ,用文氏图表示如下:
全集E V
a o e u i

注意:文氏图只是示意图,虽然直观、有助于记忆,
但不用于证明。

集合的特征
? 确定性;
? 互异性;

? 无序性;
? 多样性;

确定性
? 任何一个对象,或者是这个集合的元 素,或者不是,二者必居其一;
? 例如:A={x|x是自然数,且x<100} B={x|x是年轻人}

C={x|x是秃子}

互异性
? 集合中任何两个元素都是不同的,即 集合中不允许出现重复的元素。
? 例如: 集合A={a,b,c,c,b,d},实际上, 应该是A={a,b,c,d}

无序性
? 集合与其中的元素的顺序无关,集合 中的元素是没有顺序的,或者说,我 们不考虑集合中元素的顺序。

? 例如: 集合{a,b,c,d,e}、{d,c,e,a,b}、 {e,c,d,b,a},都是表示同一个集合。

多样性
? 集合中的元素可以是任意的对象,相 互独立,不要求一定要具备明显的共 同特征。 ? 例如: A={a,{a},{{a},b},{{a}}, 1} B={1,a,*,-3,{a,b},{x|x是汽车},地球,板 儿砖}

康托尔的朴素集合论
剖析康托尔集合论中的许多证明便知,几乎他所证明的 一切定理均能从如下三个公理得出: ?外延公理 ? 任意两个集合相等,当且仅当它们中的各个元素 都是相同的。 ?抽象公理 ? 任给一个性质,都有一个满足该性质的对象所组 成的集合。 ?选择公理 ? 每个集合都有一个选择函数。 Note:毛病出在抽象公理上. 1903年, Russel发现 “由不为自身的成员这一性质的所有客体的集合” 会导出矛盾来, 这就是著名的罗素悖论.

罗素悖论(Russell’s paradox)
? 设集合S={A|A是集合,且A?A} 1. 若S?S,则S是集合S的元素,则根据

S的定义,有S?S,与假设矛盾;
2. 若S?S,则S是不以自身为元素的集

合,则根据S的定义,有S?S,与假
设矛盾。

【定义1】集合相等
?当两个集合A和B的元素完全一样,即A,B

实际上是同一个集合时,则称集合A,B相等,
记以A=B。

?例:设A={x|x是偶数,且0<x<10},
B={2,4,6,8}, 则A=B。 {1,3,5}≠{{1,3},5}

【定义2】子集(subset)
?设A,B是两个集合,若A的元素都是B的 元素,则称A是B的子集,也称B包含A,

或A包含于B,记以A ? B,或B ? A 。
?若A?B,且A?B,则称A是B的真子集

(proper subset),也称B真包含A,或A真
包含于B,记以A?B,或B ? A 。

例:
?设A={2,4,6,8} ,B= {x|x是正偶数}, C={x|x是整数}, 则有 A ? B,B ?C,A?C, 并且 A ? B,B ? C,A ? C 。 ?{x} ? A 当且仅当 x ?A。

重要结论
? 对任意集合A, 有A ? A。 ? 若A?B,B?C,则A?C 。 ? 对于任意两个集合A、B, A=B 当且仅当 A?B且B?A。 ? 空集是任意集合的子集,是任意非空集合的真子集, 且空集是唯一的。 证明:取任意集合A,因为x∈ ?是恒假的,故 ?x(x∈? ? x∈A)是恒真的,即? ?A。
( ? ? ? , ? ? ? , ? ∈ {?})

讨论:
?是否存在集合A和B, 使得A?B 且A? B ?若存在,请举一例。 ?设A={a} ,B={a,{a},b,c},则有: A?B 且A? B ?再例如: ? ?{?}且? ?{?}

【定义3】幂集(power

set)

?设A 是集合,A的所有子集为元素做成的 集合称为A的幂集,记以?(A)或 2A。

??(A)={S|S ? A}
?例: A={a,b,c} ,则

?(A)={?, {a},{b},{c}, {a,b},{a,c},{b,c}, {a,b,c}}

注意
?幂集合仍然是集合。
? 例如,用枚举法写出集合{a,

b}的幂集

合:

正确的写法:?(A)={?,{a},{b},{a,b}} 错误的写法: ?(A)= ?,{a},{b},{a,b}

?写出?(?),? (?(?)), ? (? (?(?)))

幂集的性质
1. 若A为有穷集,|A|=n,则 |2A | = Cn0 + Cn1 + … + Cnn =2n 。 证明:首先,集合A的子集的元素个数在0到n之间,基 于这个事实,我们可以从A中取0个元素构成A的子集, 有Cn0 个,从A中取1个元素构成A的子集,有Cn1 个,以 此类推,从A中取n个元素构成A的子集,有Cnn 个。而 且取的元素个数不同,肯定得到不同的子集,根据加法 原理,集合A一共有Cn0 + Cn1 + … + Cnn 个子集。

幂集的性质
其次,要获取集合A的一个子集,那么,A

中每个元素都有两种取法,要么在这个子集
中,要么不在。而且每个元素的取法之间是 相互独立的,互不影响,这样,我们根据乘 法原理,可以很容易的得出集合A一共有: 2×2×…×2= 2n 个子集。

幂集的性质
这样,我们就证明了 若A为有穷集,|A|=n,则 |2A | = Cn0 + Cn1 + … + Cnn =2n 。 注意:我们的证明过程采用的是“组合

分析”的方法,在《组合数学》中会有
详细的讲解。

幂集的性质
2. x??(A) 当且仅当 x?A。

证明:必要性,从x??(A)推出x?A。如果
x??(A),那么x是属于A的幂集合的,从而x 是A的一个子集,即x?A。 充分性,从x?A推出x??(A)。如果x?A , 那么x是A的子集,而?(A)是以A的所有子集 为元素的,这样,就有x??(A)。

幂集的性质
3.设A、B是两个集合, A?B 当且仅当 ?(A)??(B)。

证明:必要性,任取C??(A),则C?A,又由A?B知,
C?B,即, C??(B),故?(A)??(B)。

充分性,任取x?A,则{x} ?A,即{x} ??(A),而
?(A)??(B),故{x} ??(B),即{x} ?B,故x?B。因此

A?B。
(如果?(A)??(B),那么A的所有子集都是B的子集,容易 知道A?A,则A?B。)

【定义4】集合族、标志集

?设C是一个集合。若C的元素都是集合,
则称C为集合族。 ?若集合族C可表示为C={Sd?d?D},则

称D为集合族C的标志(索引)集。

?显然,2A是一个集合族。
?设A0, A1, A2, …是集合的序列,且两 两之间互不相同,则集合{A0, A1, 例.

A2,是一个集合族,若将2 写为{A ,…,A },那么它的索引集为{0,…,2 -1}。 …}是一个集合族,可表示为 (2)2
A A 0 2n-1 n

(1)若{A1, A2, A3, …}为一个集合族,那么它的索引集为N+。

{Ai| i?N},其中,N是自然数集合,是 该集合的标志集合。

二、集合的运算及性质 【定义5】集合的并集(Union)
? 设A,B是两个集合。所有属于A或者属于B的元
素做成的集合,称为A和B的并集,记以A∪B。 即A∪B={x|x?A或x?B} ? 例如,令A={a,b,c,d},B={c,d,e,f}, 于是 A∪B={a,b,c,d,e,f}。

并集的文氏图

A

B

A∪B

【定义6】集合的交集(Intersection)
?设A,B是两个集合。由属于A且属于B的 元素组成的集合,称为A和B的交集,记以

A∩B。即A∩B={x|x?A且x?B}
?例如,

令A={a,b,c,d},B={c,d,e,f},
于是 A∩B={c,d}。

交集的文氏图

A

B

A∩B

并集和交集的推广(∪∩满足结合律)
?设A1,A2,…,An是n个集合,则, A1∪A2∪…∪An ,简记为
n

?A
i ?1

i

A1∩A2∩…∩An ,简记为 ? Ai
i ?1

n

【定义7】集合的差集(Difference)
? 设A,B是两个集合。由属于集合A而不属于集 合B的所有元素组成的集合,称为A与B的差集, 记以A-B,或A\B。 即A-B={x|x?A且x?B} ? 例. 令A={a,b,c,d},B={c,d,e,f},于是 A - B={a,b}。

差集的文氏图
E A B

A-B

【定义8】集合的补集(Complement)
?设A是一个集合,全集E与A的差集称为A 的补集或余集,记以A。即A=E-A

?例如,
令E={a,b,c,d,e,f},A={b,c},

于是A={a,d,e,f}。
?特别,E

??

??E

补集的文氏图
E A

A的补集

【定义9】集合的环和(对称差)
? 设A,B是两个集合。则A与B的环和(对称差),记 以A?B, 定义为 A?B=(A-B)∪(B-A)。 ? A与B的对称差还有一个等价的定义,即 A?B=(A∪B)-(A∩B)。 例: 令A={a,b,c,d},B={c,d,e,f},于是 A?B={a,b,e,f}。

环和(对称差)的文氏图
E A B

A?B

【定义10】集合的环积 ?设A,B是两个集合,则A与B的环积定义 为 A ? B = A?B

?A ? B = (A∩B)∪( A∪B )

环积的文氏图
E

A

B

A ? B =(A∩B)∪( A∪B )

【定义11】有序n元组(ordered n-tuple)
?将(a1,a2 ,… ,an)称为有序n元组,其中,a1

是其第一个元素, a2是其第二个元素,… ,

an是其第n个元素。
?两个有序n元组
(a1,a2 ,… ,an)和(b1,b2 ,… ,bn)相等 当且仅当 ai=bi , i=1,2,…,n

【定义12】有序对(ordered pairs)
? 对于有序n元组,当n=2 时,将其称作有 序二元组,也称作有序对,或序偶。

? 有序对的特点:
1. 若a?b,则(a,b)?(b,a)

2. 两个有序对(a,b)和(c,d)相等当且仅当a=c,
b=d

【定义13】笛卡儿积(Cartesian product)
?设A,B是两个集合,所有有序对(x, y)做 成的集合(其中x?A,y?B),称为A,B的

直乘积(笛卡儿积),记以A?B。
?A?B={(x,y)?x?A且y?B}。

笛卡儿 (René Descartes, 1596~1650) 在数学史上,笛卡儿因与费马共同创立解析几何 而闻名于世。与此同时,笛卡儿还是一位 哲学 家、物理学家、生物学家,尤其在哲学上的杰出 贡献使他成为当之无愧的一代哲学大师。

?笛卡儿是法国人,出生于一个贵族 家庭, 由于体弱多病,养成了在床上读 书的习惯, 这使得他有更多的时间独自静静地思考各种 关于自然、科学与人的问题。 ?1628年,笛卡儿移居荷兰,潜心从事哲学、 数学、 天文学、物理学、化学和生理学等 领域的研究。他的主要著作都是在荷兰完成 的,其中1637年出版的《方法论 》一书成 为哲学经典。这本书中的3个著名附录《几 何》、《折光》和《气象》更奠定了笛卡儿 在数学、物理和天文学中的地位。

在《几何》中,笛卡儿分析了几何学与 代数 学的优缺点,指出:希腊人的几何过多的依 赖于图形,总是要寻求一些奇妙的想法。代 数却完全受法则和公式的控制,以致于阻碍 了自由的思想和创造。他同时看到了几何的 直观与推理的优势和代数机械化运算的力 量。于是笛卡儿着手解决这个问题,并由此 创立了解析几何。 ?1650年2月,笛卡儿在瑞典病逝。

【定义14】笛卡儿积的推广
?设A1,A2 , ?,An是n个集合,由所有有序n 元组(a1,a2,…,an)做成的集合 (其中ai?Ai ,

i=1,2, … ,n),称为A1,A2,?,An的直乘积(笛
卡儿积),记以A1?A2 ???An。

?A1?A2 ???An={(a1,a2 ,… ,an) ? ai?Ai ,
i=1,2, … ,n }。

例如:
?设A={1,2},B={a,b,c}, 则A?B=

{(1,a), (1,b),(1,c),(2,a),(2,b),(2,c)};
B?A= {(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)};

直乘积的性质
1. |A?B|=?A? ? ?B?; 2. 对任意集合A,有A??=?,??A=?;

3. 直乘积运算不满足交换律,即
A?B?B?A;

4. 直乘积运算不满足结合律,即
(A?B)?C?A?(B?C)

5. 直乘积运算对并和交运算满足分配律, 即: A?(B∪C)=(A?B)∪(A?C), (B∪C)?A=(B?A)∪(C?A), A?(B∩C)=(A?B)∩(A?C), (B∩C)?A=(B?A)∩(C?A); 6. 设A,B,C,D是集合,若A?C且B?D, 则A?B ? C?D。

对于任意集合A,B,C有如下算律:
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)。
5. 吸收律:A∩(A∪B)=A,

A∪(A∩B)=A。

6. 互补律: A ? A ? ? , A ? A ? E 7. De Morgan律:A ? B) ? A ? B (

( A ? B) ? A ? B
8. 同一律: E∩A=A,?∪A=A。

9. 零一律: ?∩A=?,E∪A=E。
10. 双重否定律: A ? A

证明: A∩(B∪C)=(A∩B)∪(A∩C)
证明:先证A∩ (B∪C) ?(A∩B)∪(A∩C)。 任取 a∈A∩ (B∪C),则a∈A 并且 a∈ B∪C。 由a∈ B∪C知,a∈B或a∈ C。 若a∈B,则a∈A∩B; 若a∈C,则a∈A∩C。 因此,a∈A∩B或a∈A∩C,即 a∈(A∩B)∪(A∩C)。 再证(A∩B) ∩(A∩C) ? A∩ (B∪C) 。 任取 a∈(A∩B)∪(A∩C),则a∈A∩B或a∈A∩C。 若a∈A∩B,则a∈A且a∈ B; 若a∈A∩C,则a∈A且a∈ C。 总之,a∈A,且a∈B或a∈C,即a∈A且 a∈ B∪C, 亦即 a∈A∩(B∪C)。 综上: (A∩B)∩(A∩C)=A∩(B∪C)。

证明: ( A ? B) ? A ? B
证明:任取 a ? A ? B ,即a?A∪B,亦即

a?A且a?B,于是 a ? A 且a ? B ,故

a ? A ? B ,所以 ( A ? B) ? A ? B 任取 a ? A ? B ,即 a ? A 且a ? B ,亦即
a?A且a?B,于是a?A∪B ,故a ? A ? B,
所以

A ? B ? ( A ? B)

综上, ( A ? B) ? A ? B 得证。

容斥原理 (principle of

inclusion-exclusion)
? 结论1 设A1,A2是有限集,且不相交,则 | A1 ∪ A2 |= | A1| + |A2 |。 ? 结论2 设A1,A2是任意有限集,则 | A1 ∪ A2 |= | A1| + |A2 |- | A1 ∩ A2 |。 证明: A1∪A2可表为不相交的A1 和A2–A1的并, 于是, | A1 ∪ A2 |= | A1| + | A2 – A1 |。 A2 可表为不相交的A2 – A1和A1 ∩ A2的并, 于是 | A2 |= | A2 – A1 | + | A1 ∩ A2 | 。 由此得: | A1 ∪ A2 |= | A1| + |A2 |- | A1 ∩ A2 |。

容斥原理 (principle of

inclusion-exclusion)
?结论3 设A1,A2 ,A3是任意有限集,则 |A1∪A2∪A3|=|A1| + |A2| + |A3| - |A1∩A2||A1∩A3|-|A2∩A3|+|A1∩A2∩A3| 证明: |A1∪A2∪A3| = |(A1∪A2 ) ∪A3| = | A1∪A2 | + |A3| - |(A1∪A2)∩A3| = |A1|+|A2|-|A1∩A2|+|A3|-|(A1∩A3)∪(A2∩A3)| =|A1| +|A2|+|A3|-|A1∩A2||A1∩A3|-|A2∩A3|+|A1∩A2∩A3|。

容斥原理 (principle of

?设A1,A2,…,An是n个有限集合,则

inclusion-exclusion)

?A ? ? A ?? A ? A
i i ?1 i ?1 i i? j i

n

n

j

?

i? j ?k

? A ?A
i

j

? Ak

?? ? (?1) n ?1 A1 ? A2 ? ? ? An

称为包含排斥原理,简称容斥原理。
练习:
在小于等于30的正整数中,有多少个与2、3、5互质?

其它算律:
A? B ? A? B A ? B ? ( A ? B) ? ( B ? A) ? ( A ? B) ? ( A ? B)
A? A ??

??E
E ??

例,证明:A ? B ? A ? B
A ? B ? ( A ? B) ? ( A ? B) ? ( A ? B) ? ( A ? B) ? ( A ? B) ? ( A ? B) ? ( A ? A) ? ( A ? B) ? ( B ? A) ? ( B ? B) ? ( A ? B) ? ( A ? B)

A ? B ? ( A ? B) ? ( A ? B) ? ( A ? B) ? ( A ? B)
? ( A ? B) ? ( A ? B) ? ( A ? B) ? ( A ? B) ? ( A ? B) ? ( A ? B)
从而有:

A? B ? A? B

小结: 证明集合的包含关系的常用方法
令A,B是两个集合,证A?B的常用方法:

?方法1 利用定义来证明集合的包含关系。 要证明A?B,首先任取x?A,再演绎地证 出x ? B成立。特别,当A是无限集时,因 为我们不能对x ?A,逐一地证明x ? B成立, 所以证明时“x是任取的”就特别重要。
例. 证明若A?B,则 B ? A

证明集合的包含关系的常用方法
?方法2 设法找到一个集合T,满足A?T且T?B,由 包含关系的传递性有A?B. 例. 证明A-C?A?B

证明集合的包含关系的常用方法
? 方法3 利用A?B的等价定义,即A?B=B,A?B=A或 A-B=?来证. 例. 证明 A?C且B?C 当且仅当 A?B?C. 证明:必要性. (A?B)?C=(A?B)?C?C=(A?C)?(B?C) =C?C=C, 所以A?B?C. 充分性. A?C?(A?C)?B=(A?B)?C=C 所以A?C, 同理可证B?C.

证明集合的包含关系的常用方法
? 方法4 利用已知包含式的并、交等运算得到新的包含式 例.证明若A?C?B?C且A-C?B-C,则A?B. 证明:(A?C)?(A-C)?(B?C)?(B-C) (A?C)?(A? C )?(B?C)?(B? C ) A?(C? C )?B?(C? C ) A?E?B?E,所以A?B。

证明集合的包含关系的常用方法
?方法5 反证法 如上例(证明A?C?B?C且A-C?B-C则A?B.), 若不然,则有x?A 且x?B. 若x?C ,则x?A?C但x?B?C,与A?C?B?C 矛盾; 若x?C,则x?A–C但x?B-C,与A-C?B-C矛 盾。

证明集合相等的常用方法

?方法1 若A,B 是有限集,证明A=B可通过逐 一比较两集合所有元素均一一对应相等,若A, B 是无限集,通过证明集合包含关系的方法 证A ? B,B ? A即可。 ?方法2 反证法. ?方法3 通过集合的基本算律以及已证明的集 合等式,通过相等变换将待证明的等式左 (右)边的集合化到右(左)边的集合,或 者两边同时相等变换到同一集合。

例 设A,B,C是三个集合,已知A?B=A?C, A?B=A?C,求证B=C。 用方法2:使用反证法。假设B≠C,则必存在x,满 足x ? B,且x ? C,或者x ? B,且x ? C。不妨 设x ? B,且x ? C, ① 若x ? A,则x ? A?B,但x ? A?C,与 A?B=A?C矛盾。 ② 若x ? A,则x ? A?B,但x ? A?C,与 A?B=A?C矛盾。 所以原假设不对,B=C。 用方法3:利用已知以及集合运算的交换律、分配律 与吸收律,有 B = B?(A?B) = B?(A?C)= (B?A)?(B?C) = (C?A) ?(B?C)= C?(A?B)= C?(A?C) =C

?作业:习题1.1 1-5


相关文章:
《离散数学》试题及答案
离散数学》试题及答案_工学_高等教育_教育专区。一、填空题 1 设集合 A,B,其中 A={1,2,3}, B= {1,2}, 则 A - B=___; ?(B)= ___ 一、...
离散数学期末考试试题(有几套带答案)
离散数学期末考试试题(有几套带答案)_理学_高等教育_教育专区。离散试卷及答案 离散数学试题(A 卷及答案) 一、证明题(10 分) 1)(?P∧(?Q∧R))∨(Q∧R...
离散数学公式
离散数学公式_工学_高等教育_教育专区。基本等值式 1.双重否定律 A ? ┐┐A 2.幂等律 A ? A∨A, A ? A∧A 3.交换律 A∨B ? B∨A, A∧B ? ...
离散数学符号
离散数学符号 ? 全称量词 ?存在量词 ├ 断定符(公式在 L 中可证) ╞ 满足...平面 变动;求根公式 英语名 古希腊 现代希腊 中文注 数学意思 ΣζΤηΦθ...
离散数学答案
离散数学答案_理学_高等教育_教育专区。离散数学辅助教材概念分析结构思想与推理证明 第一部分 集合论刘国荣 交大电信学院计算机系 1 离散数学习题解答 习题一 (第一...
离散数学(左孝凌)课后习题解答(详细)
离散数学(左孝凌)课后习题解答(详细)_理学_高等教育_教育专区。离散数学(左孝凌)课后习题解答(详细)肯定对计算机专业的通知很有用 第1章 习题解答 离散数学~ 习题...
离散数学试卷
离散数学试卷_理学_高等教育_教育专区。新疆大学 2013—2014 学年度第二学期期末考试《离散数学》试卷 第一部分 选择题(共 20 分) 1、对任意集合 A、B、和 C...
离散数学
离散数学_数学_自然科学_专业资料。在线练习 离散数学 1 总分:100 考试时间:100 分钟 一、单项选择题 1、由 2 个命题变元组成的命题公式,有多少组赋值(正确...
2015年1月全国自考离散数学试题和答案
2015年1月全国自考离散数学试题和答案_IT认证_资格考试/认证_教育专区。2015自考压轴题,2015自考模拟试题,2015自考试题答案,2015自考,2015年1自考试题,自考试题答案 ...
离散数学第一章知识点总结
离散数学第一章知识点总结_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 离散数学第一章知识点总结_理学_高等教育_教育专区。...
更多相关标签:
离散 | 离散数学 pdf | 离散数学及其应用 | 离散数学 教学视频 | 离散数学课后习题答案 | 离散数学视频 | 离散数学自考试题 | 离散数学答案 |