离散数学省名师优质课赛课获奖课件市赛课一等奖课件

离散数学

DiscreteMathematics主讲教师：欧阳丹彤ouyd@助课教师：刘杰liu_jie@计算机学院智能信息处理研究室第1页离散数学是当代数学一个主要分支，也是计算机科学与技术一级学科及其相关专业必修基础理论关键课程。是学习后续专业课程不可缺乏数学工具。《中国计算机科学与技术学科教程》中将其列为计算机科学与技术专业14个知识领域之一。形成于七十年代早期，是伴随计算机科学发展而逐步建立。1、课程性质第2页研究对象：离散量结构及相互关系。离散量:逻辑量、图、树、整数、布尔代数连续量:温度、压力、体积、电压——计算机中离散处理可见，离散数学充分描述了计算机学科离散性特点。离散数学是一门理论性较强，应用性较广课程。1、课程性质第3页掌握离散数学基本概念和基本原理离散数学所包括概念、方法和理论，大量地出现在“编译原理”、“数据结构”、“操作系统”、“数据库系统”、“算法分析”、“定理机器证实”、“人工智能”等众多领域，为学习这些课程做了必要知识准备

。如：谓词逻辑成为程序语义理论和程序正确性证实主要研究工具；平面图理论被用于印刷电路板设计；图论概念和理论广泛用于AI、DS等；布尔代数为开关理论研究提供了分析工具，并造成了数字逻辑理论建立；代数系统理论被用于对数据结构研究，产生了抽象数据类型理论；代数系统理论成为编码理论数学基础。2、课程目标第4页离散数学、数据结构、算法设计与分析、组合数学和程序设计等课程紧密相关以问题求解步骤来详细说明5门课程紧密相关性：利用离散数学,组合数学等知识完成待解问题数学建模利用数据结构和算法设计知识选择、结构恰当数据结构，编写很好计算机算法对算法关键点，利用离散数学、组合数学知识进行正确性证实（此步骤是可选择）利用算法分析、离散数学、组合数学等知识对算法进行时空复杂性分析利用离散数学、算法设计、组合数学和运筹学等知识对算法进行优化（此步骤是可选择）(在算法基础上)使用程序设计技巧编写程序，使用程序测试技术测试程序，在计算机上完成问题求解。第5页数据结构、离散数学、算法设计与分析、组合数学和程序设计等课程紧密相关

数据结构、离散数学、算法、组合数学和汇编语言程序是图灵奖取得者、著名计算机科学家、数学家D.E.Knuth教授旷世之作《计算机程序设计艺术》主要内容。第6页2、课程目标提供良好数学训练（1）提升逻辑思维、抽象思维能力

（2）提升严密推理能力

（3）提升数学语言描述能力（4）提升判断对错能力—独立工作能力分析问题与处理问题能力第7页定义与定理多

离散数学是建立在大量定义之上逻辑推理学科，所以对概念了解是我们学习这门课程关键。在学习这些概念基础上，要尤其注意概念之间联络，而描述这些联络实体则是大量定理与性质。方法性强

离散数学许多证实题中，方法性是非常强，假如掌握了题证实方法，很轻易就能够证出来，反之则事倍功半。所以在学习该课程中要善于总结，勤于思索，这也是培养分析问题、处理问题能力与抽象思维能力一个过程。

3、课程特点第8页

4、怎样学好离散数学？掌握概念：在模棱两可地方多下功夫，弄懂、弄透。

认真完成作业一道题做完，还要提出以下几个问题：（1）是否必定一定对。（2）是否有更简练方法。（3）推理是否严密。（4）语言是否流畅。第9页5、离散数学教学内容第一章集合论基础（集合论）第二章命题逻辑第三章谓词逻辑第四章图与网络（图论）第五章数论基础（数论）六--八章抽象代数

----离散Ⅱ数理逻辑

离散Ⅰ第10页第一章集合论基础

§1.1集合基本概念§1.2关系§1.3映射第11页集合论发展史集合论(SetTheory)是当代数学基础．它起源可追溯到16世纪末，主要是对数集进行卓有成效研究．集合论实际发展是由19世纪70年代德国数学家康托尔(GCantor)在无穷序列和分析相关课题理论研究中创建．Cantor对含有任意特征无穷集合进行了深入探讨，提出了关于基数、序数、超穷数和良序集等理论，奠定了集合论深厚基础．所以，Cantor被誉为集合论创始人．他创建集合论是实数理论，以至整个微积分理论体系基础。第12页集合论创始人康托尔德国数学家

(GeorgCantor

1845－1918)第13页1845年3月3日出生于俄国一个丹麦—犹太血统家庭。1856年与父母一起迁到德国法兰克福。1863年进入柏林大学，转到纯粹数学。

1866年取得博士学位。1874年在《数学杂志》上发表了关于无穷集合理论第一篇革命性文章。数学史上普通认为这篇文章发表标志着集合论诞生。Cantor

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

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

克罗内克（L.Kronecker

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

对Cantor不一样评价第17页法国数学家庞加莱（H.Poincare1854－1912）：我个人，而且还不只我一人，认为主要之点在于，切勿引进一些不能用有限个文字去完全定义好东西。集合论是一个有趣“病理学情形”，后一代将把（Cantor）集合论看成一个疾病，而人们已经从中恢复过来了。第18页德国数学家魏尔（C.H.Hermann

Weyl，1885－1955）:关于基数等级观点是雾上之雾。菲利克斯.克莱因（F.Klein，1849－1925）:不赞成集合论思想。数学家H．A．施瓦兹—Cantor挚友因为反对集合论而同Cantor断交。第19页这对我来说是最值得钦佩数学理智之花，也是在纯粹理性范围中人类活动所取得最高成就之一。没有些人能把我们从康托尔为我们创造乐园中驱赶出去。——希尔伯特超限算术是数学思想最惊人产物，在纯粹理性范围中人类活动最美表现之一。——罗素由康托尔工作所带来哲学革命可能甚至比数学本身还伟大。——约代因第20页Cantor主要研究结果经过一一对应关系建立了集合之间等势概念，奠定了无限集分类基础。最著名著作--《超穷理论基础》:数学理论必须必定实无穷，因为很多最基本数学性质，比如一切正整数，圆周上一切点等，实际上都是实无穷性概念。而且不能把有穷所含有性质强加于无穷。他“一一对应”原理突破了传统“整体大于部分”旧观念，比如全体正整数与（其部分）全体正偶数一一对应，正整数集与正偶数集等势。第21页引进了可数集概念，证实了有理数全体及代数数（有理多项式根）全体都是可数集合。利用对角线方法证实了实数集是不可数集，从而间接推导出超越数（非代数数实数）比代数数多，同时也说明了无限集可按大小区分为不一样类。Cantor主要研究结果第22页Cantor主要研究结果证实了n维空间与一维直线之间存在一一对应。系统研究了序数理论，提出了良序原理。证实了集幂集比原集有更大基数。提出了连续统假设。第23页集合论发展史（继续）伴随集合论发展，以及它与数学哲学亲密联络所作讨论，1900年前后，出现了许多悖论，有力冲击了或者说动摇了集合论发展．（数学史上三次危机

无理数发觉──第一次数学危机无穷小是零吗？──第二次数学危机悖论产生——第三次数学危机）第24页著名罗素悖论：1902年，受到“剪发师悖论”启发而提出。

剪发师悖论：“一个剪发师宣称，他不给自己刮脸人刮脸，但给全部不自己刮脸人刮脸。”人们问：“剪发师先生，您自己脸谁刮？”（悖论不是谬论，悖论中充满着令人惊奇内容——悖论能够推导出自相矛盾结论，人们却难以指出悖论非法理由。公元前6世纪，希腊人伊比孟德说：“我说这句话时正在说谎。”伊翁问听众，他上面说那句话是真话还是假话？该怎么回答伊翁呢？“下面句子是错，上面句子是正确。”问“下面句子是错”为真还是为假？)第25页伯特兰·罗素（1872-1970）

英国著名哲学家、数学家、逻辑学家、

散文作家、社会活动家

第26页1872年5月，生于英国曼摩兹郡特雷克，幼年时父母双亡，是祖母将他抚育成人。1890年进剑桥大学三一学院学习1893年获数学荣誉学士学位一级。接着改学哲学1894年获道德哲学荣誉学士学位一级毕业后曾游学德国学经济，受马克思主义影响，回国后，在伦敦大学政治和经济学院任讲师。l903年发表《数学原理》一书，并以论文《几何学基础》获三一学院研究员职位。1908年当选为皇家学会会员。罗素生平第27页1910年发表《哲学文集》;1917年发表《哲学问题》。1914年加入工党。第一次世界大战期间，因参加和平主义者活动，被处罚金，革职入狱。在狱中，撰写了《数学哲学导论》（1919）。1920年访问中国和苏联，著有《布尔什维主义实践和理论》。1920年到北大担任客座教授，一年后离开，隔年写成《中国问题》这本书。他看见：“中国文化正在发生急遽改变”，提出提议：“假如中国人能自由地吸收我们文明中他们所需要东西，而排斥那些他们以为不好东西，那么他们将能够在其本身传统中取得一个有机发展，并产生将我们优点同他们自己优点相结合起来辉煌成就。”第28页1927年，罗素和夫人布拉克在英国彼得斯费尔德市附近创办一所私立学校，试验他教育理论，是当初英国进步主义学校之一。1935年离婚后，布拉克独自办到1939年。他一直主张“自由教育”和“爱教育”。认为教育基本目标是品格发展，而“活力、勇气、敏感和智慧”是形成“理想品格”基础；并深信经过对儿童身体、感情和智力上“恰当处理”，能够使这些品质得到普遍培养。第29页1931年他继承为第三世罗素勋爵。1949年获荣誉勋章。1950年因为他“多产而主要哲学著作，并以此成为人道主义与自由思想代言人”而取得了该年度诺贝尔文学奖。

第30页

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

1970年2月2日逝世，一生曾四次结婚，三次离婚。第32页《罗素自传》序言我为何而活着

对爱情渴望，对知识追求，对人类苦难不可遏制同情心，这三种纯洁但无比强烈激情支配着我一生。这三种激情就像飓风一样，在深深苦海上，肆意地把我吹来吹大，吹到濒临绝望边缘。

我寻求爱情，首先因为爱情给我带来狂喜，它如此强烈以致我经常愿意为了几小时欢愉而牺牲生命中其它一切。我寻求爱情，其次是因为爱情解除孤寂——那是一颗震颤心，在世界边缘，俯瞰那冰凉死寂、深不可测深渊。我寻求爱情，最终是因为在爱情结合中，我看到圣徒和诗人们所想象天堂景象神秘缩影。这就是我所寻求，即使它对人生似乎过于美好，然而最终我还是得到了它。第33页我以一样热情寻求知识，我希望了解人心灵。我希望知道星星为何闪闪发光，我试图了解毕达哥拉斯思想威力，即数字支配着万物流转。这方面我取得一些成就，然而并不多。

爱情和知识，尽其可能地把我引上天堂，不过同情心总把我带回尘世。痛苦呼号回声在我心中回荡，饥饿儿童，被压迫者折磨受害者，被儿女视为可厌负担无助老人以及充满孤寂、贫穷和痛苦整个世界，都是对人类应有生活嘲讽。我渴望减轻这些不幸，不过我无能为力，而且我自己也深受其害。

这就是我一生，我以为它值得活。假如有机会话，我还愿意再活—次。第34页TheProloguetoBertrandRussell'sAutobiography

WhatIHaveLivedFor

Threepassions,simplebutoverwhelminglystrong,havegovernedmylife:thelongingforlove,thesearchforknowledge,andunbearablepityforthesufferingofmankind.Thesepassions,likegreatwinds,haveblownmehitherandthither,inawaywardcourse,overagreatoceanofanguish,reachingtotheveryvergeofdespair.

Ihavesoughtlove,first,becauseitbringsecstasy-ecstasysogreatthatIwouldoftenhavesacrificedalltherestoflifeforafewhoursofthisjoy.Ihavesoughtit,next,becauseitrelievesloneliness--thatterriblelonelinessinwhichoneshiveringconsciousnesslooksovertherimoftheworldintothecoldunfathomablelifelessabyss.Ihavesoughtitfinally,becauseintheunionofloveIhaveseen,inamysticminiature,theprefiguringvisionoftheheaventhatsaintsandpoetshaveimagined.ThisiswhatIsought,andthoughitmightseemtoogoodforhumanlife,thisiswhat--atlast--Ihavefound.第35页WithequalpassionIhavesoughtknowledge.Ihavewishedtounderstandtheheartsofmen.Ihavewishedtoknowwhythestarsshine.AndIhavetriedtoapprehendthePythagoreanpowerbywhichnumberholdsswayabovetheflux.Alittleofthis,butnotmuch,Ihaveachieved.

Loveandknowledge,sofarastheywerepossible,ledupwardtowardtheheavens.Butalwayspitybroughtmebacktoearth.Echoesofcriesofpainreverberateinmyheart.Childreninfamine,victimstorturedbyoppressors,helplessoldpeopleaburdentotheirsons,andthewholeworldofloneliness,poverty,andpainmakeamockeryofwhathumanlifeshouldbe.Ilongtoalleviatethisevil,butIcannot,andItoosuffer.

Thishasbeenmylife.Ihavefounditworthliving,andwouldgladlyliveitagainifthechancewereofferedme.第36页罗素谚语许多人宁愿死，也不愿思索，实际上他们也确实至死都没有思索。我人生正是：使事业成为喜悦，使喜悦成为事业。一部分儿童有思索习惯，而教育目标在于铲除他们这种习惯。乞丐并不会妒忌百万富翁，不过他必定会妒忌收入更高乞丐。即使真相并不令人愉快，也一定要做到老实，因为掩盖真相往往要费更大力气。不要为自己持独特看法而感到害怕，因为我们现在所接收常识都曾是独特看法。不用盲目地崇敬任何权威，因为你总能找到相反权威。凡事不要抱绝对必定态度。第37页因为Cantor所创建朴素集合论产生了悖论，促进了集合论公理化工作。含有代表性工作有两个：由德国数学家策梅洛(E.Zermelo)于1908年首先建立，以后由以色列数学家弗兰克尔(A.A.Fraenkel)，挪威数学家斯科伦(T.Skolem)与冯•诺依曼(vonNeumann)等人于20世纪20年代加以改进ZF公理集合论系统，加入选择公理系统成为ZFC。vonNeumann-Bernays-Gödel公理系统，简称NBG系统。教材主要介绍Cantor朴素集合论工作。第38页集合论在计算机科学、人工智能领域、逻辑学及语言学等方面都有着主要应用．对于从事计算机科学工作者来说，集合论是不可缺乏理论知识，熟悉和掌握它是十分必要．第39页§1.1集合基本概念一、基本概念什么是集合(Set)？“所要讨论一类对象整体”；“含有同一性质单元集体”“所谓集合，是指我们无意中或思想中将一些确定，彼此完全不一样客体总和而考虑为一个整体。这些客体叫做该集合元素”通常，用大写英文字母A,B,C,……表示集合；第40页1、二十六个英文字母能够看成是一个集合；2、全部自然数看成是一个集合；约定自然数包含03、吉林大学软件学院级本科学生能够看成是一个集合；4、这间教室中全部座位能够看成是一个集合。比如:第41页集合元素(member或element)组成一个集合那些对象或单元称为这个集合元素。通常，用小写英文字母a,b,c,…表示集合中元素第42页设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属于(belongto)第43页约定，存在一个没有任何元素集合，称为空集(emptyset)

，记为

，有时也用{}来表示。约定，所讨论对象全体称为全集(universalset)，记作E或U，我们所讨论集合都是全集子集。全集是相正确。空集、全集第44页包含有限个元素集合，称为有限集或有穷集(finiteset)；包含无限个元素集合，称为无限集或无穷集(infiniteset

)。例：空集是有限集，全部英文字母组成集合是有限集，整数集合是无限集。有限集、无限集

第45页设A是有穷集合，A中元素个数称为集合A元素数，记为

A

。比如，设A是全部小写英文字母组成集合，则

A=26。

尤其，||=0，|{}|=1集合元素数（基数）第46页列举法（外延法）将集合中元素一一列举，或列出足够多元素以反应集合中元素特征，比如：V={a,e,i,o,u}或B={1,4,9,16,25,36……}。描述法（内涵法）经过描述集合中元素共同特征来表示集合，比如：V={x|x是英语元音字母}，B={x|x=a2,a是非零整数}惯用集合表示法第47页文氏图(VennDiagram)

英国数学家JohnVenn提出用一个大矩形表示全集，在矩形内画一些圆或其它简单封闭曲线，用其内部来表示集合，能够用一些点来表示集合中特定元素。比如：集合V={a,e,i,o,u}，用文氏图表示以下:注意：文氏图只是示意图，即使直观、有利于记忆，但不用于证实。全集EVaeiou第48页确定性；互异性；无序性；多样性；集合特征第49页任何一个对象，或者是这个集合元素，或者不是，二者必居其一；比如：A={x|x是自然数，且x<100} B={x|x是年轻人} C={x|x是秃子}确定性第50页集合中任何两个元素都是不一样，即集合中不允许出现重复元素。比如：集合A={a,b,c,c,b,d}，实际上，应该是A={a,b,c,d}互异性第51页集合与其中元素次序无关，集合中元素是没有次序，或者说，我们不考虑集合中元素次序。比如：集合{a,b,c,d,e}、{d,c,e,a,b}、{e,c,d,b,a}，都是表示同一个集合。无序性第52页集合中元素能够是任意对象，相互独立，不要求一定要具备显著共同特征。比如：

A={a,{a},{{a},b},{{a}},1}

B={1,a,*,-3,{a,b},{x|x是汽车},地球,板儿砖}多样性第53页康托尔朴素集合论剖析康托尔集合论中许多证实便知，几乎他所证实一切定理均能从以下三个公理得出:外延公理任意两个集合相等，当且仅当它们中各个元素都是相同。抽象公理任给一个性质，都有一个满足该性质对象所组成集合。选择公理每个集合都有一个选择函数。Note:毛病出在抽象公理上.1903年,Russel发觉“由不为本身组员这一性质全部客体集合”会导出矛盾来,这就是著名罗素悖论.第54页设集合S={A|A是集合，且A

A}若S

S，则S是集合S元素，则依据S定义，有S

S，与假设矛盾；若S

S，则S是不以本身为元素集合，则依据S定义，有S

S，与假设矛盾。罗素悖论(Russell’sparadox)

第55页当两个集合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}【定义1】集合相等第56页设A，B是两个集合，若A元素都是B元素，则称A是B子集，也称B包含A，或A包含于B，记以A

B，或B

A

。若A

B，且A

B，则称A是B真子集(propersubset)，也称B真包含A，或A真包含于B，记以A

B，或B

A。

【定义2】子集(subset)

第57页设A={2,4,6,8}，B={x|x是正偶数}，C={x|x是整数},则有A

B，B

C，A

C,而且A

B，BC，A

C

。{x}

A当且仅当xA。例：

第58页对任意集合A,有A

A。若A

B，BC，则A

C

。对于任意两个集合A、B，A=B当且仅当A

B且B

A。空集是任意集合子集，是任意非空集合真子集，且空集是唯一。证实：取任意集合A，因为x∈是恒假，故x(x∈

x∈A)是恒真，即A。（

，

，∈

{

}）主要结论第59页是否存在集合A和B,使得A

B且AB？若存在，请举一例。设A={a}，B={a,{a},b,c}，则有:

A

B且AB再比如：

{

}且

{

}讨论：第60页设A是集合，A全部子集为元素做成集合称为A幂集，记以

(A)或2A。

(A)={S|SA}例：

A={a,b,c}，则

(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}【定义3】幂集(powerset)第61页注意幂集合依然是集合。比如，用枚举法写出集合{a,b}幂集合：

正确写法：

(A)={,{a},{b},{a,b}}错误写法：(A)=,{a},{b},{a,b}

？写出

(

)，((

))，(((

)))第62页若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个子集。幂集性质第63页幂集性质 其次，要获取集合A一个子集，那么，A中每个元素都有两种取法，要么在这个子集中，要么不在。而且每个元素取法之间是相互独立，互不影响，这么，我们依据乘法原理，能够很轻易得出集合A一共有：2×2×…×2=2n个子集。第64页幂集性质

这么，我们就证实了 若A为有穷集，|A|=n，则

|2A|=Cn0+Cn1+

…+Cnn=2n。 注意：我们证实过程采取是“组合分析”方法，在《组合数学》中会有详细讲解。第65页幂集性质

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)。第66页幂集性质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，故xB。所以A

B。（假如

(A)

(B)，那么A全部子集都是B子集，轻易知道A

A，则A

B。）第67页设C是一个集合。若C元素都是集合，则称C为集合族。若集合族C可表示为C={Sd

d

D}，则称D为集合族C标志（索引）集。

【定义4】集合族、标志集第68页显然，2A是一个集合族。设A0,A1,A2,…是集合序列，且两两之间互不相同，则集合{A0,A1,A2,…}是一个集合族，可表示为{Ai|iN}，其中,N是自然数集合，是该集合标志集合。(1)若{A1,A2,A3,…}为一个集合族，那么它索引集为N+。(2)2A是一个集合族，若将2A写为{A0,…,A2n-1}，那么它索引集为{0,…,2n-1}。例．第69页设A，B是两个集合。全部属于A或者属于B元素做成集合，称为A和B并集，记以A∪B。即A∪B={x|xA或xB}比如，令A={a，b，c，d}，B={c，d，e，f}，于是A∪B={a，b，c，d，e，f}。

二、集合运算及性质

【定义5】集合并集(Union)第70页并集文氏图ABA∪B第71页设A，B是两个集合。由属于A且属于B元素组成集合，称为A和B交集，记以A∩B。即A∩B={x|xA且xB}比如，令A={a，b，c，d}，B={c，d，e，f}，于是A∩B={c，d}。【定义6】集合交集(Intersection)第72页交集文氏图ABA∩B第73页设A1，A2，…，An是n个集合，则，

A1∪A2∪…∪An，简记为

A1∩A2∩…∩An，简记为并集和交集推广(∪∩满足结合律)第74页设A，B是两个集合。由属于集合A而不属于集合B全部元素组成集合，称为A与B差集，记以A-B，或A\B。

即A-B={x|xA且xB}例.令A={a，b，c，d}，B={c，d，e，f}，于是A-

B={a，b}。【定义7】集合差集(Difference)第75页差集文氏图ABA－BE第76页设A是一个集合，全集E与A差集称为A补集或余集，记以A。即A=E-A比如，令E={a，b，c，d，e，f}，A={b，c}，于是A={a，d，e，f}。

尤其，【定义8】集合补集(Complement)第77页补集文氏图AA补集E第78页设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}。【定义9】集合环和（对称差）第79页环和（对称差）文氏图ABA

BE第80页设A，B是两个集合，则A与B环积定义为

A

B=A

BA

B＝（A∩B）∪（A∪B）【定义10】集合环积第81页环积文氏图ABA

B=（A∩B）∪（A∪B）E第82页将(a1,a2,…,an)称为有序n元组，其中，a1是其第一个元素，a2是其第二个元素，…，an是其第n个元素。两个有序n元组(a1,a2,…,an)和(b1,b2,…,bn)相等当且仅当ai=bi,i=1,2,…,n【定义11】有序n元组(orderedn-tuple)第83页对于有序n元组，当n=2时，将其称作有序二元组，也称作有序对，或序偶。有序正确特点：若a

b,则（a，b）

（b，a）两个有序对(a,b)和(c,d)相等当且仅当a=c，b=d【定义12】有序对(orderedpairs)第84页设A，B是两个集合，全部有序对(x,y)做成集合(其中x

A，y

B)，称为A，B直乘积(笛卡儿积)，记以A

B。A

B={(x，y)

x

A且y

B}。【定义13】笛卡儿积(Cartesianproduct)第85页笛卡儿(René

Descartes，1596～1650)

在数学史上，笛卡儿因与费马共同创建解析几何而闻名于世。与此同时，笛卡儿还是一位哲学家、物理学家、生物学家，尤其在哲学上出色贡献使他成为当之无愧一代哲学大师。第86页笛卡儿是法国人，出生于一个贵族家庭，因为体弱多病，养成了在床上读书习惯，这使得他有更多时间独自静静地思索各种关于自然、科学与人问题。1628年，笛卡儿移居荷兰，潜心从事哲学、数学、天文学、物理学、化学和生理学等领域研究。他主要著作都是在荷兰完成，其中1637年出版《方法论》一书成为哲学经典。这本书中3个著名附录《几何》、《折光》和《气象》更奠定了笛卡儿在数学、物理和天文学中地位。第87页在《几何》中，笛卡儿分析了几何学与代数学优缺点，指出：希腊人几何过多依赖于图形，总是要寻求一些奇妙想法。代数却完全受法则和公式控制，以致于妨碍了自由思想和创造。他同时看到了几何直观与推理优势和代数机械化运算力量。于是笛卡儿着手处理这个问题，并由此创建了解析几何。1650年2月，笛卡儿在瑞典病逝。

第88页设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}。【定义14】笛卡儿积推广第89页设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)}；比如：第90页|A

B|=

A

B

；对任意集合A，有A=，

A=；直乘积运算不满足交换律，即ABBA；

直乘积运算不满足结合律，即(AB)CA(BC)直乘积性质第91页5.直乘积运算对并和交运算满足分配律，即:

A(B∪C)=(AB)∪(AC)，

(B∪C)A=(BA)∪(CA)，

A(B∩C)=(AB)∩(AC)，(B∩C)A=(BA)∩(CA)；

6.设A，B，C，D是集合，若AC且BD，则ABCD。

第92页等幂律：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。对于任意集合A,B,C有以下算律：第93页互补律：DeMorgan律：

同一律： E∩A=A，

∪A=A。零一律：

∩A=

，E∪A=E。双重否定律：第94页证实：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)。第95页证实：任取，即a

A∪B，亦即a

A且a

B，于是且，故

，所以任取，即且，亦即a

A且a

B，于是a

A∪B，故 ，所以综上，得证。证实：第96页结论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|。容斥原理(principleofinclusion-exclusion)第97页结论3

设A1，A2，A3是任意有限集，则|A1∪A2∪A3|=|A1|

+

|A2|+

|A3|-|A1∩A2|-|A1