[이산수학] Binary Relation

Binary Relation

이진 관계

 

[ Binary Relation ]

  Binary Relation

    : 두 집합의 원소들 간의 관계.

    : 두 집합 간의 Relation은 두 집합의 Cartesian Product로 나타낼 수 있으며, Pair 형태가 된다.

        ( A = {1, 2, 3}, B= {a, b, c}라고 하면 A×B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c), (3, a), (3, b), (3, c)} ) 

    : 자기 자신에 대한 Relation도 표현할 수 있으며, 원소의 갯수는 n²이 된다. ( A × A )

 

  Relation의 성질들

    · Reflexive Relation

      : ∀x [ x∈ U, (x, x) ∈ R ]

      : 모든 원소에 대하여 Self-loop이 성립하는 경우.

      : 행렬의 대각선 성분이 모두 1.

Reflexive Relation

    · Symmetric Relation

      : ∀x∀y [ (x, y) ∈ U → (y, x) ∈ U ]

      : Matrix가 대각선에 대해 대칭인 경우.

      : 한 쪽으로 가는 간선이 있는 경우, 반대 간선도 존재하는 경우.

         ( 명제의 Implication(→) 조건대로, 전제가 False이면 True인 것을 생각해야 함. 간선이 아예 없어도 True. )

Symmetric Relation

    · Anti-Symmetric Relation

      : ∀x∀y [ (x, y) ∈ U ∧ (y, x) ∈ U → x = y ]

      : Self-loop을 제외하고 주고 받는 간선이 없는 경우.

      : 반대칭행렬의 형태를 지니고 있다. (0과 1로 반대칭)

Anti-Symmetric Relation

    · Transitive Relation 

      : ∀x∀y∀z [ (x, y) ∈ U ∧ (y, z) ∈ U → (x, z) ∈ U ]

      : x에서 y로 가는 간선이 있고, y에서 z로 가는 간선이 있으면 x에서 z로 가는 간선이 존재.

      : 대소 관계 비교와 같은 경우 Transitive라고 할 수 있음.

          ( a < b, b < c이면 a < c )

      : Power(자기 자신에 대한 곱) 연산을 해도 Transitive를 유지. (부분집합이 됨) → Rⁿ ⊆ R ⇔ R is Transitive

Transitive Relation

 

[ Equivalence Relation ]

  Equivalence Relation

    : 동치 관계에 있는 Relation.

    : Reflexive, Symmetric, Transitive를 모두 만족.

    : 각각을 Partition(Disjoint Set)으로 나눌 수 있는 경우. (교집합이 없고, Union 시 전체 집합)

       ( 이 때 각각의 Partition을 Equvialence Class라고 한다. )

    : R이 Equivalent한 Relation이라 할 때, aRb 또는 [a] = [b] 또는 [a] ∩ [b] ≠ ∅ 로 나타낸다.

       ( aRb ⇔ [a] = [b] ⇔ [a] ∩ [b] ≠ ∅ ) → [a] ≠ [b] ⇔ [a] ∩ [b] = ∅ 

    : 절댓값 관계, String의 길이에 대한 관계 등

 

[ Ordering ]

  Partial Ordering

    : 일부 원소에 관하여 정렬이 가능한 관계에 있는 Relation.

    : Reflexive, Anti-Symmetric, Transitive를 모두 만족.

    : Poset (N, ≤) 으로도 나타낼 수 있음.

    : 대소관계, Divide 관계 등

 

  Total Ordering

    : 모든 원소에 관하여 정렬이 가능한 관계에 있는 Relation.

    : Hasse Diagram을 만들 수 있음.

       ( 그래프에서 Self-loop와 Transitive Edge를 제거해준 그래프 )

How to make Hasse Diagram

 

사진 출처 : notesformsc, Math24