Day 03Part 05- Discrete mathematics for computer science – Finding Relation from Hasse Diagram.

Discrete Mathematics – Finding Relations from Hasse Diagram

What is a Hasse Diagram?

A Hasse Diagram is a graphical representation of a partially ordered set (poset). It simplifies the relation by removing self-loops, transitive edges, and directions.

 Key Components of a Hasse Diagram:

1. Vertices (Nodes): Represent elements of the set.
2. Edges (Lines): Show the relation between elements. If there’s an edge from a to b, then a ≤ b.
3. No Self-Loops: A node doesn’t relate to itself.
4. No Transitive Edges: If a ≤ b and b ≤ c, the direct edge a ≤ c is removed.
5. No Direction Arrows: Direction is understood bottom to top.

 Steps to Find Relations from Hasse Diagram:

1. Identify All Elements: Write all elements in the set.
2. List Minimal Elements: Start from the bottom of the diagram.
3. Follow Relations: List the ordered pairs $(a,b)$ where there is a direct edge from a to b.
4. Include Reflexive Pairs: If reflexivity is needed, add $(a,a)$ for each element.
5. Check Transitivity: Ensure no missing pairs if transitivity is considered.

 Example:

Given a Hasse diagram with elements {1, 2, 3, 4}:

Relation Set (R):

• From 1 to 2 and 3: $(1,2),(1,3)$
• From 2 to 4: $(2,4)$
• From 3 to 4: $(3,4)$

Relation (R) = $\{(1,2),(1,3),(2,4),(3,4)\}$

If considering reflexive closure:
$R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,4),(3,4)\}$

Quick Tips:

1. Minimal and Maximal Elements: Bottom-most are minimal, top-most are maximal.
2. Chains and Antichains: Chains are sequences where each element is related, while antichains have no relations.
3. Transitive Closure: Ensure all indirect relations are captured if transitivity is required.

If you need a detailed explanation or more examples, feel free to ask!

Day 03Part 05- Discrete mathematics for computer science – Finding Relation from Hasse Diagram.

Draw a Hasse diagram for (A,) (divisibility relation), where

5-Discrete-Mathematics.pdf

DISCRETE MATHEMATICS

Great! Let’s dive into Discrete Mathematics for Computer Science — Day 03, Part 05, focusing on:

Finding Relations from a Hasse Diagram

What is a Hasse Diagram?

A Hasse Diagram is a simplified visual representation of a partially ordered set (poset). It helps us understand the relationships between elements in a set based on a partial order (like “less than or equal to”).

Key Concepts You Must Know First:

• A relation R on a set A is partially ordered if it is:

  • Reflexive

  • Antisymmetric

  • Transitive

Steps to Find Relation from a Hasse Diagram:

1. List All Elements of the Set

Start with the set shown in the diagram, say A = {a, b, c, d}.

2. Observe Direct Relations (Edges in the Diagram)

Each edge in the Hasse diagram shows a covering relation:
If there’s an edge from a to b, then a < b.

But remember:

• No arrows: The diagram assumes elements are going upward.

• Edges are direct relations, not reflexive or transitive.

3. Build the Partial Order Relation (≤)

From the diagram:

• Add the reflexive pairs: (a, a), (b, b), ...

• Include direct edges: e.g., (a, b)

• Add transitive pairs: e.g., if (a, b) and (b, c) then add (a, c)

Example Hasse Diagram:

Imagine this simple diagram:

From this:

• Elements: A = {a, b, c}

• Direct Relations:

  • a < c (edge from a to c)

  • b < c (edge from b to c)

Now build the relation R:

R = {

• Reflexive: (a,a), (b,b), (c,c)

• Direct: (a,c), (b,c)

• No (a,b) or (b,a), so not related directly
  }

Final Relation:

Tips for Solving in Exams or GATE:

• Always draw the diagram from bottom to top.

• Add reflexive and transitive pairs explicitly.

• If you’re asked to check lattice or total order, know the extra rules:

  • Lattice: Every two elements must have a least upper bound and greatest lower bound.

  • Total order: Every pair of elements is comparable.

Practice Problem

Given a Hasse Diagram with:

Find the relation R.

Solution:

• Elements: {2, 4, 5, 6}

• Direct: (2,4), (2,5), (4,6), (5,6)

• Add reflexive and transitive:

Would you like:

• A PDF worksheet of Hasse diagram problems?

• A video explanation of an example?

• Practice questions for GATE or university exams?

Let me know how you’d like to continue!

Day 03Part 05- Discrete mathematics for computer science – Finding Relation from Hasse Diagram.

DIGITAL NOTES ON Discrete Mathematics B.TECH II YEAR