DIZNR INTERNATIONAL

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.

https://www.gyanodhan.com/video/7B4.%20GATE%20CSEIT/Discrete%20Mathematics%201/489.%20Day%2003Part%2015-Discrete%20mathematics%20for%20computer%20science-Properties%20of%20lattices%20with%20example.mp4

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:

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∨b=b∨aa \lor b = b \lor a

    • a∧b=b∧aa \land b = b \land a

  2. Associative Laws:

    • a∨(b∨c)=(a∨b)∨ca \lor (b \lor c) = (a \lor b) \lor c

    • a∧(b∧c)=(a∧b)∧ca \land (b \land c) = (a \land b) \land c

  3. Absorption Laws:

    • a∨(a∧b)=aa \lor (a \land b) = a

    • a∧(a∨b)=aa \land (a \lor b) = a

  4. Idempotent Laws:

    • a∨a=aa \lor a = a

    • a∧a=aa \land 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 aa in the lattice: 0≤a≤10 \leq a \leq 1.

  2. Distributive Lattice:

    • Satisfies the distributive laws:

      • a∨(b∧c)=(a∨b)∧(a∨c)a \lor (b \land c) = (a \lor b) \land (a \lor c)

      • a∧(b∨c)=(a∧b)∨(a∧c)a \land (b \lor c) = (a \land b) \lor (a \land c)

    • A lattice is distributive if it does not contain sublattices isomorphic to M3M_3 or N5N_5.

  3. Modular Lattice:

    • Satisfies the modular law: If a≤ca \leq c, then a∨(b∧c)=(a∨b)∧ca \lor (b \land c) = (a \lor b) \land c.

  4. Complemented Lattice:

    • A bounded lattice where every element aa has a complement bb such that:

      • a∨b=1a \lor b = 1

      • a∧b=0a \land 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}A = \{1, 2\}. Its power set is:

P(A)={∅,{1},{2},{1,2}}\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}

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

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:


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