集合的概念和表示法-集合与关系-离散数学

集合的概念和表示法第1页一、集合的概念集合（SET）：即是由一些确定的彼此不同的客体（事物）汇集到一起组成一个整体，称为集合。讨论：客体：泛指一切，可以是具体的、抽象的。元素(element，成员)：即组成集合的客体，称之为元素。二、集合的记法通常用带(不带)标号的大写字母A、B、C、...、A1、B1、C1、...、X、Y、Z、...表示集合；通常用带（不带）标号的小写字母a、b、c、...、a1、b1、c1、...、x、y、z、...表示元素。第2页固定的符号NIQRC第3页说明：集合中的元素都是不同的，凡是相同的元素，均视为同一个元素；{1,1,2}={1,2}一旦给定了集合A，对于任意客体a，可以准确地判定a是否在A中。集合中的元素是没有顺序的。{2,1}={1,2}集合的特性1、互异性－2、确定性－3、无序性－4、集合中的元素可以是集合。如S={a,{1,2},p,{q}}以集合为元素的集合称为集合类或集合族。如S={{a},{1,2,3,4}}第4页三、集合与元素的关系客体a与集合A之间的关系只能是属于和不属于之一。a是集合A的元素或a属于集合A，记为aA，称a是A的成员，A包含a，a在A中。a不是集合A的元素或a不属于集合A，记为aA，或者(aA)，称a不是A的成员，A不包含a，a不在A中。例如，对元素2和自然数集合N，就有2属于N，即2N，对元素-2和自然数集合N，就有-2不属于N，即-2N。有限集：组成集合的元素个数是有限的。|A|：有限集合A中元素的个数。无限集：组成集合的元素个数是无限的。第5页四、集合的表示方法集合是由它包含的元素完全确定的，为了表示一个集合，通常有：枚举法（列举法）谓词表示法（隐式法、叙述法）文氏(Venn)图-辅助的集合的表示方法第6页1、枚举法（显式表示法）就是把集合的元素（全部或部分）写在花括号的里面，每个元素仅写一次，不考虑顺序，并用”,”分开。例（1）命题的真假值组成的集合：S={T,F}（2）A＝{a，e，i，o，u}第7页在使用中，分两种情况：（1）当集合中元素个数有限且较少时，将元素全部写出。例1：设集合A是由绝对值不超过3的整数组成。A={-3,-2,-1,0,1,2,3}（2）当集合A元素的个数无限或有限但个数较多时，不能或不需要一一列举出来，只要写出少数元素，以显示出它的规律。（当规律不明确，不能用此方法）。例2：设集合B是由自然数的平方构成的集合。B={0,1,4,9,16,…,n2,…}适用场景：一个集合仅含有限个元素。一个集合的元素之间有明显关系。第8页2、谓词表示法（隐式法、叙述法）用谓词描述集合中元素的属性，称为谓词表示法（叙述法、隐式法）一般表示方法：A＝{x|P(x)}若个体域内，客体a使得P(a)为真，则a∈A，否则aA。例如：大于10的整数的集合：S={x|x∈I∧x10)}命题的真假值组成的集合：S={F,T}={x|x=F∨x=T}适用场景：一个集合含有很多或无穷多个元素；一个集合的元素之间有容易刻画的共同特征。其突出优点是原则上不要求列出集合中全部元素，而只要给出该集合中元素的特性。P(x)是谓词公式，x具有的性质P代表元素第9页A3、文氏(Venn)图-辅助的集合的表示方法文氏(Venn)图是一种利用平面上的点构成的图形来形象展示集合的一种方法，用一个矩形的内部表示全集，其他集合用矩形内的园面或一封闭曲线圈成的面积来表示。文氏图又称韦恩图，用它表示集合间的关系或运算，是一种非常直观的图示集合的工具，文图只起示意作用，不能用以代替严格证明。U第10页同一个集合可以用不同的表示方法：例方程x2-1=0的所有实数解的集合A；谓词法：A={x|xR∧x2-1=0}或A={x|x是实数且x2-1=0}枚举法：A={1，-1}第11页五、集合与集合的关系（一）包含关系（二）相等关系（三）真包含关系第12页“包含关系”的谓词表示：ABBA(x)(x∈Ax∈B)（一）包含关系例：设A={ADA,BASIC,PASCAL}，B={BASIC,PASCAL,ADA,C,JAVA}定义：A包含在B内，A包含于B，B包含A设A，B是任意两个集合，若A的每个元素都是B的元素，则称A是B的子集(Subset)，也称A包含在B内，B包含A，记作BA或AB，若A不被B所包含，则记作AB。显然，对任意集合A，都有AA。AB第13页（二）相等关系定义A＝B当且仅当A与B具有相同的元素，否则，AB。即集合A,B中的元素完全相同，称这样的两个集合相等。{1,2,4}={1,4,2}≠{1,{2,4}}定理3-1.1设A和B是任意两个集合，A=BAB且BA。集合相等的谓词表示：A=B(x)(x∈Ax∈B)第14页定理3-1.1A=BAB且BA。证明：(1)证：若AB且BA，则A=B。(反证法)已知AB且BA，假设A≠B，则至少有一个元素x，使得x∈A而xB；或者x∈B而xA。如果x∈A而xB，则与AB矛盾。如果x∈B而xA，则与BA矛盾。所以A=B。(2)证：若A=B，则AB且BA。若A=B，则两个集合有相同的元素，即(x)(x∈Ax∈B)为真，且(x)(x∈Bx∈A)为真，即必有AB且BA。所以，A=BAB且BA。该定理是证明两个集合相等的基本思路和依据。第15页集合相等的谓词定义A=BAB∧BA(x)(x∈Ax∈B)∧(x)(x∈Bx∈A)(x)((x∈Ax∈B)∧(x∈Bx∈A))(x)(x∈Ax∈B)A=B(x)(x∈Ax∈B)第16页（三）真包含关系定义1.2.2：A真包含于B设A,B是任意两个集合，集合A中的每一个元素都属于B，但集合B中至少有一个元素不属于A。则称A是B的真子集(ProperSubset)，记作AB，如果A不是B的真子集，则记作AB。“真包含关系”的谓词表示：ABAB∧A≠BAB(x)(x∈Ax∈B)∧(x)(xB∧xA)对任意x，如xA，则xB，并且存在xB，但是xA。第17页自学真包含关系的谓词定义：ABAB∧A≠B(x)(x∈Ax∈B)∧(x)(x∈Ax∈B)(x)(x∈Ax∈B)∧((x)(x∈Ax∈B)∨(x)(x∈Bx∈A))((x)(x∈Ax∈B)∧(x)(x∈Ax∈B))∨((x)(x∈Ax∈B)∧(x)(x∈Bx∈A))(x)(x∈Ax∈B)∧(x)(x∈B∧xA)集合A中的每一个元素都属于B，但集合B中至少有一个元素不属于A。第18页六、几个特殊集合1、全集2、空集3、幂集第19页1、全集定义在一个相对固定的范围内，包含此范围内所有客体的集合，称为全集或论集(UniversalSet)，用U或E表示。E={x|P(x)∨P(x)}其中：P(x)为任何谓词。用文氏图描述如下:U六、几个特殊集合一般地，根据讨论问题的范围，选择对问题讨论方便的集合作为全集。在实际应用中，常常把某个适当大的集合看成全集。第20页2、空集定义：不含任何元素的集合叫做空集(EmptySet)，记作Φ。空集可以符号化为Φ={x|P(x)∧P(x)}={}其中：P(x)为任何谓词。例设A={x|(x∈R)∧(x20)}，试列举A中的所有元素。解：A=Φ。Φ与{Φ}:Φ是不含任何元素的集合，{Φ}是含一个元素Φ的集合。{Φ}={{}}，|Φ|=0，|{Φ}|=1，Φ∈{Φ}定理3-1.2（1）空集是一切集合的子集；（2）空集是绝对唯一的。第21页反证法（1）空集是一切集合的子集；ΦA证明：因为(x)(x∈Φx∈A)为永真式，所以ΦA。（2）空集是绝对唯一的。分析：对“唯一性”的证明通常采用反证法。即假设“不唯一”，得出矛盾，从而说明结论正确。证明：（反证法）假设空集不唯一，即存在Φ1和Φ2两个空集，且Φ1≠Φ2，因为是Φ1空集，则由性质1得Φ1Φ2。因为是Φ2空集，则由性质1得Φ2Φ1。所以Φ1=Φ2。与假设矛盾，所以空集是唯一的。定理3-1.2的证明Φ{Φ}第22页3、幂集引例：求集合的子集及子集的个数例A子集子集个数ΦΦ1{a}Φ,{a}2{a,b}Φ,{a},{b},{a,b}4{a,b,c}Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}8一般来说，对于n个元素的集合A，它的不同的子集总数有：＝(1+1)n＝2n所以，n元集共有2n个子集。Cn2＋……Cn0Cn1Cnn＋＋＋第23页一般来说，对于n个元素的集合A，它的不同的子集总数有Cn2＋……Cn0Cn1Cnn＋＋＋Cn2＋…Cn0Cn1Cnn＋＋＋xn-1yxn-2y2xnynCn2＋……Cn0Cn1Cnn＋＋＋而(x+y)n=令x=y=1时得2n=所以不同子集总数有2n第24页幂集定义：幂集(powerset)给定集合A，由A的所有子集为元素组成的集合称为A的幂集(powerset)，记为ρ(A)。幂集的符号化表示为ρ(A)＝{x|xA}例如：计算下列幂集:(1)ρ(Φ)；(2)ρ({a});(3)ρ({Φ})。解：(1)ρ(Φ)={Φ}；(2)ρ({a})={Φ,{a}}(3)ρ({Φ})={Φ,{Φ}}；定理3-1.3若有限集合Ａ有n个元素，则其幂集ρ(A)共有2n个元素。|A|=n,|ρ(A)|=2n第25页子集Bijk编码Ａ＝{a,b,c}ijk是二进制数，BijkA,i=1，a∈Bijk；i=0，aBijk；j=1，b∈Bijk；j=0，bBijk；k=1，c∈Bijk；k=0，cBijk。例：Ａ＝{a,b,c}则B000B001B010B011B100B101B110B111Φ{c}{b}{b,c}{a}{a,c}{a,b}{a,b,c}B0B1B2B3B4B5B6B7故：ρ(A)={Φ,{c},{b},{b,c},{a},{a,c},{a,b},{a,b,c}}例：Ａ＝{a,{b,c,d}}B0=B00=Φ，B1=B01={{b,c,d}}，B2=B10={a}，B3=B11={a,{b,c,d}}故：ρ(A)={Φ,{{b,c,d}},{a},{a,{b,c,d}}}利用子集Ba1a2a3…an的下标编码求集合A的幂集，a1a2a3…an为二进制编码，n为集合A的元素个数。第26页设A={Φ}，B=ρ(ρ(A))ρ(A)={Φ,{Φ}}在求ρ(ρ(A))时，实际上是将{Φ,{Φ}}中的元素分别看成Φ=a,{Φ}=b,于是{Φ,{Φ}}={a,b}B=ρ(ρ(A))=ρ({a,b})={B0,B1,B2,B3}={B00,B01,B10,B11}={Φ,{b},{a},{a,b}}然后再将a,b代回即可B=ρ(ρ(A))=ρ({Φ,{Φ}})={Φ,{{Φ}},{Φ},{Φ,{Φ}}}以后熟悉后就可以直接写出。练习P86(7)第27页