离 散 数 学 Discrete Mathematics

Presentation on theme: "离 散 数 学 Discrete Mathematics"— Presentation transcript:

1 离 散 数 学 Discrete Mathematics
主讲教师：欧阳丹彤 计算机学院智能信息处理教研室

2 1、课程的性质 离散数学是现代数学的一个重要分支，也是计算机科学与技术一级学科及其相关专业必修的基础理论的核心课程。是学习后续专业课程不可缺少的数学工具。《中国计算机科学与技术学科教程》中将其列为计算机科学与技术专业14个知识领域之一。 形成于七十年代初期，是随着计算机科学的发展而逐步建立的。

3 1、课程的性质 研究对象：离散量结构及相互关系。 离散量:逻辑量、图、树、整数、布尔代数 连续量:温度、压力、体积、电压
—— 计算机中离散处理 可见，离散数学充分描述了计算机学科离散性的 特点。 离散数学是一门理论性较强，应用性较广的课程。

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

5 2、课程的目的 提供良好的数学训练 分析问题与 解决问题 的能力 （1）提高逻辑思维、抽象思维能力 （2）提高严密的推理能力
思维的重要性 （2）提高严密的推理能力 推理—思维中平常又平常的事情 （3）提高数学语言描述能力 （4）判断对错能力—独立工作能力 分析问题与 解决问题 的能力

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

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

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

9 第一章 集合论基础 §1.1 集合的基本概念 §1.2 关 系 §1.3 映 射

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

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

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

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

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

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

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

17 德国数学家魏尔（C.H.Hermann Weyl，1885－1955）:
关于基数的等级观点是雾上之雾。 菲利克斯.克莱因 （F.Klein，1849－1925）: 不赞成集合论的思想。 数学家H．A．施瓦兹—Cantor的好友 由于反对集合论而同Cantor断交。

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

19 Cantor的主要研究成果 通过一一对应关系建立了集合之间等势的概念，奠定了无限集分类的基础。
最著名的著作--《超穷理论基础》:数学理论必须肯定实无穷，因为很多最基本的数学性质，例如一切正整数，圆周上的一切点等，事实上都是实无穷性的概念。而且不能把能有穷所具有的性质强加于无穷。他的“一一对应”的原理突破了传统的“整体大于部分”的旧观念，例如全体正整数与（其部分）全体正偶数一一对应，正整数集与正偶数集等势。

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

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

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

23 著名的罗素悖论：1902年，受到“理发师悖论”的启发而提出。 理发师悖论：“一个理发师宣称，他不给自己刮脸的人刮脸，但给所有不自己刮脸的人刮脸。”人们问：“理发师先生，您自己的脸谁刮？”
（悖论不是谬论，悖论中充满着令人惊奇的内容——悖论可以推导出自相矛盾的结论，人们却难以指出悖论非法的理由。公元前6世纪，希腊人伊比孟德说： “我说这句话时正在说谎。” 伊翁问听众，他上面说的那句话是真话还是假话？该怎么 回答伊翁呢？ “下面的句子是错的， 上面的句子是对的。”问“下面的句子是错的”为真还是为假？)

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

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

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

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

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

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

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

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

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

33 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.

34 With equal passion I have sought knowledge
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.

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

36 由于Cantor所创立的朴素集合论产生了悖论，促进了集合论公理化的工作。 具有代表性的工作有两个：
由德国数学家策梅洛(E.Zermelo)于1908年首先建立，后来由以色列数学家弗兰克尔(A.A.Fraenkel)，挪威数学家斯科伦(T.Skolem)与冯•诺依曼(von Neumann)等人于20世纪20年代加以改进的ZF公理集合论系统，加入选择公理的系统成为ZFC。 von Neumann-Bernays-Gödel公理系统，简称NBG系统。 教材主要介绍Cantor的朴素集合论的工作。

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

38 §1.1 集合的基本概念 一、基本概念 什么是集合(Set)？ “所要讨论的一类对象的整体”； “具有同一性质单元的集体”
§1.1 集合的基本概念 一、基本概念 什么是集合(Set)？ “所要讨论的一类对象的整体”； “具有同一性质单元的集体” “所谓集合，是指我们无意中或思想中将一 些确定的，彼此完全不同的客体的总和而考虑 为的一个整体。这些客体叫做该集合的元素” 通常，用大写的英文字母A, B, C,……表示集合；

39 例如: 1、二十六个英文字母可以看成是一个集合； 2、所有的自然数看成是一个集合；约定自然数包括0
3、吉林大学软件学院2006级的本科学生可以看成是一个集合； 4、这间教室中的所有座位可以看成是一个集合。

40 集合的元素(member或element)
组成一个集合的那些对象或单元称为这个集合的元素。 通常，用小写的英文字母a, b, c,…表示集合中的元素

41 属于(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

42 空集、全集 约定，存在一个没有任何元素的集合，称为空集(empty set) ，记为，有时也用{}来表示。
约定，所讨论的对象的全体称为全集(universal set)，记作E或U，我们所讨论的集合都是全集的子集 。全集是相对的。

43 有限集 、无限集 包含有限个元素的集合，称为有限集或有穷集(finite set)；
包含无限个元素的集合，称为无限集或无穷集(infinite set )。 例：空集是有限集，所有英文字母组成的集合是有限集，整数集合是无限集。

44 集合的元素数（基数） 设A是有穷集合， A中元素的个数称为集合A的元素数，记为A。

45 常用的集合表示法 列举法；将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，例如：V={a,e,i,o,u} 或B={1,4,9,16,25,36……}。 描述法；通过描述集合中元素的共同特征来表示集合，例如： V= {x|x是英语元音字母} ，B= {x|x=a2 , a是非零整数}

46 E a u V 文氏图(Venn Diagram) 英国数学家John Venn提出
用一个大的矩形表示全集，在矩形内画一些圆或其它简单封闭曲线，用其内部来表示集合，可以用一些点来表示集合中的特定元素。 例如：集合V={a,e,i,o,u} ，用文氏图表示如下: a u E V 注意：文氏图只是示意图，虽然直观、有助于记忆， 但不用于证明。

47 集合的特征 确定性； 互异性； 无序性； 多样性；

48 确定性 任何一个对象，或者是这个集合的元素，或者不是，二者必居其一； 例如：A={x|x是自然数，且x<100}
B={x|x是年轻人} C={x|x是秃子}

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

50 无序性 集合与其中的元素的顺序无关，集合中的元素是没有顺序的，或者说，我们不考虑集合中元素的顺序。
例如： 集合{a,b,c,d,e}、{d,c,e,a,b}、 {e,c,d,b,a}，都是表示同一个集合。

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

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

53 罗素悖论(Russell’s paradox)
设集合S={A|A是集合，且AA} 若SS，则S是集合S的元素，则根据S的定义，有S  S，与假设矛盾； 若SS，则S是不以自身为元素的集合，则根据S的定义，有SS，与假设矛盾。

54 【定义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}

55 【定义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 。

56 例： 设A={2,4,6,8} ，B= {x|x是正偶数}， C={x|x是整数}, 则有 A  B，B C，AC, 并且
{x}  A 当且仅当 x A。

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

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

59 【定义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}}

60 注意 幂集合仍然是集合。 正确的写法：(A)={,{a},{b},{a,b}}
？写出()， (())，  ( (()))

61 幂集的性质 若A为有穷集，|A|=n，则 |2A | = Cn0 + Cn1 + … + Cnn =2n 。
有Cn0 个，从A中取1个元素构成A的子集，有Cn1 个，以 此类推，从A中取n个元素构成A的子集，有Cnn 个。而 且取的元素个数不同，肯定得到不同的子集，根据加法 原理，集合A一共有Cn0 + Cn1 + … + Cnn 个子集。

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

63 幂集的性质 这样，我们就证明了 若A为有穷集，|A|=n，则 |2A | = Cn0 + Cn1 + … + Cnn =2n 。
注意：我们的证明过程采用的是“组合分析”的方法，在《组合数学》中会有详细的讲解。

64 幂集的性质 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)。

65 幂集的性质 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。）

66 设C是一个集合。若C的元素都是集合，则称C为集合族。
【定义4】集合族、标志集 设C是一个集合。若C的元素都是集合，则称C为集合族。 若集合族C可表示为C={SddD}，则称D为集合族C的标志（索引）集。

67 显然，2A是一个集合族。 设A0, A1, A2, …是集合的序列，且两两之间互不相同，则集合{A0, A1, A2, …}是一个集合族，可表示为 {Ai| iN}，其中,N是自然数集合，是该集合的标志集合。

68 二、集合的运算及性质 【定义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}。

69 并集的文氏图 A B A∪B

70 【定义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}。

71 交集的文氏图 A B A∩B

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

73 【定义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}。

74 差集的文氏图 E A B A－B

75 【定义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}。 特别，

76 补集的文氏图 E A A的补集

77 【定义9】集合的环和（对称差） 设A，B是两个集合。则A与B的环和(对称差),记以AB, 定义为 AB=(A-B)∪(B-A)。
令A={a，b，c，d}，B={c，d，e，f}，于是 AB={a，b，e，f}。

78 环和（对称差）的文氏图 E A B AB

79 【定义10】集合的环积 设A，B是两个集合，则A与B的环积定义为 A  B = AB A  B ＝ （A∩B）∪（ A∪B ）

80 环积的文氏图 E A B A  B =（A∩B）∪（ A∪B ）

81 【定义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

82 【定义12】有序对(ordered pairs)
对于有序n元组，当n=2 时，将其称作有序二元组，也称作有序对，或序偶。 有序对的特点： 若ab,则（a，b）（b，a） 两个有序对(a,b)和(c,d)相等当且仅当a=c，b=d

83 【定义13】笛卡儿积(Cartesian product)
设A，B是两个集合，所有有序对(x, y)做成的集合(其中xA，yB)，称为A，B的直乘积(笛卡儿积)，记以AB。 AB={(x，y)xA且yB}。

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

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

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

87 【定义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 }。

88 例如： 设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)}；

89 直乘积的性质 |AB|=A  B； 对任意集合A，有A=，A=； 直乘积运算不满足交换律，即ABBA；
直乘积运算不满足结合律，即(AB)CA(BC)

90 5. 直乘积运算对并和交运算满足分配律， 即: 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。

91 对于任意集合A,B,C有如下算律： 等幂律： A∩A=A，A∪A=A。 交换律： A∩B=B∩A，A∪B=B∪A。
结合律： (A∩B)∩C=A∩(B∩C)， (A∪B)∪C=A∪(B∪C)。 分配律：A∩(B∪C)=(A∩B)∪(A∩C)， A∪(B∩C)=(A∪B)∩(A∪C)。 5. 吸收律：A∩(A∪B)=A， A∪(A∩B)=A。

92 互补律： De Morgan律： 同一律： E∩A=A，∪A=A。 零一律： ∩A=，E∪A=E。 双重否定律：

93 证明： 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)。

94 证明： 证明：任取 ，即aA∪B，亦即aA且aB，于是 且 ，故 ，所以
任取 ，即 且 ，亦即aA且aB，于是aA∪B ，故 ，所以 综上， 得证。

95 容斥原理 (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 |。

96 容斥原理 (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|。

97 容斥原理 (principle of inclusion-exclusion)
设A1，A2，…，An是n个有限集合，则 称为包含排斥原理，简称容斥原理。

98 其它算律：

99 例，证明：

100 从而有：

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

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

103 证明集合的包含关系的常用方法 方法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.

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

105 证明集合的包含关系的常用方法 方法5 反证法 如上例(证明ACBC且A-CB-C则AB.)， 若不然，则有xA 且x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矛盾。

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

107 例 设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