离散数学26.笛卡尔乘积及相关定理

第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分配律成立,即对中任何元和,有则称是一个环;定义交换环一个环中的任何两个元,如果都满足,则称是一个交换环;定义逆元、零元一个环中如果存在有元,使得对中任何一个元都有,则称是的一个单位元;定义逆元、零元在一个有单位元的环里,如果和是环中的元,满足,则称是。

离散数学部分概念和公式总结命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。

命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。

给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。

若指定的一组值使A的值为真，则称成真赋值。

真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。

将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。

命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。

（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。

（3）若A至少存在一组赋值是成真赋值，则A是可满足式。

主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B 是等值的，记作A<=>B。

约束变元和自由变元：在合式公式xA和 xA中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。

一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。

前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Qk…xkB，称A为前束范式。

集合的基本运算：并、交、差、相对补和对称差运算。

笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。

二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。

《离散数学(本)》主要概念、定理与方法第1章集合及其运算一、概念集合（元素）——集合是一些具有确定的、可以区分的若干事件的全体，而集合中的事件称为元素．因此，集合是由若干元素组成的．若a是集合A中的元素，则称a属于A，记作a∈A；若a不是集合A中的元素，则称a不属于A，记作a∉A．定义1.1.1（子集）对任意两个集合A和B，若B中的每个元素都是A中的元素，则称B 为A的子集，记作B⊆A或A⊇B．若B是A的子集，也称A包含B，或B被A包含．若B不是A的子集，即B⊆A不成立时，记作B⊆A．定义1.1.2（集合相等）对任意两个集合A和B，若有A⊆B且B ⊆A，则称A与B相等，记作A= B．定义1.1.3（真子集）对任意两个集合A和B，若B⊆A且B≠A，则称B为A的真子集，记作B⊂A或A⊃B．定义1.1.4（空集）不含任何元素的集合称为空集，记作∅．空集的定义也可以写成≠} （1.1.1）∅={x x xn元集（m元子集）——含有n个元素的集合简称n元集，它的含有m（m≤n）个元素的子集叫做它的m元子集．定义1.1.5（全集）在一个具体问题中，如果所涉及的集合都是某个集合的子集，则将这个集合称为全集，记作E．定义1.1.6（幂集）设A是一个集合，由A的所有子集组成的集合，称为A的幂集，记作P(A)或2A．定义1.2.1（并集、交集、差集、补集、对称差）设E为全集，A和B是E中任意两个子集．（1）所有属于A或属于B的元素组成的集合，称为集合A与B的并集，记作A⋃B．即∈}（1.2.1）{或x BA B x x A⋃=∈⋂．即（2）既属于A又属于B的所有元素组成的集合，称为集合A与B的交集，记作A B∈}（1.2.2）{且x B⋂=∈A B x x A如果两个集合A和B没有公共元素，即A B⋂=∅，称为集合A与B不相交．-．即（3）属于A而不属于B的所有元素组成的集合，称为A与B的差集，记作A B-=∈∉A B且（1.2.3）x x A x B{}（4）由E中所有不属于A的元素组成的集合，称为A的补集，记作~A．即~A={}且（1.2.4）x x E x A∈∉补集~A可以看作全集E与集合A的差集，即~A = E -A．（5）集合(A - B )⋃(B - A )称为集合A和B的对称差，记作A⊕B．即A⊕B = (A - B )⋃(B - A )．（1.2.5）对称差运算的另一种定义是A⊕B = (A⋃B ) - (B ⋂A )．（1.2.5’）二、定理与性质集合包含关系的自反性：对于任意集合A，有A⊆A．集合包含关系的反对称性：对任意两个集合A和B，若有A⊆B且B⊆A，则A=B．集合包含关系的传递性：对任意三个集合A，B和C，若有A⊆B，B⊆C，则A⊆C．定理1.1.1空集是一切集合的子集．定理1.1.1的推论空集是唯一的．集合运算的交换律：A B B A⋃=⋃⋂=⋂A B B A集合运算的结合律：()()A B C A B C ⋃⋃=⋃⋃()()A B C A B C ⋂⋂=⋂⋂集合运算的分配律：A B C A B A C ⋃⋂=⋃⋂⋃()()()A B C A B A C ⋂⋃=⋂⋃⋂()()()集合运算的幂等律：A ⋃A = AA ⋂A = A集合运算的同一律：A A ⋃∅=A E A ⋂=集合运算的零律：A ⋃E = EA ⋂∅=∅集合运算的补余律：A ⋃~A = EA ⋂~A =∅集合运算的吸收律：A A B A ⋃⋂=()A AB A ⋂⋃=()集合运算的摩根律：A - (B ⋃C ) = (A - B )⋂(A - C )A - (B ⋂C ) = (A - B )⋃(A - C )~ (B ⋃C ) = ~ B ⋂~ C~ (B ⋂C ) = ~ B ⋃~ C~∅= E~E =∅集合运算的双补律：~(~A ) = A对称差的交换律：A B B A ⊕=⊕对称差的结合律：()()A B C A B C ⊕⊕=⊕⊕对称差的分配律：A B C A B A C ⋂⊕=⋂⊕⋂()()()对称差的同一律：A A ⊕∅=对称差的零律：A ⊕A = ∅对称差的性质：A ⊕(A ⊕B ) = B定理1.2.1 对任意两个有限集合A 和B ，用S 表示有限集合S 中的元素数，则(1) A B ⋃≤A +B ； (2) A B ⋂≤min (A +B ) ；(3) A B -≥A -B ； (4) A B ⊕=A +B - 2A B ⋂ ．定理1.2.2（容斥定理） 对任意两个有限集合A 和B ，有A B ⋃= A +B - A B ⋂ （1.2.6） 其中A ，B 分别表示A ，B 的元素个数．定理1.2.2的推广结论：对于任意三个有限集合A , B , C ，有A B C ⋃⋃ = A +B +C -A B ⋂-A C ⋂-B C ⋂+A B C ⋂⋂（1.2.7）三、方法1．集合的三种表示方法列举法是列出集合的所有元素，并用花括号括起来．例如A = {a b c d ,,,}，N = {0, 1, 2, 3, …}．描述法是将集合中元素的共同属性描述出来．例如B = {x x x R 210-=∈且}，D = {x x 是正整数}．文氏图法是用一个简单的平面区域表示一个集合，用区域内的点表示集合内的元素．2．有限集合的计数方法首先根据已知条件把对应的文氏图画出来，然后将已知集合的元素填入表示该集合的区域内．通常从几个集合的交集填起，根据计算结果将数字逐步填入所有的空白区域内．如果交集的数字是未知的，可以将其设为x ，再根据已知条件列出方程或方程组，解出未知数x ．第2章 关系与函数一、概念有序对——有序对是指两个元素x 和y (允许x = y ) 按给定顺序排列组成的二元组合，记作<x , y > ．其中x 是它的第一元素，y 是它的第二元素．定义2.1.1（笛卡尔积、直乘积） 设A 和B 是任意两个集合，用A 中元素为第一元素，B 中元素为第二元素构成有序对，所有这样的有序对组成的集合称为集合A 和B 的笛卡尔积，或称为集合A 和B 的直乘积，记作A ⨯B ．即A ⨯B = {< x , y >x A ∈且y B ∈}定义2.1.2（二元关系） 任何一个有序对集合，称为一个二元关系，简称关系，记作R ．对于二元关系R ，若<a ，b >∈R ， 可记作aRb ；若<a ，b >∉R ， 则记作a R b ．定义2.1.3（从A 到B 的二元关系） 设A 和B 是两个集合，A ⨯B 的任一子集所定义的二元关系R 称为从A 到B 的二元关系．当A =B 时，称R 为A 上的二元关系．定义2.1.4（定义域、值域） 关系R 中有序对的第一元素所允许选取对象集合称为关系R 的定义域，记作Dom （R ），第二元素所允许选取对象集合称为关系R 的值域，记作Ran （R ）． 定义2.1.5（空关系、全关系、恒等关系） 对任何集合A ，(1) 因为空集∅是A ⨯A 的子集，所以定义了A 上的关系，称为A 上的空关系；(2) 定义 E A ={<a ，b >⎢a ∈A 且b ∈A }= A ⨯A ，称为A 上的全关系；(3) 定义I A ={<a ，a >⎢a ∈A }，称为A 上的恒等关系．定义2.1.6（关系矩阵） 设集合A ={a 1，a 2，…，a m }，B ={b 1，b 2，…，b n }，(1) 若R 是从A 到B 的一个关系，则R 的关系矩阵是m ⨯n 矩阵M R =()nm j i r ⨯， 其中 ⎪⎩⎪⎨⎧=ji j i j i b R a Rb a r 当当,0,1，(i =1, 2, …, m ；j =1, 2, …, n )． (2) 若R 是A 上一个关系，则R 的关系矩阵是m 阶矩阵M R =()mm j i r ⨯， 其中 ⎪⎩⎪⎨⎧=ji j i j i b R a Rb a r 当当,0,1，(i , j =1, 2, …, m )． 定义2.1.7（结点、关系图、自回路） 设集合A ={a 1，a 2，…，a m }，B ={b 1，b 2，…，b n }，若R 是从A 到B 的一个关系，则用m 空心点表示a 1，a 2，…，a m ，用n 空心点表示b 1，b 2，…，b n ，这些空心点统称为结点．如果a i Rb j ，那么由结点a i 到结点b j 作一条有向弧，箭头指向b j ；如果<a i ，b j >∉R ，那么结点a i 与b j 之间没有弧连结，这样的图形称为R 的关系图． 若R 是A 上一个关系，如果a i Ra j (i ≠j )，有向弧的画法与上面相同；如果a i Ra i ，则画一条从结点a i 到结点 a i 的带箭头的封闭弧，称为自回路．定义2.2.1（复合关系） 设A ，B ，C 是三个集合，R 是从A 到B 的一个二元关系，S 是从B 到C 的一个二元关系，则R 与S 的复合关系为R ·S ={<a , c >⎢a ∈A ，c ∈C ，且存在b ∈B ，使<a , b >∈R ，<b , c >∈S }这个复合关系是从A 到C 的一个二元关系．布尔运算——布尔运算只涉及数字0和1，规定：加法：0+0 = 0， 0+1 = 1+0 = 1+1 = 1；乘法：1⨯1 = 1， 1⨯0 = 0⨯1 = 0⨯0 = 0 ．定义2.2.2（复合关系矩阵） 设集合A ={a 1，a 2，…，a m }，B = {b 1，b 2，…，b n }，C = {c 1，c 2，…，c p }，从A 到B 的二元关系R 的关系矩阵M R 是一个m 行n 列的矩阵，从B 到C 的二元关系S 的关系矩阵M S 是一个n 行p 列矩阵，则从A 到C 的复合关系R ·S 的关系矩阵S R M •是一个m 行p 列矩阵，并且S R M •= M R ⨯ M S （2.2.1）其中⨯表示按布尔运算进行矩阵乘法运算．定义2.2.3（二元关系的幂） 设R 是集合A 上的一个二元关系，n ∈N ，则关系R 的n 次幂R n 定义为：(1) R 0= I A ，即R 0是集合A 上的恒等关系；(2) R n +1 = R n ·R ．定义2.2.4（逆关系） 设R 是从集合A 到B 的二元关系，则从集合B 到A 的二元关系R –1：R –1 = {<b , a > <a , b >∈R } (2.2.3) 称为R 的逆关系．定义2.3.1（自反关系、反自反关系） 设R 是集合A 上的二元关系，若对任意a ∈A ，都有aRa ，即<a , a >∈R ，则称R 为A 上自反的关系；若对任意a ∈A ，都有a R a ，即<a , a >∉R ，则称R 为A 上反自反的关系．定义2.3.2（对称关系、反对称关系） 设R 是集合A 上的二元关系，对任意a ，b ∈A ，若有<a , b >∈R ，就必有<b , a >∈R ，则称R 为A 上对称的关系；若有<a , b >∈R ，且<b , a >∈R ，就必有b = a ，则称R 为A 上反对称的关系．定义2.3.3（传递关系） 设R 是集合A 上的二元关系，对任意a ，b ，c ∈A ，若有<a , b >∈R ，且<b , c >∈R ，就必有<a , c >∈R ，则称R 为A 上传递的关系．定义2.3.4（自反闭包、对称闭包，传递闭包） 设非空集合A 上的二元关系R ，若有A 上的另一个二元关系R '满足：(1) R '是自反的（对称的，传递的）；(2) R ⊆R '；(3) 对A 上任何包含R 的自反（对称，传递）关系R ''都有R '⊆R ''；则称关系R '为R 的自反（对称，传递）闭包，记作r (R )（s (R )，t (R )）．定义2.4.1（等价关系） 设R 是非空集合A 上的二元关系，如果R 是自反的、对称的和传递的，则称R 是A 上的等价关系．设R 是一个等价关系，如果<a , b >∈R ，称a 等价于b ，记作a ~ b ．定义2.4.2（等价类） 设R 是非空集合A 上的等价关系，对任意a ∈A ，令[a ]R = {b ⎪b ∈A 且aRb } (2.4.1)则称集合[a ]R 为a 关于R 的等价类，简称a 的等价类，简记作[a ]或a ．定义2.4.3（商集） 设R 是非空集合A 上的等价关系，以R 的所有等价类作为元素的集合，成为A 关于R 的商集，记作A/R ．即A/R = {[a ]R ⎪a ∈A } (2.4.2) 定义2.4.4（划分块） 设A 是非空集合，若A 的子集族π满足：(1) π∉∅；(2) π中任何两个子集都不相交；(3) π中所有子集的并集就是A ．则称π为A 的一个划分，称π中的元素为A 的划分块．定义2.5.1（相容关系） 设R 是非空集合A 上的二元关系，如果R 是自反的、对称的，则称R 是A 上的相容关系．定义2.5.2（相容类） 设R 是非空集合A 上的相容关系，B 是A 的子集，如果在B 中的任意两个元素都是相关的，则称为由相容关系R 产生的相容类．最大相容类——R 是A 上的相容关系，B 是相容类，若在差集A -B 中没有一个元素能和B 中所有元素都是相关的，则称B 为最大相容类．定义2.5.3（覆盖） 设A 是非空集合，若A 的子集族π满足：(1) π∉∅；(2) π中所有子集的并集就是A ．则称π为A 的一个覆盖，称π中的元素为A 的覆盖块．定义2.5.4（完全覆盖） 设集合A 的子集族π={A 1 , A 2 , … , A n }是A 的覆盖，且对π中任意元素A i ，不存在其它元素A j ，使得A i 是A j 的子集，则称π为A 的一个完全覆盖．定义2.5.5（偏序关系） 设R 是非空集合A 上的二元关系，如果R 是自反的、反对称的和传递的，则称R 是A 上的偏序关系，或称序关系，记作≤．设≤是偏序关系，如果<a , b >∈≤，则记作a ≤b ，读作a “小于等于”b ．定义2.5.6（拟序关系） 设R 是非空集合A 上的二元关系，如果R 是反自反的和传递的，则称R 是A 上的拟序关系，记作<．设<是拟序关系，如果<a , b >∈<，则记作a <b ，读作a “小于”b ．定义2.5.7（全序关系、线序关系） 设R 是非空集合A 上的偏序关系，如果对任意a ，b ∈A ，必有a ≤b 或b ≤a ，则称R 是A 上的全序关系，或称线序关系．定义2.5.8（偏序集） 集合A 和A 上的偏序关系≤一起称为偏序集，记作<A ，≤>． 哈斯图——对于给定的偏序集<A ，≤>，用一个简化的偏序关系图来表示，我们将这种简化的关系图称为哈斯（Hasse ）图．它的作图规则为：(1) 去掉每个结点的自回路，只用一个空心点表示集合A 的元素；(2) 适当排列结点的顺序，即对任意a ，b ∈A ，若a ≤b ，则将a 画在b 的下方；(3) 对任意a ，b ∈A ，若a <b ，且不存在c ∈A ，使得a <c <b ，则就在a ，b 之间画一条无向弧．定义2.5.9（盖住） 设R 是非空集合A 上的偏序关系，a 和b 是A 中两个不同的元素，如果<a , b > ∈R ，且在A 中没有其它元素c ，使得<a , c >∈R 和<c , b >∈R ，则称元素b 盖住元素a ． 定义2.5.10（最大元、最小元、极大元、极小元） 设<A ，≤>为序集，集合B ⊆A ，存在元素b ∈B ，(1) 若对任意a ∈B ，都有a ≤b ，则称b 为B 的最大元；(2) 若对任意a ∈B ，都有b ≤a ，则称b 为B 的最小元；(3) 若对任意a ∈B ，且b ≤a ，都有a = b ，则称b 为B 的极大元；(4) 若对任意a ∈B ，且a ≤b ，都有a = b ，则称b 为B 的极小元．定义2.5.10（上界、下界、最小上界、上确界、最大下界、下确界） 设<A ，≤>为偏序集，集合B ⊆A ，存在元素b ∈A ，(1) 若对任意a ∈B ，都有a ≤b ，则称b 为B 的上界；(2) 若对任意a ∈B ，都有b ≤a ，则称b 为B 的下界；(3) 若集合C = {b ⎪b 为B 的上界}，则C 的最小元称为B 的最小上界或上确界；(4) 若集合D = {b ⎪b 为B 的下界}，则D 的最大元称为B 的最大下界或下确界． 定义2.6.1（函数、映射） 对集合A 到集合B 的二元关系f ，若满足下列条件：(1) 对任意a ∈Dom(f )，都存在唯一的b ∈Ran(f )，使<a , b >∈f ，（即afb ）成立；(2) Dom(f ) = A ；则称f 为从A 到B 的函数，或称为映射，记作f ：A →B ．若有afb ，则可记作b = f (a )．定义2.6.2（函数相等） 设f 和g 是从集合A 到B 的两个函数，若对任意a ∈A ，都有f (a ) = g (a )，则称函数f 和g 相等，记作f = g ．定义2.6.3（函数的象） 设f 是从集合A 到B 的函数，且A 1⊆A ，则将f (A 1) = {f (a ) a ∈A 1}称为A 1在f 下的象．特别地，称f (A )为函数的象．定义2.6.4（满射、单射、双射） 设f 是从集合A 到B 的函数，(1) 若Ran(f ) = B ，则称f 为从A 到B 的满射；(2) 若对任意b ∈Ran(f )，都存在唯一的a ∈Dom(f )，使得f (a ) = b ，则称f 为从A 到B 的单射，或称一对一的；(3) 若f 从A 到B 既是满射又是单射的，则称f 为从A 到B 的双射，或称一一对应的．定义2.6.5（常数函数、恒等函数、单调递增、严格单调递增、单调递减、严格单调递减、特征函数、自然映射）(1) 设f 是从集合A 到B 的函数，若存在一个b ∈B ，使得对所有的a ∈A 都有f (a ) = b ，则称f 是从A 到B 的常数函数．(2) 集合A 上的恒等关系I A 称为A 上的恒等函数．即对所有的a ∈A 都有I A (a ) = a ．(3) 设f 是实数集R 上的函数，对任意的a 1，a 2∈A ，如果由a 1< a 2，可得f (a 1)≤ f (a 2)，则称f 为单调递增的；如果由a 1< a 2，可得f (a 1)< f (a 2)，则称f 为严格单调递增的．类似地，可以定义单调递减的和严格单调递减的函数．(4) 设A 为集合，对任意子集A '⊆ A ，A '的特征函数A 'χ：E →{0 , 1}定义为A 'χ(a )=⎩⎨⎧'-∈'∈A A a A a ,0,1 (2.6.1) (5) 设R 是集合A 上的等价关系，令g 为从A 到A/R 的函数，即g (a ) =[a ]，则称g 为从A 到商集A/R 的自然映射．定义2.6.6（复合函数）设函数f：A→B，g：B→C，则将复合关系g•f = {<a , c> a∈A，c∈C，且存在b∈B，使f(a) = b，g(b) = c}称为函数f和g的复合函数．定义2.6.7（反函数）设函数f：A→B是双射的，则将f的逆关系称为反函数，记作f–1：B →A．可逆函数——如果函数f 存在反函数f–1，称f是可逆的．二、定理与性质有序对性质1 当x≠y时，有序对< x , y >≠< y , x > ．有序对性质2有序对< x , y > = < a , b > 的充分必要条件是x = a，y = b．笛卡尔积性质1对任意集合A，有A⨯∅= ∅，∅⨯A= ∅．笛卡尔积性质2 笛卡尔积运算不满足交换律，即当集合A≠∅，B≠∅且A≠B时，A⨯B≠B⨯A．笛卡尔积性质3笛卡尔积运算不满足结合律，即当集合A≠∅，B≠∅且C≠∅时，(A⨯B )⨯C≠A⨯(B⨯C )．笛卡尔积性质4对并集的分配律：A⨯(B⋃C ) = (A⨯B)⋃(A⨯C )；(B⋃C )⨯A= (B⨯A)⋃(C⨯A )；笛卡尔积性质5对交集的分配律：A⨯(B⋂C ) = (A⨯B)⋂(A⨯C )；(B⋂C )⨯A= (B⨯A)⋂(C⨯A )．定理2.1.1对任意三个集合A, B和C，若有C≠∅，则(1)A⊆B的充分必要条件是A⨯C⊆B⨯C；(2)A⊆B的充分必要条件是C⨯A⊆C⨯B．定理2.1.2对任意四个非空集合A, B, C和D，则A⨯B⊆C⨯D的充分必要条件是A⊆C，B⊆D．定理2.2.1设R和S从A到B的两个二元关系，那么R和S的R⋃S，R⋂S，R-S，~R，R⊕S仍然是从A到B的二元关系．定理2.2.2设R是从集合A到B的二元关系，S和T分别是从集合B到C的二元关系，U 是从集合C到D的二元关系，则(1) R·(S⋃T) = R·S⋃R·T；(2) R·(S⋂T)⊆R·S⋂R·T；(3)(S⋃T)·U = S·U⋃T·U；(4)(S⋂T)·U⊆S·U⋂T·U．定理2.2.3设R，S，T，分别表示从集合A到B，从集合B到C，从集合C到D的二元关系，则(R·S)·T= R·(S·T) （2.2.2）定理2.2.4设R是集合A上的二元关系，m，n∈N，则(1) R m·R n = R m + n；(2) (R m)n = R m n．定理2.2.5设R和S分别是从集合A到B的二元关系，则(1) (R –1)-1 = R(2) (R⋃S)-1 = R -1⋃S -1(3) (R⋂S)-1 = R -1⋂S -1(4) (R -S)-1 = R –1 -S -1(5) (~R)–1 = ~R -1(6) (A⨯B)-1 = B⨯A(7) ∅-1 =∅(8) R=S⇔R –1=S –1 (9) R⊆S⇔R -1⊆S -1定理2.2.6设R是从集合A到B的二元关系，S是从集合B到C二元关系，则(R·S)-1 = S -1·R –1定理2.3.1设R是非空集合A上的二元关系，则(1) R是自反的当且仅当r (R) = R；(2) R是对称的当且仅当s (R) = R；(3) R是传递的当且仅当t (R) = R；定理2.3.2设R是非空集合A上的二元关系，I A是A上的恒等关系，则r (R) = R⋃I A．（2.3.1）定理2.3.3设R是非空集合A上的二元关系，则s (R) = R⋃R –1（2.3.3）定理2.3.4 设R是非空集合A上的二元关系，则t (R) =∞=⋃1iR i=R⋃R 2⋃R 3⋃… （2.3.5）定理2.3.4的推论设R是非空有限集合A上的二元关系，且A有n个元素，则t (R ) = ni 1=⋃R i =R ⋃R 2⋃…⋃R n （2.3.6） 定理2.4.1 设R 是非空集合A 上的等价关系，对任意a , b ∈A ，(1) [a ]∅≠，且[a ]⊆A ； (2) 若aRb ，则[a ]= [b ]；(3) 若a R b ，则[a ]⋂[b ]= ∅； (4) ⋃{[a ]⎪a ∈A }= A ．定理2.5.1 设R 是集合A 上的拟序关系，则R 是反对称的．定理2.6.1 设函数f ：A →B ，g ：B →C ，那么复合函数g •f 是一个从A 到C 的函数，而且，对任意一个a ∈A ，都有(g •f )(a ) = g (f (a ))．定理2.6.2 设函数f ：A →B ，g ：B →C ，h ：C →D ，那么h •(g •f ) = (h •g )•f (2.6.2)定理2.6.3 设函数f ：A →B ，g ：B →C ，且g •f ：A →C ，那么(1) 若f 和g 都是满射的，则g •f 也是满射的；(2) 若f 和g 都是单射的，则g •f 也是单射的；(3) 若f 和g 都是双射的，则g •f 也是双射的．定理2.6.4 设函数f ：A →B ，g ：B →C ，且g •f ：A →C ，那么(1) 若g •f 是满射的，则g 也是满射的；(2) 若g •f 是单射的，则f 也是单射的；(3) 若g •f 是双射的，则g 是满射的，f 是单射的．定理2.6.5 设函数f ：A →B 是双射的，则f -1：B →A 也是双射的．定理2.6.6 如果函数f ：A →B 是双射的，则有(1) f –1•f = I A ， f •f –1= I B ；(2) (f –1)-1 = f ． (2.6.4) 定理2.6.7 设函数f ：A →B ，g ：B →C ，且f 和g 都是双射的，则有(g •f )-1 = f –1•g –1 (2.6.5)定理2.6.8 设函数f ：A →B ，g ：B →C ，且f 和g 都是双射的，则有(g •f )-1 = f –1•g –1三、方法1．关系的矩阵表示法设集合A ={a 1 , a 2 , … , a m }，B ={b 1 , b 2 , … , b n }，(1) 若R 是从A 到B 的一个关系，则R 的关系矩阵是m ⨯n 矩阵M R =()n m j i r ⨯，其中⎪⎩⎪⎨⎧=ji j i j i b R a Rb a r 当当,0,1 ，(i =1, 2, …, m ；j =1, 2, …, n ） (2) 若R 是A 上一个关系，则R 的关系矩阵是m 阶矩阵M R =()m m j i r ⨯，其中 ⎪⎩⎪⎨⎧=ji j i j i b R a Rb a r 当当,0,1 ，(i , j =1, 2, …, m ） 2．关系的图象表示法设集合A ={a 1 , a 2 , … , a m }，B ={b 1 , b 2 , … , b n }，若R 是从A 到B 的一个关系，则用m 空心点表示a 1 , a 2 , … , a m ，用n 空心点表示b 1 , b 2 , … , b n ，这些空心点统称为结点．如果a i Rb j ，那么由结点a i 到结点b j 作一条有向弧，箭头指向b j ；如果<a i , b j >∉R ，那么结点a i 与b j 之间没有弧连结，这样的图形称为R 的关系图．若R 是A 上一个关系，如果a i Ra j (i ≠j )，有向弧的画法与上面相同；如果a i Ra i ，则画一条从结点a i 到结点 a i 的带箭头的封闭弧，称为自回路．3．复合关系的矩阵运算法设集合A ={a 1，a 2，… ，a n }，B = {b 1，b 2，… ，b n }，C = {c 1，c 2，… ，c n }，从A 到B 的二元关系R 的关系矩阵M R 是一个m 行n 列的矩阵，从B 到C 的二元关系S 的关系矩阵M S 是一个n 行p 列矩阵，则从A 到C 的复合关系R ·S 的关系矩阵S R M •是一个m 行p 列矩阵，并且S R M •= M R ⨯ M S ，其中⨯表示按布尔运算进行矩阵乘法运算．4．二元关系性质的判别法(1) 若R 是集合A 上自反的关系，则有I A ⊆R ⊆E A ；(2) 若R 是集合A 上非自反的关系，则有R ⋂I A =∅；(3) R 为集合A 上对称关系的充分必要条件是R = R -1 ；(4) R 为集合A 上反对称关系的充分必要条件是R ⋂R -1⊆ I A ；(5) R 为集合A 上传递关系的充分必要条件是R ·R ⊆R ．5．求闭包的方法(1) 设R 是非空集合A 上的二元关系，I A 是A 上的恒等关系，则r (R ) = R ⋃I A ．(2) 设R 是非空集合A 上的二元关系，则s (R ) = R ⋃R –1．(3) 设R 是非空集合A 上的二元关系，则t (R ) = ∞=⋃1i R i =R ⋃R 2⋃R 3⋃… 设R 是非空有限集合A 上的二元关系，且A 有n 个元素，则t (R ) = ni 1=⋃R i =R ⋃R 2⋃…⋃R n ． 6．等价关系的判别方法利用等价关系的关系图进行判别，即当关系R 的关系图满足：每个结点都有自回路；两个结点a ，b 之间若有从a 指向b 的弧，就有从b 指向a 的弧；若有从结点a 指向b 的弧，且有从b 指向c 的弧，就有从a 指向c 的弧时，则R 是等价关系．7．哈斯图的作图规则(1) 去掉每个结点的自回路，只用一个空心点表示集合A 的元素；(2) 适当排列结点的顺序，即对任意a ，b ∈A ，若a ≤b ，则将a 画在b 的下方；(3) 对任意a ，b ∈A ，若a <b ，且不存在c ∈A ，使得a <c <b ，则就在a ，b 之间画一条无向弧．第3章 图的基本概念与性质一、概念图——图可以用集合的形式表示，即图可以表示为一个三元组，包含结点集、边集，以及边与结点对集间的映射．如果用结点对来表示边，则图可以表示成一个由结点集与边集组成的二元组．定义3.1.1 图G 是一个三元组<V （G ），E （G ），ϕG >，其中V （G ）是一个非空的结点集（或称顶点集），E （G ）是边集，ϕG 是从边集E （G ）到结点偶对（无序偶或有序偶）集上的函数．图定义中的结点偶对可以是有序的，也可以是无序的．有向边、端点——若图中的边e 所对应的结点偶对是有序的，记为<a ，b >，则称e 是有向边（简称弧）．a ，b 分别称为弧的始点与终点，并均称为e 的端点．称e 是关联于结点a 和b 的，结点a 和结点b 是相、邻的，或称结点a 和结点b 是邻接的．无向边、端点——若图中的边e 所对应的结点偶对是无序的，记为（a ，b ），则称e 是无向边（简称棱）．a ，b 称为e 的端点．称e 是关联于结点a 和b 的，结点a 和结点b 是相、邻的，或称结点a 和结点b 是邻接的．有向图——每一条边均为有向边的图称为有向图．无向图——每一条边均为无向边的图称为无向图．底图——如果把有向图中每条有向边都看作无向边，就得一个无向图，此无向图称为原有向图的底图．底图只表示出结点间的连接关系而没有表示出连接边的方向．弧立结点——图中不与任何相邻的结点称为弧立结点．零图——全由孤立结点构成的图称为零图．自回路（环）——关联于同一结点的一条边称为自回路或环．重边（平行边）——在有向图中，两结点间（包括结点自身间）若多于一条边，则称这几条边为重边或平行边．多重图——含有重边的图称为多重图．线图——非多重图称为线图．定义3.1.2（简单图）无自回路的线图称为简单图．定义3.1.3（结点的度数、最大度、最小度）图G=<V，E>中，与V中结点v（v∈V）相关联的边数，称为该结点的度数，记作为deg(v)．记∆（G）= max{deg(v)| v∈V（G）}，δ（G）= min{deg(v)| v∈V（G）}，分别称为G=<V，E>的最大度和最小度．定义3.1.4（出度、入度、度数）在有向图中，对于任何结点v，以v为始点的边的条数称为结点v的引出次数（或出度）；以v为终点的边的条数称为结点v的引入次数（或入度）；结点v的引出次数和引入次数之和称为v的次数（或度数）．定义3.1.5（二部图）设G=〈V，E>是n阶无向图，若能将V分成两个互不相交的子集V1与V2使得G中任一边的两端点都不在同一个V i（i=1,2）中，则称G为二部图．记G=<V1,V2，E>．定义3.1.6（完全图）简单图G=<V，E>中，若每一对结点间都有边相连，则称该图为完全图．有n个结点的无向完全图记为K n．定义3.1.7（k-正则图）若无向简单图中，每个结点的度均为某个固定整数k，则称该图为k-正则图．定义3.1.8（赋权图）赋权图G是一个三重组<V，E，g>或四重组<V，E，f，g>，其中V 是结点集合，E是边的集合，f是定义在V上的函数，g是定义在E上的函数．定义3.1.9（补图）设图G=<V，E>有n个顶点，图H=<V，E’>也有同样的顶点，而E’是由n个结点的完全图的边删去E所得，则图H称为图G的补图，记为H=G，显然，G=H．定义3.1.10（子图、真子图、生成子图）设G=<V,E>和G’=<V’,E’>是两个图．(1)若V’⊆V且E’⊆E，则称G’是G的子图；(2)若V’⊂V或E’⊂E,则称G’是G的真子图；(3)若V’=V和E’ ⊆E,则称G’是G的生成子图；(4)若子图G’中没有孤立结点，G’由E’唯一确定，则称G’为由边集E’导出的子图；(5)若子图G’中，对V’中的任意两个结点u，v，当u，v∈V’时有[u，v]∈E’，则G’由V’唯一确定，则称G’为由结点集V’导出的子图．定义3.1.11(补图) 设G’=<V’，E’>是G=<V，E>的子图，若给定另外一个图G’’=<V’’，E’’>，使得E’’=E-E’，且V’’中仅包含E’’的边所关联的结点，则称G’’是子图G’的相对于G的补图．定义3.1.12(同构) 设G=〈V，E>和G’=<V’,E’>是两个图，若存在从V到V’的双射函数f，使对任意[a，b]∈E，当且仅当[f(a)，f(b)]∈E’，并且[a，b]和[f(a)，f(b)]有相同的重数，则称G 和G’是同构的．定义3.1.13(路径) 在图G=<V，E>中，设v0，v1，…，v n∈V，e1，e2,…., e n∈E，其中e i是关联于结点v i-1，v i的边，交替序列v0 e1 v1 e2…e n v n称为联结v0到v n的路径（或称路）．v0与v n 分别称为路的起点与终点，边的数目n称为路的长度．孤立点——长度为0的路定义为孤立点．简单路径——若序列中所有的边e1，e2,…., e n均互不相同，则称此路径为简单路径．基本路径——若序列中所有的点v0，v1，…，v n均互不相同，则称此路径是基本路径．回路——若v0=v n，即路径中的终点与始点相重合，则称此路径为回路．简单回路——没有相同边的回路称为简单回路．基本回路（圈）——各结点均互不相同的回路称为基本回路（或圈）．奇圈（偶圈）——长度为奇（偶）数的圈称为奇（偶）圈．定义3.2.1（可达、连通）在图G=<V,E>中，设有结点v j与v k，若从v j到v k存在任何一条路径，则称结点v k从结点v j可达，也称结点v j与v k是连通的．定义3.2.2（连通图、非连通图、分离图）若G是平凡图或G中任意两个结点都是连通的，则称G是连通图，否则称G为非连通图或分离图．定义3.2.3（连通分支） 设G =<V ,E >是图，连通关系的商集为{V 1, V 2,…, V m }，则其导出的子图G (V i)（i=1,2,…m ）称为图G 的连通分支（图），将图G 的连通分支数记作W （G ）．定义3.2.4（短程线） 设u 与v 是图G 的两个结点，若u 与v 连通，则称u 与v 之间的长度最短的路为u 与v 之间的短程线，短程线的长度可作为结点u 与v 间的距离，记作d (u ,v )，其满足下列性质：d (u ,v ) ≥ 0，u =v 时，d (u ,v ) =0 （非负性）d (u ,v ) = d (v ,u ) （对称性）d (u ,v ) + d (v ,w ) ≥ d (u ,w ) （三角不等式）若u 与v 不连通，则通常记d (u ,v ) = ∞ ．定义3.2.5（单向连通、强连通、弱连通） 在简单有向图中，如果在任何结点偶对中，至少从一个结点到另一个结点可达的，则称图G 是单向（侧）连通的；如果在任何结点偶对中，两结点对互相可达，则称图G 是强连通的；如果图的底图（在图G 中略去边的方向，得到无向图）是连通的，则称图G 是弱连通的． 定义3.2.6（极大强连通子图、极大单向连通子图、极大弱连通子图、强分图、单向分图、弱分图） 在简单有向图G =<V ，E >中，G’是G 的子图，如G’是强连通的（单向连通的，弱连通的），且没有包含G’的更大的子图G’’是强连通的（单向连通的，弱连通的），则称G’是极大强连通子图（极大单向连通子图，极大弱连通子图）又叫强分图（单向分图，弱分图）．定义3.2.7（点割集、割点） 设无向图G =<V ,E >为连通图，若有点集V 1⊂V ，使图G 删除了V 1的所有结点后，所得的子图是不连通图，而删除了V 1的任何真子集后，所得的子图是连通图，则称V 1是G 的一个点割集．若某个结点构成一个点割集，则称该结点为割点．定义3.2.8（点连通度） 若G 为无向连通图且不含Kn 为生成子图，则称k (G )=min{|V 1| ∣V 1是G 的一个点割集}为G 的点连通度（简称连通度）．规定：完全图Kn 的点连通度为n ，n ≥1．非连通图的点连通度为0．若k (G ) ≥k ，则称G 为k -连通图．定义3.2.9（边割集、割边、桥） 设无向图G =<V ,E >为连通图，若有边集E 1⊂E ，使图G 删除了E 1的所有边后，所得的子图是不连通图，而删除了E 1的任何真子集后，所得的子图是连通图，则称E 1是G 的一个边割集．若某个边构成一个边割集，则称该结点为割边（或桥）．定义3.2.10（连通度） 若G 为无向连通图，则称λ(G )=min{|E 1| ∣E 1是G 的一个边割集}为G 的边连通度．规定：非连通图的边连通度为0．若λ(G ) ≥k ，则称G 为k 边-连通图．定义3.3.1（邻接矩阵） 设G =<V ，E >是一个简单图，其中V ={v 1，v 2，…， v n }，则n 阶方阵A （G ）=（a ij ）称为G 的邻接矩阵．其中各元素⎪⎩⎪⎨⎧==ji v v v v a j i j i ij 不相邻或与相邻与01 定义3.3.2（可达性矩阵） 设G =<V ，E >是一个简单图，|V |=n ,假定G 的结点已编序，即V ={v 1，v 2，…， v n }，定义一个n ⨯n 方阵P =（p ij ）．其中⎪⎩⎪⎨⎧=不存在一条路与从至少存在一条路到从j i j i ij v v v v p 01 则称矩阵P 为图G 的可达性矩阵．最短路径的数学模型——给定一个网络N （有向或无向赋权图），u 0与v 0是N 中指点的两个顶点，在N 中找一条从u 0到v 0且权最小的路．规定N 中的一条路P 的权w (P )称为p 的长度．若N 中存在从u 到v 的路，则将N 中从u 到v 且权最小的路称为u 到v 的最短路，其长度称为u 到v 的距离，记为d N （u ,v ）．二、定理定理3.1.1（握手定理） 设G 是一个图，其结点集合为V ，边集合为E ，则∑∈=V v E v ||2)deg(定理3.1.2 图中次数为奇数的结点有偶数个．。

笛卡尔乘积及相关性质一、笛卡尔乘积1、定义令A和B为任意两个集合, 如果序偶的第一元素是A 的元素, 第二元素是B的元素;所有这样的序偶的集合称为集合A 和B的笛卡尔乘积或者直积, 记作A ⨯ B. 笛卡尔乘积的符号化表示为:A ⨯B = { <x, y> | (x∈A)∧(y∈B) }例如, 设A = { a, b }, B = { 0, 1, 2 }, 则A ⨯B = { <a, 0>, <a, 1>, <a, 2>, <b, 0>, <b, 1>, <b, 2> }B ⨯ A = { <0, a>, <0, b>, <1, a>, <1, b>, <2, a>, <2, b> }A⨯B≠B⨯A 即“⨯”是不满足交换律.笛卡尔乘积举例Jerry,Kelly,July三人去访友，可选择的汽车线路有：382，381。

每人与一个汽车线路配对，共有多少种方式？设集合A={ Jerry,Kelly,July }，集合B={ 382，381 }所有可能的配对的集合是A B。

共有6种方式.2、笛卡尔积运算性质1)．对任意集合A，根据定义有A×Φ = Φ, Φ×A = Φ2)．一般的说，笛卡尔积运算不满足交换律，即A×B≠B×A(当A≠Φ∧B≠Φ∧A≠B时)3)．笛卡尔积运算不满足结合律，即(A×B)×C≠A×(B×C) (当A≠Φ∧B≠Φ∧C≠Φ时)注意：(A×B)×C的元素是三元组，但A×(B×C)的元素不是三元组.例1 设A={a，b}，B={1，2}，C={z}(A⨯B)⨯C={〈a,1〉,〈a,2〉,〈b,1〉,〈b,2〉}⨯{z}={〈a,1,z〉,〈a,2,z〉,〈b,1,z〉,〈b,2,z〉}A⨯ ( B⨯C ) ={a, b}⨯{〈1,z〉,〈2,z〉}={〈a,〈1,z〉〉,〈a,〈2,z〉〉,〈b,〈1,z〉〉,〈b,〈2,z〉〉} 故（A⨯B）⨯C≠A⨯（B⨯C）“⨯”不满足结合律.二、笛卡尔乘积相关定理1.定理3-4.1 笛卡尔积运算对并和交运算满足分配律，即A×(B∪C) = (A×B)∪(A×C)A×(B∩C) = (A×B)∩(A×C)(A∪B)×C = (A×C)∪(B×C)(A∩B)×C = (A×C)∩(B×C)2.定理3-4.2 设A, B, C为任意集合，若C≠Φ，则：A⊆B ⇔(A⨯C⊆B⨯C) ⇔ (C⨯A⊆C⨯B)3.定理3-4.3 若A，B，C，D为四个非空集合，则A⊆C∧B⊆D ⇔ A×B⊆C×D求证：A ⨯ (B∪C) = (A ⨯ B)∪(A ⨯ C).证明任取<x, y> ∈A ⨯ (B∪C) ,<x, y>∈A ⨯ (B∪C)⇔ x∈A∧y∈(B∪C)⇔ x∈A∧(y∈B∨y∈C)⇔ (x∈A∧y∈B)∨(x∈A∧y∈C)⇔ <x, y>∈A ⨯ B∨<x, y>∈A ⨯ C⇔ <x, y>∈(A ⨯ B)∪(A ⨯ C)定理3-4.2 A, B, C是任意三个集合, C≠Φ,(1) A ⊆ B ⇔ (A⨯C⊆B⨯C)；(2) A ⊆ B ⇔ (C⨯A⊆C⨯B)(1)证明(必要性)因C非空，存在c∈C，若A⊆B，则对任意的<a,c> ∈A⨯C，其中a∈ A ⊆ B，c ∈ C,必有<a,c> ∈ B ⨯ C,所以A⨯C ⊆ B ⨯ C. (充分性)因C非空，存在c∈C，任意a∈ A ，有<a,c> ∈ A⨯C，因为A⨯C ⊆ B ⨯ C ，则必有<a,c> ∈ B ⨯ C，所以a∈ B,所以 A⊆B.同理可证（2）.定理3-4.3 若A，B，C，D为四个非空集合，则(A⊆C)∧(B⊆D) ⇔ A×B⊆C×D证：(充分性)若A⨯B ⊆ C⨯D,又A,B,C,D都不是空集, 故对任意的a∈A,b∈B,<a,b>∈ A⨯B ⊆ C⨯D.所以a∈C, b∈D, 所以 A ⊆ C, B ⊆ D.(必要性)若A ⊆C, B ⊆D,故对任意的<a,b>∈A×B ，必有a∈A⊆C, b∈B⊆D.所以<a,b> ∈ C×D，所以A×B ⊆ C×D.例2 设A , B , C , D 为任意集合，判断下列命题是否为真.（1）A ×B ＝A ×C ⇒ B=C（2）(A –B)×C = (A ×C) – (B ×C)（3）(A=B)∧(C=D) ⇒ A ×C=B ×D（4）存在集合A,使 A ⊆A ×A解:(1) 不一定为真.(3) 为真. (4) 为真. (2) 为真.等量代入.当A = Φ时,使A ⊆A ×A. 当A=Φ, B={1}, C={2,3}时，便不真.。

1.内容及范围主要来自 ppt，标签对应书本2.可能有错，仅供参考离散数学知识点说明：定义：红色表示。

定理性质：橙色表示。

公式：蓝色表示。

算法: 绿色表示页码：灰色表示数理逻辑：1.命题公式：命题，联结词(⌝，∧，∨，→，↔)，合式公式，子公式2.公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式3.范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式4.联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集5.推理理论：重言蕴含式，有效结论，P 规则，T 规则， CP 规则，推理6.谓词与量词:谓词，个体词，论域，全称量词，存在量词7.项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入8.公式语义:解释，赋值，有效的，可满足的，不可满足的9.前束范式:前束范式10.推理理论:逻辑蕴含式，有效结论，∀-规则（US），∀+规则（UG），∃-规则(ES)，∃+规则(EG), 推理集合论：1.集合: 集合, 外延性原理, ∈, ⊆, ⊂, 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关系3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R),对称闭包 s(R), 传递闭包 t(R)4.等价关系: 等价关系, 等价类, 商集, 划分5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下界6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集代数结构：1.运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺元,零元,逆元2.代数系统：代数系统，子代数，积代数，同态，同构。

笛卡尔乘积函数定义-概述说明以及解释1.引言引言部分是文章的开端，通常包括对主题的简要介绍以及文章的结构和目的。

在这篇关于笛卡尔乘积函数定义的长文中，可以这样写1.1 概述部分的内容：概述：笛卡尔乘积函数是数学中一个重要而又复杂的概念，它在不同领域有着广泛的应用。

本文将对笛卡尔乘积函数的定义、应用和特性进行深入探讨，以期能够帮助读者更好地理解和运用这一概念。

在2.1 部分，我们将详细介绍笛卡尔乘积函数的概念和相关定义；在2.2 部分，我们将阐述笛卡尔乘积函数在实际应用中的具体场景；而在2.3 部分，我们将探讨笛卡尔乘积函数的一些特性。

通过本文的阐述，读者将能够更全面地了解笛卡尔乘积函数，并体会到它在数学和现实生活中的重要性。

1.2 文章结构:本文将分为引言、正文和结论三个部分进行论述，以便全面深入地探讨笛卡尔乘积函数的定义及其相关内容。

在引言部分中，将介绍本文的概述、文章结构以及研究目的，为读者明确本文的主要内容和目标。

在正文部分，将详细阐述笛卡尔乘积函数的概念、应用及特性，分析其在数学和实际应用中的重要性和价值。

最后，在结论部分，将对笛卡尔乘积函数的重要性进行总结，展望其未来发展方向，并得出结论，为读者提供全文的逻辑收尾。

整篇文章将按照以上思路展开，以便读者全面了解笛卡尔乘积函数的相关知识和意义。

1.3 目的目的部分的内容:本文的主要目的是介绍和探讨笛卡尔乘积函数的定义、应用和特性，并对其重要性进行总结。

通过对笛卡尔乘积函数的深入理解，可以帮助读者更好地应用这一概念解决实际问题，并展望其在未来发展中的潜力和可能性。

通过本文的阐述，读者能够更全面地了解和掌握笛卡尔乘积函数的相关知识，为其进一步研究和应用打下坚实的基础。

容2.正文2.1 笛卡尔乘积函数的概念笛卡尔乘积函数是数学中常见的一种函数形式，通常用来描述两个集合之间的关系。

在集合论中，笛卡尔乘积是指由两个集合中所有可能的有序对组成的集合。

换句话说，如果A和B是两个集合，那么它们的笛卡尔乘积就是所有形式为(a, b)的有序对的集合，其中a属于A，b属于B。

离散数学一、逻辑和证明1.1命题逻辑命题：是一个可以判断真假的陈述句。

联接词：A、V、一、f「。

记住“p仅当q”意思是“如果p,则q"，即p-。

记住“q除非p”意思是“」p-q”。

会考察条件语句翻译成汉语。

构造真1.2语句翻译系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。

1.3命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。

证逻辑等价是通过p推导出q,证永真式是通过p推导出T。

(p—r)A(q-r) = (pVq)-r(p—q)V(p-r) = p—(qVr)(p—r)V(q-r) = (pAq)-r双条件命题等价式pf = (pfq) A (qfp)pf = -pfqpf Q (pAq) V(-pA-q)「(pf) = pfq1.4量词谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如V x>0P(x)。

当论域中的元素可以一一列举，那么V xP(x)就等价于P(x1)AP(x2)...A P(xn)。

同理，3 xP(x)就等价于 P(x1)VP(x2)...VP(xn)。

两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如V x(P(x)AQ(x))和(V xP(x)) A (V xQ(x))。

量词表达式的否定：「V xP(x) Q 3 x-P(x),「3 xP(x) Q V x-P(x)。

1.5量词嵌套我们采用循环的思考方法。

量词顺序的不同会影响结果。

语句到嵌套量词语句的翻译，注意论域。

嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。

1.6推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。

但有效论证不代命题和量化命题的组合使用。

二、集合、函数、序列、与矩阵2.1集合£说的是元素与集合的关系，^说的是集合与集合的关系。

离散数学知识点摘要：离散数学是计算机科学和数学的一个分支，它专注于非连续结构的研究。

本文旨在概述离散数学的核心知识点，包括集合论、逻辑、关系、函数、图论、组合数学和递归等。

1. 集合论- 集合的基本概念：集合是离散数学的基础，它是一组明确的、无重复的对象的集合。

- 集合运算：包括并集、交集、差集、补集等。

- 幂集：一个集合所有子集的集合。

- 笛卡尔积：两个集合所有可能的有序对的集合。

2. 逻辑- 命题逻辑：研究命题（声明的真值）和它们之间的关系，如合取、析取、否定等。

- 谓词逻辑：使用量词（如全称量词和存在量词）来表达更复杂的逻辑关系。

- 逻辑推理：包括直接证明、间接证明和归谬法等。

3. 关系- 关系的定义：一个集合到另一个集合的有序对的集合。

- 关系的类型：自反性、对称性和传递性等。

- 关系的闭包：在给定关系下，集合的最小闭包。

4. 函数- 函数的定义：一个集合到另一个集合的映射，每个元素有唯一的像。

- 函数的类型：单射、满射和双射。

- 复合函数：两个函数可以组合成一个新的函数。

5. 图论- 图的基本概念：由顶点（节点）和边组成的结构。

- 图的类型：无向图、有向图、连通图、树等。

- 图的算法：如最短路径、最小生成树、图的着色等。

6. 组合数学- 排列和组合：从n个不同元素中取出r个元素的不同排列和组合的数量。

- 二项式定理：描述了二项式的幂展开的系数。

- 生成函数：一种编码序列的方法，用于解决复杂的计数问题。

7. 递归- 递归定义：一个对象通过引用比自己更小的版本来定义。

- 递归函数：在计算机程序中，一个函数调用自身来解决问题。

结论：离散数学为理解和设计计算机系统提供了基础工具和理论。

它的知识点广泛应用于算法设计、数据结构、编程语言理论和数据库等领域。

掌握离散数学对于任何希望在计算机科学领域取得进展的人来说都是至关重要的。

本文提供了一个简洁的离散数学知识点概述，每个部分都直接针对一个主题，避免了不必要的背景信息和解释。

笛卡尔积和外积-概述说明以及解释1.引言1.1 概述笛卡尔积和外积是数学中重要的概念，它们在不同领域有着广泛的应用。

笛卡尔积是两个集合中所有可能的有序对组成的新集合，外积则是向量空间中常用的运算，用于描述向量之间的关系和性质。

本文将对笛卡尔积和外积进行详细介绍，包括其定义、性质、应用以及与其他数学概念的关系。

通过深入了解这两个概念，我们可以更好地理解它们在数学和实际问题中的作用，为深入研究提供基础和启发。

1.2 文章结构:本文将分为以下几个部分进行讨论:1. 引言：首先会对笛卡尔积和外积的概念进行介绍，阐述文章的目的和重要性。

2. 笛卡尔积：将详细讨论笛卡尔积的定义、应用和性质，以便读者更好地理解这一概念。

3. 外积：会探讨外积的概念、几何意义和应用，揭示外积在数学和物理领域的重要作用。

4. 结论：总结笛卡尔积和外积之间的关系，探讨它们的应用价值，并展望未来在这一领域的发展方向。

1.3 目的本文旨在深入探讨笛卡尔积和外积这两个数学概念，分析它们的定义、性质以及应用。

通过对这两个概念的详细讨论，旨在帮助读者更好地理解它们在数学和实际问题中的重要性和作用。

同时，本文还旨在总结笛卡尔积和外积之间的关系，并探讨它们在未来的发展和应用前景。

通过本文的阐述，希望读者能够对这两个概念有更深入的理解，为进一步研究和应用提供参考和启发。

2.正文2.1 笛卡尔积:2.1.1 定义:在数学上，笛卡尔积是指给定两个集合A和B，笛卡尔积是一个集合，其中的元素是由A和B中的元素对组成的有序对。

换句话说，如果A={a, b}，B={1, 2}，那么A和B的笛卡尔积是{(a, 1), (a, 2), (b, 1), (b, 2)}。

笛卡尔积可以表示为A×B。

2.1.2 应用:笛卡尔积在很多领域都有广泛的应用。

在关系数据库中，笛卡尔积可以用来进行多表连接操作。

在组合数学中，笛卡尔积可以用来求解排列组合问题。

在离散数学中，笛卡尔积可以用来定义直积和子群等概念。

笛卡儿积什么是笛卡儿积在集合论中，笛卡儿积（Cartesian product）是一种集合运算，用来将两个集合的元素按照所有可能的组合方式进行配对。

笛卡儿积的概念由法国数学家雷威·笛卡儿（René Descartes）提出，因此得名。

笛卡儿积的定义如下：设有两个集合A和B，那么它们的笛卡儿积A × B是一个新的集合，其中的元素是由A和B中的元素按照配对方式组成的有序对。

简单来说，笛卡儿积是用来描述两个集合的所有可能的元素对的集合。

笛卡儿积的表示方法在数学中，笛卡儿积可以使用不同的表示方法来进行表示。

最常见的表示方法是使用乘号来表示笛卡儿积，即A × B。

这种表示方法是非常直观和易于理解的。

另外，还可以使用括号和逗号来表示笛卡儿积，即(A, B)。

这种表示方法更类似于二维坐标系中的点的表示方法。

除了以上两种表示方法之外，还可以使用集合的形式来表示笛卡儿积，即{ (a, b) | a ∈ A, b ∈ B }。

这种表示方法更加形式化，并且便于在集合论中进行描述和推导。

举例说明为了更好地理解笛卡儿积的概念和表示方法，我们来看一个简单的例子。

设有两个集合A = {1, 2}，B = {a, b}，那么它们的笛卡儿积为：A ×B = { (1, a), (1, b), (2, a), (2, b) }以上表示了A和B集合中所有元素的所有可能组合，共有4个元素。

笛卡儿积可以用于描述两个集合之间的关系。

例如，设有两个集合分别表示坐标轴上的点的集合，我们可以使用笛卡儿积来表示这两个点之间的关系。

具体的示例请参见下面的表格：A B A × B{0, 1} {a, b} { (0, a), (0, b), (1, a), (1, b) }{2, 3} {c, d} { (2, c), (2, d), (3, c), (3, d) }{4, 5} {e, f} { (4, e), (4, f), (5, e), (5, f) }以上表格中的每一行表示了两个集合A和B中元素对的笛卡儿积。

离散数学实验报告专业班级：12级计算机本部一班姓名：鲍佳珍学号：201212201401016 实验成绩：1．【实验题目】通过编程实现求给定集合A和B的笛卡儿乘积C（C=A×B）的运算。

2．【实验目的】已知所给集合A和B，求A与B的笛卡儿乘积C（C=A×B）。

假设集合A={1,2,3,4,5},集合B={2,3,8,9,10},3、实验原理与实现过程笛卡儿集合：设A，B是两个集合，称集合A×B={<x,y>|(x∈A)∧(y∈B)}为集合A与B的笛卡儿积。

换句话说，笛卡儿乘积是以有序偶为元素组成的集合，它的定义为C={<x,y>|x∈A∧y∈B}。

所以，欲求笛卡儿乘积。

只需取尽由集合A的元素及集合B的元素，并构成序偶<ai ，bi>送入C之中即可。

算法描述：。

（1）将集合A的元素个数送入N。

（2）将集合B的元素个数送入M。

（3）1⇒i。

（4）若i>N,则结束。

（5）1⇒j。

（6）若j>M，则转（9）。

（7）<ai ，bj>⇒C。

（8）j+1⇒j，转（6）。

（9）i+1⇒i，转（4）。

4、C或C＋＋语言编程实现将实验内容与结果按实验报告格式要求填写并上传。

5. 【算法描述】1.实验原理真值表:表征逻辑事件输入和输出之间全部可能状态的表格。

列出命题公式真假值的表。

通常以1表示真，0 表示假。

命题公式的取值由组成命题公式的命题变元的取值和命题联结词决定，命题联结词的真值表给出了真假值的算法。

真值表是在逻辑中使用的一类数学表，用来确定一个表达式是否为真或有效。

2.实验过程首先是输入一个合理的式子，生成相应真值表，然后用函数运算，输出结果：要求可生成逻辑非、合取、析取、蕴含、双条件表达式的真值表，例如：输入 !a输出真值表如下：a !a0 110输入a&&b输出真值表如下：a b a&&b0 0 00 1 01 0 01 1 1输入a||b输出真值表如下：a b a||b0 0 00 1 11 0 11 1 1输入a->b输出真值表如下：a b a->b0 0 10 1 11 0 01 1 1输入a<>b (其中<>表示双条件)输出真值表如下：a b a<>b0 0 10 1 01 0 01 1 16.【源程序（带注释）】#include<stdio.h>#include<iostream.h>int main(){int i,j,m,n,k;int a[30],b[30];printf("欢迎使用");printf("请输入集合A的元素个数:");scanf("%d",&m);printf("请输入集合B的元素个数:");scanf("%d",&n);cout<<endl;for(i=0;i<m;i++){printf("请输入集合A的第%d个数:",i+1);scanf("%d",&a[i]);} //输入集合A的元素cout<<endl;for(j=0;j<n;j++){printf("请输入集合B的第%d个数:",j+1); //输入集合B的元素scanf("%d",&b[j]);}k=0;printf("c={");for(i=0;i<m;i++){for(j=0;j<n;j++){printf("<%d,%d>",a[i],b[j]);k++;}} //输出最后结果printf("}\n");return 0;}7．【实验结果与分析总结（含运行结果截图）】。

离散数学部分概念和公式总结命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。

命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。

给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。

若指定的一组值使A的值为真，则称成真赋值。

真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。

将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。

命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。

（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。

（3）若A至少存在一组赋值是成真赋值，则A是可满足式。

主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

命题的等值式：设A、B为两命题公式，若等价式A↔B是重言式，则称A与B是等值的，记作A<=>B。

约束变元和自由变元：在合式公式∀x A和∃x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。

一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A↔B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。

前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。

集合的基本运算：并、交、差、相对补和对称差运算。

笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。

二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。

命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。

命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。

给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。

若指定的一组值使A的值为真，则称成真赋值。

真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。

将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。

命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。

（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。

（3）若A至少存在一组赋值是成真赋值，则A是可满足式。

主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

命题的等值式：设A、B为两命题公式，若等价式A↔B是重言式，则称A与B是等值的，记作A<=>B。

约束变元和自由变元：在合式公式∀x A和∃x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。

一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A↔B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。

前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。

集合的基本运算：并、交、差、相对补和对称差运算。

笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。

二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。

笛卡尔乘积百科名片笛卡尔（Descartes）乘积又叫直积。

假设集合A= {a,b}，集合B={0,1,2}，则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}。

可以扩展到多个集合的情况。

类似的例子有，如果A表示某学校学生的集合，B表示该学校所有课程的集合，则A与B的笛卡尔积表示所有可能的选课情况。

目录序偶与笛卡尔积程序代码展开序偶与笛卡尔积程序代码展开名称定义序偶定义由两个元素x和y（x=y）按一定顺序排列成的二元组叫做一个有序对或序偶，记作<x，y>，其中x是它的第一元素，y是它的第二元素。

有序对<x，y>；具有以下性质：1.当x≠y时，<x，y>≠<y，x>[1].2.<x,y>=<u,v>；的充分必要条件是x=u且y=v.这些性质是二元集{x，y}所不具备的。

例如当x≠y时有{x，y}={y，x}。

原因在于有序对中的元素是有序的，而集合中的元素是无序的。

例：已知<x+2,4>=<5,2x+y>；，求x和y。

解：由有序对相等的充要条件有 x+2=5和2x+y=4 联立解得 x=3，y=-2.笛卡尔积定义设A,B为集合，用A中元素为第一元素，B中元素为第二元素构成的有序对，所有这样的有序对组成的集合叫做A与B的笛卡尔积，记作AxB.笛卡尔积的符号化为：AxB={<x,y>|x∈A∧y∈B}例如，A={a,b},B={0,1,2},则AxB={<a,o>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>,}BxA={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}笛卡尔积的运算性质1.对任意集合A，根据定义有AxΦ =Φ，Φ xA=Φ2.一般地说，笛卡尔积运算不满足交换律，即AxB≠BxA（当A≠Φ ∧B≠Φ∧A≠B时）3.笛卡尔积运算不满足结合律，即（AxB)xC≠Ax(BxC）（当A≠Φ ∧B≠Φ∧C≠Φ时)4.笛卡尔积运算对并和交运算满足分配律，即Ax(B∪C)=(AxB）∪（AxC)(B∪C)xA=(BxA）∪（CxA)Ax(B∩C)=(AxB）∩（AxC)(B∩C)xA=(BxA）∩（CxA)推导过程给定一组域D1，D2，…，Dn，这些域中可以有相同的。

笛卡尔积的计数
设a,b为集合，用a中元素为第一元素，b中元素为第二元素构成有序对，所有这样的有序对组成的集合叫做a与b的笛卡尔积，记作a x b.笛卡尔积的符号化为:a×b={(x,y)|x∈a∧y∈b}。

笛卡尔乘积是一个数学概念：笛卡尔乘积是指在数学中，两个集合 X 和 Y 的笛卡尔积，又称直积。

表示为 X × Y，第一个对象是 X 的成员而第二个对象是 Y 的所有可能有序对的其中一个成员。

笛卡尔出生于法国，毕业于普瓦捷大学，法国著名哲学家、物理学家、数学家，被黑格尔称为“近代哲学之父”。

笛卡尔对数学最重要的贡献是创立了解析几何。

在笛卡尔时代，代数还是一个比较新的学科，几何学的思维还在数学家的头脑中占有统治地位。