[이산수학] 관계

관계의 개념

---

• 관계(relation: R: A→B, aRb) / 이항관계(binary relation): 집합 A, B가 있을 때 집합 A에서 집합 B로 가는 관계로, R은 A x B의 부분집합이다. a∈A, b∈B일 때, (a, b)∈R이면 aRb, (a, b) ∉ R이면 aR/b 이라고 표현한다.
• 정의역(domain: dom(R)): 집합 A에서 집합 B로 가는 이항관계 R에 속한 순서쌍의 첫 번째 원소가 포함된 집합, 즉 집합 A를 말한다. dom(R) = {a | a ∈ A}
• 공역(codomain: codom(R)): 집합 A에서 집합 B로 가는 이항관계 R에 속한 순서쌍의 두 번째 원소가 포함된 집합, 즉 집합 B를 말한다. codom(R) = {b | b ∈ B}
• 치역(range: ran(R)): 집합 A에서 집합 B로 가는 이항관계 R에 속한 순서쌍의 두 번째 원소를 모아놓은 집합, 즉 공역의 부분집합을 말한다. ran(R) = {b | (a, b) ∈ R}
• n항 관계: n개의 집합 A1, A2, ..., An이 있을 때 A1 x A2 x ... x An의 부분집합을 말한다.
• 역관계(inverse relation: R-1): 집합 A에서 집합 B로의 관계 R이 있을 때, 집합 B에서 집합 A로의 관계를 말한다. R-1 = {(b, a) ∈ B x A | (a, b) ∈ R}

 

관계의 표현

---

• 화살표 선도: 집합 A에서 집합 B로 가는 관계 R이 있을 때, 두 집합의 원소 간의 관계를 화살표로 나타낸 도표를 말한다.

관계 R의 역관계와 화살표 선도

• 좌표도표: 집합 A에서 집합 B로 가는 관계 R이 있을 때, 집합 A(정의역)의 원소를 x축에, 집합 B(공역)의 원소를 y축에 표시하여 관계 R을 좌표로 나타낸 도표를 말한다.

관계 R의 역관계와 좌표도표

• 관계행렬: 원소가 m개인 집합 A = {a1, a2, ..., am}와 원소가 n개인 집합 B = {b1, b2, ..., bn}가 있을 때, 집합 A에서 집합 B로 가는 관계 R을 나타낸 m x n 행렬 MR = [mij]를 말한다.

mij = 1, (ai, bj) ∈ R / 0, (ai, bj) ∉ R

관계 R의 역관계와 관계행렬

• 방향그래프: 하나의 집합 A에서 집합 A로 가는 관계 R을 꼭짓점과 화살표를 이용하여 나타낸 그래프를 말한다.

관계 R의 역관계와 방향그래프

 

관계의 성질

---

• 반사관계: 집합 A에 대한 관계 R이 있을 때, 모든 a ∈ A에 대해 (a, a) ∈ R인 관계를 말한다.

반사관계

• 비반사관계: 집합 A에 대한 관계 R이 있을 때, 모든 a ∈ A에 대해 (a, a) ∉ R인 관계를 말한다.

비반사관계

• 대칭관계: 집합 A에 관한 관계 R이 다음을 만족하면 대칭관계라 한다. 어떤 a, b ∈ A에 대해서 aRb이면 bRa이다.
• 비대칭 관계: 집합 A에 관한 관계 R이 다음을 만족하면 비대칭관계라 한다. 어떤 a, b ∈ A에 대해서 aRb이면 bR/a이다.
• 반대칭관계: 집합 A에 관한 관계 R이 다음을 만족하면 반대칭관계라 한다. 어떤 a, b ∈ A에 대해서 aRb이고 bRa이면 a = b이다. 즉, a, b ∈ A에 대해서 𝑎≠𝑏이면 aR/b이거나 bR/a인 관계를 말한다.
• 추이관계: 집합 A에 대한 관계 R이 있을 때, 어떤 a, b, c ∈ A에 대해 (a, b) ∈ R이고 (b, c) ∈ R이면 (a, c) ∈ R인 관계를 말한다.

 

합성관계

---

• 합성관계: 집합 A에서 집합 B로의 관계 R과 집합 B에서 집합 C로의 관계 S가 있을 때, 이 두 관계를 이용해 구하는 집합 A에서 집합 C로의 관계를 말한다.                                                  S º R = {(a, c) ∈ A x C | a ∈ A, b ∈ B, c ∈ C, (a, b) ∈ R, (b, c) ∈ S}
• 합성관계는 교환법칙이 성립하지 않는다. 그리고 관계 R의 공역과 관계 S의 정의역이 같아야(또는 그 반대) 합성이 가능하다.

합성 관계

• 합성관계 예시)

합성관계 예

• 합성관계의 거듭제곱(R^n): 집합 A에 대한 관계 R에 대하여 n번의 합성으로 구하는 합성관계를 말한다. R^n = R (n=1일 때) / R^(n-1) (n>1일 때)
• 추이관계와 거듭제곱의 관계: 집합 A에 대한 관계 R이 추이관계일 필요충분조건은 모든 양의 정수 n에 대하여 R^n ⊆ R인 것이다.
• 예시)

합성관계와 추이관계

 

관계의 폐포

---

• 관계의 폐포(closure): 집합 A에 대한 관계를 R이라 하고 관계 R이 가져야 하는 성질을 P라고 할 때, 관계 R을 포함하면서 성질 P를 갖는 집합 A에 대한 관계 S를 말한다.
• 반사폐포: 집합 A에 대한 관계 R을 포함하면서 반사관계를 갖는 관계 S를 말한다. S = R ∪ {(a, a) | a ∈ A}

반사폐포

• 대칭폐포: 집합 A에 대한 관계 R을 포함하면서 대칭관계를 갖는 관계 S를 말한다.                 S = R ∪ {(b, a) ∈ A x A | (a, b) ∈ R} = R ∪ R-1

대칭폐포

• 추이폐포: 집합 A에 대한 관계 R을 포함하면서 추이관계를 갖는 관계 S를 말한다.                 S = R ∪ {(a, c) ∈ A x A | (a, b) ∈ R ∧ (b, c) ∈ R}
• 연결관계(R*): 집합 A에 대한 관계 R에 대하여,

연결관계

• 관계 R의 연결관계 R*은 관계 R의 추이폐포이다.

 

동치관계와 부분순서관계

---

• 동치관계: 반사관계, 대칭관계, 추이관계가 모두 성립하는 관계를 말한다. (반대추)

동치관계

• 동치류([a]): 집합 A에 대한 관계 R이 동치관계일 때, 집합 A의 각 원소 a와 순서쌍을 이루는 원소들의 집합을 말한다. [a] = {x | (a, x) ∈ R}
• 동치류의 분할: 집합 A에 대한 관계 R이 동치관계일 때, 동치류 집합 S = {A1, A2, ..., Ak}는 다음과 같은 특징을 갖는다.

1. i = 1, 2, ..., k일 때, Ai ≠ ∅
2. Ai ⊆ A
3. i ≠ j이면, Ai ∩ Aj = ∅

 

• 부분순서관계: 반사관계, 빈대칭관계, 추이관계가 성립하는 관계를 말한다. (반반대추)

부분순서관계

• 부분순서집합: 집합 A에 대한 관계 R이 부분순서관계일 때, 집합 A를 말한다.
• 비교 가능: 집합 A에 대한 관계 R이 부분순서관계이고 a, b ∈ A이고, (a, b) ∈ R 또는 (b, a) ∈ R일 때, 'a와 b는 비교 가능'하다.
• 비교 불가능: 집합 A에 대한 관계 R이 부분순서관계이고 (a, b) ∉ R 또는 (b, a) ∉ R일 때, 'a와 b는 비교 불가능'하다.
• 완전순서관계와 완전순서집합: 집합 A에 대한 관계 R이 부분순서관계일 때, 집합 A의 모든 원소가 그 관계에서 비교 가능하면 그 관계 R을 완전순서관계라 하고 집합 A를 완전순서집합이라고 한다.

 

궁금한 것이나 잘못된 것이 있다면 댓글에 남겨주세요!