{"id":3078,"date":"2025-06-07T09:49:14","date_gmt":"2025-06-07T09:49:14","guid":{"rendered":"https:\/\/diznr.com\/?p=3078"},"modified":"2025-06-07T09:49:14","modified_gmt":"2025-06-07T09:49:14","slug":"part-10-discrete-mathematics-for-computer-science-equivalence-relation-and-use-its","status":"publish","type":"post","link":"https:\/\/www.reilsolar.com\/pdf\/part-10-discrete-mathematics-for-computer-science-equivalence-relation-and-use-its\/","title":{"rendered":"Part 10 – Discrete mathematics for computer science – Equivalence relation and it’s use."},"content":{"rendered":"

Part 10 – Discrete mathematics for computer science – Equivalence relation and it’s use.<\/p>\n

[fvplayer id=”241″]<\/p>\n

Equivalence Relation in Discrete Mathematics<\/strong><\/h3>\n

An equivalence relation<\/strong> is a relation that satisfies three key properties:<\/p>\n

    \n
  1. Reflexivity<\/strong>: aRaaRa<\/span>a<\/span>R<\/span>a<\/span><\/span><\/span><\/span> for all aa<\/span>a<\/span><\/span><\/span><\/span> in set AA<\/span>A<\/span><\/span><\/span><\/span>.<\/li>\n
  2. Symmetry<\/strong>: If aRbaRb<\/span>a<\/span>R<\/span>b<\/span><\/span><\/span><\/span>, then bRabRa<\/span>b<\/span>R<\/span>a<\/span><\/span><\/span><\/span>.<\/li>\n
  3. Transitivity<\/strong>: If aRbaRb<\/span>a<\/span>R<\/span>b<\/span><\/span><\/span><\/span> and bRcbRc<\/span>b<\/span>R<\/span>c<\/span><\/span><\/span><\/span>, then aRcaRc<\/span>a<\/span>R<\/span>c<\/span><\/span><\/span><\/span>.<\/li>\n<\/ol>\n

    Example of Equivalence Relation<\/strong><\/h4>\n

    Consider a relation RR<\/span>R<\/span><\/span><\/span><\/span> on a set of integers where aRbaRb<\/span>a<\/span>R<\/span>b<\/span><\/span><\/span><\/span> if a\u2261bmod\u2009\u20093a \\equiv b \\mod 3<\/span>a<\/span>\u2261<\/span><\/span>b<\/span><\/span>mod<\/span><\/span>3<\/span><\/span><\/span><\/span>. This means that two numbers are related if they have the same remainder when divided by 3.<\/p>\n

    \u00a0Reflexive: a\u2261amod\u2009\u20093a \\equiv a \\mod 3<\/span>a<\/span>\u2261<\/span><\/span>a<\/span><\/span>mod<\/span><\/span>3<\/span><\/span><\/span><\/span> (always true)
    \u00a0Symmetric: If a\u2261bmod\u2009\u20093a \\equiv b \\mod 3<\/span>a<\/span>\u2261<\/span><\/span>b<\/span><\/span>mod<\/span><\/span>3<\/span><\/span><\/span><\/span>, then b\u2261amod\u2009\u20093b \\equiv a \\mod 3<\/span>b<\/span>\u2261<\/span><\/span>a<\/span><\/span>mod<\/span><\/span>3<\/span><\/span><\/span><\/span>
    \u00a0Transitive: If a\u2261bmod\u2009\u20093a \\equiv b \\mod 3<\/span>a<\/span>\u2261<\/span><\/span>b<\/span><\/span>mod<\/span><\/span>3<\/span><\/span><\/span><\/span> and b\u2261cmod\u2009\u20093b \\equiv c \\mod 3<\/span>b<\/span>\u2261<\/span><\/span>c<\/span><\/span>mod<\/span><\/span>3<\/span><\/span><\/span><\/span>, then a\u2261cmod\u2009\u20093a \\equiv c \\mod 3<\/span>a<\/span>\u2261<\/span><\/span>c<\/span><\/span>mod<\/span><\/span>3<\/span><\/span><\/span><\/span><\/p>\n

    Use of Equivalence Relations<\/strong><\/h4>\n
      \n
    1. Partitioning a Set<\/strong> \u2013 Equivalence relations divide a set into disjoint equivalence classes<\/strong>.<\/li>\n
    2. Modular Arithmetic<\/strong> \u2013 Used in cryptography and computer science.<\/li>\n
    3. Graph Theory<\/strong> \u2013 Helps in clustering similar nodes.<\/li>\n
    4. State Reduction in Automata<\/strong> \u2013 Used in minimizing finite automata.<\/li>\n<\/ol>\n

      Would you like some practice problems or examples on equivalence relations?<\/p>\n

      Part 10 – Discrete mathematics for computer science – Equivalence relation and it’s use.<\/a><\/h3>\n

      Notes on Discrete Mathematics<\/a><\/h3>\n

      Here\u2019s a detailed and easy-to-understand explanation of Equivalence Relation<\/strong> from Discrete Mathematics \u2013 Part 10<\/strong>, especially useful for Computer Science<\/strong>, Engineering<\/strong>, or GATE<\/strong> aspirants:<\/p>\n

      \n

      \ud83d\udcd8 Part 10 \u2013 Discrete Mathematics for Computer Science<\/strong><\/h2>\n

      \ud83d\udd17 Equivalence Relation and Its Use<\/strong><\/h2>\n
      \n

      \u2705 Definition:<\/strong><\/h3>\n

      A relation R<\/strong> on a set A<\/strong> is called an Equivalence Relation<\/strong> if it satisfies all three<\/strong> properties:<\/p>\n

        \n
      1. \n

        Reflexive<\/strong> \u2013 Every element is related to itself.<\/p>\n

        \n

        (a, a) \u2208 R for all a \u2208 A<\/p>\n<\/blockquote>\n<\/li>\n

      2. \n

        Symmetric<\/strong> \u2013 If a is related to b, then b is related to a.<\/p>\n

        \n

        (a, b) \u2208 R \u21d2 (b, a) \u2208 R<\/p>\n<\/blockquote>\n<\/li>\n

      3. \n

        Transitive<\/strong> \u2013 If a is related to b and b to c, then a is related to c.<\/p>\n

        \n

        (a, b) \u2208 R and (b, c) \u2208 R \u21d2 (a, c) \u2208 R<\/p>\n<\/blockquote>\n<\/li>\n<\/ol>\n

        \n

        \ud83d\udd0d Example:<\/strong><\/h3>\n

        Let A = {1, 2, 3, 4}
        Define R on A as: R = { (1,1), (2,2), (3,3), (4,4), (1,2), (2,1) }<\/p>\n