离散数学教程——集合的基本概念

第1章集合集合的基本概念1. 集合、元元素、有限集、无限集、空集2. 表示集合的方法：列举法、描述法3. 定义子集：给定集合A和B,如果集合A的任何一个元都是集合B中的元,则称集合A包含于B或B包含A,记为或,并称A为B的一个子集;如果集合A和B满足,但B中有元不属于A,则称集合A真包含于B,记为,并且称A为B的一个真子集;4. 定义幂集：给定集合A,以A的所有子集为元构成的一个集合,这个集合称为A的幂集,记为或集合的运算定义并集：设A和B是两个集合,则包含A和B的所有元,但不包含其他元的集合,称为A和B 的并集,记为.定义交集：A和B是两个集合,包含A和B的所有公共元,但不包含其他元的集合,称为A和B 的交集,记为.定义不相交：A和B是两个集合,如果它们满足,则称集合A和B是不相交的;定义差集：A和B是两个集合,属于A而不属于B的所有元构成集合,称为A和B的差集,记为.定义补集：若A是空间E的集合,则E中所有不属于A的元构成的集合称为A的补集,记为. 定义对称差：A和B是两个集合,则定义A和B的对称差为包含排斥原理定理设为有限集,其元素个数分别为,则定理设为有限集,其元素个数分别为,则定理设为有限集,则重要例题P11 例第2章二元关系关系定义序偶：若和是两个元,将它们按前后顺序排列,记为,则成为一个序偶;※对于序偶和,当且仅当并且时,才称和相等,记为定义有序元组：若是个元,将它们按前后顺序排列,记为,则成为一个有序元组简称元组;定义直接积：和是两个集合,则所有序偶的集合,称为和的直接积或笛卡尔积,记为.定义直接积：设是个集合,,则所有元组的集合,称为的笛卡尔积或直接积,记为.定义二元关系若和是两个集合,则的任何子集都定义了一个二元关系,称为上的二元关系;如果,则称为上的二元关系;定义恒等关系：设是上的二元关系,,则称是上的恒等关系;定义定义域、值域：若是一个二元关系,则称为的定义域;为的值域;定义自反：设是集合上的关系,若对于任何．．,都有即则称关系是自反的;定义反自反：设是集合上的关系,若对于任何,都满足,即对任何都不成立,则称关系是反自反的;定义对称：设是集合上的关系,若对于任何,只要,就有,那么称关系是对称的;定义反对称：设是集合上的关系,若对于任何,只要并且时,就有,那么称关系是对称的;定义传递设是集合上的关系,若对于任何,只要并且时,就有,则称关系是传递的;定理设是集合上的关系,若是反自反的和传递的,则是反对称的;关系矩阵和关系图定义无定理无关系的运算定义连接：设为上的关系,为上的关系,则定义关系称为关系和的连接或复合,有时也记为.定义逆关系：设为上的关系,则定义的逆关系为为上的关系：.定理设和都是上的二元关系,则下列各式成立12345定理设为上的关系,为上的关系,则闭包运算定义自反闭包：设是集合上的二元关系,如果是包含的最小自反关系,则称是关系的自反闭包,记为.定义对称闭包：设是集合上的二元关系,如果是包含的最小对称关系,则称是关系的对称闭包,记为.定义传递闭包：设是集合上的二元关系,如果是包含的最小传递关系,则称是关系的传递闭包,记为或.定理设是集合上的二元关系,则（1）是自反的,当且仅当.（2）是对称的,当且仅当.（3）是传递的,当且仅当.定理设是集合上的二元关系,则. “恒等关系”定理设是集合上的二元关系,则. “逆关系”定理设是集合上的二元关系,则. “幂集”定理设是一个元集,是上的二元关系,则存在一个正整数,使得.等价关系和相容关系定义覆盖、划分：是一个集合,,如果,则称是的一个覆盖;如果,并且,则称是的一个划分,中的元称为的划分块;定义等价关系：设是上的一个关系,如果具有自反性、对称性和传递性三个性质,则称是一个等价关系;设是等价关系,若成立,则称等价于.定义等价类：设是上的一个等价关系,则对任何,令,称为关于的等价类,简称为的等价类,也可以简记为.定义同余：对于整数和正整数,有关系式：如果,则称对于模同余的,记作定义商集：设是上的一个等价关系,由引出的等价类组成的集合称为集合上由关系产生的商集,记为. “等价类的集合”定理若是上的一个等价关系,则由可以产生唯一的一个对的划分; “商集”定义相容关系：设是上的一个关系,如果是自反的和对称的,则称是一个相容关系;相容关系可以记为.所有的等价关系都是相容关系,但相容关系却不一定是等价关系;定义最大相容块：设是一个集合,是定义在上的相容关系;如果,中的任何两个元都有关系,而的每一个元都不能和中所有元具有关系,则称是的一个最大相容块;偏序关系定义偏序关系：是定义在集合上的一个关系,如果它具有自反性、反对称性和传递性,则称是上的一个偏序关系,简称为一个偏序,记为.更一般地讲,若是一个集合,在上定义了一个偏序,则我们用符号来表示它,并称是一个偏序集;定义全序/链：是一个偏序集,对任何,如果或这两者中至少有一个必须成立,则称是一个全序集或链,而称是上的一个全序或线性序;定义盖住：是一个偏序集,,若,并且不存在,使并且,则称盖住. “紧挨着”定义最小元、最大元：是一个偏序集,如果中存在有元,对任何都满足,则称是的最小元;如果中存在有元,对任何都满足,则称是的最大元; 定义极小元、极大元：是一个偏序集,如果,而中不存在元,使,则称是的极小元;如果,而中不存在元,使,则称是的极大元;定义上界、下界、上确界、下确界：是一个偏序集,,如果对于所有的,都有,则称是的一个上界;如果对于所有的,都有,则称是的一个下界;如果是的一个上界,对于的任一上界,都有,则称是的最小上界上确界. 如果是的一个上界,对于的任一上界,都有,则称是的最大下界下确界.定义良序集：设是一个偏序集,对于偏序,如果的每个非空子集都具有最小元,则称是一个良序集,而称是上的一个良序;每个良序集都是全序集;第3章函数和运算函数定义映射、象：关系定义在上,如果对于每一个．．．．．,使,．．．,都有唯一的一个则称是从到的一个函数或映射,记为.称为函数的变元,称为变元在下的值或象,记为.注意：（1）定义域,而不是.（2）每一个,有唯一的,使. 多值函数不符合定义（3）值域.定义受限、扩展：若是从到的一个函数,,则也是一个函数,它定义于到,我们称它是在上的受限;如果是函数的一个受限,则称是的一个扩展;★定义映上、映内、一对一、一一对应：若,则的值域时,称函数是映上的或满射;如果的值域时,则称函数是映内的;如果,则有,则称是一对一的单射即时,有.如果映上的,又是一对一的,则称是一一对应的或双射;定义复合运算：若,则定义和的复合运算为：即.注：逆函数若要存在需要满足以下条件：1函数是映上的2函数必须是一对一的定义恒等函数函数称为恒等函数;定理,则的充分必要条件是,并且运算定义二目运算：若是一个集合,是从到的一个映射函数,则称为一个二目运算;一般地,若是从到的一个映射是正整数,则称是一个目运算;运算的封闭：运算的结果总是集合中的一个元,因此这个定义保证了运算的施行,这种情况又称为集合对于该种运算是封闭的;定义可交换：若是一个运算,对于任何,都有,则称运算是可交换的或者说,服从交换律.定义可结合：若是一个运算,对于任何,都有,则称运算是可结合的或者说,服从结合律.定义可分配：若是一个运算,是一个运算,对于任何,都有,则称运算对于运算是可分配的或者说,对于服从分配律定义左单位元、右单位元：设是上的一个运算,如果中存在有一个元,对于任何,有,则称是运算的左单位元；如果中存在有一个元,对于任何,有,则称是运算的右单位元;定理若是上的一个运算,和分别是它的左、右单位元,则,并且是唯一的因此,称为运算的单位元.定义左零元、右零元：设是上的一个运算,如果中存在有一个元,对于任何,有,则称是运算的左零元；如果中存在有一个元,对于任何,有,则称是运算的右零元.定义等幂：若是上的一个运算,,对于运算,有,则称元对于运算是等幂的;定义左逆元、右逆元：若是上的一个运算,它具有单位元,对于任何一个,如果存在有元,使,则称是的左逆元；如果存在有元,使,则称是的右逆元；定理若是上的一个运算,它具有单位元,并且是可结合．．．的,则当元可逆时,它的左、右逆元相等,并且唯一的此时称之为的逆元,并且记为.定义可消去：若是上的一个运算,对于任何,如果元满足：则；或则,则称元对于运算是可消去的;第4章无限集合基数★定义等势：若和是两个集合,如果在和之间可以建立一个一一．．．．对应关系,则称集合和等势,并记为;定理令是由若干个集合为元所组成的集合,则上定义的等势关系是一个等价关系;定义有限集、无限集：若是一个集合,它和某个自然数集等势,则称是一有限集,不是有限集的集合称为无限集;定理有限集的任何子集都是有限集定理有限集不与其任何真子集等势定理自然数集是无限集可列集定义可列集：若是一个集合,它和所有自然数的集合等势,则称是一个可列集;可列集的基数用符号表示;定理若是一个集合,可列的充分必要条件是可以将它的元排列为的序列形式;定理任何无限集必包含有可列子集;定理可列集的子集是有限集或可列集记为：定理若是可列集,是有限集,并且,则是可列集记为：.定理若和都是可列集,并且,则是可列集记为：推论设都是可列集,则是可列集记为：定理设都是可列集,并且,则是可列集记为：推论设都是可列集,则是可列集.定理所有有理数的集合是可列集;不可列集定理区间中所有实数构成的集合是不可列的;定义连续基数：开区间中所有数组成集合的基数记为,具有基数的集合称为连续统,称为连续基数;推论：集合的基数也是.定理所有实数的集合是不可列的,它的基数是.定理对于任何数,若,则区间,以及都具有连续基数定理一个无限集和一个可列集作并集时,并集的基数等于集的基数;推论一个无限集和一个有限集的并集,其基数等于集的基数;基数的比较定义设集合的基数是.如果与的真子集等势,而和不等势,则称的基数小于的基数,记为.定理：是两个集合,若与的某一子集等势,与的某一子集等势,则.定理：是任意两个集合,的基数为,的基数为,则下列三个关系：中必有一个且只有个成立;定理：若是有限集的基数,则.定理：若是无限集合,则定理：若是可列个互不相交的集合,它们的基数都是,则的基数是记为：定理：可列集的幂集,其基数是记为：定理：若是一个集合,是的幂集,则.此定理说明：不存在最大的基数;补充：第5章形式语言文法和语言定义产生式：一个产生式或重写规则是一个有序对,通常写成,其中,是一个符号,而是一个符号的非空有限串,是这个产生式的左部,而是产生式的右部.产生式将简称为规则;定义非终极符号、字母表、终极符号、开始符号：一个文法是一个四元组.其中,是元语言的语法类或变元的集合,它生成语言的串,这些语法类或变元成为非终极符号,是符号的非空有穷集合,称为字母表,的符号称为终极符号.是之一,是词汇表的一个识别元素,称为开始符号.是产生式的集合;定义直接产生、直接推导,直接规约：设是一个文法,如果,而中有规则,就称串直接产生串,或称是直接推导出来的,或直接规约到,记为.定义产生、规约到、推导：设是一个文法,如果存在产生式序列,使得,而,就说产生规约到,或是的推导,记为.定义句型：令是一个文法,如果串可从开始符号推导出来,即如果,则称为一个句型;补充：若,则,其中是空串,不含空串文法的类型定义0-型文法：在上的0-型文法由以下组成：（1）不在中的不同符号的非空集合,称为变量表,它包含一个纲符号,称为开始变量; （2）产生式的有限集合;由产生的所有字集称为由产生的语言;定义0-型语言：在上可由某一0-型文法产生的字集称为0-型语言;定义1-型文法：如果在0-型文法中,对于中的每个产生式,要求,则这文法称为1-型文法或上下文敏感文法.定义2-型文法：设文法,对于中的每一个产生式有且有的人要求,则此文法叫2-型文法或前后文无关文法;定义3-型文法：设为一文法,又设中的每一个产生式都是或,其中和都是变量,而为终极符号,而此文法为3-型文法或正规文法;第1章代数系统代数系统的实例和一般性质定义代数系统：若是序偶,是一个非空集合,是定义在上的某些运算的非空集合,则称是一个代数系统,或称代数;代数系统的类型：（1）代数系统的类型是,其中代表目运算符; （2）,分别为目运算符,则的类型为.同态和同构定义同态象、同态映射:和是两个同类型的代数系统,映射和也构成一一对应.如果对于任意目运算,及其对应的运算,当时,都有,则称代数是的同态象,称是从到的一个同态映射;定义同态象、同态映射：若和是两个同类型的代数系统,和都是二目运算,映射.如果对于任何,都有,则称是的一个同态象,称是从到的一个同态映射;注：如果就是,则映射是从到它自身;当上述条件仍然满足时,我们就称是的一个自同态映射;定义同构、同构映射、自同构映射：如果和是同态的,映射不仅是同态映射,而且是一一对应．．．．的,则称和同构,称是从到的一个同构映射;如果就是,则称是上的一个自同构映射定义同余关系：设是一个代数系统,是上的一个等价关系,如果存在,当时,成立,则称是上的一个同余关系;定理：设～是上的一个等价关系,如果存在同态映射,使得当时,当且仅当,则～是上的同余关系;商代数与积代数定义子代数：设是一个代数系统,在运算下封闭的,则称是的一个子代数;定义直接积：设到是两个同类型的代数系统,如果对任意的和,定义运算于,称是和的直接积,称和为的因子;第2章半群和群半群和有幺半群定义半群、有幺半群：是一个非空集合,如果中定义了一个二目运算,对于任何,都有,则称是一个半群.如果半群中具有单位元,使得对任何,都有,则称是一个有幺半群;1是一个由有限个符号组成的集合,其中的元称为字母;表示所有的字构成的集合,表示非空串组成的集合;2自由半群：半群的各元相互间没有任何关系;说明：半群是一个定义了二目运算,并且服从结合律的代数系统;有幺半群则是具有单位元的半群;群和循环群定义群：在代数系统中,如果二目运算满足1对于任何,有；2中存在单位元,对任何,有；3对于任何,存在有逆元,使则称是一个群;注：对于群来说,单位元是唯一的,每个元的逆元也是唯一的;“存在逆元的有幺半群叫做群”定义阶数：若是一个群,当是有限集时,则称中元的个数为群的阶数,记为.定理若是一个群,,则,其中即.定义幂：是一个群,,则记个的积为,称为幂,记为表示单位元;定理指数律：若和是整数,则.定理若则定义次数：若是一个群,,使的最小正整数,称为元的次数;定理若是一个群,,的次数为,则都是中不同的元;定义循环群、生成元：由一个单独元素的一切幂所组成的群称为循环群,称为这个群的生成元;定理在阶数为的循环群,由生成元所产生的元次数为,即是生成元的充分必要条件是和互质;定理若和不是互质的,则的次数是,其中的是和的最小公倍数;定义阿贝尔群：如果群中的元对于运算满足交换律,则称这个群是一个阿贝尔群; “满足交换律的群叫做阿贝尔群”循环群是一个阿贝尔群;定理若和都是有限的阿贝尔群,定义则是一个阿贝尔群;最简单的一个阿贝尔群是群,为按位加二面体群、置换群二面体群是从图形的变换中到处,这些图形都是比较正规的图形;定理更一般地讲,定义置换：若是一个非空的有限集合,则上任何一个到它自身的一一对应的映射,都称为上的置换;定理两个置换的乘积仍是一个置换,并且置换的乘积服从结合律;的恒等映射也是一个置换称为单位置换;上所有置换的集合,对于置换乘法构成一个群,这个群称为对称群,记为,是中元的个数;定义阶置换群若是非空有限集合,是上的个置换所构成的群,则称是一个阶置换群; 定理任何一个阶群都同构于一个阶置换群;子群、群的同态定义子群：是一个群,,如果1单位元2若,则的逆元3若,则则称是的一个子群;定理是一个群,,是一个子群的充分必要条件是：若,则定义同态象、群同态映射：和是群,.若对任何,有群的同态映射具有下列性质：1将单位元映射为单位元2将逆元映射为逆元3对运算封闭,即对任何,有定理若和是群,是一个群同态映射,则将的子群映射为的子群;定义同态核：若是一个群同态映射,是的单位元,则中所有满足的元的集合,称为同态核,记为.定理同态核是一个子群;定理若是群的子群,则定义了上的一个划分因而也定义了上一个等价关系. 群子集：假定都是群中的元构成的集合称之为群子集,定义特别地,当是一元集时,我们简记为,则定理若是群的子群都是群的子群,则是一个群的充分必要条件是.陪集、正规子群、商群定义左陪集：若是群的子群,对于,称称为的一个左陪集. 定理若是群的子群,则的所有左陪集构成的一个划分;定理拉格朗日定理每个左陪集的元和中的元都是一样多;推论子群中元的个数一定是群中元的个数的因子;定义正规子群：若是群的子群,对于任何,都满足,则称是群的一个正规子群.一个阿贝尔群的任何子群都是正规子群;当是群的正规子群时,对于关于的陪集.定义运算为考虑所有关于的陪集组成的集合和运算构成的系统为一个群;这个群称为关于的商群,记为.定理若是从群到群的映上的同态映射,则核是正规子群,商群同构于.群同态基本定理：商群是由陪集构成的群,也是同余类的集构成的群,所以它同构于象代数,即同构于.如果群没有真正的正规子群,则该群为单群;正规群的任何子群都是正规子群;第3章格和布尔代数格定义格：表示一个偏序集,如果对于中的任何两个元和,在中都存在一个元是它们的上确界,存在一个元是它们的下确界,则称是一个格;对于中的元,它们的上确界常常记为,它们的下确界常常记为,前者又称为和析取或和或,后者又称为和的合取或积或或;定理若是一个格,则对于任何,有（1）的充分必要条件是.（2）的充分必要条件是.定理保序性若是一个格,则对于任何,当时,有引理若是一个格,,则定理分配不等式：若是一个格,则对于任何,定理模数不等式若是一个格,则对于任何,的充分必要条件是定理若是一个代数系统,和是上的二目运算,它服从交换律、结合律和吸收律.则是一个格.定义子格是一个格,,当且仅当对于运算和是封闭的,运算结果和在中相同时,则称代数系统是的一个子格;定义直接积若和是两个格,则称为这两个格的直接积,其中的运算和定义为：对于任何的,定义同态映射设和是两个格,.如果对任何,有则称是到的一个同态映射.特别地,当是一个一一对应时,称是一个同构映射,并且称格和同构的;如果是格上一个同态映射,则称是一个自同态映射.如果是一个同构映射,则称是一个自同构映射.定义完备：对于一个格,如果它的每一个非空子集在格中都具有一个上确界和下确界,则这个格称为完备的;显然每个有限的格都是完备的;对于一个格,它的上确界和下确界如果存在,我们称它们为这个格的边界,并分别记为1和0,因此有时这种格称为有界格;定义补元：是一个有界格,,如果存在元,使且,则称为的补元;定义补格：中的每个元都至少具有一个补元,则称这个格是一个补格;定义分配格：是一个格,如果对任何,有则称是一个分配格;定理任何两个分配格的直接积是分配格;定理若是一个分配格,则对于任何,如果,并且,则推论如果一个格是分配格,同时又是补格,则它的每一个元都具有唯一的一个补元;布尔代数定义布尔代数一个既是补格,又是分配格的格,称为布尔代数;定义对偶命题如果是一个布尔代数,是关于中变元的一个命题,它可以由中变元元通过运算来表示.如果对的表示式进行下列代换：代换为；代换为；代换0；0代换为1,则这样代换后也将得到一个命题,它成为命题的对偶命题,简称为对偶;定理对偶原理如果是一个命题,它在任何一个布尔代数中都成立,并且可以由运算来表示,则对它的对偶命题也在任何一个布尔代数中成立;定理对偶原理如果是一个命题,它在任何一个布尔代数中都成立,并且可以由运算和关系来表示,则将中的运算代换为；代换为；0代换为1,代换0；换为,换为,所得到的对偶命题也在任何一个布尔代数中成立;定理若和是两个布尔代数,是一个同态映射,则在中的同态象是的一个子布尔代数;定义基元：是一个布尔代数,,如果中不存在元,使,则称是的一个基元;如果对于任何都存在有基元,则称这个布尔代数是基元的; 定理若是一个布尔代数,,则下列命题是等价的;1是一个基元2对于所有的,若,则或3对于所有的,推论若和是不同的基元,定理是一个基元的布尔代数,是其基元的集合,对任一令,则,并且作为基元的析取式,这个表达式是唯一的;定理若是一个非空有限的布尔代数,是它的所有基元构成的集合,则同构.推论一个有限的布尔代数具有个元,其中的是它的基元的个数;推论对于任意正整数,具有个元的布尔代数是同构的;其他代数系统定义环若代数系统满足下列条件：1对于二目运算是一个可交换的加法群;2对于二目运算即乘法是封闭的;3乘法结合律成立,即对中任何三个元和,有4分配律成立,即对中任何元和,有则称是一个环;定义交换环一个环中的任何两个元,如果都满足,则称是一个交换环;定义逆元、零元一个环中如果存在有元,使得对中任何一个元都有,则称是的一个单位元;定义逆元、零元在一个有单位元的环里,如果和是环中的元,满足,则称是。

离散数学集合论基础知识离散数学是计算机科学中一门重要的基础学科，集合论是离散数学的基础之一。

在这篇文章中，我们将介绍离散数学集合论的基础知识，包括集合的定义、运算、关系等内容。

一、集合的定义与表示集合是具有确定性的事物或对象的总体，它是数学中的一个基本概念。

我们可以用不同的方式表示一个集合，包括列举法、描述法和图形法。

（一）列举法列举法是通过列举集合中的元素来表示一个集合。

例如，可以用列举法表示自然数集合N={1, 2, 3, 4, …}，表示所有正整数的集合。

（二）描述法描述法是通过描述集合中元素的性质来表示一个集合。

例如，可以用描述法表示偶数集合E={x | x是整数，且x能被2整除}，表示所有能被2整除的整数的集合。

（三）图形法图形法是用图形的方式表示一个集合。

例如，可以用图形法表示平面上所有整数坐标点构成的集合。

二、集合的运算集合的运算包括并集、交集、差集和补集等。

（一）并集集合A与集合B的并集，记作A∪B，表示由所有属于集合A或集合B的元素组成的集合。

例如，设A={1, 2, 3}，B={3, 4, 5}，则A∪B={1, 2, 3, 4, 5}。

（二）交集集合A与集合B的交集，记作A∩B，表示由既属于集合A又属于集合B的元素组成的集合。

例如，设A={1, 2, 3}，B={3, 4, 5}，则A∩B={3}。

（三）差集集合A与集合B的差集，记作A-B，表示由属于集合A但不属于集合B的元素组成的集合。

例如，设A={1, 2, 3}，B={3, 4, 5}，则A-B={1, 2}。

（四）补集对于给定的全集U，集合A相对于全集U的补集，记作A'或者A^c，表示由全集U中不属于集合A的元素组成的集合。

例如，设全集U为自然数集合N，A={2, 4, 6}，则A'={1, 3, 5, 7, ...}（即不是偶数的自然数）。

三、集合的关系集合的关系包括包含关系、相等关系和互斥关系等。

离散数学教程——的基本概念离散数学是一门研究离散的、不连续的数学结构和对象的学科。

它涉及了数理逻辑、集合论、图论、代数、组合数学等多个领域，其基本概念构成了离散数学的基础，下面将介绍其中的几个重要概念。

1.集合：集合是离散数学中最基本的概念之一、集合是由一些对象组成的整体，这些对象称为集合的元素。

集合可以用大写字母表示，元素用小写字母表示，并用花括号括起来。

例如，{1,2,3}是一个包含了元素1、2和3的集合。

2.二元关系：二元关系是一种描述两个对象之间关系的数学概念。

通常用有序对来表示。

例如，对于集合A={1,2,3}和B={4,5,6}，我们可以定义一个二元关系R，其中每个有序对(x,y)表示x属于A，y属于B。

例如，(1,4)表示1和4之间存在这个关系。

3.图论：图论是研究图及其性质的数学分支。

图由节点和边组成，节点表示对象，边表示对象之间的连接关系。

图可以分为有向图和无向图，有向图中边有方向，无向图中边没有方向。

图的顶点数和边数分别用，V，和，E，表示。

图的最短路径、连通性、最大流等是图论中常见的问题。

4.排列与组合：排列和组合是组合数学中的两个重要分支。

排列是指从n个元素中取出k个，按照一定顺序排列的方式。

组合是指从n个元素中取出k个，不考虑排列顺序的方式。

排列数和组合数可以用公式来计算，例如排列数的计算公式是P(n,k)=n!/(n-k)!，组合数的计算公式是C(n,k)=n!/((n-k)!*k!)。

5.布尔代数：布尔代数是对逻辑运算进行抽象和推广后所形成的一种代数系统。

它由逻辑与、或、非等运算符以及逻辑变量组成，可以表示和操作命题逻辑中的各种逻辑关系。

布尔代数在计算机科学中有广泛的应用，可以用于逻辑电路设计、布尔函数的表示与化简等。

以上是离散数学中的一些基本概念，这些概念在离散数学的理论研究和实际应用中起着重要作用。

离散数学的研究方法和思维方式与连续数学不同，强调离散结构的分析和推理，对于计算机科学、信息技术等领域的学习和研究都具有重要意义。

离散数学第三章集合的基本概念和运算知识点总结集合论部分第三章、集合的基本概念和运算3.1 集合的基本概念集合的定义与表⽰集合与元素集合没有精确的数学定义理解：⼀些离散个体组成的全体组成集合的个体称为它的元素或成员集合的表⽰列元素法A={ a, b, c, d }谓词表⽰法B={ x | P(x) }B 由使得P(x) 为真的x构成常⽤数集N, Z, Q, R, C 分别表⽰⾃然数、整数、有理数、实数和复数集合，注意0 是⾃然数.元素与集合的关系：⾪属关系属于∈，不属于?实例A={ x | x∈R∧x2-1=0 }, A={-1,1}1∈A, 2?A注意：对于任何集合A 和元素x (可以是集合)，x∈A和x?A 两者成⽴其⼀，且仅成⽴其⼀.集合之间的关系包含（⼦集）A?B??x (x∈A→x∈B)不包含A?B??x (x∈A∧x?B)相等A = B?A?B∧B?A不相等A≠B真包含A?B?A?B∧A≠B不真包含A?B思考：≠和?的定义注意∈和?是不同层次的问题空集?不含任何元素的集合实例{x | x2+1=0∧x∈R} 就是空集定理空集是任何集合的⼦集Ax (x∈?→x∈A) ?T推论空集是惟⼀的.证假设存在?1和?2，则?1??2 且?1??2，因此?1=?2全集E 相对性在给定问题中，全集包含任何集合，即?A (A?E )幂集定义P(A) = { x | x?A }实例P(?) = {?}，P({?}) = {?,{?}}P({1,{2,3}})={?,{1},{{2,3}},{1,{2,3}}}计数如果|A| = n，则|P(A)| = 2n3.2 集合的基本运算集合基本运算的定义??-~⊕并A?B = { x | x∈A∨x∈B }交A?B = { x | x∈A∧x∈B }相对补A-B = { x | x∈A∧x?B }对称差A⊕B = (A-B)?(B-A)= (A?B)-(A?B)绝对补~A = E-A⽂⽒图（John Venn）关于运算的说明运算顺序：~和幂集优先，其他由括号确定并和交运算可以推⼴到有穷个集合上，即A1?A2?…A n= {x | x∈A1∨x∈A2∨…∨x∈A n}A1?A2?…A n= {x | x∈A1∧x∈A2∧…∧x∈A n}某些重要结果A-B?AA?B ?A-B=?（后⾯证明）A?B=??A-B=A命题演算法证X?Y：任取x ，x∈X?… ?x∈Y 例3 证明A?B?P(A)?P(B)任取xx∈P(A) ?x?A?x?B ? x∈P(B)任取xx∈A ? {x}?A ? {x}∈P(A) ? {x}∈P(B){x}B x∈B包含传递法证X?Y：找到集合T 满⾜X?T 且T?Y，从⽽有X?Y例4 A-B ? A?B证A-B ? AA ? A?B所以A-B ? A?B利⽤包含的等价条件证X?Y：例5 A?C∧B?C ?A?B?C证A?C?A?C=CB?C?B?C=C(A?B)?C=A?(B?C)=A?C=C(A?B)?C=C ?A?B?C命题得证反证法证X?Y：欲证X?Y, 假设命题不成⽴，必存在x 使得x∈X 且x?Y. 然后推出⽭盾.例6 证明A?C ∧ B?C ? A?B?C证假设A?B ? C 不成⽴，则?x (x∈A?B∧x?C)因此x∈A 或x∈B，且x?C若x∈A, 则与A?C ⽭盾；若x∈B, 则与B?C ⽭盾.利⽤已知包含式并交运算：由已知包含式通过运算产⽣新的包含式X?Y ?X?Z?Y?Z, X?Z?Y?Z 例7 证明A?C?B?C ∧ A-C?B-C ? A?B证A?C?B?C，A-C ? B-C上式两边求并，得(A?C)?(A-C) ? (B?C)?(B-C)(AC)(A~C) (BC)(B~C)A(C~C) B(C~C)AE BEA B命题演算法证明X=Y：任取x ，x∈X ?… ?x∈Yx∈Y ?… ?x∈X或者x∈X ?… ? x∈Y例8 证明A?(A?B)=A （吸收律）证任取x,x∈A?(A?B) ? x∈A∨ x∈A?Bx∈A ∨ (x∈A ∧ x∈B) ? x∈A等式替换证明X=Y：不断进⾏代⼊化简，最终得到两边相等例9 证明A?(A?B)=A （吸收律）证(假设交换律、分配律、同⼀律、零律成⽴)A?(A?B)=(A?E)?(A?B) 同⼀律=A?(E?B) 分配律=A?(B?E) 交换律=A?E 零律=A 同⼀律反证法证明X=Y：假设X=Y 不成⽴，则存在x 使得x∈X且x?Y，或者存在x 使得x∈Y且x?X，然后推出⽭盾.例10 证明以下等价条件A?B ? A?B=B ? A?B=A ? A-B=?(1) (2) (3) (4)证明顺序：(1) ?(2), (2) ?(3), (3) ?(4), (4) ?(1)(1) ?(2)显然B?A?B，下⾯证明A?B?B.任取x，x∈A?B ? x∈A∨x∈B ? x∈B∨x∈B ? x∈B因此有A?B?B. 综合上述（2）得证.(2) ?(3)A=A?(A?B) ? A=A?B（将A?B⽤B代⼊)(3) ?(4)假设A-B≠?, 即?x∈A-B，那么x∈A且x?B. ⽽x?B ? x?A?B.从⽽与A?B=A⽭盾.(4) ?(1)假设A?B不成⽴，那么x (x∈A ∧ x?B) ? x∈A-B ? A-B≠?与条件（4）⽭盾.集合运算法证明X=Y：由已知等式通过运算产⽣新的等式X=Y ? X?Z=Y?Z, X?Z=Y?Z，X-Z=Y-Z 例11 证明A?C=B?C ∧ A?C=B?C ? A=B证由A?C=B?C 和A?C=B?C 得到(A?C)-(A?C)=(B?C)-(B?C)从⽽有A⊕C=B⊕C因此A⊕C=B⊕C ? (A⊕C)⊕C =(B⊕C)⊕CA⊕(C⊕C) =B⊕(C⊕C) ?A⊕?=B⊕?? A=B3.3 集合中元素的计数集合的基数与有穷集合集合A 的基数：集合A中的元素数，记作card A有穷集A：card A=|A|=n，n为⾃然数.有穷集的实例：A={ a,b,c}, card A=|A|=3；B={ x | x2+1=0, x∈R}, card B=|B|=0⽆穷集的实例：N, Z, Q, R, C 等包含排斥原理：定理设S 为有穷集，P1, P2, …, P m是m 种性质，A i 是S中具有性质P i的元素构成的⼦集，i=1, 2,…, m.则S中不具有性质P1, P2, …, P m 的元素数为证明要点：任何元素x，如果不具有任何性质，则对等式右边计数贡献为１，否则为０证设x不具有性质P1, P2, … , P m ,x?A i, i= 1, 2, … , mx?A i?A j, 1≤i < j ≤m…x?A1?A2?…?A m,x 对右边计数贡献为1 - 0 + 0 -0 + … + (-1)m· 0 = 1例1 求1到1000之间（包含1和1000在内）既不能被5 和6 整除，也不能被8 整除的数有多少个？解：S ={ x | x∈Z, 1≤x ≤1000 },如下定义S的3 个⼦集A, B, C：A={ x | x∈S, 5 | x }，B={ x | x∈S, 6 | x }，C={ x | x∈S, 8 | x }对上述⼦集计数：|S|=1000,|A|= ?1000/5? =200, |B|=?1000/6?=133，|C|= ?1000/8? =125,|A?B|= ?1000/30? =33, |B?C| = ?1000/40? =25,|B?C|= ?1000/24? =41,|A?B?C| = ?1000/120? =8,代⼊公式N = 1000-(200+133+125)+(33+25+41)-8=600例224名科技⼈员，每⼈⾄少会1门外语.英语：13；⽇语：5；德语：10；法语：9英⽇：2; 英德：4；英法：4；法德：4 会⽇语的不会法语、德语求：只会1 种语⾔⼈数，会3 种语⾔⼈数x+2(4-x)+y1+2=13x+2(4-x)+y2=10x+2(4-x)+y3=9x+3(4-x)+y1+y2+y3=19x=1, y1=4, y2=3, y3=2。