离散数学学习笔记

离散数学I

第一章 集合论基础

有穷集,无穷集.子集,真子集(真子集符号是$\subset$不是高中学的$\varsubsetneqq$)

元素数:有穷集合的元素个数,记作$|A|$.

几个特殊集合:全集$E$,空集$\varnothing$(没有任何元素),

几种运算

1. 幂集$\rho(A)$
   每个元素都有出现或不出现两种选择,所以元素数就是$2^n$.是对集合求其子集,所以直接空集而不是大括号空集.两个性质:
   $A\subseteq B$当且仅当$\rho(A)\subseteq\rho(B)$.
   $x\in\rho(A)$当且仅当$x\in A$.
2. 差集-
   $A-B$都有的全没了,剩下A独有的部分.B独有的部分不算.
3. 交并集运算不解释,高中学过
4. 笛卡尔积 $$A\times B=\{(x,y)|x\in A\&\&y\in B\}$$很像坐标系的运算,单个点集相乘整一个矩阵一样的东西,乘完之后有mn个元素.性质: 1.$A\times\varnothing=\varnothing\times A=\varnothing$ 2.一般不满足交换律和结合律.即 $$A\times B\neq B\times A\\(A\times B)\times C\neq A\times(B\times C)$$ 3.满足分配律(交集也一样满足的,只是式子太难打了) $$A\times(B\cup C)=(A\times B)\cup(A\times C)$$
5. 环和(对称差) $$\begin{aligned}A\oplus B&=(A-B)\cup(B-A)\\&=(A\cup B)-(A\cap B)\end{aligned}$$

6. 环积

   $$A\otimes B=\overline{A\oplus B}$$

7. 常见算律

   $$A\cup A=A,A\cap A=A\\ A\cup B=B\cup A,A\cap B=B\cap A\\ (A\cap B)\cap C=A\cap(B\cap C)\\ (A\cup B)\cup C=A\cup(B\cup C)\\ A\cap(B\cup C)=(A\cup B)\cap(A\cup C)\\ A\cup(B\cap C)=(A\cap B)\cup(A\cap C)\\ A\cap(A\cup B)=A,A\cup(A\cap B)=A\\ A\cup\overline A=E,A\cap\overline A=\varnothing,A=\overline{\overline A}\\ \overline{(A\cap B)}=\overline A\cup\overline B,\overline{(A\cup B)}=\overline A\cap\overline B\\ E\cap A=A,\varnothing\cup A=A\\ \varnothing\cap A=\varnothing,E\cup A=E$$

关于空集

空集是任何集合的子集,但是空集不默认是任何集合的元素,也就是说集合里面出现了空集符号对于求幂集等要参与运算(这个时候空集作为元素).
几个例题:
对{$\varnothing$,{$\varnothing$}}求幂集:

$$\{\varnothing,\{\varnothing\},\{\{\varnothing\}\},\{\varnothing,\{\varnothing\}\}\}$$

对$\{1,2\}$求幂集:

$$\{\varnothing,1,2,\{1,2\}\}$$

上面的如果改成$\{1,2,\varnothing\}$就会是8个元素了.

几个证明方法

1. 证明A=B
   $A\subseteq B$而且$B\subseteq A$即可,$\subseteq$的意思是一个集合的元素都是另一个集合的元素.
2. 取元素法证明$\overline{(A\cap B)}=\overline A\cup\overline B$:
   任取$a\in\overline A\cup\overline B$,即a属于xxx,然后一直推就行.

   关系

   这个东西非常重要.(a,b)这玩意叫序偶,就是用序偶的排列组合表示关系长啥样.

几个特殊关系:空关系$\varnothing$,全域关系$E_A=A\times A$,相等关系$I_A=\{(x,x)\}$

$\overline R=A\times A-R$

若 $|A|=n$ ,则A上的关系有 $2^{n^2}$ 个.如何理解?首先,A上的序偶一共有$n^2$个,然后单个序偶只是一个序偶,尝试解释序偶得到关系(序偶的排列组合),因为每个序偶都是可以去可以不去,就有这么多个关系.

关系常用大写字母RS等表示.因为关系也是集合,所以支持交并补运算,注意余运算的作用是针对全域而言,也就是$E=A\times B$.

写作$xRy$.

逆关系:序偶反过来,别的条件一样.令

$$R^{-1}=\{(y,x)|x\in A,y\in A,xRy\}$$

小于关系的逆关系是大于关系,相等关系的逆关系还是相等关系(可以注意到,逆关系并不是单纯对该关系取补集)

自反关系:对任意$x\in A$,有$xRx$.重点是任意元素.也就是说(x,x)都应该在集合内部.以下命题等价:

1. R是自反的
2. $I_A\subseteq R$
3. $R^{-1}$是自反的

反自反关系:对任意$x\in A$xRx均不成立.以下命题等价:

1. R是反自反的
2. $R\cap I_A=\varnothing$

对称关系:如果$xRy$则$yRx$.以下命题等价:

1. R是对称的
2. $R^{-1}$=R(真就一点渲染不多给是吧)

反对称关系:除了xRx那么只要有xRy必有$y\not Rx$.以下命题等价:

1. R是反对称的
2. $R\cup R^{-1}\subseteq I_A$

传递关系:如果xRy,yRz那么xRz.有点像并查集的路径压缩,比个例子:

$$R=\{(a,a),(a,b),(b,c),(a,c)\}$$

是一个传递性的关系,然后找到ab,bc,发现ac能缩点,然后就有传递性了,找不到就结束了.(比方说例子里面找到bc但是找不到c啥,那就忽略),以下命题等价:

1. R是传递的
2. $R^2\subseteq R$

关系运算

关系乘积(合成):$R\circ S=\{(x,y)|x\in A,y\in A,\exists z\in A,xRz,zRy\}$有点像矩阵乘法,满足乘法结合律,不满足交换律.

幂:好几个叠加在一起.规定$R^0=I_A$.有

$$(R^n)^m=R^{nm},R^n\circ R^m=R^{n+m}$$

线性代数知识:

$$(R\circ S)^{-1}=S^{-1}\circ R^{-1}$$

闭包运算:设R’是R的(自反,对称,传递三选一)闭包,R是A上的二元关系,则有:

1. R’是(自反,传递,对称三选一)的
2. $R\subseteq R’$
3. 对A上任何二元关系R’’都有$R’\subseteq R’’$(满足闭包最小)

设自反闭包对称闭包传递闭包分别为rst,则有(定理计算):

$$\begin{aligned}r(R)&=I_A\cup R\\ s(R)&=R\cup R^{-1}\\ t(R)&=\bigcup_{t=1}^{\infty}R^t\end{aligned}$$

(n有穷时式子会变成下面的)

$$t(R)=\bigcup_{t=1}^{n}R^t$$

等价关系:有的时候需要一些关系,把某些元素看成一类,某些元素看成另一类,然后不允许有公共元素(向左还是向右?).R是等价关系,当且仅当R具有自反性对称性传递性.

等价类关系R的值不相同然后进行区分.

集合划分:设A的子集族C有以下条件称C为A的划分:

1. 若$B\in C$,则$B\neq\varnothing$(不能是空的)
2. $\bigcup_{B\in C}B=A$(合起来就是A)
3. 对任意的$B,B’\in C$若$B\neq B’$则有$B\cap B’=\varnothing$(元素不重)

商集:本质上还是一种划分.R是一个A上的等价关系,A是一个集合,以R的所有不同等价类为元素构成的集合为A的商集,记作A/R.
举个例子:设

$$A=\{1,2,3,4,5,6,7,8,9\},R=\{(x,y)|x,y\in A\&\&x\equiv y\mod3\}$$

则

$$A/R=\{[1][2][3]\}=\{ \{1,4,7\},\{2,5,8\},\{3,6,9\} \}$$

其中[]表示所有元素构成的等价类.

第二类斯特林数:n个球放到r个盒子里,不能有空盒,问多少种放法,略,dp即可.

偏序关系

自反的, 反 对称的,传递的关系被称作偏序关系,类似小于等于的关系.(偏的意思是对于部分元素有这个关系)

全序集:对于集合中的a或b,必有a<b或者b<a,则称A是一个全序集,全序集有时被称为链.全序集的子集仍为全序集.

拟序关系:如果关系R是反自反的传递的,则称为拟序关系,记作<,读作小于.

最大最小元,极大极小元:分别介绍.

1. 最大元:是否存在一个元素与其他元素都是偏序关系
2. 最小元:是否存在一个元素与其他元素都是被偏序关系
3. 极大元:是否存在元素除自己外不是别人的偏序对象
4. 极小元:是否存在元素除自己外不是别人的被偏序对象

哈斯图

满足偏序关系的,中间不会有小三的两个元素中间画一条直线,小的数字放在底下,同一级偏序的放相同高度.比如24的整除关系哈斯图长这样:

24
| \
8  12
| / |
4   6
| / |
2   3
| /
1

先给一个简单的图分析:

24    36
  \  /
   12
   |
   6
  / \
 2   3

分别对于A中的部分元素找值,看表:

	{6,12}	{2,3}	{24,36}	{2,3,6,12}
上界	12,24,36	6,12,24,36	无	12,24,36
上确界	12	6	无	12

上界:只要A中元素的任意元素对于任意B(B就是给你表格上面的那个部分A中的元素)都有偏序关系,则称为上界元素,其中最小出现的被称为上确界.
极大元,最大元:唯一在最上面的叫最大元,宁缺毋滥,但是极大元可以有很多个,最小元同理.

全序关系:哈斯图是一条直线的关系.

良序集:对于任意A的非空子集都存在最小元.

完备的:一个偏序集被称作完备的,如果

1. A有最小元,记作$\perp_A$或者$\perp$.
2. A中的每一个链K都有最小上界(上确界)

映射:

b叫映像,a叫原像
每一个B都有A对应是满射(A可以没取值的)
一对一是单射(这个时候B可以有多余没映射的)
如果是A对A的映射叫变换.
既是满射又是单射的叫双射.

逆映射略.

$$\sigma^{-1}(\sigma(a))=a$$

规定:

$$(\tau\circ\sigma)(a)=\tau(\sigma(a))$$

满足结合律不满足交换律.

基数

就是,我们要开始研究无限集的集合元素个数了,通过映射实现无限集基数的计算.

定义:AB是集合,假如存在AB间的双射,则AB基数相同,记作|A|=|B|,读作 等势.

例:$A(0,1),B(0,+\infty)$,构造双射$\sigma(x)=\tan(\frac{\pi}{2}x)$

一个集合的元素个数是一个非负整数.我们把自然数(非负整数)集合的基数叫做$\aleph_0$(阿列夫0).

集合的对等关系是一个等价关系.

如果有从A到B单射或者从B到A满射,则$|A|\geqslant|B|$

集合的基数关系$\leqslant$:有自反性和传递性.

关于反对称性,有$\mathbf{Bernstein}$定理:存在A的子集A’和B的子集B’,满足|A|=|B’|和|B|=|A’|,则|A|=|B|.

可数集合:一个集合元素数有限或者映射能映射到自然数集合上(双射),就叫可数集合,否则叫无穷集合.性质:

1. 可数集合的子集仍然是可数集合.
2. 无穷个可数集合的并集还是可数集合.
3. AB是可数无穷集合,$A\times B$是可数集合.

聊聊不可数集合:

1. 实数集不可数(康托对角线法证明的)
2. 实数集的区间$(a,+\infty),[a,b],[a,b),(a,b],a\neq b$是不可数的
3. 集合不能与A的所有子集建立双射

第二章 计数

课程不讲,略.

第三章 古典数理逻辑

命题逻辑:大写字母表示事件,用P,Q等表示.否命题用$\neg$表示.($LaTeX$打法\neg)

析取:打法\lor写作$\lor$,表示PQ之间P或者Q的关系,有点像集合的并集关系.
合取:打法\land写作$\land$,表示PQ之间与的关系,有点像集合里面的交集关系.
蕴含:打法\to写作$\to$如果P那么Q,称为P蕴含Q,也就是$P\to Q$.(注意命题逻辑和日常逻辑的区别,命题逻辑中的PQ可以任何关联没有)
特别注意蕴含假的定义是当且仅当P是真的而Q是假的,比个例子,P:2^2=5,Q:雪是黑的,那么p->Q是真的.

等价:打法\leftrightarrow写作$\leftrightarrow$,读作”当且仅当”,该命题为真当且仅当PQ同真或者同假(一样).

原子:命题符号称为原子.

优先级

递增顺序如下:

$$\leftrightarrow,\to,\land,\lor,\neg$$

举例:

$$P\land Q\lor R\to Q\land\neg S\lor R$$

即

$$(P\land(Q\lor R))\to(Q\land((\neg S)\lor R))$$

因为命题符号是抽象的,所以需要进行解释才有意义.解释叫做I,真值通常写作$T_1(G)$.G在所有解释下表现的值叫真值表.

P	Q	R	G		P	Q	R	G
0	0	0	1		0	1	0	1

(像这样的就叫真值表)

解释I可以用原子表示,写作{xxxx},比如

$$\{\neg P,\neg Q,R\}$$

其中加非的都是0,保持原样的都是1.

恒真,恒假
可满足的:G不全是假那就是可满足的.G在I下是真的叫I满足G,否则叫I弄假G.

公式:

1. $(G\leftrightarrow H)=(G\to H)\land(H\to G)$
2. $(G\to H)=(\neg G\lor H)$
3. $G\land G=G,G\lor G=G$幂等律
4. $G\land H=H\land G,G\lor H=H\lor G$交换律
5. $G\lor(H\lor S)=(G\lor H)\lor S,G\land(H\land S)=(G\land H)\land S$结合律
6. $G\lor(G\land H)=G,G\land(G\lor H)=G$吸收律
7. $G\land(H\lor S)=(G\land H)\lor(G\land S),G\lor(H\land S)=(G\lor H)\land(G\lor S)$分配律
8. $G\lor0=G,G\land1=G$同一律
9. $G\land0=0,G\lor1=1$零一律
10. $\neg(G\lor H)=\neg G\land\neg H,\neg(G\land H)=\neg G\lor\neg H$摩根律

非联结词:
与非式:打法\uparrow写作$\uparrow$,表示两个原子先与再非.
或非式:打法\downarrow写作$\downarrow$,表示两个原子先或再非.(使用这俩的不叫公式)

完备集:设为Q,任意公式都可以使用Q中元素表示,且Q任意真子集没这个性质.常见完备集有:

$$\{\neg,\lor\}\{\neg,\land\}\{\uparrow\}\{\downarrow\}$$

如果对任意I满足G,I也满足H则记为$G\implies H$,所以$G\implies H$的充要条件是$G\to H$是恒真的.

共同蕴含:$(G_1\land G_2\land G_3\land…)\to H$就叫G…共同蕴含H.

若G…P共同蕴含H,则G…共同蕴含$P\to H$

演绎

若P则Q,因为P有Q,写作$(P\to Q)\land P\implies Q$
同理,式子反过来会有$(P\to Q)\land\neg Q\implies\neg P$
(原理:$\neg(P\to Q)=\neg Q\to\neg P$)

公式:

$$A\to(B\to C)=(A\land B)\to C$$ $$P\lor Q=\neg P\to Q$$

演绎就是从命题集合S中选几个命题,然后进行推论得到的结果. 记作从S中演绎出G,也就是$S\implies G$.

比个例子:

$$S=\{P\lor Q,Q\to R,P\to M,\neg M\}$$

则下面的公式序列就是一个演绎:

$$\neg M,P\to M,\neg P,P\lor Q,Q$$

演绎的合理性:

$$若G\implies H_1,G\implies H_2,有G\implies(H_1\land H_2)$$

演绎定理:若 $S\bigcup\{G\}$ 可演绎出H,则从S可演绎出$G\to H$.
结论证明:把给的当前提使用就行了.

基本蕴含式

$$P\land Q\implies P(Q)\\ P(Q)\implies P\lor Q\\ \neg P\implies(P\to Q)\\ Q\implies(P\to Q)\\ \neg(P\to Q)\implies P$$

证明公式蕴含的方法:证G蕴含H

1. 真值表法
2. 证明$G\to H$恒真
3. 推导法
4. 任取解释I,如果I满足G,往证I满足H
5. 反证,设结论假,证明前提假,即$\neg H\implies\neg G$

例1:设$A=(R\to P)\to Q,B=P\to Q$,证明A蕴含B:
证明$A\to B$恒真.

$$\begin{aligned} &((R\to P)\to Q)\to(P\to Q)\\=&\neg(\neg(\neg R\lor P)\lor Q)\lor(\neg P\lor Q)\\=&((\neg R\lor P)\land\neg Q)\lor(\neg P\lor Q)\\=&(\neg R\land\neg Q)\lor(P\land\neg Q)\land\neg(P\land\neg Q)\\=&1 \end{aligned}$$

利用一些基本等价式推导:
例:$A=(R\to P)\to Q,B=P\to Q$

$$\begin{aligned}A&=(R\to P)\to Q\\&=\neg(\neg R\lor P)\lor Q\\&=(R\lor\neg P)\lor Q\\&=(R\lor Q)\land(\neg P\lor Q)\\&=(R\lor Q)\land(P\to Q)\end{aligned}$$

由基本蕴含式$P\land Q\implies Q$知

$$(R\lor Q)\land(P\to Q)\implies(P\to Q)$$

即A蕴含B

形式演绎法

考试必考.三条规则:

1. 可以随便使用前提
2. 可以随便使用前面演绎出来某些公式的逻辑结果
3. 如果需要演绎的公式是$P\to Q$的形式,则P可以当作附加前提使用,力图证Q

注意写的时候要标规则几(推理谁都会,但我们要你使用离散给的东西推理)

例1:证明$\{(P\lor Q),(P\to R),(Q\to S)\}\implies S\lor R$

1. $P\lor Q$ 规则1(右对齐)
2. $\neg P\to Q$ 规则2,根据1
3. $Q\to S$ 规则1
4. $\neg P\to S$ 规则2,根据2,3
5. $\neg S\to P$ 规则2,根据4
6. $P\to R$ 规则1
7. $\neg S\to R$ 规则2,根据5,6
8. $S\lor R$ 规则2,根据7

例2,证明$\{P\to(Q\to S),\neg R\lor P,Q\}\implies R\to S$

1. $\neg R\lor P$ 规则1
2. $R$ 规则3
3. $P$ 规则2,根据1,2
4. $P\to(Q\to S)$ 规则1
5. $Q\to S$ 规则2,根据3,4
6. $Q$ 规则1
7. $S$ 规则2,根据5,6
8. $R\to S$ 规则3,根据2,7

应用:具体问题里面先设状态,然后再使用命题.比个例子:盗窃案,事实如下:

1. A或B盗窃了x
2. 若A盗窃了x,作案时间不能发生在午夜前
3. 若B证词正确,则在午夜时间屋里灯光未灭
4. 若B证词不正确,则作案时间发生在午夜前
5. 午夜时屋里灯光灭了
6. A并不富裕

试用演绎法找罪犯:
第一步:符号化:
P:A盗窃了x
Q:B盗窃了x
R:作案时间发生在午夜前
S:B证词正确
T:在午夜时屋里灯光未关
U:A并不富裕
第二步:写出各前提:

$$G_1:P\lor Q,G_2:P\to\neg R,G_3:S\to T\\G_4:\neg S\to R,G_5:\neg T,G_6:U$$

自己演绎,反正是B偷了.

文字,子句,短语和范式

范式的引入:我们都知道,真值表很好用但是每加一个原子都会扩大一倍的表格,极其不好用,所以我们引入一种叫范式的东西.

文字:原子或原子的否定,如$P,\neg P$.
子句:有限个文字的析取式叫子句.
短语:有限个文字的合取式叫短语.
析取范式:有限个短语的析取式,如$(A\land B)\lor(C\land D)$.
合取范式:有限个子句的合取式,如$(A\lor B)\land(C\lor D)$.
(特别的,文字既是合取范式也是析取范式,一个短语或子句既可以看作合取范式也可看作析取范式.)

数字逻辑讲,任意范式都存在析取范式和合取范式.

主析取范式:先引入极小项的概念:
极小项:对于PQR三个原子而言,$P\land Q\land R$是,$P\land Q$不是.然后带入的时候就带1,如果非就是0.如:

$$\neg P\land Q\land\neg R对应010也就是m_2$$

性质:唯一性,公式等价能用这个看,恒假能用这个看($P\land\neg P=0$)

主合取范式:先引入极大项的概念:
极大项:对于PQR三个原子而言,$P\lor Q\lor R$就是极大项.极大项带入的是非是1否则是0.比如:

$$\neg P\lor Q\lor R对应100也就是M_4$$

关系:

$$m_4=\neg M_4$$

怎么求:加非分割,然后分别计算.

谓词逻辑

繁琐.比方说一个1-50的集合中大于3的元素,需要整整50个命题.

有的时候命题之间是有内在联系的,但是这种关系在命题逻辑中无法表示.比如:

1. P:凡人必死
2. Q:张三是凡人
3. R:张三必死

上式叫”哲学三段论”,命题中应该有$(P\land Q)\implies R$,但是大家都知道,$(P\land Q)\to R$式子并不恒真,一个$\{P,Q,\neg R\}$就能弄假式子.

所以,我们需要引入 谓词 的概念.
谓词,个体:上式”张三是人”中,”是人”是谓词,”张三”是主语,又叫个体.学生,自然数都可以当个体.

设$D^n$是一个取值0或1的n元函数,表示集合D的n次笛卡尔积.

如:G(a,b)表示a高于b,则G(张三,李四)表示张三高于李四.如果张三不高于李四,则G(张三,李四)=0.

量词:由于张三必死的否定是所有人都不死,太离谱了,上个量词限制一下.

$$\forall,\exists$$

换量词,否结论.(没给量词默认任意)

比个例子:任何人都会犯错误:
P(x):x是人
R(x):x会犯错误

$$\forall x(P(x)\to R(x))$$

约束范围:括号内部.括号外部自由的变量可以和内部不一样的,也就是,比方说:

$$\forall x(P(x,y)\lor Q(x,z))\lor(R(x,v))$$

可以改成

$$\forall a(P(a,y)\lor Q(a,z))\lor(R(x,v))$$

(注意这个x没变)

(存在展开和任意展开:就是对于D中展开,使用$\land\lor$连接)

项:
常量是项,变量是项.
若f(x1,xn)是n元函数符号,t1-tn是项,则f()也是项.
项是有限次使用上面俩生成的符号串.
公式:
原子是公式.
若G,H是公式,则$\neg G,G\lor H,G\land H,G\to H,G\leftrightarrow H$也是公式.
若G是公式,x是自由变量,则$\forall xG,\exists xG$也是公式.
有限次使用上几条生成的符号串.

多重量词时,注意量词顺序.写在前面的先展开.

等价:如果$G\leftrightarrow H$则记作等价,写作$G=H$,在任意解释I下的真值相同.
蕴涵:如果$G\to H$恒真则有(蕴含,逻辑结果)$G\implies H$

前束范式:长这样:

$$Q_1x_1Q_nx_nM$$

首先要知道,范式里面的量词是不可以随便提前的,不然会错.

对于不含x的H有:量词随便拆括号.即$\exists x(G(x)\land H)=\exists xG(x)\land H$.其余就换量词否结论.

前束范式的意思就是变元作用域是整个式子,所以需要变变量名.

提示:若 $\exists xG(x)$ 假则 $\forall xG(x)$ 假,若 $\forall xG(x)$ 真则 $\exists xG(x)$ 真.

Skolem范式:看不懂.

第四章 图与网络

图论关注的是点之间的关系而不是图的形状.
$G(P,L)$称为图.P是点集,L是边集(不考虑自环重边的叫简单图,离散研究简单图).
有点没边的图叫零图.点边状况一样的叫同构图(一个图肆意扭曲旋转的都叫同构图).
子图,支撑子图:点集和边集都是母图子集的叫子图,点集和母图一样但是少边的叫支撑子图.

图的存储:三种.关联矩阵,邻接矩阵,前向星,前向星不讲,离散不考.
关联矩阵:就是$O(nm)$,矩阵一边是点一边是边,表示一条边的情况.
邻接矩阵:就是$O(n^2)$,表示点之间的情况.
前向星:略.

度:记作$d_G(v)$表示一个点的度.

几句废话:

1. 所有点的度加一起是二倍边数,i.e. $$\sum_{v\in P(G)}d_G(v)=2m$$
2. 任意有限图中,奇数度点的个数是偶数.

路:(一个点的序列).允许有重复,允许首尾相接.长度是点的个数-1.

简单路:除了首尾可以相同之外每一个点都不能相同的路.

回路:从自己到自己的长度不小于3的 简单路 叫回路.(长度不小于3是为了排除原路返回的情况)

几个定义

相连的:两个点有一条路连接,注意不只是边.
连通分支:把P(G)依据联通关系分开(有点像找连通块),每一个拆出来的都叫一个连通分支.
连通的:图只有一个连通分支.

树:连通的无回路的图.
森林:无回路的图(可能不连通).

性质

1. G是至少有一条边的有限图,且无回路,则G至少有一个点度数是1.

2. 假如G是一个图,则下列命题等价:
   1.G是树
   2.G是连通的而且删任何一条边都不连通
   3.对于G中任意两点,只有一条路连接彼此
   如果G还是有限图,则还有这两条性质:
   4.G不含回路,并且G有n-1条边
   5.G连通,并且G有n-1条边

3. 任意有限连通图必有一个支撑子图是树(叫做支撑树)

4. 支撑树加任意一条边会产生回路

Dijkstra和Kruscal

略

有向图,欧拉路

$G(P,A)$(绩点?)叫做有向图.很好理解,graph,point,line,arrow.
e是弧,v=init(e)起点,v’=fin(e)终点.
这个时候自环有别名了,叫反身弧.

P有限就叫有限有向图.点集和边集都是子集的就是子图(自己是自己子图可还行)

为了简便有时也写作点$v\in G$或者边$e\in G$

路:这里用$(e_1,e…,e_n)$表示路.
简单有向路:所有有向边入点和出点互不相同的路.
有向回路:到自身的简单有向路,长度可以是1或2
强连通:所有点之间相互可到达
根:所有点都可以到达该点(除了自己),根可以有很多个.
漠视图:把弧看成边,删掉反身弧的无向图.
有向树:满足以下条件:1,r是根,2,r不是任意一条弧的起点,3,其他点恰好是 一条 弧的起点.

第五章 数论基础

挖坑.
(23届不考欧拉函数的计算,只需要填表用辗转相除算一个gcd就行,整章数论非常水.)

离散数学II

代数系统

二元代数运算:设 $S$ 是一个集合,然后 映射 $f$ 是一个从 $S\times S$ 到 $S$ 的映射,这就是二元代数运算.条件: 集合非空,运算封闭

交换律,结合律,忽略.

如果对于 * 有 $a*a=a$ 则 $a$ 叫幂等元,所有元素都满足这个就叫具有 幂等律 .

对于运算 * 若 a*b=a*c 则 b=c 则有 * 满足消去律.

对于 *+ 若有 a*(b+c)=(a*b)+(a*c) 且 (b+c)*a=(b*a)+(c*a) 被称作 运算 * 对 + 满足分配律 (注意顺序不可变).

对于 *+ 若有 a+(a*b)=a 且 a*(a+b)=a 被称作 运算 * 和 + 满足吸收律 (这里不区分顺序).

零元 :设存在 $\theta$ 满足对任意元素a都有 $a*\theta=\theta*a=\theta$ 则被称作零元.

代数系统 :(集合,运算1,运算2,…).

群论

半群 : (G,*) 假如G非空, * 是二元运算且满足结合律,则被称作 半群 .

群 :存在单位元和逆元.(单位元:对任意a有 a*1=1*a=a ,逆元是对于任意a都有 a*b=b*a=1 然后b就叫逆元 $a^{-1}$ )

群的性质

1. 单位元是群中唯一幂等元.
2. 群中消去律一定成立.(群是有逆元的,不要担心0的问题)

3. |G|>1 时群中无零元(群要求有逆元,0没有逆元(或者逆元就是他自己))

4. 群中单位元素和元素的逆元是唯一的.

5. 群定义可以减弱如下:同时存在左一和左逆 $1a=a,a^{-1}a=1$ 也是群.
6. 群定义等价以下可除条件:对于任意ab,存在xy有 $ax=b,ya=b$ .
7. 一元群,二元群,三元群都是唯一的,而且满足交换律.
8. $(a*b)^n=a^n*b^n$ 一般是不成立的.
9. 有限半群,如果满足消去条件,一定是群.

Abel群

满足交换律的群称为Abel群,或者交换群.

置换群

变换:A到A的映射.

M是一个有限集合,M的一个一对一变换称为一个置换.
置换有 $n!$ 个,元素不变的那个称为n元恒等变换.

$S_n$ 是n元置换形成的集合( $n!$ 个元素).

置换乘法 :对于a,有 $\sigma\tau(a)=\sigma(\tau(a))$ .
置换乘法的性质:

1. 满足结合律 $(\sigma\tau)\rho=\sigma(\tau\rho)$
2. $S_n$ 中有单位元,设为 $\sigma_0$ ,单位元就是n元恒等置换.
3. 每个置换在 $S_n$ 中都有逆元素(上下颠倒过来就行了)

乘法举例:

$$\sigma=\begin{pmatrix}1&2&3&4&5\\2&4&3&5&1\end{pmatrix},\tau=\begin{pmatrix}1&2&3&4&5\\2&5&1&4&3\end{pmatrix}$$ $$\sigma\tau=\begin{pmatrix}1&2&3&4&5\\5&4&1&3&2\end{pmatrix}$$

一个一个对应就行了.

n次置换群:集合是n次置换,运算是置换乘法.
性质:1元和2元的置换乘法满足交换律,是交换群.

轮换表法(顺着找环)

$$\begin{pmatrix}1&2&3&4&5&6\\3&2&4&1&5&6\end{pmatrix}=(1\space3\space4)=(1\space3\space4)(2)(5)(6)$$

轮换相逆直接倒过来,reverse.

相杂轮换 :元素A同时出现在两个轮换中.
轮换合并 :必须严格按照轮换乘法运算,举例(123)(342)=(12)(34)并不是(1234)

不相杂轮换直接放到后面就行了.(不相杂的轮换满足交换律)

轮换表示方法:去掉单轮换,然后把最小元素挪移到前面.

对换:大的拆小的.(123…n)=(1n)(1{n-1})…(13)(12),注意对换没有(xx)的情况出现,单轮换是不转对换的.

置换奇偶性 :元素个数n-轮换个数k(不算单轮换),或者对换的个数.
奇偶性乘法律 :相同是偶,不然就是奇.

子群

如果集合的子集和这个运算符仍满足群的关系,就叫子群.(真子群定义一样,忽略)

平凡子群 :任意群都有两个子群:单位子群1和自己.这俩叫平凡子群.
非平凡子群:其他的子群如果存在都叫这个.

子群判定 :

1. 设H是G子群,H充要条件是: 1H非空 2任意ab属于H,必有a*b属于H 3任意元素逆元属于H
2. 对任意 $a,b\in H$ ,有 $a*b^{-1}\in H$ .
3. 如果群有限,非空,封闭,就是子群

若一个群g有非平凡子群,则g中元素数量大于等于4.

S是n元恒等置换,a是S中的所有偶置换的集合.

$A_4$ 称为四次交代群, $S_4$ 为四次对称群, $A_4$ 没有六元子群, $A_4$ 子群有10个.

子群性质 :单位元一样,任意元素逆元一样.

生成子群 :a的任意整数次幂生成的一个群叫生成子群,记作 (a)

循环群 :如果存在某个元素能够生成整个子群,就把G叫做循环子群.(性质:每个循环群都是交换群).
循环群是abel群,abel群一定有正规子群.

元素周期 :元素经过多少次对自己的乘法能回到自己,就叫做周期.回不到的周期定为无穷或者0.
单位元的周期是1,一个元素和逆元的周期相同.周期是取最小的元素.

循环群的生成元素 :1. 无限循环群里有两个生成元: $a$ 和 $a^{-1}$

1. n元循环群中元素 $a^k$ 是 $(a)$ 的生成元的充要条件是 $\gcd(n,k)=1$ .
2. 故 $(a)$ 共有 $\phi(a)$ 个生成元素.

模x加法群是循环群.

循环群的子群还是循环群.

G与N之间的子群一一对应
大群对应大群,小群对应小群.
正规子群对应正规子群.

有若 $N\in H$ 有 $\sigma^{-1}(\sigma(H))=H$
任意有

$$\sigma(\sigma^{-1}(H'))=H'$$

只需证明大群对应大群,小群对应小群,正规子群对应正规子群.

陪集

陪伴,陪衬的集合.从G中选的子群H具有某种性质,但是G中还有某些集合也满足这个性质,但是因为他们缺少单位元不算子群,这个就叫陪集.aH左陪集可以看做a拜访H中每个元素,右陪集可以看做H挨个拜访a,如果两种拜访方式结果是一样的,就被称为正规子群H.

陪集性质:1. |aH|=|H|

1. H本身是H的左右陪集.
2. aH=H iff $a\in H$
3. a在陪集aH中
4. 对于右陪集aH中任意元素b有aH=bH,说明右陪集中任意元素都可以当陪集代表
5. aH=bH充要条件是 $ab^{-1}\in H$
6. 任意两个右陪集aH bH相等或者不相交(所以求陪集直接暴力然后去个重就行了)

   正规子群

   对任意 $g\in G$ 都有gH=Hg,则有H是正规子群.

平凡子群是正规子群.

交换群的任意子群是正规子群.

必要且只要 $g\in G,gHg^{-1}⊆H$

如果H的任意两个右陪集的乘积仍是一个右陪集,则H是一个正规子群.

拉格朗日定理

设G为有限群,则子群H元数整除G元数.(逆命题不成立)

若G是循环群,则G必定且有且存在一个m元子群满足m整除|G|(注意是任意因数).

若G是有限群,|G|=n,则任意元素的周期一定是n的因子.

若G的元数是个质数,则对任意非单位元,都是群的生成元(由任意子群元数是n的因子,任意元素周期是n的因子推出)

所以任意元数是质数的群都是循环群.

设G元素个数是n,则对任意元素 $a\in G$ 有 $a^n=1$ .

有限交换群的所有元素相乘结果不是1的,一定是偶数元群.

H在G中的指数:元数相除得到的整数,记作 $(G:H)$ (等价类的个数)(同时也是左右陪集的个数)(G:H)若指数为2则H一定是G的正规子群.

当n<6时,n元群都是交换群.

群的同态和同构

同态映射 :设 $(G,\cdot)$ 是一个群, $(K,)$ 是一个代数系统.假如存在一个映射 $\sigma$ 对G中任意元素ab满足 $\sigma(a\cdot b)=\sigma(a)\sigma(b)$ 就叫同态映射.这玩意不一定是单射也不一定是满射(同态是函数式的映射).

设 $G’=\sigma(G)$ ,有:

1. $(G’,\cdot)$ 是一个群
2. G’中单位元 $1’=\sigma(1)$
3. $\sigma(a)^{-1}=\sigma(a^{-1})$
4. 若 $\sigma(a)=\sigma(b)$ ,则 $\sigma(a^{-1})=\sigma(b^{-1})$

同构映射

如果 $\sigma$ 是一个1-1映射,就叫同构映射,记作 $G\cong\sigma(G)$ (G\cong\sigma(G)).

举例:正整数乘法群同构于实数加法群:设 $\sigma(x)=\ln x$ 有

$$\sigma(a*b)=\ln(a*b)=\ln a+\ln b=\sigma(a)+\sigma(b)$$

整数加法群同构于偶数加法群.
无限循环群同构于整数加法群.
$(R^*,\cdot)$ (非零实数乘法群)和 $(R,+)$ 不可能同构.

$\sigma()$ 是G到G的同构映射叫自同构映射.

同态核

所有满足 $\sigma(x)=1’$ 的x组成的集合叫同态核,记作N,称为N是 $\sigma$ 的核.
同态核是正规子群.

群的第一同态定理

$\sigma^{-1}(a’)=x$ 满足逆映射的显然不止一个,他们构成一个集合.集合是N(核)在G中的一个陪集.

设N是G的正规子群,若A,B是N陪集,则AB也是N的陪集.

群的第二同态定理

设N是G正规子群,按照陪集乘法,做成 $\overline G$ .
映射 $\sigma:a\to aN,a\in G$
则映射 $\sigma$ 是一个同态映射,且核为N,记作 $\overline G=G/N$
元素个数就是N在G中指数(|G|/|N|),陪集个数.

群的第三同态定理

映射和核满足 $G’\cong G/N$ .

G和G’的关系

若H是G子群,则H’也是G’子群.反过来也成立.

$σ^{−1}(σ(H))=HN$

当 $N⊆H$ ,即 $HN=H$ 时,有 $σ^{−1}(σ(H))=H$ .

H是G的正规子群必要而且只要 H’=σ(H)是G’的正规子群

环

定义:九条

1. 集合非空
2. 对于加法封闭
3. 对于乘法封闭
4. 加法是交换群(结合律,交换律,单位元,逆元)
5. 乘法是半群(结合律)
6. 乘法对于加法有左右的分配律

约定在环这里,乘法优先级比加法高(因为乘法不满足交换律,先运算更省事)
约定 $a-b$ 的意思是 $a+(-b)$ ,其中 $-b$ 是 $b$ 的加法逆元

性质(加法):

1. $0a=0,a0=0$ ,前面是有理数0,后面是群中加法单位元.
2. $a(c-b)=ac-ab,(c-b)a=ca-ba$
3. $(-a)b=-(ab)=a(-b),(-a)(-b)=ab$
4. 对任意整数 $m$ 有 $a(mb)=(ma)b=m(ab)$

性质(乘法):

因为乘法是半群,无法保证单位元是否在群内,所以以下幂次方运算的n和m必须是正整数(0都不可以).

1. $a^na^m=a^{m+n}$
2. 如果任意 $ab=ba$ 则环叫做交换环.环内有第三指数律 $(ab)^n=a^nb^n$

整数环,多项式环是交换环,矩阵环不是交换环.
交换环中二项式定理成立: $(a+b)^n=…$

含壹环 :如果R不只有一个元素,而且存在元素1满足 $1a=a1=a$ ,则R称为含壹环(因为不能和加法单位元混).

整数环是含壹环,所有偶数在加法乘法下不做成含壹环.
性质:

1. 含壹环的1唯一确定,且一定不是加法的单位元.
2. 任意环均可扩充为含壹环.

子环

老规矩,自己和{0}是两个平凡子环.

子环的壹与原来的环的壹未必一致.

消去环

零因子 :如果 $a\neq0,b\neq0,ab=0$ 则ab互称0因子.如果R没有这样的元素,就叫做消去环.比个例子:整数环是消去环,矩阵环不是消去环.

$$\begin{bmatrix}1&0\\1&0\end{bmatrix}\begin{bmatrix}0&0\\1&1\end{bmatrix}=\begin{bmatrix}0&0\\0&0\end{bmatrix}$$

无零因子,非零元满足消去律.

性质:

1. 消去环中,不为0的元素加法周期相同,且为0或质数.

整区 :有壹无零因子的交换环叫做整区.
所有整数,有理数,实数,所有复数在数的加法和乘法下做成的环叫做整区.

体 :如果去掉0,R的其余元素做成一个乘法群,称R为体.
体有壹无零因子,任意非零元素有逆.

域 域是交换体.在域中, $ab^{-1}$ 可以写作 $a/b$ (有限整区).
有理数域,实数域,复数域都是域.

子某 :如果截一部分仍然满足某的定义就叫子某.子环,子体,子域,子整区,etc.

偏序格

定义:给出一个偏序集(L,≤),如果对于任意a,b∈L,L的子集{a,b}在L中都有一个最大下界(记为inf{a, b})和一个最小上界(记为sup{a, b})则称(L,≤)为一个格.

全序集是一个格,不是所有偏序集都是格.

偏序子格 :直接集合就行了.设 $(S,\le)$ 是格,则 $L⊆S,(L,\le)$ 是子格.

代数格

定义:设L是一个集合,×,⊕是L上两个二元代数运算,如果这两种运算对于L中元素满足:
交换律: $a×b=b×a,a⊕b=b⊕a$
结合律: $a×(b×c)=(a×b)×c,a⊕(b⊕c)=(a⊕b)⊕c$
吸收律: $a ×(a⊕b)=a,a ⊕(a×b)=a$
则称此代数系统(L,×,⊕)为一个格.

因为满足吸收律,所以一定满足幂等律.

代数格和偏序格是等价的 .

子格 :子集,如果也满足运算封闭,也是格,那就是子格.

代数子格与偏序子格的关系

若 $(S,×,⊕)$ 是 $(L,×,⊕)$ 的代数子格,则 $(S,≤)$ 是 $(L,≤)$ 的偏序子格.

若 $(S,≤)$ 是 $(L,≤)$ 的偏序子格,则 $(S,×,⊕)$ 不一定是 $(L, ×, ⊕)$ 的代数子格. (因为代数子格必须满足封闭性)

格的其他性质

设(L,≤)是一个格,a,b是 L 中任意元素,于是 $a≤b \leftrightarrow a×b = a \leftrightarrow a ⊕ b = b$
设(L,≤)是一个格,a,b,c是 L 中任意元素,如果 $b≤c$ ,则有 $a×b ≤ a×c,a⊕b ≤ a⊕c$
设(L,≤)是一个格,a,b,c是L中任意元素.于是有分配不等式

$$a⊕(b×c) ≤ (a⊕b)×(a⊕c)$$ $$a×(b⊕c) ≥ (a×b)⊕(a×c)$$

(记忆方法:最后进行⊕的式子小)
在一般格中,分配律不是总成立的,但上述分配不等式总是成立的.
设(L,≤)是一个格,a,b,c是 L 中任意元素,于是, $a≤b \leftrightarrow a⊕(b×c) ≤ b×(a⊕c)$

判断一个哈斯图是不是格 :找,如果存在两个元素之间不存在上下确界,那就不是格.举例:

  o
 / \
o   o  //aaa
|\ /|
|/ \|
o   o
 \ /
  o

这并不是一个格,因为标注释那行两个没有下确界(下确界可以没有但是必须唯一,于是这两个横着的因为有两个下确界就出问题了)

格的同态与同构

设(L,×,⊕)和(S,∧,∨)是两个格,L到S内的映射g称为 $(L,×,⊕)$ 到 $(S,∧,∨)$ 的格同态映射,如果对任意a,b∈L,都有

$$g(a×b)= g(a)∧g(b)$$ $$g(a⊕b) = g(a)∨g(b).$$

L到L的被称为自同态映射.一对一的映射又叫同构映射.

其他奇奇怪怪的格

有界格

顾名思义.

有余格

   o      o       o
   |     / \     / \
   o    a   b   a   c
  / \    \ /    |   |
 a   b    o     b   |
  \ /            \ /
   o              o
ab均无余 a余b c有ab两个余

每个元素至少存在一个余元素.

分配格

$$a×(b⊕c) = (a×b)⊕(a×c)$$ $$a⊕(b×c) = (a⊕b)×(a⊕c)$$

任意元素满足这两个式子.

分配格的任意子格仍然是分配格.

分配格当且仅当不含有五角格和钻石格

  o      o
 /|\    / \
o o o  o   o
 \|/   o   |
  o     \ /
         o
钻石格 五角格

模格

设 $(L,≤)$ 是一个格,对任意 $a,b,c∈L$ ,如果 $a≤b$ ,都有 $a⊕(b×c)= b×(a⊕c)$ 则称 $(L,≤)$为模格.

模格就是不包含和五角格同构的格.

布尔代数

有余分配格是一个布尔代数,记为 $(B,·,+,ˉ,0,1)$ .

判定:

1. 满足交换律,结合律
2. 满足分配律
3. 存在0元和1元
4. 存在取反运算,满足 $a\bar a=0,a+\bar a=1$

就被称作一个布尔代数.

子代数

运算封闭,子集,包含01,三种运算都是封闭的,就叫子代数.