集合

• 给定两个集合$A,B$和全集$S$求：
  • 交集$A\cup B$
    • A与B的所有元素
  • 并集
    • A与B中都有的元素
  • 差集$A-B$
    • 将$A$中元素减去$B$中存在的
  • 对称差$A△B$
    • $A△B=(A-B)\cup (B-A)$
  • $A$的余集
    • 全集中非$A$的部分,即 $S-A$
  • 笛卡尔积$A\times B$
    • $A\times B=\{(a,b)|a\in A,b\in B\}$
    • 最后形式上应该如$\{(a_1,b_1),(a_1,b_2),(a_1,b_3),(a_2,b_1)\cdots (a_3,b_3)\}$
    • 笛卡尔积对交并差有结合律
  • $2^A$ 即$A$所有子集构成的集合 注意不要忘记$\varnothing$和本身
• 证明两个集合相等
  • 互为子集法
  • 例：集合A为偶数集合，集合B$\{x|x\mathrm{mod}2=0,x\in Z\}$
  • 具体步骤
    1. 任取元素 ： 设 $x\in A$
    2. 性质处理 ： 则 $x$ 为偶数，即 $\exists k,x=2k$
    3. 证明子集 ： $2k\mathrm{mod}2=0$即$x\in B$ ,故$A\subseteq B$
    4. 反向证明 ： 设 $y\in B$ 有 $y\mathrm{mod}2=0$,即 $y$ 为偶数，故 $B\subseteq A$
    5. 证明相等 ： 因为 $A\subseteq B$ 且 $B\subseteq A$,故 $A=B$
• 证明对称差满足结合率
  • 即证明 ： $A△(B△C)=(A△B)△C$
  • 证明思路：
    • $A△B=(A-B)\cup (B-A)$
    • 将上式左右打开即可证明
• 容斥原理
  • $\left|\sum _{i=1}^n{A}_i\right|=\sum _{i=1}^n|A_i|-\sum _{i=1}^{\frac{n}{2}}|A_{2i+1}{A}_{2(i+1)}|+\cdots (-1{)}^{n-1}\left|{\bigcup }_{i=1}^n{A}_i\right|$