1.逻辑

命题：能够判断正确或错误的叙述。

复合命题：若\(p\),则\(q\)

设原命题为若\(p\),则\(q\)，则：

• 1.逆命题：若\(q\),则\(p\)
• 2.否命题：若\(\neg p\),则\(\neg q\)
• 3.逆否命题：若\(\neg q\),则\(\neg p\)

其中原命题与逆否命题等价，逆命题与否命题等价。

条件：

若 \(p \Rightarrow q\) ,则 \(p\) 是 \(q\) 的充分条件，\(q\) 是 \(p\) 的必要条件。

量词：

• 1.全称量词：任意，符号为$\forall $
• 2.存在量词：存在，符号为$\exists $

eg1.\(\forall x \in R,有 f(x) > k\)

很典型的题目，可以转化为\(max(f(x))>k\)

eg2.\(\exists x \in R,有 f(x) > k\)

存在一个\(x\)满足条件即可，转化为\(min(f(x))>k\)

2.集合，元素

• 1.集合元素的三个特征：无序性，互异性，确定性
• 2.元素与集合之间的关系是属于或不属于，用\(\in\)或$\notin $表示
• 3.常见的集合记法：

ps:在符号上加$ * ,+$的上下标通常表示正的部分

集合与元素间的基本关系

若\(a\)属于集合\(A\)，记作\(a \in A\),若\(a\)不属于集合\(A\)，记作\(a \notin A\)

集合与集合间的基本关系

子集：

集合\(A\)包含于集合\(B\)(集合\(A\)是集合\(B\)的子集)，记作\(A\subseteq B\),也可以记作\(B \supseteq A\)
下面我们用数学语言解释\(A\subseteq B\)：
\(\forall x \in A\),均有\(x \in B\)。
从这条解释可以看出\(A\subseteq B\)可以得出\(x \in A\)是\(x \in B\)的充分条件，\(x \in B\)是\(x \in A\)的必要条件
\(Venn\)图:

真子集：

集合\(A\)是集合\(B\)的子集，且集合\(B\)中至少有一个元素不在集合\(A\)中
\(Venn\)图:

集合相等：

如果有\(A\subseteq B\)，\(B\subseteq A\)，称\(A=B\)
\(Venn\)图:

集合与集合间的基本运算

集合的并集：

图像（黄色部分）：

n个集合\(A_1,A_2....A_n\)的并集可以记作\(\bigcup_{i=1}^{n} A_i\)

集合的交集：

图像：

n个集合\(A_1,A_2....A_n\)的交集可以记作\(\bigcap_{i=1}^{n} A_i\)

集合的补集：

要谈补集，我们首先要钦定一个全集\(U\),\(U\)里包含了所有讨论的元素。

图像：

集合相乘：

就是笛卡尔积,没什么好说的。

幂函数：

\(2^{A}\)={\(A\)的所有子集}

集合的运算律：

• 1.\(A \cup (B \cap C)=(A\cup B)\cap (A \cup C)\)

证明：

\(\forall x \in A \cup (B \cap C)\)

<1>若\(x \in A\),则\(x \in (A\cup B),x \in (A \cup C)\)

\(\therefore x \in (A\cup B)\cap (A \cup C)\)

<2>若\(x \in (B \cap C)\),则\(x \in B,x \in C\)

\(\therefore x \in (A \cup B),x \in (A \cup C)\)

\(\therefore x \in (A\cup B)\cap (A \cup C)\)

综上，\(A \cup (B \cap C)\subseteq (A\cup B)\cap (A \cup C)\)

\(\forall x \in (A\cup B)\cap (A \cup C)\)

\(\therefore x \in A\)

\(\therefore x \in A \cup (B \cap C)\)

\(\therefore (A\cup B)\cap (A \cup C) \subseteq A \cup (B \cap C)\)

\(\therefore (A\cup B)\cap (A \cup C) = A \cup (B \cap C)\)

• 2.\(A \cap (B \cup C)=(A \cap B) \cup (A \cap C)\)

证明：

\(\forall x \in A \cap (B \cup C)\)

\(\therefore x \in A,x \in (B \cup C)\)

\(\therefore x \in A,x \in B,x \in C\)

\(\therefore x \in (A \cap B) \cup (A \cap C)\)

\(\therefore A \cap (B \cup C)\subseteq (A \cap B) \cup (A \cap C)\)

\(\forall x \in (A \cap B) \cup (A \cap C)\)

<1>\(x \in (A \cap B)\)

\(\therefore x \in A,x \in B\)

\(\therefore x \in (B \cup C)\)

\(\therefore x \in A \cap (B \cup C)\)

<2>\(x \in (A \cap C)\)

\(\therefore x \in A,x \in C\)

\(\therefore x \in (B \cup C)\)

\(\therefore x \in A \cap (B \cup C)\)

综上，$ (A \cap B) \cup (A \cap C)\subseteq A \cap (B \cup C)$

\(\therefore (A \cap B) \cup (A \cap C)= A \cap (B \cup C)\)

容斥原理

忘记介绍一种符号了，\(\left | A \right |\) 代表\(A\)集合中的元素个数。
容斥原理的内容：$\left | \bigcup_{i=1}^{n}A_i \right | =\sum_{i=1}^{n}\left | A_i \right | -\sum_{1<=i<j<=n}\left | A_i\cap A_j \right |+......+(-1)^{n-1}\left | A_1\cap A_2\cap ......\cap A_n \right | $

证明：
\(\forall x \in \bigcup_{i=1}^{n}A_i\)在等式左边计算一次
设\(x \in A_{i1},x \in A_{i2},......,x \in A_{ik}\),令\(S\)为\(x\)在右式的计算次数，则：
\(S=C_{k}^{1}-C_{k}^{2}+......+(-1)^{k}C_{k}^{k}\)
根据二项式定理:\((1+y)^{k}=C_{k}^{0}+C_{k}^{1} \times y+......+C_{k}^{k} \times y^{k}\)
令\(y=-1\),得：\(0=1-S,S=1\)
\(\therefore x\)在等式右边被计算一次，等式成立。

映射

有\(A,B\)两个非空集合，若果按照某种确定的对应关系\(f\),使得对于集合\(A\)中任意的一个元素\(x\),在集合\(B\)中都有唯一确定的元素\(f(x)\)与之对应，称为\(f:A\to B\)

在\(f:A \to B\)中，\(x\)的取值范围\(A\)为映射的定义域，\(f(x)\)为\(x\)在映射\(f\)下的象集合\(f(x)=\){\(f(x)|x \in A\)}

单射：

若对于\(\forall x_1 \in A,x_2 \in A\),均满足\(f(x_1)\ne f(x_2)\),称映射\(f\)为单射。

满射：

若\(f(A)=B\),则称映射\(f\)为满射。

一一对应：

若映射\(f\)，既是单射也是满射，称映射\(f\)为一一映射，存在\(f^{-1}:B \to A\)(反函数)，使得:

• 1.\(\forall x \in A\),均有\(f^{-1}(f(x))=x\)
• 2.\(\forall y \in B\),均有\(f(f^{-1}(y))=y\)

构造映射：

\(eg1.\)构造一个一一映射\(f:\)整数集\(\to\)偶数集

\(\forall x \in Z,f(x)=2 \times x\)

\(eg2.\)构造一个一一映射\(f:\)正整数集\(\to\)整数集

\(f(1)=0,f(2)=1,f(3)=-1......\)

\(eg3.\)构造一个一一映射\(f:\)正整数集\(\to\)有理数集

这个对应有点难度，先自己想一想。
先把\(0\)单独考虑，现在每一个有理数可以对应一个最简分数$\frac{p}{q} \(,我们把每个有理数对应一个二元组\)(p,q)$,放到直角坐标系中，形成下图（先只考虑大于\(0\)的有理数）：

我们从\((1,1)\)开始，蛇行向上对应，如果不是最简分数就跳过：

怎么对应负有理数呢，一正一负就行了。

\(eg4.\)是否能构造一个一一映射\(f:\)正整数集\(\to\)实数集

先自己试着构造试试。
不难发现根本不可行，下面是证明：
反证法：
若{\(a_1,a_2,......,a_n,......\)}\(=R\)
取一个实数\(x\)使得:

其中\(b_i \ne a_i\)的第\(i\)位小数。显然\(x\ne a_1,x\ne a_2,.....\)但\(x \in R\),与条件矛盾。

实际应用：

\(eg1.1000\)瓶药水中有一瓶有毒，每次可以取出若干瓶药水混合在一起检验是否有毒。问找到有毒的药水至少需要多少次操作。

这个问题的答案其实不难，10次，但是包含了一些思想。

二分法：最简单的方案，有一个问题，每次操作依赖于前一次操作的结果，若果等待前一次结果的时间很长，这就不是理想的方案。

二进制法：给每一瓶药水二进制编号，不会超过\(10\)位，第\(i\)次操作取二进制从前往后第\(i\)位为\(1\)的药水一起检验，\(10\)次的结果有毒记为\(1\),无毒记为\(0\)，把这十个数字放在一起形成一个二进制数，对应会编号即可。正确性是显然的

更深入一点思考为什么至少要进行\(10\)次操作，我们其实是在建立每一组操作结果与有毒药水编号之间的一一对应，假设进行\(9\)次操作，只有\(512\)个操作结果，无法一一对应\(1000\)个药水编号