离散数学复习 – Hi! endermite!

离散数学

集合的界

设 \(A\) 是一个数集。

上界：大于或等于 \(A\) 中所有元素的数，不一定属于 \(A\)；
下界：小于或等于 \(A\) 中所有元素的数，不一定属于 \(A\)；
上确界：所有上界中最小的一个，记作 \(\sup A\)；
下确界：所有下界中最大的一个，记作 \(\inf A\)；
最大值：\(A\) 中最大的元素，必须属于 \(A\)；
最小值：\(A\) 中最小的元素，必须属于 \(A\)。

集合运算

de Morgan 律

设 \(A,B\subseteq X\)，则

(A\cup B)'=A'\cap B',

(A\cap B)'=A'\cup B'.

相对补还满足

A\setminus(B\cup C) =(A\setminus B)\cap(A\setminus C),

A\setminus(B\cap C) =(A\setminus B)\cup(A\setminus C).

常用的差运算公式还有

A\cap(B\setminus C)=(A\cap B)\setminus(A\cap C),

A\setminus(B\setminus C)=(A\setminus B)\cup(A\cap C).

对称差（环和）

集合 \(A\) 与 \(B\) 的对称差定义为

A\oplus B =\{x\mid(x\in A\land x\notin B)\lor(x\in B\land x\notin A)\}.

等价地，

A\oplus B=(A\setminus B)\cup(B\setminus A) =(A\cap B')\cup(B\cap A').

环积

设 \(X\) 为全集，定义

A\otimes B =\{x\mid(x\in A\lor x\notin B)\land(x\in B\lor x\notin A)\}.

因此

A\otimes B=(A\cup B')\cap(B\cup A').

初级交、初级并、广义交、广义并

有限个集合的初级交与初级并分别为

\bigcap_{k=1}^{n}A_k =\{x\mid(\forall k)(1\le k\le n\Rightarrow x\in A_k)\},

\bigcup_{k=1}^{n}A_k =\{x\mid(\exists k)(1\le k\le n\land x\in A_k)\}.

设 \(\mathcal A\) 是集合族，则

\bigcap\mathcal A =\{x\mid(\forall A\in\mathcal A)(x\in A)\},

\bigcup\mathcal A =\{x\mid(\exists A\in\mathcal A)(x\in A)\}.

广义交要求集合族非空；广义并对空集合族仍可定义，并有 \(\bigcup\varnothing=\varnothing\)。

广义运算也满足分配律和 de Morgan 律。例如

A\cap\left(\bigcup_{i\in I}B_i\right) =\bigcup_{i\in I}(A\cap B_i),

A\cup\left(\bigcap_{i\in I}B_i\right) =\bigcap_{i\in I}(A\cup B_i),

A\cap\left(\bigcap_{i\in I}B_i\right) =\bigcap_{i\in I}(A\cap B_i),

A\cup\left(\bigcup_{i\in I}B_i\right) =\bigcup_{i\in I}(A\cup B_i),

\left(\bigcup_{i\in I}A_i\right)' =\bigcap_{i\in I}A_i'.

特征函数

可以用一种很简单的函数来刻画集合与集合之间的关系，这种函数称为特征函数。

设 \(X\) 为任意集合，\(f,g\) 是从 \(X\) 到实数集的函数。定义函数之间的点态运算：

\(f\le g\)：对每个 \(x\in X\)，都有 \(f(x)\le g(x)\)；
\(f+g\)：对每个 \(x\in X\)，都有 \((f+g)(x)=f(x)+g(x)\)；
\(f-g\)：对每个 \(x\in X\)，都有 \((f-g)(x)=f(x)-g(x)\)；
\(f*g\)：对每个 \(x\in X\)，都有 \((f*g)(x)=f(x)g(x)\)。

设 \(E\) 为全集，\(A\subseteq E\)。集合 \(A\) 的特征函数是从 \(E\) 到 \(\{0,1\}\) 的函数 \(\psi_A\)：

\psi_A(x)= \begin{cases} 1, & x\in A,\\ 0, & x\notin A. \end{cases}

特征函数把集合运算转化为 \(0\)、\(1\) 函数的代数运算。常用性质如下：

\(0\le\psi_A\le1\)，对任意 \(A\subseteq E\) 成立；
\(\psi_A=0\)，当且仅当 \(A=\varnothing\)；
\(\psi_A=1\)，当且仅当 \(A=E\)；
\(\psi_A\le\psi_B\)，当且仅当 \(A\subseteq B\)；
\(\psi_A=\psi_B\)，当且仅当 \(A=B\)；
\(\psi_{A'}=1-\psi_A\)；
\(\psi_{A\cap B}=\psi_A*\psi_B\)；
\(\psi_{A\cup B}=\psi_A+\psi_B-\psi_A*\psi_B\)；
\(\psi_{A\setminus B}=\psi_A-\psi_A*\psi_B=\psi_A*(1-\psi_B)\)。

其中性质 6 的证明可以直接按是否属于 \(A\) 分类：

\psi_{A'}(x)= \begin{cases} 0, & x\in A,\\ 1, & x\notin A \end{cases} =1-\psi_A(x).

性质 7 来自交集的“同时属于”：

\psi_{A\cap B}(x)=1 \Longleftrightarrow x\in A\cap B \Longleftrightarrow x\in A\text{ 且 }x\in B,

所以

\psi_{A\cap B}=\psi_A*\psi_B.

性质 8 可由 de Morgan 律推出：

\begin{aligned} \psi_{A\cup B} &=1-\psi_{(A\cup B)'}\\ &=1-\psi_{A'\cap B'}\\ &=1-\psi_{A'}*\psi_{B'}\\ &=1-(1-\psi_A)*(1-\psi_B)\\ &=\psi_A+\psi_B-\psi_A*\psi_B. \end{aligned}

性质 9 来自 \(A\setminus B=A\cap B'\)：

\begin{aligned} \psi_{A\setminus B} &=\psi_{A\cap B'}\\ &=\psi_A*\psi_{B'}\\ &=\psi_A*(1-\psi_B)\\ &=\psi_A-\psi_A*\psi_B. \end{aligned}

特征函数也可以用来证明集合恒等式。例如证明

A\cup(B\cap C)=(A\cup B)\cap(A\cup C).

只需比较两边的特征函数：

\begin{aligned} \psi_{A\cup(B\cap C)} &=\psi_A+\psi_{B\cap C}-\psi_A*\psi_{B\cap C}\\ &=\psi_A+\psi_B*\psi_C-\psi_A*\psi_B*\psi_C\\ &=(\psi_A+\psi_B-\psi_A*\psi_B) *(\psi_A+\psi_C-\psi_A*\psi_C)\\ &=\psi_{A\cup B}*\psi_{A\cup C}\\ &=\psi_{(A\cup B)\cap(A\cup C)}. \end{aligned}

因此由特征函数相等可得原集合相等。

Cartesian 积与二元关系

Cartesian 积

设 \(A,B,C\) 是非空集合，则

A\times B=C\times D \Longrightarrow A=C\land B=D.

Cartesian 积对并、交满足左右分配律：

A\times(B\cup C)=(A\times B)\cup(A\times C),

A\times(B\cap C)=(A\times B)\cap(A\times C),

(A\cup B)\times C=(A\times C)\cup(B\times C),

(A\cap B)\times C=(A\times C)\cap(B\times C).

关系的基本性质

设 \(R\subseteq X\times X\)。

自反：\((\forall x\in X)(xRx)\)；
反自反：\((\forall x\in X)(\neg xRx)\)；
对称：\(xRy\Rightarrow yRx\)；
反对称：\(xRy\land yRx\Rightarrow x=y\)；
传递：\(xRy\land yRz\Rightarrow xRz\)。

若 \(R\subseteq A\times B\)，则定义域与值域分别记作 \(\operatorname{dom}(R)\) 与 \(\operatorname{ran}(R)\)。若 \(R_1\subseteq R_2\)，则

\operatorname{dom}(R_1)\subseteq\operatorname{dom}(R_2),

\operatorname{ran}(R_1)\subseteq\operatorname{ran}(R_2).

逆关系

设 \(R\subseteq A\times B\)，其逆关系为

R^{-1}=\{(b,a)\mid(a,b)\in R\}\subseteq B\times A.

常用性质：

(R^{-1})^{-1}=R,

R\subseteq S\Longrightarrow R^{-1}\subseteq S^{-1},

(R\cup S)^{-1}=R^{-1}\cup S^{-1},

(R\cap S)^{-1}=R^{-1}\cap S^{-1},

(X\times Y)^{-1}=Y\times X.

此外，逆运算还满足

\varnothing^{-1}=\varnothing,

(R')^{-1}=(R^{-1})',

(R\setminus S)^{-1}=R^{-1}\setminus S^{-1}.

关系的合成

若 \(R\subseteq A\times B\)，\(S\subseteq B\times C\)，定义

R\circ S =\{(a,c)\mid(\exists b\in B)(aRb\land bSc)\}.

关系合成满足结合律，但一般不满足交换律。

关系的幂与闭包

对 \(R\subseteq A\times A\)，定义

$$ R^0=I_A, $$

其中 \(I_A=\{(a,a)\mid a\in A\}\)，并递归定义 \(R^{n+1}=R^n\circ R\)。

传递闭包为

R^+=\bigcup_{k=1}^{\infty}R^k =R\cup R^2\cup R^3\cup\cdots.

自反传递闭包为

R^*=\bigcup_{k=0}^{\infty}R^k =I_A\cup R\cup R^2\cup\cdots.

\(R^+\) 是包含 \(R\) 的最小传递关系；\(R^*\) 是包含 \(R\) 的最小自反传递关系。若 \(R\) 已经传递，则 \(R^+=R\)；若 \(R\) 已经自反且传递，则 \(R^*=R\)。

若 \(|A|=n\)，则只需取有限次关系幂：

R^+=\bigcup_{k=1}^{n}R^k,

R^*=\bigcup_{k=0}^{n}R^k.

等价关系、等价类与划分

关系 \(R\) 是集合 \(A\) 上的等价关系，当且仅当 \(R\) 具有自反性、对称性和传递性。

等价类与商集

对任意 \(a\in A\)，由 \(a\) 生成的等价类为

[a]_R=\{b\in A\mid bRa\}.

\(a\) 称为该等价类的代表元。所有不同等价类构成的集合

A/R=\{[a]_R\mid a\in A\}

称为 \(A\) 关于 \(R\) 的商集。

\(A/R\) 中不同等价类的个数称为等价关系 \(R\) 的秩。

对任意 \(a,b\in A\)：

a\in[a]_R,

aRb\Longleftrightarrow[a]_R=[b]_R,

\neg(aRb)\Longleftrightarrow[a]_R\cap[b]_R=\varnothing.

因此两个等价类要么完全相同，要么互不相交。

若 \(R,S\) 都是 \(A\) 上的等价关系且 \(R\subseteq S\)，则称 \(R\) 细于 \(S\)，或 \(S\) 粗于 \(R\)。此时

(\forall a\in A)([a]_R\subseteq[a]_S).

覆盖与划分

设 \(A\ne\varnothing\)，集合族 \(\Pi=\{A_i\mid i\in I\}\) 中每个 \(A_i\ne\varnothing\)。

若

A\subseteq\bigcup_{i\in I}A_i,

则称 \(\Pi\) 是 \(A\) 的覆盖。

若进一步满足

A=\bigcup_{i\in I}A_i,

并且 \(i\ne j\) 时 \(A_i\cap A_j=\varnothing\)，则称 \(\Pi\) 是 \(A\) 的划分，\(A_i\) 称为划分块。

等价关系的等价类构成一个划分；反过来，每个划分都能诱导一个等价关系。因此，等价关系与划分一一对应。

半序关系

关系 \(\preceq\) 是集合 \(A\) 上的半序关系，当且仅当它具有自反性、反对称性和传递性。系统 \((A,\preceq)\) 称为半序集。

可比较、全序与良序

半序集中的 \(a,b\) 可比较，是指

a\preceq b\lor b\preceq a.

若任意两个元素均可比较，则称该半序为全序或线性序，\((A,\preceq)\) 称为全序集或链。

若 \(A\) 的每个非空子集都有最小元，则称 \((A,\preceq)\) 为良序集。良序集一定是全序集；若 \(a\) 不是良序集的最大元，则 \(a\) 的直接后继存在。

直接后继与 Hasse 图

\(b\) 是 \(a\) 的直接后继，是指

a\prec b

且不存在 \(t\) 使

a\prec t\prec b.

此时 \(a\) 称为 \(b\) 的直接前驱。

Hasse 图表示半序关系时省略自环、传递边和箭头；若 \(b\) 是 \(a\) 的直接后继，就把 \(b\) 画在 \(a\) 上方并连边。

最大元、最小元、极大元、极小元

设 \(B\subseteq A\)。

\(M\in B\) 是 \(B\) 的最大元，当且仅当

(\forall x\in B)(x\preceq M).

\(m\in B\) 是 \(B\) 的最小元，当且仅当

(\forall x\in B)(m\preceq x).

最大元和最小元若存在，则唯一。

\(M\in B\) 是极大元，是指 \(B\) 中不存在严格大于 \(M\) 的元素；\(m\in B\) 是极小元，是指 \(B\) 中不存在严格小于 \(m\) 的元素。极大元、极小元可能不存在，也可能不唯一。

若 \(B\) 是非空有限集，则 \(B\) 至少有一个极大元和一个极小元。

上界、下界、上确界、下确界

\(u\in A\) 是 \(B\) 的上界，当且仅当

(\forall x\in B)(x\preceq u).

\(l\in A\) 是 \(B\) 的下界，当且仅当

(\forall x\in B)(l\preceq x).

所有上界中最小的一个称为上确界，记作 \(\operatorname{LUB}(B)\)；所有下界中最大的一个称为下确界，记作 \(\operatorname{GLB}(B)\)。上、下界不一定属于 \(B\)，但上确界、下确界若存在则唯一。

函数、置换与集合基数

单射、满射与双射

设 \(f:X\to Y\)。

\(f\) 是单射，当且仅当

(\forall x_1,x_2\in X) (f(x_1)=f(x_2)\Rightarrow x_1=x_2).

\(f\) 是满射，当且仅当

(\forall y\in Y)(\exists x\in X)(f(x)=y),

也就是 \(f(X)=Y\)。既单射又满射的函数称为双射。

若 \(X,Y\) 都是有限集且 \(|X|=|Y|\)，则对函数 \(f:X\to Y\)，以下条件等价：\(f\) 是单射、\(f\) 是满射、\(f\) 是双射。

复合函数与复合幂

若 \(f:X\to Y\)，\(g:Y\to Z\)，则

(g\circ f)(x)=g(f(x)).

复合函数满足结合律：

h\circ(g\circ f)=(h\circ g)\circ f.

对 \(f:X\to X\)，定义 \(f^1=f\)，\(f^{n+1}=f\circ f^n\)。

若

$$ f^2=f, $$

则称 \(f\) 为幂等函数。

置换

有限集 \(X\) 上的 \(n\) 次置换是双射

P:X\to X,

其中 \(|X|=n\)。所有 \(n\) 次置换构成集合 \(S_n\)，且

$$ |S_n|=n!. $$

恒等置换记作 \(I_X\)。置换的合成使用关系的合成方向。

等势、有穷集与可数集

若存在双射 \(f:A\to B\)，则称 \(A\) 与 \(B\) 等势，记作

A\sim B.

等势关系具有自反性、对称性和传递性。

常用基数记号为

|\varnothing|=0, \qquad |N_n|=n, \qquad |\mathbb N|=\aleph_0, \qquad |\mathbb R|=\mathfrak c.

若集合与空集或某个 \(N_n=\{1,2,\ldots,n\}\) 等势，则称为有穷集；否则称为无穷集。

若

A\sim\mathbb N,

则称 \(A\) 为可数集。无穷集 \(A\) 可数，当且仅当可以写成

A=\{a_1,a_2,a_3,\ldots\}.

常用结论：

从可数集中删去有限个元素，剩余集合仍可数；
可数集可与自己的某个无穷真子集等势；
有限个可数集的并仍是可数集；
集合无穷，当且仅当它含有可数子集；
实数区间 \((0,1)\) 不可数。

代数系统

幺元、零元与消去律

设 \((X,*)\) 是代数系统。

\(e\in X\) 是幺元，当且仅当

(\forall x\in X)(e*x=x*e=x).

\(0\in X\) 是零元，当且仅当

(\forall x\in X)(0*x=x*0=0).

幺元与零元若存在，都必唯一。

运算 \(*\) 满足消去律，是指

x*y=x*z\Rightarrow y=z,

以及

y*x=z*x\Rightarrow y=z.

分配律、反身律与 de Morgan 律

若 \(*\) 与 \(\triangle\) 是 \(X\) 上的二元运算，则 \(*\) 对 \(\triangle\) 的分配律为

x*(y\triangle z)=(x*y)\triangle(x*z),

(y\triangle z)*x=(y*x)\triangle(z*x).

若 \('\) 是一元运算，则反身律为

$$ (x')'=x, $$

二元运算与一元运算满足鞋袜律，是指

$$ (x*y)'=y'*x'. $$

de Morgan 律为

(x*y)'=x'\triangle y',

(x\triangle y)'=x'*y'.

子代数系统

设

\mathcal A=(X,O_1,O_2,\ldots,O_m).

若非空子集 \(S\subseteq X\) 对每个运算 \(O_i\) 都封闭，则这些运算限制在 \(S\) 上构成的系统称为 \(\mathcal A\) 的子代数系统。

结合律和交换律具有遗传性：若原系统中的运算满足结合律或交换律，则子代数系统中对应的运算也满足。

同态与同构

设

\mathcal A=(X,O_1,\ldots,O_m),\qquad \mathcal B=(Y,O'_1,\ldots,O'_m)

是同类型代数系统。函数 \(h:X\to Y\) 是同态，是指它保持所有运算。例如对二元运算，

$$ h(O_i(x_1,x_2))=O'_i(h(x_1),h(x_2)). $$

单射同态称为单同态，满射同态称为满同态，双射同态称为同构。若 \(\mathcal A\) 与 \(\mathcal B\) 同构，记作

\mathcal A\cong\mathcal B.

\(h(X)\) 与目标系统中相应运算构成的代数系统称为 \(\mathcal A\) 在 \(h\) 下的同态象。若 \(h\) 单射，则称为单同态；若 \(h\) 满射，则 \(h(X)=Y\)，目标系统就是满同态象。

代数系统之间的同构关系 \(\cong\) 是等价关系。

半群与群

半群

满足封闭性和结合律的代数系统 \((X,*)\) 称为半群。若还满足交换律，则称为交换半群；若有幺元，则称为含幺半群或单子。

元素的正整数次幂递归定义为

x^1=x,\qquad x^{m+1}=x^m*x.

若存在 \(x_0\in X\)，使每个 \(x\in X\) 都能写成 \(x_0^n\)，则称该半群为循环半群，\(x_0\) 称为生成元。

若非空子集 \(S\subseteq X\) 对半群运算封闭，则 \((S,*)\) 是 \((X,*)\) 的子半群。

群与交换群

若 \((G,*)\) 是含幺半群，且每个 \(g\in G\) 都有逆元，则称 \((G,*)\) 为群。验证群需要检查：

封闭性；
结合律；
幺元存在；
每个元素的逆元存在。

若群运算还满足交换律，则称为交换群或 Abel 群。

在 \(n\) 阶有限群的运算表中，每个元素在每一行、每一列都恰好出现一次。

元素的阶与循环群

群中元素 \(g\) 的阶为

o(g)=\min\{m\in\mathbb N_+\mid g^m=e\}.

若这样的 \(m\) 不存在，则称 \(g\) 的阶为无穷。

若 \(o(g)=n\)，则

e,g,g^2,\ldots,g^{n-1}

互不相同；\(g\) 与 \(g^{-1}\) 的阶相同。有限群中每个元素的阶都是有限的，并且不超过群的阶。

若 \(g\) 的阶为无穷，则

e,g,g^2,\ldots,g^n,\ldots

互不相同。

若存在 \(g_0\in G\)，使

G=\langle g_0\rangle =\{g_0^n\mid n\in\mathbb Z\},

则称 \(G\) 为循环群。循环群一定是交换群。

置换群与 Cayley 定理

\(n\) 元集合上的全部置换在复合运算下构成 \(n\) 次对称群 \(S_n\)。

Cayley 定理：每个 \(n\) 阶有限群都同构于某个 \(n\) 次置换群。

子群

若 \(S\subseteq G\) 且 \((S,*)\) 自身构成群，则称 \(S\) 是 \(G\) 的子群，记作

S\le G.

子群判别法：非空子集 \(S\subseteq G\) 是子群，当且仅当

(\forall a,b\in S)(a*b^{-1}\in S).

等价地，可以分别检查对运算封闭和对取逆封闭。\(\{e\}\) 与 \(G\) 本身称为平凡子群；循环群的子群仍是循环群。

陪集与 Lagrange 定理

设 \(H\le G\)，\(a\in G\)。左、右陪集分别为

aH=\{a*h\mid h\in H\},

Ha=\{h*a\mid h\in H\}.

全部不同左陪集构成 \(G\) 的一个划分，全部不同右陪集也构成 \(G\) 的一个划分。每个陪集都与 \(H\) 等势，因此在有限群中

$$ |aH|=|Ha|=|H|. $$

不同左陪集的个数等于不同右陪集的个数，称为 \(H\) 在 \(G\) 中的指数，记作 \([G:H]\) 或 \(|G/H|\)。

Lagrange 定理：若 \(H\) 是有限群 \(G\) 的子群，则

$$ |G|=[G:H]|H|. $$

推论：

子群的阶整除群的阶；
有限群中每个元素的阶整除群的阶；
素数阶群是循环群；
素数阶群只有两个平凡子群；
四阶群只有两种同构类型：四阶循环群与 Klein 四元群。

环与域

环

代数系统 \((R,+,\cdot)\) 是环，是指：

\((R,+)\) 是交换群；
\((R,\cdot)\) 是半群；
乘法对加法满足左右分配律。

环的加法幺元记作 \(0\)，称为环的零元；元素 \(a\) 的加法逆元记作 \(-a\)，并约定

$$ a-b=a+(-b). $$

若乘法可交换，则称为交换环；若乘法有幺元，则称为含幺环；两者同时满足时称为交换含幺环。

零因子、整环与除环

若存在非零元素 \(a,b\in R\)，使

$$ ab=0, $$

则 \(a,b\) 称为零因子。没有零因子的环满足乘法消去律。

更具体地，当 \(a\ne0\)、\(b\ne0\) 且 \(ab=0\) 时，\(a\) 称为左零因子，\(b\) 称为右零因子。

交换、含幺且无零因子的环称为整环或整区。

每个非零元素都有乘法逆元的含幺环称为除环。除环是含幺的无零因子环，但除环不一定交换，因此不一定是整环。

有限含幺环中，无零因子等价于每个非零元素都有逆元。

域

代数系统 \((F,+,\cdot)\) 是域，是指：

\((F,+)\) 是交换群；
\((F\setminus\{0\},\cdot)\) 是交换群；
乘法对加法满足分配律。

可交换的除环是域；有限整环是域。

有限整环成为域的关键是：在有限含幺环中，无零因子保证每个非零元素都有乘法逆元。

格

代数格与半序格

设 \((L,\preceq,*,\oplus)\) 是格，其中 \(*\) 表示下确界运算，\(\oplus\) 表示上确界运算。两个运算满足：

结合律；
交换律；
幂等律；
吸收律

a*(a\oplus b)=a,

a\oplus(a*b)=a.

验证代数格时，还要先确认 \(*\) 与 \(\oplus\) 对 \(L\) 封闭。格的两个运算具有对偶的对称结构。

在格中定义

a\preceq b \Longleftrightarrow a*b=a \Longleftrightarrow a\oplus b=b.

则 \(\preceq\) 是半序关系，并且

\operatorname{GLB}\{a,b\}=a*b,

\operatorname{LUB}\{a,b\}=a\oplus b.

反过来，若半序集 \((L,\preceq)\) 中任意两个元素都有上确界和下确界，则它是半序格。

模格与分配格

格满足模律，是指当 \(a\preceq c\) 时，

a\oplus(b*c)=(a\oplus b)*c.

模律也可用一对对偶恒等式表示：

(a*b)\oplus(a*c) =a*\bigl(b\oplus(a*c)\bigr),

(a\oplus b)*(a\oplus c) =a\oplus\bigl(b*(a\oplus c)\bigr).

满足模律的格称为模格。

若格满足分配律

a*(b\oplus c) =(a*b)\oplus(a*c),

a\oplus(b*c) =(a\oplus b)*(a\oplus c),

则称为分配格。

分配格一定是模格；全序格一定是分配格。

用 Hasse 图判断有限格是否为分配格时，只需要看其中是否含有典型的非分配子格：

找不到钻石格 \(M_3\) 和五边形格 \(N_5\)，则该有限格是分配格；
只要找到 \(M_3\) 或 \(N_5\) 中的任意一个，则该有限格不是分配格。

最常见的非分配格有两个。

\(M_3\) 是钻石格：

\(N_5\) 是五边形格：

分配格满足消去律：若

$$ a*b=a*c $$

且

a\oplus b=a\oplus c,

则 \(b=c\)。

有界格与有补格

存在最小元 \(0\) 和最大元 \(1\) 的格称为有界格，其中

(\forall a\in L)(0\preceq a\preceq1).

若对每个 \(a\in L\)，都存在 \(b\in L\)，使

$$ a*b=0, $$

a\oplus b=1,

则称 \(b\) 是 \(a\) 的补元；每个元素都有补元的有界格称为有补格。

在有界分配格中，每个元素的补元唯一。

布尔代数

有补的分配格

(B,\preceq,*,\oplus,',0,1)

称为布尔代数。布尔代数 \((B,\preceq,*,\oplus,',0,1)\) 简记为 \(B\)。

若 \(0=1\)，则 \(B\) 称为退化的布尔代数。以后通常不讨论这种情况，因此默认 \(|B|\ge2\)。

布尔代数中有

$$ (x')'=x. $$

布尔代数还满足以下两种消去律。若

x\oplus y=x\oplus z, \qquad x'\oplus y=x'\oplus z,

则 \(y=z\)；若

x*y=x*z, \qquad x'*y=x'*z,

则 \(y=z\)。

序关系也可以由运算刻画：

x\preceq y \Longleftrightarrow x*y=x \Longleftrightarrow x\oplus y=y \Longleftrightarrow x*y'=0 \Longleftrightarrow x'\oplus y=1.

原子与原子表示

非零元素 \(a\in B\) 是原子，是指不存在严格位于 \(0\) 与 \(a\) 之间的元素。等价地，\(a\) 是 \(0\) 的直接后继。

等价地，\(a\ne0\) 且对任意 \(x\in B\)，都有

a*x=0 \quad\text{或}\quad a*x=a.

若 \(a,b\) 都是原子，则

a*b\ne0\Longrightarrow a=b,

所以不同原子的 \(*\) 为 \(0\)。

设有限布尔代数 \(B\) 的原子集合为 \(S\)。每个非零元素 \(x\) 都能唯一表示为位于它下方的全部原子的 \(\oplus\)：

首先，每个非零元素下面至少存在一个原子：

(\forall x\in B) \bigl(x\ne0\Rightarrow(\exists a\in S)(a\preceq x)\bigr).

x=\bigoplus_{a\in S(x)}a, \qquad S(x)=\{a\in S\mid a\preceq x\}.

若 \(a_1,a_2,\ldots,a_n\) 都是原子且

x=\bigoplus_{i=1}^{n}a_i,

则对任意原子 \(b\)，

b\preceq x \Longrightarrow b\in\{a_1,a_2,\ldots,a_n\}.

Stone 定理：有限布尔代数 \(B\) 与其原子集 \(S\) 的幂集代数

(2^S,\subseteq,*,\oplus,{}',\varnothing,S)

同构。其中在幂集代数中，\(A*B=A\cap B\)，\(A\oplus B=A\cup B\)。

图中的路与连通性

无重复边的路称为简单路，无重复边的圈称为简单圈；无重复顶点的路称为初级路，无重复顶点的圈称为初级圈。

对有向图：

任意两顶点相互可达，称为强连通；
任意两顶点中至少有一个可达另一个，称为单向连通；
略去边的方向后连通，称为弱连通。

强连通一定推出单向连通，单向连通一定推出弱连通；两个逆命题通常都不成立。

极大的强连通子图、单向连通子图和弱连通子图分别称为强连通分支、单向连通分支和弱连通分支。

简单有向图中，每个顶点恰属于一个强连通分支和一个弱连通分支；每条边恰属于一个弱连通分支。

此外，每个顶点和每条边都至少属于一个单向连通分支。

Euler 路与 Euler 圈

Euler 路是恰好经过每条边一次的简单路；Euler 圈是恰好经过每条边一次的简单圈；含有 Euler 圈的图称为 Euler 图。

对无孤立点的无向图 \(G\)：

\(G\) 是 Euler 图，当且仅当 \(G\) 连通且所有顶点的度均为偶数；
\(G\) 存在 Euler 路，当且仅当 \(G\) 连通且恰有两个奇度顶点，这两个顶点分别是路的起点和终点。

Fleury 算法：从一个奇度顶点出发，每经过一条边就将其标记；除非没有其他选择，否则不走当前图中的割边。

对无孤立点的有向图 \(G\)：

\(G\) 有 Euler 圈，当且仅当 \(G\) 连通且每个顶点的入度等于出度；
\(G\) 有 Euler 路，当且仅当除两个顶点外其余顶点的入度都等于出度，其中起点满足 \(d^+-d^-=1\)，终点满足 \(d^--d^+=1\)。

中国邮路问题

中国邮路问题要求在带权连通图中寻找一条经过每条边至少一次并回到起点的最短闭路。它等价于选择一些需要重复的边，使重复后得到的多重图成为 Euler 图，并使重复边的总权最小。

管氏定理：设 \(E'\) 为选出的重复边集。\(E'\) 最优，当且仅当对图中的每个初级圈 \(C\)，\(C\) 中重复边的长度之和不超过圈长的一半，即

\sum_{e\in E'\cap E(C)}w(e) \le \frac12\sum_{e\in E(C)}w(e).

证明所依据的两个要点是：

若某条边重复 \(k\ge2\) 次后得到 Euler 图，则少重复两次仍保持各顶点度数的奇偶性，因此仍是 Euler 图；
在一个初级圈上，把原来的重复边取消，并把原来未重复的边各重复一次，各顶点的度数只改变 \(0\) 或 \(2\)，不会破坏 Euler 性。若原重复边长度超过圈长的一半，这一替换会降低总重复长度，说明原方案并非最优。

Edmonds-Johnson 算法的基本步骤：