cs保研经验贴|离散数学

保研资料：离散数学

关系

笛卡尔积：设A,B是两个集合，所有有序对（x，y）做成的集合称为笛卡尔积。其中x来自A，y来自B。
关系：集合ABC的一个子集F称为A,B,C上的一个n元关系。存储：关系矩阵、关系图。
传递性：等价于R²包含于R。
空关系：反自反、对称性、反对称性、传递性；空集合上的额外多出自反性。可用谓词、蕴含式证明。
商集：以R的所有不同等价类为元素构成的集合。商集是集合的一个划分。
最大元是最小上界；在集合中的上界必是最大元。（最大元、极大元在集合中；上界未必在集合中）。极大元对有限部分序集必存在，但未必唯一。
完备的偏序集：有最小元、每一个链有上确界（或仅含有穷链）。
一个偏序集是一个全序集，如果它本身是一条链。
A包含于B，当且仅当A的幂集包含于B的幂集。

范式

G与其stolen范式S的可满足性、恒假性等价。
主合取范式（存在且唯一）、主析取范式（存在且唯一）；前束范式、skolem范式（首标中无存在量词、母式为合取范式）。
有限个短语的析取式：析取范式。主析取范式由极小项组成：一个短语包含所有原子，且排列顺序与原始顺序一致。
利用主合取范式、主析取范式可求解判定问题：判断命题公式是否等价、求公式的成真赋值和成假赋值、验证公式的恒假恒真性质。

原理

集合：确定性、互异性、无序性、元素多样。
鸽巢原理：将 n 个物体，划分为 k 组，那么至少存在一个分组，含有大于或等于 ⌈n/k⌉ 个物品。
自然数、有理数与代数数：可数无穷，基数为阿列夫0。
证明可数无穷：和自然数一一对应、是可数无穷个可数集合的并集、能按照某种规律排序。
实数：不可数无穷。
康托尔基本定理：集合A的元素不能与A的所有子集建立1-1映射。
命题公式：谓词、量词、逻辑连接词、括号组成的字符串。如果不对符号做出解释，公式无真假可言。
解释：指定公式中原子的一组真值。
形式演绎法：根据基本的等价式和蕴含式。可以随便使用前提、随便使用逻辑结果。
命题：有真假意义的一句话。
谓词：定义在n个个体集合的笛卡尔乘积上，输出是1或0 的n元函数。谓词包含常量、变量、函数，是一个命题函数。零元谓词即命题，一元谓词描述性质，二元谓词描述关系。
谓词逻辑的改名规则：当同一个变量在不同的量词辖域中出现时，需要使用不同的名字；当一个变量既作为约束变元又作为自由变元出现时，需要将约束变元换名。改名的目的：为了规范使得个体变元要么以约束出现，要么以自由出现，方便前束范式化。

命题逻辑的缺陷：无法表达量化关系；忽略命题内部结构，将原子命题视为不可分割的整体；难以表达关系命题。
什么是谓词逻辑：拆解原子命题，引入个体、谓词和量词，描述对象间的逻辑关系。
什么是命题逻辑：将完整陈述句视为不可分割的原子命题（如 P, Q），仅关注命题间的逻辑组合关系（与、或、非、蕴含、等价、异或、同或）。
幂集：原集合中所有的子集（包括全集和空集）构成的集合

欧拉图

通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路，具有欧拉回路的无向图称为欧拉图；通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。
1.对于无向图 G , G是欧拉图当且仅当 G 是连通的且没有奇度顶点。
2.对于无向图 G , G是半欧拉图当且仅当 G是连通的且 G中恰有 0个或 2个奇度顶点。
3.对于有向图 G, G是欧拉图当且仅当 G的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。G是半欧拉图时仅G是单向连通的，允许两个顶点入度出度相差1。
欧拉路未必是简单路，哈密顿路一定是简单路。