离散数学第7章格

第7章格和布尔代数

7.1偏序集7.2格及其性质7.4分配格和有补格7.3格是一种代数系统7.5布尔代数

7．1偏序集

1.偏序集

定义7-1

集合L和定义在L

上的偏序关系“≤”一起称为偏序集，用<L；≤>表示.若是集合A上的偏序关系，则的逆关系也必是A上的偏序关系，证明如下：例如<R；≤>，<I：≤>，<2U；>和<N；|>都是偏序集.１．对任意的a

A，因为自反，所以有（a,a）,于是（a,a），因此也是自反的；２．对任意a,b

A

，若（a,b）且（b,a），则有（b,a）且（a,b），必有a=b，因此是反对称的；３．对任意a,b,c

A,若（a,b）,(b,c），则有（c,b）且（b,a），必有（c,a），于是（a,c），因此是可传递的。由上证得也是偏序关系.

由定义=

例1

设A=，定义A

上的整除关系：当旦仅当a

整除b

时，有.

的次序图如下的次序图如下

61362231根据逆关系的定义

=

l1

≤l1(7-1)若l1

≤l2,

l2≤l1,则l1=l2

(7-2)若l1

≤l2,

l2≤l3,则l1≤l3(7-3)若<L；≤>是一个偏序集，则对于任意元素

l1,l2,l3

L，有以下六个关系式成立：

l1

≥l1(7-1')若l1

≥l2,

l2≥l1,则l1=l2

(7-2')若l1

≥l2,

l2≥l3,则l1≥l3(7-3')如果元素a是l1和l2的下界,且对于任意a'

L，若a'也是l1和l2的下界，便有a'≤a,则称a是l1和l2的最大下界，简记作a=glb(l1,l2).如果元素b是l1和l2的上界,且对于任意b'

L，若b'也是l1和l2的上界，便有b≤b',则称b是l1和l2的最小上界，简记作b=lub(l1,l2).

2．最大下界和最小上界定义7-1

设l1和l2是偏序集<L；≤>中的两个元素,元素a

L，如果满足a≤

l1,a≤l2,则称a是l1和l2的下界.

定义7-2

设l1和l2是偏序集<L；≤>中的两个元素,元素b

L，如果满足l1≤b,l2≤b,则称b是l1和l2的上界.

lub(2,3)=？glb(12,18)=?lub(18,27)=?有2≤6，3≤6；2≤12，3≤12；2≤18，3≤18。

由于6≤12，6≤18，6≤6，因此，lub（2，3）=6。

6≤12，6≤18；2≤12，2≤18；3≤12，3≤18；1≤12,1≤18；

因为1≤6，2≤6，3≤6，所以glb(12,18)＝6.

例2

设A=“整除”关系是A上的偏序关系，其次序图如下，因此，它们构成一个偏序集<A；≤>.11812272369

试问glb(18,12)=?lub(2,3)=?2≤18，2≤12；3≤18，3≤12，1≤18，1≤12.

但glb(18,12)不存在.类似地，12，18和36均是2和3的上界，但lub（2，3）不存在.

例3

设A=，整除关系是A上的偏序关系，其次序图如下:

361812231

定理7-1

设l1和l2是偏序集<L；≤>的两个元素，如果l1和l2有glb,则glb是唯一的，如果l1和l2有lub，则lub是唯一的.

证明

设a1和a2都是l1和l2的glb，

由定义7-1,则a2≤a1,a1≤a2,于是有a1=a2.

类似地可以证明,l1和l2若存在lub，则lub也一定是唯一的.

定理7-2

如果偏序集<L；≤>有最小元素，则最小元素是唯一的.如果<L；≤>有最大元素，则最大元素也是唯一的.3最小元素和最大元素

定义7-3

设<L；≤>是一偏序集。

(1)如果存在元素a

L，使得对于所有的元素l

L，有a≤

l

，则称a是<L；≤>的最小元素；

证明

设和都是<L；≤>的最小元素，则有≤，且≤，得＝.

(2)如果存在元素b

L，使得对于所有的元素l

L，有l

≤

b，则称b是<L；≤>的最大元素.

60361283264由图可以看出：偏序集<J；≤>没有最大元素，也没有最小元素；另外，2和3没有下界，因而没有最大下界；8和12没有上界，因而没有最小上界.7．2格及其性质

1．格的定义定义7-4

设<L；≤>是一个偏序集，如果L中任意两个元素都存在着最大下界和最小上界，则称<L；≤>是格.因此<L；≤>是一个格意味着<L；≤>也是一个形为<L；˄,˅>的代数系统，其中˄和˅是L上的两个二元运算，l1˄

l2=glb(l1,

l2),l1˅

l2=lub(l1,

l2).对于任意l1，l2，l1˅

l2表示在偏序“≤”意义下，l1和l2的最小上界，l1˄

l2表示l1和l2的最大下界.在格上定义两个二元运算“˄”和“˅”如下：例5

试判断下列次序图给出的偏序集是不是格？解(1)是格;(2)是格.

fhgdebca(1)51210153630(2)例5

试判断下列次序图给出的偏序集是不是格？解

(3)不是格，efdcab(3)edbca(4)因为a和b没有最大下界;(4)不是格，因为d和e没有最小上界.

l1

≤l1(自反)(7-1)若l1

≤l2,

l2≤l1,则l1=l2

(反对称)(7-2)若l1

≤l2,

l2≤l3,则l1≤l3(传递)

(7-3)若<L；≤>是一个偏序集，则对于任意元素

l1,l2,l3

L，有以下六个关系式成立：

l1

≥l1(7-1')若l1

≥l2,

l2≥l1,则l1=l2

(7-2')若l1

≥l2,

l2≥l3,则l1≥l3(7-3')在格＜L；≤>中有如下四个关系式成立:

l1˄l2≤l1

，l1˄l2≤l2(7-4)若l3

≤l1,

l3≤l2,则l3≤l1˄l2

(7-5)

l1˅l2≥l1

，l1˅l2≥l2(7-4')若l3

≥l1,

l3≥l2,则l3≥l1˅l2

(7-5')2．格的性质

定理7-3

在格<L；≤>中，对于任意l1，l2

以下三式中若任意一式成立，那么其它两式也成立.51210153630例(1)l1˅l2=l2;(2)l1˄l2=l1;(3)l1≤l2.

定义

设<L；≤>是格，P是包含格的元素和符号=、≤、≥，∧，∨的关系式，

例如关系式P:

(l1˅l2)˄l3

对偶原理：

对于格<L，≤>上的任一真命题P，其对偶PD亦为格<L，≤>上的真命题.

PD:

(l1˄l2)˅l3

对偶关系式将P中的≤、≥，∧和∨分别替换成≥、≤、∨和∧所得的关系式PD称为P的对偶.定理7-4（交换律）

设<L；≤>是格，则对任意的有:定理7-5

（结合律）设<L；≤>是格，则对任意的，有51210153630例

定理7-6

（等幂律）

设＜L；≤＞是格，则对任意，有定理7-7

（吸收律）设＜L；≤＞是格，则对任意

，有51210153630例

定理7-8

（格的保序性）设＜L；≤＞是格，则对于任意，有51210153630例

例6

设L=，L上的整除关系与L构成一个格，记作<L；≤>，3∨(6∧4)=3∨1=3,(3∨6)∧(3∨4)=6∧12=6,于是

3∨(6∧4)≠(3∨6)∧(3∨4).6∧(3∨4)=6∧12=6,(6∧3)∨(6∧4)=3∨1=3,

于是6∧(3∨4)≠(6∧3)∨(6∧4).126431

定理7-9

设<L；≤>是格，则对任意

,有(分配不等式)51210153630例7．3格是一种代数系统

定理7-10

设<L;∨,∧>是一个代数系统，其中∨和∧都是二元运算，这两个运算都满足交换律、结合律和吸收律，则在L上必存在一偏序关系≤

，使得<L

;≤

>是一个格.

可以证明关系≤是L上的自反，反对称和可传递的关系，因此≤是L上的偏序关系.故<L；

∨,∧

>是一个格.

证明

在L上定义二元关系：对任意l1

,l2

,当且仅当l1

∨

l2=l1时，有l2≤l1

.

进一步还可以证明，对任意l1

,l2，l1

∨

l2是在偏序关系≤意义下l1和l2的最小上界，l1

∧

l2是l1和l2的最大下界.

格既可以看作是一个偏序集<L；≤>，又可以看作是一个代数系统<L;∨,∧>.

定义7-5

设<L;∨,∧>是一个代数系统，∨和∧是L

上的两个二元运算，如果这两个运算满足交换律、结合律和吸收律，则称<L;∨,∧>是格.

-------格的另外定义

例7

在全集合U

的幂集2U

=上的包含关系“

”是2U

上的一偏序关系.

所以<2U；>是一偏序集.因为(1)对任意Si2U，总有Si

Si，所以是自反的;(2)对任意Si

,

Sj

2U

,若Si

Sj

，且Sj

Si

，则必有Si

=Sj

，所以是反对称的;

(3)

对任意Si,Sj

，Sk

2U，若Si

Sj

，Sj

Sk

，则必有Si

Sk，所以是可传递的.因此，Si∪Sj是Si和Sj的上界.

对于任意Si,Sj

2U，有Si

Si∪Sj，Sj

Si∪Sj，

则必有Si∪Sj

S.因此Si∪Sj是Si和Sj的最小界，即lub(Si，Sj)=Si∪Sj.

若有S2U，使得Si

S

，Sj

S，

类似地可以证明，对任意Si,Sj

2U,glb(Si，Sj)=Si∩Sj.另一方面，集合的并运算和交运算和2U构成代数系统<2U；∪,∩>，因为运算∪和∩都满足交换律，结合律和吸收律，因此<2U；∪,∩>是一个格.

因此<2U，>是一个格.

例6

设U={a,b,c}

则2U={φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}二、子格

定义7-6

设<L；∨,∧>是格，格：<2U；>，对应的代数系统是：<2U；∪，∩>.子格也是一个格.则称<T；∨,∧>是<L；∨,∧>的子格.若<T；∨,∧>是<L；∨,∧>的子代数，(1)若S1={{b},{a,b}{b,c},{a,b,c}},则<S1；∪，∩>是<2U；∪，∩>的子格;则<S2；∪，∩>也是<2U；∪，∩>的子格.

则S3不能与这两个运算构成<2U；∪，∩>的子格.φ{a,b,c}{a,c}{b,c}{a,b}{a}{c}{b}(2)若S2={φ,{a},{c},{a,c}},(3)若S3={φ,{a},{c},{a,b},{a,c},{b,c},{a,b,c}}26

112练习1．

设L={1，2，3，4，6，12}，在L上定义整除关系，构成偏序集<L;≤>.（1）glb(6,4)=

;lub(2,3)=

；（2）该偏序集的最小元素是

;最大元素是

.126432134110

（1）glb(6,9)=

;glb(8,12)=

；（2）glb(9,7)=;lub(5,10)=

.12

2．设L={1，2，3，…，11，12}，在L上定义整除关系，构成偏序集.8421105639711下面给出的三个次序图，其中哪些是格？在图下方相应的括号内键入“Y”或“N”表示肯定或否定.()()()NYYYYNN4．对下图所给出的格判断以下子集是否能构成它的子格，在相应的括号内键入“Y”或“N”来回答.（1）S1={e,c,b}()

（2）S2={d,b,a}()

（3）S3={c,d,b}()

（4）S4={c,d,a}()edcba

定义7-7

设<L；，>是一个格，若对于任意的l1,

l2,

l3∈L，有则称<L

；，>是分配格.7．4分配格和有补格一、分配格

1．分配格的定义dcbaecdbadbca

例1

对任意的集合A，<2A

；∪，∩>是一个分配格.

因此b∧(c∨d)≠（b∧c）∨（b∧d）

而(b∧c)∨(b∧d）ebcda例2

b∧(c∨d)

=b∧e=b=

a∨a

=a不是分配格.2．分配格中运算特点

定理7-11

在格<L；∨，∧>中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的；如果并运算对交运算是可分配的，则交运算对并运算也是可分配的.

证明设在格<L；，>中，对任意l1,

l2,

l3∈L，有

例如设L={1，2，4，16，32，64},定义在L上的整除关系≤与L构成一个链<L;≤>.

设<L;≤>是一个偏序集，若对于任意的l1,l2∈L，或者l1≤l2,

或者l2≤l1

,则称<L;≤>是一个链.643216421

例3

每一个链<L;≤>都是一个分配格.证明（1）先证明<L;≤>是一个格.

由链的定义，对于任意l1,l2∈L，或者l1≤l2,

或者l2

≤l1

.

若l1≤l2

，则glb(l1,l2)=l1,lub(l1,l2)=l2

;

所以<L;≤>是一个格，可将其表示为<L;∨,∧>.对任意l1,l2∈

L，l1∨l2

=lub(l1,l2),l1∧

l2

=glb(l1,l2).

若l2≤l1

，则glb(l1,l2)=l2,lub(l1,l2)=l1

.(2)

证明

<L；∨，∧>是一个分配格.对任意l1,l2,l3

∈L,必有l2

≤l3

或者l3

≤l2

，不妨设l2

≤l3.

于是有l1

∧(l2

∨l3)=l1

∧l3.又因为l1

∧l2

≤

l1

∧l3,所以(

l1

∧l2)

∨(l1

∧l3

)=l1

∧l3

,

因此l1

∧(l2

∨l3)=(

l1

∧l2)

∨(l1

∧l3

).若l3

≤l2

，其证明方法类似，因此链<L;≤>是一个分配格.

3．分配格的性质定理7-12

设l1,l2,l3是分配格<L；∨,∧>中的任意三个元素，那么证明

(1)若(2)反之，设则则显然当且仅当注意：

对于非分配格，定理7－12不成立.

c

d=c

b,c

d=c

b

，

但

b≠d.例如，edbca是非分配格二有补格<I；≤>是一个格，但这个格既无最小元素，又无最大元素.<N；≤>这个格有最小元素，但没有最大元素.例4

格<2U；>中无论U是什么样的集合，均有最小元素φ和最大元素U.具有最小元素和最大元素的格称为有界格.

在有界格<L；≤>中，对任意l，有l≤1，0≤l.于是由定理7-3，对任意，有

1．最小元素0和最大元素1用0表示最小元素，用1表示最大元素.2．补元素

定义7-8

设<L；∨,∧>是一个有界格，

l

∈

L，若存在元素

∈

L，使得l∨

=1

l∧=0，则称是l的补元素.

注意：在任一有界格中0和1互为补元素.例51abcd01abcdeg0f

因为对任意S∈2U，所以S的补集是S的补元素.

例6

格是一个有补格，3．有补格定义7-9

设<L；∨,∧>是一个有界格，如果L中每一个元素都有补元素，则称<L；∨,∧>是有补格.注意：

(1)

有补格中元素的补元素不唯一;例如，edbca非分配格(2)

有补格不一定是分配格；(3)

分配格不一定是有补格；例7

是有补分配格.三、有补分配格

若格<L；∨，∧>既是分配格，又是有补格，则称<L；∨，∧>为有补分配格.

(1)是分配格，但不是有补格;(3)既是有补格，又是分配格；例8

确定下面分别是什么格?(4)是有补格，但不是分配格.

(2)既不是分配格，又不是有补格；(1)(2)(3)(4)1acb01ab01ab0c1acb0de有补分配格有如下一些性质：定理7-13

在有补分配格<L；，>中，任一元素的补元素是唯一的.于是

我们记的补元素为.

证明

假设l

有两个补元素l1和l2，使得由定理7-12

定理7-14

（对合律）在有补分配格<L；∨，∧>中，对每一个，有.所以是的补元素，由补元素的唯一性,故有.证明

因为，由交换律有.

定理7-15（德·摩根定律）

在有补分配格<L

；∨，∧>中，对于任意的l1,l2∈L证明(1)

由补元素的唯一性有(2)同理可证.(或根据对偶原理)

练习1、填空（1）下图所表示的格中

①d

有

个补元素，它们分别是___________.

②a

有

个补元素，它们是

.③b

的补元素是

.

3

a、b、c

1d

d1cbda0BBA(2)判断下列次序图所表示的格是什么性质的格。

A．分配格；B．有补格；C．有补分配格；

D．非分配格，非有补格1cbda01cbda01cbda0(

)(

)()7.5布尔代数一布尔代数的定义

定义7-10

如果一个格是有补分配格，则称其为布尔代数，一般记作<B;，，->.（1）交换律：

（3)等幂律：（4）吸收律：

（2）结合律：

布尔代数<B

；，，->具有如下性质，对于B中任意元素x，y，z，有（5）分配律：

（6）同一律：

（7）零一律：

（8）互补律：

（9）对合律：

（10）德·摩根定律：

例1

全集合U

的幂集2U

上定义的集合的并，交和补运算与2U

构成的代数系统<2U，∪，∩,′>称作集合代数，它是一个布尔代数.

定义

设<B；，，->是一个代数系统，和是B上的二元运算，-是一元运算，若这些运算满足交换律，分配律，同一律和互补律，则称<B；，，->是布尔代数.

例

设是一布尔代数，φ{a,b,c}{a,c}{b,c}{a,b}{a}{c}{b}其次序图如下：二、布尔代数的性质定理7-20

布尔代数的每一子代数都是布尔代数.

定理7-27

每一有限布尔代数都有2n（n∈Z）个元素，元素个数相同的布尔代数必同构.

定理7-21

布尔代数的每一满同态象也是布尔代数.

例2

设

,则和等都是的子代数.

练习

1．

在下列各题后面的括号中键入“Y”或“N”来回答各题中相应的问题.（1）

设<L；，>是一个五元素的分配格，问该格是有补格吗？（）（2）

设<L；，>是一个九元素的有补格，问该格是分配格吗？（）（3）

U={a,b,c}，<2U

；是布尔代数吗？()(4)上题的<2U；的子代数是布尔代数吗？

()NNYY1.试证明在格中对于任意元素a,b,c,d,有

(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)证明因为

a∧b≤a

；a≤a

∨c，因此a∧b≤a∨c，

同理，c∧d≤c，c≤a∨c，因此