离散数学总结集合论.ppt

离散数学集合论集合论的知识点集合A上的关系f:AB单射f:AB满射f:AB双射f:AB关系f元素为有序对或者空集domf=A单值从A到B的关系fdomfAranfB函数f单值性A=Bdomf=AranfB一对一ranf=BIA,EA,DA,LA,,R特殊关系实例IA,特征函数B,自然映射g单调函数集合论-集合代数掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示。BAx(x∈B→x∈A) BAx(xBxA)P(A)={x|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={x|z(z∈A∧x∈z)}元素的元素∩A={x|z(z∈A→x∈z)}元素的公共元素……掌握基本的集合恒等式(等幂律、交换律、结合律、分配律、德·摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律)。运用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式 。集合恒等式的证明方法逻辑演算法 利用逻辑等值式和推理规则集合演算法 利用集合恒等式和已知结论逻辑演算法的格式题目:A=B证明:x, x∈A …… x∈B 所以A=B或证AB∧AB题目:AB证明:x, x∈A …… x∈B 所以AB集合演算法的格式题目:A=B证明:A =…… =B 所以A=B题目:AB证明:A …… B 所以AB集合论-二元关系有序对及卡氏积的概念及卡氏积的性质 二元关系,A到B的二元关系,A上的二元关系,关系的定义域和值域,关系的逆,关系的合成等概念,掌握关系的定义域、值域、逆、合成等的主要性质 集合A上的二元关系的主要性质(自反性,反自反性,对称性,反对称性,传递性)的定义及判别法,对某些关系证明它们有或没有中的性质A上二元关系的n次幂的定义及主要性质等价关系、等价类、商集、划分等概念,以及等价关系与划分之间的对应偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念关系性质的特点自反性反自反性对称性反对称性传递性定义x∈A→<x,x>∈Rx∈A→<x,x>R<x,y>∈R→<y,x>∈R<x,y>∈R∧<y,x>∈R→x=y<x,y>∈R∧<y,z>∈R→<x,z>集合表达式IARR∩IA=R=R-1R∩R-1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij=1,且i≠j,则rji=0对M2中1所在位置,M中相应的位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,一定是一对方向相反的边(无单边)如果两点之间有边,一定是一条有向边(无双向边)如果顶点xi到xj有边,xj到xk有边,则从xi到xk也有边关系性质的证明通常的证明方法是利用定义证明。R在A上自反 任取x,有 x∈A…………………………………<x,x>∈RR在A上对称 任取<x,y>,有 <x,y>∈R……………………………<y,x>∈R R在A上反对称 任取<x,y>,有 <x,y>∈R∧<y,x>∈R……………x=yR在A上传递 任取<x,y>,<y,z>,有 <x,y>∈R∧<y,z>∈R……………<x,z>∈R集合论-函数掌握函数、A到B的函数、集合在函数下的像、集合在函数下的完全原像的概念及表示法;当A与B都是有穷集时,会求A到B的函数的个数。 掌握A到B的函数是单射、满射、和双射的定义及证明方法。 掌握常函数、恒等函数、单调函数、特征函数、自然映射等概念。 掌握合成函数的主要性质和求合成函数的方法。 掌握反函数的概念及主要性质。