离散数学推理与证明方法
用定义证明（最基本）
数理逻辑
- 基本等值式
- 推理定律
- 直接证明法
- 附加前提证明法
- 反证法（包括消解法）
- 替换规则（整体思想）
- 构造证明（难想到）
集合论
- 集合恒等式，等值式
- 证明相等可以证明相互包含
- 证明递归可以用数学归纳法（幂运算）
- 空集属于任意一个集合。
证明时往往会去寻找简单的证明思路。
- 证明相等时如果等式左右两边都比较复杂，可以把左右两边化简，得到相同的中间结果，即可证明相等。如果一边简单，另一边复杂，往往从复杂的一端出发证明。
- 集合论中证明两个集合相等可以证明相互包含。线性代数中证明两个矩阵A和B的秩相等r(A) = r(B)可以证明r(A) <= r(B)且r(A) >= r(B)。基数中证明等势可以利用SB定理构造两个单射证明相互优势。群中证明元素阶相等可以证明相互整除。
- 证明充分必要或者等值可以用等值式直接证明，也可以从充分性和必要性两个角度证明。
- 如果证明的结论较强或者较复杂，可以从结论的反面出发，使用反证法证明。证明不存在一般可以用反证法。
- 如果用定义证明时需要的条件很苛刻，数学家们不断寻找简单的证明方法，将苛刻的条件变得简单一些，例如证明等势如果用定义需要构造双射，SB定理提供了简单的方法构造两个单射。
- 证明连等式，如果较少，可以分别得到相同的中间结果，如果较多，可以采用环状证明1=>2=>...=>n=>1。
- 如果要证的结论简单而且已知条件比较少，有时会构造一些和已知条件或要证结论有关的条件帮助证明。
- 证明唯一性，可以假设存在两个，然后证明这两个相等或者用反证法证明。
- 存在性定理的证明中可能有解题思路和隐含信息。
- 分类讨论时要完整，考虑所有可能的情况，不能遗漏。
- 数学归纳法一般用于证明有规律、递推、整数的结论，证明时一定要用到假设。
- 证明时如果第一问比较难，后面问题简单，可以先做后面问题，并且证明时可以用第一问的结论。
复习
数理逻辑
公式的类型（3种）：重言式、矛盾式、可满足式
基本等值式
推理定律
推理规则
先消去存在量词或者全称量词，再用推理规则
集合论
集合：
一般集合元素为x，集族元素为集合
集合恒等式
对偶原理，对偶式同真假，方便记忆
容斥原理
对称差：交减并，只有交集对对称差有分配律
集合包含或相等的证明方法
幂集，集族，广义交（任意），广义并（存在）
卡氏积
二元关系：
证明时，有时候证明有序对<x,y>整体属于A×B，有时候分别证明x,y属于两个集合A,B
A到B的二元关系是卡氏积A×B的任意子集
定义域dom，值域ran，域fld
逆，合成（复合，逆序合成）
限制（有序对），像（在限制条件下的值域），注意求法
单根（任意y唯一存在x）根就是x，单值（任意x唯一存在y）
关系矩阵M(R)：正交矩阵
关系图G(R)：元素为顶点，有序对为有向边
关系的性质：画关系图看直观，证明
自反，反自反，对称，反对称，传递
幂运算（合成），零次幂为恒等关系，周期性
关系的闭包：扩充、最小
性质，求法
注意传递闭包和对称闭包组合的性质：1.若R传递，则r(R)传递，但s(R)不一定。2.st(R)包含于ts(R)。反例：R={<a,b>}
等价关系：自反、对称、传递，等价类，典例：模n同余关系
商集，划分，等价关系和划分一一对应，第二类Stirling子集数（求划分或者等价关系的个数），划分的加细（划分是自身的加细）
序关系：
偏序关系：自反、反对称、传递，偏序集
全序关系（线序）：x与y可比，全序集
拟序关系：反自反、反对称、传递，拟序集
典例：整除，大（小）于，集合包含，划分加细
哈斯图
最大元，最小元，极大元，极小元，上界，下界，最小上界（上确界），最大下界（下确界），画哈斯图看直观
良序关系：拟全序集，任何非空子集均有最小元
链（可比），反链（不可比）
函数：单值
偏函数=全函数+真偏函数
自然映射
满射（值域满）、单射（单根）、双射
象y，原象x
函数的合成，反函数（单根）
基数：
证明等势的方法：1.直接构造双射。2.传递性。3.SB定理构造两个单射。
等势
N≈Z≈Q≈N×N
R≈(0,1)
无穷基数：|N|≈阿列夫零，|R|≈阿列夫，|P(N)|=2的阿列夫零次方，|P(R)|=2的阿列夫次方，阿列夫=2的阿列夫零次方
基数比较、运算
代数结构
反之不然=其逆不真=逆命题不成立
不满足=举一个反例即可
由运算表判别算律的方法：
一个运算（交换律，结合律，幂等律），两个运算（分配律，吸收律），消去律（非零元唯一）
单位元，零元，可逆元，幂等元
0是模k加法的单位元，1是模k乘法的单位元
载体是非空集合
子代数：运算封闭，一定包括代数常数，注意验证零元运算封闭，平凡子代数（最大、最小）
积代数：保持因子代数的性质（消去律不一定保持）
同态映射（同态）：
证明同态：对所有运算保持等式（零元、一元……）
同态性质，满同态保持原代数的性质（消去律不一定保持）
同构（双射）
同态像（函数值）
f导出的同余关系（函数值相等）=载体等价关系+运算置换性质
商代数：保持原代数的性质
两种证明同构方法：1.f是同态且f是双射。2.同态基本定理（代数系统的同态像同构于它的商代数）。
半群：封闭、结合
独异点：封闭、结合、单位元
群：封闭、结合、单位元、逆元，3个等价定义，性质，群的阶，元素的阶
子群：3个判定定理，生成子群，子群格
循环群：生成元（无限：a和a逆，有限：欧拉函数），子群（无限，有限：正因子，生成元做幂运算），循环群是交换群
变换群：变换乘法（函数合成）
置换群：置换（n元），轮换（k阶），对换（2阶），置换乘法，置换求逆，轮换分解（唯一、不相交），对换分解（不唯一、可相交），轮换指数
陪集：Lagrange定理
正规子群：判断定理
(m,n) 最大公约数
[m,n] 最小公倍数
x|y 表示x整除y，即x是y的因子，x是除数，y是被除数
x mod y 表示x模y，即x除以y的余数