2013年同等学力计算机组合数学知识点小结.pdf

集合论小结集合论小结 1 集合代数的基本概念集合代数的基本概念 集合的表示法集合的表示法：列元素与谓词表示列元素与谓词表示 集合与元素的关系：属于、不属于 集合与集合的关系集合与集合的关系：包含包含、相等相等、不等不等、真包含真包含 空集与全集 文氏图 要求要求:: 属于与不属于的判断. 包含包含、相等相等、真包含的判断真包含的判断. 掌握空集及全集的概念和运算特征. 会使用文氏图会使用文氏图 2 基本计算基本计算 1. 绝对补∼、幂集P(A) 2.并并∪、交交∩、相对补补−、对称差⊕ 运算顺序： 11 类运算优先于类运算优先于22类运算类运算 2 类运算之间先后顺序由括号确定 1 类运算之间由右向左进行 注意： 先化简集合，去掉重复元素 尽量运用已知结果尽量运用已知结果：：包含的等价条件等包含的等价条件等 3 集合恒等式集合恒等式 与并与交运算有关的算律： 交换交换、、结合结合、、幂等幂等、、吸收吸收、、分配分配、、同同一、、零律零律 与补有关的算律 DMDM律律、矛盾律矛盾律、排中律排中律、双重否定律双重否定律 与对称差有关的算律 交换、结合、同一、有逆、消去律 与对称差与交有关的算律与对称差与交有关的算律 分配律 4 其他重要等式或包含关系其他重要等式或包含关系 A⊆A∪B AA∩∩BB⊆⊆AA ∅⊆∅⊆AA −BB⊆⊆AA ，((AA −BB))∪∪BB==AA∪∪BB A −B=A∩∼B AA −BB=AA ⇔AA∩BB=∅∅ A⊆B ⇔A∪B=B ⇔A∩B=A ⇔A −B=∅ ⇔∼B⊆∼A ⇔∼A∪B=E 5 基本证明基本证明 包含X⊆Y 的证明 命题演算法命题演算法、包含传递法包含传递法、反证法反证法 恒等式X=Y 的证明 命题演算法、恒等代换法、反证法 注意注意：： 先分析证明的前提和结论 注意当且仅当注意当且仅当 ““⇔⇔””必须证明两个方向必须证明两个方向 注意“⇔”和“⇒”的区别 6 关系与函数关系与函数 关系与函数的基本概念 关系与函数的基本计算关系与函数的基本计算 关系的基本证明关系的基本证明 7 关系与函数的基本概念关系与函数的基本概念 有序对与笛卡儿积 集合集合、关系与函数关系与函数 关系的表示 关系的性质关系的性质 等价关系与划分 偏序关系与偏序集偏序关系与偏序集 函数的定义与实例 函数的性质 8 有序对与笛卡儿积有序对与笛卡儿积 有序对及其性质: 有序性有序性 相等的充要条件 笛卡儿积及其性质笛卡儿积及其性质 不交换、不结合 对于交和并的分配律 x,y,y ∈A ×B ⇔x ∈A∧yy ∈B x,y ∉A ×B ⇔x ∉A∨y ∉B 计数性质计