离散数学期末3-4章复习

1、第三章 集合与关系3-1 集合的概念和表示方法定义定义(集合集合set)：把具有共同性质的一些对象汇集成一个整体，就构成一个集合，这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,表示集合用小写英文字母a,b,c,表示元素aA：表示a是A的元素，读作“a属于A”aA：表示a不是A的元素，读作“a不属于A”3-1.4 集合之间的关系集合之间的关系子集、相等、真子集；空集、全集；幂集、n元集、有限集；（1 1）子集）子集定义子集(subset)：设A、B是任意两个集合，如果A的每一个元素是B的成员，则称A为B的子集, 或说A包含于B, 或说B包含A, 记作AB，或B

2、A。AB (x)(xAxB)若A不是B的子集, 则记作ABAB (x)(xAxB)包含()的性质：1AA（自反性）证明: AA(x)(xAxA) T2若AB,且AB,则 BA（反对称性）3若AB,且BC, 则AC（传递性）证明: AB (x)(xAxB)x, xA xB (AB) xC (BC) (x)(xAxC), 即AC. （2）真子集真子集定义真子集(proper subset)如果集合A的每一个元素都属于B，但集合B至少有一个元素不属于A，则称A为B的真子集，记作AB。AB AB ABAB(x)(xAxB)(x)(xBxA)真包含()的性质1AA （反自反性）证明: A A AA AA

3、 TF F. 2若AB,则 BA （反对称性）证明: (反证) 设BA, 则AB AB AB AB (化简)BA BA BA BA所以 AB BA A=B (=定义)但是 AB AB AB AB (化简) 矛盾! 3若AB,且BC, 则AC （传递性）证明: AB AB AB AB (化简),同理 BC BC, 所以AC.假设A=C, 则BCBA, 又AB, 故A=B, 此与AB矛盾, 所以AC.所以, AC. #（3）空集空集定义空集(empty set)：没有任何元素的集合是空集,记作例如： xR|x2 +1=0定理 对任意集合A空集是它的子集也就是对任意集合A, A证明: Ax(xxA)

4、x(FxA)T. 对于每一个非空集合A，至少有两个不同的子集，A和，称为A的平凡子集。（4） 全集全集定义全集: 在一定范围内，如果所有集合均为某一集合的子集,则称这个集合是全集,记作E。E=x | P(x) P(x)，P(x)为任何谓词全集是相对的, 视情况而定, 因此不唯一。例如, 讨论(a,b)区间里的实数性质时, 可以选 E=(a,b), E=a,b), E=(a,b, E=a,b, E=(a,+), E=(-,+)等（5）幂集幂集定义幂集(power set)给定集合A，由集合A的所有子集为元素组成的集合,称为A的幂集,记作P (A)P (A)=x|xA注意: xP (A) xA例如

5、: A=a,b, P (A)=,a,b,a,b. 定理如果有限集合A有n个元素，则幂集P (A)有2n个元素。证明: 见课本第85页，利用二项式展开定理。3-2集合的运算3.1.1 定义 集合的交(intersection): 设任意两个集合A和B，由集合A和B的所有共同元素组成的集合S，称为A和B的交集，记作AB 。S=AB = x | (xA) (xB) xAB (xA) (xB)3.1.4 集合交运算的性质a) A A = A （幂等律）b) A = （零律）c) A E = A （同一律）d) A B = B A （交换律）e) (A B) C = A (B C) （结合律）因为集合交

6、运算满足结合律，故n个集合的交记为： nP=A1 A2 An = Ai i=13.2 集合的并3.3.1 定义并集(union)：设任意两个集合A和B，由所有集合A和B的元素组成的集合S，称为A和B的并集，记作AB 。 S=AB = x | (xA) (xB) xAB (xA) (xB)3.3.3 集合并运算的性质a) A A = A （幂等律）b) A = A （同一律）c) A E = E （零律）d) A B = B A （交换律）e) (A B) C = A (B C) （结合律）因为集合并运算满足结合律，故n个集合的并记为： nP=A1A2 An = Ai i=13.3 集合的补相对

7、补3.3.1 定义补集相对补集(relative complement , difference set)：属于A而不属于B的全体元素组成的集合S，称为B对于A的补集相对补集, 记作A-BS=A-B = x | (xA) (xB) 3.3.2 定义绝对补(complement)：设E为全集，对任一集合A关于E的补E-A，称为集合A的绝对补，记作 A。A=x|(xExA)集合运算的性质（集合恒等式）(1) 幂等律( idempotent laws)AA=A AA=A(2) 结合律(associative laws)(AB)C=A(BC) (AB)C=A(BC) (3) 交换律(commutati

8、ve laws)AB=BAAB=BA(4) 分配律(distributive laws)A(BC)=(AB)(AC) A(BC)=(AB)(AC) (5) 对合律(double complement law)A=A(6) 零律(dominance laws)AE=E A=(11) 吸收律(absorption laws)A(AB)=AA(AB)=A(12) 德.摩根律( DeMorgans laws)(AB)=AB(AB)=AB(13) 补交转换律(difference as intersection)A-B=AB 集合恒等式证明(方法)（1）逻辑演算法: 利用逻辑等价式和逻辑推理规则（2）集

9、合演算法: 利用集合恒等式和已知的集合结论（1）逻辑演算法(格式) 题型: A=B. 证明： x, xA (?) xB A=B 证毕. 或证明： x, xA (?) xB . 另，x, xB (?) xA . A=B证毕.题型: A B. 证明: x, xA (?) xB A B证毕.例1：分配律(证明)A(BC)=(AB)(AC)证明: x, xA(BC) xA x(BC) (定义) xA (xB xC) (定义) (xAxB)(xAxC) (命题逻辑分配律) (xAB)(xAC) (定义) x(AB)(AC) (定义) A(BC)=(AB)(AC)成立(2) 集合演算法（格式）集合演算法（

10、格式）题型: A=B. 题型: AB. 证明: A 证明: A =(?) (?) =B B A=B. # AB. #例1：吸收律(一式证明)A(AB)=A证明: A(AB) = (AE)(AB) (同一律) = A(EB) (逆用分配律) = AE (零律) = A (同一律) A(AB)=A(2) 集合演算法（格式）续 题型题型: A B 证明: AB (或AB) =(?) = A (或B) AB. # 说明说明: 化化 成成=题型题型: A=B证明: () AB () A B A = B. #说明说明: 把把=分成分成 与与 AB=AABAB=BAB集合恒等式证明(举例)1. 基本集合恒等

11、式例如：补交转换律A-B = AB 证明: x, xA-B xA xB xA xB x ABA-B = AB. 德摩根律的相对形式A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C) ？（怎么做）证明: A-(BC) = A(BC) (补交转换律) = A(BC) (德摩根律) = (AA)(BC) (幂等律) = (AB)(AC) (交换律,结合律)= (A-B)(A-C) (补交转换律). #3-4 序偶与笛卡尔积3-4.1 序偶(二元组)定义序偶ordered pair：由两个固定次序的客体 a,b组成的序列称为序偶，记作，其中a,b称为序偶的分量。 其中, a是第一元素

12、, b是第二元素, 记作也记作(a,b)。定理：序偶和 相等，当且仅当a=c 且b=d，即= (a=c)(b=d)推论: ab 3-4.2 三元组(ordered triple)定义三元组：=,c.定义 n(2)元组： =,an.定理: = ai = bi, i =1,2,n. 3-4.3 笛卡尔积(Cartesian product)及其性质 定义笛卡尔积：A和B为任意两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样序偶的集合，称为A和B的笛卡尔积或直积，记为： AB=|(xA)(yB).例1: A=,a, B=1,2,3.AB= ,.BA= ,.AA= , , , .

13、BB= , , . 3-4.4 笛卡尔积的性质：当|A|=m，|B|=n时，|AB|是多少？|AB|= mn3-4.4 笛卡尔积的性质：1. 非交换: AB BA (除非 A=B A= B=)反例: A=1, B=2.AB=, BA=.2. 非结合: (AB)C A(BC) (除非 A= B= C=)反例: A=B=C=1. (AB)C=,1, A(BC)=1,.3. 笛卡尔积分配律：（对或运算满足）（1） A(BC) = (AB)(AC)（2） A(BC) = (AB)(AC)（3） (BC)A = (BA)(CA)（4） (BC)A = (BA)(CA)对任意非空集合A,B,C，是否一定有

14、ABAC BC，试证明或举出反例。l正确l证明：因为A,B,C非空，故xA，yB，有AB AC，l故AC，因此有yC，于是有B C。定义关系：二元关系(binary relation) ，简称关系，任一序偶的集合即确定了一个二元关系R，R中任一序偶 可记为 R或xRy。不在R中的任一序偶 可记为 R或xRy例1: 在实数中关系“”可记作 “ ”=|x,y是实数且x y。例2: R1=, R1是二元关系. 例3: A=,a,1 A不是关系. A到B的二元关系也可定义关系为：设有任意两个集合A和B，直积AB的子集R称为A到B的二元关系。R是A到B的二元关系 RAB RP (AB)（幂集）若|A|=

15、m, |B|=n, 则|AB|= mn , 故|P (AB)|=2mn，即A到B不同的二元关系共有2mn个A到B的二元关系(举例)例: 设 A=a1,a2, B=b, 则A到B的二元关系共有221=4个: R1=, R2=, R3=, R4=,B到A的二元关系也有4个: R5=, R6=, R7=, R8=,。 A上的二元关系定义 A上的二元关系: 是AA的任意子集。 R是A上的二元关系 RAA RP (AA)。若|A|=m, 则|AA|=m2, 故|P (AA)|= 2 m2 ，即A上不同的二元关系共有2 m2个。A上的二元关系(举例)例1: 设 A=a1,a2, 则A上的二元关系共有16个

16、: R1 = , R2 = , R3 = , R4 = , R5 = , R6 = , , R7 = , , R8 = , ,R9 = , ,R10 = , ,R11 = , , R12 = , ，R13 = , ，R14 = , , ，R15 = , ，R16 = , 。例2:已知有限集合A，|A| =2 ，A上可以定义 ? 个二元运算，其中 8 个是可交换的， 4 个是幂等的。若|A| =3 ，|P(A)| = ? , |AA| = ? , A上有 ?个不同的二元关系，其中 ?个是反自反的， 23（8） 个既是对称的也是反对称的，A到A共有 见P149 个不同的函数，其中 ?个是双射函数。

17、 3-5.2 与二元关系有关的概念对任意集合R, 可以定义:前域定义域（domain）： dom R = x | y (xRy) 值域（range）: ran R = y | x(xRy) 域（field）: FLD R = dom R ran R定义域,值域,域(举例)例: R1=a,b, R2=, R3=,.当a,b不是序偶时, R1不是关系.dom R1=, ran R1=, FLD R1=dom R2=c,e, ran R2=d,f, FLDR2=c,d,e,fdom R3=1,3,5, ran R3=2,4,6,FLD R3=1,2,3,4,5,6. 3-5.3 一些特殊关系设A是任

18、意集合, 则可以定义A上的：空关系(empty relation): 恒等关系(identity relation): IA = | a A 全域关系(universal relation): UA = AA = | xA yA3-6 3-6 关系的性质关系的性质（1） 自反性(reflexivity)（2） 反自反性( irreflexivity)（3） 对称性(symmetry)（4） 反对称性( antisymmetry)（5） 传递性(transitivity)3-6.1自反性(reflexivity)定义（自反性reflexivity）：设R为定义在A上的二元关系，即RAA, 如果对

19、于每一个xA，有xRx (R)，则称二元关系R是自反的。 R在A上是自反的 (x)( xA xRx) R在A上是非自反的 (x)( xA R)。定理： R是自反的 IA RMR主对角线上的元素全为1GR的每个顶点处均有自环。自反性(举例)：平面上三角形的全等关系，实数集中实数的小于等于关系，幂集上的集合的相等、包含关系，命题集合上的命题的等价、蕴含关系。3-6.2反自反性(irreflexivity)定义（反自反性irreflexivity）：设RAA, 如果对于每一个xA，有R，则称二元关系R是反自反的。R在A上是反自反的 (x)(xA R )。R在A上是非反自反的 (x)( xA xRx)

20、注意：非自反不一定是反自反的。即存在有关系既不是自反的也不是反自反的。3-6.3对称性(symmetry)定义（对称性symmetry）：设RAA, 如果对于每个x,yA,每当 xRy，就有 yRx，则称集合A上的关系R是对称的。R在A上对称 (x)(y)(xAyA xRyyRx).R非对称 (x)(y)(xAyA xRyyRx)3-6.4 反对称性(antisymmetry)定义（反对称性antisymmetry）：设RAA,如果对于每个x,yA,每当 xRy和yRx，必有x=y，则称集合A上的关系R是反对称的。R是反对称的 (x)(y)(xAyA xRy yRx x=y )(x)(y)(x

21、AyA xy xRy yRx ).R非反对称 (x)(y)(xA yA xRy yRx xy)3-6.5传递性(transitivity)定义（传递性transitivity）：设RAA, 如果对于任意的x,y,zA, 每当xRy， yRz 时就有xRz ，称关系R在A上是传递的。 R在A上是传递的 (x)(y)(z)(xAyAzAxRy yRz xRz)R非传递 (x)(y)(z)(xAyAzAxRy yRzxRz)。判断以下关系所具有的性质。A=a,b,cR1=,R2=,R3=,R4=,R5=,R6=,R7 =解答：R1=,反对称,传递R2=,反对称R3=,自反,对称,传递R4=,对称R5

22、=,自反,反对称,传递R6=,R6= （空关系） 反自反，对称，传递，反对称. 设A=1,5,8，A上的关系R=(1,1),(1,5),(5,1),(5,5),(8,8),(8,5), (5,8)， R具备哪些性质（自反性、反自反性、对称性、反对称性、传递性） ？ 3-7 复合关系和逆关系3-7.1复合关系复合关系定义定义1复合复合 (合成合成)(composite)关系关系:设设R为为X到到Y的关系，的关系，S为从为从Y到到Z上的关系，上的关系，则则RS称为称为R和和S的复合关系，表示为：的复合关系，表示为：RS= |xXzZ(y)(yYRS).例题：设关系f=(1,5),(3,8) ，g=

23、(8,5),(5,3) ，则关系fog= (1,3),(3,5) ，关系gof= (5,8) 。 3-7.23-7.2逆关系逆关系定义定义2逆逆(inverse)关系关系 : 设R是X到Y的二元关系，则从Y到X的二元关系Rc定义为： Rc = |R.整数集合上的“”关系的逆关系是“”关系。人群中的父子关系的逆关系是子父关系。容易看出(Rc) c=R例1: 设 R= , , S= , .求: (1)Rc ，Sc. (2) RS, SR解: (1) Rc = , Sc = ,. (2) RS= , SR=. 由复合关系满足结合律，可以把关系R本身所组成的复合关系写成：RR， RRR， RRR(m个

24、)，分别记作 R(2)， R(3)， ， R(m)。可以证明复合关系不满足交换律。R1R2 R2R1证明: 若关系R是对称的, 则Rk(k1, kN)也是对称的。 证明: 对于任意的(a, b) Rk, 存在(a, c1) R, (c1, c2) R, , (ck-1, b) R。由R是对称的, (b, ck-1) R, (ck-1, ck-2) R, , (c2, c1) R, (c1, a) R 。所以(b, a) Rk , 即Rk是对称的。3-9 3-9 集合的划分和覆盖集合的划分和覆盖定义定义3-9.1覆盖覆盖cover：若把一个集合若把一个集合A分分成若干个叫做分块的非空子集，使得成

25、若干个叫做分块的非空子集，使得A中每个中每个元素至少属于一个分块，这些分块的全体叫元素至少属于一个分块，这些分块的全体叫做做A的一个覆盖。的一个覆盖。即：设即：设A为非空集合，为非空集合，S=S1,S2 ,Sm，其中其中Si A，Si(i=1,2, ,m) 且且S1 S2 SmA，则集合则集合S称作集合称作集合A的覆盖。的覆盖。定义定义3-9.2划分划分partition ：给定集合给定集合A的一个覆盖的一个覆盖S，若，若A中的每个元素属于且仅中的每个元素属于且仅属于属于S的一个分块，则的一个分块，则S称作是称作是A的一个划的一个划分。分。即：若即：若S是集合是集合A的覆盖，的覆盖，且满足且满

26、足SiSj=， （这里（这里ij），），则称则称S是是A的划分。的划分。定义定义3-9.3交叉划分交叉划分：若若A1,A2, ,Ar与与B1,B2, ,Bs是同一集合是同一集合A的两种划分，的两种划分，则其中所有则其中所有AiBj组成的非空集合，称为原组成的非空集合，称为原来两种划分的交叉划分。来两种划分的交叉划分。定义定义3-9.4加细加细：给定给定X集合的任意两集合的任意两个划分个划分A1,A2, ,Ar和和B1,B2, ,Bs，若，若对于每一个对于每一个Aj，均有，均有Bk使使Aj Bk，则称，则称A1,A2, ,Ar为为B1,B2, ,Bs的加细。的加细。定理定理3-9.1:设设A1,

27、A2, ,Ar与与B1,B2, ,Bs是同一集合是同一集合X的两种划分，则其交叉划分仍是的两种划分，则其交叉划分仍是原集合的一种划分。原集合的一种划分。定理定理3-9.2: 任何两种划分的交叉划分，任何两种划分的交叉划分，都是原来各划分的一种加细。都是原来各划分的一种加细。证明见书证明见书130页。页。3-10 等价关系与等价类3-10.1 等价关系定义3-10.1等价关系Equivalence Relations：设A ，R A A，若R是自反的、对称的和传递的，则称R为A上的等价关系。3-10.2 等价类定义3-10.2等价类Equivalence classes：设R是非空集合A上的等价

28、关系，对任意的aA，定义 aR = xA | aRx，称为a关于R的等价类，简称a的等价类，在不混淆的情况下记为a。显然aR非空，因为a aR 定理3-10.2：非空集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。集合A上有多少个不同的等价关系，就有多少种不同的划分。 是否正确？3-12 序关系在这一节中，我们将介绍以下一些序关系：偏序关系全序关系良序关系拟序关系*3-13.1 偏序关系定义定义3-13.1偏偏序关系序关系 (partial order) : 设设A ，R A A，若，若R是自反的、反对是自反的、反对称的和传递的，则称称的和传递的，则称R是是A上的偏序关系。上的

29、偏序关系。常将偏序关系常将偏序关系R记为记为“”，并将，并将 xRy记为记为xy。序偶。序偶称为偏序集称为偏序集(partially ordered set, poset) 。定义定义3-13.2盖住盖住:设设是偏序集，若有是偏序集，若有x, y A，x y ，且，且x y，且不存在其它元素，且不存在其它元素z， z A，使得，使得x z z y，则称元素，则称元素y盖住元素盖住元素x。并且记盖住集为：并且记盖住集为：COVA=|x,y A ;y盖住盖住x。例例2 2：求盖住集。求盖住集。P140 例例2COVA=, , 。例例3 3： P140 例例3COVA=, 。3-13.2 哈斯图根据

30、上述定义，可以简化偏序关系的关系图根据上述定义，可以简化偏序关系的关系图得到哈斯图得到哈斯图(Hasse diagram)，具体画法如下：，具体画法如下：用小圆圈代表元素；用小圆圈代表元素； 若若x y，x y，将代表，将代表y的小圆圈放在代的小圆圈放在代表表x的小圆圈之上，的小圆圈之上，1.如果如果 COVCOVA A，则，则在在y与与x之间用直线连之间用直线连接。接。列出集合a,b,c的所有子集，画出各子集之间包含关系的哈斯图。 4-1 4-1 函数的概念函数的概念定义4-1.1：函数（function）集合之间的函数(function，或说映射mapping)：设X和Y是任意两个集合，而

31、f 是X到Y的一个关系，如果对于每一个xX,有唯一的yY，使得f，称关系f 为函数，记作f : XY或 X Y如果f，则x称为自变元（原象），y称为在f 作用下x的象(image)，f 亦可记作y=f(x)，且记 f(X)= f(x)| xX f从函数的定义可以知道它与关系有别于如下两点：a：函数的定义域是X，而不能是X的某个真子集。b：一个x只能对应于唯一的一个y。即如果f(x)=y 且 f(x)=z，那么y=z。从X到Y的函数往往也叫做从X到Y的映射。 函数f : XY的前域就是函数的定义域(domain) dom f 定义为：dom f = x | 存在某个yB使得f =X函数f : XY的值域(range) ran f 定义为：ran f = y | (x)(xA)f Yf 的值域有时也记作Rf集合Y称为f 的共域，ran f 称为函数的像集合。 有限集X、Y上函数的个数设X和Y都为有限集，|X|=m，|Y|=n(1) 从X到Y任意一个函数的定义域是X，在这些函数中，每一个函数恰有m个序偶。(2) 任何元素xX，可以有Y的n个元素中的任何一个作为它的像，故共有nm个不同的函数。例如n=2，m=3，故应有23个不同的函数。今后我们用符号YX表示从X到Y的所有函数的集合，甚至当X和Y是无限集时，也用这个符号。定义定义4-1.4：f 是是满射满射( surjectio