《公务员知识集合的基本概念》由会员分享，可在线阅读，更多相关《公务员知识集合的基本概念（55页珍藏版）》请在金锄头文库上搜索。
1、离 散 数 学吉林大学计算机科学与技术学院 智能决策与自动推理教研室离散数学l第一章 集合论基础l第二章 命题逻辑l第三章 一阶逻辑l第四章 图与网络l第五章 数论基础第一章 集合论基础 1.1 集合的基本概念1.2 关 系 1.3 映 射康托尔 (Cantor)1.1 集合的基本概念什么是集合(Set)？“所要讨论的一类对象的整体”；“具有同一性质单元的集体” 通常，用大写的英文字母A, B, C,表 示集合；1、二十六个英文字母可以看成是一个集 合；2、所有的自然数看成是一个集合；3、吉林大学计算机学院2001级的本 科学生可以看成是一个集合；4、这间教室中的所有座位可以看成 是一个集合。
2、例如:集合的元素(member或element)组成一个集合的那些对象或单元称为 这个集合的元素。通常，用小写的英文字母a, b, c,表 示集合中的元素 设A是一个集合，a是集合A中的元素，记以aA，读作a属于A；若a不是集合A中的元素，则记以aA，读作a不属于A。例如：A是正偶数集合，则2A，8A，36A；而 3A，9A，17A属于(belong to)包含有限个元素的集合，称为有限集或有穷集(finite set)；包含无限个元素的集合，称为无限集或无穷集(infinite set )。例：所有英文字母组成的集合是有限集，整数集合是无限集。有限集 、无限集 约定，存在一个没有任何元素的集
3、合，称为空集(empty set) ，记为，有时也用来表示。约定，所讨论的对象的全体称为全集(universal set)，记作E或U，我们所讨论的集合都是全集的子集 。全集是相对的。空集、全集设A是有穷集合， A中元素的个数称为集合A的元素数，记为A。例如，设A是所有英文字母组成的集合，则A=26。特别， | |=0集合的元素数列举法；将集合中的元素一一列举，或 列出足够多的元素以反映集合中元素的 特征，例如：V=a,e,i,o,u 或 B=1,4,9,16,25,36。 描述法 ；通过描述集合中元素的共同特 征来表示集合，例如： V= x|x是元音字 母 ，B= x|x=a2 , a是自然
4、数集合的表示法文氏图(Venn Diagram) 用一个大的矩形表示全集，在矩形内画一些圆 或其它的几何图形，来表示集合，有时也用一 些点来表示集合中的特定元素。例如：集合V=a,e,i,o,u ，用文氏图表示如下 :EVa u确定性；互异性； 无序性；多样性；集合的特征任何一个对象，或者是这个集合的元素 ，或者不是，二者必居其一；例如：A=x|x是自然数，且x100B=x|x是年轻人C=x|x是秃子确定性集合中任何两个元素都是不同的，即集 合中不允许出现重复的元素。例如： 集合A=a,b,c,c,b,d，实际上， 应该是A=a,b,c,d互异性集合与其中的元素的顺序无关例如： 集合a,b,c
5、,d,e、d,c,e,a,b、 e,c,d,b,a，都是表示同一个集合。无序性集合中的元素可以是任意的对象，相互 独立，不要求一定要具备明显的共同特 征。例如： A=a,a,a,b,a, 1 A=1,a,*,-3,a,b,x|x是汽车,地球多样性设集合S=A|A是集合，且AA若SS，则S是集合S的元素，则根据S的定义，有S S，与假设矛盾；若SS，则S是不以自身为元素的集合，则根据S的定义，有SS，与假设矛盾；罗素悖论(Russells paradox) 当两个集合A和B的元素完全一样，即A，B实际上是同一个集合时，则称集合A，B相等，记以A=B。 例：设A=x|x是偶数，且0x10，B=2,
6、4,6,8，则A=B。【定义1】集合相等设A，B是两个集合，若A的元素都是B的元素，则称A是B的子集，也称B包含A，或A包含于B，记以A B，或B A 。若AB，且AB，则称A是B的真子集(proper subset)，也称B真包含A，或A真包含于B，记以AB，或B A 。 【定义2】子集(subset) 设A=2,4,6,8 ，B= x|x是正偶数， C=x|x是整数,则有A B，B C，AC,并且A B，B C，A C 。 例： 对任意集合A, 有A A。空集是任意集合的子集，且空集是唯一的。对于任意两个集合A、B，A=B的充要条件是AB且BA。 重要结论是否存在集合A和B, 使得AB 且
7、A B ？若存在，请举一例。讨论：设A 是集合，A的所有子集为元素做成的集合称为A的幂集，记以(A)或A。即： (A)=S|S A例： A=a,b,c ，则(A)=,a,b,c,a,b,a,c,b,c,a,b,c【定义3】幂集(power set)若A为有穷集，|A|=n，则|2A | = Cn0 + Cn1 + + Cnn =2n 。x(A)当且仅当xA。设A、B是两个集合，AB当且仅当(A)(B)；幂集的性质设C是一个集合。若C的元素都是集合，则称C为集合族。 若集合族C可表示为C=SddD，则称D为集合族C的标志（索引）集。 【定义4】集合族、标志集显然，2A是一个集合族。设A1, A2
8、, A3, 是集合的序列，且两两之间互不相同，则集合A1, A2, A3, 是一个集合族，可表示为Ai| iN，其中,N是自然数集合，是该集合的标志集合。 设A，B是两个集合。所有属于A或者属于B的元素做成的集合，称为A和B的并集，记以AB。即AB=x|xA或xB例如，令A=a，b，c，d，B=c，d，e，f，于是AB=a，b，c，d，e，f。 【定义5】集合的并集(Union)并集的文氏图ABAB设A，B是两个集合。由属于A又属于B的元素组成的集合，称为A和B的交集，记以AB。即AB=x|xA且xB例如，令A=a，b，c，d，B=c，d，e，f，于是AB=c，d。 【定义6】集合的交集(In
9、tersection)交集的文氏图ABAB设A1，A2，An是n个集合，则，A1A2An ，简记为A1A2An ，简记为并集和交集的推广设A1，A2，An是n个集合，则 容斥原理 (principle of inclusion-exclusion)称为包含排斥原理，简称容斥原理 。 设A，B是两个集合。由属于集合A而不属于集合B的所有元素组成的集合，称为A与B的差集，记以A-B，或AB。即A-B=x|xA且xB例如，令A=a，b，c，d，B=c，d，e，f，于是A - B=a，b。 【定义7】集合的差集(Difference)差集的文氏图ABA-BE设A是一个集合，全集E与A的差集称为A的余集
10、或补集，记以A。即A=E-A例如，令E=a，b，c，d，e，f，A=b，c，于是A=a，d，e，f。 特别，【定义8】集合的补集(Complement)补集的文氏图AA的补集E设A，B是两个集合。则A与B的环和(对称差),记以AB, 定义为AB=(A-B)(B-A)。A与B的对称差还有一个等价的定义，即AB=(AB)-(AB)。 例：令A=a，b，c，d，B=c，d，e，f，于是AB=a，b， e，f。 【定义9】集合的对称差对称差的文氏图ABABE设A，B是两个集合，则A与B的环积定义为 A B = AB【定义10】集合的环积ABE我们将(a1,a2 , ,an)称为有序n元组，其中，a1是
11、其第一个元素， a2是其第二个元素， ，an是其第n个元素。两个有序n元组(a1,a2 , ,an)和(b1,b2 , ,bn)相等当且仅当ai=bi , i=1,2,n【定义11】有序n元组(ordered n-tuples)对于有序n元组，当n=2时，我们将其称作有序二元组，也称作有序对,或有序偶。有序对的特点：若ab,则(a,b)(b,a)两个有序对(a,b)和(c,d)相等当且仅当a=c，b=d【定义12】有序对(ordered pairs)设A，B是两个集合，所有有序对(x, y)做成的集合(其中xA，yB)，称为A，B的直乘积(笛卡儿积)，记以AB。AB=(x，y)xA且yB。 【
12、定义13】笛卡儿积(Cartesian product)设A1,A2 , ,An是n个集合，由所有有序n元组(a1,a2,an)做成的集合(其中aiAi，i=1,2, ,n)，称为A1,A2,An的直乘积(笛卡儿积)，记以A1A2 An。A1A2 An=(a1,a2 , ,an) aiAi，i=1,2, ,n 。 【定义14】笛卡儿积的推广设A=1,2，B=a,b,c,则AB=(1,a), (1,b),(1,c),(2,a),(2,b),(2,c)； BA =(a,1), (a,2),(b,1),(b,2),(c,1),(c,2)；例如：|AB|=A B；对任意集合A，有A=，A=；直乘积运算
13、不满足交换律，即ABBA； 直乘积运算不满足结合律，即(AB)CA(BC) 直乘积的性质5. 直乘积运算对并和交运算满足分配律， 即: A(BC)=(AB)(AC)， (BC)A=(BA)(CA)， A(BC)=(AB)(AC)， (BC)A=(BA)(CA)； 6. 设A，B，C，D是集合，若AC且BD ，则AB CD。 等幂律： AA=A，AA=A。交换律： AB=BA，AB=BA。结合律： (AB)C=A(BC)，(AB)C=A(BC)。分配律： A(BC)=(AB)(AC)，A(BC)=(AB)(AC)。吸收律： A(AB)=A，A(AB)=A。 对于任意集合A,B,C有如下算律： 互补律： 摩根律：同一律：EA=A，A=A。零一律：A=，EA=E。 双重否定律：其它算律： 证明：任取 ，即aAB，亦即aA且aB，于是 且 ，故，所以任取 ，即 且 ，亦即aA且aB，于是aAB ，故，所以从而， 得证。证明 ：证明 ：作业：6页 1
