第十章 格与布尔代数 10.1 格的定义与性质 1.定义 与群，环，域，不同，格与布尔代数的基集都是一个偏序集，格是具有两个二元运算的代数系统，是一个特殊的偏序集，布尔代数是一个特殊的格。 定义10.1：设<S, ≤>是偏序集，若 都有上下确界，则称<S, ≤>为格(Lattice) (1)偏序集的任一子集并非都有上下确界，

Presentation on theme: "第十章 格与布尔代数 10.1 格的定义与性质 1.定义 与群，环，域，不同，格与布尔代数的基集都是一个偏序集，格是具有两个二元运算的代数系统，是一个特殊的偏序集，布尔代数是一个特殊的格。 定义10.1：设<S, ≤>是偏序集，若 都有上下确界，则称<S, ≤>为格(Lattice) (1)偏序集的任一子集并非都有上下确界，"— Presentation transcript:

1 第十章 格与布尔代数 10.1 格的定义与性质 1.定义 与群，环，域，不同，格与布尔代数的基集都是一个偏序集，格是具有两个二元运算的代数系统，是一个特殊的偏序集，布尔代数是一个特殊的格。 定义10.1：设<S, ≤>是偏序集，若 都有上下确界，则称<S, ≤>为格(Lattice) (1)偏序集的任一子集并非都有上下确界， (2)偏序集的某一子集的上下确界若存在，则唯一，格的定义确定了上下确界的存在性， (3){x, y}的上确界记为x∨y，下确界记为x∧y

2 10.1 格的定义与性质 定义10.2：设f是含有格中元素及符号=, ≤,≥, ∨, ∧的命题，令 是将f中≤,≥, ∨, ∧分别替换为≥, ≤,∧,∨所得到的命题，则称 是f的对偶命题或称对偶式。 格的对偶原理：若f对一切格为真，则 也对一切格为真。 例： 定理10.1：设<L, ≤>是格，则运算∨, ∧满足交换律，结合律，幂等律，吸收律，即

3 10.1 格的定义与性质

4 10.1 格的定义与性质 由定理10.1知，格的两个运算满足交换律，结合律，幂等律，因此可以考虑用带有这4条性质的2个二元运算∨, ∧，来像群，环，域，一样定义格，即用<L, ∨, ∧ >来定义格，可以证明这是可行的。 定理10.2：设<S,*,ο>是具有二个二元运算的代数系统，且*,ο运算满足交换律，结合律，吸收律，则可以适当定义S中的偏序≤，使得<S,≤>构成一个格，

5 10.1 格的定义与性质

6 10.1 格的定义与性质

7 10.1 格的定义与性质 由定理10.1,10.2可知：

8 10.1 格的定义与性质 2.性质 因此，根据定理10.1，10.2，可以用代数系统的方式来定义格。
定义10.3：设<S,*,ο>是代数系统， *,ο是二元运算且满足交换律，结合律，吸收律(幂等律)，则<S,*,ο>构成一个格。 2.性质 定理10.3：设<L, ≤>是格，则 ，有

9 10.1 格的定义与性质

10 10.1 格的定义与性质

11 10.2 子格与格同态 1.子格 定义10.4：设代数系统<L,*,ο>是一个格， ，若S满足： ，则称<S,*,ο>是<L,*,ο>的子格。 定义10.5：设<L, ≤>是一个格， ，若S满足： ，则称<S,≤>是<L,≤>的子格。 例10-1：(1)设<L, ≤>是一个格，其中L={a,b,c,d,e}，其哈斯图如右图。 a b c d e

12 10.2 子格与格同态 2.格同态 定义10.6：设 和 是格， ，若 有 ，则称 为格 到 的同态映射，简称格同态，若 是双射，则称 为格同构。 定义10.7：设 和 是格，其中 分别为格 上的偏序关系，存在映射 ，若 ，称f是序同态，若f是双射，则称f是序同构。 (格同态定理)定理10.4：(1)设 是格 到格 的同态，则 是序同态，即同态是保序的，即

13 10.2 子格与格同态 (2) 是双射，则 是 到 的同构的充要条件是

14 10.2 子格与格同态 例10-2：在同构意义下：具有1，2，3个元素的格分别同构于元素个数相同的链，4个元素的格必同构于下图4元素格之一，5个元素的格必同构于下图5元素格之一 (1) (2) (7) 五角格 (8) 钻石格 (5) (3) (9) (10) (4) (6)

15 10.2 子格与格同态 定义10.8：设 和 是格，定义 上的二元运算 ：对 ，有： 则称 为 和 的直积。
定义10.8：设 和 是格，定义 上的二元运算 ：对 ，有： 则称 为 和 的直积。 直积仍是格(证明满足交换，结合，吸收律即可)

16 10.3 特殊格 1.分配格 一般来说，对格 ，有 ，则 定义10.9：设 是格，若 ，有 则称L为分配格。 例：(1) (2) 是 非 非
一般来说，对格 ，有 ，则 定义10.9：设 是格，若 ，有 则称L为分配格。 例：(1) (2) 是 非 非 是

17 10.3 特殊格 定理10.5：L是格，则L是分配格<=>L中不含有与钻石格或五角格同构的子格。
推论：(1)小于五元的格都是分配格；(2)任何一条链都是分配格。 (分配格的性质)定理10.6：若L是格，则L是分配格当且仅当

18 10.3 特殊格 命题条件 同时成立，否则不正确。 反例：分配格 中：

19 10.3 特殊格 2.模格 定义10.10：设 是格，若 ，有： (模律)，则称 为模格，也称为戴德金格。
定义10.10：设 是格，若 ，有： (模律)，则称 为模格，也称为戴德金格。 定理10.7：格L是模格的充要条件是它不含有同构于五角格的子格。 定理10.8：设 为分配格，则 是模格

20 10.3 特殊格 3.有界格 定义10.11：设L是格，若存在 ，使得 ，有 ，则称a为L的全下界，若存在 ，使得 ，有 ，则称b为L的全上界。 (1):有限格 一定是有界格，全下界 ，全上界 ； (2):无限格可以为有界格，如 全下界 ，全上界B； (3):全上界，全下界唯一，分别记为1和0 定义10.12：设L是格，若L存在全上界和全下界，则称L为有界格，记为

21 10.3 特殊格 定理10.9：设 为有界格，则 ，有 4.有补格 定义10.13：设 是有界格， ，若存在 ，使得 且 ，则称b是a的补元。 补元的性质：(1):补元素相互的；(2):并非有界格的每个元素都有补元，而有补元也不一定唯一；(3):0，1互为补元，且唯一。

22 10.3 特殊格 定理10.10：设 是有界分配格，若 且对于a存在补元b，则b是a的唯一补元。 定义10.14：设 是有界格，若
定理10.10：设 是有界分配格，若 且对于a存在补元b，则b是a的唯一补元。 定义10.14：设 是有界格，若 在L中都有a的补元存在，则称L是有补格。

23 10.4 布尔代数 1.概念 定义10.15：如果一个格是有补分配格，则称它为布尔代数。
有补格保证每个元素有补元，分配格保证每个元素的补元的唯一性，因此，可将求补元看作是布尔代数的一元运算，即 例： 定理10.11：设 是布尔代数，则

24 10.4 布尔代数 布尔代数：交换律，结合律，吸收律，分配律，存在补元，可用交换律，分配律，同一律，补元律代替。另一等价定义：
定义10.16： 是代数系统， 是二元运算，且 满足：(1)交换律，(2)分配律，(3)同一律：存在 (4)补元律： 则称 是布尔代数。

25 10.4 布尔代数 (1):∧:幺元为1；∨：幺元为0(同一律)。可证： ∧:零元为0；∨：零元为1。 (2):吸收律成立。 结合律成立。

26 10.4 布尔代数 2.子布尔代数 定义10.17：设 是布尔代数， ，若 ，且S对∧，∨，’封闭，则称S是B的子布尔代数。

27 10.4 布尔代数 1 (2) 定理10.12(判定定理)：设 是布尔代数， ，若 ，则S是B的子布尔代数，记作 a c b d f e

28 10.4 布尔代数 3.布尔代数的同态 4.有限布尔代数的结构 定义10.18：设 和 是两个布尔代数， ，若 ，有：
定义10.18：设 和 是两个布尔代数， ，若 ，有： 则称 为 到 的布尔同态，若 为双射，则为布尔同构。 4.有限布尔代数的结构 定义10.19：设L是格，若a是0的覆盖，则称a是L中的原子，即： 定理10.13：设 是布尔代数，B中元素a是原子的充要条件是a≠0，且对 ，有：

29 10.4 布尔代数 定理10.14：设L是格，a，b是L中的原子，若a≠b，则a∧b=0。
定理10.15：设B是有限布尔代数， ，令 是B中所有≤x的原子构成的集合( )，则：

30 10.4 布尔代数

31 10.4 布尔代数

32 10.4 布尔代数 定理10.16(有限布尔代数的表示定理)：设 是有限布尔代数，A={a|a∈B且a是原子}，则

33 10.4 布尔代数

34 10.4 布尔代数 推论1：任何有限布尔代数的基数为 推论2：任何具有 个元素的布尔代数互相同构(对无限布尔代数不成立)

35 10.4 布尔代数 5.布尔表达式 定义10.20：设 是一个布尔代数，B中的元素称为布尔常元，取值于B中元素的变元称为布尔变元。
(3).如果 是布尔表达式，则 也是布尔表达式； (4).有限次使用(1)，(2)，(3)所构造的符号串是布尔表达式。

36 10.4 布尔代数 定义10.22：设 是一个布尔代数，B的一个含有n个相异布尔变元的布尔表达式称为n元布尔表达式，记为 ，其中
是布尔变元。 定义10.23：设 和 是布尔代数 上的两个布尔表达式，如果对n个布尔变元的任意指派， 和 的值均相等，则称 与 是等价的或相等的，记作： (1).如果能有限次应用布尔代数的公式，将一个布尔表达式化成另一个布尔表达式，就可判定两式是等价的；

37 10.4 布尔代数 (2).等价关系将n元布尔表达式集合划分成等价类，同一等价类中的布尔表达式等价，等价类数目有限。
( )，称为极小项。 (1).n个布尔变元就有 个不同的极小项，分别记为 ，下标是二进制数 的十进制表示，其中

38 10.4 布尔代数 (2). (3). 定义10.25：设 是布尔代数，如 的布尔表达式称为主析取范式，其中 是布尔常元， 是极小项( ).
定义10.25：设 是布尔代数，如 的布尔表达式称为主析取范式，其中 是布尔常元， 是极小项( ). (1).每个 有|B|种取法，故有n个布尔变元的不同的主析取范式有 个，当B={0,1}时有 个; (2). 个极小项，最多能构造出 个主析取范式，所以一个n元布尔表达式必等价于这 个主析取范式之一； (3).可用数理逻辑中的方法，用德摩根律等将一

39 10.4 布尔代数 个n元布尔表达式转化为等价的主析取范式； (4).相应的：极大项： 主合取范式为：
是布尔常元， 是极大项，同样有 个不同的主合取范式， 个极大项最多能构造 个不同的主合取范式。 例：将布尔代数 上的布尔表达式 化为主析取范式和主合取范式

40 10.4 布尔代数

41 10.4 布尔代数 定义10.26：设 是一个格，一个从 到B的函数，如果能够用该布尔代数上的布尔表达式来表达，则称这个函数为布尔函数。
(1).每一个n元布尔表达式可以看作是一个n个布尔变元的函数； (2).n个变元的主析取范式最多有 个，∴只能代表 个不同的函数， 到|B|的函数共有 个； 当B={0,1}时，函数有 个，主析取范式 个，每个函数均可用布尔表达式表示，当B≠{0,1}时，如B={0,1,a,b}时，函数有 个，主析取范式有 个，即当|B|>2时，有些 到B的函数不能用布尔表达式表示。

42 10.4 布尔代数 (3).命题逻辑可以用布尔代数 来描述，开关代数可以用布尔代数<{断开，闭合}，并联，串联，反向>来描述。