Day 03Part 15-Discrete mathematics for computer science-Properties of lattices with example.

Day 03Part 15-Discrete mathematics for computer science-Properties of lattices with example.

Here is a concise overview of lattices in discrete mathematics, focusing on their properties with examples, suitable for GATE CSE/IT preparation:

What is a Lattice?

A lattice is a partially ordered set (POSET) in which every pair of elements has both:

• Least Upper Bound (LUB), also known as join (denoted by $a\vee b$)

• Greatest Lower Bound (GLB), also known as meet (denoted by $a\wedge b$)

This structure ensures that for any two elements in the set, both their join and meet exist.

Key Properties of Lattices

1. Commutative Laws:

   • $a\vee b=b\vee a$

   • $a\wedge b=b\wedge a$

2. Associative Laws:

   • $a\vee (b\vee c)=(a\vee b)\vee c$

   • $a\wedge (b\wedge c)=(a\wedge b)\wedge c$

3. Absorption Laws:

   • $a\vee (a\wedge b)=a$

   • $a\wedge (a\vee b)=a$

4. Idempotent Laws:

   • $a\vee a=a$

   • $a\wedge a=a$

These properties define the algebraic structure of lattices and are fundamental in their analysis.

Types of Lattices

1. Bounded Lattice:

   • Contains both a least element (0) and a greatest element (1).

   • For all $a$ in the lattice: $0\le a\le 1$.

2. Distributive Lattice:

   • Satisfies the distributive laws:

     • $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$

     • $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$

   • A lattice is distributive if it does not contain sublattices isomorphic to M3M_3M3​ or N5N_5N5​.

3. Modular Lattice:

   • Satisfies the modular law: If $a\le c$, then $a\vee (b\wedge c)=(a\vee b)\wedge c$.

4. Complemented Lattice:

   • A bounded lattice where every element $a$ has a complement $b$ such that:

     • $a\vee b=1$

     • $a\wedge b=0$

5. Complete Lattice:

   • Every subset has both a join and a meet.

   • All finite lattices are complete.

Example: Power Set Lattice

Consider the set $A=\{1,2\}$. Its power set is:

$$\mathcal{P}(A)=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$$

With the subset relation ($\subseteq$), this forms a lattice where:

• Join ($\vee$): Union of sets

• Meet ($\wedge$): Intersection of sets

This lattice is bounded, distributive, complemented, and complete.

Recommended Video Lectures

For a visual and detailed explanation of lattice properties, you may refer to the following lectures:

• Properties of Lattice with Proofs: This lecture discusses various properties of lattices with proofs.

• Properties of Lattice in Discrete Mathematics: This video covers properties of lattices in discrete mathematics.

If you need further examples, practice problems, or explanations on specific types of lattices, feel free to ask!

Day 03Part 15-Discrete mathematics for computer science-Properties of lattices with example.

DIGITAL NOTES ON Discrete Mathematics B.TECH II YEAR

Notes on Discrete Mathematics