文章目录
第三章 集合代数
-
特点：
- 研究问题的广泛性
- 分析思考问题的抽象性
- 处理问题的统一性
3.1 基本概念
-
集合 (SET)：在一定范围内的讨论的对象组成的整体。
-
表示方法：
-
枚举法
-
隐式法(叙述法)：用共同特征划分， P = { x ∣ P ( x ) } P=\{x|P(x) \} P={x∣P(x)}
-
归纳法：基础 + 归纳(确定下限) + 极小性(确定上限)
例题 \color{White}\colorbox{Fuchsia}{例题} 例题：定义集合 M M M，
- 每一个英文字母都是 M M M中的元素
- 如果 P , Q P,Q P,Q是 M M M中的元素，则 P Q , Q P PQ,QP PQ,QP也是 M M M中的元素
- 有限次使用 ( 1 ) , ( 2 ) (1),(2) (1),(2)后所得到的字符串都是 M M M中的元素。
-
递归指定：通过计算规则定义集合中的元素
-
巴科斯范式BNF(Backus Normal Form)表示法：
-
文氏图
-
特征函数表示法： X A = { 1 , x ∈ A 0 , x ∉ A X_A=\begin{cases}\begin{aligned}&1,&x\in A\\&0,&x\notin A\end{aligned}\end{cases} XA={1,0,x∈Ax∈/A
罗素悖论（理发师悖论）：说明集合不能被精确定义
-
-
关系与子集：
-
子集： B ⊆ A ⟺ ∀ x , x ∈ B ⟶ x ∈ A B\subseteq A\iff \forall x,x\in B\longrightarrow x\in A B⊆A⟺∀x,x∈B⟶x∈A
-
相等： A = B ⟺ A ⊇ B ∧ B ⊆ A A=B\iff A\supseteq B \land B\subseteq A A=B⟺A⊇B∧B⊆A
-
基数 Cardinality： ∣ A ∣ |A| ∣A∣
- A A A 为有限集合： ∣ A ∣ |A| ∣A∣ 有限
- A A A 为无限集合： ∣ A ∣ |A| ∣A∣ 无限
-
空集： ∅ = { x ∣ x ≠ x } \emptyset=\{x|x\ne x \} ∅={x∣x=x}
∅ = { } , ∅ ≠ { ∅ } \emptyset=\{\},\emptyset\ne\{\emptyset\} ∅={},∅={∅}
-
全集 U or E：在某个固定范围内的所有对象的全体
-
-
性质：
- 全集相对唯一，而非绝对唯一
- 空集绝对唯一
- 对于 ∀ A \forall A ∀A，有 ∅ ⊆ A , A ⊆ A \emptyset\subseteq A,A\subseteq A ∅⊆A,A⊆A. 若 A ⊆ B , B ⊆ C A\subseteq B,B\subseteq C A⊆B,B⊆C，则 A ⊆ C A\subseteq C A⊆C
-
外延性原理：集合中元素都是不同且无序的。
3.2 集合运算
-
特殊子集：
-
并集 Union： A ⋃ B = { x ∈ U ∣ x ∈ A ∨ x ∈ B } A\bigcup B=\{x\in U|x\in A\lor x\in B \} A⋃B={x∈U∣x∈A∨x∈B}
-
交集 Intersection： A ⋂ B = { x ∈ U ∣ x ∈ A ∧ x ∈ B } A\bigcap B=\{x\in U|x\in A\land x\in B \} A⋂B={x∈U∣x∈A∧x∈B}
不相交 Disjoint： A ⋂ B = ∅ A\bigcap B=\emptyset A⋂B=∅
-
差集 Subtraction： A − B = { x ∈ U ∣ x ∈ A ∧ x ∉ B } A-B=\{x\in U|x\in A\land x\notin B \} A−B={x∈U∣x∈A∧x∈/B}
-
补集 Complement： A ‾ = U − A = { x ∣ x ∈ U ∧ x ∉ A } \overline{A}=U-A=\{x|x\in U\land x\notin A \} A=U−A={x∣x∈U∧x∈/A}
-
对称查集： A ⊕ B = { x ∣ ( x ∈ A ∧ x ∉ B ) ∨ ( x ∈ B ∧ x ∉ A ) } = ( A − B ) ⋃ ( B − A ) A\oplus B=\{x|(x\in A\land x\notin B)\lor(x\in B\land x\notin A)\}=(A-B)\bigcup(B-A) A⊕B={x∣(x∈A∧x∈/B)∨(x∈B∧x∈/A)}=(A−B)⋃(B−A)
-
-
性质：幂等律，交换律，结合律，零一律，分配律 ，吸收律（ A ⋂ ( A ⋃ B ) = A , A ⋃ ( A ⋂ B ) = A A\bigcap(A\bigcup B)=A,A\bigcup(A\bigcap B)=A A⋂(A⋃B)=A,A⋃(A⋂B)=A），否定律，德摩根定律，矛盾律
3.3 幂集和笛卡尔集
-
幂集 power set：由集合 A A A 的子集组成的集合，记为 ρ ( A ) \rho(A) ρ(A) 或 2 A 2^A 2A
2 A = ρ ( A ) = { x ∣ ∀ X ⊆ A } 2^A=\rho(A)=\{x|\forall X\subseteq A\} 2A=ρ(A)={x∣∀X⊆A}集族 Family of Set：以集合为元素构成的集合。
例题 \color{White}\colorbox{Fuchsia}{例题} 例题： 2 ∅ = { ∅ } , 2 { ∅ } = { ∅ , { ∅ } } 2^\emptyset=\{\emptyset\},2^{\{\emptyset\}}=\{\emptyset,\{\emptyset\}\} 2∅={∅},2{∅}={∅,{∅}}
- 性质：
- 若 B ⊆ A B\subseteq A B⊆A，则 2 B ⊆ 2 A 2^B\subseteq 2^A 2B⊆2A
- ∣ 2 A ∣ = 2 ∣ A ∣ |2^A|=2^{|A|} ∣2A∣=2∣A∣
- 性质：
-
笛卡尔积(直积) Descartes： A 1 , A 2 , . . . , A n A_1,A_2,...,A_n A1,A2,...,An 的笛卡尔积为
A 1 × A 2 × . . . × A n = { < a 1 , a 2 , . . . , a n > ∣ a i ∈ A i , 1 ≤ i ≤ n } A_1\times A_2\times ...\times A_n=\{<a_1,a_2,...,a_n>|a_i\in A_i,1\le i \le n\} A1×A2×...×An={<a1,a2,...,an>∣ai∈Ai,1≤i≤n}-
若 ∀ i , A i = A \forall i,A_i=A ∀i,Ai=A，则 A 1 × A 2 × . . . × A n = A n A_1\times A_2\times ...\times A_n=A^n A1×A2×...×An=An
-
基数计算： ∣ ( A 1 × A 2 × . . . × A n ) ∣ = ∣ A 1 ∣ × ∣ A 2 ∣ × . . . × ∣ A n ∣ |(A_1\times A_2\times ...\times A_n)|=|A_1|\times |A_2|\times ...\times |A_n| ∣(A1×A2×...×An)∣=∣A1∣×∣A2∣×...×∣An∣
-
笛卡尔积不服从交换律和结合律，但对于交并运算可分配律
A × ( B ⋃ C ) = ( A × B ) ⋃ ( A × C ) A\times(B\bigcup C)=(A\times B)\bigcup(A\times C) A×(B⋃C)=(A×B)⋃(A×C) A × ( B ⋂ C ) = ( A × B ) ⋂ ( A × C ) A\times(B\bigcap C)=(A\times B)\bigcap(A\times C) A×(B⋂C)=(A×B)⋂(A×C) ( B ⋃ C ) × A = ( B × A ) ⋃ ( C × A ) (B\bigcup C)\times A=(B\times A)\bigcup(C\times A) (B⋃C)×A=(B×A)⋃(C×A) ( B ⋂ C ) × A = ( B × A ) ⋂ ( C × A ) (B\bigcap C)\times A=(B\times A)\bigcap(C\times A) (B⋂C)×A=(B×A)⋂(C×A) -
存属关系
A ⊆ B ⟺ A × C ⊆ B × C A\subseteq B\iff A\times C\subseteq B\times C A⊆B⟺A×C⊆B×C A ⊆ B ⟺ C × A ⊆ C × B A\subseteq B\iff C\times A\subseteq C\times B A⊆B⟺C×A⊆C×B A × B ⊆ C × D ⟺ A ⊆ C ∧ B ⊆ D A\times B\subseteq C\times D\iff A\subseteq C\land B\subseteq D A×B⊆C×D⟺A⊆C∧B⊆D /
-