TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Discrete Mathematics Lattices

Discrete Mathematics Lattices with introduction, sets theory, types of sets, set operations, algebra of sets, multisets, induction, relations, functions and algorithms etc.

<< Back to DISCRETE

Lattices:

Let L be a non-empty set closed under two binary operations called meet and join, denoted by ∧ and ∨. Then L is called a lattice if the following axioms hold where a, b, c are elements in L:

1) Commutative Law: -
(a) a ∧ b = b ∧ a           (b) a ∨ b = b ∨ a

2) Associative Law:-
(a) (a ∧ b)∧ c = a ∧(b∧ c)           (b) (a ∨ b) ∨ c = a ∨ (b ∨ c)

3) Absorption Law: -
(a) a ∧ ( a ∨ b) = a           (b) a ∨ ( a ∧ b) = a

Duality:

The dual of any statement in a lattice (L,∧ ,∨ ) is defined to be a statement that is obtained by interchanging ∧ an ∨.

For example, the dual of a ∧ (b ∨ a) = a ∨ a is           a ∨ (b ∧ a )= a ∧ a

Bounded Lattices:

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

Example:

  1. The power set P(S) of the set S under the operations of intersection and union is a bounded lattice since ∅ is the least element of P(S) and the set S is the greatest element of P(S).
  2. The set of +ve integer I+ under the usual order of ≤ is not a bounded lattice since it has a least element 1 but the greatest element does not exist.

Properties of Bounded Lattices:

If L is a bounded lattice, then for any element a ∈ L, we have the following identities:

  1. a ∨ 1 = 1
  2. a ∧1= a
  3. a ∨0=a
  4. a ∧0=0

Theorem: Prove that every finite lattice L = {a1,a2,a3....an} is bounded.

Proof: We have given the finite lattice:

          L = {a1,a2,a3....an}

Thus, the greatest element of Lattices L is a1∨ a2∨ a3∨....∨an.

Also, the least element of lattice L is a1∧ a2∧a3∧....∧an.

Since, the greatest and least elements exist for every finite lattice. Hence, L is bounded.

Sub-Lattices:

Consider a non-empty subset L1 of a lattice L. Then L1 is called a sub-lattice of L if L1 itself is a lattice i.e., the operation of L i.e., a ∨ b ∈ L1 and a ∧ b ∈ L1 whenever a ∈ L1 and b ∈ L1.

Example: Consider the lattice of all +ve integers I+ under the operation of divisibility. The lattice Dn of all divisors of n > 1 is a sub-lattice of I+.

Determine all the sub-lattices of D30 that contain at least four elements, D30={1,2,3,5,6,10,15,30}.

Solution: The sub-lattices of D30 that contain at least four elements are as follows:

1. {1, 2, 6, 30}          2. {1, 2, 3, 30}
3. {1, 5, 15, 30}          4. {1, 3, 6, 30}
5. {1, 5, 10, 30}          6. {1, 3, 15, 30}
7. {2, 6, 10, 30}

Isomorphic Lattices:

Two lattices L1 and L2 are called isomorphic lattices if there is a bijection from L1 to L2 i.e., f: L1⟶ L2, such that f (a ∧ b) =f(a)∧ f(b) and f (a ∨ b) = f (a) ∨ f (b)

Example: Determine whether the lattices shown in fig are isomorphic.

Solution: The lattices shown in fig are isomorphic. Consider the mapping f = {(a, 1), (b, 2), (c, 3), (d, 4)}.For example f (b ∧ c) = f (a) = 1. Also, we have f (b) ∧ f(c) = 2 ∧ 3 = 1

Lattices

Distributive Lattice:

A lattice L is called distributive lattice if for any elements a, b and c of L,it satisfies following distributive properties:

  1. a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
  2. a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

If the lattice L does not satisfies the above properties, it is called a non-distributive lattice.

Example:

  1. The power set P (S) of the set S under the operation of intersection and union is a distributive function. Since,
                        a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
              and, also a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪c) for any sets a, b and c of P(S).
  2. The lattice shown in fig II is a distributive. Since, it satisfies the distributive properties for all ordered triples which are taken from 1, 2, 3, and 4.
Lattices

Complements and complemented lattices:

Let L be a bounded lattice with lower bound o and upper bound I. Let a be an element if L. An element x in L is called a complement of a if a ∨ x = I and a ∧ x = 0

A lattice L is said to be complemented if L is bounded and every element in L has a complement.

Example: Determine the complement of a and c in fig:

Lattices

Solution: The complement of a is d. Since, a ∨ d = 1 and a ∧ d = 0

The complement of c does not exist. Since, there does not exist any element c such that c ∨ c'=1 and c ∧ c'= 0.

Modular Lattice:

A lattice (L, ∧,∨) is called a modular lattice if a ∨ (b ∧ c) = (a ∨ b) ∧ c whenever a ≤ c.

Direct Product of Lattices:

Let (L111)and (L222) be two lattices. Then (L, ∧,∨) is the direct product of lattices, where L = L1 x L2 in which the binary operation ∨(join) and ∧(meet) on L are such that for any (a1,b1)and (a2,b2) in L.

              (a1,b1)∨( a2,b2 )=(a11 a2,b12 b2)
and       (a1,b1) ∧ ( a2,b2 )=(a11 a2,b12 b2).

Example: Consider a lattice (L, ≤) as shown in fig. where L = {1, 2}. Determine the lattices (L2, ≤), where L2=L x L.

Lattices

Solution: The lattice (L2, ≤) is shown in fig:

Lattices
Next TopicBoolean Algebra




Related Links:


Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf