离散数学课本定义和定理

离散数学课本知识点第1章集合1.1 集合的基本概念1. 集合、元（元素）、有限集、无限集、空集2. 表示集合的方法：列举法、描述法3. 定义1.1.1（子集）：给定集合A和B，如果集合A的任何一个元都是集合B中的元，则称集合A包含于B或B包含A，记为AB或BA，并称A为B的一个子集。如果集合A和B满足AB，但B中有元不属于A，则称集合A真包含于B，记为AB，并且称A为B的一个真子集。4. 定义1.1.2（幂集）：给定集合A，以A的所有子集为元构成的一个集合，这个集合称为A的幂集，记为 A 或 2A1.2 集合的运算定义1.2.1（并集）：设A和B是两个集合，则包含A和B的所有元，但不包含其他元的集合，称为A和B的并集，记为AB.定义1.2.2（交集）：A和B是两个集合，包含A和B的所有公共元，但不包含其他元的集合，称为A和B的交集，记为AB.定义1.2.3（不相交）：A和B是两个集合，如果它们满足AB=，则称集合A和B是不相交的。定义1.2.4（差集）：A和B是两个集合，属于A而不属于B的所有元构成集合，称为A和B的差集，记为A-B.定义1.2.5（补集）：若A是空间E的集合，则E中所有不属于A的元构成的集合称为A的补集，记为A'.定义1.2.6（对称差）：A和B是两个集合，则定义A和B的对称差AB为AB=A-BB-A1.3 包含排斥原理定理1.3.1 设A1,A2为有限集，其元素个数分别为A1，A2则 A1A1=A1+A2-A1A2定理1.3.2 设A1,A2,A3为有限集，其元素个数分别为A1,A2,A3，则A1A2A3=A1+A2+A3-A1A2-A1A3-A2A3+A1A2A3定理1.3.3 设A1,A2,An为有限集，则A1A2An=i=1nAi-1i<jnAiAj+1i<j<knAiAjAk+-1n-1A1A2An重要例题 P11 例1.3.1第2章 二元关系2.1 关系定义2.1.1（序偶）：若 x 和 y 是两个元，将它们按前后顺序排列，记为x,y，则y,x成为一个序偶。 对于序偶x,y和a,b，当且仅当x=a并且y=b时，才称x,y和a,b相等，记为x,y=a,b定义2.1.2（有序n元组）：若x1,x2,xn是个元，将它们按前后顺序排列，记为x1,x2,xn，则成为一个有序n元组（简称n元组）。定义2.1.3（直接积）：A和B是两个集合，则所有序偶x,y的集合，称为和的直接积（或笛卡尔积），记为A×B.定义2.1.4（直接积）：设A1,A2,An是n个集合，xiAi,i=1,2,n ，则所有n元组x1,x2,xn的集合，称为A1,A2,An的笛卡尔积（或直接积），记为A1×A2××An.定义2.1.5（二元关系） 若A和B是两个集合，则A×B的任何子集都定义了一个二元关系，称为A×B上的二元关系。如果A=B，则称为A上的二元关系。定义2.1.5（恒等关系）：设Ix是X上的二元关系，Ix=x,x|xX，则称Ix是X上的恒等关系。定义2.1.7（定义域、值域）：若S是一个二元关系，则称DS=x|存在y,使x,yS为S的定义域。RS=y|存在x,使x,yS为S的值域。定义2.1.8（自反）：设 R 是集合上 X 的关系，若对于任何 xX，都有 xRx 即x,xR则称R关系是自反的。定义2.1.9（反自反）：设R 是集合上 X 的关系，若对于任何xX，都满足x,xR,即xRx对任何xX都不成立，则称关系R是反自反的。定义2.1.10（对称）：设R 是集合上 X 的关系，若对于任何x,yX，只要xRy,就有yRx,那么称关系R是对称的。定义2.1.11（反对称）：设R 是集合上 X 的关系，若对于任何x,yX，只要xRy并且yRx时,就有x=y，那么称关系R是对称的。定义2.1.11（传递） 设R 是集合上 X 的关系，若对于任何x,yX，只要xRy并且yRz时，就有xRz，则称关系R是传递的。定理2.1.1 设R 是集合上 X 的关系，若R是反自反的和传递的，则R是反对称的。2.2 关系矩阵和关系图定义 无 定理 无2.3 关系的运算定义2.3.1（连接）：设 R 为X×Y上的关系，S为Y×Z上的关系，则定义关系RS=x,z|存在y,使x,yR且y,zSRS称为关系R和S的连接或复合，有时也记为RS.定义2.3.2（逆关系）：设 R 为X×Y上的关系，则定义R的逆关系为R-1为Y×X上的关系：R-1=y,x|y,xR.定理2.3.1 设R和S都是X×Y上的二元关系，则下列各式成立（1）R-1-1=R（2）RS-1=R-1S-1（3）RS-1=R-1S-1（4）R'-1=R-1'（5）R-S-1=R-1-S-1定理2.3.2设R为X×Y上的关系，S为Y×Z上的关系，则RS-1=S-1R-12.4 闭包运算定义2.4.1（自反闭包）： 设R是集合X上的二元关系，如果R1是包含R的最小自反关系，则称R1是关系R的自反闭包，记为rR.定义2.4.2（对称闭包）： 设R是集合X上的二元关系，如果R1是包含R的最小对称关系，则称R1是关系R的对称闭包，记为sR.定义2.4.3（传递闭包）： 设R是集合X上的二元关系，如果R1是包含R的最小传递关系，则称R1是关系R的传递闭包，记为tR或R+.定理2.4.1 设R是集合X上的二元关系，则（1） R是自反的，当且仅当rR=R.（2） R是对称的，当且仅当rR=R.（3） R是传递的，当且仅当tR=R.定理2.4.2 设R是集合X上的二元关系，则rR=RIx. “R恒等关系”定理2.4.3 设R是集合X上的二元关系，则sR=RR-1. “R逆关系”定理2.4.4 设R是集合X上的二元关系，则R+=RR2R3=i=1Ri.“R幂集”定理2.4.5 设X是一个n元集，R是X上的二元关系，则存在一个正整数kn，使得R+=RR2R3Rk.2.5 等价关系和相容关系定义2.5.1（覆盖、划分）： S是一个集合，AiS,i=1,2,n,如果i=1nAi=S，则称a=A1,A2,An是S的一个覆盖。如果i=1nAi=S，并且AiAji,j=1,2,n,ij，则称a是S的一个划分，a中的元称为S的划分块。定义2.5.2（等价关系）：设R是X上的一个关系，如果R具有自反性、对称性和传递性三个性质，则称R是一个等价关系。设R是等价关系，若xRy成立，则称x等价于y.定义2.5.3（等价类）：设R是X上的一个等价关系，则对任何xX，令xR=y|yX且xRy，称xR为x关于R的等价类，简称为x的等价类，xR也可以简记为x.定义2.5.4（同余）：对于整数a,b和正整数m,有关系式：a=mk1+r10r1<mb=mk2+r20r2<m如果r1=r2，则称a,b对于模m同余的，记作abmod m定义2.5.5（商集）：设R是X上的一个等价关系，由R引出的等价类组成的集合x|xX称为集合X上由关系R产生的商集，记为X/R.“等价类的集合”定理2.5.1若是 X 上的一个等价关系，则由R可以产生唯一的一个对 X 的划分。“商集”定义2.5.6（相容关系）：设R是X上的一个关系，如果R是自反的和对称的，则称R是一个相容关系。相容关系可以记为.所有的等价关系都是相容关系，但相容关系却不一定是等价关系。定义2.5.7（最大相容块）：设X是一个集合，是定义在X上的相容关系。如果AX, A中的任何两个元都有关系，而x-A的每一个元都不能和A中所有元具有关系，则称A是X的一个最大相容块。2.6 偏序关系定义2.6.1（偏序关系）：R是定义在集合X上的一个关系，如果它具有自反性、反对称性和传递性，则称R是X上的一个偏序关系，简称为一个偏序，记为.更一般地讲，若X是一个集合，在X上定义了一个偏序，则我们用符号 X, 来表示它，并称X,是一个偏序集。定义2.6.2（全序/链）：X,是一个偏序集，对任何x,yX，如果xy或yx这两者中至少有一个必须成立，则称X,是一个全序集或链，而称是X上的一个全序或线性序。定义2.6.3（盖住）：X,是一个偏序集，x,yX，若xy，并且不存在zX,使xz并且zy，则称y盖住x.“紧挨着”定义2.6.4（最小元、最大元）：X,是一个偏序集，如果X中存在有元y，对任何xX都满足yx，则称y是X,的最小元。如果X中存在有元z，对任何xX都满足xz，则称z是X,的最大元。定义2.6.5（极小元、极大元）：X,是一个偏序集，如果yX,而X中不存在元x，使x<y,则称y是X,的极小元。如果zX,而X中不存在元x,使z<x,则称z是X,的极大元。定义2.6.6（上界、下界、上确界、下确界）：X,是一个偏序集，AX,x,yX,如果对于所有的aA,都有ax,则称x是A的一个上界。如果对于所有的aA,都有ya,则称y是A的一个下界。如果x是A的一个上界，对于A的任一上界z,都有xz,则称x是A的最小上界（上确界）. 如果y是A的一个上界，对于A的任一上界w,都有wy,则称y是A的最大下界（下确界）.定义2.6.5（良序集）：设X,是一个偏序集，对于偏序，如果X的每个非空子集都具有最小元，则称X,是一个良序集，而称是X上的一个良序。每个良序集都是全序集。第3章 函数和运算3.1 函数定义3.1.1（映射、象）： 关系f定义在X×Y上，如果对于每一个xX，都有唯一的一个yY，使x,yf，则称f是从X到Y的一个函数（或映射），记为f:XY.x称为函数 f 的变元，y称为变元x在f下的值（或象），记为fx.注意：（1） 定义域Df=X，而不是DfX.（2） 每一个x，有唯一的yY，使x,yf.多值函数不符合定义（3） 值域RfY.定义3.1.2（受限、扩展）： 若f是从X到Y的一个函数，AX，则fA×Y也是一个函数，它定义于A到Y，我们称它是f在A上的受限。如果f是函数g的一个受限，则称g是f的一个扩展。定义3.1.3（映上、映内、一对一、一一对应）： 若f:XY，则f的值域Rf=Y时，称函数f是映上的（或满射）。如果f的值域RfY时，则称函数f是映内的。如果x1,x2X,x1x2，则有fx1fx2,则称f是一对一的（单射）（即fx1=fx2时，有x1=x2）.如果f映上的，又是一对一的，则称f是一一对应的（或双射）。定义3.1.4（复合运算）：若f:XY,g:YZ，则定义f和g的复合运算fg为：fg=x,z|存在yY,使y=fx,且z=gy即fgx=gfx.注：逆函数f-1若要存在需要满足以下条件：（1）函数f是映上的（2）函数f必须是一对一的定义3.1.5（恒等函数） 函数Ix=x,x|xX称为恒等函数。定理3.1.1 f:XY,g:YZ，则g=f-1的充分必要条件是gf=Iy，并且fg=Ix3.2 运算定义3.2.1（二目运算）： 若X是一个集合，f是从X×X到X的一个映射（函数），则称f为一个二目运算。一般地，若f是从Xn到X的一个映射（n是正整数），则称f是一个n目运算。运算的封闭：运算的结果总是集合X中的一个元，因