《离散数学》导学资料.docVIP

《离散数学》导学资料一 —— 第一章 集合 1.1 集合的基本概念 1.2 集合的基本运算 1.3 集合的宏运算 1.4 集合运算的其他表示法 一、集合的基本概念 1．集合的概念有三要素 a. 个体（元素） b. 个体的可辨认性 c. 集合（动词） 通常用小写拉丁字母表示个体：a、b、c、d… 通常用大写拉丁字母表示集合：A、B、C、D… 个体与集合之间的关系称为属于关系。 对于某个个体 a 和某个集合 A 而言， a 只有两种可能： 1）a 属于 A，记为 a(A，同时称 a 是 A 中的元素。 2）a 不属于 A，记为 a(A ，称 a 不是 A 中的元素。 判断个体 a 属于 A 还是不属于 A ，必须使用个体的可辨认性，而且个体的可辨认性是无二义性的，即或者 a 属于 A 或者 a 不属于 A，二者居其一且只居其一。 关于个体的辨认有赖于各方面的公认的知识。 2．集合的表示法 文字表示法 用文字表示集合的元素，两端加上花括号。 元素列举法 将集合中的元素逐一列出，两端加上花括号。 谓词表示法 { x︱p(x) } p 表示 x 所满足的性质。 3．集合的特殊情况 不含任何元素的集合称为空集，记为(或{ }。 只含一个元素的集合称为单元素集，记为{ a }。 含讨论问题所需全部元素的集合称为全集，记为X。 4．集合与集合之间的关系 定义 设A，B是两个集合 1）若对于A中的每个元素x，都有x属于B，则称A包含在B中，记为A(B。同时称A是B的子集。 2）若A中的每个元素都属于B，且B中的每个元素都属于A，则称A等于B，记为A=B。 子集的两种特殊情况（平凡子集）： 1）空集是任一集合的子集。 2）每个集合是它自己的子集。 集合与集合之间的关系称为包含关系。 5．幂集 定义 设A是集合，A的所有子集组成的集合称为A的幂集，记为 2A。 2A ={ x ( x ( A } 定理1 设集合A是有限集合， ( A ( = n，则 ( 2A ( = 2 ( A ( 。 定理2 设A，B是两个集合。那么，A=B当且仅当 2A = 2B。 二、集合的基本运算 1．集合的补运算（一元运算） 定义 设X是集合，A是X的子集。 A(={ x ( x(X ∧ x(A } ,称A(是A关于X的补集，称 ( 为补运算。 定理 设X是集合，A，B是X的子集。则 1）(A() (=A； 2）若A ( B，则B( ( A(； 3）若A = B，则A(= B( ； 4）X(= (，((=X。 2．集合的交运算和并运算 定义 设A，B是两个集合 ? 1）A∩B = { x︱x(A∧x(B }，称A∩B为A与B的交集，称∩为集合交运算。 2）A∪B = { x︱x(A∨x(B }，称A∪B为A与B的并集，称∪为集合并运算。 定理 设X是全集，A，B，C是X的三个子集合，则 1）A∩A=A， A∪A=A 2）A∩A( = (， A∪A( =X 3）A∩X=A， A∪X=X 4）A∩( = ( ， A∪( =A 5）A∩B= B∩A， A∪B= B∪A 6）(A∩B) ∩C = A∩ (B∩C), (A∪B) ∪C = A∪ (B∪C) 7）A∩(B ∪C) = (A∩B) ∪(A∩C) A∪(B ∩C) = (A∪B) ∩(A∪C) 定理 设A，B，C为三个集合，则 1）A ( A∪B， A∩B ( A； 2）若 A ( C 且 B ( C，则 A∪B ( C； 3）若 C ( A 且 C ( B，则 C ( A∩B 。 定理 设A，B为两个集合，则下面三式等价。 1）A ( B 2）A∪B = B 3) A∩B=A 定理 设A，B为两个集合，则 1）( A∪B)( = A(∩B( 2）( A∩B)( = A(∪B( 三、集合的宏运算 定义 设A，B是两个集合，A\B = { x︱x(A∧x(B }，称 A\B 为 A 和 B 的差集，称 \ 为集合差运算。 由差运算、交运算、补运算的定义知 A\B = A∩B(。 由于差运算可以由并、交、补运算线性表出，因此称差运算为宏运算。 定理 设X是全集，A，B，C是X的三个子集合，则 1） A\B ( A ； 2） A\A = ( ； 3） X\A = A( ；A\X = ( ； 4） A\( = A ； (\A = ( ；