离散数学CH01_集合论与关系代数.ppt

1.1集合的基本概念和运算 集合的基本概念 集合的基本运算 1.2 集合中元素的计数 1.3 集合的笛卡儿积与二元关系 1.4 关系的基本运算 1.5 关系的性质 1.6 关系的特殊运算——逆、闭包、复合 1.7 等价关系 1.8 相容关系 1.9 偏序关系 1.10 函数的定义和性质 1.11 函数的复合和反函数 在某一非空全集中，有这样一个确定的集合，这个集合中“只有不属于这个集合的元素”。 集合论矛盾的出现，形成第三次数学危机，动摇了整个数学的基础, 导致罗素类型论和策梅罗系统的诞生 1897年3月28日，布拉里·福蒂第一个提出了集合论中存在悖论，罗素悖论的提出更是震动了整个数学界，造成了第三次数学危机。 1908年，策墨罗采用了把集合论公理化的方法来消除悖论，随后又经过多人的努力，公理化集合论已成为数学中发展最为迅速的一个分支。 集合的定义与表示 集合与元素 集合之间的关系 空集 全集 幂集 集合的运算：并、交、补、差、对称差 元素与集合的关系：隶属关系 属于?，不属于 ? 实例：A={ x|x?R?x2-1=0}, A={-1,1} 1?A, 2?A 注意：对于任何集合 A 和元素 x (可以是集合)，x?A和 x?A 两者成立其一，且仅成立其一. 例 1.1 A={ a, {b,c}, d, {{d}} } {b,c}?A b?A {{d}}?A {d}?A d?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? B且 A ? B 不真包含 A?B 思考： ? 和 ? 的定义 注意 ? 和 ? 是不同层次的问题. 空集 ? 不含任何元素的集合 实例 {x | x2+1=0且x?R} 就是空集 命题 空集是任何集合的子集 ??A ? ?x (x???x?A) ?T 推论 空集是惟一的. 证 假设存在?1和?2，则?1??2 且?1??2， 因此?1=?2 全集 E 相对性:在给定问题中，全集包含任何集合，即 ?A (A?E ) 定义 P(A) = { x | x?A } 实例 （1）P(?) = ？ （2）P({?}) = ？ （3）P({1,{2,3}})=？ （4）设A= { a,b,c } ，则P (A)=？ 【实例解答】 （1）P(?) = {?}， （2）P({?}) = {?,{?}} （3）P({1,{2,3}})={?,{1},{{2,3}},{1,{2,3}}} （4）设A= { a,b,c } ，则P (A)= { ?, { a }, { b }, { c }, { a,b }, { a,c }, { b,c }, { a,b,c } } 【思考题】 如果 |A| = n，则 |P(A)| = ？ 【思考题解答】 证明：如果 |A| = n，则 |P(A)| = 2n 集合基本运算的定义 ? ? ? ? ? 文氏图（John Venn） 例题 集合运算的算律 集合包含或恒等式的证明 并 A?B = { x | x?A 或 x?B } 交 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 = E?A 运算顺序： ?和幂集优先，其他由括号确定 并和交运算可以推广到有穷个集合上，即 A1?A2?…An= {x | x?A1?x?A2?…?x?An} A1?A2?…An= {x | x?A1?x?A2?…?x?An} 某些重要结果 ??A?B?A A?B ? A?B=?（后面证明） A?B=? ? A?B=A 证明 X?Y 命题演算法 包含传递法 等价条件法 反证法 并交运算法 例1 证明A?B ? P(A)?P(B) 任取x x?P(A) ? x?A