当前位置：首页 > article >正文

离散数学笔记

article 2024/11/19 19:49:00

第 1 章数理逻辑

1.1 命题

1.1.1 基本概念

非真即假的陈述句称作命题

作为命题的陈述句所表达的判断结果称作命题的真值

真值只取两个值：真（1或T）或假（0或F）

真值为真的命题称作真命题，真值为假的命题称作假命题

断言“我正在说谎”事实上不能指定它的真假，所以不是命题，这种断言叫悖论。

原子命题：不能被分解成更简单命题的陈述句

1.1.2 命题联结词

复合命题：（原子）命题+联结词

“p 并且 q (或 p 与 q)” 称为 p 与 g 的合取式，记作 $p\wedge q$ ， $\wedge$ 称作合取联结词，规定 $p\wedge q$ 为真当且仅当 p 与 g 同时为真

“p 或 q” 称作 p 与 q 的析取式，记作 $p\vee q$ ， $\vee$ 称作析取联结词，规定 $p\vee q$ 为假当且仅当 p 与 g 同时为假

“如果 p，则 q” 称为 p 与 q 的蕴涵式 ，记作 $p\rightarrow q$ ，并称 p 是蕴涵式的前件，q 为蕴涵式的后件， $\rightarrow$ 称作蕴涵联结词，并规定 $p\rightarrow q$ 为假当且仅当 p 为真 q 为假，如果 p 为假 q 为真，则 $p\rightarrow q$ 依旧是真，p 为假 q 为假， $p\rightarrow q$ 依旧为真

p	q	$p\rightarrow q$
1	0	0
0	1	1
0	0	1

形式蕴含：前提和结论之间有因果或实质关系

实质蕴含：前提和结论并不需要有因果和实质联系

"p 当且仅当 q" 称作 p 与 q 的等值式，记作 $p\leftrightarrow q$ ， $\leftrightarrow$ 称作等价联上词，规定 $p\leftrightarrow q$ 为真当且仅当 p 与 q 同时为真或同时为假

相容或： $P\vee Q$

排斥或： $(P\wedge \neg Q)\vee (\neg P\wedge Q)$ ，不能同时成立

联结词优先级： $\neg >\wedge >\vee > \rightarrow >\leftrightarrow$ ，同一级：一元从右到左，二元从左到右

注意 $\wedge$ 和 $\vee$ 的优先级不一样

将命题公式 A 在所有赋值下取值情况列成表，称作 A 的真值表

设 S 是一个联结词集合，如果任何 $n(n\geqslant 1)$ 元真值函数都可以由仅含 S 中的联结词构成的公式表示，则称 S 是联结词完备集

$S=\{\neg , \wedge, \vee \}$ 是联结词完备集

1.1.3 命题变元和命题公式

如果尸代表真值未指定的任意命题，我们就称P 为命题变元；

如果 P 代表一个真值已指定的命题，我们就称 P 为命题常元

以“真”、“假”为其变域的变元，称为命题变元；T 和 F 称为命题常元。

将命题变项用联结词和圆括号按照一定的逻辑关系联结起来的符号串称作命题公式

(1) 单个命题变项和命题常项是命题公式，并称为原子命题公式

(2) 若 A 是命题公式，则 $(\neg A)$ 是命题公式.

(3) 若 A, B 是命题公式，则 $(A\wedge B),(A\vee B),(A\rightarrow B),(A\leftrightarrow B)$ 是命题公式

(4) 有限次地应用 (1) ~ (3) 形成的符号串是命题公式

简称为公式

考点：语言符号化

1.2 重言式

1.2.1 基本概念

设有一个 n 元命题公式， $A(P_1,\cdots ,P_n)$ 每一个变元有真、假两个值可选，即命题变元的真值有 $2^n$ 种不同组合，每一种组合叫做一个指派

设 A 为任一命题公式

(1) 重言式或永真式：在所有指派下取值均为真

(2) 矛盾式或永假式：在所有指派下取值均为假

(3) 可满足式：至少存在一个指派使公式的值为真

(4) 偶然式：既不是永真式，也不是永假式

(5) 非永真：至少存在一个指派，使公式的值为假

永真式的否定是永假式

设公式 A, B 中共含有命题变项 $p_1,p_2,\cdots,p_n$ ，而 A 或 B 不全含这些命题变项，例如，A 中不含 $p_i,p_{i+1},\cdots,p_n,i\geqslant 2$ ，称这些命题变项为 A 的哑元

设公式 A, B 共同含有 n 个命题变项，A 或 B 可能有哑元，若 A 与 B 有相同的真值表，则说明在所有 $2^n$ 个赋值下，A 与 B 的真值都相同，因而等价式 $A\leftrightarrow B$ 为重言式.

1.2.2 恒等式

若等价式 $A\leftrightarrow B$ 为重言式，则称 A 与 B 是等值的，即 A 和 B 对于任何指派都具有相同的真值，记作 $A\Leftrightarrow B$ ，称为逻辑恒等式，A 恒等于 B，或 A 等价于 B

逻辑恒等式

双重否定律	$A\Leftrightarrow \neg \neg A$
幂等式	$A\Leftrightarrow A\vee A,A\Leftrightarrow A\wedge A$
交换律	$A\vee B\Leftrightarrow B \vee A, A\wedge B\Leftrightarrow B\wedge A$
结合律	$(A\vee B)\vee C \Leftrightarrow A\vee(B\vee C)\\ (A\wedge B)\wedge C \Leftrightarrow A\wedge(B\wedge C)$
分配律	$A\vee (B\wedge C) \Leftrightarrow (A\vee B)\wedge (A\vee C)\\ A\wedge (B\vee C) \Leftrightarrow (A\wedge B)\vee (A\wedge C)$
德摩根律	$\neg (A\vee B)\Leftrightarrow \neg A \wedge \neg B\\ \neg (A\wedge B)\Leftrightarrow \neg A \vee \neg B$
吸收律	$A\vee (A\wedge B)\Leftrightarrow A\\ A\wedge (A\vee B)\Leftrightarrow A$
零律	$A\vee 1\Leftrightarrow 1,A\wedge 0\Leftrightarrow 0$
同一律	$A\vee 0\Leftrightarrow A,A\wedge 1\Leftrightarrow A$
排中律	$A\vee \neg A\Leftrightarrow 1$
矛盾律	$A\wedge \neg A\Leftrightarrow 0$
蕴涵等值式	$A\rightarrow B\Leftrightarrow \neg A\vee B$
等价等值式	$A\leftrightarrow B\Leftrightarrow (A\rightarrow B)\wedge (B\rightarrow A)$
假言易位	$A\rightarrow B\Leftrightarrow \neg B\rightarrow \neg A$
等价否定等值式	$A\leftrightarrow B\Leftrightarrow\neg A \leftrightarrow \neg B$
归谬论	$(A\rightarrow B)\wedge (A\rightarrow \neg B)\Leftrightarrow \neg A$

1.2.3 永真蕴含式

如果 $A\rightarrow B$ 是一永真式，那么称为永真蕴含式 $A\rightarrow B$ ，记为，读做“A 永真蕴含 B”

永真蕴含式也可用真值表证明，但也可用以下办法证明：

(1) 假定前件是真，若能推出后件是真，则此蕴含式是真。

(2) 假定后件是假，若能推出前件是假，则此蕴含式是真，即证逆否命题

例：证明 $\neg Q\wedge (P\rightarrow Q)\Rightarrow \neg P$

方法 1：设 $\neg Q\wedge (P\rightarrow Q)$ 是真，则 $\neg Q,P\rightarrow Q$ 是真。所以，Q 是假，P 是假。因而 $\neg P$ 是真。故 $\neg Q\wedge (P\rightarrow Q)\Rightarrow \neg P$ 。

方法 2：设 $\neg P$ 是假，则 P 是真。以下分情况讨论。

(i) 若 Q 为真，则 $\neg Q$ 是假，所以 $\neg Q\wedge (P\rightarrow Q)$ 是假。

(ii) 若 Q 是假，则 $P\rightarrow Q$ 是假，所以 $\neg Q\wedge (P\rightarrow Q)$ 是假。

故 $\neg Q\wedge (P\rightarrow Q)\Rightarrow \neg P$ 。

1.2.4 恒等式和永真蕴含式的两个性质

若 $A\Rightarrow B,A\Rightarrow C$ ，则 $A\Rightarrow B\wedge C$ 。

1.2.5 代入规则和替换规则

代入规则

重言式中某个命题变元出现的每一处均代入以同一公式后，所得的仍是重言式。

这条规则之所以正确是由于重言式之值不依赖于变元的值的缘故。重言式就是永真式

代人后所得公式称为原公式的代入实例。

替换规则

设有恒等式 $A\Leftrightarrow B$ ，若在公式 C 中出现 A 的地方替换以 B(不必每一处)而得到公式 D，则 $C\Leftrightarrow D$

例：证明 $P\wedge \neg Q\vee Q\Leftrightarrow P\vee Q$

例：证明 $(P\rightarrow Q)\rightarrow (Q\vee R)\Leftrightarrow P\vee Q\vee R$

1.2.6 对偶原理

设有公式 A，其中仅有联结词 $\wedge$ 、V 、 $\neg$ 。在 A 中将 $\wedge$ 、V、T、F 分别换以 V 、 $\wedge$ 、F、T 得公式 A*，则 A* 称为 A 的对偶公式。

设 A 和 A* 是对偶式。 $P_1,P_2,\cdots,P_n$ 是出现于 A 和 A* 中的所有命题变元，于是

$\neg A(P_1,P_2,\cdots,P_n)\Leftrightarrow A^*(\neg P_1,\neg P_2,\cdots,\neg P_n)$

对偶原理：若 $A\Leftrightarrow B$ ，则 $A^*\Leftrightarrow B^*$

如果 $A\Rightarrow B$ ，则 $B^*\Rightarrow A^*$

1.3 范式

1.3.1 析取范式和合取范式

1.3.2 主析取范式和主合取范式

1.3.3 主析取范式的个数

1.4 联结词的扩充与归约

1.4.1 联结词的扩充

1.4.2 联结词的归约

*1.4.3 其它主范式

1.5 推理规则和证明方法

1.5.1 推理规则

1.5.2 证明方法

*1.5.3 推理的其它问题

1.6 谓词和量词

1.6.1 谓词

1.6.2 量词

1.6.3 量化断言和命题的关系

1.6.4 谓词公式

1.6.5 自由变元与约束变元

1.7 谓词演算的永真公式

1.7.1 基本定义

1.7.2 谓词演算的基本永真公式

1.7.3 几条规则

1.8 谓词演算的推理规则

1.8.1 术语“A(x)对y是自由的”的意义

1.8.2 谓词演算中的推理规则

1.8.3 推理举例

第 2 章集合

2.1 集合论的基本概念

2.2 集合上的运算

2.3 归纳法和自然数

*2.4 语言上的运算

2.5 集合的笛卡尔乘积

第 3 章二元关系

3. 1 基本概念

3. 2 关系的合成

3.3 关系上的闭包运算

3.4 次序关系

3.5 等价关系和划分

第 4 章函数

4.1 函数的基本概念

4.2 特殊函数类

4.3 逆函数

第 5 章无限集合

5.1 可数和不可数集合

5.2 基数的比较

*5.3 基数算术

第 6 章代数

6.1 代数结构

6.2 子代数

6.3 同态

6.4 同余关系

6.5 商代数和积代数

6.6 半群和独异点

6.7 群

6.8 环和域

第 7 章格与布尔代数

7.1 格

7.2 格是代数系统

7.3 特殊的格

7.4 布尔代数

第 8 章图论

8.1 图的基本概念

8.2 路径和回路

8.3 图的矩阵表示

8.4 图的支配集、独立集和覆盖

8.5 二部图

8.6 平面图和图的着色

8.7 树

8.8 有向树

*8.9 运输网络

第 1 章命题逻辑的基本概念

1.1 命题与联结词

1.2 命题公式及其赋值

第 2 章命题逻辑等值演算

2.1 等值式

2.2 析取范式与合取范式

2.3 联结词的完备集

2.4 可满足性问题与消解法

由于任一公式都能化成等值的合取范式，因而一般的命题公式的可满足性问题可以归结为合取范式的可满足性问题

设 S 和 S' 是两个合取范式，用 $S\approx S'$ 表示 S 是可满足的当且仅当 S' 是可满足的

设 $C_1,C_2$ 是两个简单析取式， $C_1$ 含文字 $l$ ， $C_2$ 含 $l^c$ ，从 $C_1$ 中删去 $l$ ，从 $C_2$ 中删去 $l^c$ ，然后再将所得到的结果析取成一个简单析取式，称这样得到的简单析取式为 $C_1,C_2$ 的 (以 $l$ 和 $l^c$ 为消解文字的) 消解式或消解结果，记为 $Res(C_1,C_2)$

即设 $C_1=C_1'\vee l,C_2=C_2'\vee l^c$ ， $Res(C_1,C_2)=C_1'\vee C_2'$

根据上述定义由 $C_1,C_2$ 得到 $Res(C_1,C_2)$ 的规则称作消解规则

第 3 章命题逻辑的推理理论

3.1 推理的形式结构

设 $A_1,A_2,\cdots,A_k$ 和 B 都是命题公式，若对于 $A_1,A_2,\cdots,A_k$ 和 B 中出现的命题变项的任意一组赋值，或者 $A_1\wedge A_2 \wedge \cdots \wedge A_k$ 为假，或者当 $A_1\wedge A_2 \wedge \cdots \wedge A_k$ 为真时 B 也为真，则称由前提 $A_1,A_2,\cdots,A_k$ 推出结论 B 的推理是有效的或正确的，并称 B 为有效的结论.

3.2 自然推理系统 P

一个形式系统 $I$ 由下面 4 个部分组成

(1) 非空的字母表 $A(I)$

(2) $A(I)$ 中符号构造的合式公式集 $E(I)$

(3) $E(I)$ 中一些特殊的公式组成的公理集 $A_X(I)$

(4) 推理规则集 $R(I)$

将 $I$ 记为 4 元组 $<A(I),E(I),A_X(I),R(I)>$ ，其中 $<A(I),E(I)>$ 是 $I$ 的形式语言系统，而 $<A_X(I),R(I)>$ 为 $I$ 的形式演算系统

形式系统一般分为两类：

一类是自然推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，最后得到的命题公式是推理的结论 (它是有效的结论，可能是重言式，也可能不是重言式)

另一类是公理推理系统，它只能从若干条给定的公理出发，应用系统中的推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理

3.3 消解证明法

消解证明法是根据归谬法的思想，采用消解规则构造证明的方法。

它的基本做法是，把前提中的公式和结论的否定都化成等值的合取范式，以这些合取范式中的所有简单析取式作为前提，用消解规则构造证明，如果能得到空式，则证明推理是正确的。

消解证明法除准备工作外，只使用前提引入和消解两条规则.

第 4 章一阶逻辑基本概念

在命题逻辑中只能将推理中出现的 3 个简单命题依次符号化为 p，g，r，将推理的形式结构符号化为 $(p\wedge q)\rightarrow r$

4.1 一阶逻辑命题符号化

个体词、谓词和量词是一阶逻辑命题符号化的 3 个基本要素

个体词

个本词是指所研究对象中可以独立存在的具体的或抽象的客体，例如，小王，小李，中国， $\sqrt{2}$ ，3 等都可作为个体词

将表示具体或特定的客体的个体词称作个体常项 ，一般用小写英文字 a, b, c 等表示，而将表示抽象或泛指的个体词称作个体变项，常用 x, y, z 等表示，并称个体变项的取值范围为个体域(或称作论域)，个体域可以是有穷集合，例如，{1, 2, 3}，{a, b, c, d}，{a, b, c, …, x, y, z} 等，也可以是无穷集合，如自然数集合 N、实数集合 R 等

有一个特殊的个体域，它是由宇宙间一切事物组成的，称作全总个体域

谓词

谓词是用来刻画个体词性质及个体词之间相互关系的词，常用 F, G, H 等表示

考虑下面 4 个陈述句：

(1) $\sqrt{2}$ 是无理数， $\sqrt{2}$ 是个体常项，“…是无理数”是谓词，记为 F，整个陈述句可以表示成 $F(\sqrt{2})$

(2) x 是有理数，x 是个体变项，“……是有理数”是谓词，记作 G，这个陈述句可以表示成 G(x).

(3) 小王与小李同岁，小王，小李都是个体常项，“……与……同岁”是谓词，记作 H，这个陈述句可符号化为 H(a, b)，其中 a 表示小王，b 表示小李.

(4) x 与 y 具有关系 L，x, y 为两个个体变项，L 是谓词，这个陈述句的符号化形式为 L(x, y).

同个体词一样，谓词也有常项与变项之分。

表示具体性质或关系的谓词称作谓词常项，表示抽象的或泛指的性质或关系的谓词称作谓词变项，无论是谓词常项或变项都用大写英文字母 F, G, H 等表示，要根据上下文区分

在上面 4 个陈述句中，(1), (2), (3)中谓词 F, G, H 是常项，而 (4) 中谓词 L 是变项，因为关系 L 没有具体表明

含 $n(n\geqslant 1)$ 个个体变项 $x_1,x_2,\cdots,x_n$ 的谓词 P 称作 n 元谓词，记作 $P(x_1,x_2,\cdots,x_n)$ ，当 n = 1 时， $P(x_1)$ 表示 $x_1$ 具有性质 P；当 $n\geqslant 2$ 时， $P(x_1,x_2,\cdots,x_n)$ 表示 $x_1,x_2,\cdots,x_n$ 具有关系 P，n 元谓词是以个体域为定义域，以 {0, 1} 为值域的 n 元函数或关系.

有时将不带个体变项的谓词称作 0 元谓词。例如， $F(a),G(a,b),P(a_1,a_2,\cdots,a_n)$ 等都是 0 元渭词

当 F, G, P 为谓词常项时，0 元谓词为命题，反之，任何命题均可以表示成 0 元谓词，因而可以将命题看成特殊的谓词

量词

表示个体常项或变项之间数量关系的词称作量词

(1) 全称量词，日常生活和数学中常用的“一切的”“所有的”“每一个”“任意的”“凡”“都” 等词统称作全称量词，用符号“ $\forall$ ”表示， $\forall x$ 表示个体域里的所有个体 x，其中个体域是事先约定的。例如， $\forall xF(x)$ 表示个体域里所有个体 x 都有性质 F， $\forall x\forall yG(x,y)$ 表示个体域里的所有个体 x 和 y 有关系 G，其中 F 和 G 是谓词

(2) 存在量词，日常生活和数学中常用的“存在”“有一个”“有的”“至少有一个”等词统称作存在量词，用符号“ $\exists$ ”表示， $\exists x$ 表示个体域里有一个个体 x，例如，用 $\exists x F(x)$ 表示在个体域里存在个体 x 具有性质 F， $\exists x \exists yG(x,y)$ 表示在个体域里存在个体 x 和 y 有关系 G。

全称量词和存在量词可以联合使用，例如， $\forall x \exists y G(x,y)$ 表示对个体域里所有个体 x，存在 y 使得 x 和 y 有关系 G；而 $\exists x \forall yG(x,y)$ 表示个体域里存在个体 x 使得其和所有的个体 y 有关系 G

4.2 一阶逻辑公式及其解释

在描述对象和形式化时要使用个体常项、个体变项、函数、谓词、量词、联结词和括号与逗号，个体常项符号、函数符号和谓词符号称作非逻辑符号

个体变项符号、量词符号、联结词符号和括号与逗号称作逻辑符号

第 5 章一阶逻辑等值演算与推理

5.1 —阶逻辑等值式与置换规则

置换规则

设 $\Phi (A)$ 是含公式 A 的公式， $\Phi(B)$ 是用公式 B 取代 $\Phi (A)$ 中所有的 A 之后所得到的公式，那么，若 $A\Leftrightarrow B$ ，则 $\Phi(A)\Leftrightarrow \Phi(B)$

换命规则

设 A 为一公式，将 A 中某量词辖域中的一个约束变项的所有出现及相应的指导变元全部改成该量词辖域中未曾出现过的某个个体变项符号，公式中其余部分不变，将所得公式记作 A'，则 $A'\Leftrightarrow A$

5.2 一阶逻辑前束范式

具有如下形式 $Q_1x_1Q_2x_2\cdots Q_kx_kB$ 的一阶逻辑公式称作前束范式，其中 $Q_i(1\leqslant i \leqslant k)$ 为 $\forall$ 或 $\exists$ ，B 为不含量词的公式

5.3 —阶逻辑的推理理论

第 6 章集合代数

6.1 集合的基本概念

6.2 集合的运算

6.3 有穷集的计数

6.4 集合恒等式

第 7 章二元关系

7.1 有序对与笛卡儿积

7.2 二元关系

7.3 关系的运算

7.4 关系的性质

7.5 关系的闭包

7.6 等价关系与划分

7.7 偏序关系

设 R 为非空集合 A 上的关系，如果 R 是自反的、反对称的和传递的，则称 R 为 A 上的偏序关系，记作 $\preceq$ ，设 $\preceq$ 为偏序关系，如果 $<x,y>\in \preceq$ ，则记作 $x\preceq y$ ，读作 x "小于等于" y

$\forall x,y\in A,x$ 与 y 可比 $\Leftrightarrow x\preceq y\vee y \preceq x$

设 R 为非空集合 A 上的偏序关系，如果 $\forall x,y\in A,x$ 与 y 都是可比的，则称 R 为 A 上的全序关系(或线序关系)

集合 A 和 A 上的偏序关系 $\preceq$ 一起称作偏序集，记作 $<A,\preceq>$

设 $<A,\preceq >$ 为偏序集， $\forall x,y\in A$ ，如果 $x\prec y$ 且不存在 $z\in A$ 使得 $x\prec z \prec y$ ，则称 y 覆盖 x

设 $<A,\preceq>$ 为偏序集， $B\subseteq A,y\in B$

(1) 若 $\forall x(x\in B\rightarrow y\preceq x)$ 成立，则称 y 为 B 的最小元

(2) 若 $\forall x(x\in B\rightarrow x\preceq y)$ 成立，则称 y 为 B 的最大元

(3) 若 $\forall x(x\in B\wedge x\preceq y \rightarrow x = y)$ 成立，则称 y 为 B 的极小元

(4) 若 $\forall x(x\in B\wedge y\preceq x \rightarrow x = y)$ 成立，则称 y 为 B 的极大元

设 $<A,\preceq>$ 为偏序集， $B\subseteq A,y\in A$

(1) 若 $\forall x(x\in B\rightarrow x\preceq y)$ 成立，则称 y 为 B 的上界

(2) 若 $\forall x(x\in B\rightarrow y\preceq x)$ 成立，则称 y 为 B 的下界

(3) 令 C={y | y 为 B 的上界}，则称 C 的最小元为 B 的最小上界或上确界

(4) 令 D={y | y 为 B 的下界}，则称 D 的最大元为 B 的最大下界或下确界

第 8 章函数

8. 1 函数的定义与性质

8.2 函数的复合与反函数

8.3 双射函数与集合的基数

8.4 一个电话系统的描述实例

第 9 章代数系统

9. 1 二元运算及其性质

9.2 代数系统

9.3 代数系统的同态与同构

第 10 章群与环

10.1 群的定义及性质

(1) 设 $V=<S,\circ>$ 是代数系统， $\circ$ 为二元运算，如果 $\circ$ 是可结合的，则称 b 为半群

(2) 设 $V=<S,\circ>$ 是半群，若 $e\in S$ 是关于 $\circ$ 运算的单位元，则称 V 是幺半群，也称作独异点，有时也将独异点 V 记作 $V=<S,\circ,e>$

(3) 设 $V=<S,\circ>$ 是独异点， $e\in S$ 是关于 $\circ$ 运算的单位元，若 $\forall a\in S$ ，有 $a^{-1}\in S$ ，则称 V 是群，通常将群记作 G

10.2 子群与群的陪集分解

设 H 是群 G 的子群， $a\in G$ ，令 $Ha=\{ha|h\in H\}$ ，称 Ha 是子群 H 在 G 中的右陪集，称 a 为 Ha 的代表元素

一般说来，对于群 G 的子群 H 和元素 a，不能保证 Ha = aH，如果对于所有的 $a\in G$ 都有 aH = Ha，那么称 H 为 G 的正规子群或不变子群，记作 $H\trianglelefteq G$

任何群 G 都有正规子群，因为它的两个平凡子群 {e} 和 G 都是正规的

由于 H 在 G 中的右陪集数和左陪集数相等，今后不再区分右陪集数和左陪集数，而统称 H 在 G 中的陪集数，也称作 H 在 G 中的指数，记作 [G: H]

拉格朗日定理

设 G 是有限群，H 是 G 的子群，则 $|G|=|H|\cdot [G:H]$

10.3 循环群与置换群

若存在 $a\in G$ 使得 $G=<a>$ ，则称 G 为循环群，称 a 为 G 的生成元

循环群 $G=<a>$ 根据生成元 a 的阶可以分成两类：n 阶循环群和无限循环群

设 $G=<a>$ 是循环群，若 a 是 n 阶元，则

那么 $|G|=n$ ，称 G 为 n 阶循环群

若 a 是无限阶元，则

这时称 G 为无限循环群

设 $S=\{1,2,\cdots,n \}$ ，S 上的任何双射函数 $\sigma :S\rightarrow S$ 称为 S 上的 n 元置换，一般将 n 元置换 $\sigma$ 记作

例如， $S=\{1,2,3,4,5\}$ ，则

都是 5 元置换

设 $\sigma, \tau$ 是 n 元置换， $\sigma$ 和 $\tau$ 的复合 $\sigma \circ \tau$ 也是 n 元置换，称作 $\sigma$ 和 $\tau$ 的乘积，记作 $\sigma \tau$

例如，上面的 5 元置换 $\sigma$ 和 $\tau$ 有

设 $\sigma$ 是 $S=\{1,2,\cdots,n\}$ 上的 n 元置换，若

且保持 S 中的其他元素不变，则称 $\sigma$ 为 S 上的 k 阶轮换，记作 $(i_1i_2\cdots i_k)$ ，若 k = 2，称 $\sigma$ 为 S 上的对换

10.4 环与域

设 $<R,+,\cdot>$ 是代数系统，+ 和 • 是二元运算，如果满足以下条件：

(1) $<R,+>$ 构成交换群；

(2) $<R,\cdot>$ 构成半群；

(3) • 运算关于 + 运算适合分配律，

则称 $<R,+,\cdot>$ 是一个环。

第 11 章格与布尔代数

11.1 格的定义与性质

设 $<S, \preceq >$ 是偏序集，如果 $\forall x,y\in S,\{x,y\}$ 都有最小上界和最大下界，则称 S 关于偏序 $\preceq$ 作成一个格

由于最小上界和最大下界的唯一性，可以把求 $\{x,y\}$ 的最小上界和最大下界看成 x 与 y 的二元运算 V 和 $\wedge$ ，即 $x\vee y$ 和 $x\wedge y$ 分别表示 x 与 y 的最小上界和最大下界

设 f 是含有格中元素以及符号 $=,\preceq ,\succeq ,\vee$ 和 $\wedge$ 的命题，令 $f^*$ 是将 f 中的 $\preceq$ 替换成 $\succeq$ ， $\succeq$ 替换成 $\preceq$ ，V 替换成 $\wedge$ ， $\wedge$ 替换成 V 所得到的命题，称 $f^*$ 为 f 的对偶命题