计科八股20260629——离散数学复习（数理逻辑、集合论、代数结构，图论明天补）

这是我原来写的笔记

8张笔记带你打穿《离散数学》

Part 1 数理逻辑

双否律、幂等律、交换律、结合律、分配律、吸收律、德摩根律、同一律、零律、排中律、

蕴涵等值律、假言易位律、等价易位律

ps：这一部分看一遍就想起来了。

范式、主范式、合取范式、析取范式

这边不太好记起来的是极小项极大项

极小项是当且仅当PQR取这个数时，这个式子为1。

极大项是当且仅当PQR取这个数时，这个式子为0。

这一部分不怎么重要。

从这里开始进入高能。但还是属于较简单的范畴。

化简规则、附加规则、合取引入规则、假言推理规则、拒取式规则、

析取三段论规则、假言三段论规则、构造性两难规则、前提引入规则、结论引入规则、置换规则

两大题型：附加前提法（CP规则法）、归谬法（反证法）结论否定引入。

在这里我看到这两题就懵逼了一下，P和否PvQ怎么推出Q的，查了一下是蕴涵等值律。

否PvQ等价于P->Q，而已经有P，故已经有Q。

那么在这里复习一下蕴涵等值律：这里包括三种合理的情况：P1Q1，P0Q0，P0Q1，最艾斯比的是P0Q1的情况，不好从实际角度去理解，你可以理解为好比Q是一个公理，无论P的对错Q都是对的，所以P不论对错都能导出Q（难绷）。而P1Q0这就显然是不行的。

这一部分就是辖域有点抽象。

这里有点看不太明白了，蕴涵等值跟这个有啥关系，主要是括号的问题。

• (∀x)(A(x) → B)：对任意 x，只要 A(x) 成立，B 就成立。

• (∃x)A(x) → B：如果存在某个 x 使 A(x) 成立，那么 B 成立。

原来下方有一个条件是x让Ax成立，上方是默认Ax成立！

然后演算推理相对没什么，UI，UG，EI，EG。UG是不能瞎做的情况。

Part 2 集合论

最重要的是幂集P(A)，例如A={0,1}则P(A)={空集,{0},{1},{0,1}}。

理解难度不大。

从这里开始有点搞了。互斥但不对立意思是：一个关系可能不是自反也不是反自反，比如{<1,1><1,2>}。

对称性和反对称性则可能同时发生，也可能都不发生。

传递性就好理解。

这里我记得期末出了一道商集的题，我傻眼了，完全不记得这是啥。其实就是等价类的集合。

这里哈斯图最重要，一定要学会。

上面的例题代表整除关系：设A={1,2,3,4,5,6,7,8,9,10,11,12,24}，偏序集S={A,《 },其中《为整除关系，请画出S的哈斯图。

Part 3 代数结构

直到这里其实也还好。。。

从此刻开始，战争由我一人主宰！半群来了。

半群一定拥有可结合性。

可交换半群、子半群、积半群、同态。

群：半群且含有幺元且全有逆元，就是半群->独异点->群。

一个群拥有的性质：可结合性、有幺元、每个元素均有逆元。

阿贝尔群：在此基础上有可交换性。

阶数：群的元素个数。

元素的阶：让x^k=e成立的最小正整数k。记作|x|=k。

子群、平凡子群、非平凡子群。

子群判定定理，感觉不太重要，没细看。

陪集就是H是G的子群，那么a∈G，a和H里每个运算得出来的结果构成一个集合，叫做左陪集。同理有右陪集。

拉格朗日定理：子群的阶数一定是群的阶数的因子（先得回去看懂阶数，然后再感叹定理的玄学）

我们那年的期末考试求证质数阶群都是循环群，6分直接干瞪眼。