命题必须是断言 **仅当-> 1 -> 0 才为假 ** 仅当后面是结果，例如只当A，B 为B->A

当且仅当<->，第一个是充分条件，第二个是必要条件

重言式(永真式) 矛盾式(永假式)既不是重言式也不是矛盾式，称为偶然式

所有指派都是真的，永真的，if有->它是永真的，if是<->则为永真式

证明永真蕴含式，前真则后真，后假则前假

情况并非如此 就是加个非

用非和和和表示可以先找出用或表示的表达式，然后不是

有些公式简化结果不同，可以 与（P或非P）

对偶规则：不变元，不变， 只变和，或，量词

分析范式：基本积之和 合取范式:基本和积累 P既是基本的，也是基本的 极小项：在基本积每个变元必须出现一次，而且只出现一次，n个变元有2个n次方极小项

极小项之和为主析取范式，加非为0，反之亦然 注意补全

极大项：在基本和中。。。 非为1，反之为0

注意！！！找出主析取范式后，可以直接找到主合取范式，如主析取范式{0、1、2、7} 主合取范式为{3，4，5，6} ,数字不同，但范式中每个变元的非情况可能相同

P29 CP规则可以用来证明包含式

反证法 很有用P30 将结论取反作为条件使用，最终证明上非A可以

个体：张三 3等 个体变元代表个体的变元位 谓词描述个体性质或个体之间的关系有多少？个体变元是几元谓词 讨论域:个体变元的取值范围在个体域空集不能作为讨论域 命题是0元谓词 在谓词之前量化后，命题的真假论述域相关(先看论述域)！ 存在y，y=3 不一定是真的，如果讨论域>3，就是错的 全总个体域：包括所有个体

针对整个体域，M(x)是人，是特征谓词(描绘讨论对象具有人的特征)特征谓词加入断言有两个条件:（P37） 对于全称量词，特征谓词作为包含前件加入 而对于存在量词，加入合取式

原子公式:不含命题联结词(非、和、等)。

量词紧接后的最小子公式是量词的辖区

存在x，或者任何x时，辖区内x（注意必须是x，若辖区内有y但无y等，y仍然是自由变元）为约束变元，辖区外为自由变元。

否定词可以通过量词深入辖区

证明公式不等价，可以直接举例

注意量词辖区的扩张和收缩 量词分配的恒等式(任意、存在或恒等式) CP规则 Q1

量词的顺序很重要！

更名规则只能用于约束变元，代入规则只能用于自由变元（原式为永真式，代入仍为永真式，原式为非永真式，替换可能会改变）。

去量词时，量词必须是公式最左边的量词，量词前面没有符号， 其辖区作用于公式末尾。

[外链图片转存失败，源站可能有防盗链机制，建议保存图片并直接上传(img-oSwActYF-1654527431830)(C:\Users\fanshihao\AppData\Roaming\Typora\typora-user-images\image-20220526210931066.png)]

US :

ES: 不能是前面推导的自由变元，也不能是ES表面自由变元本身引入的表面自由变元

EG:

UG: 1. x既不自由，也不自由ES引入的 2. 如果US自由变元x引入后，ES如果引入新变元y并自由出现，则不能使用UG

US和ES删除量词，使用ES而产生的变元不能保留在结论中，因为这只是暂时的假设

如果在推导过程中使用，US又要用ES,先处理存在ES,在使用US

集合和交是可交换的，可以与分配率相结合

自然数(0，1，2，3…)N 正整数N

实数R

整数I

五种运算 并 交 差（-） 补

n收集个元素A，其**(集合A中所有子集)**元素数为2n次

n重组的第一部分是n-1重组

集合笛卡尔乘积运算不能交换，也不能结合法律

偏序集合自反、反对称、传输

为什么哈斯图可以表示偏序关系:偏序关系是反对称的，所以可以用无向图表示，有传递关系，不需要画多余的传递边缘

哈斯图画法

[外链图片转存失败，源站可能有防盗链机制，建议保存图片并直接上传(img-IS7vi0By-1654527431832)(C:\Users\fanshihao\AppData\Roaming\Typora\typora-user-images\image-20220527191654471.png)]

哈斯图的画法，以及利用哈斯图寻找大元等 - 知乎 (zhihu.com)

在确定最大元最小元之前，先判断极大元和极小元：在子集B中，顶部行为值很大，底部行为值很小，不是唯一的

判断最大元和最小元：如果最大（小）值是唯一的，则存在最大（小）值，否则不存在

如果存在最大元和最小元，那一定是唯一的

上界和下界：注意两者必须有关系！，如{6、12、24}上界没有36，因为与24无关

注意！！！所选上下界必须与子集中的所有元素有关，可能不是子集，也可能包括子集

极大的元极小元一定存在 最大元，最小元，上下界不一定存在

[外链图片转存失败，源站可能有防盗链机制，建议保存图片并直接上传(img-yNSUyvlo-1654527431834)(C:\Users\fanshihao\AppData\Roaming\Typora\typora-user-images\image-20220527193458015.png)]

最小上界和最大下界：上界里面最小的和下界里面最大的

如果有最大元，则一定是最小上界，最小元同理

子集为{2，6，8}时

上界为24 12，36不是上界，因为都和8没有关系

下界为1 2 3和2，8无关，不是

拟序集合：集合A上的二元关系R是反自反，反对称，传递 例如实数集合中的<关系

线序集合：对于偏序集合A中，任意两个元素都有关系 哈斯图就是一条链，无分支

良序集合：A上的二元关系R是一线序，则A的每一个非空字节都有最小元素（极小元素存在且唯一），则R叫做A的良序。

每个有限线序集合是良序的

等价关系R是自反，对称，传递的。

模k等价：其含义为等价类里面的任何数，模k之后都相等。k为几就有几个等价类

等价类：与集合A中x具有R关系的y的组成集合，其中R是等价关系

不同等价类的个数称为R的秩 集合A的等价关系，要么相等，要么不相交

集合的覆盖与划分

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ylBKvdVS-1654527431835)(file:///C:\Users\fanshihao\Documents\Tencent Files\1360532588\Image\C2C\Image1\7S3DXDIHU8C535ZC8_T%}7.png)]

单射函数（一对一，但B中可以有多余元素没有被A指向，但如果指向了必须只有A中的一个元素指向B）： 满射：B中元素都有至少一个相对的A的元素 双射：满足单射和满射，真正意义上的一对一

代数是一集合，运算封闭，具有代数常元

幺元与任何元素运算都是其元素本身

零元与任何元素运算都是零元 零元不存在逆元

左右幺元是对集合中是所有元素来说的

左幺元和右幺元相等则存在幺元，顺序搞清楚

零元同理

一个运算的幺元和零元是唯一的

逆元：xy=1，x是y的左逆元，y是x的右逆元，1是幺元 若xy=1 y*x=1同时成立则x是y的逆元（y也是x的逆元）

对于每一个元素，如果元素存在逆元，则唯一

可逆一定可约，但可约不一定可逆

子代数运算封闭，基本是原集合的子集，代数常元在子集中，但原集合的代数常元不一定是子集的代数常元

子代数一定存在，最大是它本身

同态：存在一双射函数h

映射h为A到A撇的同构（双射函数）

A与A撇同构，ARA撇，R是二元关系

若h不是双射函数，只是一普通函数，其余与同构条件相同，则h是从A到A撇的同态

若h是单射函数，则称h为单一同态

若h是满射函数，则称h为满同态

双射就是同构

若A=A撇 则称h为自同态

若A=A撇并且h是同构 则称h为自同构

同余关系是等价关系的一种,它需要具备等价关系的特点，即传递，对称，自反除了具有等价关系的特点，还需要有已知a_b，则a*cb*c且c*a~c*b，*是代数A中的关系

相等关系是任何代数上的同余关系

具有结合律的代数称为半群 子半群是半群

半群含幺元称为独异点（含幺半群） 子独异点也是独异点

加法和乘法符合结合率，减法和除法不符合（不一定，主要看集合）

若运算可交换，则为可交换半群

在任何可交换独异点S中，S等幂元素的集合T可构成子独异点

在半群中，等幂元素可能不止一个，但在群中，幺元是唯一等幂元素

生成元（不是幺元，但幺元为生成元的0次幂） 如果在独异点中，存在一个元素a属于S，a可以表示S中其余任何元素，则该独异点为循环独异点，a为生成元，由生成元生成循环独异点。

并不是所有的独异点都具有生成元。但循环独异点都是可交换的，即为可交换独异点

独异点的子半群（只要求集合T属于S就行）可以是个独异点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5eu2E5Kj-1654527431836)(C:\Users\fanshihao\AppData\Roaming\Typora\typora-user-images\image-20220604181246928.png)]

群中只有幺元是等幂的。

群的定义：除了具有半群（可结合）和独异点（存在幺元）的性质外，还具有一性质：每个元素都存在逆元的代数系统

群还具有消去律

幺元是群中唯一的等幂元

所以如果有零元则一定构不成群，因为零元没有逆元

如果还具有可交换的性质，则为可交换群或者阿贝尔群

群的阶数为群中元素的个数，元素的阶数为元素a^k=e的k的最小值（元素和逆元具有相同的阶数

{e,a^1,a2}则该群为三阶，因为e=a^3

置换群定义：n个元素组成的集合A，(置换有n!个)，A上的置换（不一定是所有置换）所构成的群称为n次置换群，所有置换所构成的群为n次对称群

循环群：循环群是由g生成的，g为生成元。循环群是可交换群 类比于循环独异点（不同点是幺元是生成元的0次幂） 生成元都不一定为1个

if G为有限循环群 并且 |G| = n 则 g^n=e

在有向图中，任意两个结点，至少有一个结点能直接到达另一个结点，则为单向联通

若任意两结点都互相可到达，则图为强连通

若任意两结点不能相互到达，但把方向去掉，可联通，则为弱连通图

欧拉图的判定：无向连通图，顶点次数都为偶数

判断是否存在欧拉路径：该无向连通图存在0个或者两个奇次次数的顶点

哈密顿图