离散数学概念总结

命题逻辑

命题

能确定真值的陈述句

原子命题

不能再细分的命题

复合命题

由联结词、标点符号和原子命题复合构成的命题

重言式

给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为 $T$ ，则称命题公式为重言式

蕴含式

设 $p, q$ 为两个命题，复合命题“如果 $p$ 则 $q$ ”称为 $p$ 与 $q$ 的蕴含式，记作 $p \rightarrow q$

矛盾式

无论对分量作怎样的指派，其对应的真值永为 $F$ ，记为 $F$

子公式

如果 $X$ 是合式公式 $A$ 的一部分，且 $X$ 本身也是一个合式公式，则称 $X$ 为公式 $A$ 的子公式

置换

设 $X$ 是合式公式 $A$ 的子公式，且 $X \Leftrightarrow Y$ ，将 $A$ 中的 $X$ 用 $Y$ 来置换，得到新的公式 $B$ ，则 $A \Leftrightarrow B$

命题公式

单个命题变元是一个命题公式

如果 $A$ 和 $B$ 是命题公式，那么 $\neg A, (A \land B), (A \lor B), (A \rightarrow B), (A \Leftrightarrow B)$ 都是命题公式

当且仅当能够有限次地应用(1),(2)生成的公式是命题公式

命题公式的等价

设命题公式 $A$ 和 $B$ ， $P_1$ , $P_2$ , ..., $P_n$ 为所有出现于 $A$ 和 $B$ 中的原子变元，若给 $P_1$ , $P_2$ , ..., $P_n$ 任一组真值指派， $A$ 和 $B$ 的真值都相同。则称 $A$ 和 $B$ 是等价的

命题公式的对偶式

命题公式 $A$ 中含联结词 $\land$ ， $\lor$ ，将 $\land$ 与 $\lor$ 互换，T 与 F 互换所得公式 $A^{*}$ 称为 $A$ 的对偶式

联结词

$\overline{\lor}$ ：不可兼析取

$\xrightarrow{c}$ ：条件否定

$\uparrow$ ：与非

$\downarrow$ ：或非

范式

求范式的步骤

将命题公式的联结词全部化为 $\neg, \land, \lor$

利用德·摩根律，将否定符号 $\neg$ 直接移到各命题变元之前

利用分配律、结合律将命题公式化为范式

小项

$n$ 个命题变元 $P_1, P_2, \dots, P_n$ 的合取式，称为布尔合取或小项，在任一小项中
1. 每个变元 $P_i$ 与它的否定 $\neg P_i$ 不能同时出现
1. 但 $P_i$ 与 $\neg P_i$ 必须出现且仅出现一次

大项

$n$ 个命题变元 $P_1, P_2, \dots, P_n$ 的析取式，称为布尔析取或大项，在任一小项中
1. 每个变元 $P_i$ 与它的否定 $\neg P_i$ 不能同时出现
1. 但 $P_i$ 与 $\neg P_i$ 必须出现且仅出现一次

谓词逻辑

谓词公式

原子谓词公式是谓词公式

若 $A$ 是谓词公式则 $\neg A$ 是一个谓词公式

若 $A$ 和 $B$ 都是谓词公式，则 $(A \land B)$ ， $(A \lor B)$ ， $(A \rightarrow B)$ 和 $(A \Leftrightarrow B)$ 是谓词公式

如果 $A$ 是谓词公式， $x$ 是 $A$ 中出现的任何变元，则 $(\forall x)A$ 和 $(\exist x)A$ 都是谓词公式

只有经过有限次应用规则(1), (2), (3), (4)所得到的公式是谓词公式

谓词公式的等价

任意给定两个谓词公式wff $A$ 和wff $B$ ，设它们有共同的个体域 $E$ ，若对 $A$ 和 $B$ 的任一组变元进行赋值，所得命题的真值相同，则称谓词公式 $A$ 和 $B$ 在 $E$ 上是等价的，并记作： $A \Leftrightarrow B$

前束范式

定义

所有量词都位于该公式的最左边

所有量词前都不含否定

量词都辖域都延伸到整个公式都末端

运算方法

消去 $\Rightarrow$ 、 $\Leftarrow$

否定 $\neg$ 右移

量词左移（分配等值、辖域收缩扩张、变项改名）

分配等值：
- $(\forall x)(A(x) \land B(x)$ $\equiv$ $(\forall x)A(x) \land (\forall x)B(x)$ $\forall$ 对 $\lor$ 不满足
- $(\exist x)(A(x) \lor B(x))$ $\equiv$ $(\exist x)A(x) \lor (\exist x)B(x)$ $\exist$ 对 $\land$ 不满足
辖域收缩扩张： $(\forall x)(A(x) \lor B(x)) \equiv (\forall x)A(x) \lor B$ ， $A(x)$ 含 $x$ 自由出现， $B$ 不含 $x$

推理理论

P规则

前提引入：前提在推导过程中的任何时候都可以引入

T规则

结论引用：在推导中，如果有一个或多个公式重言蕴含着公式 $S$ （结论），则公式 $S$ 可以引入推导之中

CP规则

要证明，转化为证明
- R：附加前提

全称指定规则（US）

$\Large{\frac{(\forall x)P(x)}{\therefore P(c)}}$

$\Large{\frac{(\forall x)P(x)}{\therefore P(y)}}$

全称推广原则（UG）

$\Large{\frac{P(x)}{\therefore (\forall x)P(x)}}$

存在制定原则（ES）

$\Large{\frac{(\exist x)P(x)}{\therefore P(c)}}$

存在推广原则（EG）

$\Large{\frac{P(c)}{\therefore (\exist x)P(x)}}$

集合论

平凡子集

非空集合 $A$ 的子集 $A$ 和 $\emptyset$

全集

在一定范围内，若所有集合均为某一集合的子集，则称该集合为全集，记作 $E$

幂集

给定集合 $A$ ，以 $A$ 的全体子集为元素构成的集合，称为 $A$ 的幂集，记为 $\mathscr{P}$ （或 $2^A$ ）

商集

设 $R$ 为非空集合 $A$ 上的等价关系，其等价类集合 $\{[a]_R|a \in A\}$ 称为 $A$ 关于 $R$ 的商集，记为 $A \setminus R$

集合的划分

设 $A$ 为非空集合， $S = \{ S_1, S_2, ..., S_n \}$ ，其中 $S_i \subseteq A$ , $S_i \neq \varnothing (i = 1, 2, ..., m)$ ，
$\bigcup_{i = 1}^m S_i = A$
$S_i \bigcap S_j = \varnothing$ $(i \neq j , i, j = 1, 2, ..., m)$ ，则称 $S$ 为 $A$ 的划分

例：集合 $A$ 的一个划分确定 $A$ 的元素间的一个等价关系

证明：

设集合 $A$ 有一个划分 $S = \{S_1, S_2, \cdots, S_m\}$ ，现定义一个关系 $R$ ， $aRb$ 当且仅当 $a, b$ 在同一分块中。可以证明这样规定的关系 $R$ 是一个等价关系。因为

$a$ 与 $a$ 在同一分块中，故必有 $aRa$ 。即 $R$ 是自反的

若 $a$ 与 $b$ 在同一分块中， $b$ 与 $a$ 也必在同一分块中，即 $aRb \Rightarrow bRa$ ,故 $R$ 是对称的

若 $a$ 与 $b$ 在同一分块中， $b$ 与 $c$ 在同一分块中，因为

$S_i \cap S_j = \varnothing (i \neq j)$

即 $b$ 属于且仅属于一个分块，故 $a$ 与 $c$ 必在同一分块中，故有

$(aRb) \land (bRc) \Rightarrow (aRc)$

即 $R$ 是传递的。

$R$ 满足上述三个条件，故 $R$ 是等价关系，由 $R$ 的定义可知， $S$ 就是 $A \setminus R$

集合的覆盖

设 $A$ 为非空集合， $S = \{S_1, S_2, ..., S_n\}$ 其中 $S_n \subseteq A$ , $S_i \neq \varnothing$ $(i = 1, 2, ..., m)$
$\bigcup_{i = 1}^m S_i = A$
则称 $S$ 为 $A$ 的覆盖

交叉划分

若 $\{A_1, A_2, \cdots, A_r\}$ 与 $\{B_1, B_2, \cdots, B_s\}$ 是同一集合 $X$ 的两种划分，则其中所有 $A_i \cap B_i \neq \varnothing$ 组成的集合，称为是原来两种划分的交叉划分

划分的加细

设 $\{A_1, A_2, \cdots, A_r\}$ 与 $\{B_1, B_2, \cdots, B_s\}$ 是同一集合 $X$ 的两种划分，若对于每个 $A_j$ 均有 $B_k$ ，使 $A_j \subseteq B_k$ ，则 $\{A_1, A_2, \cdots, A_r\}$ 称为是 $\{B_1, B_2, \cdots, B_s\}$ 的加细

集合的等势

集合 $A$ 的元素与集合 $B$ 的元素之间存在一一对应

集合的对称差

设 $A$ 和 $B$ 为任意两个集合， $A$ 和 $B$ 的对称差是由或者属于 $A$ ，或者属于 $B$ ，但不能既属于 $A$ 又属于 $B$ 但元素所组成的集合

集合的基数

所有与集合 $A$ 等势的集合所组成的集合，叫做集合 $A$ 的基数，记为 $K[A]$ （或 $\overline{\overline{A}}$ ）

无限集

设 $A$ 为一个集合，若 $A$ 为空集或与集合 $\{0, 1, \cdots, n - 1\}$ 等势，则称 $A$ 为有限集，否则 $A$ 为无限集
等价定义： $A$ 是无限集当且仅当与其某一个真子集等势

可数集

与自然数集合等势的集合

连续统的势

$\aleph$ ：我们把集合 $(0, 1)$ 的基数记为" $\aleph$ "，因为 $(0, 1)$ ~ $R$ ，故 $K[R]=\aleph$

可数集合的基数

$\aleph_0$ ：与自然数集合等势的任意集合称为可数的，可数集合的基数用 $\aleph_0$ 表示

集合的置换

设 $S$ 是一个非空集合，从集合 $S$ 到 $S$ 的一个双射称为 $S$ 的一个置换

集合的运算

集合的对称差

$A \oplus B = (A - B) * (B - A) = \{x|x \in A \overline{\lor} x \in B\}$

又称环和

关系

笛卡尔积的子集为关系

笛卡尔积

令 $A$ 和 $B$ 是任意两个集合，若序偶的第一个成员是 $A$ 的元素，第二个成员是 $B$ 的元素，所有这样的序偶集合，称为集合 $A$ 和 $B$ 的笛卡尔积，记作 $A \times B$

集合 $A$ 上的二元关系

$A \times A$ 的一个子集为集合 $A$ 上的一个二元关系

对称关系

设 $R$ 是 $X$ 上的关系，对于每一个 $x, y \in X$ ，每当 $xRy$ 时，就有 $yRx$ ，则称 $R$ 为 $X$ 上的对称关系

反对称关系

设 $R$ 为 $X$ 上的关系，对于每一个 $x, y \in X$ ，每当 $xRy$ ， $yRx$ 时，必有 $x = y$ ，则称 $R$ 为 $X$ 上的反对称关系

等价关系

一个二元关系若满足自反性，对称性和传递性则称为等价关系

等价类

设 $R$ 是非空集合 $A$ 上的等价关系， $\forall a \in A$ ，令

$[a]_R = \{x|x \in A \land aRx\}$

称 $[a]_R$ 为 $a$ 关于 $R$ 的等价类

简称为 $a$ 的等价类，简记为 $[a]$

$a$ 称为等价类 $[a]_R$ 的代表元素

相容关系

若集合 $A$ 上的二元关系 $R$ 是：
1. 自反的
1. 对称的
则称 $R$ 是 $A$ 上的相容关系

相容关系又称相似关系

相容类

设 $R$ 是集合 $A$ 的相容关系，子集 $B$ 满足 $\forall x, y \in B, xRy$ ，则称 $B$ 为 $A$ 关于 $R$ 的相容类

最大相容类

设 $R$ 是集合 $A$ 的相容关系，子集 $B$ 满足：
1. $\forall x, y \in B, xRy$
1. $\forall x \in A - B, \exist z \in B, x$ R $z$
则称 $B$ 为 $A$ 关于 $R$ 的最大相容类

完全覆盖

在集合 $A$ 上给定相容关系 $R$ ，其最大相容类的集合，称作集合 $A$ 的完全覆盖，记作 $C_R(A)$

偏序关系

若集合 $A$ 上的二元关系 $R$ 是自反的、反对称的和传递的，则称 $R$ 是 $A$ 上的偏序关系

序偶 $<A, R>$ 称为偏序集

又称半序

盖住

设 $<A, \preccurlyeq>$ 为偏序集， $\forall x, y \in A$ ，若 $x \preccurlyeq y，x \neq y$ ，且不存在 $z \in A$ 使得 $x \preccurlyeq z \preccurlyeq y$ ，则称 $y$ 盖住 $x$

哈斯图

设有偏序集 $<A, \preccurlyeq>$ ， $\forall x, y \in A (x \neq y)$ ，适当排列结点的顺序使得：
1. 若 $x \preccurlyeq y$ ，则将 $x$ 画在 $y$ 的下方
1. 若 $y$ 盖住 $x$ ，则用一条直线连接 $x$ 和 $y$

偏序集合的子集的特殊元素

设 $<A, \preccurlyeq>$ 为偏序集， $B \subseteq A$ ，对 $a \in A$ ， $b \in B$

极大元

若 $B$ 中不存在元素 $x$ ，使 $b \neq x$ 且 $b \preccurlyeq x$ ，则 $b$ 为 $B$ 的极大元

$(\forall x \in B)(b \preccurlyeq x \rightarrow x = b)$

极小元

若 $B$ 中不存在元素 $x$ ，使 $b \neq x$ 且 $x \preccurlyeq b$ ，则 $b$ 为 $B$ 的极小元

$(\forall x \in B)(x \preccurlyeq b \rightarrow x = b)$

最大元

若 $B$ 中任意元素 $x$ ，有 $x \preccurlyeq b$ ，则称 $b$ 为 $B$ 的最大元

$(\forall x)(x \in B \rightarrow x \preccurlyeq b)$

最小元

若 $B$ 中任意元素 $x$ ，有 $b \preccurlyeq x$ ，则称 $b$ 为 $B$ 的最小元

$(\forall x)(x \in B \rightarrow b \preccurlyeq x)$

最大元与极大元的比较

最大元与其他所有元素均可比；而极大元不一定与所有元素都可比，只要没有比它大的元素，它就是极大元

都不一定存在，但非空有限元中极大元一定存在

最大元存在即唯一，极大元可有多个

唯一的极大元 $\iff$ 最大元

上界

若 $(\forall x)(x \in B \rightarrow x \preccurlyeq a)$ 成立，则称 $a$ 为 $B$ 的上界

下界

若 $(\forall x)(x \in B \rightarrow a \preccurlyeq x)$ 成立，则称 $a$ 为 $B$ 的下界

上确界

设 $a$ 是 $B$ 的一个上界，若对所有上界 $y$ 均有 $a \preccurlyeq y$ ，则称 $a$ 为 $B$ 的最小上界或上确界，记为 $\mathrm{LUB}B$ 或 $\mathrm{sup}B$

下确界

设 $b$ 是 $B$ 的一个下界，若对 $B$ 的所有下界 $z$ 均有 $z \preccurlyeq b$ ，则称 $b$ 为 $B$ 的最大下界或下确界，记为 $\mathrm{GLB}B$ 或 $\mathrm{inf}B$

拟序关系

设 $A$ 是一个集合，如果 $A$ 上的一个集合 $R$ ，满足反自反的和传递的，则称 $R$ 是 $A$ 上的一个拟序关系

全序关系

在偏序集 $<A, \preccurlyeq>$ 中，若 $A$ 是一个链，则称 $<A, \preccurlyeq>$ 为全序集合或线序集合

自反、反对称、传递、每个元素之间都有关系

良序集合

在偏序集 $<A, \preccurlyeq>$ 中，若 $A$ 的每一个非空子集总含有最小元，则称 $<A, \preccurlyeq>$ 为良序集合

自反、反对称、传递、每个元素之间都有关系、子集存在最小元

称二元关系 $\preccurlyeq$ 为 $A$ 上的良序

$\{良序\} \subseteq \{全序\} \subseteq \{偏序\}$

对称闭包

设 $R$ 是一个二元关系，如果存在一个关系 $R'$ 满足： $R'$ 是对称的， $R' \supseteq R$ ，对于任何对称关系 $R''$ ，如果有 $R'' \supseteq R$ 就有 $R'' \supseteq R'$ ，则称 $R'$ 为 $R$ 的对称闭包

自反闭包

设 $R$ 是一个二元关系，如果存在一个关系 $R'$ 满足： $R'$ 是自反的； $R' \supseteq R$ ；对于任何自反的关系 $R''$ 如果有 $R'' \supseteq R$ 就有 $R'' \supseteq R'$ ，则称 $R'$ 为 $R$ 的自反闭包

传递闭包

设 $R$ 是一个二元关系，如果存在一个关系 $R'$ 满足： $R'$ 是传递的； $R' \supseteq R$ ；对于任何传递的关系 $R''$ 如果有 $R'' \supseteq R$ 就有 $R'' \supseteq R'$ ，则称 $R'$ 为 $R$ 的传递闭包

Warshall算法

procedure Warshell（ $M_R: n \times n$ 的 0-1 矩阵）

$W := M_R$

for $k := 1$ to $n$ //按列遍历

for $i := 1$ to $n$

for $j := 1$ to $n$

$w_{ij} := w_{ij} \lor (w_{ik} \land w_{kj})$ //若第 $j$ 列是1则把第 $j$ 行上的元素逻辑加到第 $i$ 行上

return $W\{W = [w_{ij}] 是 M_{R^*}\}$

主对角线可跳过

第 $i$ 行均为零可跳过

链

设 $<A, \preccurlyeq>$ 是一个偏序集合，在 $A$ 的一个子集中，如果每两个元素都是有关系的，则这个子集为链

反链

设 $<A, \preccurlyeq>$ 是一个偏序集合，在 $A$ 的一个子集中，如果每两个元素都是无关的，则这个子集为反链

函数

设 $X$ 和 $Y$ 是任何两个集合， $f$ 是 $X$ 到 $Y$ 的一个关系，如果对于每一个 $x \in X$ ，有唯一的 $y \in Y$ ，使得 $<x, y> \in f$ ，则称关系 $f$ 为函数

亦称 $f$ 为 $X$ 到 $Y$ 的映射

满射

对于映射 $f: X \rightarrow Y$ ，如果 $ranf = Y$ 则称这个映射为满射

入射

对于映射 $f: X \rightarrow Y$ ，如果 $\forall y \in ranf$ 都存在唯一的 $x \in X$ 使得 $f(x) = y$ ，则称 $f: X \rightarrow Y$ 是入射（或一对一映射）

双射

若 $f: X \rightarrow Y$ 既是满射又是入射，则称 $f: X \rightarrow Y$ 是双射

逆函数

设 $f: X \rightarrow Y$ 是一双射函数，称 $Y \rightarrow X$ 的双射函数 $f^c$ 为 $f$ 的逆函数，记作 $f^{-1}$

常函数

函数 $f: X \rightarrow Y$ ， $\exist y_0 \in Y$ ，使得 $\forall x \in X$ ， $f(x) = y_0$ ，即 $f(X) = y_0$

恒等函数

如果 $I_X = \{<x, x>|x \in X\}$ ，则称函数 $I_X: X \rightarrow X$ 为恒等函数

基数的比较

概念

如果两个集合能够建立双射函数，则该两集合应具有相同的基数
连续统的势 $\aleph$ ：我们把集合 $(0, 1)$ 的基数记为" $\aleph$ "，因为 $(0, 1)$ ~ $R$ ，故 $K[R]=\aleph$
可数集合的基数 $\aleph_0$ ：与自然数集合等势的任意集合称为可数的，可数集合的基数用 $\aleph_0$ 表示
若从集合 $A$ 到集合 $B$ 存在一个入射，则称 $A$ 的基数不大于 $B$ 的基数，记作 $K[A] \leqslant K[B]$
若从集合 $A$ 到集合 $B$ 存在一个入射，但不存在双射，则称 $A$ 的基数小于 $B$ 的基数，记作 $K[A] < K[B]$

Cantor-Schroder-Bernstein 定理

设 $A$ 和 $B$ 是任意集合，若 $K[A] \leqslant K[B], K[B] \leqslant K[A]$ ，则 $K[A] = K[B]$

例题

证明 $[0,1]$ 和 $(0,1)$ 有相同的基数

证明：作入射函数：

$f: (0, 1) \rightarrow [0, 1], f(x) = x$

$g: [0, 1] \rightarrow (0, 1), g(x) = \frac{x}{2} + \frac{1}{4}$

设 $A = N$ ， $B=(0,1)$ ， $K[A] = \aleph_0$ ， $K[B] = \aleph$ ，求证： $K[A \times B] = \aleph$

证明：
定义一个从 $A \times B$ 到正实数的函数 $f$ ，

$f: A \times B \rightarrow \{x|x \in R_+\}$ > $f(n, x) = n + x$

因为 $f$ 是一个入射函数，且 $K[R_+] = \aleph$

所以 $K[A \times B] \leqslant \aleph$

此外，作映射 $g: (0, 1) \rightarrow A \times B$

$g(x) = <0, x>$

因为 $g$ 是入射的，故 $\aleph \leqslant K[A \times B]$

因此 $K[A \times B] = \aleph$

代数系统

闭运算

对于集合 $A$ ，一个从 $A^n$ 到 $B$ 的映射，称为集合 $A$ 上的一个 $n$ 元运算，如果 $B \subseteq A$ ，则称该 $n$ 元运算是封闭的（集合 $R$ 上的运算的结果都是在原来的集合 $R$ 中）

代数系统

一个非空集合 $A$ 连同若干个定义在该集合上的运算 $f_1, f_2, \cdots , f_k$ 所组成的系统就称为一个代数系统，记作 $<A, f_1, f_2, \cdots, f_k>$

二元运算

运算性质

封闭性

设 $*$ 是定义在集合 $A$ 上的一个二元运算，如果对于任意的 $x, y \in A$ ，都有 $x * y \in A$ ，则称二元运算 $*$ 在 $A$ 上是封闭的
- 表中每个元素都属于 $A$

可交换性

设 $*$ 是定义在集合 $A$ 上的一个二元运算，如果对于任意的 $x, y \in A$ ，都有 $x * y = y * x$ ，则称该二元运算是可交换的
- 表关于主对角线是对称的

可结合性

设 $*$ 是定义在集合 $A$ 上的一个二元运算，如果对于任意的 $x, y \in A$ ，都有 $(x * y) * z = x * (y * z)$ ，则称该二元运算 $*$ 是可结合的

可分配性

设 $*, \triangle$ 是定义在集合 $A$ 上的两个二元运算，如果对于任意的 $x, y \in A$ ，都有

$x * (y \triangle z) = (x * y) \triangle (x * z)$
$(y \triangle z) * x = (y * x) \triangle (z * x)$
则称运算 $*$ 对运算 $\triangle$ 是可分配的

吸收律

设 $*, \triangle$ 是定义在集合 $A$ 上的两个二元运算，如果对于任意的 $x, y \in A$ ，都有

$x * (x \triangle y) = x$
$x \triangle (x * y) = x$
则称运算 $*$ 和运算 $\triangle$ 满足吸收律

等幂性

设 $*$ 是定义在集合 $A$ 上的一个二元运算，如果对于任意的 $x \in A$ ，都有 $x * x = x$ ，则称运算 $*$ 是等幂的
- 运算表的主对角线上的每个元素与它所在的行（列）表头元素相同

幺元

左幺元： $\exist e_l \in A$ ， $\forall x \in A$ 都有 $e_l * x = x$
右幺元： $\exist e_r \in A$ ， $\forall x \in A$ 都有 $x * e_r = x$
幺元： $\exist e \in A$ ， $\forall x \in A$ ，有 $e * x = x * e = x$
- 设 $*$ 是定义在集合 $A$ 上的一个二元运算，且在 $A$ 中有关于运算 $*$ 的左幺元 $e_l$ 和右幺元 $e_r$ ，则 $e_l = e_r = e$ ，且 $A$ 中的幺元是唯一的
表中元素所对应的行和列依次与运算表的行和列一致

零元

左零元： $\exist \theta_l \in A$ ， $\forall x \in A$ 都有 $\theta_l * x = \theta_l$
右幺元： $\exist \theta_r \in A$ ， $\forall x \in A$ 都有 $x * \theta_r = \theta_r$
幺元： $\exist \theta \in A$ ， $\forall x \in A$ ，有 $\theta * x = x * \theta = \theta$
- 设 $*$ 是定义在集合 $A$ 上的一个二元运算，且在 $A$ 中有关于运算 $*$ 的左零元 $\theta_l$ 和右零元 $\theta_r$ ，则 $\theta_l = \theta_r = \theta$ ，且 $A$ 中的零元是唯一的
表中元素所对应的行和列中的元素都与该元素相同

逆元

左逆元： $\exist b \in A$ ， $\exist a \in A$ ，使得 $b * a = e$
右逆元： $\exist b \in A$ ， $\exist a \in A$ ，使得 $a * b = e$
逆元： $\exist b \in A$ ， $\exist a \in A$ ， $b$ 既是 $a$ 的右逆元又是 $a$ 的左逆元
- $b = a^{-1}$
左右逆元不一定相等、不一定唯一、不一定同时存在
表中 $a$ 和 $b$ 互逆，当且仅当位于 $a$ 所在行， $b$ 所在列的元素以及 $b$ 所在行， $a$ 所在列的元素都是幺元

群

群的概念

群的定义

$\{群\} \subset \{独异点\} \subset \{半群\} \subset \{广群\}$

广群

一个代数系统 $<S, *>$ ，其中 $S$ 是非空集合， $*$ 是 $S$ 上的一个二元运算，如果 $*$ 是封闭的，则称代数系统 $<S, *>$ 为广群

半群

一个代数系统 $<S, *>$ ，其中 $S$ 是非空集合， $*$ 是 $S$ 上的一个二元运算，如果：
1. 运算 $*$ 是封闭的
1. 运算 $*$ 是可结合的，即对任意的 $x, y, z \in S$ 满足
  
  $(x * y) * z = x * (y * z)$
  
  则称代数系统 $<S, *>$ 为半群

子半群

设 $<S, *>$ 是一个半群， $B \subseteq S$ 且 $*$ 在 $B$ 上是封闭的，那么 $<B, *>$ 也是一个半群。通常称 $<B, *>$ 是半群 $<S, *>$ 的子半群

独异点

含有幺元的半群称为独异点
- 性质：
  - 设 $<S, *>$ 是一个独异点，则在关于运算 $*$ 的运算表中任何两行和两列都是不相同的
  - 设 $<S, *>$ 是独异点，对于任意 $a, b \in S$ ，且 $a, b$ 均有逆元，则
  - $(a^{-1})^{-1} = a$
  - $a * b$ 有逆元，且 $(a * b)^{-1} = b^{-1} * a^{-1}$

群

设 $<G, *>$ 是一个代数系统，其中 $G$ 是非空集合， $*$ 是 $G$ 上的一个二元运算，如果
1. 运算 $*$ 是封闭的
1. 运算 $*$ 是可结合的
1. 存在幺元 $e$
1. 对于每一个元素 $x \in G$ ，存在这它的逆元 $x^{-1}$
则称 $<G, *>$ 是一个群

有限群

设 $<G, *>$ 是一个群。如果 $G$ 是有限集，那么称 $<G, *>$ 为有限群

有限群的阶数

有限集 $G$ 中元素的个数，记为 $|G|$

无限群

设 $<G, *>$ 是一个群。如果 $G$ 是无限集，那么称 $<G, *>$ 为无限群

等幂元

代数系统 $<G, *>$ 中，如果存在 $a \in G$ ，有 $a * a = a$ ，则称 $a$ 为等幂元

子群

设 $<G, *>$ 是一个群， $S$ 是 $G$ 的一个非空子集，如果 $<S, *>$ 也构成群，则称 $<S, *>$ 是 $<G, *>$ 的一个子群

阿贝尔群

如果群 $<G, *>$ 中的运算 $*$ 是可交换的，则该群为阿贝尔群，或称交换群

循环群

设 $<G, *>$ 为群，若存在 $a \in G$ ，使得 $G$ 中的任意元素都由 $a$ 的幂组成，则称该群为循环群，元素 $a$ 称为循环群 $G$ 的生成元

左陪集

设 $<H, *>$ 是群 $<G, *>$ 的一个子群， $a \in G$ ，则集合 $\{a\}H$ 称为由 $a$ 所确定的 $H$ 在 $G$ 中的左陪集

拉格朗日定理

设 $<H, *>$ 是有限群 $<G, *>$ 的一个子群， $|G|=n$ ， $|H|=m$ ，则 $m|n$

群的性质

群中不可能有零元
- 零元 $\theta$ 不存在逆元
设 $<G, *>$ 是一个群，对于 $a, b \in G$ ，必存在唯一的 $x \in G$ ，使得 $a * x = b$
消去律：设 $<G, *>$ 是一个群，对于任意的 $a, b, c \in G$ ，如果有 $a * b = a * c$ 或者 $b * a = c * a$ ，则必有 $b = c$
群 $<G, *>$ 的运算表中的每一行或每一列都是 $G$ 的元素的一个置换
设 $<G, *>$ 是一个群， $B$ 是 $G$ 的非空子集，如果 $B$ 是一个有限集，那么，只要运算 $*$ 在 $B$ 上封闭， $<B, *>$ 必定是 $<G, *>$ 的子群
设 $<G, \triangle>$ 是群， $S$ 是 $G$ 的非空子集，如果对于 $S$ 中的任意元素 $a$ 和 $b$ 有 $a \triangle b^{-1} \in S$ ，则 $<S, \triangle>$ 是 $<G, \triangle>$ 的子群
群是阿贝尔群的充要条件：对任意的 $a, b \in G$ ，有 $(a * b) * (a * b) = (a * a) * (b * b)$
设 $<G, *>$ 是一个由元素 $a \in G$ 生成的有限循环群。如果 $|G| = n$ ，则 $a^n = e$ ，且 $G = \{a, a^2, a^3, \cdots, a^{n-1}, a^n=e\}$
- $n$ 为元素 $a$ 的阶
群的积：设 $<G, *>$ 是一个群， $A, B \in \mathscr{P}(G)且 A \neq \varnothing, B \neq \varnothing$ , 记 $AB = \{a * b|a \in A, b \in B\}$
群的逆： $A^{-1} = \{a^{-1}|a \in A \}$

拉格朗日定理

推论：
1. 任何质数阶的群不可能有非平凡子群
- 非平凡子群： $<\{e\}, *>$ , $<G, *>$
1. 有限群 $<G, *>$ 中任何元素 $a$ 的阶可整除 $|G|$ ，进而有 $a^{|G|}=e$
1. 质数阶的群一定是循环群

陪集

设 $<H, *>$ 是群 $<G, *>$ 的子群， $\forall a \in G$
- 左陪集： $\{a\}H = \{a * h|h \in H\}$ 称为由 $a$ 所确定的 $H$ 在 $G$ 中的左陪集，简称为 $H$ 关于 $a$ 的左陪集记为 $aH$
- 右陪集： $H\{a\} = \{h * a|h \in H\}$ 称为由 $a$ 所确定的 $H$ 在 $G$ 中的右陪集，简称为 $H$ 关于 $a$ 的右陪集记为 $Ha$

同态与同构

同态

设 $<A, *>$ 和 $<B, \triangle>$ 是两个代数系统，若
1. $f: A \rightarrow B$ 是一函数
1. $\forall a, b \in A$ ，有 $f(a*b) = f(a) \triangle f(b)$
则称 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 到一个同态映射，简称同态
$<A, *>$ 同态于 $<B, \triangle>$ ，记作 $A \sim B$
称 $<f(A), \triangle>$ 为 $<A, *>$ 到一个同态象
先算后映 = 先映后算
- 例： $a \rightarrow a_1$ , $b \rightarrow b_1$ $\Leftrightarrow$ $a * b \rightarrow a_1 \triangle b_1$

自同态

设 $<A, *>$ 是一个代数系统，若 $f$ 是 $<A, *>$ 到 $<A, *>$ 的一个同态，则称 $f$ 为自同态

满同态

设 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的一个同态，若 $f$ 是 $A$ 到 $B$ 的满射，则称 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的满同态（或同态满射）

单一同态

设 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的一个同态，若 $f$ 是 $A$ 到 $B$ 的入射（即单射），则称 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的单一同态

同态核

设 $f$ 是群 $<G, *>$ 到群 $<H, \triangle>$ 的同态， $e_H$ 是 $<H, \triangle>$ 的幺元，称 $Ker(f) = \{x|x \in G \land f(x) = e_H\}$ 为同态映射的核，简称同态核

同态的性质

设 $f$ 是代数系统 $<A, *>$ 到 $<B, \triangle>$ 的同态映射
- 若 $<A, *>$ 是半群，则 $<f(A), \triangle>$ 也是半群
- 若 $<A, *>$ 是独异点，则 $<f(A), \triangle>$ 也是独异点
- 若 $<A, *>$ 是群，则 $<f(A), \triangle>$ 也是群
- 若 $<A, *>$ 是阿贝尔群，则 $<f(A), \triangle>$ 也是阿贝尔群
设 $f$ 是群 $<G, *>$ 到群 $<H, \triangle>$ 的同态，则 $<Ker(f), *>$ 是群 $<G, *>$ 的子群；若令 $K = Ker(f)$ ，则 $\forall a \in G, aK = Ka$

同构

设 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的一个同态，若 $f$ 是 $A$ 到 $B$ 的双射（即一一映射），则称 $f$ 是 $<A, *>$ 到 $<B, \triangle>$ 的同构映射，并称 $<A, *>$ 与 $<B, \triangle>$ 同构

记作 $A \cong B$

自同构

设 $<A, *>$ 是一个代数系统，若 $g$ 是 $<A, *>$ 到 $<A, *>$ 的一个同构，则称 $g$ 为自同构

同构关系的性质

同构关系是等价关系

证明：

自反性：

$\forall <A, *> \in G$ ，作恒等映射 $f: A \rightarrow A$ ， $f(a) = a， a \in A$ ，

则 $f$ 是双射，并且 $\forall a, b \in A$ 有：

$f(a * b) = a * b = f(a) * f(b)$

所以， $<A, *> \cong <A, *>$

对称性：

设代数系统 $<A, *> \cong <B, \triangle>$ ，

则存在双射 $f: A \rightarrow B$ ，并且 $\forall a_1, a_2 \in A$ ，有：

$f(a_1 * a_2) = f(a_1) \triangle f(a_2)$

所以， $f^{-1}: B \rightarrow A$ 也是双射， $\forall b_1, b_2 \in B$ ， $\exist a_1, a_2 \in A$ ，使得：

$f^{-1}(b_1) = a_1$ ， $f^{-1}(b_2) = a_2$ ，即 $f(a_1) = b_1$ ， $f(a_2) = b_2$ ，故有：

$f^{-1}(b_1 \triangle b_2) = f^{-1}(f(a_1) \triangle f(a_2)) = f^{-1}(f(a_1 * a_2))$

因此， $<B, \triangle> \cong <A, *>$

传递性

设 $<A, *> \cong <B, \triangle>, <B, \triangle> \cong <C, \oplus>$

则存在双射 $f: A \rightarrow B$ 和 $g: B \rightarrow C$ ，故 $g \circ f$ 也为双射

$\forall a, b \in A$ 有：

$\begin{aligned} g \circ f(a * b) &= g(f(a * b)) \\\\ &= g(f(a) \triangle f(b)) \\\\ &= g(f(a)) \oplus g(f(b)) \\\\ &= g \circ f(a) \oplus g \circ f(b) \end{aligned}$
所以， $<A, *> \cong <C, \oplus>$

因此，代数系统间的同构关系是等价关系

同余

同余关系

设 $<A, *>$ 是一个代数系统， $R$ 是 $A$ 上的等价关系，若 $\forall <a, b> \in R, <c, d> \in R$ ，有：

$<a * c, b * d> \in R$

则称 $R$ 是 $A$ 上关于运算 $*$ 的同余关系

同余类

同余关系 $R$ 将非空集合 $A$ 划分称的等价类称为同余类

同余与同态关系

设 $<A, *>$ 是一个代数系统， $R$ 是 $A$ 上的同余关系. $B = \{[a]|a \in A\}$ 是由 $R$ 诱导的一个划分，则必存在同态映射 $f$ ，使 $<B, \triangle>$ 是 $<A, *>$ 的同态象

推论：设 $f$ 是群 $<A, *>$ 到群 $<B, \triangle>$ 的同态映射， $e'$ 为 $B$ 的幺元， $H = Ker(f)$ ，定义 $A$ 上的二元关系 $R$ ：

$<a, b> \in R \Leftrightarrow f(a) = f(b)$

$\forall x_1, x_2, y_1, y_2 \in G$ ，若 $x_1 H = y_1 H$ ，则

$(x_1 * x_2)H = (y_1 * y_2)H$

环与域

$\{环\} \subseteq \{整环\} \subseteq \{域\}$

环

设 $<A, \triangle， *>$ 是代数系统，若
1. $<A, \triangle>$ 是阿贝尔群
  - 封闭、可结合、幺元、逆元、交换律
1. $<A, *>$ 是半群
  - 封闭、可结合
1. 乘法 $*$ 对加法 $\triangle$ 可分配，即 $\forall a, b, c \in A$ 有
  
  $a*(b \triangle c) = a * b \triangle a * c$
  
  $(b \triangle c) = b * a \triangle c * a$
  
  则称 $<A, \triangle, *>$ 是一个环
称第一个运算 $\triangle$ 为加法，并记为 $+$
称第二个运算 $*$ 为乘法，并记为 $\cdot$
在环中
- 加法幺元记为 $\theta$
- 加法逆元 $a^{-1}$ 记为 $-a$
- $a + (-b)$ 记为 $a - b$

环的性质

设 $<A, +, \cdot>$ 是环， $\forall a, b, c \in A$

环的加法幺元必为乘法零元，即 $\theta \cdot a = a \cdot \theta = \theta$

$(-a) \cdot b = a \cdot (-b) = -(a \cdot b)$

$(-a) \cdot (-b) = a \cdot b$

$a \cdot (b - c) = a \cdot b - a \cdot c$

$(b - c) \cdot a = (b + (-c)) \cdot a = b \cdot a + (-c) \cdot a$

零因子

设 $<A, +, \cdot>$ 是环，若 $\exist a, b \in A, a \neq \theta, b \neq \theta$ ，使 $a \cdot b = \theta$ ，则称 $a, b$ 为零因子， $<A, +, \cdot>$ 是零因子环

无零因子

$\forall a, b \in A, a \neq \theta, b \neq \theta$ ，必有 $a \cdot b = \theta$
无零因子的环称为无零因子环

性质

环 $<A, +, \cdot>$ 无零因子，当且仅当 $<A, \cdot>$ 满足消去律
- 即 $\forall a, b, c \in A$ ，若 $a \cdot b = a \cdot c$ ， $a \neq \theta$ ，必有 $b = c$

整环

交换环

给定环 $<A, +, \cdot>$ ，若 $<A, \cdot>$ 可交换，则称 $<A, +, \cdot>$ 为交换环

含幺环

给定环 $<A, +, \cdot>$ ，若 $<A, \cdot>$ 含幺元，则称 $<A, +, \cdot>$ 为含幺环

整环

给定环 $<A, +, \cdot>$ ，若 $<A, \cdot>$ 可交换、含幺元、无零因子（或满足消去律），则称 $<A, +, \cdot>$ 为整环
整环 = 环 + 乘法幺元 + 乘法可交换 + 无零因子（或乘法消去律）
设 $<A, +, \cdot>$ 是代数系统，若
1. $<A, +>$ 是阿贝尔群
1. $<A, \cdot>$ 是可交换独异点，且无零因子（或满足消去律）
1. 运算 $\cdot$ 对 $+$ 可分配
则称 $<A, +, \cdot>$ 是一个整环

域

设 $<A, +, \cdot>$ 是代数系统，若
1. $<A, +>$ 是阿贝尔群
1. $<A - \{\theta\}, \cdot>$ 是阿贝尔群
1. 运算 $\cdot$ 对 $+$ 可分配
则称 $<A, +, \cdot>$ 是域

域与整环

整环	域
$<A, \cdot>$ 是可交换独异点，且无零因子	$<A - \{\theta\}, \cdot>$ 是阿贝尔群

域 = 整环 + 除了零元外，每个元素都有逆元
域无零因子
域一定是整环
有限整环一定是域

两个运算代数系统间的同态

同态映射

设和是两个代数系统，若存在映射满足：，有
1. $f(a + b) = f(a) \oplus f(b)$
2. $f(a \cdot b) = f(a) \otimes f(b)$
  则称 $f$ 是 $<A, +, \cdot>$ 到 $<B, \oplus, \otimes>$ 的一个同态映射，并称 $<f(A), \oplus, \otimes>$ 是 $<A, +, \cdot>$ 的同态象

同态映射的性质

任一环的同态象是一个环

格

格的定义

若偏序集 $<A, \preccurlyeq>$ 中任意两个元素 $a, b$ 都有最小上界 $（LUB\{a, b\}）$ 和最大下界 $（GLB\{a, b\}）$ ，则称 $<A, \preccurlyeq>$ 是格
通常记： $a \lor b = LUB\{a, b\}$ , $a \land b = GLB\{a, b\}$
由于最小上界、最大下界若存在则唯一，所以 $\lor$ 、 $\land$ 是二元运算，分别称为并运算和交运算
称 $<A, \lor, \land>$ 为由格 $<A, \preccurlyeq>$ 所诱导的代数系统

子格

设 $<A, \preccurlyeq>$ 是格， $<A, \lor, \land>$ 是由 $<A, \preccurlyeq>$ 所诱导的代数系统，设 $B \subseteq A$ 且 $B \neq \varnothing$ ，若运算 $\lor$ 和 $\land$ 在 $B$ 中封闭，则称 $<B, \preccurlyeq>$ 是 $<A, \preccurlyeq>$ 的子格

格的对偶

设是偏序集，用表示偏序关系的逆关系，则
- $<A, \succcurlyeq>$ 也是偏序集
- $<A, \preccurlyeq>$ 和 $<A, \succcurlyeq>$ 的哈斯图是互为颠倒的
- 称 $<A, \preccurlyeq>$ 与 $<A, \succcurlyeq>$ 为彼此对偶的偏序集
- 若是格，则也是格，反之亦成立，称这两个格互为对偶
  - $\forall a, b \in A$ ， $<A, \preccurlyeq>$ 的 $LUB\{a, b\}$ 对应于 $<A, \succcurlyeq>$ 的 $GLB\{a, b\}$
  - $\forall a, b \in A$ ， $<A, \preccurlyeq>$ 的 $GLB\{a, b\}$ 对应于 $<A, \succcurlyeq>$ 的 $LUB\{a, b\}$

格的对偶原理

设 $P$ 是对任意格都为真的命题，将 $P$ 中的 $\preccurlyeq$ , $\lor$ , $\land$ 分别换成, $\succcurlyeq$ , $\land$ , $\lor$ 得命题 $P'$ ，则 $P'$ 对任意格也是真的命题

格的基本性质

自反性

$a \preccurlyeq a, a \succcurlyeq a$
反对称性

$(a \preccurlyeq b) \land (b \preccurlyeq a) \Rightarrow a = b$

$(a \succcurlyeq b)\land(b \succcurlyeq a) \Rightarrow a = b$
传递性

$(a \preccurlyeq b) \land (b \preccurlyeq c) \Rightarrow a \preccurlyeq c$

$(a \succcurlyeq b) \land (b \succcurlyeq c) \Rightarrow ac$
确界描述一

$a \preccurlyeq a \lor b, b \preccurlyeq a \lor b$

$a \land b \preccurlyeq a, a \land b \preccurlyeq b$
确界描述二

$(a \preccurlyeq c) \land (b \preccurlyeq c) \Rightarrow a \lor b \preccurlyeq c$

$(c \preccurlyeq a) \land (c \preccurlyeq b) \Rightarrow c \preccurlyeq a \land b$
盖住的等价

$a \preccurlyeq b \Leftrightarrow a \land b = a \Leftrightarrow a \lor b = b$
交换律

$a \lor b = b \lor a, a \land b = b \land a$
结合律

$(a \lor b) \lor c = a \lor (b \lor c)$

$(a \land b) \land c = a \land (b \land c)$
幂等律

$a \lor a = a, a \land a = a$
吸收律

$a \lor (a \land b) = a$

$a \land (a \lor b) = a$
若 $a \preccurlyeq b, c \preccurlyeq d$ ，则

$a \lor c \preccurlyeq b \lor d$

$a \land c \preccurlyeq b \land d$
保序性

若 $b \preccurlyeq c$ ，则

$a \lor b \preccurlyeq a \lor c$

$a \land b \preccurlyeq a \land c$
分配不等式

$a \lor (b \land c) \preccurlyeq (a \lor b) \land (a \lor c)$

$(a \land b) \lor (a \land c) \preccurlyeq a \land (b \lor c)$
模不等式

$a \preccurlyeq c \Leftrightarrow a \lor (b \land c) \preccurlyeq (a \lor b) \land c$
推论：

$(a \land b) \lor (a \land c) \preccurlyeq a \land (b \lor (a \land c))$

$a \lor (b \land (a \lor c)) \preccurlyeq (a \lor b) \land (a \lor c)$
引理：若 $<A, \lor, \land>$ 是一个代数系统，其中 $\lor$ ， $\land$ 都是二元运算且满足吸收律，则 $\lor$ ， $\land$ 必满足幂等律
定理一：设 $<A, \lor, \land>$ 是一个代数系统，其中 $\lor$ ， $\land$ 都是二元运算且满足交换律，结合律和吸收律，则 $A$ 上存在偏序关系 $\preccurlyeq$ ，使 $<A, \preccurlyeq>$ 是一个格

格同态与格同构

格同态

设 $<A_1, \preccurlyeq_1>, <A_2, \preccurlyeq_2>$ 是格，它们所诱导的代数系统分别是 $<A_1, \lor_1, \land_1>, <A_2, \lor_2, \land_2>$ ，若存在映射 $f: A_1 \rightarrow A_2$ ，对 $\forall a, b \in A_1$ ，有：

$f(a \lor_1 b) = f(a) \lor_2 f(b)$

$f(a \land_1 b) = f(a) \land_2 f(b)$

则称 $f$ 是从 $<A_1, \lor_1, \land_1>$ 到 $<A_2, \lor_2, \land_2>$ 的格同态

称 $<f(A_1), \preccurlyeq_2>$ 是 $<A, \preccurlyeq_1>$ 的格同态象

格同构

若 $f$ 是双射，则称 $f$ 是从 $<A_1, \lor_1, \land_1>$ 到 $<A_2, \lor_2, \land_2>$ 的格同构
也称格 $<A, \preccurlyeq_1>$ 与 $<A, \preccurlyeq_2>$ 同构

格同构的性质

设 $f$ 是格 $<A, \preccurlyeq_1>$ 到 $<A, \preccurlyeq_2>$ 的格同态， $\forall a, b \in A_1$ ，若 $a \preccurlyeq_1 b$ ，必有 $f(a) \preccurlyeq_2 f(b)$
- 逆命题不成立
设两个格 $<A, \preccurlyeq_1>$ 和 $<A, \preccurlyeq_2>$ ， $f$ 是 $A_1$ 到 $A_2$ 的双射，则 $f$ 是格 $<A, \preccurlyeq_1>$ 到 $<A, \preccurlyeq_2>$ 的格同构，当且仅当

$\forall a, b \in A_1, a \preccurlyeq_1 b \Leftrightarrow f(a) \preccurlyeq_2 f(b)$

分配格

设 $<A, \lor, \land>$ 是由格 $<A, \preccurlyeq>$ 所诱导的代数系统，若 $\forall x, y, z \in A$ ，满足

$x \land (y \lor z) = (x \land y) \lor (x \land z)$

$x \lor (y \land z) = (x \lor y) \land (x \lor z)$

则称 $<A, \preccurlyeq>$ 是分配格

分配格的性质

若在一个格中交运算对并运算可分配，则并运算对交运算也一定可分配，反之亦然

设 $<A, \preccurlyeq>$ 是分配格，则 $\forall a, b, c \in A$ ，有

$a \land c = b \land c 且 a \lor c = b \lor c \Rightarrow a = b$

分配格的判定

定义

$x \land (y \lor z) = (x \land y) \lor (x \land z)$

$x \lor (y \land z) = (x \lor y) \land (x \lor z)$

其一成立

格 $<A, \preccurlyeq>$ 是分配格当且仅当 $A$ 中不含与钻石格或五角格同构的子格

分配格的子格必是分配格

每个链是分配格

模格

模格的定义

设 $<A, \lor, \land>$ 是由格 $<A, \preccurlyeq>$ 所诱导的代数系统，若 $\forall a, b, c \in A$ ，当 $b \preccurlyeq a$ 时，满足

$a \land (b \lor c) = b \lor (a \land c)$

则称 $<A, \preccurlyeq>$ 是模格

分配格与模格的关系

分配格必是模格
- 模格不一定是分配格
  - 例：钻石格是模格但不是分配格

有界格

全下界

设是格，若存在，对任意有，则称为的全下界，记为0
- 若存在必唯一

全上界

设是格，若存在，对任意有，则称为的全上界，记为1
- 若存在必唯一

有界格

具有全下界和全上界的格称为有界格

有界格的性质

设 $<A, \preccurlyeq>$ 为有界格，则 $\forall a \in A$ 有

$a \lor 1 = 1, a \land 1 = a$

$a \lor 0 = a, a \land 0 = 0$

在有界分配格中，若某元素有补元，则必唯一

补元

设是有界格，，若，使

则称是的补元
- $a$ 和 $b$ 互为补元

有补格

在一个有界格中，如果每个元素至少有一个补元，则称此格为有补格

布尔代数

布尔格

若一个格既是有补格，又是分配格，则此格称为有补分配格，又称布尔格

布尔格中任一元素 $a$ 的补元存在且唯一，记为 $\overline{a}$

原子

设格 $<A, \preccurlyeq>$ 具有全下界0，若有元素 $a$ 盖住0，则称元素 $a$ 为原子

布尔代数

布尔格 $<A, \preccurlyeq>$ 可以诱导一个代数系统 $<A, \lor, \land, \overline{\over}>$ ，则此代数系统为布尔代数

布尔代数的性质

设是布尔代数中任一两个元素，则
- $\overline{(\overline{a})} = a$
- $\overline{(a \lor b)} = \overline{a} \land \overline{b}$
- $\overline{(a \land b)} = \overline{a} \lor \overline{b}$

设 $<A, \preccurlyeq>$ 是一个具有全下界0的有限格，若 $b \neq 0$ ，则至少存在一个原子 $a$ ，使 $a \preccurlyeq b$

布尔代数的同构

设和是两个布尔代数，则存在双射满足：，有：
1. $f(a \lor b) = f(a) \lor f(b)$
2. $f(a \land b) = f(a) \land f(b)$
3. $f(\overline{a}) = \overline{f(a)}$
  
  则称 $<A, \lor, \land, \overline{\over}>$ 和 $<B, \lor, \land, \overline{\over}>$ 同构

有限布尔代数

具有有限个元素的布尔代数

有限布尔代数的结论

对任一正整数 $n$ ，必存在含有 $2^n$ 个元素的布尔代数

任一有限布尔代数的元素的个数必为 $2^n$ ， $n$ 为正整数

元素个数相同的布尔代数是同构的

有限布尔代数的引理

在布尔格中， $b \land \overline{c} = 0$ 当且仅当 $b \preccurlyeq c$

设 $<A, \lor, \land, \overline{\over}>$ 是一个有限布尔代数，若 $b \in A$ ，且 $b \neq 0$ ，又设 $a_1, a_2, \cdots, a_k$ 是 $A$ 中满足 $a_j \preccurlyeq b(j = 1, 2, \cdots, k)$ 的所有原子，则

$b = a_1 \lor a_2 \lor a_3 \cdots \lor a_k$

设 $<A, \lor, \land, \overline{\over}>$ 是一个有限布尔代数，若 $b \in A$ ，且 $b \neq 0$ ，又设 $a_1, a_2, \cdots, a_k$ 是 $A$ 中满足 $a_j \preccurlyeq b(j = 1, 2, \cdots, k)$ 的所有原子，则

$b = a_1 \land a_2 \land a_3 \cdots \land a_k$

是将 $b$ 表示为原子的的并的唯一形式

设 $<A, \preccurlyeq>$ 是布尔格， $a$ 为任意一个原子， $b \neq 0$ ，则

$a \preccurlyeq b$ 和 $a \preccurlyeq \overline{b}$ 两式中，有且仅有一个成立

布尔表达式

设 $<A, \lor, \land, \overline{\over}>$ 是布尔代数
1. $A$ 中任何元素(即布尔常元)是布尔表达式
1. 任何布尔变元是布尔表达式
1. 若 $e_1, e_2$ 是布尔表达式，则 $\overline{e_1}, (e_1 \lor e_2), (e_1 \land e_2)$ 都是布尔表达式
1. 尤其仅有通过有限次地运用规则(2),(3)所构造的符号串是布尔表达式

布尔常元

$A$ 中的元素

布尔变元

以 $A$ 为取值范围的变元

n元布尔表达式

一个含 $n$ 格相异变元的布尔表达式，称为 $n$ 元布尔表达式，记作

$E(x_1, x_2, \cdots, x_n)$

其中 $x_1, x_2, \cdots, x_n$ 为布尔变元

布尔表达式的值

设 $<A, \lor, \land, \overline{\over}>$ 是布尔代数， $n$ 元布尔表达式 $E(x_1, x_2, \cdots, x_n)$ 的值是指：

将 $A$ 中的布尔常元作为变元 $x_i$ 的值来代替表达式中相应的变元(即对变元赋值)，从而计算得出表达式的值

布尔表达式的等价

设 $E_1(x_1, x_2, \cdots, x_n)$ 和 $E_2(x_1, x_2, \cdots, x_n)$ 是布尔代数 $<A, \lor, \land, \overline{\over}>$ 上的两个 $n$ 元布尔表达式，若对 $n$ 格变元的任意赋值 $x_i = a_i, a_i \in A, i = 1, 2, \cdots, n$ 均有

$E_1(a_1, a_2, \cdots, a_n) = E_2(a_1, a_2, \cdots, a_n)$

则称布尔表达式 $E_1, E_2$ 是等价的，记作：

$E_1(x_1, x_2, \cdots, x_n) = E_2(x_1, x_2, \cdots, x_n)$