LA4-1: 基本抽象代数

no comments

发布于 2026年10月31日最后更新 2026年10月31日

Preview 11

问题一：关系具有哪些重要性质？自反性、对称性/反对称性、传递性。

问题二：如何计算关系的闭包？自反闭包、对称闭包直接计算，传递闭包可使用 Warshall 算法。

关系的性质

关系的性质：自反性。

自反性（reflexive）： $\forall a \in A$ 有 $a R a$ .
反自反性（irreflexive）： $\forall a \in A$ 有 $\neg a R a$ .
$R$ 是 $A$ 上的自反关系等价于 $I_{A} \subseteq R$ .

关系的性质：对称性。

对称性（symmetric）： $a R b$ 则 $b R a$ .
反对称性（anti-symmetric）： $a R b$ 且 $b R a$ 则 $a = b$ .
$R$ 是集合 $A$ 上的对称关系等价于 $R^{- 1} = R$ .

关系的性质：传递性。

传递性（transitive）：若 $a R b, b R c$ 则 $a R c$ .
记 $R^{n} = R \circ R \circ \dots \circ R$ 其中共 $n$ 个 $R$ ，那么 $R$ 是集合 $A$ 上的对称关系等价于 $R^{2} \subseteq R$ .

一些常用关系的性质。

关系运算与性质的保持。

关系的闭包

闭包一般定义：设 $R$ 是集合 $A$ 上的关系， $P$ 是某种给定的性质，满足下列所有条件的关系 $p (R)$ 称为 $R$ 的关于 $P$ 的闭包：

$p (R)$ 满足性质 $P$ .
$R \subseteq p (R)$ .
如果存在集合 $A$ 上的关系 $R^{'}$ ，其满足性质 $P$ 且包含 $R$ ，则必然有 $p (R) \subseteq R^{'}$ .

自反闭包、对称闭包、传递闭包分别记为 $r (R), s (R), t (R)$ .

$r (R) = R \cup I_{A}$ .
$s (R) = R \cup R^{- 1}$ .
$t (R) = R^{*} = ⋃_{k = 1}^{\infty} R^{k}$ .

简记 $p (q (R))$ 为 $pq (R)$ ，那么：

$rs (R) = sr (R)$ .
$s t (R) \subseteq t s (R)$ .

关于某性质的闭包存在则必唯一。

有限集合上的传递闭包：特别地，如果 $∣ A ∣ = n$ ，那么 $t (A) = ⋃_{i = 1}^{n} R^{i}$ .

使用矩阵乘法计算传递闭包。

求传递闭包的 Warshall 算法。

Preview 12

一、等价关系与等价类。等价关系分元素为等价类，等价类集合为商集。

二、偏序关系、偏序集、偏序格。

等价关系

等价关系：非空集合上满足自反性、对称性、传递性的关系。

等价类：对于非空集合 $A$ 上的等价关系 $R$ ， $\forall x \in A$ ，称 $[x]_{R} = {y ∣ y \in A \land x R y}$ 为 $x$ 所在的等价类， $x$ 称为该等价类的代表元素。

商集：对于非空集合 $A$ 上的等价关系 $R$ ，其所有等价类的集合称为商集，记作 $A / R$ .

集合的划分：集合 $A$ 的划分 $π$ 是 $A$ 的一组非空子集的集合，且满足交空不漏：

$\forall x \in A, \exists A_{i} \in π, x \in A_{i}$ .
$\forall A_{i}, A_{j} \in π, i \neq = j \leftrightarrow A_{i} \cap A_{j} = \emptyset$ .

商集是集合的一种划分，反过来一个划分也可以定义一个等价关系。

偏序关系

偏序关系：非空集合上满足自反性、反对称性、传递性的关系，经常使用 $⪯$ 记录。

任取两元素 $x, y \in A$ ，存在三种情况： $x ≺ y$ 或 $y ≺ x$ ， $x = y$ ， $x ∥ y$ （二者不可比）。

若任何两元素都可比，则偏序关系转而称呼为全序关系（或线序关系）。

如果 $x ≺ y$ 且不存在 $z \in A$ 使得 $x ≺ z ≺ y$ ，则称 $y$ 覆盖 $x$ .

偏序集：集合 $A$ 和 $A$ 上的偏序关系构成的二元组，记作 $(A, ⪯)$ .

哈斯图：利用偏序关系的自反性、反对称性、传递性进行简化的关系图，特点如下：

每个结点无环。
两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前。
具有覆盖关系的两个结点之间连边。

字典序（lexicographic order）。

偏序集中的特殊元素

设 $(A, ⪯)$ 为偏序集， $B \subseteq A$ ， $y \in B$ ：

最小元： $\forall x (x \in B \to y ⪯ x)$ 则称 $y$ 为 $B$ 的最小元。
最大元： $\forall x (x \in B \to x ⪯ y)$ 则称 $y$ 为 $B$ 的最大元。
极小元： $\forall x (x \in B \land x ≺ y \to x = y)$ 则称 $y$ 为 $B$ 的极小元。
极大元： $\forall x (x \in B \land y ≺ x \to x = y)$ 则称 $y$ 为 $B$ 的极大元。

性质：对于有穷集，极大极小元一定存在，但不一定唯一。最大最小元不一定存在，但存在必唯一。最小元一定是极小元，最大元一定是极大元。孤立点既是极小元也是极大元。

此时如果改设 $y \in A$ ：

上界： $\forall x (x \in B \to x ⪯ y)$ 则称 $y$ 是 $B$ 的上界（UB）。
下界： $\forall x (x \in B \to y ⪯ x)$ 则称 $y$ 是 $B$ 的下界（LB）。
上确界：上界集合的最小元称为最小上界（LUB），也即上确界。
下确界：下界集合的最大元称为最大上界（GLB），也即下确界。

性质：四个界不一定存在。上下界存在也不一定唯一。上下确界存在则必唯一。集合的最小元就是它的下确界，集合的最大元就是它的上确界，反之不对。

偏序集与格

格（lattice）作为一个代数系统可以通过两种方式进行定义：

偏序集与偏序关系定义。
普通集合与特殊运算定义。

下文采用前者。

对于偏序集 $(S, ⪯)$ ，若 $\forall x, y \in S$ 我们都有 ${x, y}$ 的上下确界，那么 $S$ 关于偏序 $⪯$ 形成一个格。

依照前文，上下确界存在必唯一，所以可以将求上下确界写成二元运算，分别记为 $x \lor y$ 和 $x \land y$ .

格的对偶原理：设 $f$ 是含有格中元素以及符号 $=, ⪯, ⪰, \lor, \land$ 的命题，则将 $⪯, ⪰$ 互换， $\land, \lor$ 互换，得到的命题 $f^{*}$ 称为 $f$ 的对偶命题。若 $f$ 对一切格为真，那么 $f^{*}$ 也对一切格为真。

Preview 13

问题一：什么是代数系统？非空集合+封闭的（二元）运算。

问题二：代数系统相关性质？见下文。

问题三：什么是群？非空集合，二元运算，封闭性，结合律，单位元，逆元。

问题四：群有哪些性质？元素的阶、群的阶。

代数系统

代数系统一般被称为「抽象代数」（abstract algebra）或「近世代数」，20 世纪初被命名，但其研究的主要内容却于 19 世纪就已开展。

代数系统研究的主要内容包括：代数结构、群、环、域、模、向量空间、格、布尔代数、李代数等。

运算的函数定义：函数 $f : A^{n} \to B$ 称为（从 $A$ 到 $B$ 的） $n$ 元运算。下文主要讨论二元运算。

运算表：通常用于定义有限集合（一般元素很少）上的一元或二元运算。

运算的封闭性：对于运算 $f : A^{n} \to B$ ，若 $B \subseteq A$ ，则称该运算在集合 $A$ 上封闭（closeness）。

代数系统（简称代数）：给定一个非空集合 $S$ ，给定一个或若干个运算 $\circ$ ，运算对上述集合封闭，记作 $⟨ S, \circ ⟩$ .

运算的性质

结合性（associativity）：集合 $A$ 上的运算 $\circ$ 具有结合性定义为： $\forall x, y, z \in A, (x \circ y) \circ z = x \circ (y \circ z)$ .

交换性（commutativity）：集合 $A$ 上的运算 $\circ$ 具有交换性定义为： $\forall x, y \in A, x \circ y = y \circ x$ .

分配性（distributivity）：集合 $A$ 上的运算 $\circ$ 对 $*$ 满足分配性定义为： $\forall x, y, z \in A, x \circ (y * z) = (x \circ y) * (x \circ z)$ .

单位元（identity element）：元素 $e$ 是代数系统 $⟨ S, \circ ⟩$ 的单位元（幺元）当且仅当 $\forall x \in S, e \circ x = x \circ e = x$ .

单位元可记为 $1_{S}$ 或简记为 $1$ （幺），代数系统不一定有单位元。

左单位元和右单位元：元素 $e_{L}$ 称为系统的左单位元（左幺）当且仅当 $\forall x \in S, e_{L} \circ x = x$ ，类似可定义右单位元（右幺） $e_{R}$ .

左右单位元不一定存在也不一定唯一。但若一个代数系统同时有左右单位元，则左右单元必相等且唯一，即为单位元。系统若有单位元则必唯一。

逆元（inverse element）：只对存在单位元的代数系统讨论逆元：给定系统 $S$ 中的元素 $x$ ，若存在 $x_{L}^{'} \in S$ 满足 $x_{L}^{'} \circ x = 1_{S}$ ，那么称其为左逆元；同理得到右逆元 $x_{R}^{'}$ ；若存在 $x^{*} \in S$ 满足 $x^{*} \circ x = x \circ x^{*} = 1_{S}$ ，那么称 $x^{*}$ 为 $x$ 的逆元，一般记为 $x^{- 1}$ .

逆元既是左逆元也是右逆元， $x$ 和 $x^{- 1}$ 互为逆元。

若代数系统满足结合律：那么对于既有左逆又有右逆的元素，左右逆必相等且唯一；每个元素均有左逆，则左逆即右逆，同时逆元唯一。

零元：元素 $t$ 是代数系统的零元当且仅当 $\forall x \in S, t \circ x = x \circ t = t$ ，可记为 $0_{S}$ ，或简记为 $0$ .

一个代数系统不一定存在零元。

同构（isomorphism）：代数系统 $⟨ S_{1}, \circ ⟩$ 和 $⟨ S_{2}, * ⟩$ 同构（ $S_{1} ≅ S_{2}$ ）当且仅当存在双射函数 $f : S_{1} \to S_{2}$ 满足： $\forall x, y \in S_{1}, f (x \circ y) = f (x) * f (y)$ ，这个函数 $f$ 称为同构映射。同构关系是等价关系。

同态（homomorphism）：代数系统 $⟨ S_{1}, \circ ⟩$ 和 $⟨ S_{2}, * ⟩$ 同态（ $S_{1} \sim S_{2}$ ）当且仅当存在函数 $f : S_{1} \to S_{2}$ 满足： $\forall x, y \in S_{1}, f (x \circ y) = f (x) * f (y)$ ，这个函数 $f$ 称为同态映射。特别地，若 $f$ 为满射则称二者「满同态」（epimorphism）

群

代数系统（magma）+结合性称为「半群」（semigroup）。

半群+单位元称为「幺半群」（monoid, semigroup with unit）。注意代数系统中存在左右单位元则必相等且唯一。

幺半群+所有元素均有逆元称为「群」（group）。注意半群中逆元若存在则唯一。

群的性质：设 $⟨ G, *, e,^{- 1} ⟩$ 为群：

$(a^{- 1})^{- 1} = a$ .
$(ab)^{- 1} = b^{- 1} a^{- 1}$ .
左消去律： $ab = a c \to b = c$ .
右消去律： $ba = c a \to b = c$ .
$a x = b$ 和 $y a = b$ 在 $G$ 中对 $x, y$ 有唯一解。

运算 $a * b$ 常省去符号而直接拼在一起 $ab$ ， $a * a$ 等常记为 $a^{2}$ 及 $a^{k}$ 等。显然在群中 $a^{n} * a^{m} = a^{n + m}, (a^{n})^{m} = a^{nm}$ .

元素的阶： $∣ a ∣ = min {k \in Z_{+} ∣ a^{k} = e}$ ，如果这样的 $k$ 不存在，则 $a$ 为无限阶元 $∣ a ∣ = \infty$ .

性质：

有限群不存在无限阶元。
群中元素及其逆元具有相同的阶。
有限群中阶大于二的元素有偶数个。
偶数群中阶为二的元素有奇数个。

对于 $⟨ G, *, e,^{- 1} ⟩, a, b \in G, ∣ a ∣, ∣ b ∣$ 均有穷：

$a^{k} = e \leftrightarrow ∣ a ∣ ∣ k$ .
$∣ a ∣ = a^{- 1}$ .
$∣ ab ∣ = ∣ ba ∣$ .
$∣ b^{- 1} ab ∣ = ∣ a ∣$ .

群的阶：若集合有限，则成为有限群，阶为元素的个数；若集合为无穷集，则称其为无限群。

一阶群、二阶群、三阶群在同构一一下只有一个。四阶群均为 Abel 群，同构意义下仅有两个： $Z_{4}$ 和 $K_{4}$ .

群方程，群的方程定义。

Preview 14

问题一：什么是子群，如何判别？非空子集为群，判定根据定义或三个判定定理。

问题二：子群一定存在吗？若存在则有什么性质？一定存在平凡子群。性质包括子群的所有陪集构成母群的一个划分，Lagrange 定理及其推论。

子群

设 $⟨ G, \circ ⟩$ 是群， $H$ 是 $G$ 的非空子集，若 $⟨ H, \circ ⟩$ 也是群，则 $H$ 是 $G$ 的子群，记作 $⟨ H, \circ ⟩ \leq ⟨ G, \circ ⟩$ ，简记为 $H \leq G$ . 两个平凡子群是 $⟨{e}, \circ ⟩$ 和 $⟨ G, \circ ⟩$ .

子群的判定：

判定定理一：对于群 $G$ 的非空子集 $H$ ，其为 $G$ 的子群当且仅当 $\forall a, b \in H, ab \in H$ 且 $\forall a \in H, a^{- 1} \in H$ .
判定定理二：对于群 $G$ 的非空子集 $H$ ，其为 $G$ 的子群当且仅当 $\forall a, b \in H, a b^{- 1} \in H$ .
判定定理三：对于群 $G$ 的非空有限子集 $H$ ，其为 $G$ 的子群当且仅当 $\forall a, b \in H, ab \in H$ .

生成子群和陪集

设 $G$ 是群， $a \in G$ ，构造 $G$ 的子群 $H = {a^{k} ∣ k \in Z}$ ，称为 $a$ 生成的子群 $⟨ a ⟩$ .

左陪集和右陪集：若 $H$ 是群 $G$ 的一个子群， $a \in G$ ，定义 $a H = {ah ∣ h \in H}$ 为 $H$ 关于 $a$ 的左陪集，类似可定义右陪集。

设 $H$ 是群 $G$ 的子群，则 $H$ 的所有左陪集构成 $G$ 的划分。右陪集同理。

正规子群： $H$ 是 $G$ 的一个子群，当且仅当 $\forall g \in G$ 使得 $g H = H g$ 时，称 $H$ 为 $G$ 的正规子群。

引理：左右陪集和子群的势相等： $H \approx a H \approx H a$ .

指数：对有限群 $G$ ，每个陪集元素个数有限且相同，并等于 $∣ H ∣$ （引理），所以 $∣ G ∣ = k ∣ H ∣$ ，此 $k$ 即为左陪集（右陪集）的数量，称为 $H$ 在 $G$ 中的指数，记作 $[G : H]$ .

Lagrange 定理：设 $⟨ G, * ⟩$ 为有限群， $⟨ H, * ⟩ < ⟨ G, * ⟩$ 则 $∣ G ∣ = ∣ H ∣ [G : H]$ .

推论： $a \in G$ ，则 $∣ a ∣ ∣ ∣ G ∣$ .

推论：质数阶群存在元素，其阶等于群的阶。

推论：六阶群必含三阶子群。

Preview 15

问题一：什么是循环群？可通过某个元素（生成元）生成所有元素的群。

问题二：循环群的子群是否存在？如何构造？对于 $n$ 阶循环群，恰有一个 $d$ 阶子群 $⟨ a^{n / d} ⟩$ ，此处 $d ∣ n$ .

问题三：循环群是否存在统一的规律性？无限循环群同构于整数加法群，有限循环群同构于模加法群。

循环群与生成元

设 $⟨ G, * ⟩$ 为「循环群」（cyclic group），则 $\exists a \in G, G = ⟨ a ⟩$ ，此处 $⟨ a ⟩ = {a^{n} ∣ n \in Z}$ ， $a$ 称为 $G$ 的「生成元」（generator）。

有限循环群：循环群的生成元的阶有限。

无限循环群：循环群的生成元为无限阶元。

命题：若 $a$ 是无限循环群的生成元，则 $a^{- 1}$ 也是该无限循环群的生成元。

命题：无限循环群有且仅有两个生成元。

命题：设有限循环群 $G = ⟨ a ⟩, ∣ a ∣ = n$ ，则对任意正整数 $r \leq n$ 有 $G = ⟨ a^{r} ⟩ \Leftrightarrow g cd (n, r) = 1$ .

命题：由 Euler phi 函数的定义， $n$ 阶有限循环群有 $φ (n)$ 个生成元。

循环群的子群

设 $G = ⟨ a ⟩$ 为循环群，则：

$G$ 的子群为循环群
若 $∣ a ∣ = \infty$ ，则 $G$ 的子群除 ${e}$ 外均为无限循环群。

命题：对 $n$ 的每个因子 $d$ ， $n$ 阶循环群 $G$ 中恰有一个 $d$ 阶子群。

循环群的性质

群同构与同构映射、群同态与同态映射。

命题：若 $f$ 为 $G$ 到 $H$ 的同态，则： $f (e_{G}) = e_{H}, f (a^{- 1}) = (f (a))^{- 1}, \forall a \in G$ .

定理：设 $⟨ G, * ⟩$ 为无限循环群，则 $⟨ G, * ⟩ ≅ ⟨ Z, + ⟩$ .

定理：设 $⟨ G, * ⟩$ 为有限循环群，则 $⟨ G, * ⟩ ≅ ⟨ Z_{n}, \oplus_{n} ⟩$ .（ $\oplus_{n}$ 为模 $n$ 加法）。

推论：循环群都是阿贝尔群。

群的直积：对于群 $⟨ S, \circ ⟩$ 和 $⟨ T, * ⟩$ ，定义笛卡尔积 $S \times T$ 上的运算 $\otimes$ ： $(s_{1}, t_{1}) \otimes (s_{2}, t_{2}) = (s_{1} \circ s_{2}, t_{1} * t_{2})$ ,则 $⟨ S \times T, \otimes ⟩$ 为群，称作群的直积（群的外直积）。

循环群的直积： $g cd (m, n) = 1$ 则 $C_{m} \times C_{n} ≅ C_{mn}$ ，其中 $C_{k}$ 表示 $k$ 阶循环群。

命题： $\sum_{d ∣ n} φ (d) = n$ . 推论： $C_{n}$ 中 $d$ 阶元素共有 $φ (d)$ 个。

欧拉定理： $a^{φ (n)} \equiv 1 (mod n), g cd (a, n) = 1$ .

Preview 16

内容一：代数格的定义与性质。满足结合律、交换律、吸收律的两个二元运算与集合。

内容二：格同态、格同构。格的同态、格的同构。

内容三：分配格、有补格，有补分配格。

代数格

代数格：设 $L$ 是一个集合， $\land, \lor$ 是 $L$ 上的二元运算，且满足结合律、交换律、吸收律，则称 $⟨ L, \land, \lor ⟩$ 是代数格。

代数格中的偏序关系： $\forall x, y \in L, x \land y = x \leftrightarrow x \lor y = y$ ，从而可以定义 $x ⪯ y \leftrightarrow x \land y = x$ . 从而代数格等同于（偏序格）。

两次应用吸收律推出幂等律： $x \land x = x \land (x \lor (x \land x)) = x$ .

格同态：设 $L_{1}$ 和 $L_{2}$ 为格，若有 $f : L_{1} \to L_{2}$ 使得 $\forall a, b \in L_{1}$ 有 $f (a \land b) = f (a) \land f (b), f (a \lor b) = f (a) \lor f (b)$ ，则称 $f$ 为 $L_{1}$ 到 $L_{2}$ 的同态映射，称为格同态。

格同态的性质：

格同态保序，即 $\forall x, y \in L_{1}, x ⪯ y \to f (x) ⪯ f (y)$ .
若 $f$ 为双射，则格同态转换为格同构。其等价条件是 $\forall x, y \in L_{1}, x ⪯ y \leftrightarrow f (x) ⪯ f (y)$ .

几种典型的格

链（chain）
钻石格（diamond lattice）： $M_{3}$ .
五角格（pentagon lattice）： $N_{5}$ .

分配格（distributive lattice）：满足 $\land$ 对 $\lor$ 的分配律和 $\lor$ 对 $\land$ 分配律的格。

子格（sub lattice）：子集对两个集合仍然构成格。

分配格判定定理一：格为分配格当且仅当其不含有与钻石格或五角格同构的子格。

推论：小于五元的格均为分配格。

推论：链均为分配格。

分配格判定定理二：格 $L$ 为分配格当且仅当 $\forall a, b, c \in L, a \land b = a \land c$ 且 $a \lor b = a \lor c \to b = c$ .

有界格：对于格 $L$ ，若存在 $b \in L, \forall x \in L, b ⪯ x$ ，则称 $b$ 为格的「全下界」（bottom）；若存在 $t \in L, \forall x \in L, x ⪯ t$ ，则称 $t$ 为格的「全上界」（top）。同时拥有两者的格称为有界格（bounded lattice）。

格中存在全下界或全上界，则必唯一。
一般记全下界为 $0$ ，全上界为 $1$ .
有界格一般记为 $⟨ L, \land, \lor, 0, 1 ⟩$ .
有限格皆为有界格，所有元素的 join 和 meet 为该有界格的全上界和全下界。
由此推广对偶原理，将全上界和全下界调换，命题成立。
有界格满足同一律和支配律，全上下界为两个运算的单位元和零元。

补元：有界格中若 $a \in L, \exists b \in L, a \land b = 0$ 且 $a \lor b = 1$ 则称 $b$ 为 $a$ 的补元（complement）。

任何有界格中，全上下界互补。
对于一般元素，补元不一定存在。
补元若存在，也不一定唯一。
对于有界分配格，补元若存在则唯一。

有补格：有界格中所有元素都存在补元，此时称为有补格（complemented lattice）。

有补分配格：既是有补格也是分配格。

代数格：结合律、交换律、吸收律、（幂等律）。
分配格：分配律。
有界：同一律、（支配律）。
有补：补律、（双重补律）、（德摩根律）。

Preview 17

内容一：布尔代数。

内容二：有限布尔代数表示定理。

布尔代数的抽象定义

一个布尔代数是一个集合 $B$ ，其有二元运算 $+ (\lor)$ 和 $\cdot (\land)$ ，一元运算及特殊元素 $0$ 和 $1$ 满足以下五条性质：结合律、交换律、分配律、同一律、补律。则 $⟨ B, +, \cdot, 0, 1 ⟩$ 为布尔代数。

这五条性质蕴含吸收律、支配律、幂等律、双重补律、德摩根律。

布尔代数相当于有补分配格。

有限布尔代数表示定理

原子（覆盖最小元的元素）：设 $L$ 为格， $L$ 有最小元（全下界） $0$ ，给定元素 $a \neq = 0$ ，若 $\forall x \in L, 0 ≺ x ⪯ a \to x = a$ ，则称 $a$ 是 $L$ 中的原子。

命题：原子的 meet 是最小元。

有限布尔代数表示定理：任一有限布尔代数 $B$ 同构于 $B$ 中所有原子构成的集合 $A$ 的幂集代数系统 $P (A)$ ，也即： $⟨ B, +, \cdot,, 0, 1 ⟩ ≅ ⟨ P (A), \cap, \cup, \sim, \emptyset, A ⟩$ .

注：无限布尔代数不一定有原子。

推论：任何有限布尔代数的基数是二的幂次。

推论：等势的有限布尔代数均同构。

推论： $B_{n} ≅ B_{1} \times \dots \times B_{1}$ ，其中 $n$ 个 $B_{1}$ .

推论：无平方因子的正整数可构造出一个布尔代数。

推论：有平方因子的正整数不可构造出一个布尔代数。

证明：设 $p^{2} ∣ n, p$ 是整数，那么考虑 $p$ 的补 $p^{'}$ ，将会有 $p p^{'} = n$ ，这就导致了 $g cd (p, p^{'}) = p$ ，与 $g cd (p, p^{'}) = 1$ 矛盾，故不是布尔代数。

布尔代数应用

数字电路中逻辑图表：or gate, and gate, inverter、卡诺图（Karnaugh map）及其简化。