Main Ads

Header ADS

Booleam Algebra:


Chapter-03
Booleam Algebra:
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                 [ 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≤ bL
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 ≤ cL
Þ 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

Theme images by cutiebootiele. Powered by Blogger.