离散数学(杨圣洪版)-第3章-复习总结.ppt

离散数学 第三章 复习与总结 第三章 复习与总结 基本概念 计算方法 基本概念 集合：子集、幂集、集合的运算(交叉并补) 性质： 幂等律 A?A=A， A?A=A 结合律 A?B?C= A?(B?C)= (A?B)?C A?B?C= A ?(B ? C)= (A?B)?C 交换律 A?B=B?A A?B=B?A 分配律 A?(B?C)=(A?B)?(A?C) A?(B?C)=(A?B)?(A?C) 同一/零律 A??=A A ? ?= ? 排中/矛盾律 A??A=E A ? ?A= ? 吸收律(大吃小) A?(B?A)=A, A?(B?A)=A 德摩律 ?(A?B)= ?A??B ?(A?B)= ?A ? ?B 双重否定 ? ?A=A 基本概念 序偶 定义3.4.1 将具有次序的两对象写在一块，称为序偶即有秩序的二个对象，记为对象1，对象2或x,y。 三元组、n元组 定义3.4.3 如果x,y是序偶，且x,y,z也是一个序偶，则称x,y,z为三元组。 定义3.4.4 如果x1,x2,…,xn-1是n-1 元组，而x1,x2,…,xn-1,xn是序偶，则称为x1,x2,…,xn-1,xn为n元组。 笛卡尔积 关系 将笛卡尔积中前后两个元素之间存在某种关系的序偶检出来,便得到一个关系。 基本概念 关系矩阵、关系图 基本概念 关系复合 设F,G为二元关系,G对F的右复合记为F?G,定义 F?G={x,y|?t( x,t?F,t,y?G)} 乘法是合取?，加法是析取?， 复合性质： (1)结合律 (P?R)?S=P?(R?S)； (2)复合的逆 (P?R)-1= R-1?P-1； (3)不满足交换率； 基本概念 关系的性质与分类 自反关系:?x?A ? x,x?R?IA?R 反自反关系:?x?A ? x,x?R?IA?R=? 对称关系:x,y?R ? y,x?R? R=R-1 反对称关系:x,y?R,y,x?R?x=y x,y?R且x?y ?y,x?R ? R?R-1?IA 传递关系:x,y?R,y,z?R?x,z?R?R2?R 自反:主对角线均为1 反自反:主对角线均为0 对称:M=MT。 反对称：M?MT后只有主对角非0 传递:R2?R即M2?M 基本概念 等价关系 自反、对称、可传递的关系称为等价关系。 等价类 彼此有等价关系的元素的集合,称为等价类. 如：{1、4、7}，{2、5、8}，{3、6} 商集 设R?A?A，R是等价关系，A0,A1,…,Ak是基于R得到的等价类，则称集合{A0,A1,…,Ak}为A关于R的商集，记为A/R。 如：A= {1、2、3、4、5、6、7、8}，R={ x,y|x-y=3k} 划分 若A=A0?A1 ?…?Ak, 且不相交,则称A的划分。 基本概念 偏序关系 自反、反对称、可传递的关系。广义的“小于等于”关系，记为?。 全序(线序): ?x,y?A ，x与y都可比。 偏序集A, ?：集合A、偏序关系。 如:A={?,{1,2}} R1={x,y:x?y,x?A,y?A}, A, R1 A={?,{1},{2},{1,2}} R2={x,y:x?y,x?A,y?A}, A, R2 哈斯图 去掉箭头; 去掉自旋箭头; 去掉复合边; 盖住: x?A,y?A,xy, ??z?A,使得xzy,则称y盖住x. 基本概念 最大元、最小元、极大元、极小元 设A,R是偏序集，B?A, y0?B, 若?x?B,均有x,y0?R，则y0是B的最大元。 极大元:不存在x使y0,x?R. 上界、下界、上确界、下确界 在偏序集A,R中，B?A，y?A，若任意x?B都有x,y?R，则称y是B的上界。 在偏序集A,R中，B?A，设C为B的所有上界元的集合，若C中有最小元则该最小元称为B的上确界 第三章 复习与总结 基本概念 计算方法 笛卡尔积与复合的算法：乘法是合取?，加法是析取?， 算法： 性质： (1)结合律 (P?R)?S=P?(R?S) (2)复合的逆