离散数学

（1）

任何两个元素都有最小上界和最大下届的偏序集称为格，也称为偏序格。

（2）

最小上界：∨(保联运算)，LUB，sup

最大下界：∧(保交运算)，GLB，inf

（3）

设〈𝐿, ≤〉是格,≥是≤的逆关系,则格〈𝐿, ≥〉称 为格〈𝐿, ≤〉的对偶格(互为对偶格)。

关系≤ 和关系≥称为互为对偶的关系.

定理:

若〈𝐿, ≤〉是一个格,则〈𝐿, ≥〉也是一个 格,

且格〈𝐿, ≥〉中的保联运算和保交运算( 用⨁和⨂表示)

与格〈𝐿, ≤〉中的保联运算和保交运算（用∨和∧表示）

满足a∨b=a⨂b,a∧b=a⨁b

注释：就是运算意义交叉等价

（4）

定义:

一个由格〈𝐿, ≤〉中的元素以及符号∨ ,∧, =和≤所组成的命题𝑃的对偶命题是指 命题𝑃 ∗ ,它是将𝑃中的≤换为≥,∨换为∧,∧换 为∨所得到的命题.

对偶原理：

对于格〈𝐿, ≤〉中的任一真 命题𝑃,其对偶命题𝑃 ∗ 也是真命题.

（5）

定理:

设〈𝐿, ≤〉为格,则对L中任何元素𝑎,𝑏和 𝑐有:

(1)𝑎 ≤ 𝑎 ∨ 𝑏, 𝑏 ≤ 𝑎 ∨ 𝑏, 𝑎 ∧ 𝑏 ≤ 𝑎, 𝑎 ∧ 𝑏 ≤ 𝑏

(2)若𝑎 ≤ 𝑏, 𝑎 ≤ 𝑐,则:𝑎 ≤ 𝑏 ∧ 𝑐. 若𝑎 ≤ 𝑐, 𝑏 ≤ 𝑐,则:𝑎 ∨ 𝑏 ≤ 𝑐.

(3)若𝑎 ≤ 𝑏, 𝑐 ≤ 𝑑,则:𝑎 ∨ 𝑐 ≤ 𝑏 ∨ 𝑑, 𝑎 ∧ 𝑐 ≤ 𝑏 ∧ 𝑑.

(4)若𝑏 ≤ 𝑐,则:𝑎 ∨ 𝑏 ≤ 𝑎 ∨ 𝑐, 𝑎 ∧ 𝑏 ≤ 𝑎 ∧ 𝑐.

（6）

定理:

设〈𝐿, ≤〉为格,那么对𝐿中任何元素𝑎,𝑏 和𝑐,以下定律成立.

(1)幂等律 𝑎 ∨ 𝑎 = 𝑎, 𝑎 ∧ 𝑎 = 𝑎

(2)交换律 𝑎 ∨ 𝑏 = 𝑏 ∨ 𝑎, 𝑎 ∧ 𝑏 = 𝑏 ∧ 𝑎

(3)结合律 (𝑎 ∨ 𝑏) ∨ 𝑐 = 𝑎 ∨ (𝑏 ∨ 𝑐), (𝑎 ∧ 𝑏) ∧ 𝑐 = 𝑎 ∧ (𝑏 ∧ 𝑐)

(4)吸收律 𝑎 ∨ (𝑎 ∧ 𝑏) = 𝑎,𝑎 ∧ (𝑎 ∨ 𝑏) = 𝑎

（7）

定理:

设〈𝐿, ≤〉为格,则对L中任何元素𝑎和𝑏,

有 𝑎 ≤ 𝑏 ⇔ 𝑎 ∧ 𝑏 = 𝑎 ⇔ 𝑎 ∨ 𝑏 = 𝑏.

（8）

定理:

设〈𝐿, ≤〉为格,则对𝐿中任何元素𝑎,𝑏和 𝑐,有:

(1)𝑎 ∨ (𝑏 ∧ 𝑐) ≤ (𝑎 ∨ 𝑏) ∧ (𝑎 ∨ 𝑐).

(2)𝑎 ∧ (𝑏 ∨ 𝑐) ≥ (𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐).

其中关系≥是关系≤的对偶关系.

（9）

定理: 设〈𝐿, ≤〉为格,那么对𝐿中任何元素 𝑎,𝑏和𝑐,

有:𝑎 ≤ 𝑐 ⇔ 𝑎 ∨ (𝑏 ∧ 𝑐) ≤ (𝑎 ∨ 𝑏) ∧ 𝑐.

（1）

定义:设〈𝐿,∨,∧〉(或〈𝐿,∧,∨〉)是代数系统,

∨和 ∧是𝐿上的两个二元运算,如果这两个运算 对𝐿中的元素满足:

(1)交换律 𝑎 ∨ 𝑏 = 𝑏 ∨ 𝑎, 𝑎 ∧ 𝑏 = 𝑏 ∧ 𝑎

(2)结合律 (𝑎 ∨ 𝑏) ∨ 𝑐 = 𝑎 ∨ (𝑏 ∨ 𝑐), (𝑎 ∧ 𝑏) ∧ 𝑐 = 𝑎 ∧ (𝑏 ∧ 𝑐)

(3)吸收律 𝑎 ∨ (𝑎 ∧ 𝑏) = 𝑎, 𝑎 ∧ (𝑎 ∨ 𝑏) = 𝑎

则称代数系统〈𝐿,∨,∧〉是格.也称这样定义的格为代数格.

（2）

定理:

由代数系统定义的格和由偏序集定义的格是等价的.

亦即,一个代数格必是一个偏序格;一个偏序格必是一个代数格.

（1）

定义1:

设〈𝐿,∨,∧〉是格,𝑆是𝐿的非空子集,

如果 〈𝑆,∨,∧〉仍构成一个格,则称〈𝑆,∨,∧〉是〈𝐿,∨,∧〉 的子格.

定义2:

设〈𝐿,∨,∧〉是格,𝑆是𝐿的非空子集,

若对 𝑆中的任意元素𝑎和𝑏,有:

(1)𝑎 ∨ 𝑏 ∈ 𝑆

(2)𝑎 ∧ 𝑏 ∈ 𝑆

则称〈𝑆,∨,∧〉是〈𝐿,∨,∧〉的子格.

定义3:

设〈𝐿, ≤〉是格,𝑆是𝐿的非空子集,

若对于任意𝑎, 𝑏 ∈ 𝑆,{𝑎, 𝑏}在𝐿中求得的最小上界𝑎 ∨ 𝑏和最大下界𝑎 ∧ 𝑏仍在𝑆中,

则称〈𝑆,≤〉是〈𝐿,≤〉 的子格.

注意：

子格必是格.

因为当运算限制在S上时，交换律，结合律和吸收律也是成立的。

（1）

定义:

设〈𝐿,∨,∧〉和〈𝑆, ⨁, ⨂〉是两个格,

若存在映射f:𝐿 → 𝑆,使对∀𝑎, 𝑏 ∈ 𝐿,有:

𝑓(𝑎 ∨ 𝑏) = 𝑓(𝑎)⨁𝑓(𝑏)

𝑓(𝑎 ∧ 𝑏) = 𝑓(𝑎)⨂𝑓(𝑏)

则称𝑓是〈𝐿,∨,∧〉到〈𝑆, ⨁, ⨂〉的格同态映射, 简称同态映射。

注意：

若𝑓是单射,满射或双射时,则称𝑓分别是单同态映射,满同态映射和同构映射。

特别地,〈𝐿,∨,∧〉到〈𝐿,∨,∧〉的格同态映射称为自同态映射;

〈𝐿,∨,∧〉到〈𝐿,∨,∧〉的格同构映射称为自同构映射.

若〈𝐿,∨,∧〉到〈𝑆, ⨁, ⨂〉存在同构映射,则称 〈𝐿,∨,∧〉和〈𝑆, ⨁, ⨂〉是同构的.

同构的两个格其哈斯图是相同的.

（2）

定义:

设〈𝐿, ≤l 〉和〈𝑆, ≤s 〉是两个格,

若存在映射𝑓: 𝐿 → 𝑆,使对𝐿中任意元素𝑎,𝑏，

当 𝑎 ≤l 𝑏时,有 𝑓(𝑎) ≤s 𝑓(𝑏),

则称𝑓是〈𝐿, ≤l 〉 到〈𝑆, ≤s 〉的格保序映射(序同态映射),简称保序映射.

定理:

设〈𝐿, ≤l 〉和〈𝑆, ≤s 〉是两个格

映射𝑓: 𝐿 → 𝑆,

如果𝑓是〈𝐿,∨,∧〉到〈𝑆, ⨁, ⨂〉 同态映射,则𝑓是保序映射.

即对任意𝑎, 𝑏 ∈ 𝐿,

若𝑎 ≤l 𝑏,有: 𝑓(𝑎) ≤s 𝑓(𝑏).

其中:≤l 是集合𝐿上对应于运算∨和∧的偏序关系,

≤s 为集合𝑆上对应于运算⨁和⨂的偏序关系.

（1）

定义:

设〈𝐿,∨,∧〉是一个格,若∨对∧, ∧对∨均 满足分配律,

即对任意𝑎, 𝑏, 𝑐 ∈ 𝐿,有:

𝑎 ∨ (𝑏 ∧ 𝑐) = (𝑎 ∨ 𝑏) ∧ (𝑎 ∨ 𝑐)

𝑎 ∧ (𝑏 ∨ 𝑐) = (𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑐)

则称〈𝐿,∨,∧〉是分配格.

（2）

定理:

在格〈𝐿,∨,∧〉中,

如果保交运算∧运算对保联运算∨是可分配的,

那么保联运算∨ 对保交运算∧也一定是可分配的.

反之亦然。

（3）

定理:

设〈𝐿,∨,∧〉是分配格,

对于任意的 𝑎, 𝑏, 𝑐 ∈ 𝐿,若:

𝑎 ∧ 𝑏 = 𝑎 ∧ 𝑐, 𝑎 ∨ 𝑏 = 𝑎 ∨ 𝑐 成立,

则𝑏 = 𝑐.

证明:

因为(𝑎 ∧ 𝑏) ∨ 𝑐

= (𝑎 ∧ 𝑐) ∨ 𝑐

= 𝑐

而:

(𝑎 ∧ 𝑏) ∨ 𝑐

= (𝑎 ∨ 𝑐) ∧ (𝑏 ∨ 𝑐)

= (𝑎 ∨ 𝑏) ∧ (𝑏 ∨ 𝑐)

= 𝑏 ∨ (𝑎 ∧ 𝑐)

= 𝑏 ∨ (𝑎 ∧ 𝑏)

= 𝑏

因此有𝑏 = 𝑐.

（4）

定理:

格〈𝐿,∨,∧〉是分配格的充分必要条件是:

〈𝐿,∨,∧〉中不含有与钻石格和五角格同构的子格.

（1）

定义:

对于格〈𝐿,∨,∧〉,若𝐿中的元素个数有限,则称〈𝐿,∨,∧〉为有限格.

（2）

定义:

对于格〈𝐿,∨,∧〉,

若存在一个元素𝑎 ∈ 𝐿,对于∀𝑥 ∈ 𝐿,都有𝑥 ≤ 𝑎(𝑎 ≤ 𝑥),

则称𝑎是 格𝐿的一个最大(最小)元.

如果一个格存在最小元和最大元,则称它们是格的界,

分别用𝟎和𝟏来表示最小元和最大元.

（3）

定义:

如果一个格同时存在最小元和最大元,则称该格为有界格.

注意：

有限格都是有界格。

（4）

定理:设〈𝐿,∨,∧〉是有界格,

则对任意的𝑎 ∈ 𝐿, 必有:

(1)𝑎 ∨ = 𝟏,𝑎 ∧ 𝟏 = 𝑎

(2)𝑎 ∨ 𝟎 = 𝑎,𝑎 ∧ 𝟎 = 𝟎

（5）

定义:

设〈𝐿,∨,∧〉是有界格,

对于𝐿中的一元 素𝑎，

若存在𝑏 ∈ 𝐿,使得𝑎 ∨ 𝑏 = 𝟏,𝑎 ∧ 𝑏 = 𝟎,

则称𝑏为𝑎的补元.

（6）

补元有下列特点:

(1)补元是相互的,即𝑏是𝑎的补元,那么𝑎也是𝑏 的补元;

(2)𝟎和𝟏互为补元;

(3)并非有界格中每个元素都有补元,即使存在也未必是唯一的.

（7）

定义:

在一个有界格〈𝐿,∨,∧〉中,如果𝐿中每个元素都有补元,则称此格为有补格.

（8）

定理:

有补格〈𝐿,∨,∧〉中元素𝟎和𝟏的补元是唯一的.

（9）

定义:

如果一个格既是有补格又是分配格, 则称它为有补分配格.

（10）

定理:

有补分配格中每一元素的补元都是唯一的

证明:

反证法：

设〈𝐿,∨,∧〉是有补分配格,𝑎是𝐿中 的一元素,

假设它有两个补元𝑏和𝑐,那么有:

𝑎 ∨ 𝑏 = 𝟏, 𝑎 ∧ 𝑏 = 𝟎

𝑎 ∨ 𝑐 = 𝟏, 𝑎 ∧ 𝑐 = 𝟎

即:𝑎 ∨ 𝑏 = 𝑎 ∨ 𝑐,𝑎 ∧ 𝑏 = 𝑎 ∧ 𝑐.

根据分配格的性质,有𝑏 = 𝑐.

所以𝑎的补元 是唯一的.

有补分配格中任一元素𝑎的唯一补元可用 ∼ 𝑎(或𝑎' )来表示.

（11）

定理:

对有补分配格中每一元素𝑎,有 (𝑎')'= 𝑎.(对合律)

（12）

定理:

设〈𝐿,∨,∧〉是有补分配格,

则对𝐿中任 意元素𝑎和𝑏,有

(1)(𝑎 ∨ 𝑏)'= 𝑎'∧ 𝑏'

(2)(𝑎 ∧ 𝑏)' = 𝑎' ∨ 𝑏'

(德·摩根律)

（13）

定理:

对有补分配格的任何元素𝑎和𝑏,有:

𝑎 ≤ 𝑏 ⇔ 𝑎 ∧ 𝑏' = 𝟎

𝑎 ∧ 𝑏' = 0 ⇔ 𝑎' ∨ 𝑏 = 1

（1）

定义:

一个有补分配格称为布尔代数

（2）

在有补分配格中,因为每一个元素𝑎都有唯一的补元𝑎 ' ,

所以可定 义一个一元运算' ,

使得𝑎 ' 为𝑎的补元,

这个一元运算称为补运算

（3）

布尔代数一般用〈𝐵,∨,∧,' 〉或〈𝐵,∨ ,∧,' , 𝟎, 𝟏〉来表示.

（4）

定义:

具有有限个元素的布尔代数称为有限布尔代数.

（5）

定义:

设〈𝐵,∨,∧,' , 𝟎, 𝟏〉是布尔代数,𝐴 ⊆ 𝐵且非空,

若〈𝐴,∨,∧,' , 𝟎, 𝟏〉也是布尔代数,

则称 〈𝐴,∨,∧,' , 𝟎, 𝟏〉是〈𝐵,∨,∧,' , 0,1〉的子(布尔)代数.

（6）

定理:

设〈𝐵,∨,∧,' , 𝟎, 𝟏〉为布尔代数,𝐴 ⊆ 𝐵且 𝐴含有元素𝟎和𝟏,

若𝐴对运算∨,∧和' 封闭,

那 么〈𝐴,∨,∧,' , 𝟎, 𝟏〉为〈𝐵,∨,∧,' , 𝟎, 𝟏〉的子代数.

（7）

定义:设〈𝐴,∨,∧,' , 𝟎, 𝟏〉和〈𝐵,∨,∧,' , 𝟎, 𝟏〉是两 个布尔代数,

如果存在𝐴到𝐵的函数𝑓,使得对于任意的𝑎, 𝑏 ∈ 𝐴,都有:

𝑓(𝑎 ∨ 𝑏) = 𝑓(𝑎) ∨ 𝑓(𝑏)

𝑓(𝑎 ∧ 𝑏) = 𝑓(𝑎) ∧ 𝑓(𝑏)

𝑓(𝑎') = (𝑓(𝑎))'

则称𝑓是布尔代数〈𝐴,∨,∧,' , 𝟎, 𝟏〉到布尔代 数〈𝐵,∨,∧,' , 𝟎, 𝟏〉的同态(映射).

注意：

若𝑓是单射的,则称为单同态;

若𝑓是满射的,则称为满同态;

若𝑓是双射的,则称为同构;

若存在同构映射f,则称布尔代数〈𝐴,∨,∧ ,' , 𝟎, 𝟏〉和布尔代数〈𝐵,∨,∧,', 𝟎, 𝟏〉同构。