6. 代数

6.1 代数结构

代数系统: 非空集合 $A$, 定义在 $A$ 上的运算封闭 $f$, 代数常元. $<A, f, k>$

运算

封闭性: $f$ 是 $A^n \rightarrow B$ 的映射, 若 $B \subset A$, 则运算 $f$ 在 $A$ 上封闭 (结果在原来的集合中)

代数运算性质:

性质	定义	运算表结构
交换律	略	关于主对角线对称
结合律	略
分配律	$a \times (b + c) = (a \times b) + (a \times c)$, $\times$ 对 $+$ 可左分配
吸收律	$x * (x \circ y) = x$, $*$ 对 $\circ$ 左可吸收
等幂律	$x * x = x$	主对角线元素与行列表头相同
消去律	$\forall a \in A, a * x = a * y \Rightarrow x = y$, 运算 $*$ 满足可消去	任意行, 列没有相同元素

代数常元

幺元

• 左幺元: $\exists e_l \in A, \forall x \in A, e_l * x = x$, $e_l$ 为 $A$ 中关于 $*$ 的左幺元
• 右幺元: $x * e_l = x$.
• 幺元: 左且右

(之后代数常元都有左右之分, 不全写了)

定理:

存在关于 $*$ 的左右幺元 $e_l, e_r$, 则 $e_l = e_r = e$ 且唯一.

证明:

$e_l * e_r = e_r$ (左幺元)

$e_l * e_r = e_l$ (右幺元)

$e_l = e_r = e$

假设有另一幺元 $e’ \ne e$, 则 $e = e * e’ = e’$ 矛盾.

例如普通乘法里的 $1$.

零元

$\exists \theta \in A, \forall x \in A, \theta * x = x * \theta = \theta$

定理:

存在关于 $*$ 的左右零元 $\theta_l, \theta_r$, 则 $\theta_l = \theta_r = \theta$ 且唯一.

证明类似幺元的.

例如普通乘法里的 $0$.

逆元

$\exists x, y \in A, x * y = e$, $x$ 为 $y$ 的左逆元, $y$ 为 $x$ 的右逆元

定理:

若 $*$ 可结合, $l * x = e, x * r = e$, 则 $l = r = x^{-1}$, 且唯一

证明:

$l * x = x * r = e$

$l * e = l * (x * r) = (l * x) * r = e * r = r = x^{-1}$

假设另一逆元 $a \ne x^{-1}$, 则 $a = a * e = a * (x * x^{-1}) = (a * x) * x^{-1} = e * x^{-1} = x^{-1}$ 矛盾.

运算表中的代数常元

代数常元	运算表结构
零元	行列都是该元素
幺元	行列与行列表头相同

子代数

$<A, *, k>$

1. $A’ \subset A$
2. $k \in A'$
3. $*$ 在 $A’$ 上封闭

则 $<A’, *, k>$ 为 $<A, *, k>$ 的子代数

证明按定义三点证

6.2 同态

$A = <S, \Delta, *, k>$, $A’ = <S’, \Delta’, *’, k’>$

1. $\exists f$, $S \rightarrow^f S'$
2. $\forall x \in S$, $f(\Delta x) = \Delta’ f(x)$, $\forall x, y \in S, f(x * y) = f(x) *’ f(y)$
3. $f(k) = k'$

则 $A \sim A'$

证明按定义三点证

• 满同态: $f$ 是满射
• 单一同态: $f$ 是单射
• 同构: $f$ 是双射, $A \cong A'$

同态象: $A’’ = <f(S), \Delta’, *’, k>$, 且可证 $A’’ \cong A$ (证明略)

同态象 (同构) 的性质: 运算规律和代数常元(通过 $f$) 保留.

6.3 同余

可保持: $A = <S, *, \Delta>$ 上的一个等价关系 $\sim$, 若:

1. $\forall a, b \in A, a \sim b$, $\Delta a \sim \Delta b$, 则 $\sim$ 在一元运算 $\Delta$ 下是可保持的
2. $\forall a, b, c, d \in A, a \sim b, c \sim d$, $\Delta ac \sim \Delta bd$, 则 $\sim$ 在二元运算 $*$ 下是可保持的

同余: 等价关系 $\sim$ 在所有运算下可保持

定理:

设 $g$ 是从代数系统 $A=<S, *, \Delta, k>$ 到 $A’ = <S’, *’, \Delta’, k’>$ 的一个同态映射, 如果在 $A$ 上定义等价关系 $\mathbb R$ 为 $<a, b> \in \mathbb{R}$ iff. $g(a)=g(b)$ 那么, $R$ 是 $A$ 上的一个同余关系.

证明按定义:

$\forall a, b \in A$ st. $a\mathbb{R}b$, $g(a) = g(b)$

$\therefore g(\Delta a) = \Delta’ g(a) = \Delta’ g(b) = g(\Delta b) \Rightarrow \Delta a \mathbb{R} \Delta b$

$\forall a, b, c, d, \in A$ st. $a\mathbb{R}b, c\mathbb{R}d$, $g(a) = g(b), g(c) = g(d)$

$\therefore g(a * c) = g(a) *’ g(c) = g(b) *’ g(d) = g(b * d) \Rightarrow a * c \mathbb{R} b * d$

商代数:

$\sim$ 是 $A = <S, *, \Delta, k>$ 上的同余关系, $A$ 关于 $\sim$ 的商代数 $A/\sim = <S/\sim, *’, \Delta’, [k]>$, 其中 $\Delta’ [a] = [\Delta a], [a] *’ [b] = [a * b]$

$[a]$ 是 $a$ 的等价类 (集合), $S/\sim$ 是所有等价类的集合

相当于是, 商代数的元素以及运算都以 $\sim$ 的等价类为单位

6.4 半群

半群: 代数系统 $A = <S, *>$, $*$ 是二元运算, $*$ 满足结合律, 则 $A$ 是半群.

独异点: 含有幺元的半群

循环独异点: $\exists g \in S$, $\forall a \in S$, $\exists k \in N, a = g^k$ ($a^0 = e$)

定理:

半群 $<S, *>$, 若 $S$ 是有限集合, 则 $\exists a \in S$, $a * a = a$

证明:

设 $|S| = n$, 任取 $b \in S$, 在 $b, b^2, \dots b^n, b^{n+1}$ 中, 一定存在两个相同的值 (运算封闭性 + 抽屉原理), 不妨设为 $b^{i} = b^{i+p}, p \ge 1$

左右同时 $*$ 若干个 $b$, 使得 $b^{kp} = b^{kp + p}$ 成立

这个式子说明, 在 $b^{kp}$ 上 $*$ $p$ 个 $b$, 结果不变, 则有 $b^{kp} = b^{2kp}$

即 $b^{kp} = b^{kp} * b^{kp}$, 即 $\exists a = b^{kp}, a * a = a$

6.5 群

每个元素都有逆元的独异点

性质:

• 没有零元
• 每个元素的逆元唯一
• 唯一的 $x$, $a * x = b$
• 满足消去律
• 有且仅有一个等幂元且为 $e$
• 运算表行列都没有相同元素 (都是元素的置换)

元素的阶: 满足 $a^n = e$ 最小正整数 $n$, $n$ 为 $a$ 的阶 (周期), 否则阶无限

定理:

群 $<G, *>$ 的任意元素 $a$ 与 $a^{-1}$ 同阶

证明:

$\forall a \in G$, $a * a^{-1} = e$. $(a * a^{-1})^n = e = a^n * a^{-n} = e * a^{-n} = e$

假设存在 $0 < n’ < n$, $a^{-n’} = e$, 则 $(a * a^{-1})^{n’} = e = a^{n’} * a^{-n’} = a^{n’} = e$, 与 $n$ 是 $a$ 的阶矛盾

定理:

群 $<G, *>$ 的元素 $a$ 的有限阶为 $n$, $a^k = e$, 当且仅当 $n \mid k$

证明:

必要性:

设 $k = mn + t, m, t \in \mathbb{Z}, 0 \le t < n$

$a^t = a^{k-mn} = a^k * a^{-mn} = e * e = e \Rightarrow t = 0$

$\therefore k = mn$, 即 $n \mid k$

充分性直接定义.

定理:

有限群 $<G, *>$ 任何元素的阶最多是 $G$

证明:

$\forall a \in G$, $a^k \in G, 1 \le k \le |G| + 1$

由抽屉原理得, 必有 $a^i = a^j, 1 \le i < j \le |G| + 1}$, 则 $a^{j-i} = e$

有 $j - i \le |G|$, 即 $a^n = e, n \le |G|$

子群判定定理

子群: $<S, *, e>$ 是 $<G, *, e>$ 的子群, 满足:

1. 子代数 ($S \subseteq G$, 运算封闭, $e \in S$)
2. 是群 ($*$ 可交换, 有幺元, $\forall a \in S, a^{-1} \in S$)

平凡子群 $<G, *>, <{e}, *>$

父群为 $<G, *>$, 要判定的代数系统为 $<S, *>$, 下面不再重复说明

$S \subset G, S \ne \emptyset$, $S$ 是有限集, 封闭

证明:

和上面的抽屉原理类似, 先得到 $\forall a \in S$, $a^i = a^j, 1 \le i < j \le n+1$

然后有 $a^{j-i} = e \in S$, $a^{-1} = a^{j-i-1}$, $j - i - 1 \ge 0$, 故 $a^{-1} \in S$

$S \subset G, S \ne \emptyset$, $\forall a, b \in S$, $a * b^{-1} \in S$

证明:

$\forall a \in S, a * a^{-1} = e \in S$, 存在幺元

$\forall a \in S, e * a^{-1} \in S \Rightarrow a^{-1} \in S$, 每个元素都有逆元

$\forall a, b \in S, a * (b^{-1})^{-1} \in S \Rightarrow a * b \in S$, 封闭

循环群

循环群: $\exists g \in G$, $\forall a \in G$, $\exists k \in I, a = g^k$ ($a^0 = e$)

生成元可能不止一个, 生成元的指数可以是负数, 而循环独异点是自然数.

阿贝尔群: 可交换

定理:

循环群是阿贝尔群

证明:

$\forall a, b \in G, a = g^i, b = g^j$, $a * b = g^{i+j} = g^{j+i} = b * a$

定理:

有限循环群 $<G, *>$ 的生成元为 $g$, $|G| = n$, 则

1. $g$ 的阶为 $n$
2. $G = {x | x = g^k, 1 \le k \le n}$

证明:

假设 $m < n, g^m = e$, $\forall a \in G$, $a = g^k = g^{qm + r} = g^r, q, r \in N, 0 \le r < m$

$G = {x | x = g^k, 1 \le k \le m}$, $|G| \le m$ 与 $|G| = n$ 矛盾

假设 $g^i = g^j, 1 \le i < j \le n$, $g^{j-i} = e$, 与 $g$ 的阶为 $n$ 矛盾

定理:

循环群的子群是循环群

证明:

假设 $m$ 是最小的正整数, 满足 $g^m \in S$, 任取 $g^l \in S$, 设 $l = tm + r$, 则 $g^r = g^{l - tm} = g^l * (g^m)^{-t} \in S$, 因为 $0 \le r < m$, $m$ 是满足 $g^m \in S$ 的最小正整数, 所以 $r = 0$. 所以 $g^l = g^tm$, 即子群是生成元为 $g^m$ 的循环群

定理:

无限循环群与 $<I, +>$ 同构, 有限循环群与 $<N_k, +_k>$ 同构

证明按同构定义即可, 证同态和 $f$ 双射 (满射且单射)

群同态

定理:

群的同态象是群

证明:

按定义证明即可, 可以用同态象 (同构) 的性质 怀疑 PPT 在乱证

同态核: 设 $h$ 是群 $<G, *>$ 到 $<H, *’>$ 的同态映射, $e_H$ 是 $<H, *’>$ 的幺元, 同态核 $Ker(h) = {x | h(x) = e_H, x \in G}$

定理:

$<Ker(h), *>$ 是 $<G, *>$ 的子群

证明:

显然 $Ker(h) \subseteq G$

$\forall a, b \in Ker(h)$, $h(a) *’ h(b) = e_H * e_H = e_H = h(a * b)$, 即 $a * b \in Ker(h)$

$h(e) = e_H, e \in Ker(h)$

可交换略

$\forall a \in Ker(h), h(a^{-1}) *’ h(a) = h(a * a^{-1}) = e_H = h(a^{-1}) * e_H \Rightarrow h(a^{-1}) = e_H$, 所以 $a^{-1} \in Ker(h)$

陪集

群 $<G, *>$ 的子群 $<H, *>$, 对于每个 $a \in G$, 定义由 $a$ 确定的 $H$ 在 $G$ 中的左陪集 $aH = {a * b | b \in H}$, 类似还有右陪集

定理:

$aH = bH$ 或者 $aH \cup bH = \emptyset$ 只有一个成立

证明:

假设 $aH \cup bH \ne \emptyset$, $\exists h1, h2$ st. $a * h1 = b * h2$, 即 $a = b * h2 * h1^{-1}$

$\forall x = a * h3 \in aH$, $x = (b * h2 * h1^{-1}) * h3 = b * (h2 * h1^{-1} * h3)$, $\because h2 * h1^{-1} * h3 \in H$, $\therefore x \in bH$

所以 $aH \subseteq bH$. 同理可证 $bH \subseteq aH$, 故 $aH = bH$

定理:

$\forall a \in G, |aH| = |H|$

证明非常平凡, 略

定理:

$a, b \in G$, $b \in aH$ iff. $a^{-1} * b \in H$

证明:

$b \in aH \Longleftrightarrow \exists x \in H, b = a * x \Longleftrightarrow a^{-1} * b \in H$

拉格朗日定理

$<H, *>$ 是 $<G, *>$ 的子群, 有

1. $R = \{<a, b> | a, b \in G, a^{-1} * b \in H\}$ 是 $G$ 上的等价关系, 且有 $[a]$ = $aH$
2. 若 $G$ 有限, $|G| = n, |H| = m$, 则 $m | n$

证明等价关系 (自反 ($<a, a> \in R$), 对称 ($<a, b>, <b, a> \in R$), 传递 $<a, b> \in R, <b, c> \in R, <a, c> \in R$):

1. 自反: $\forall a \in G, a^{-1} * a = e \in H \Longrightarrow <a, a> \in R$
2. 对称: $\forall <a, b> \in R, a^{-1} * b \in H$, $(a^{-1} * b)^{-1} \in H \Longrightarrow b^{-1} * a \in H$ (取逆之后会交换, 不放心手动推一遍)
3. 传递: $\forall <a, b>, <b, c> \in R, a^{-1} * b, b^{-1} * c \in H, (a^{-1} * b) * (b^{-1} * c) = a^{-1} * c \in H \Longrightarrow <a, c> \in R$

证明 $m | n$:

等价类: $|aH| = |H| = m$, $|G| = n$, 等价类诱导划分, 所有等价类元素个数都为 m, 所以 $m | n$

推论:

1. $|G|$ 为质数, 没有非平凡子群 (由拉格朗日 2 得)
2. $G$ 有限, $\forall a \in G$, $a$ 的阶数是 $n$ 的因子

证明: 假设 $a$ 的阶为 $r$ 构造子群 $H = <\{a^k | 0 \le k < r\}, *>$, 则 $r | n$

3. $|G|$ 为质数, $G$ 是循环群, 除了 $e$ 都可以是生成元

证明: $\forall a \in G, a \ne e$ 构造子群 $H = <\{a^k | 0 \le k < r\}, *>$, 则 $r | n$, 由于 $n$ 是质数且 $r \ne 0$, 所以 $r = n$, 所以 $H$ 是循环群, $G = H$ 是循环群

6.6 环和域

环

环 $<A, +, \cdot>$ 满足:

1. $<A, +>$ 是阿贝尔群 (可结合可交换, 每个元素都有逆元)
2. $<A, \cdot>$ 是半群 (可结合)
3. $\cdot$ 对 $+$ 可分配

性质:

1. $+$ 的幺元 ($\theta$) 是 $\cdot$ 的零元

证明:

$\forall a \in A$, $a \cdot \theta = a \cdot (\theta + \theta) = (a \cdot \theta) + (a \cdot \theta)$, 群 $<A, +>$, 消去律, 得 $\theta = a \cdot \theta$. 同理可证 $a \cdot \theta = \theta$

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

证明:

$\begin{aligned} (-a) \cdot b &= (-a) \cdot b + \theta \newline &= (-a) \cdot b + (a \cdot b - (a \cdot b)) \newline &= ((-a) \cdot b + a \cdot b) - (a \cdot b) \newline &= ((-a + a) \cdot b) - (a \cdot b) \newline &= - (a \cdot b) \end{aligned}$

同理可得 $a \cdot (-b) = -(a \cdot b)$

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

证明:

$\begin{aligned} (-a) \cdot (-b) &= (-a) \cdot (-b) + \theta \newline &= (-a) \cdot (-b) + ((-a) \cdot b - ((-a) \cdot b)) \newline &= ((-a) \cdot (-b) + (-a) \cdot b) - ((-a) \cdot b) \newline &= ((-a) \cdot (-b + b)) - ((-a) \cdot b) \newline &= - (- (a \cdot b)) \newline &= a \cdot b \end{aligned}$

4. $\cdot$ 对 $-$ 可分配

证明很简单, 略

• 交换环: $\cdot$ 可交换
• 含幺环: $<A, \cdot>$ 有幺元
• 含零因子环 $\exists a, b \in A$, $a \ne \theta, b \ne \theta$, $a \cdot b = \theta$, $a, b$ 称为零因子
• 整环: $<A, \cdot>$ 含幺元, $\cdot$ 可交换, 无零因子 (如 $<I, +, \times>$, $<N_p, +_p, \times_p>$, $p$ 是质数)

定理:

无零因子 iff. 可约律 ($\forall a, b, c \in A, c \ne \theta, c \cdot a = c \cdot b \Rightarrow a = b$)

证明:

必要性:

$\forall a, b, c \in A, c \ne \theta$,

$\begin{aligned} &c \cdot a = c \cdot b \newline \Longleftrightarrow &(c \cdot a) - (c \cdot b) = (c \cdot b) - (c \cdot b) \newline \Longleftrightarrow &c \cdot (a - b) = \theta \end{aligned}$

无零因子, $(a-b) = \theta \Longleftrightarrow a = b$

充分性:

取 $\forall a, b \in A, a \ne \theta, a \cdot b = \theta$

$a \cdot b = a \cdot \theta$, 可约律, 则 $b = \theta$, 故无零因子

域

• 定义1: 整环 $<F, +, \cdot>$, 且 $|F| > 1, <F-\{\theta\}, \cdot>$ 是群
• 定义2:
  • $<F, +>$ 阿贝尔群
  • $<F - \{\theta\}, \cdot>$ 阿贝尔群
  • $\cdot$ 对 $+$ 可分配

性质:

• 域一定是整环
• 有限整环一定是域

7. 格

偏序集合 $<L, \preccurlyeq>$ 中任意两个元素都有最小上界和最大下界, 则 $<L, \preccurlyeq>$ 是格

• 保交运算 $a \wedge b$, 求 $a, b$ 的最大下界
• 保联运算 $a \vee b$, 求 $a, b$ 的最小上界

子格

$<S, \wedge, \vee>$ 是 $<L, \wedge, \vee>$ 的子格, iff. 是子代数, 并且 $\forall a, b \in S$, 在 $<L, \wedge, \vee>$ 中的运算结果 $a \wedge b, a \vee b$ 在 $S$ 中

代数格

$<L, \preccurlyeq>$ 是格, $<L, \wedge, \vee>$ 是格 $<L, \preccurlyeq>$ 诱导的代数系统, 简称代数格

性质:

1. $a \preccurlyeq a \vee b, b \preccurlyeq a \vee b$, $a \wedge b \preccurlyeq a, a \wedge b \preccurlyeq b$

证明略

2. $a \preccurlyeq b, c \preccurlyeq d$, 则 $a \vee c \preccurlyeq b \vee d$, $a \wedge c \preccurlyeq b \wedge d$

证明:

$a \preccurlyeq b \preccurlyeq b \vee d$, $c \preccurlyeq d \preccurlyeq b \vee d$, 说明 $a, c$ 的一个上界是 $b \vee d$, 故 $a \vee c \preccurlyeq b \vee d$. 同理可证 $a \wedge c \preccurlyeq b \wedge d$

它还能推得:

• $a \preccurlyeq b \Rightarrow a \wedge c \preccurlyeq b \wedge c, a \vee c \preccurlyeq b \vee c$
• $a \preccurlyeq b, a \preccurlyeq c \Rightarrow a \preccurlyeq b \wedge c, a \preccurlyeq b \vee c$
• $a \preccurlyeq c, b \preccurlyeq c \Rightarrow a \wedge b \preccurlyeq c, a \vee b \preccurlyeq c$

$\vee$ 和 $\wedge$ 满足:

• 交换律
• 结合律
• 等幂律 ($a \vee a = a$)
• 吸收律 ($a \wedge (a \vee b) = a$)
• 分配不等式 $a \vee (b \wedge c) \preccurlyeq (a \vee b) \wedge (a \vee c)$, $a \wedge (b \vee c) \succcurlyeq (a \wedge b) \vee (a \wedge c)$ (不会证, 记, $\vee$ 的更小)
• 模不等式 $a \preccurlyeq b \Rightarrow a \preccurlyeq a \vee (b \wedge c) \preccurlyeq (a \vee b) \wedge c \preccurlyeq c$ (不会证, 记不住) (有个叫模格的东西, 满足中间是等号, iff. 不存在五角格子格)

tnnd 怎么这么多, 不管了反正用集合的那套能乱搞 md, 两个不等式搞不了

定理:

$<A, \wedge, \vee>$ 运算都满足吸收律, 则都满足等幂律

证明: $\forall a, b, c \in A, c = a \wedge b$, 有

• $a \wedge (a \vee c) = a$
• $a \vee (a \wedge b) = a$

$a = a \wedge (a \vee c) = a \wedge (a \vee (a \wedge b)) = a \wedge a$

同理可证 $a \vee a = a$

定理:

$A, \wedge, \vee$ 运算满足交换律, 结合律, 吸收律, 则存在偏序关系 $\preccurlyeq$, 使 $<L, \preccurlyeq>$ 是格

证明:

先证明 $a \preccurlyeq b \Longleftrightarrow a = a \wedge b$ 是偏序

1. 自反性: $a = a \wedge a$ 成立 (吸收律推出等幂律), 则 $a \preccurlyeq a$ 成立
2. 反对称性: $a \preccurlyeq b, b \preccurlyeq a$, 则 $a = a \wedge b = b$ 成立
3. 传递性: $a \preccurlyeq b, b \preccurlyeq c$, 则 $a = a \wedge b = a \wedge (b \wedge c) = (a \wedge b) \wedge c = a \wedge c$, 即 $a \preccurlyeq c$ 成立

再证明 $a \wedge b$ 是 $a, b$ 的最大下界

$(a \wedge b) \wedge a = a \wedge b \Rightarrow a \wedge b \preccurlyeq a$, 同理 $a \wedge b \preccurlyeq b$, 说明 $a \wedge b$ 是 $a, b$ 的一个下界. 假设 $c$ 是 $a, b$ 的任意下界, 有 $c = a \wedge c, c = b \wedge c$, 则 $c \wedge c = a \wedge c \wedge b \wedge c \Rightarrow c = c \wedge (a \wedge b) \Rightarrow c \preccurlyeq a \wedge b$, 即 $a \wedge b$ 是最大下界

同理可证 $a \vee b$ 是 $a, b$ 的最小下界

($a \preccurlyeq b \Leftrightarrow a \wedge b = a \Leftrightarrow a \vee b = b$)

分配格

$\wedge, \vee$ 相互可分配

定理:

代数格 $<L, \wedge, \vee>$, 若 $\wedge$ 对 $\vee$ 可分配, 则 $\vee$ 对 $\wedge$ 可分配, 反之亦然

证明:

$\forall a, b, c \in L$,

$\begin{aligned} (a \vee b) \wedge (a \vee c) &= ((a \vee b) \wedge a) \vee ((a \vee b) \wedge c) \newline &= a \vee ((a \wedge c) \vee (b \wedge c)) \newline &= a \vee (a \wedge c) \vee (b \wedge c) \newline &= a \vee (b \wedge c) \end{aligned}$

另一个命题同理可证

定理:

链是分配格

证明:

$\forall a, b, c \in L$, $a \preccurlyeq b \preccurlyeq b \vee c, a \preccurlyeq c \preccurlyeq b \vee c$, $a \wedge (b \vee c) = a$, $(a \wedge b) \vee (a \wedge c) = a \vee a = a$, 故 $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$ 成立. 同理可整另一个命题.

定理:

分配格 $<L, \preccurlyeq>$, $\forall a, b, c \in L$, 若 $a \wedge b = a \wedge c, a \vee b = a \vee c$, 则 $b = c$

证明:

$\begin{aligned} b &= b \wedge (b \vee a) \newline &= b \wedge (c \vee a) \newline &= (b \wedge c) \vee (b \wedge a) \newline &= (b \wedge c) \vee (c \wedge a) \newline &= (a \vee b) \wedge c \newline &= (a \vee c) \wedge c \newline &= c \end{aligned}$

定理:

分配格当且仅当不存在与钻石格和五角格同构的子格

证明: 不会

分配格的子格是分配格

证明: 子代数的运算性质保持

全上 / 下界: $\forall a \in L, 0 \preccurlyeq a \preccurlyeq 1$

定理:

若有全上 / 下界, 则唯一

证明:

若还有一全下界 $0’$, 则有 $0 \preccurlyeq 0’, 0’ \preccurlyeq 0$, 则由偏序的反对称性得 $0’ = 0$

有界格: 既有全上界又有全下界

定理:

有限格是有界格

证明:

$1 = \vee a, 0 = \wedge a$

补元: 有界格, $a \wedge b = 0, a \vee b = 1$, 则 $a, b$ 互为补元

有补格: 有界格, 每个元素至少有一个补元

布尔格

分配且有补的格

定理:

布尔格每个元素的补元唯一

证明:

$a \wedge b = 0, a \wedge c = 0, a \vee b = 1, a \vee c = 1$, 根据分配格性质 $b = c$

布尔代数

布尔格诱导代数系统 $<B, \wedge, \vee, ’ >$.

任何有限布尔代数同构于 $<\rho(S), \cap, \cap>$.

覆盖: 最 “小” 的 $a$, 使得 $b \preccurlyeq a$, 则 $a$ 覆盖 $b$

原子: $a$ 覆盖 $0$, $a$ 是原子

都可以用集合的性质, 略

布尔表达式

$E(x, \dots) = \dots$, 看成一个 $n$ 元函数

布尔函数: $B^n \longrightarrow^f B$, $f$ 能用 $E(x, \dots)$ 表示

极小项: $n$ 元布尔表达式 $E(x_1, \dots) = (\wedge x_i) \wedge (\wedge x_j’)$

主析取范式: 形如 $\vee (a_i \wedge m_i)$ 的布尔表达式, $a_i \in B$, $m_i$ = 变量极小项, $x_k$ 则 set k, $x_k’$ 则 clear k, 得到一个二进制数 $i$.

极大项:

主合取范式:

表达式利用德摩根律, 将最外面的符号从 $\wedge$ 换到 $\vee$ 或者反过来, 然后求范式.

规律: 假设主析取的某一项为 $a \wedge m_i$, 则对应主合取的一项有 $a’ \vee M_i$

特别注意, 布尔代数可能不是二元的, 求解过程中会有 $(a \wedge m_i) \vee (b \wedge m_i)$ 这种, 要合并成 $(a \vee b) \wedge m_i$