离散数学

集合的概念、表示方法、子集、空集、笛卡尔积、幂集、集合并交补差运算、集合恒等式 函数的概念、单射、满射、双射、逆函数、函数的复合

集合的概念 一般来说，把具有共同性质的一些东西，汇集成一个整体，就形成一个集合。通常用大写英文字母表示集合的名称；用小写英文字母表示组成集合的事物，即元素。若元素 a a a 属于集合 A A A ，记作 a ∈ A a\in A a∈A ，否则记作 a ∉ A a\notin A a∈/​A 。一个集合，若其元素个数是有限的，则称作有限集，否则称为无限集。

集合的表示 列举法，如 A = { a , b , c , d } A=\{ a,b,c,d\} A={a,b,c,d}; 描述法，如 B = { x ∣ x < 10 } B=\{x|x0,1,2,3….} Z = { … , − 3 , − 2 , − 1 , 0 , 1 , 2 , 3 , … } \{…,-3,-2,-1,0,1,2,3,…\} {…,−3,−2,−1,0,1,2,3,…} Z⁺ = { 1 , 2 , 3 , … . . } \{1,2,3,…..\} {1,2,3,…..} R = 实数集 R+ = 正实数集 C = 复数集 Q = 有理数集

子集（subsets） 定义： A ⊆ B ≡ ∀ x ( x ∈ A → x ∈ B ) A \subseteq B \equiv \forall x (x\in A \rightarrow x \in B) A⊆B≡∀x(x∈A→x∈B)

真子集(proper subsets) 定义： ∀ x ( x ∈ A → x ∈ B ) ∧ ∃ x ( x ∈ B ∧ x ∉ A ) \forall x (x\in A \rightarrow x \in B) \wedge \exists x(x\in B \wedge x\notin A) ∀x(x∈A→x∈B)∧∃x(x∈B∧x∈/​A)

集合相等 定义： A = B ≡ ∀ x ( x ∈ A ↔ x ∈ B ) A=B \equiv \forall x({x\in A \leftrightarrow x\in B }) A=B≡∀x(x∈A↔x∈B) 判定定理： A = B ≡ ( A ⊆ B ∧ B ⊆ A ) A=B \equiv (A \subseteq B \wedge B \subseteq A ) A=B≡(A⊆B∧B⊆A)

集合的基数（Cardinality） 集合的基数是用来衡量集合里面不同元素的个数的。

幂集（power sets） 给定集合 A A A ，由集合 A A A 的所有子集为元素组成的集合，称为集合 A A A 的幂集，记作 P ( A ) \mathscr{P}(A) P(A) 。 例如，如果 A={a,b}，那么 P ( A ) = { ∅ , { a } , { b } , { a , b } } \mathscr{P}(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\} P(A)={∅,{a},{b},{a,b}}。 如果有限集合 A A A 有 n n n 个元素，则其幂集 P ( A ) \mathscr{P}(A) P(A) 有 2 n 2^n 2n 个元素。

序偶(ordered pair) 序偶可以看作是具有两个元素的集合。但它与一般集合不同的是序偶具有确定的次序。

笛卡尔积（直积）(Cartesian Products) 令 A A A 和 B B B 是任意两个集合，若序偶的第一个成员是 A A A 的元素，第二个成员是 B B B 的元素，所有这样的序偶集合，称为集合 A A A 和 B B B 的笛卡尔乘积或直积，记作 A × B A\times B A×B 。 A × B = { ⟨ x , y ⟩ ∣ ( x ∈ A ) ∧ ( y ∈ B ) } A \times B = \{\langle x,y \rangle \vert (x \in A)\wedge(y \in B)\} A×B={⟨x,y⟩∣(x∈A)∧(y∈B)}

推广： A × B × C … … A\times B\times C…… A×B×C…… 注意这和 ( A × B ) × C (A\times B)\times C (A×B)×C与 A × ( B × C ) A\times (B\times C) A×(B×C)的含义不同。 特别地， A × A A \times A A×A 可以写成 A 2 A^2 A2 ，同样地， A × A × ⋯ × A ⏞ n = A n \overbrace{A \times A \times \cdots \times A}^{n}=A^n A×A×⋯×A ​n​=An 。

定义: A − B = { x ∣ x ∈ A ∧ x ∉ B } A-B=\{x|x\in A \wedge x\notin B\} A−B={x∣x∈A∧x∈/​B} = A ∩ B ‾ A \cap \overline{B} A∩B

这是教材的一小节，讲的东西其实状态压缩DP的状态压缩。（当然状态压缩的方式有很多种，这里只是最简单的一种。） 假定全集 U = { a 1 , a 2 , a 3 , … … a n } U=\{ a_1,a_2,a_3,……a_n\} U={a1​,a2​,a3​,……an​}，现在要表示集合 A A A的中的元素的情况， 便可以一个长度为n的01串来表示，其中若第i位，表示 a i ∈ A a_i\in A ai​∈A,若第i为0，表示 a i ∉ A a_i\notin A ai​∈/​A。

这样做的好处在于，可以很方便的进行集合交并运算。 记 A 、 B A、B A、B两个集合的位串为 S 1 , S 2 S1,S2 S1,S2； 那么 A ∪ B A\cup B A∪B的情况可以表示为： S 1 ∣ S 2 S1 | S2 S1∣S2（按位与运算） 而 A ∩ B A\cap B A∩B的情况可以表示为: S 1 & S 2 S1 \&S2 S1&S2 (按位或运算)

函数，英文为function，mapping，transformation。

定义： 设 X X X 和 Y Y Y 是任意两个集合，而 f f f 是 X X X 到 Y Y Y 的一个关系，如果对于每一个 x ∈ X x\in X x∈X ，有唯一的 y ∈ Y y\in Y y∈Y ，使得 ⟨ x , y ⟩ ∈ f \langle x,y \rangle\in f ⟨x,y⟩∈f ，称关系 f f f 为函数，记作 f : X → Y  或  X → f Y f:X\rightarrow Y\text{ 或 }X\overset{f}{\rightarrow}Y f:X→Y 或 X→fY A叫做定义域(demain),B叫做伴域(codomain); 如果， f ( a ) = b f(a)=b f(a)=b，那么b是像(image),a是原像(preimage)。 像的集合叫值域(range)。

集合在函数下的像 f ( S ) = { f ( s ) ∣ s ∈ S } f(S) = \{f(s) | s\in S \} f(S)={f(s)∣s∈S} 注意， f ( S ) f(S) f(S)也是集合，是像的集合。

利用笛卡尔积定义函数

函数相等 定义： 设函数 f : A → B , g : C → D f:A\rightarrow B,g:C\rightarrow D f:A→B,g:C→D ，如果 A = C , B = D A=C,B=D A=C,B=D ，且对于所有 x ∈ A x\in A x∈A 和 x ∈ C x\in C x∈C ，有 f ( x ) = g ( x ) f(x)=g(x) f(x)=g(x) ，则称函数 f f f 和 g g g 相等，记作 f = g f=g f=g 。

单射（入射）(one -to-one、injection) 定义： 从 X X X 到 Y Y Y 的映射中， X X X 中不存在两个不同元素有相同的象，则称这个映射为入射（或一对一映射）。设 f : X → Y f:X\rightarrow Y f:X→Y 是入射，即是对于任意 x 1 , x 2 ∈ X x_1,x_2\in X x1​,x2​∈X ， 即 x 1 ≠ x 2 ⇒ f ( x 1 ) ≠ f ( x 2 ) x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2) x1​​=x2​⇒f(x1​)​=f(x2​) 或者 f ( x 1 ) = f ( x 2 ) ⇒ x 1 = x 2 f(x_1)=f(x_2)\Rightarrow x_1=x_2 f(x1​)=f(x2​)⇒x1​=x2​

满射（onto、surjection） 定义： 对于 X → f Y X\overset{f}{\rightarrow}Y X→fY 的映射中，如果 range f = Y \text{range}f=Y rangef=Y ，即 Y Y Y 的每一个元素是 X X X 中一个或多个元素的象点，则称这个映射为满射（或到上映射）,即 ∀ y ∈ Y , ∃ x ∈ X , s . t . f ( x ) = y \forall y\in Y,\exists x\in X,s.t. f(x)=y ∀y∈Y,∃x∈X,s.t.f(x)=y 通俗的说，就是B中的每一个元素都没有漏下，伴(陪)域就是值域。

双射（one-to-one correspondence、bijection） 从 X X X 到 Y Y Y 的一个映射，若既是满射又是入射的，则称这个映射是双射的。

一一对应关系式可逆的 （invertible）。

定义： 设 f : X → Y f:X\rightarrow Y f:X→Y 是一双射函数，称 Y → X Y \rightarrow X Y→X 的双射函数 f c f_c fc​ 为 f f f 的逆函数，记作 f − 1 f^{-1} f−1 。 f − 1 ( y ) = x f^{-1}(y)=x f−1(y)=x ,iff， f ( x ) = y f(x)=y f(x)=y。 所以： x ∈ f − 1 ( S ) ≡ f ( x ) ∈ S x\in f^{-1}(S) \equiv f(x)\in S x∈f−1(S)≡f(x)∈S 定理： 只有双射函数才存在逆函数。

注意：函数的复合并不满足交换律。

定义： 集合 A 、 B A、B A、B有相同的基数，当且仅当存在一个 A A A到 B B B的双射的时候，此时记为 ∣ A ∣ = ∣ B ∣ |A|=|B| ∣A∣=∣B∣