第一章 集合论基础

软件学院离散数学郑州大学任课教师：刘学文软件学院第一篇绪言离散数学的特征和性质此课程的主要学习内容此课程的主要学习方法软件学院第一篇绪言正如马克思所说的：“一门科学，只有当它能够运用数学时，才算真正发展了。”计算机正是在离散数学中图灵机理论的指导下诞生的。离散数学是数学的一个分支，它以离散量作为其主要研究对象，是研究离散对象的结构以及它们之间相互关系的科学。由于计算机不论硬件还是软件都属于离散结构，所以计算机所应用的数学必是离散数学。软件学院第一篇绪言离散数学课程是计算机系核心课程信息类专业必修课其它类专业的重要选修课程离散数学也是后继课的基础软件学院第一篇绪言离散数学课程的学习可以培养学生抽象的思维、逻辑推理能力和创新能力。让学生见识一些重要的数学思想、数学方法以及用数学解决实际问题的著名事例。培养逻辑思维的能力和分析问题解决问题的能力。软件学院第一篇绪言离散数学的主要学习内容：1.集合论2.代数系统3.图论4.数理逻辑*5.组合数学*6.形式语言与自动机软件学院第一篇绪言特点：内容较杂，概念多，定理多，比较抽象，学习有一定的难度。学习方法：1.准确掌握每个概念(包括内涵及外延)。2.要有刻苦钻研的精神,不断总结经验。3.在理解内容的基础上，要多做练习题，从而再进一步加深理解所学内容。4.注意培养分析问题和解决问题的能力软件学院第二篇集合论主要包括如下内容：集合论基础二元关系函数软件学院第一章集合论基础本章主要介绍如下内容：基本概念及集合的表示方法集合间的关系特殊集合集合的运算软件学院基本概念1.集合与元素集合：是由确定的对象(客体)构成的集体。一般用大写的英文字母表示。这里所谓“确定”是指：论域内任何客体，要么属于这个集合，要么不属于这个集合，是唯一确定的。元素：集合中的对象，称之为元素。∈：表示元素与集合的属于关系。例如，N表示自然数集合，2∈N，而1.5不属于N，写成1.5N。软件学院2.有限集合与无限集合这里对有限集合与无限集合先给出朴素的定义，以后再给出严格的形式定义。有限集合：元素是有限个的集合。如果A是有限集合，用|A|表示A中元素个数。例如，A={1,2,3},则|A|=3。无限集合：元素是无限个的集合。对无限集合的所谓‘大小’的讨论，以后再进行。软件学院3.集合的表示方法列举法：将集合中的元素一一列出，写在大括号内。例如，N={1,2,3,4,……}A={a,b,c,d}描述法：用句子描述元素的属性。例如，B={x|x是偶数}C={x|x是实数且2≤x≤5}一般地，A={x|P(x)},其中P(x)是谓词公式，如果客体a使得P(a)为真，则a∈A，否则aA。软件学院4.说明⑴集合中的元素间次序是无关紧要的，但是必须是可以区分的，即是不同的。例如A={a,b,c}，B={c,b,a}，C={a,b,c,a}，则A、B和C是一样的。⑵对集合中的元素无任何限制，例如令A={人，石头，1，Ｂ},B={Φ,{Φ}}⑶本书中常用的几个集合符号的约定：自然数集合N={1,2,3,……}整数集合I，实数集合R，有理数集合Q软件学院⑷集合中的元素也可以是集合，下面的集合的含义不同：如a：张书记{a}:党支部(只有一个书记){{a}}：分党委(只有一个支部){{{a}}}：党委(只有一个分党委){{{{a}}}}：市党委(只有一个党委)软件学院特殊集合1.全集E定义：包含所讨论的所有集合的集合，称之为全集，记作E。由于讨论的问题不同，全集也不同。所以全集不唯一。例如:若讨论数，可以把实数集看成全集。若讨论人，可以把人类看成全集。性质：对于任何集合A，都有A在E中。软件学院特殊集合2.空集Φ定义：没有元素的集合，称之为空集，记作Φ。性质：(1).对于任何集合A，都有Φ在A中。(2).空集是唯一的。软件学院集合间的关系1.包含关系(子集)(1).定义：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的子集。记作AB。文氏图表示如右下图。例如，N是自然数集合，R是实数集合，则NRAB软件学院集合间的关系(2).性质：(a).有自反性，对任何集合A有AA。(b).有传递性，对任何集合A、B、C，有AB且BC，则AC。(c).有反对称性，对任何集合A、B，有AB且BA，则A=B。软件学院集合间的关系2.相等关系定义：A、B是集合，如果它们的元素完全相同，则称A与B相等。记作A=B。性质：⑴有自反性，对任何集合A，有A=A。⑵有传递性，对任何集合A、B、C，如果有A=B且B=C，则A=C。⑶有对称性，对任何集合A、B，如果有A=B，则B=A。软件学院集合间的关系3.真包含关系(真子集)定义：A、B是集合，如果AB且A≠B，则称B真包含A，A真包含于B，也称A是B的真子集。记作AB。性质：有传递性，对任何集合A、B、C，如果有AB且BC，则AC。软件学院集合的运算1.交运算∩定义：A、B是集合，由既属于A，也属于B的元素构成的集合,称之为A与B的交集,记作A∩B。例如:A={1,2,3},B={2,3,4}则A∩B={2,3}ABA∩B软件学院集合的运算性质：⑴幂等律对任何集合A，有A∩A=A。⑵交换律对任何集合A、B，有A∩B=B∩A。⑶结合律对任何集合A、B、C，有(A∩B)∩C=A∩(B∩C)。⑷同一律对任何集合A，有A∩E=A。⑸零一律对任何集合A，有A∩Φ=Φ。⑹ABA∩B=A。软件学院集合的运算2.并运算∪定义：A、B是集合，由或属于A，或属于B的元素构成的集合,称之为A与B的并集,记作A∪B。例如:A={1,2,3},B={2,3,4}则A∪B={1,2,3,4}BAA∪B软件学院集合的运算性质：⑴幂等律对任何集合A，有A∪A=A。⑵交换律对任何集合A,B，有A∪B=B∪A。⑶结合律对任何集合A,B,C,有(A∪B)∪C=A∪(B∪C).⑷同一律对任何集合A，有A∪Φ=A。⑸零一律对任何集合A，有A∪E=E。软件学院集合的运算⑹分配律对任何集合A、B、C，有A∩(B∪C)=(A∩B)∪(A∩C)。A∪(B∩C)=(A∪B)∩(A∪C)。⑺吸收律对任何集合A、B，有A∪(A∩B)=AA∩(A∪B)=A。⑻ABA∪B=B。软件学院集合的运算3.绝对补集~定义：A是集合,由不属于A的元素构成的集合,称之为A的绝对补集,记作~A。例如，E={1,2,3,4}，A={2,3},则~A={1,4}AE~A软件学院集合的运算性质：设A、B、C是任意集合，则⑴~E=Φ⑵~Φ=E⑶~(~A)=A⑷A∩~A=Φ⑸A∪~A=E注：在这里只有~A同时满足性质（4）（5）（称作~A的惟一性）。证明：此时我们假设除了~A还有B满足（4）（5），则有B=B∪Φ=B∪(A∩~A)=（B∪A）∩（B∪~A）=E∩(B∪~A)=B∪~A.同理，我们可以得到~A=~A∪B.因此B=~A.⑹A-B=A∩~B⑺德·摩根定律（DeMorgan’sLaw）：~(A∩B)=~A∪~B~(A∪B)=~A∩~B软件学院集合的运算4.差运算-(相对补集)定义：A、B是集合，由属于A，而不属于B的元素构成的集合,称之为A与B的差集,或B对A的相对补集，记作A-B。从图中可以知道A-B=A∩～B例如:A={1,2,3},B={2,3,4}则A-B={1}ABA-B软件学院集合的运算性质：设A、B、C是任意集合，则⑴A-Φ=A⑵Φ-A=Φ⑶A-A=Φ⑷A-BA⑸ABA-B=Φ⑹(A-B)-C=(A-C)-(B-C)⑺A-(B∩C)=(A-B)∪(A-C)⑻A-(B∪C)=(A-B)∩(A-C)⑼A∩(B-C)=(A∩B)-(A∩C)⑽但∪对-是不可分配的，如A∪(A-B)=A而(A∪A)-(A∪B)=Φ软件学院集合的运算补集与差集的关系：~A=E-A，A∩(~B)=A-B，A∩~A=Φ，A∪~A=E利用以上性质我们可以得到著名的德.摩根定律（DeMorgan’sLaw):～(A∪B)=～A∩～B～(A∩B)=～A∪～B我们简单地证明一下第一个式子：只需证：(A∪B)∪(～A∩～B)=E和(A∪B)(～A∩～B)=Φ软件学院德.摩根定律的证明显然：(A∪B)∪(～A∩～B)=[(A∪B)∪(～A)]∩[(A∪B)∪(～B)]=E∩E=E及：(A∪B)∩(～A∩～B)=[(A∪B)∩(～A）]∩[(A∪B)∩(～B)]=(B-A)∩(A-B)=Φ其中，我们用到了B∩(～A)=B-A和A∩(～B)=A-B由补集的惟一性，得～(A∪B)=(～A∩～B)同理可得～(A∩B)=(～A∪～B)软件学院差集性质证明(6)(A-B)-C=(A-C)-(B-C)证明:（6）(A-B)-C=(A-B)∩～C=(A∩～B)∩～C同时(A-C)-(B-C)=(A∩～C)∩[～(B∩～C)]=(A∩～C)∩[～B∪C]=[(A∩～C)∩～B]∪[(A∩～C)∩C]=[(A∩～C)∩～B]∪Φ=[(A∩～C)∩～B]==(A∩～B)∩～C软件学院集合的运算5.对称差定义：A、B是集合,由属于A而不属于B，或者属于B而不属于A的元素构成的集合,称之为A与B的对称差,记作AB。由右图可以看出：AB=A∪B-A∩B=(A-B)∪(B-A)例如：A={1,2,3}，B={2,3,4}则AB={1,4}ABABE软件学院集合的运算性质：⑴交换律对任何集合A、B，有AB=BA。⑵结合律对任何集合A、B、C，有(AB)C=A(BC)。⑶同一律对任何集合A，有AΦ=A。⑷对任何集合A，有AA=Φ。⑸∩对可分配A∩(BC)=(A∩B)(A∩C)软件学院幂集6.集合的幂集定义:A是集合，由A的所有子集构成的集合，称之为A的幂集。记作P(A)或2A。P(A)={B|BA}例如:AA的幂集P(A)Φ{Φ}{a}{Φ,{a}}{a,b}{Φ,{a},{b},{a,b}}软件学院幂集性质：(1).给定有限集合A，如果|A|=n,则|P(A)|=2n。例如：Ａ＝{a,b,c}则P(A)={Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}＝23＝8C33C32C31C30|P(A)|＝＋＋＋软件学院n元有序组7.笛卡尔乘积先给出n元有序组的定义定义：n个（n1）按一定次序排列的客体a1,a2,…，an组成一个有序序列，称为n元有序组，记为（a1,a2,…，an）。例如我国当前使用的身份证号码是由一个七元有序组组成（省、市、区、出生年、月、日、序列号）410102198708250037软件学院笛卡尔乘积两个集合的笛卡尔乘积：定义：集合A、B的笛卡尔乘积可表示为A×B={(a,b)|a∈A，b∈B}例如：设A={1,2}，B={a,b}，则A×B={(1,a),(2,a),(1,b),(2,b)}软件学院笛卡尔乘积n个集合的笛卡尔乘积定义：集合A1、A2、…、An的笛卡尔乘积可表示为A1×A2×…×An={(a1,a2,…,an)|ai∈Ai，i=1,2,…}性质：如果A、B都是有限集，且|A|=m,|B|=n，则|AB|=mn.