离散数学基础
[一]集合论
集合论是非常简单又基础的，在高中数学的第一章便是集合论，因为内容重复，我只简单地提一句。
集合要有以下性质：
- 互异性：集合内没有重复的元素，比如{1,1,2}和{1,2}表示的是同一个集合
- 无序性：集合内元素没有先后顺序，{1,2}和{2,1}也是一回事
- 确定性：元素一定可以被确定是或否属于集合，像“高个子的人”这种没个准话的描述就构不成集合
元素和集合的关系用属于和不属于表示，元素a在集合A里记作$a∈A$，不在就记作$a∉A$。另外还有一个特殊的空集，里面一个元素都没有，记作$\varnothing$。空集是任何集合的子集，这个性质做题的时候经常碰到。含有n个元素的集合，它的子集一共有$2^n$个，因为每个元素都有“选”和“不选”两种可能。
集合的关系与运算
集合之间主要有子集和真子集的父子关系，或者集合相等，也就是两个互为子集的集合，一般记作A=B。这里把话说全一点：如果A里的每个元素都在B里，就说A是B的子集，记作$A⊆B$；如果A是B的子集并且A不等于B，那A就是B的真子集，记作$A⊂B$；两个集合互相为子集，也就是$A⊆B$且$B⊆A$，这时候才能写A=B。集合的表达常用的有三种，描述法，列举法，Venn氏图法，描述法就是对集合内的元素的区间加以描述，比如：
- A={ 所有的地球人 }
列举法就是列举出集合内所有元素，比如：
- B={ Minloha，Minloha的女朋友 }
Venn氏图法可以通过直观的图形描述，这里就不举例了。
集合的运算
集合运算是简单的，同样的，集合运算也适用于概率论中事件的运算。集合运算有以下几种
- 交集：取出集合的公共部分，组成新的集合$A∩B$
- 并集：将集合所有元素构成一个新的集合，新集合要满足集合的性质记作$A∪B$
- 补集：从全集U中取出不属于该集合的元素，组成新的集合，记作$\bar A$或者$C^A_U$意为在全集U中的补集
- 差集：从一个集合中拿出另一个集合的部分，记作$A-B$,公式可以写作$A∩\bar B$意为A与B补集的交集
- 对称差集：指集合交集在并集中的补集，记作$A⊕B$，表示的集合是$(A-B)∪(B-A)$
光看定义有点绕，随手举个小例子就清楚了。设全集U={1,2,3,4,5}，A={1,2}，B={2,3}，那么$A∩B$={2}，$A∪B$={1,2,3}，$\bar A$={3,4,5}，$A-B$={1}，对称差$A⊕B$={1,3}。差集和对称差的区别就在这：差集只挖掉公共部分，对称差是两边各自独有的部分都要。另外注意，补集是相对全集说的，同一个集合换个全集，补集就完全不一样了，做题的时候先把全集是谁看清。
这里主要有几个常用的公式：
- 分配律
- $A∩(B∪C)=(A∩B)∪(A∩C)$
- $A∪(B∩C)=(A∪B)∩(A∪C)$
- 吸收律
- $A∩(A∪B)=A,A∪(A∩B)=A$
- 德摩根律(记得变号)
- $ \overline{(A∪B)} = \bar A∩\bar B$
- $ \overline{(A∩B)} = \bar A∪\bar B$
这些定律都可以通过Venn图表示证明，都是非常简单的。德摩根律两个式子可以一起记：长杠拆开，并变交、交变并。
集合的限度
集合可以分为有限集和无限集，而无限集又分为可数集合和不可数集合两类，我们把映射的含义拿来定义可数集合，规定自然数集N，如果集合与N存在对应关系Ψ使得集合与N之间每一个元素都存在一一对应关系，那么就说这个集合是可数的。也就是说，能不能给集合里的元素挨个编号，编号用的还是自然数，能排成一列一个个编下去就是可数。而这个运算关系，也可以理解为是在计算集合的势，所以也可以说是集合与自然数集N等势。等势集合一般记作下面的形式：
很像映射，也确实是一种映射关系。
如果集合A与自然数集N等势，那A是可数集合，记作$\aleph_0$读作阿列夫零。自然数集、整数集、有理数集都是可数的，有理数那个稍微绕一点：每个有理数都能写成两个整数的比，按分子分母之和从小到大排就能把它排成一列，一个个拿自然数编号，所以有理数看着比自然数密得多，数量上却是一样多的。而不可数集合就是与$(0,1)$开区间等势的集合，记作$\aleph$。实数集是最典型的不可数集合，$(0,1)$里的实数没法排成一列，不管你列出多少个，总能构造出一个不在表里的新数，这个证法叫对角线法，这里就不展开了。
而判断集合是否是可数的集合，只要找出对应的关系Ψ就可以了，能建立一一对应就是可数；反过来要证不可数，就得说明这样的对应关系根本不存在。
集合的应用
集合用于描述解决方案以及列举描述元素，它主要应用于概率论中，在离散数学我们几乎只涉及其表示方法，下面是一个例题，可以参考一下
传说在20人中，一定有10人是会编程的，10人会唱歌的，6人既会编程又会唱歌，问既不会编程又不会唱歌有几人
可以设所有人为全集U，会编程的人组成集合A，会唱歌的组成集合B，可以写出$A∪B$,就是所有会编程和会唱歌无重复元素的集合，那么它的补集就是要求的集合（竖线$|A|$表示集合里元素的个数），$|A∪B|= |A| + |B| - |A∩B|=10+10-6=14$，那么补集大小就是20-14=6，所以有6人既不会编程又不会唱歌。
这里面用的就是容斥的思想：把重复算的6个人扣掉，剩下的14个是至少会一样的，再拿总数一减就完事了。
[二]计数原理
这里在高中教材中同样有，这里的难点不是在计算，而是在思考解决问题的算式。同时在描述一些复杂的流程或者是在学习概率论的分布时，都会接触计数原理的内容。
计数原理在离散数学中主要介绍两个计算原理和两种数(排列组合)，如果感兴趣可以在文末的评论区留言，我可能会出一期排列组合的博客，讲一讲常用的排列组合模型！对高考生也是有帮助的哟~
乘法与加法原理
乘法原理主要讲的是如果一件事情需要分成若干步，每一步都有不同数目的选择，那么最终可以产生的方案就是不同步骤下选择的乘积。即$n_1×n_2×n_3×n_{….}$，举例说：Minloha要从北京到上海，再去深圳。假设北京到上海有7种交通工具可以选择，上海到深圳有8种交通工具可以选择，那么Minloha可以有几种方案到达深圳？
很简单，7×8=56就可以了，这就是乘法原理的应用
加法原理主要讲的是分类的情况，比如处理一件事有AB两种情况，那么只需要把不同情况下的选择数加和就可以了，也可以写作$i_1+i_2+i_3+i_{…}$，举例说：Minloha已经到达了深圳，现在Minloha要去买一台电脑，A电脑店有20台电脑，B电脑店有10台电脑，请问Minloha有多少种选择？
答案很简单，就是20+10=30，也就是把具体的情况加和
这两个原理的分界就看事情是“分步做完”还是“分类做完”：一步步走完用乘法，几种并列的情况挑一种用加法，后面排列组合的公式都是从这两个原理推出来的。
排列组合
排列组合主要是他的含义，排列数在高中教材被写为$A_n^m$表示从n开始向减小的方向乘以m个数字，概率意义是从n个元素中有顺序的抽取m个。计算可以看例子，比如$A_4^2$表示从4开始向后乘两位，即4×3=12，而在《离散数学及其应用第三版》中将他写作$P_n^m$，表达的含义是一样的。对于排列的计算可以有公式：
这里的$n!$是阶乘，$n!=n×(n-1)×…×2×1$，规定0!=1。公式也好理解：排队的时候第一个位置有n种选择，第二个剩n-1种，接下去一直乘m项，就是分子上那段，分母的$(n-m)!$正好把后面用不上的项约掉。
而组合数同样地记作$C_n^m$表示从n个元素无顺序的取出m个，计算可以写作以下格式：
组合和排列就差一个要不要排队：选出来的m个元素自己内部全排列有$m!$种排法，所以组合数就是把排列数除掉$m!$。组合数还有个很好用的性质$C_n^m=C_n^{n-m}$，从n个里挑m个拿走，和挑n-m个留下是一回事。
应用
应用主要讲两个原理，对于高中学过排列组合的一定都背过那些模型，插空隔板什么的。
对于常用的排列组合模型，我就不细说，直接一道题看看
将标号为1、2、3、4、5、6的6张卡片放入三个不同的信箱中，如果每个信箱放两张，其中标号1、2放入一个信箱中，则不同的分发有几种？
解析：因为1、2已经确定，只要分3、4、5、6就可以了，有$C_4^2C_2^2$种；而装有1、2的信箱可以是3个中的任意一个，所以结果要乘以3。
答案是：$3×C_4^2C_2^2$=18种
容斥原理
所谓容斥原理，说的其实很简单，就是人们排斥不想要的，包容想要的，但有些问题比较特殊，需要包含错误内容作为补偿，这个原理就叫容斥原理，在高中数学中主要体现在计算模型：总体剔除，定序缩倍。名字本身也挺好记，容是加回来，斥是减出去，用公式写就是$|A∪B|=|A|+|B|-|A∩B|$，多加的那部分交集减掉一次，三个集合的话式子还要长一点
规律就是加加减减来回倒：多加的减掉，多减的加回来。
抽屉原理
这是一个在小学学习的内容，简单的说，你有5个苹果，要放进4个抽屉中，不管怎么放，必然有一个抽屉里面至少有两个苹果，这就是抽屉原理，哪怕有的抽屉空着也不影响这个结论。推广一下就是kn+1个东西塞进n个抽屉，必有一个抽屉里至少有k+1个东西。
最后简单的来一个排列组合问题，高中难度的哟！
公司安排5位员工前往3个地点出差，要求每个人都要去，每个人只要去一个地方，请问有几种方案？
答案是：$3^5$=243种方案
这题用的是乘法原理，5个人各自独立地在3个地方里挑一个，每个人3种选择，乘起来就是3的5次方。
总结
集合和计数这两块就聊到这里，内容看着简单，但后面讲关系、图论、概率论的时候都得拿它们打底。集合重点是记几个运算律和可数性的判断思路，计数就一句话——分类用加法，分步用乘法，剩下的靠做题找感觉。排列组合的常见模型以后有机会再单独出一期，有想看的同学评论区见。