[이산수학] 관계

관계

---

1. 관계(Relation)

이산수학에서 관계는 한 집합의 원소와 다른 집합 원소 간의 연관성을 표현하는 것에 중점을 둡니다. 관계를 나타내는 일반적인 기호로는 R을 사용하며, 집합 X, Y의 원소인 x, y가 R의 관계를 가지고 있을 때 xRy라고 표현합니다. 이 때 R은 집합 X, Y의 곱집합의 부분집합 개념이기도 합니다. 그리고 X, Y의 관계처럼 2개 집합의 관계를 "이항 관계(Binary relation)"라고 정의합니다.

 

이러한 관계는 순서쌍의 집합, 화살표 도표, 부울행렬 등 다양한 방법으로 표현할 수 있습니다.

 

2. 관계의 성질

2.1. 반사성(Reflexivity)

모든 x ∈ A에 대해 xRx를 만족하면, R은 반사적이라고 합니다.

 

2.2. 대칭성(Symmetry)

모든 x, y ∈ A에 대해 xRy일 때 yRx가 성립한다면, R은 대칭적이라고 합니다.

 

2.3. 추이성(Transitivity)

모든 x, y, z ∈ A에 대해 xRy이고 yRz일 때 xRz가 성립한다면, R은 추이적이라고 합니다.

 

3. 관계의 종류

3.1. 역관계(Inverse relation)

관계 R이 집합 A에서 집합 B로의 이항 관계라고 할 때, R의 역관계는 집합 B에서 집합 A로의 관계를 의미합니다. R의 역관계는 R-1로 표현합니다.

R-1= {(y, x) | (x, y) ∈ R}

 

3.2. 합성관계(Composite relation)

합성은 2개 이상의 관계를 합성하여 새로운 관계를 만드는 것을 의미합니다. 관계 R과 S의 합성관계는 R ∘ S라고 표현합니다.

R: 집합 A에서 집합 B로의 관계
S: 집합 B에서 집합 C로의 관계

R ∘ S = {(a, c) ∈ A × C ∣ a ∈ A, b ∈ B, c ∈ C, (a, b) ∈ R and (b, c) ∈ S}

 

3.3. 동치관계(Equivalence relation)

동치관계는 반사성, 대칭성, 추이성을 모두 만족하는 관계를 의미합니다. 대표적인 동치관계로는 나머지를 연산하는 모듈로 연산(mod)의 "모듈로 합동"이 있습니다.

(예시)
m mod n = (m를 n으로 나눈 나머지)
(반사성) a ≡ a mod k
(대칭성) a ≡ b mod k이면, b ≡ a mod k
(추이성) a ≡ b mod k이고, b ≡ c mod k이면, a ≡ c mod k

---

연관 게시글

[이산수학] 이산수학?

[이산수학] 이산수학?

---

참조

•