[go: up one dir, main page]
Scribd
Upload
108 views11 pages

Lattice and Its Property ##

The document defines and provides examples of lattices, partially ordered sets (posets), and Hasse diagrams. It explains that a lattice is a poset where every pair of elements has a greatest lower bound and least upper bound. Examples of different types of lattices such as bounded, complemented, and distributive lattices are given. Properties of lattices like idempotent, absorption, commutative, and associative properties are also listed.

Uploaded by

chandan.thakur
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
108 views11 pages

Lattice and Its Property ##

The document defines and provides examples of lattices, partially ordered sets (posets), and Hasse diagrams. It explains that a lattice is a poset where every pair of elements has a greatest lower bound and least upper bound. Examples of different types of lattices such as bounded, complemented, and distributive lattices are given. Properties of lattices like idempotent, absorption, commutative, and associative properties are also listed.

Uploaded by

chandan.thakur
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

2.

Lattices
Lattice

A lattice is a poset (L, ≤) for which every pair {a, b} ∈ L has a least upper bound
(denoted by a ∨ b) and a greatest lower bound (denoted by a ∧ b). LUB ({a,b}) is called the join
of a and b. GLB ({a,b}) is called the meet of a and b.

Example

This above figure is a lattice because for every pair {a, b} ∈ L, a GLB and a LUB exists.

VEMU, Dept of CSE Page 63


This above figure is a not a lattice because GLB (a, b) and LUB (e, f) does not exist.

Some other lattices are discussed below −

Bounded Lattice

A lattice L becomes a bounded lattice if it has a greatest element 1 and a least element 0.

Complemented Lattice

A lattice L becomes a complemented lattice if it is a bounded lattice and if every element in the
lattice has a complement. An element x has a complement x’ if ∃x(x ∧ x’= 0 and x ∨ x’ = 1)

Distributive Lattice

If a lattice satisfies the following two distribute properties, it is called a distributive lattice.

• a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
• a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)

Modular Lattice

If a lattice satisfies the following property, it is called modular lattice.

a ∧( b ∨ (a ∧ d)) = (a ∧ b) ∨ (a ∧ d)

Properties of Lattices
Idempotent Properties

• a ∨a = a
• a ∧a = a

VEMU, Dept of CSE Page 64


Absorption Properties

• a ∨ (a ∧ b) = a
• a ∧ (a ∨ b) = a

Commutative Properties

• a ∨b = b ∨a
• a ∧b = b ∧a

Associative Properties

• a ∨ (b ∨ c) = (a ∨ b) ∨ c
• a ∧ (b ∧ c) = (a ∧ b) ∧ c

Dual of a Lattice

The dual of a lattice is obtained by interchanging the ‘∨’ and ‘∧’ operations.

Example

The dual of [a ∨ (b ∧ c)] is [a ∧ (b ∨ c)]

Partially Ordered Set (POSET)

A partially ordered set consists of a set with a binary relation which is reflexive, antisymmetric
and transitive. "Partially ordered set" is abbreviated as POSET.

Examples

• The set of real numbers under binary operation less than or equal to (≤) is a poset.

Let the set S = {1, 2, 3} and the operation is ≤

The relations will be {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3)}

This relation R is reflexive as {(1, 1), (2, 2), (3, 3)} ∈ R

This relation R is anti-symmetric, as

{(1, 2), (1, 3), (2, 3)} ∈ R and {(1, 2), (1, 3), (2, 3)} ∉ R

This relation R is also transitive. Hence, it is a poset.

• The vertex set of a directed acyclic graph under the operation ‘reachability’ is a poset.

VEMU, Dept of CSE Page 65


Hasse Diagram

The Hasse diagram of a poset is the directed graph whose vertices are the element of that poset
and the arcs covers the pairs (x, y) in the poset. If in the poset x<y, then the point x appears lower
than the point y in the Hasse diagram.If x<y<z in the poset, then the arrow is not shown between
x and z as it is implicit.

Example

The poset of subsets of {1, 2, 3} = {φ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} is shown
by the following Hasse diagram −

Linearly Ordered Set

A Linearly ordered set or Total ordered set is a partial order set in which every pair of element is
comparable. The elements a, b ∈ S are said to be comparable if either a ≤ b or b ≤ a holds.
Trichotomy law defines this total ordered set. A totally ordered set can be defined as a
distributive lattice having the property {a ∨ b, a ∧ b} = {a, b} for all values of a and b in set S.

Example

The powerset of {a, b} ordered by ⊆ is a totally ordered set as all the elements of the
power set P = {φ, {a}, {b}, {a, b}} are comparable.

Example of non-total order set

A set S = {1, 2, 3, 4, 5, 6} under operation x divides y is not a total ordered set.

Here, for all (x, y) ∈ S, x ≤ y have to hold but it is not true that 2 ≤ 3, as 2 does not divide 3 or 3
does not divide 2. Hence, it is not a total ordered set.

VEMU, Dept of CSE Page 66


VEMU, Dept of CSE Page 67
VEMU, Dept of CSE Page 68
VEMU, Dept of CSE Page 69
VEMU, Dept of CSE Page 70
VEMU, Dept of CSE Page 71
VEMU, Dept of CSE Page 72
VEMU, Dept of CSE Page 73

You might also like