1、离离 散散 数数 学学吉林大学计算机科学与技术学院智能决策与自动推理教研室离散数学离散数学l第一章 集合论基础集合论基础l第二章第二章 命题逻辑命题逻辑l第三章第三章 一阶逻辑一阶逻辑l第四章第四章 图与网络图与网络l第五章第五章 数论基础数论基础第一章第一章 集合论基础集合论基础 1.1 集合的基本概念集合的基本概念1.2 关关 系系 1.3 映映 射射康托尔康托尔(Cantor)1.1 集合的基本概念集合的基本概念什么是集合(Set)？“所要讨论的一类对象的整体”；“含有同一性质单元的集体”普通，用大写的英文字母A,B,C,表达集合；1、二十六个英文字母能够当作是一种集、二十六个英文字母能
2、够当作是一种集合；合；2、全部的自然数当作是一种集合；、全部的自然数当作是一种集合；3、吉林大学计算机学院、吉林大学计算机学院2001级的本科学级的本科学生能够当作是一种集合；生能够当作是一种集合；4、这间教室中的全部座位能够当作是一、这间教室中的全部座位能够当作是一种集合。种集合。例如例如:集合的元素集合的元素(member或element)构成一种集合的那些对象或单元称为构成一种集合的那些对象或单元称为这个集合的元素。这个集合的元素。普通，用小写的英文字母普通，用小写的英文字母a,b,c,表表达集合中的元素达集合中的元素 设设A是一种集合，是一种集合，a是集合是集合A中的元素，中的元素，记
3、以记以a A，读作，读作a属于属于A；若；若a不是集合不是集合A中的元素，则记以中的元素，则记以a A，读作，读作a不属于不属于A。例如：例如：A是正偶数集合，则是正偶数集合，则2 A，8 A，36 A；而；而 3 A，9 A，17 A属于属于(belong to)包含有限个元素的集合，称为有限集或包含有限个元素的集合，称为有限集或有穷集有穷集(finite set)(finite set)；包含无限个元素的集合，称为无限集或包含无限个元素的集合，称为无限集或无穷集无穷集(infinite set)(infinite set)。例：全部英文字母构成的集合是有限集，例：全部英文字母构成的集合是有
4、限集，整数集合是无限集。整数集合是无限集。有限集有限集、无限集无限集 商定，存在一种没有任何元素的集合，商定，存在一种没有任何元素的集合，称为空集称为空集(empty set)，记为，记为，有时也用，有时也用来表达。来表达。商定，所讨论的对象的全体称为全集商定，所讨论的对象的全体称为全集(universal set)，记作，记作E或或U，我们所讨，我们所讨论的集合都是全集的子集论的集合都是全集的子集。全集是相对。全集是相对的。的。空集空集、全集、全集设设A A是有穷集合，是有穷集合，A A中元素的个数称为中元素的个数称为集合集合A A的元素数，记为的元素数，记为 A A。例如，设例如，设A A
5、是全部英文字母构成的集合，是全部英文字母构成的集合，则则A A=26=26。特别，特别，|=0|=0集合的元素数集合的元素数列举法；将集合中的元素一一列举，列举法；将集合中的元素一一列举，或列出足够多的元素以反映集合中元或列出足够多的元素以反映集合中元素的特性，例如：素的特性，例如：V=a,e,i,o,u 或或B=1,4,9,16,25,36。描述法描述法；通过描述集合中元素的共同；通过描述集合中元素的共同特性来表达集合，例如：特性来表达集合，例如：V=x|x是元是元音字母音字母，B=x|x=a2,a是自然数是自然数集合的表达法集合的表达法文氏图文氏图(Venn Diagram)用一种大的矩形
6、表达全集，在矩形内画某些用一种大的矩形表达全集，在矩形内画某些圆或其它的几何图形，来表达集合，有时也圆或其它的几何图形，来表达集合，有时也用某些点来表达集合中的特定元素。用某些点来表达集合中的特定元素。例如：集合例如：集合V=a,e,i,o,u，用文氏图表达以，用文氏图表达以下下:EVau拟定性；拟定性；互异性；互异性；无序性；无序性；多样性；多样性；集合的特性集合的特性任何一种对象，或者是这个集合的元任何一种对象，或者是这个集合的元素，或者不是，两者必居其一；素，或者不是，两者必居其一；例如：例如：A=x|x是自然数，且是自然数，且x100B=x|x是年轻人是年轻人C=x|x是秃子是秃子拟定
7、性拟定性集合中任何两个元素都是不同的，即集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。集合中不允许出现重复的元素。例如：例如：集合集合A=a,b,c,c,b,d，事实上，事实上，应当是应当是A=a,b,c,d互异性互异性集合与其中的元素的次序无关集合与其中的元素的次序无关例如：例如：集合集合a,b,c,d,e、d,c,e,a,b、e,c,d,b,a，都是表，都是表达同一种集合。达同一种集合。无序性无序性集合中的元素能够是任意的对象，互集合中的元素能够是任意的对象，互相独立，不规定一定要含有明显的共相独立，不规定一定要含有明显的共同特性。同特性。例如：例如：A=a,a,a,b,a,
8、1A=1,a,*,-3,a,b,x|x是汽车是汽车,地球地球多样性多样性设集合设集合S=A|A是集合，且是集合，且A A若若S S，则，则S是集合是集合S的元素，则根据的元素，则根据S的定义，有的定义，有S S，与假设矛盾；，与假设矛盾；若若S S，则，则S是不以本身为元素的集合，是不以本身为元素的集合，则根据则根据S的定义，有的定义，有S S，与假设矛盾；，与假设矛盾；罗素悖论罗素悖论(Russells paradox)当两个集合当两个集合A A和和B B的元素完全同样，的元素完全同样，即即A A，B B事实上是同一种集合时，则称事实上是同一种集合时，则称集合集合A A，B B相等，记以相等
9、，记以A=BA=B。例：设例：设A=x|xA=x|x是偶数，且是偶数，且0 x100 x10，B=2,4,6,8B=2,4,6,8，则，则A=BA=B。【定义定义1 1】集合相等集合相等设设A，B是两个集合，若是两个集合，若A的元素都是的元素都是B的元素，则称的元素，则称A是是B的子集，也称的子集，也称B包含包含A，或，或A包含包含于于B，记以，记以A B，或，或B A。若若A B，且，且A B，则称，则称A是是B的真子集的真子集(proper subsetproper subset)，也称，也称B真包含真包含A，或，或A真包含真包含于于B，记以，记以A B，或，或B A。【定义定义2 2】子
10、集子集(subsetsubset)设设A=2,4,6,8，B=x|x是正偶数是正偶数，C=x|x是整数是整数,则有则有A B，B C，A C,并且并且A B，B C，A C。例：例：对任意集合对任意集合A,有有A A。空集是任意集合的子集，且空集是唯一空集是任意集合的子集，且空集是唯一的。的。对于任意两个集合对于任意两个集合A、B，A=B的充要条的充要条件是件是A B且且B A。重要结论重要结论与否存在集合与否存在集合A A和和B,B,使得使得A A B B 且且A A B B？若存在，请举一例。？若存在，请举一例。讨论：讨论：设设A A 是集合，是集合，A A的全部子集为元素做成的集的全部子
11、集为元素做成的集合称为合称为A A的幂集，记以的幂集，记以(A)(A)或或A A。即：即：(A)=S|S(A)=S|S A A例：例：A=a,b,c A=a,b,c，则，则(A)=(A)=,a,b,c,a,b,a,c,b,c,a,b,c,a,b,a,c,b,c,a,b,ca,b,c【定义【定义3】幂集幂集(power set)1.若若A为有穷集，为有穷集，|A|=n，则，则|2A|=Cn0+Cn1+Cnn=2n。2.x(A)当且仅当当且仅当x A。3.设设A、B是是两两个个集集合合，A B当当且且仅仅当当(A)(B)；幂集的性质幂集的性质设设C是一种集合。若是一种集合。若C的元素都是集合，的元
12、素都是集合，则称则称C为集合族。为集合族。若集合族若集合族C可表达为可表达为C=Sd d D，则，则称称D为集合族为集合族C的标志（索引）集。的标志（索引）集。【定义定义4 4】集合族、标志集集合族、标志集显然，显然，2A2A是一种集合族。是一种集合族。设设A1,A2,A3,A1,A2,A3,是集合的序列，且是集合的序列，且两两之间互不相似，则集合两两之间互不相似，则集合A1,A2,A1,A2,A3,A3,是一种集合族，可表达为是一种集合族，可表达为Ai|Ai|i i NN，其中，其中,N,N是自然数集合，是该集是自然数集合，是该集合的标志集合。合的标志集合。设设A，B是是两两个个集集合合。全
13、全部部属属于于A或或者者属属于于B的的元元素素做做成成的的集集合合，称称为为A和和B的的并并集集，记以记以AB。即。即AB=x|x A或或x B例例如如，令令A=a，b，c，d，B=c，d，e，f，于是，于是AB=a，b，c，d，e，f。【定义【定义5】集合的并集集合的并集(Union)并集的文氏图并集的文氏图ABAB设设A A，B B是是两两个个集集合合。由由属属于于A A又又属属于于B B的的元元素素构构成成的的集集合合，称称为为A A和和B B的的交交集集，记记以以ABAB。即。即AB=x|xAB=x|x A A且且x x BB例例如如，令令A=aA=a，b b，c c，dd，B=cB=
14、c，d d，e e，ff，于是，于是AB=cAB=c，dd。【定义【定义6】集合的交集集合的交集(Intersection)交集的文氏图交集的文氏图ABAB设设A1，A2，An是是n个个集集合合，则则，A1A2An，简记为，简记为A1A2An，简记为，简记为并集和交集的推广并集和交集的推广设设A1，A2，An是是n个集合，则个集合，则 容斥原理容斥原理 (principle of inclusion-exclusion)称为包含排斥原理，简称容斥原理。称为包含排斥原理，简称容斥原理。设设A A，B B是两个集合。由属于集合是两个集合。由属于集合A A而不属于而不属于集合集合B B的全部元素构成
15、的集合，称为的全部元素构成的集合，称为A A与与B B的的差集，记以差集，记以A-BA-B，或，或ABAB。即即A-B=x|xA-B=x|x A A且且x x BB例如，令例如，令A=aA=a，b b，c c，dd，B=cB=c，d d，e e，ff，于是，于是A-B=aA-B=a，bb。【定义【定义7】集合的差集集合的差集(Difference)差集的文氏图差集的文氏图ABA-BE设设A是是一一种种集集合合，全全集集E与与A的的差差集集称称为为A的余集或补集，记以的余集或补集，记以A。即。即A=E-A例例如如，令令E=a，b，c，d，e，f，A=b，c，于是，于是A=a，d，e，f。特别，特
16、别，【定义【定义8】集合的补集集合的补集(Complement)补集的文氏图补集的文氏图AA的补集的补集E设设A，B是是两两个个集集合合。则则A与与B的的环环和和(对对称称差差),记以记以A B,定义为定义为A B=(A-B)(B-A)。A与与B的的对对称称差差尚尚有有一一种种等等价价的的定定义义，即即A B=(AB)-(AB)。例例：令令A=a，b，c，d，B=c，d，e，f，于是，于是A B=a，b，e，f。【定义定义9 9】集合的对称差集合的对称差对称差的文氏图对称差的文氏图ABA BE设设A，B是是两两个个集集合合，则则A与与B的的环环积积定定义义为为 A B=A B【定义定义1010
17、】集合的环积集合的环积ABE我们将我们将(a1,a2,an)(a1,a2,an)称为有序称为有序n n元组，元组，其中，其中，a1a1是其第一种元素，是其第一种元素，a2 a2是其第二个是其第二个元素，元素，anan是其第是其第n n个元素。个元素。两个有序两个有序n n元组元组(a1,a2,an)(a1,a2,an)和和(b1,b2(b1,b2,bn),bn)相等当且仅当相等当且仅当ai=bi,ai=bi,i=1,2,ni=1,2,n【定义定义1111】有序有序n n元组元组(ordered n-tuples)对于有序对于有序n n元组，当元组，当n=2n=2时，我们将其称作时，我们将其称作
18、有序二元组，也称作有序对有序二元组，也称作有序对,或有序偶。或有序偶。有序对的特点：有序对的特点：1.1.若若a a b,b,则则(a,b)(a,b)(b,a)(b,a)2.2.两个有序对两个有序对(a,b)(a,b)和和(c,d)(c,d)相等当且仅当相等当且仅当a=ca=c，b=db=d【定义定义1212】有序对有序对(ordered pairs)设设A，B是是两两个个集集合合，全全部部有有序序对对(x,y)做做成成的的集集合合(其其中中x A，y B)，称称为为A，B的的直直乘积乘积(笛卡儿积笛卡儿积)，记以，记以A B。A B=(x，y)x A且且y B。【定义定义1313】笛卡儿积笛
19、卡儿积(Cartesian product)设设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。【定义定义1414】笛卡儿积的推广笛卡儿积的推广设设 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),(
20、c,2)；例如：例如：1.|A B|=A B；2.2.对任意集合对任意集合A，有，有A=，A=；3.3.直乘积运算不满足交换律，即直乘积运算不满足交换律，即A A B B B B A A；4.4.直乘积运算不满足结合律，即直乘积运算不满足结合律，即(A B)C A(B C)直乘积的性质直乘积的性质5.直乘积运算对并和交运算满足分派律，直乘积运算对并和交运算满足分派律，即即:A(BC)=(A B)(A C)，(BC)A=(B A)(C A)，A(BC)=(A B)(A C)，(BC)A=(B A)(C A)；6.设设A，B，C，D是集合，若是集合，若A C且且B D，则，则A B C D。1.等
21、幂律：等幂律：AA=A，AA=A。2.交换律：交换律：AB=BA，AB=BA。3.结合律：结合律：(AB)C=A(BC)，(AB)C=A(BC)。4.分派律：分派律：A(BC)=(AB)(AC)，A(BC)=(AB)(AC)。5.吸取律：吸取律：A(AB)=A，A(AB)=A。对于任意集合对于任意集合A,B,C有以下算律：有以下算律：6.互补律：互补律：7.摩摩根根律律：8.同一律：同一律：EA=A，A=A。9.零一律：零一律：A=，EA=E。10.双重否认律：双重否认律：其它算律：其它算律：证明：任取证明：任取 ，即，即a AB，亦即，亦即a A且且a B，于是，于是 且且 ，故，故 ，因此，因此任取任取 ，即，即 且且 ，亦即，亦即a A且且a B，于是，于是a AB，故，故，因此，因此从而，从而，得证。得证。证明：证明：证明：证明：作业：作业：6页页 1
