Tuesday, August 12, 2008

Boolean Algebra



Boolean algebra is one of the most interesting and important algebraic structure which has significant applications in switching
circuits, logic and many branches of computer science and engineering.

Boolean algebra can be viewed as one of the special type of lattice.

A complemented distributive lattice with 0 and 1 is called Boolean algebra.
Generally Boolean algebra is denoted by (B, *, Å , ', 0, 1).

Example 1 :

( P(A), Ç , È , ', f, A) is a Boolean algebra. This is an important example of Boolean algebra [In fact the basic properties of
the (P (A), Ç , È , ' ) led to define the abstract concept of Boolean algebra]. Further, it can be proved that every finite Boolean
algebra must be isomorphic to (P (A), Ç , È , ' , f , A) for a suitably chosen finite set A. [refer [2]].

Example 2:

The structure ( Bn = {0,1}n , *, Å , 1, 0 ) is a Boolean algebra, where Bn is an n-fold Cartesian product of
{0,1} and the operations *, Å , are defined below.
We have Bn = {( l1, l 2, … , l n) / l r = 0 or 1, 1 £ r £ n}
(i 1, i 2, … , in) * (j1 , j2, … , jn) = (min (i 1, j1 ), min (i 2, j2), .., min (i n, jn) )
(i1, i2, … , in) Å (j1, j2,…, jn) = (max ( i1, j1), max ( i2, j2), … , max ( i n, jn) )
(l 1, l 2, l 3, … , l n)' = (l 1', l 2', …. , l n'),



1 = (1,1, …, 1) is the greatest element of Bn.
0 = (0, 0,0, … ,0) is the least element of Bn.
Since B is distributive, Bn is distributive. From the definition of unary operation " ' ",

it is clear that Bn is complemented. Further, it has 0 and 1. Thus, (Bn, *, Å , ', 0,1) is a Boolean algebra.
For the case n = 3 we have,
B3 = {000, 100, 010, 001, 110, 101, 011, 111}.
The structure of the B3 is given in the following Hasse diagram.



The Boolean algebra (Bn, *, Å , ', 0,1) plays an important role in the construction of switching circuits, electronic circuits and
other applications. Also it can be proved that every finite Boolean algebra is isomorphic to the above Boolean algebra
(Bn, *, Å , ', 0,1), for some n. Thus, it is interesting to observe that number of elements in any finite Boolean algebra must be
always 2n, for some n.

Let (B, *, Å , ' , 0,1) be a Boolean algebra and S Í B. If S contains the elements 0 and 1 and is closed under the
operation *, Å and ' then (S, *, Å , ', 0,1) is called sub Boolean algebra.


Example 1:


Consider the Boolean algebra (P ({1,2,3}), Ç , È , ' ,f , {1,2,3})



Then (S = {f , {1}, {2,3}, {1,2,3}}, Ç , È , ', f , {1,2,3}) is also sub Boolean algebra.
Similarly, S = ({f ,{3},{1,2},{1,2,3}}, Ç , È , ', f , {1,2,3}) is also sub Boolean algebra.
But (S = ({f, {1}, {2,3}, {1,2,3}}, Ç , È ,' , f , {1,2,3})) is not a sub Boolean algebra.

[Find why it is not a sub Boolean algebra].


If we have two Boolean algebras (B1, *1, Å 1, ', 01, 11) and (B2, *2, Å 2, '', 02, 12) then we can get new Boolean algebra
by taking direct product of these two Boolean algebras. The direct product of these Boolean algebra is the Boolean algebra
(B1 ´ B2, *3, Å 3, ''', 03, 13); where for any two elements (a1, b1) and (a2, b2) Î B1 ´ B2,

(a1,b1) * (a2,b2) = (a1 *1 a2, b1 *2 b2)

(a1,b1)Å (a2,b2) = (a1 Å 1 a2 , b1 Å 2 b2)

(a1,b1) ''' = (a1', b1'')

03=(01,02) and 13=(11,12).

Let (B, *, Å ,
', 0B , 1B) and (A, Ç , È, - , 0A , 1A) be two Boolean algebra. A mapping

f : B A is called a Boolean homomorphism if f preserves all the Boolean operations, that is,

f (a * b) = f (a) Ç f (b).
f (a Å b) = f (a) È f (b).

f (0B) = 0A.
f (1B) = 1A.


A bijective Boolean homomorphism is called Boolean isomorphism.


Exercise:
  1. Prove that mapping f defined in the exercise 1 of the Section 3.3.3 is a Boolean isomorphism.
  2. In every Boolean algebra, prove that (x * y)' = x' Å y' and (x Å y)' = x' * y', for all x, y.
  3. In a Boolean algebra B, for all x, y Î B, prove that
    x £ y x * y = 0x' Å y = 1x * y = xx Å y = y.



fig ( i ) fig ( ii ) fig ( iii )
  1. Show that in a Boolean algebra the following are equivalent for any a and b.
    ( i ) a' Ú b = 1
    ( ii ) a b' = 0.
  2. The Boolean algebras (P (A3), Ç , È, ', A3, f) and D30, where A3 = {1,2,3} are (Boolean) isomorphic? Justify your
    answer.

Lattices

© Moreniche


Lattices

In this section we introduce lattices as special type of partial ordered set and we discuss basic properties of lattices and some
important type of special lattices.

6.3.1. Lattice Ordered Sets

In this section we define lattice ordered sets and see some examples.


A poset (L, £ ) is called lattice ordered set if for every pair of elements x, y Î L, the sup (x, y) and inf (x, y) exist in L.


Example 1:

Let S be a nonempty set. Then (P(S), Í ) is a lattice ordered set. For (P (S), Í ) is a poset. Further for any subsets A, B of S,
inf (A, B) = A Ç B Î P(S) and sup (A, B) = A È B Î P(S).

Example 2:

Every totally ordered set is a lattice ordered set (Prove !).

Example 3:

Consider the set of all positive integer Z+ with divisor as a relation, i.e., a £ b if and only if a½b.
Then (Z+ , ½) is a poset.
For, if a, b Z+, then inf (a, b) = GCD(a, b) Z+ and sup (a, b) = LCM(a, b) Z+.
Thus, inf (a, b) and sup (a,b) exist in Z+ for any two element a, b Î Z+.
Hence (Z+ , ½) is a lattice ordered set. In fact (Dn , ½) ( Dn denotes the set of all positive divisors of positive number n ) is also
a lattice ordered set.


Example 4:
Consider the set B, where Bn = {(l1, l2, … , ln) / li = 0 or 1, for 1 £ r £ n}.
Define the relation £ ' by (i1, i2, … , in) £ ' (j1, j2, … , jn) if and only if ir £ jr , 1 £ r £ n.
Note that here in the expression ir £ jr, £ is usual less than or equal to.
We have already seen in Example 7 of Section 6.2.1 that (Bn, £ ') is a poset.

Observe that
inf [ (i1, i2, ….. ,in), (j1, j2, … , jn)] = (min (i1, j1), min (i2,j2), …. , min (in, jn) ) and
sup [ (i1, i2, … , in), (j1, j2, … , jn)] = (max (i1, j1), max (i2,j2), …. , max (in, jn) )

Since min (ir, jr) and max (ir, jr) is either 0 or 1,
so, inf { (i1, i2,… , in), (j1,j2, .. ,jn) } and sup { (i1, i2, … , in), (j1, j2, … , jn) } exist in B.
Thus, (Bn, £ ) is a lattice ordered set.

Example 5:
Poset represented by the Hasse diagram is not a lattice ordered set since inf (a, b) does not exist.




Example 6:

Poset represented by the Hasse diagram is not a lattice ordered set as sup (f, g) does not exist.



Exercise
:

  1. Prove that if (L, £ ) and (M, £ ' ) are lattice ordered sets. Then (L ´ M, R) is a lattice ordered set, where (a, b) R (x, y)
    if and only if a £ x in L and b £ ' y in M.
  2. Check whether the poset represented by the following Hasse diagram that is lattice ordered set or not?




Remark 1:
Let (L, £ ) be a lattice ordered set and let x, y Î L. Then the following are equivalent.
(i) x £ y
(ii) sup (x, y) = y
(iii) inf (x, y) = x

Proof
:

( i ) ( ii )
Let x £ y …… (1)
We have, y £ y , for all y Î L. …… (2)
From (1) and (2), we have y is an upper bound of (x, y).
Therefore, sup (x, y ) £ y (by definition of superimum).
But, y £ sup (x, y).
Therefore, y = sup (x, y) (since £ is anti - symmetric).
( ii ) ( iii )
Given that sup (x, y) = y. Therefore we have x £ y.
Also, we have x £ x.
Therefore, x is a lower bound for x and y.
Thus, x £ inf (x, y).
But, we have inf (x, y) £ x.
Hence, x = inf (x, y) ( since £ is anti-symmetric).
( iii ) ( i )

Given that x = inf (x, y).
Therefore, by the definition of infimum, x £ y.

6.3.2 Algebraic Lattice

In this section we define algebraic lattice by using two binary operations * (meet) and Å (join). Then we shall prove that lattice
ordered sets and algebraic lattices are equivalent.


An algebraic lattice (L, *,
Å ) is a non empty set L with two binary operations * (meet) and Å (join), which satisfy the
following conditions for all x, y, z L.

L1. x * y = y * x, x Å y = y Å x (Commutative)

L2. x * (y*z) = (x * y) * z, x
Å (y Å z) = (x Å y) Å z (Associative)

L3. x * (x
Å y) = x, x Å (x * y) = x (Absorption)

L4. x * x = x, x
Å x = x (Idempotent)


Theorem 3.2.1:
Let (L,
£) be a lattice ordered set. If we define x * y = inf (x, y), x Å y = sup (x, y) then (L, *, Å ) is an algebraic lattice.

Proof:
Given that (L, £ ) is a lattice ordered set and x * y = inf (x, y) and x Å y = sup (x, y).
Now we shall prove that * and Å satisfy the commutative, associative, absorption and idempotent laws.

Commutative

x * y = inf (x, y) = inf (y, x) = y * x.
x
Å y = sup (x, y) = sup (y, x) = y Å x.

Associative

x * (y * z) = inf (x, (y * z))
= inf (x, inf (y,z))
= inf (x,y,z)
= inf ( inf (x, y), z))
= inf ((x*y), z)
= (x*y) *z.

Now, x
Å (y Å z) = sup (x, (y Å z))
= sup (x, sup (y,z))
= sup (x, y,z)
= sup (sup (x,y), z)
= sup ((x
Å y), z)
= (x
Å y) Å z.

Absorption


Now, x * (x
Å y) = inf (x, x Å y)
= inf (x, sup (x, y))
= x [since x
£ sup (x, y)]
and
x
Å (x * y) = sup (x, x * y)
= sup (x, inf (x, y))
= x [since inf (x, y)
£ x ].

Idempotent

We have, x * x = inf (x, x) = x and x Å x = sup (x, x) = x.
Hence (L, * , Å ) is an algebraic lattice.



Theorem 3.2.2:
Let (L, *, Å ) be an algebraic lattice. If we define x £ y x * y = x or x £ y x Å y = y, then (L, £ ) is a lattice ordered set.

Proof:
Given that (L, *, Å ) is an algebraic lattice and x £ y x * y = x or x Å y = y.
We shall now prove that (L, £ ) is a poset and inf (x, y) and sup (x, y) exist in L, for all x, y in L.


£ is reflexive
Since x * x = x, for all x L (by indempotent of *).
We have by definition of £ , x £ x, for all x Î L.
Therefore, £ is reflexive.


£ is anti-symmetric
If x £ y and y £ x in L, then by definition of £ , we have x * y = x and y * x = y.
But * satisfies commutative law, so, we have x * y = y * x.
Therefore, x = y.
Hence, £ is anti-symmetric.


£ is transitive
If x £ y and y £ z, then by the definition of £ , we have x * y = x and y * z = y.
Therefore, x * z = (x * y) * z
= x * (y * z) [by associativity of *]
= x * y [by definition £ )]
= x [by definition of £ ]
Hence, by definition of £ , we have x £ z.
Thus, £ is transitive.

sup (x, y) and inf (x, y) exist in L

We shall now show that inf (x, y) = x * y and sup (x, y) = x Å y.
Now by absorption law, we have
x = x * (x Å y) and y = y * (x Å y)
Then by the definition of £ , we have x £ x Å y and y £ x Å y
Therefore, x Å y is an upper bound for x and y.
Let z be any upper bound for x and y in L.
Then x £ z and y £ z. So, by definition of £ ,
we have x Å z = z and y Å z = z …… ( 1 )
Therefore, (x Å y) Å z = x Å (y Å z) [by associative law]
= x Å z [by ( 1 )]
= z [by ( 1 )].
Thus, by definition of £ , we have x Å y £ z. that is, x Å y is related to every upper bound of x and y. Hence sup (x, y) = x Å y.
Similarly, we can show that inf (x, y) = x * y.
Thus, x * y and x Å y exists for every x, y Î L.
Hence, we have (L, £ ) is lattice ordered set.




Remark 1:

From the Theorem 3.2.1 and the Theorem 3.2.2, we see that if we have lattice ordered set (L, £ ) then we can get an algebraic
lattice (L, *, Å ) and conversely. Hence, we conclude that the algebraic lattice and a lattice ordered sets are equivalent system.
Thus, here after we shall say simply lattice to mean both.

In an algebraic system it is better convenience for imposing further conditions on the binary operations. Hence developing
structural concepts will be much easier than the ordered system. In fact, it is one of the motivation to view a lattice ordered set as
an algebraic lattice.


6.3.3 Sublattice, Direct Product and Homomorphism
In this section we discuss sublattices of a lattice, direct product of two lattices and homomorphism between two lattices.

6.3.3.1 Sublattices

Substructure helps to know more about the whole structure. So, here we discuss about sublattice of a lattice.
Let (L, *, Å ) be a lattice and let S be subset of L. The substructure (S, *, Å) is a sublattice of (L, *, Å ) if and only if S is
closed under both operations * and
Å.

Remark 1:
A subset S in a lattice (L, *, Å ) is said to be sublattice, for a, b S, if a * b = c in L and a Å b = d in L, then c, d must
necessary exist in S also.

Example 1:
Consider the lattice L represented by the following Hasse diagram.



Here the substructure S1 represented by the Hasse diagram given below is not a sublattice, for inf (a, b) = 0 in L, which does not
belong to S1.

It is clear that the substructure S2 represented by the Hasse diagram given below is sublattice of L.


It is interesting to note that the substructure 3 of L represented by the in the following Hasse diagram is not a sublattice but it is a
lattice on its own. So, it is a lattice without being a sublattice.


Exercise:
ind all the sub lattices of (D30, ½).

  1. Let L be a lattice and let a < style="font-family: Symbol;">Î L / a £ x £ b }. Prove
    that [a,b] is a sublattice.



6.3.3.2 Direct Product of Lattices


From given two lattices, we can always construct a new lattice by taking Cartesian product of the given two lattices. So, in this
section we discuss about product of two lattices.


Let (L, *, Å ) and (M,,) be two lattices. Consider the Cartesian product of L and M, that is,
L ´ M = {(x, y) / x Î L, y Î M}.
Define operations D and Ñ in L ´ M, by (x, y) D (a, b) = (x * a, y b) and (x, y) Ñ (a, b) = (x Å a, yb), then we shall prove
that ( L ´ M, D ,Ñ ) is a lattice.


D and Ñ are commutative.

By definition (x, y) D (a, b) = (x * a, y b)
= (a * x, b y) (since * and are commutative)
= (a, b) D (x, y) (by definition D ).

Similarly, (x, y) Ñ (a, b) = (x Å a, y b)
= (a Å x, b y)
= (a, b) Ñ (x, y).

Hence, commutative law holds good for both operations D and Ñ .

D and Ñ are associative

[ ( x, y) D (a, b) ) D (u, v)] = [ (x * a, y b) ] D (u, v) (by definition of D )
= [ (x * a ) * u, (y b) v] (again by definition of D )
= [ x * (a * u), y (b v) ] (since * and are associative)
= [ (x, y) D (a * u, b v) ] (by definition of D )
= [ (x, y) D [ (a, b) D (u, v) ] (by definition of D )

Similarly we can show that
[ (x, y) Ñ (a, b) ] Ñ (u, v) = (x, y) Ñ [ (a, b) Ñ (u, v) ]
Thus, associative law hold good for both operations and Ñ in L ´ M.


Absorption

(x, y) D [ (x, y) Ñ (a, b) ] = (x, y) D [ x Å a, y b]
= [ x * (x Å a), y (y b) ] (by definition of D and Ñ )
= (x, y ) (by absorption law in L and M).
Therefore, absorption law hold good in L ´ M.

Idempotent

(x, y) D (x, y) = [ x * x, y y]
= (x, y) (since * and satisfy idempotent law)
Similarly, (x, y) Ñ (x, y) = (x, y).

Hence, (L ´ M, D , Ñ ) is an algebraic lattice.
Thus, (L ´ M, D , Ñ ) is a lattice.

Remark 1:

If (L, *, Å ) is a lattice, then L² = L x L is a lattice. In general one can show that
Ln = L ´ L ´ L ´ …. ´ L (n times) is a lattice.

In the finite lattices, Bn is a very important lattices, where B = {0,1}, which has rich structural property and will play very
important role in the applications.

Let (L, £ ) and (M, £ ' ) be two lattices, then we have already seen that (L ´ M, R) where (x1, y1) R (x2, y2) if and only if
x1 £ x2 and y1 £ ' y2, is a poset. It can be proved that

(L ´ M, R) is a lattice ordered set. [ Prove !]

6.3.3.3 Homomorphism


In this section to understand the structural similarity between two lattices we define homomorphism between two lattices and we
discuss about it.


Let
(L, *, Å ) and (M, ,) be two lattices. A function f : L ® M is called a Lattice homomorphism if
f (a * b) = f (a) f (b) and
f (a Å b) = f (a) f (b), for all a, b Î L,

and it is called order preserving if x
£ y in L implies f (x) ' f (y), where £ is an order relation in L and ' is an order
relation in M.

A bijecitve homomorphism is called isomorphism.


Example 1:

Consider the lattices D6 = {1,2,3,6} and D30 = {1,2,3,5,6,10,15,30}. We can show that there exist a homomorphism f
between D6 and D30.

Define a mapping f from D6 into D30 by
f (1) = 1,
f(2) = 6,
f (3) = 15 and
f (6) = 30.

Then f (1 * 2) = f(1) = 1.
f (1) * f(2) = 1 * 6 = 1.
[Note that in both D6 and D30 a * b and a Å b are GCD and LCM of two element a, b]
Similarly, f (1 * 3) = f(1) = f(1) * f(3).
f(1 * 6) = f(1) * f (6) = f(1).
f(2 * 3) = f(2) * f(3) = f(1).
f(2 * 6) = f(2) * f(6) = f(2).
f(3 * 6) = f(3) * f(6) = f(3).


Similarly we can prove that
f (x Å y) = f (x) Å f (y) for all x, y D6 .


Thus, f is homomorphism.

Note that f is not onto but f is one-one.

Hence f is not an isomorphism.


Exercise 1:


It is very interesting to prove that the mapping f defined from Bn into P(An), where

An = {1,2, …. , n} by f (i1, i2, …. , in) = { k / ik ¹ 0} is a homomorphism.

6.3.3.4 Special Lattices


In this section we shall discuss some of the special types of lattices which in turn help to define the Boolean algebra.


6.3.3.4.1 Isotone, Distributive and Modular Inequalities

In this subsection we shall prove that in every lattice the operation * and Å are isotone and distributive and modular inequalities
holds good.

Lemma 3.4.1.1:

In every lattice L the operation * and Å are isotone,

i.e., if y £ z Þ x * y £ x * z and x Å y £ x Å z.

Proof:


x * y = (x * x) * (y * z) (since x * x = x and since y £ z, y * z = y)
= (x * y) * (x * z) (by associative and commutative of *).
x * y £ x * z (since a £ b a * b = a).

Also, x
Å z = (x Å x) Å (y Å z)
= (x
Å y) Å (x Å z)
x Å y £ x Å z.
Hence the lemma.

Theorem 3.4.1.2:
The elements of an arbitrary lattice satisfy the following inequalities

  1. x * (y Å z) ³ (x * y) Å (x * z)
    x
    Å (y * z) £ (x Å y) * (x Å z) (distributive inequalities.)
  2. x ³ z x * (y Å z) ³ (x * y) Å (x * z) = (x * y) Å z
    x
    £ z x Å (y * z) £ (x Å y) * (x Å z) = (x Å y) * x (modular inequalities.)


Proof:

Claim:
Distributive inequalities are true in a lattice.

By definition of Å, y £ y Å z and z £ y Å z.
By isotone property

we have x * y £ x * (y Å z) ............... (1)
and x * z £ x * (y Å z) ............... (2)

From (1) and (2) we observe that x * (y Å z) is an upper bound for x * y and x * z.

Hence, (x * y) Å (x * z) £ x * (y Å z).
By duality principle, we have (x Å y) * (x Å z) ³ x Å (y * z).

ii) It is given that z £ x, then by Theorem 3.2.2 z * x = z.
From the inequality ( i ) we have x* (y Å z) ³ (x*y) Å (x*z).
Therefore, x * (y Å z) ³ (x * y) Å z.
Since x £ z, we have x Å z = z.
Thus, from the inequality x Å (y * z) £ (x Å y) * (x Å z), we have
x Å (y * z) £ (x Å y) * z.
Hence the theorem.


6.3.3.4.2 Modular Lattices

In this section we shall define and discuss about the modular lattices.
A lattice L is said to be modular

if for all x, y, z
Î L, x£ z Þ x * (y Å z) = (x * y) Å z.

Example 1:

(P(A), Ç , È ) is a modular lattice [ Proof left as an exercise].


Example 2
:

The set of all normal subgroups of a group form a modular lattice. [Recall that a subgroup H of a group G is said to be normal if
gHg-1 = H, for all g Î G]. It can be easily shown that M, the set of normal subgroups of a group G, with `set inclusion' relation is
a poset.

Now for any two normal subgroups H1 and H2 of G, we have
H1 * H2 = inf (H1, H2) = H1 Ç H2 and
H1 Å H2 = sup (H1, H2) = H1H2.

Since H1 Ç H2 and H1H2 are normal subgroups if both H1 and H2 are normal subgroups. Therefore, (M, Í ) is a lattice ordered
set. Hence (M, *, Å ) is an algebraic lattice. Let H1, H2, H3, Î M such that H1 Í H3. Since in every lattice modular inequality
holds good, we have H1(H2 * H3) Í (H1 Å H2) * H3 ………. (1)

Now we shall prove that (H1 Å H2) * H3 Í H1 Å (H2 * H3).
Let a Î (H1 Å H2) * H3
i.e., a Î (H1 H2) Ç H3
a Î H1 H2 and a Î H3
a = h1h2 and a = h3, for some h1 Î H1 ,h2 Î H2 and h3 Î H3.
Therefore, h1h2 = h3
h2 = h1-1 h3 Î H3 [ h3 Î H3 and h1Î H1 Í H3 , therefore, h1-1 h3Î H3]
h2Î H2 and h2Î H3
Thus, h2 Î H2 Ç H3 ……… (2)
Since a = h1h2, we have a Î H1(H2 Ç H3) (by (2))
That is, aÎ H1 Å (H2 * H3)
That is, (H1 Å H2) * H3 Í H1 Å (H2 * H3) ………. (3)
From (1) and (3) we have
H1 Å (H2 * H3) = (H1 Å H2) * H3.
Hence (M, *,Å ) is a modular lattice.


Theorem 3.4.2.1:
A lattice L is modular if and only if x, y, z Î L , x Å (y * (x Å z)) = (x Å y) * (x Å z).
Proof :
Let (L, *, Å ) be a modular lattice
Then, if x £ z implies x Å (y * z) = (x Å y) * z ……… (1)
But, for all x , z Î L, x £ x Å z,
So, by (1) we have
x Å (y * (x Å z)) = (x Å y) * (x Å z), for all x, y, z Î L

Conversely, suppose x Å (y * (x Å z)) = (x Å y) * (x Å z). ……… ( 2 )

Then we shall prove that L is modular.
If x £ z then x Å z = z ………. (3)
Substitute (3) in (2), we have if x £ z Þ x Å (y * z) = (x Å y) * z
Thus, (L, *, Å ) is modular.


If we have a characteristic result in terms of Hasse diagram for the modular lattice then it would effectively help in deciding a given
lattice is modular or not. So, we shall prove the following lemma.


Lemma 3.4.2.1:

The "Pentagon Lattice" represented by the Hasse diagram given below is not modular.

Proof:
From the structure of the pentagon lattices we see that c £ a.
Now c Å (b * a) = c Å 0 = c. On the other hand, (c Å b) * a = 1 * a = a.
Definitely c ¹ a, thus, pentagon lattice is not a modular lattice.

On the other hand, it can be proved that if any lattice whose substructure is isomorphic to a pentagon lattice cannot be a
modular lattice. So, we have the following theorem.

Theorem 3.4.2.2:
A lattice L is modular if and only if none of its sublattice is isomorphic to the "pentagon lattice" [ for the detailed proof refer [2]]

Exercise 1:
Prove that the intervals [x, x Å y] and [ x * y, y] are isomorphic in a modular lattice. [ By interval [u ,v] we mean the set
{ t Î L / u £ t £ v }]

Exercise 2:
Prove that if a ³ b and if there exists c Î L with a Å c = b Å c and a * c = b * c then a = b.


6.3.4.3 Distributive Lattices
In this section we will define and discuss distributive lattices.

A lattice (L, *,
Å) is called a distributive lattice if for any a, b, c Î L,
a * (b Å c) = (a * b) Å (a * c)
a Å (b * c) = (a Å b)*(a Å c)

Example 1:
(P(A), Ç , È ) is a distributive lattice. [ For proof refer Section1.2]

Example 2:

Every totally ordered set is a distributive lattice.
Proof:
In a totally ordered set (T, £ ) for any two elements a, b in T, we have either a £ b or b£ a. Therefore, for any three elements a,
b, c in T, the following are the possible situations in the structure of (T, £ ).









All these possible choices can be covered in the following two cases.

Case 1: a £ b or a £ c [ the first four choices ]

Case 2: a ³ b and a ³ c [ the last two choices ]

For the case 1, we have,
a*(b Å c) = a and (a * b) Å (a * c) = a Å a = a
For the case 2, we have,
a*(b Å c ) = b Å c and (a * b) Å (a * c) = b Å c
Hence any totally ordered set (T, £ ) is a distributive lattice.



Example 3:
The set of all positive integers Z+, ordered by divisibility is a distributive lattice.
Proof:
We know that (Z+, ½ ) is lattice, where x * y = GCD(x, y) and x Å y = LCM(x, y), for x, y Î Z+.
Since every positive integer can be expressed as product of powers of primes,

Let x = , y = and z = .

Note that xi , yi , zi may be zero also.
Now , y * z =

x Å (y * z) =

=

= *

= (x Å y) * (x Å z)

Remark 1:

It is clear from the definition of distributive lattice that if a ³ c then a * c = c and a Å c = a.

Therefore, a * (b Å c) = (a * b) Å (a * c)
= (a * b) Å c.

If a £ c then a * c = a and a Å c = c.
Therefore we have a Å (b * c) = (a Å b) * (a Å c)
= (a Å b) * c.

Thus, every distributive lattice is modular.

On the other hand every modular lattice need not be distributive.
For example, the following modular lattice called diamond lattice is not distributive lattice.

Diamond Lattice:




For,Å (b * c) = a Å 0 = a
(a Å b) * (a Å c) = 1 * 1 = 1
Therefore, aÅ (b * c) ¹ (a Å b) * (a Å c).
Hence, a diamond lattice is not a distributive lattice.


It is interesting to observe that if a lattice is not modular it cannot be a distributive lattice.
It follows from the Theorem 3.4.2.2. and the above Remark1, we have the following theorem which will effectively decide the
given lattice is distributive or not.


Theorem 3.4.3.1:

A lattice is distributive iff none of its sublattice is isomorphic to either the pentagon lattice or diamond lattice.
[ For the proof refer [ 2 ] ]

Exercise:

Prove that the direct product of two distributive lattices is a distributive lattice.

Theorem 3.4.3.2:
Let (L, *, Å ) be a distributive lattice. Then for any a, b, c Î L,
a * b = a * c and a Å b = a Å c Þ b = c [cancellation law].
Proof:
(a * b) Å c = (a * c) Å c = c (since a * b = a * c and by absorption law, (a * c) Å c = c)

Now, (a * b) Å c = (a Å c) * (b Å c) (by distributive law)
= (a Å b) * (b Å c) (since a Å c = a Å b)
= b Å (a * c) (by distributive law)
= b Å (a * b) (since a * c = a * b)
= b (by absorption law)
Hence, b = c .
3.4.4 Complemented Lattices


In this section we shall define complemented lattices and discuss briefly.


In a lattice (L, *, Å ), the greatest element of the lattice is denoted by 1 and the least element is denoted by 0.

If a lattice (L, *,Å ) has 0 and 1, then we have,
x * 0 = 0, x Å 0 = x, x * 1 = x, x Å 1 = 1, for all x Î L.


A lattice L with 0 and 1 is complemented if for each x in L there exists atleast one y Î L such that x * y = 0 and
x
Å y = 1 and such element y is called complement of x.

Note:
It is customary to denote complement of x by x'.

Remark 1:
It is clear that complement of 1 is 0 and vice versa.

Example 1:

Consider the lattice (P(A), Í )
Here 0 = f and 1 = A.
Then, for every S Î P(A), that is, S Í A, complement of S is A\ S, i.e. S'.


Example 2:
Consider the lattice L described in the Hasse diagram given below.

Here, c does not have a complement.
For, c * 0 = 0, but, c Å 0 = c.
Therefore, 0 can not be a complement of c.

Since a Å c = c, therefore, a can not be a complement of c.

Further, since c * b = c, b is not a complement of c.
Also, c * 1 = c, 1 is not a complement of c.
Hence, c does not have any complement in L.
Therefore, L is not a complemented lattice.

Example 3:
In a totally ordered set, except 0 and 1, all the other elements do not have complements.

Example 4:
Consider the lattice L described by the Hasse diagram given below.
Here, for c, we have, c * a = 0 and c Å a =1 and also, c * b = 0
and c Å b = 1.
Thus, c has a and b as its complements.
From this example, it is clear that complement of an element in a complemented lattice need not be unique.


Theorem 3.4.5.1:

In a distributive lattice L with 0 and 1, if a complement of an element exists then it is unique.
Proof:
Let L be a distributive lattice with 0 and 1. Let aÎL. Suppose a' and a" be two complement of a. Then by the definition of
complement of an element, we have
a * a' = 0 and a Å a' = 1
a Å a" = 0 and a Å a" = 1

Therefore, a * a' = a * a" and a Å a' = a Å a".
Therefore by cancellation law in a distributive lattice, we have a' = a".
Thus, complement of an element in a distributive lattice is unique.

Exit Quiz Questions:

  1. Is the poset A = {2, 3, 6, 12, 24, 36, 72} under the relation of divisibility a lattice.
  2. If L1 and L2 are the lattices shown in the following figure, draw the Hasse diagram.of L1´ L2 with product partial order.

  1. Show that a subset of a totally ordered set is a sublattice.
  2. Find all the sublattices of D24 that contains at least five elements.
  3. Shows that sublattice of a distributive lattice is distributive.
  4. Show that the lattice given below is not a distributive lattice but modular.

  1. Find the complement of each element of D42.
  2. Determine whether the lattice given below is distributive, complemented or both.