5.1 Lattice as partially ordered set | unit 5 lattice boolean algebra

DMS

UNIT–5

Lattice & Boolean algebra

5.1 Lattice as partially ordered set

Lattices-

A lattice is a partially ordered set in which every pair of elements a,b has a greatest lower bound and a least upper bound

For example-

Suppose S be a non-empty set and L = P(S); that means ( is partially ordered.

If X and Y are two elements of L, then-

Hence ( is a Lattice.

Axiomatic definition of Lattice-

Let L be a non-empty set closed under two binary operations denoted by ∧ and ∨.

Then L is said to be a Lattice if it follows the axioms given below, here a, b and c are the elements of L.

1. Commutative law-

(i) a∧ b = b ∧ a (ii) a ∨ b = b ∨ a

2. Associative law-

(i) (a ∧ b) ∧ c = a ∧ ( b ∧ c) (ii) (a ∨ b) ∨ c = a ∨ (b ∨ c)

3. Absorption law-

(i) a∧ (a∨b) = a (ii) a∨(a∧b) = a

To show that which operation is involved we denote the Lattice by (L, ∧, ∨)

Theorem-Let (L, ≤) be a lattice in which ‘⋅’ And ‘+’ denote the operations of meet and join respectively.

Then

a≤b ⇔a ⋅b = a ⇔a + b = b ∀a, b, c ∈L

Proof: Suppose a ≤b

As we know that a ≤a so that a ≤a.b but according to definition a.b≤a

So that- a ≤b ⇒a ⋅b = a

Let a ⋅b = a

But this is possible only if a ≤b which means a ⋅b = a ⇒a ≤b

∴a≤b⇒a ⋅b = a and a ⋅b = a ⇒a ≤b

Combine these two, we get

a≤b ⇔a ⋅b = a

Now let,

a⋅b = a,

Then we have

b + (a ⋅b) = b + a + a + b

But,

b + (a ⋅b) = b

Hence a + b = b

Similarly by assuming a + b = b

We can show that a ⋅b = a

Hence a ≤b ⇔a ⋅b = a ⇔a + b = b = a

Isomorphic Lattice-

Two lattices L and L’are said to be isomorphic if there is a one-to-one correspondence

f: L →L’

Such that

f (a ∧b) = f (a) ∧f (b) and f (a ∨b) = f (a) ∨f (b)

For any elements a, b in L.

Note-

1. A lattice is called complete if each of its non-empty subsets has a least upper bound and a greatest lower bound.

2. A lattice L is complemented if it is bounded and if every element in L has a complement.

3. Let ( L, ⋅, +, 0, 1) be a bounded lattice and a ∈L. If there exists an element b ∈L

Such that

a⋅b = 0 and a + b = 1

Then b is called the complement of a.

Sub Lattices and Direct products-

Sub Lattices-

Let (L, ≤) be a lattice. A non-empty subset A of L is called a sub lattice of L if

a + b ∈A and a ⋅b ∈A whenever a ∈A and b ∈A.

If A is a sub lattice of L, then A is closed under the operations of ‘’ ⋅and ‘+’.

Direct product-

Let (L1, *, +) and (L2,∧, ∨) be two lattices. The algebraic system (L1 × L2,...,+)

In which the binary operation + and ‘’ ⋅are on L1 × L2 defined as

(a1, b1) ⋅(a2 ,b2 ) = (a1 ∗a2 , b1 ∧b2 )

(a1, b1 )+ (a2 ,b2 ) = (a1 ⊕a2 , b1 ∨b2 )

For all (a1, b1) and (a2, b2) (a2 ,b2 ) ∈L1 × L2

Is called the direct product of the lattices L1 and L2.

Note-

1. Let (L, ⋅, +, 0, 1) be a lattice L is said to complemented lattice if every element has atleast one complement.

2. A lattice (L, ⋅, +) is called a distributive lattice if for any a, b, c ∈L

a⋅ (b + c) = (a ⋅b) + (a ⋅c) and

a + (b ⋅c) = (a + b) ⋅ (a + c)

3. Let (L, ≤) be a lattice, with an upper bound 1. An element a ∈L is said to be meet irreducible if a = x ⋅y implies a = x or a = y.

If a ≠0 then a is meet irreducible if and only if a has unique immediate successor

5.2 Lattice as an algebraic system, Special lattice

A lattice is an algebraic system (L, ⋅, +) with two binary operation ‘⋅’ and ‘+’ on Lwhich are both commutative and associative and satisfy absorption laws.

Bounded lattice-

If L is a lattice, then every pair of elements of L has a least upper bound and a greatest lower bound. If A is a finite subset of A, then A has both least upper bound and greatest lower bound. This property may not hold if A is not a finite subset of L, we find greatest lower bound and least upper bound of a subset of a lattice as follows.

Let (L, ⋅, +) be a lattice and A ≤L be a finite subset of L. The greatest and least upper bound of Aare defined as

Where A = {}.

Note-

1. A lattice is called complete if each of its non-empty subsets has a least upper bound and a greatest lower bound.

2. Let ( L, ⋅, +, 0, 1) be a bounded lattice and a ∈L. If there exists an element b ∈L

Such that

a⋅b = 0 and a + b = 1

Then b is called the complement of a

3. Let A be a non-empty set and L = P (A). Then the every element of L has a complement.

Sub lattice

Let (L, ≤) be a lattice. A non-empty subset A of L is called a sub lattice of L if

a + b ∈A and a ⋅b ∈A whenever a ∈A and b ∈A.

If A is a sub lattice of L, then A is closed under the operations of ‘’ ⋅and ‘+’.

Example: Let be the set of all positive integers and let D denote the relation “division” in such that for any a, b ∈, a D b if a divides 6. Then (, D) is a lattice in which a + b = LCM of a andb and a ⋅b = GCD of a and b.

Direct product of the lattices-

Let (L1, *, +) and 2 (L ,∧, ∨) be two lattices. The algebraic system (× , ..., +) in which the binary operation + and ‘.’are on × defined as

(a1, b1) ⋅(a2 ,b2 ) = (a1 ∗a2 , b1 ∧b2 )

(a1, b1 )+ (a2 ,b2 ) = (a1 ⊕a2 , b1 ∨b2 ) for all (a1, b1) and (a2, b2) (a2 , b2 ) ∈is called the direct product of the lattices and

Distributive lattice-

A lattice (L, ⋅, +) is called a distributive lattice if for any a, b, c ∈L

a⋅ (b + c) = (a ⋅b) + (a ⋅c) and

a + (b ⋅c) = (a + b) ⋅ (a + c)

Note- The power set of a non-empty set A is a lattice under the operation ∩and ∪is a distributive lattice.

5.3 Boolean algebra: Definitions & Examples

A Boolean algebra is a distributive complemented lattice having atleast two elements as well as 0 and 1.

A Boolean algebra is generally denoted by a 6-tuple, (B, +, ⋅, 1, 0, 1) where (B, +, ⋅) is a lattice with two binary operations + and ⋅, called the join and meet respectively is a unary operation in B. The elements 0 and 1 are the least and greatest elements of the lattice (B, +, ⋅). The following axioms are satisfied:

1. There exist at least two elements a, b in B and that a ≠b.

2. ∀a, b ∈B

(i) a+ b ∈B

(ii) a⋅b ∈B

3. for all a, b ∈B

(i) a+ b = b + a

(ii) a⋅b = b ⋅a

Commutative laws

4. Associative laws: for all a, b, c ∈B

(i) a+ (b + c) = (a + b) + c

(ii) a⋅(b ⋅c) = (a ⋅b) ⋅c

5. Distributive laws: for all a, b, c ∈B

(i) a+ (b ⋅c) = (a + b) ⋅(a + c)

(ii) a⋅(b + c) = (a ⋅b) + (a ⋅c)

6. (i) Existence of zero: There exists of B such that

a + 0 = a ∀a ∈B

The element 0 is called the zero element

(ii) Existence of unit: There exists 1 ∈B sum that

a⋅1 = a ∀a ∈B

The element 1 is called the unit element.

7. Existence of complement: ∀a ∈B there exists an element a′∈B such that

(i) a+ a′ = 1 and (ii) a ⋅a′ = 0

Sub-Boolean algebra-

Let (B, +, ⋅, ', 0, 1) be a Boolean algebra and S ≤B. If S contains the elements 0 and

1 and is closed under the operations +, and ⋅, then (S, +, ⋅, ', 0, 1) is called a sub-Boolean algebra.

5.4 Boolean functions, representation and minimization of Boolean functions

Boolean functions

Let (B, +, ⋅, ', 0, 1) be a Boolean algebra. A function: f: →B which is associatedwith a Boolean expression in n variables is called a Boolean function.

Boolean expression-

A Boolean expression or form, in n variables :is any finite string of symbols formed as given below:

1. 0 and 1 are Boolean expression.

2. are Boolean expressions.

3. If αand βare Boolean expression, then (α)(β)and (α)+(β) are also Boolean expressions.

4. If α is a Boolean expression then is also a Boolean expression.

5. No strings symbols except those formed in accordance with the above rules are Boolean expressions.

Equivalent Boolean expression-

Two Boolean expression α() and β() are said to be equivalent if one can be obtained from the other by a finite number of application of the identities of Boolean algebra.