Booleam Algebra:
Chapter-03
v Lattice: A partially ordered set is said to be a lattice if
every two elements in the set have a unique least upper bound and a unique
greatest lower bound.
Lattice Not a
lattice
v Algebra system: let (A, ≤) be a lattice define an algebraic system
(A, V, L) Where v and L are two binary operation on A such that for a and b
in A, avd is equal to the least upper bound of a and b and aLb is equal to the greatest lower bound of a and b.
The binary operation v is known as the join operation and the binary operation L is known as the meet operation.
v
|
a
|
b
|
c
|
d
|
e
|
f
|
g
|
a
|
a
|
a
|
a
|
a
|
a
|
a
|
a
|
b
|
a
|
b
|
a
|
a
|
b
|
a
|
b
|
c
|
a
|
a
|
c
|
a
|
c
|
c
|
c
|
d
|
a
|
a
|
a
|
d
|
a
|
d
|
d
|
e
|
a
|
b
|
c
|
a
|
e
|
c
|
e
|
f
|
a
|
a
|
c
|
d
|
c
|
f
|
f
|
g
|
a
|
b
|
c
|
d
|
e
|
f
|
g
|
L
|
a
|
b
|
c
|
d
|
e
|
f
|
g
|
a
|
a
|
b
|
c
|
d
|
e
|
f
|
g
|
b
|
b
|
b
|
e
|
g
|
e
|
g
|
g
|
c
|
c
|
e
|
c
|
f
|
e
|
f
|
g
|
d
|
d
|
g
|
f
|
d
|
g
|
f
|
g
|
e
|
e
|
e
|
e
|
g
|
e
|
g
|
g
|
f
|
f
|
g
|
f
|
f
|
g
|
f
|
g
|
g
|
g
|
g
|
g
|
g
|
g
|
g
|
g
|
v For any a and ab in a lattice (A,≤) a≤ a vb and aLb
≤ a.
Proof: Since the join of a and b that is avb is an upper
bound of a and b, \
a≤ avb
Again, the meet of a and b that is aLb
is a lower bound of a and b
\
a L b ≤ a.
(proved)
v For any a, b, c, d in a lattice (A, ≤) if a ≤b and c≤d then
A v c ≤ b v d
and
A L c ≤ b L
d
Proof: given that a ≤ b and c ≤ d.
Since we know that,
B ≤ b v d and d ≤ b v d
Then by
transitivity we get, a≤ b v d and c≤ b v d.
In other words b v d is an upper bound of a and c,
therefore, a v c ≤ (b v d) v (bvd)
Þ
avc ≤ bvd
Again, since a≤ b and c ≤d and aLc
≤ a and aLc ≤ c
Then by transitivity we get, aLc
≤ b and a Lc ≤ d
In other words a Lc is a lower bound of b and d, therefore, aLc
≤ bLd.
v Principle of
Duality: let (A, ≤) be a
partially ordered set. Let ≤R be a binary relation on A, such that for any a and b in A, a ≤ R b if and only if b≤a. If is
clear that (A, ≤R) is also a partially ordered set. Furthermore, if (A, ≤) is a
lattice than (A, ≤R) is also a lattice. We note that the lattice (A, ≤) and (A≤R)
are closely related and so are the algebraic system defined by them. To be
specific, the join operation of the algebraic system defined by (A, ≤) is the
meet operation of the algebraic system defined by (A, VR), and the= meet
operation of the algebraic system defined by (A, ≤) is the join operation of
the algebraic system defined by (A, ≤ R).
As an example we note that the relation a≤aL
b can be stated as “the join operation of any two elements in a lattice is less
then or equal to each of the two elements.
Conversely we have the met operation of any two
elements in a lattice is equal elements. Both the join and meet operations are
commutative, i.e avb = bva, aLb=bLa.
Both joind and meet operation are communicative,
I,e,\avb = bva
aLb = bLa
proof: By definition, avb = least upper bound of a and b
bva = least upper bound of a and b since the least upper bound of a set is unique
therefore, we have avb = bva
again, by definitions,
aLb = greatest lower bound of a and b since the greatest lower bound of a set
unique, therefore we have,
aLb = bL a
(proved)
v Both the join and keep operation are associative , i,e,
Av (bvc) = (avb) vc
And aL (bLc) = (aVb) L c
Proof: we first show that the join operation v is
associative. That is for a , b, c, in A,
Av (bvc) = (avb) vc
Let, av (bvc)
= g and
(avb ) vc =h
Since g is
the least upper bound of a and bvc, than we have
A ≤ g and bvc ≤ g
again, since b ≤ bvc and c ≤ bvc then by
transitivity, b ≤ g and c ≤ g. Now, a ≤ g and b ≤ g imply that, avb ≤ g,
again, avb ≤ g and c ≤ g
Þ
(avb)vc ≤g
Þh
≤ g ……(i)
Since h is
the least upper bound of avb and c, then avb ≤ h and c ≤ h.
Again, since a ≤ avb and b ≤ avb then by
transitivity, a ≤ h and b ≤ h.
Now, b≤ h and c ≤ h imply that bvc ≤ h. Again a ≤ h
and bvc ≤ h
Þ
av (bvc) ≤ h
Þ
g≤ h …………(ii)
Equation (i) and (ii) implies that g = h
\
a v (bvc) = (avb) vc
Now by
principle of duality, we have aL (bLc) = (aLb) L c
(Proved)
v Idempotent
Property: The relation ava = a
and aLa =a are know as idempotent property of the join and
meet operation.
v For every a in A,
Ava = a and aL a = a
Proof: we know that, a ≤ a v a ………………….(i)
Since, a ≤ a,
we obtain, av a ≤ a……………..(ii)
From (i) and
(ii) we have, ava = a
According to the principle of duality we also have,
aL a = a
(Proved)
[Idempotent + Absorption properties এর শুধু স্টেটমেন্ট ও আসে]
v (Absorption property): for any a and b in A,
av(aLb)
= a
And aL (avb) = a
Proof: Since av (aLb) is the join of a and aLb
then we have
a ≤ av (aLb)……..(i)
aL b ≤ a v (aLb) ………….(ii)
again since,
a≤a and aLb ≤ a
Þ
av (aLb) ≤ ava
Þ
av (aLb) ≤ a ………………..(iii)
From (i) and
(iii) we get, av (aLb) = a
Then by principle of duality, aL
(avb) = a
(Proved)
v Equational form
of absorption property: Max [a, min (a,b)] =a
Min [a, max (a,b)] = a
v Distributive
lattice: A lattice is said to
be a distributive lattice if the meet operation distributes over the join operation and the join operation
distributes over the meet operation. For any a, b and c,
aL (bvc) = (aLb) v (aLc)
av (bLc) = (avb) L ( avc)
Example:
Distributive
lattice
Not distributive lattice
v If the meet operation is distributive over the join
operation in lattice than the join operation is also distributive over the meet
operation. If the join operation is distributive over the meet operation, then
the meet operation is also distributive over the join operation.
Proof: Given that, aL (bvc) = (aLb) v (aLc)
Off topic: because of commutativity, the equation, (avb ) L c = (aL c) v (bLc)
(aLb)
vc = (avc) L (bvc)
Now, (avb)L (avc) =
[(avb)L a] v [(avb)
c]
=
av [(avb)Lc]
=
Av[(aLc) v (bLc)]
=
[av (aLc)] v (bLc)
=
av (bLc)
\
av (bLc) = (avb ) L (avc)
By duality, we obtain the result that if the join
operation is distributive over the met
operation then the meet operation is also distributive over the join operat ion.
v Universal upper bound:
An element a in a lattice (A, ≤) is called universal upper bounds if for every
element bÎA, b≤a. If a lattice has a universal upper bound
then it is unique.
v Universal lower
bound: An element a in a
lattice (A, ≤) is called a universal lower bound if for every element bÎA,
a≤b. If a lattice has a universal lower bound, it is unique.
Figure shows that, h is
a universal lower bound.
v Uniqueness: we assure that, there are two universal
upper bound a and which implies then b≤a and a≤b which implies a = b. Similarly
universal lower bound are also unique.
v Let (A, ≤) be a lattice with universal upper bound
and lower bound 1 and o. For any element a in A,
I) av1 = 1 ii) av 0= a
iii) aL1 = a iv)
aL0 = 0
Proof: we know
that, 1≤ av1 …………..(1)
Since 1 is the universal upper bound
\
av1 ≤ 1 …………………….(ii)
From (i) and (ii) we get, av1 = 1 (proved i)
Again, we know that,
aL1 ≤ a ……………….(iii)
since a≤ a and a ≤ 1 then,
a≤ a L1……………….(iv)
from (iii) and (iv) we get,
aL1 = a (proved ii)
we know, a ≤ av0 …………………….(v)
since, a≥a and a≥0, then av0≤a……………………(vi)
from (v) and (vi) we eget. Av0 = a (proved iii)
we have, aL0≤ 0 …………………………(vii)
since 0 is the universal lower bound then 0 ≤ a L0
………………..(viii)
from (vii) and (viii) we get, aL0
= 0 (proved iv)
v
Complement
of an element: let (A, ≤) be a
lattice with universal upper bound and lower bound 1 and 0. For any
element a in A, an element b is
said to be a complement of a if avb = 1 and aLb = 0
Because of commutativity if a is a complement
of b, then b is also complement of a. for example
in the
lattice in figure , both b and c ae
complement of d. On the other hand, c no complement.
v Complemented
lattice: A lattice is said
to be a
complemented lattice if every element in the
lattice has a complement. (clearly, a complemented
lower and upper bounds.)
For example, the lattice in figure is a complemented
lattice,
where the complement of a and b is c.
v In a
distributive lattice, if an element has a complement,
then this complement, then this complement is
unique.
Proof: Suppose that an element a has two complements
b and c, that is
avb =1, aLb = 0, avc =
1 aLc= 0
we have, b=
bL1
=
bL (avc)
=
(bLa) v (bLc)
=
0 v (bLc)
=(aLc)
v (bLc)
=
(avb) Lc
=1Lc
=
c
\
b = c , this implies that the complement is unique..
v Boolean Lattice: a lattice (A, ≤)
Is said to be
a Boolean lattice if it is distributive and complemented. Since every
element in a Boolean lattice has a unique complement, we can define a unary
operation on a denoted by ‘_’ , so that for every a in A, a is the complement
of a. The unary operation referred to as complementation operation.
v Boolean Algebra: Suppose a
Boolean lattice (A, ≤) defines an algebraic system
(A,v,L,-)
Where vLand are the join, meet and complement respectively,
then the algebraic system defined by the Boolean lattice is known as the
Boolean A lgebra.
v For any a and b in a Boolean algebra,
avb =a̅ L b̅ [
De Morgan’s law]
aLb = a̅ v b̅
Proof: we have, (avb) v (a̅ L b̅ ) = {(avb) v a̅ } L {(avb) v b̅}
=
{(ava̅) v b } L {av (bv b̅)}
=
{ (1vb) L (a v 1)}
=
1L1
=
1
=
1
(avb) (a̅ L b̅) = 1
and (avb) L (a̅ L b̅) = {a L (a̅ L b̅)} v { bL (a̅ L b̅)}
=
{|(aLa̅) L b̅} v {a̅ L(bLb̅)}
=
(0Lb̅) v (a̅L0)
=
0v0
=
0
\
(avb) L (a̅ L b̅) = 0
Thus a̅ L
b̅ is the complement of avb, i.e, avb =
a̅ L b̅ (proved)
Again, we have,
(aLb) v (a̅ v b̅) = { a v (a̅ v b̅)} L
{bv (a̅ v b̅)}
=
{(ava̅) v b̅} L {a̅ v (av b̅)}
=
(1 v b̅) L (a̅ v 1)
=
1L1
=
1
\
(aLb) v (a̅ v b̅) = 1
And, (aLb) L (a̅ v b̅) = {(aLb)La̅} v {(aLb)Lb̅}
=
{(aLa̅)Lb} v {aL (bLb̅)}
=
(0Lb) v (aL0)
=
0v0
=
0
Thus a̅ v b̅ is the complement of aLb
i.e,
aLb = a̅ v b̅
(Proved)
v Cover: let a and b are two element in a lattice, then a is
said to be cover b if b<a and there is no element c such that b<c and
c<a.
v Atom: let (A,≤) be
a lattice with universal lower bound O.
An element is called atom if it covers O
For example, the lattice in figure e and f are atoms
Off topic: Universal lower bound যাকে cover করে তাকে atom বলে।
v
In a distributive lattice , if bLc̅ = 0 then b≤ c.
Proof:
since bLc̅ = 0, we have (bLc̅) vc = ovc
Þ (bvc) L (c̅vc) =
c
Þ (bvc) L 1 = c
Þ bvc = c
Since c is the least upper bound of
b and c, then b≤ c (Proved)
Off
Topic: c≤ bvc and b≤ bvc Þ b≤c
v Let (A,v,L,̅ ) be a finite Boolean algebra. Let b be any non-zeroo element in A and a1,
a2…………..ak be all the atoms of A such that ai≤ b. Then b = a1 v a2
v ………….. vak.
Proof: Since, a1≤ b, a2≤ b
If follows that, a1va2v…………….vak≤b…………………..(1)
Let us consider that, a1va2v…………….vak =c
Let us suppose that bLc̅ ≠ 0
Then there exist an atom a such that, a≤ bLc̅
Since bL c̅ ≤ b and bL ≤ c̅ then by
transitivety we get,
a≤ b and a ≤ c̅ Since a ≤ b and a1 ≤ b
then a is equal to one of the atom ai, then a ≤ c
Combining a ≤ c and a ≤ c̅ we obtain, aL
a ≤ cLc̅
Þ
a ≤0 which is contradiction. If follows that we must have, bLc̅
= 0 and b ≤ c
By antisymmentric law , b = a1 v a2
v ……………vak. (proved)
v Let a and b are the two elements in a lattice (A, ≤)
show that aLb = b iff avb
= b
Proof: Let aLb = b
Þ
av (aLb) = avb
Þ
a = a vb ( by absorption property)
Conversely let avb= a
Þ
(avb ) L b = aLb
Þ
b = aLb (by
absorption property) (proved)
v Let a, b and c are the elements in a lattice (A, ≤)
show that if a ≤ b then, av (bLc) ≤ b L (avc)
Proof: since, a ≤ b and b ≤ b then avb ≤b
Again, we have, b ≤ avb , avb = b
Since b≤ avb and
c ≤ avc
\
bLc ≤ (avb)L (avc) ………………….(i)
Again, a≤ avb and a≤ avc
Þ
aLa ≤ (avb) L (avc)
Þ
a ≤ (abv) L (avc)……………….(ii)
From (i) and
(ii)
a v (bLc)
≤ (avb) L (avc)
av(bLc) ≤ bL (avc) [
avb=b]
(proved)
v Let a, b, c are the elements in a lattice (A, ≤)
then show that,
1.
Av (bLc)
≤ (avb) L (avc)
2.
(aLb)
v (aLc) ≤ aL (bvc)
Proof: (1): since, b≤ avb and c ≤ avc
Þ
bLc ≤ (avb ) L (avc)…………(1)
Again, since a≤ avb, a ≤ avc
Þ
a ≤ (avb) L (avc)…………………..(ii)
From (i) and (ii), av (bLc)
≤ (aavb)L (avc)
Proof: Since, b≥ aLb, c ≥ a Lc
Þ
bvc ≥ (aLb) v (aLc) ………..(i)
Again since, a ≥ (a Lb, a ≥ ac)
Þ
a ≥ (aLb) v (aLc) ………………….(ii)
From (i) and (ii), aL (bvc) ≥ (aLb) v (aLc)
(proved)
v Show than a lattice is a distributive iff for any
element a,b,c in a lattice, (avb)Lc ≤ av (bLc)
Proof: since a, b, c are elements in a distributive
lattice then,
av (bLc) = (avb )L (avc)………(i)
(avd)Lc = (aLc) v(bLc)………….(ii)
Since b ≥ bLc
and c ≥ bLc
Þ
bLc ≥ bLc and a ≥ aLc
Þ
a v (bLc) ≥ (bLc) v (aLc)
Þ
a v (bLc) ≥ (avb)Lc
\
(avb ) Lc ≤ av (bLc)
Conversely, let (avb)Lc
≤ a v (bLc)
Which implies that, (avb) Lc
≤ a ………….(p)
(avb)Lc ≤ bLc………………….(q)
And (avb) Lc≤ c……………….(r)
From (p) and (r)
(avb)Lc ≤ aLc ……………..(s)
Now, from (q) and (s) we get,
(avb) Lc ≤ (aLc) v (bLc) …………….(A)
But avb ≥ a and c ≥ c
Þ
(avb)Lc ≥ aLc……………….(t)
Also, avb ≥ b and c≥ c
Þ
(avb)Lc ≥ bLc……………..(u)
From (t) and (u), (avb)Lc
≥ (aLc) v(bLc) …………….(B)
From (A) and (B) it is clear that (avb)Lc
= (aLc) v (bLc)
Similarly, we have to that, av(bLc)
= (avb)L(avc)
Absorption Property use করা হয়েছে।
v
Let (A,
≤ ) be a distributive lattice show that aLx = aLy and avx = avy, for some a,
then x=y
Proof:
given that , (A, ≤)
be a distributive lattice, Now,
x = x v (a L x)
= (xva) L (x v x)
= (avy) L x
= (aL x) v (y L x)
= aLy V ( yLx)
= {av (yLx)} L {yv (yLx)}
= {(avy) L (avx)} L y
= {(avy) L (avy)} L y
= (avy) Ly
= y
x =y
No comments