// 待更新补充
// 12-24刷夜做学术记录点
// 12-26睡醒记录点, 稀有概念已经刷完, 此博文不再更新
逻辑大章
- 对偶原理 P13
A(~P, ~Q, ~R) <=> ~A(P, Q, R), 其中A为A中所有逻辑取反
- 辖域扩张 P37
(ranx)A(x)VP = (ranx)(A(x)VP)
- 量词分配 P38
任意x(ranx)对合取满足分配率, 存在x(existx)对析取满足分配率
- 前束范式 P44
所有量词均非否定的出现在公式最前面
二元关系
- 关系在集合上的限制 P69
对A集合上的关系R, 如果有R限制在集合B上, 对序偶<x, y>只取x∈B的那部分
- 最大相容类 P92
X集合中的子集A, 对A中任意元素满足对X集合中满足相容关系, 且X-A集合中不存在与X集合中满足相容关系的元素
- 相容关系 P91
自反, 对称的关系, 比如{2166, 243, 375, 648, 755}中关系R: <x, y>, x与y有相同的数字
- 良序关系 P99
全序关系中每一个非空集合都有最小元
- 全序关系
对偏序集合中, 对每一个x, y 都有x <= y或 y <= x, 则全序, 比如格
- 拟序
偏序: x <= y, 拟序: x < y
集合论与函数
- 包含排斥原理 P60
总基数 - 1集合基数 + 2集合基数…..
- 特征函数 P118
对全集中的集合A, 如果全集中元素在A中, 则特征函数记为1, 反之记为0
- 函数缩小与扩大 P109
g是f在A上的缩小则记为 g = f/A
- 基数 P120
等势：如果集合A与B之间存在双射函数，则等势, 记作A~B
和自然数等势的无限集基数为阿列夫0
和实数集等势的无限集基数为阿列夫1
阿列夫0 < 阿列夫1
代数系统与群论
- 同余关系 P144
满足代换性质的关系叫做同余关系
同余关系是一种等价关系
x1,x2,y1,y2在集合S中, 有关系E， 使得x1Ex2, y1Ey2, 使得(x1代数系统中定义的运算x2)E(y1代数系统中定义的运算y2), 则关系E叫做同余关系
- 商和积代数 P146
商集: 集合S上等价关系R, 引出的所有等价类集合的集合叫做S的商集,记作S/R
商代数: 同余关系E引出的商集S/E, 构成的新的代数结构<S/E, *>称为商代数
积代数: 两个代数系统<S, +>, <T, *>同类型, 则积代数为<S笛卡尔乘积T, circle>其中<x1, x2>, <y1, y2> 如果在S笛卡尔乘积T中, 则两者circle之后为<x1 + x2, y1 * y2>
- 子群性质 P160
中心: 可交换的子群则为该群的中心, 对阿贝尔群G, G的中心就是G
子群格: <L(G), 包含关系>这是一个偏序关系, 也可以构成格.
- 拉格朗日定理
群的阶数必能整除子群的阶数
六阶群中必含有三阶群
- 循环群与置换群 P164
对称群: 集合上所有的双射和复合运算构成的群叫对称群
三次对称群S3: 为六个置换组成, 比如S = {1, 2, 3}, 则六个置换分别为{(1, 2, 3), (1, 2, 3)}….(满足双射的六个对应关系)
- 域 P169
环: 形如<R, +, *>的代数系统叫做环, 其中+满足交换群, *满足半群
可交换环: 如果<R, *>满足交换律, 则是可交换环
域: 在可交换环中, 如果去除<R, *>的零元之后, 能让这个半群变成群, 则<R, +, *>叫做域
<R, +, *>, <Q, +, *>都是域, <Z, +, *>不是域
所以一个代数系统<H, +, *>要是域, 需要满足这么几个条件:
- <H, +>是阿贝尔群
- <H, *>是阿贝尔半群
- <H - {0}, *>是阿贝尔群
图论
- 关联矩阵 P206
有向图里, 把邻接矩阵的入度变成-1就是关联矩阵
- 二部图 P220
二部图是基于无向图的
二部图满足这么几个条件:
- 顶点可以划分为两个部分, 每个部分里的元素两两不相邻
- 所有回路长度都为偶数
- 最大边数 m = [n^2 / 4], 取整
二部图匹配图每个结点的度都为0或1
当匹配图中结点度为1的点达到最多的时候,则为最大匹配
如果有一个部分, 没有结点度为0的点, 则这个最大匹配叫做完美匹配
- 平面图 P224
能画出边在图形上不交叉的图, 则为平面图
五阶图和六阶图只要不含有库拉托夫斯基图, 则为平面图
库拉托夫斯基图, 一个是水晶形, 一个是完全五阶图
- 对偶图 P228
看一眼就能懂的东西, 不细说了
树
- 有向树 P264
一个结点入度0, 其余结点入度1的弱连通图, 比如二叉搜索树, 不能前溯
- 有序树 P267
兄弟之间有大小顺序, 比如说哈夫曼编码数, 兄弟位置不能随便移动