逻辑, 集合, 计数与映射
咕咕咕
逻辑集合计数
逻辑
命题：指可以判断对错的叙述.
真值：若命题为真则为真(\(1\))，否则为假(\(0\)).
充分必要：\(p \Rightarrow q\) 指 \(p\) 推出 \(q\)，\(p\) 为 \(q\) 充分条件，\(q\) 为 \(p\) 必要条件(可以理解为判定和性质的区别).
\(p \Leftrightarrow q\) 即互为充要条件 .
原命题：若 \(p\) 则 \(q\) 逆命题：若 \(q\) 则 \(p\).
否命题：若 \(\neg p\) 则 \(\neg q\).
逆否命题：若 \(\neg q\) 则 \(\neg p\) .
其中原命题和逆否命题真值相同，否命题和逆命题互为逆否命题
| 条件 | 概念 |
|---|---|
| \(p\) 是 \(q\) 的充分不必要条件 | \(p\Rightarrow q\) 且 \(q\nRightarrow p\) |
| \(p\) 是 \(q\) 的必要不充分条件 | \(p\nRightarrow q\) 且 \(q\Rightarrow p\) |
| \(p\) 是 \(q\) 的充分必要条件 | \(p\Leftrightarrow q\) |
| \(p\) 是 \(q\) 的不充分不必要条件 | \(p\nRightarrow q\) 且 \(q\nRightarrow p\) |
量词
全称量词和存在量词： \(\forall\)（对于任意），\(\exists\)（存在）.
考虑这么一件事，就是说设函数 \(f(x)\) 考虑两种情况：
\(\forall x \in R,f(x)<k\)，\(k\) 的取值是 \(k>\max f(x)\)，因为 \(\forall\) 的任意性 .
\(\exists x \in R,f(x)<k\) 由于只是存在，我们只能得知 \(k>\min f(x)\).
集合
集合元素三个特征：确定性、互异性、无序性.
通常用 \(\{\}\) 描述集合，用 \(()\) 描述一个有序对.
常见集合：
| 集合 | 自然数集 | 正整数集 | 整数集 | 有理数集 | 实数集 |
|---|---|---|---|---|---|
| 符号 | \(\mathbb N\) | \(\mathbb N^*\) 或 \(\mathbb N_+\) | \(\mathbb Z\) | \(\mathbb Q\) | \(\mathbb R\) |
一个元素 \(a\) 属于集合 \(A\) 记作 \(a \in A\)，不属于记作 \(a \notin A\)
\(|A|\) 是 \(A\) 中元素个数 .
若两个集合 \(A\)，\(B\) 满足 \(\forall x \in A,x \in B\)，则称 \(A\) 被包含于 \(B\)，记作 \(A \subseteq B\)，\(A \supseteq B\) 反之同理 .
若同时满足 \(A \subseteq B\) 和 \(A \supseteq B\) ，则称 \(A=B\) .
称 \(x^A\) 为 \(A\) 子集数量之和，即 \(x^{|A|}\) 由于讨论问题时常常要限定范围，则规定全集（\(U\)）为所有讨论范围内的集合组成的集合.
集合间基本运算主要有 并（\(\cup\)） 、交（\(\cap\)） 、差（\(\setminus\)）、 全集为 \(U\) 下的补集(以下默认全集为 \(U\))（\(\complement_U\) ）.
\(A \cup B = \{x|x \in A 或 x \in B\}\),
\(A \cap B = \{x|x \in A 且 x \in B\}\),
\(\complement_U A = \{x|x \in U 且 x \notin A\}\),
\(A \setminus B = \{x|x \in A 且 x \notin B\} = A \cap \complement_U B\).
运算律：显然并交满足交换和结合律，同时满足分配律，即
\(A \cup ( B \cap C ) = (A\cup B) \cap (A \cup C)\)，
\(A \cap ( B \cup C ) = (A\cap B) \cup (A \cap C)\) .
证明：对于式一，\(\forall x \in A\cup (B\cap C)\) 若 \(x\in A\) 则显然也属于右侧
若 \(x\in ( B \cap C )\)，则显然其同时属于 \((A\cup B)\) 和 \((A\cup C)\).
对于式二，\(\forall x \in A \cap ( B \cup C )\)，则其要么属于 \((A\cap B)\) 要么属于 \((A\cap C)\)，右式成立.
集合与逻辑的关系：
设 \(A=\{x\mid P(x)\},B=\{x\mid Q(x)\}\).
| 关系 | 条件 |
|---|---|
| \(A\subseteq B\) | \(P\) 是 \(Q\) 的充分条件 |
| \(A\supseteq B\) | \(P\) 是 \(Q\) 的必要条件 |
| \(A=B\) | \(P\) 是 \(Q\) 的充要条件 |
| \(A\nsubseteqq B\) | \(P\) 是 \(Q\) 的充分不必要条件 |
| \(A\nsupseteqq B\) | \(P\) 是 \(Q\) 的必要不充分条件 |
| \(A\nsubseteqq B\) 且 \(A\nsupseteqq B\) | \(P\) 是 \(Q\) 的不充分不必要条件 |
容斥原理
\[\left|\bigcup\limits_{i=1}^{n} A_{i}\right|=\sum\limits_{k=1}^{n}(-1)^{k-1} \sum\limits_{1 \leq i_{1}<i_{2}<\cdots<i_{k} \leq n}\left|A_{i_{1}} \cap A_{i_{2}} \cap \cdots \cap A_{i_{k}}\right| \]证明考虑计算贡献，可知左式每个元素出现一次，右式出现 \(C_{k}^{1}-C_{k}^{2}+C_{k}^{3}-\ldots+(-1)^{i-1} C_{k}^{i}+\ldots+(-1)^{k-1} C_{k}^{k}=1\).
欧拉函数
小于等于 \(n\) 的数中与 \(n\) 互质的个数，记作 \(\varphi (n)\) 令数列 \(p\) 为唯一分解后 \(n\) 的质因子数列， \(k\) 为质因子数，\(A_i\) 为 \(p_i\) 倍数个数.
则 \(\varphi(n)=n-\left|\bigcup\limits_{i=1}^{n} A_{i}\right|=n\prod\limits_{i=1}^{k} (1-p_i)\).
错排问题
设一个排列 \(z\)，问有多少种 \(z_i \neq i\) 的排列.
设 \(D_n\) 为 \(n\) 个数错排.
易知全排列 \(n!\) 种.
用全排列减去正确排序即为错排，即减去只对一位的方案数，但你会发现有些对多个位置方案也减掉了，于是考虑容斥：
易知， \(D_n=\sum\limits_{i=0}^{n} (-1)^i \binom{n}{i}(n-i)! =n!\sum\limits_{i=0}^{n} (-1)^i\frac{1}{i!}\).
映射与计数
以下认为 \(A,B\) 是两集合.
对应关系 \(f：A\to B\) 按某种确定的对应关系 \(f\)，使得对于 \(A\) 中任意一元素 \(x\) 在 \(B\) 中都有唯一确定的元素 \(f(x)\) 与之对应，称 \(f：A\to B\) 是集合 \(A\) 到 \(B\) 的一个映射.
映射相关定义：在映射中， \(x\) 的取值范围称为映射的定义域， 与 \(x\) 对应的 \(f(x)\) 称为 \(x\) 在 \(f\) 下的像.
集合 \(f(A)=\{f(x)|x\in A\}\) 称为映射的像集合.
若 \(f(A)=B\) 则称映射 \(f\) 是一个满射 ，若 \(\forall x_1,x_2(x_1 \neq x_2),f(x_1) \neq f(x_2)\) 则称映射 \(f\) 是一个单射.
若一个映射又是满射又是单射则称 \(f\) 为一一映射，此时存在反映射 \(f^{-1}：B \to A\) 满足 \(\forall x\in A，f^{-1}(f(x))=x\) 同时 \(\forall y\in B，f(f^{-1}(y))=y\) .
映射很大的用途之一是判断无限集的大小，如果可以构造一个一一映射则说明二集合大小相等.
可以证明整数集、偶数集、正整数集、有理数集可以构造出一一映射关系.
此处给出对于实数集无法构造一个一一映射和上述集合的证明 设已经构造好一个有理数向实数的映射，那么假设排成的映射数列为 \(z\)，从而可以发现永远可以找到一个实数使得其第 \(i\) 位和 \(z_i\) 的第 \(i\) 位不同，也就是说这不是一个一一映射，过程就如在走对角线 我们也可以从映射角度来说组合数，但本文不这么做因为怕写错真的不是不会 此处给出一些常见的计数公式：
- \(\binom{n}{k}=\binom{n}{n-k}\)
- \(\sum\limits_{i=0}^{n} \binom{n}{i} =2^n\)
- \(\binom{n}{0}+\binom{n}{2}+\binom{n}{4}...= \binom{n}{1}+\binom{n}{3}+\binom{n}{5}...\)
- \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\)
- \(\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}=\frac{n-k+1}{k}\binom{n}{k-1}\)