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

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