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

第三章 集合与关系 3-1 集合的概念和表示方法 定义(集合set)：把具有共同性质的一些对象汇集成一个整体，就构成一个集合，这些对象称为元素(element)或成员(member) 用大写英文字母A,B,C,…表示集合 用小写英文字母a,b,c,…表示元素 a?A：表示a是A的元素，读作“a属于A” a?A：表示a不是A的元素，读作“a不属于A” 3-1.4 集合之间的关系 子集、相等、真子集； 空集、全集； 幂集、n元集、有限集； （1）子集 [定义]　子集(subset)： 设A、B是任意两个集合，如果A的每一个元素是B的成员，则称A为B的子集, 或说A包含于B, 或说B包含A, 记作A?B，或B?A。 A?B ? (?x)(x?A?x?B) 若A不是B的子集, 则记作A?B A?B ? (?x)(x?A?x?B) 包含(?)的性质： 1．A?A（自反性） 证明: A?A?(?x)(x?A?x?A) ?T 2．若A?B,且A?B,则 B?A（反对称性） 3．若A?B,且B?C, 则A?C（传递性） 证明: A?B ? (?x)(x?A?x?B) ?x, x?A ? x?B (A?B) ? x?C (B?C) ? (?x)(x?A?x?C), 即A?C. （2）真子集 [定义]　真子集(proper subset) 如果集合A的每一个元素都属于B，但集合B至少有一个元素不属于A，则称A为B的真子集，记作A?B。 A?B ? A?B ? A?B A?B?(?x)(x?A?x?B)?(?x)(x?B?x?A) ?真包含(?)的性质 1．A?A （反自反性） 证明: A ? A? A?A ? A?A ? T?F ? F. 2．若A?B,则 B?A （反对称性） 证明: (反证) 设B?A, 则 A?B ? A?B ? A?B ? A?B (化简) B?A ? B?A ? B?A ? B?A 所以 A?B ? B?A ? A=B (=定义) 但是 A?B ? A?B ? A?B ? A?B (化简) 矛盾! 3．若A?B,且B?C, 则A?C （传递性） 证明: A?B ? A?B ? A?B ? A?B (化简), 同理 B?C ? B?C, 所以A?C. 假设A=C, 则B?C?B?A, 又A?B, 故A=B, 此与A?B矛盾, 所以A?C. 所以, A?C. # （3）空集 [定义]　空集(empty set)： 没有任何元素的集合是空集,记作? 例如： {x?R|x2 +1=0} [定理]　 对任意集合A空集是它的子集 也就是对任意集合A, ??A 证明: ??A??x(x???x?A) 　??x(F?x?A)?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|x?A} 注意: x?P (A) ? x?A 例如: 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的交集，记作A?B 。 S=A?B = { x | (x?A) ? (x?B) } x?A?B? ? (x?A) ? (x?B) 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) （结合律） 因为集合交运算满足结合律，故n个集合的交记为： n P=A1 ? A2 ? ? ? An