background image

Denition 2.63.

An element of bounded distributive lattice is called

complemented

when its

complement exists.

Denition 2.64.

A distributive lattice is a

complemented lattice

i every its element is comple-

mented.

Proposition 2.65.

For a distributive lattice

(

a

n

b

)

n

c

=

a

n

(

b

t

c

)

if

a

n

b

and

(

a

n

b

)

n

c

are dened.

Proof.

((

a

n

b

)

n

c

)

u

c

= 0

;

((

a

n

b

)

n

c

)

t

c

= (

a

n

b

)

t

c

;

(

a

n

b

)

u

b

= 0

;

(

a

n

b

)

t

b

=

a

t

b

.

We need to prove

((

a

n

b

)

n

c

)

u

(

b

t

c

) = 0

and

((

a

n

b

)

n

c

)

t

(

b

t

c

) =

a

t

(

b

t

c

)

.

In fact,

((

a

n

b

)

n

c

)

u

(

b

t

c

) =

(((

a

n

b

)

n

c

)

u

b

)

t

(((

a

n

b

)

n

c

)

u

c

) =

(((

a

n

b

)

n

c

)

u

b

)

t

0 =

((

a

n

b

)

n

c

)

u

b

v

(

a

n

b

)

u

b

= 0

;

so

((

a

n

b

)

n

c

)

u

(

b

t

c

) = 0

;

((

a

n

b

)

n

c

)

t

(

b

t

c

) =

(((

a

n

b

)

n

c

)

t

c

)

t

b

=

(

a

n

b

)

t

c

t

b

=

((

a

n

b

)

t

b

)

t

c

=

a

t

b

t

c:

2.1.8 Boolean lattices

Denition 2.66.

A

boolean lattice

is a complemented distributive lattice.

The most important example of a boolean lattice is

P

A

where

A

is a set, ordered by set

inclusion.

Theorem 2.67.

(De Morgan's laws) For every elements

a

,

b

of a boolean lattice

1.

a

t

b

=

a

u

b

;

2.

a

u

b

=

a

t

b

.

Proof.

We will prove only the rst as the second is dual.

It is enough to prove that

a

t

b

is a complement of

a

u

b

. Really:

(

a

t

b

)

u

(

a

u

b

)

v

a

u

(

a

u

b

) = (

a

u

a

)

u

b

 = 0

u

b

 = 0;

(

a

t

b

)

t

(

a

u

b

) = ((

a

t

b

)

t

a

)

u

((

a

t

b

)

t

b

)

w

(

a

t

a

)

u

(

b

t

b

) = 1

u

1 = 1

:

Thus

(

a

t

b

)

u

(

a

u

b

) = 0

and

(

a

t

b

)

t

(

a

u

b

) = 1

.

Denition 2.68.

A complete lattice

A

is

join innite distributive

when

x

u

F

S

=

F

h

x

u i

S

;

complete lattice is

meet innite distributive

when

x

t

d

S

=

d

h

x

t i

S

for all

x

2

A

and

S

2

P

A

.

Denition 2.69.

Innite distributive complete lattice

is a complete lattice which is both join

innite distributive and meet innite distributive.

Theorem 2.70.

Every complete boolean lattice is both join innite distributive and meet innite

distributive.

Proof.

We will prove only join innitely distributivity, as the other is dual.

Let

S

be a subset of a complete boolean lattice.

22

Common knowledge, part 1