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

Ali Seron Jason

1 month ago

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

Contents

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.

Commutative Laws:
- $\lor b = b \lor a$
- $\land b = b \land a$
Associative Laws:
- $\lor (b \lor c) = (a \lor b) \lor c$
- $\land (b \land c) = (a \land b) \land c$
Absorption Laws:
- $\lor (a \land b) = a$
- $\land (a \lor b) = a$
Idempotent Laws:
- $\lor a = a$
- $\land a = a$

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

Bounded Lattice:
- Contains both a least element (0) and a greatest element (1).
- For all $a$ in the lattice: $\leq a \leq 1$ .
Distributive Lattice:
- Satisfies the distributive laws:
  - $\lor (b \land c) = (a \lor b) \land (a \lor c)$
  - $\land (b \lor c) = (a \land b) \lor (a \land c)$
- A lattice is distributive if it does not contain sublattices isomorphic to $M_3$ or $N_5$ .
Modular Lattice:
- Satisfies the modular law: If $\leq c$ , then $\lor (b \land c) = (a \lor b) \land c$ .
Complemented Lattice:
- A bounded lattice where every element $a$ has a complement $b$ such that:
  - $\lor b = 1$
  - $\land b = 0$
Complete Lattice:
- Every subset has both a join and a meet.
- All finite lattices are complete.

Consider the set $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.