离散数学与证明方法 · 小纸条

核心机制：并交差、补与对称差的核心是：集合恒等式可用元素追踪或指示函数证明，补集必须相对全集；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为并交差、补与对称差手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：维恩图只能帮助发现，不自动覆盖任意元素。

核心机制：集合、子集与幂集的核心是：集合以成员资格定义，子集按全称蕴含，幂集元素是原集合的子集；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为集合、子集与幂集手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：元素与单元素集合、属于与包含不能混用。

核心机制：函数、复合与逆像的核心是：函数给每个定义域元素唯一像，逆像对任意函数都定义且保持集合运算；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为函数、复合与逆像手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：逆函数只在双射时存在，逆像不是把函数倒着算。

核心机制：笛卡尔积与有限集合计数的核心是：有序对区分位置，乘法原理给有限积集大小；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为笛卡尔积与有限集合计数手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：A×B通常不等于B×A，空因子会让整个积为空。

核心机制：二元关系与表示的核心是：关系是笛卡尔积子集，可用有序对、矩阵和有向图表示；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为二元关系与表示手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：矩阵对称不等于传递，表示改变不能改变关系语义。

核心机制：单射、满射、双射与基数的核心是：单射防碰撞、满射无遗漏、双射建立等势；证明要覆盖任意元素；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为单射、满射、双射与基数手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：有限集上的单射满射等价不应无条件推广到无限集合。

核心机制：等价关系与偏序的核心是：等价关系形成划分，偏序满足自反反对称传递并产生Hasse图；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为等价关系与偏序手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：反对称不是不对称，偏序中元素不必两两可比。