离散数学1.doc

离散数学第一章集合与关系§1 集合的概念与运算一、集合的概念集合是数学中最基本的概念。指一些可确定的,可分辨的事物组成的整体。集合通常用大写字母, , , A B C ?表示。组成集合的每个成员叫做这个集合的元素,用小写字母, , , a b c ?表示。如果a 是集合 A 的一个元素,那么记为 a A ?如果a 不是集合 A 的一个元素,那么记为 a A ? Notice: 集合的元素是确定的,即对于某个元素 a 与某个特定的集合 S ,要么 a S ?,要么 a S ?。集合的元素是互异的。集合的元素是没有次序的。集合通常有两种表示方法: (1 )列举法 N 表示自然数集?? 0,1, 2, N??;Z 表示整数集; Z ?表示正整数集; Q 表示有理数集; R 表示实数集。(2 )描述法如果一个集合是由满足某条件 P 的那些元素组成,那么就把该集合记为??( ) x p x 如所有质数组成的集合可表示为?? x x 为质数一般说来,集合的元素可以是任何类型的事物,一个集合也可以作为另一个集合的元素集合??????, , , , E a b c d d ?。必须指出,??, b c E ?,而 b E ?, 但是?? d E d E ? ?且二、集合的关系定义 设, A B 为集合, A B 与相等, iff 它们有相同的元素,记作 A B ?,两个集合不相等,则记为 A B ?。性质:(1 )自反性: , A A A ? ?; (2 )对称性: , . , A B A B B A ? ??若则; (3 )传递性: , , , , A B C A B B C A C ? ???若且则。定义 设, A B 为两个集合,若 A 中的没一个元素都是 B 中的元素,则称 A 为B 的子集,记为 A B ?。并称关系" " ?为包含关系。如果 A 不是B 的子集,记为 AB 。特别地,若 A 是B 的子集,且集合 B 中至少有一个元素不在 A 中,则称 A 是B 的真子集, 记为 A B ? ,“? ”称为真包含关系。例1?????? 1, 2,3, 4 , 1,3, 6,8,10 1, 6 A B C ? ??则定理 设 A B 和 S 是两个集合,则 A B iff A B B A ? ??且" " ?具有下列性质: (1 )自反性: , A A A ? ?; (2 )反对称性: , . , , A B A B B A B ? ???若且则A ; (3 )传递性: , , , , A B C A B B C A C ? ???若且则。 Notice: 属于关系" " ?与包含关系" ' ?有本质的区别。前者表示集合 A 中的元素与集合本身的一种从居关系, 而后者是两个集合之间的一种关系。例如: ??????, , a a a b ??????, , a a a b ????? 1, 2 0,1, 2 ?????, , a a a b ?,但????, a a b ?????????, , , , a b a b a b ?对,因为, a b 都是??????, , , a b a b 中的元素。????????, , , , a b a b a b ?错,因为??, a b 不是??????, , , a b a b 中的元素。两个特殊的集合: 不含任何元素的集合, 称为空集, 记为?, 规定它是任何一个集合的子集。空集是唯一的。全集:包含了某个问题中所讨论的一切元素,记为 U 定义 给定集合 A 的所有子集组成的集合,称为集合 A 的幂集,记为例2设A??, , a b c ?,求( ) A?解:首先, A ?? A 的仅含有一个元素的子集有: ??????, , a b c 。 A 的含有二个元素的子集有: ??????, , , , , a b b c a c 。 A 的含有三个元素的子集有: ??, , a b c 。所以( ) A?????????????????, , , , , , , , , , , , a b c a b a c b c a b c ? ?运用例 2 的方法不难证明下面的定理: 定理 如果集合 A 有n 个元素,那么其幂集( ) A?中有2 n 个元素。例设????, A a