第一章集合王元元

1计算机科学中的离散结构浙江海洋学院数理与信息学院2课程基本情况总学时：56；周学时4，共14周学分：3.5考核方式：考试（平时30%，期末70%）先修课程：线性代数，计算机编程基础参考书目：离散数学及其应用（美.罗森著）离散数学导论（王元元等编著）3课程简介一、什么是离散数学离散数学是数学中适用于研究离散对象的那一部分。“离散”与“连续”是数量关系中一对极为深刻的矛盾，“离散”是“连续”的否定。例如：实数是连续的，整数是不连续的。4计算机是基于0和1的运算，它只能处理离散的或离散化了的数量关系。因此无论是计算机科学本身，还是与计算机应用密切相关的领域，都面临着如何对离散结构建立相应的数学模型，又如何将已用连续数量关系建立起来的数学模型离散化，从而由计算机加以处理。5二、离散结构课程的地位和作用离散结构是信息与计算机专业的一门专业基课，又被称为计算机数学。1离散数学为计算机专业的后继课程如操作系统、数据库、编译原理、人工智能等课程提供必要的数学基础。2为学生今后从事计算机科学和技术各方面的工作提供有力的工具。6三、离散结构课程的特点以离散量为研究对象，内容丰富，涉及面较宽。因此概念多、定理多、推理多并且内容较为抽象。但由于它是为学生后继专业知识的学习做必要的数学准备，因此它研究的内容均比较基础，难度不大。7重点：外延性公理、集合相等的充分必要条件掌握集合的概念及表示法；深刻理解两个集合相等的定义和充分必要条件；掌握子集、真子集、空集、全集、幂集的定义；熟练掌握集合的五种基本运算：并、交、补、差、对称差及其满足的性质；掌握笛卡儿积的概念；第一章集合代数8第一章集合代数集合论是现代数学的基础创始人：Cantor91.1集合的概念与表示集合是有确定的、互相区别的、并作整体识别的一些对象组成的总体。浙江海洋学院的全体学生。方程x2-2x+1=0的解。好书的全体。组成集合的对象称为集合的元素。一、集合的概念10通常用大写英文字母来标记集合，用小写英文字母标记组成集合的元素。若a是集合A的元素，则记作“a∈A”若a不是集合A的元素，则记作“aA”11二、集合的表示1.几个常见的集合的表示符号：N：所有自然数集合。I或Z：所有整数的集合。（I+：所有正整数的集合）Q：所有有理数的集合。C：所有复数的集合。R：所有实数的集合。Nn：从0到n-1，这前n个自然数的集合。（E：偶整数集合）122.集合的表示方法(1)列举法：按任意顺序逐一列举集合中的元素于花括号内，元素之间用逗号隔开。例如：A={2,a,b,9}(元素无次序、不重复)(2)描述法：给定一个条件P(x)，当且仅当元素a使P(a)成立时，a∈A。其一般形式为A={x∣P(x)}例如：A={X|X能被3整除}(3)归纳法133.特殊的集合有限集，集合的基数有限集：空集和只含有有限个元素的集合。有限集合中成员的个数称为集合的基数。集合A的基数，记作|A|。空集没有任何元素的特定集合，称为空集，记作。例如A={x|x∈R且x2+8=0}=全集全体对象组成的集合，称为全集，记作U。14三、外延性公理1.外延性公理：集合A和集合B相等，当且仅当它们具有相同的元素。{a,b,c}={b,a,c}={x|x=a或x=b或x=c}152.定义定义1-3集合A称为集合B的子集合，如果A的每一个元素都是B的元素，即，若元素x属于A，那么x属于B。A是B的子集，则记作AB。如果A不是B的子集，则记作AB。例如设A={a,b,c,d},B={a,e,x,y,z},C={a,x}存在这样两个集合，其中一个既是另一个的子集，又是它的元素。163.性质定理1-1对任意集合A，B，A=B当且仅当AB且BA。特别地，对任意集合A，AA。定理1-2对任意集合A，AU。定理1-3设A，B，C为任意集合，若AB且BC。则AC。17定理1-4对任意集合A，。A定理1-5空集是唯一的。定理1-6设A为一有限集合，|A|=n，那么A的子集个数为2n。定义1-4集合A称为集合B的真子集，如。记为。且ABABAB181.并集设有集合A、B，属于A或属于B的所有元素组成的集合称为A与B的并集，记作。即或ABx|xAxBAB例如设A={a,b,c},B={c,d,f},C={b,e}则ABa,b,c,d,fACa,b,c,eBCb,c,d,e,f1.2集合运算192.交集设有集合A、B，属于A同时又属于B的所有元素组成的集合称为A与B的交集，记作。即AB且ABx|xAxB例如设A={a,b,c,d},B={d,f,a},C={e,f,g}则ABd,aACBC{f}203.差集设有集合A、B，所有属于A而不属于B的元素组成的集合，称为A与B的差集，记作A-B。即且ABx|xAxB例如设A={a,b,c,d},B={d,f,a},C={e,f,g}B-A={f},C-A={e,f,g}=C214补集集合A相对于全集合U的差集称为A的补集，记作。即A且AUAx|xUxAx|xAAAA22集合运算的定律1.集合运算的十条定律对于全集合U的任意子集A、B、C，有：交换律ABBA结合律A(BC)(AB)C分配律A(BC)(AB)(AC)A(BC)(AB)(AC)同一律AAAUA23互补律AAUAA对合律AA等幂律AAA零一律AUUA吸收律A(AB)AA(AB)A德•摩根律ABAB24定理1-10对任意集合A,B,C,D有（1）（2）（3）（4）四命题等价（5）则AABABAABA,,,ABABABBABAABBA25证明两个集合相等，可用如下办法：1基本法集合相等的充要条件是两个集合互为子集；即，左式右式，右式左式。所以证明：x左式x右式；x右式x左式。2公式法由集合运算的基本性质，通过推演，进行证明。3反证法261.2.2幂集运算定义1-6对任意结合A，称为A的幂集，定义为即A的全体子集组成的集合是A的幂集。(A)(A){x|xA}n|(A)|2|A|n例A={a,b}B={0,{1,2}}271.2.3笛卡儿积定义1-9设a，b为任意对象，称集合{{a}，{a，b}}为二元有序组，或序偶，简记a，b。a为a，b的第一分量，b为a，b的第二分量。注：a和b可以相等。28定义1－10定义n元序组a1,…,an:a1,a2={{a1},{a1,a2}}a1,a2,a3=a1,a2,a3...a1,…,an=a1,…,an-1,an定理1-18对任意对象a1,…,an;b1,…,bn有a1,…,an=b1,…,bn当且仅当a1=b1,…,an=bn1.2.3笛卡儿积29定义1-11对任意集合A1,A2,…,An,A1×A2,称为A1,A2的笛卡儿积。A1×A2＝{u,v|u∈A1,v∈A2}而A1×A2×A3=(A1×A2)×A3...A1×A2×…×An＝(A1×A2×…×An-1)×An1.2.3笛卡儿积301.2.3笛卡儿积定理1-21对任意有限集合A1,…,An，有|A1×…×An|=|A1|*…*|An|311.3集合归纳定义三部分组成：（1）基础条款：规定待定义集合以某些元素为其基本成员，集合的其它元素可以从它们出发逐步确定。（2）归纳条款：规定由已确定的集合元素去进一步确定其它元素的规则。于是，可以从基本元素出发，反复运用这些规则来确认待定义集合的所有成员。（3）终极条款：规定待定义集合只含有（l），（2）条款所确定的成员。32例1:设U为整数集I，用归纳定义规定偶数集E33例2：∑：非空符号集合∑＋：∑上的字（符号串）∑——＞∑＋问题描述：定义：(2)若ww＋＋，，则。(3)终极条款（略）（1）基础条款:∑∑+34练习1数学表达式中允许出现的括号的嵌套和毗连所形成的括号串称为成形括号串。试归纳定义成形括号串集合（假定它含有空括号串）35成形括号串集合（1）基础条款：空括号串是成形括号串。(2)归纳条款：如果x，y是成形括号串，那么（x），xy都是成形括号串。（3）略