[DiscreteMath]관계

April 15, 2023

📚기본사항Permalink

📄관계Permalink

두 집합 X와 Y에 대하여 곱집합 X × Y의 부분집합 R을 X에서 Y로의 관계라고 말합니다. x와 y가 각각 X와 Y의 원소이고 $(x, y) \in R$ 이면 $x R y$ 로 표기하고, x는 y와 R의 관계가 있다라고 합니다. $(x, y) \notin R$ 이면 $x \overset{―}{R} y$ 로 표기하고, x는 y와 R의 관계가 없다라고 합니다. X, Y 두 집합이 X = Y를 만족하면 이들 사이의 관계 R을 X에서의 관계라고 합니다.

📚관계의 표현Permalink

📄화살표 도표Permalink

관계를 화살표 도표로 나타내는 방법은 예제를 통해 알아보겠습니다.
집합 A = {0, 1, 2}, 집합 B = {2, 3, 4}이 있을 때, A에서 B로의 관계 R은 $R = {(a, b) | b = a + 1, a \in A, b \in B}$ 로 정의된다고 해보겠습니다.

관계 R에 대한 화살표 도표를 그리면 아래와 같습니다.

📄부울 행렬Permalink

집합 X와 Y가 아래와 같이 있습니다.

X = {x_{1}, x_{2}, . . ., x_{m}}, Y = {y_{1}, y_{2}, . . ., y_{n}}

X에서 Y로의 관계 R은 다음과 같이 m × n 크기의 부울행렬 M_R로 나타낼 수 있습니다.

M_{R} = (\begin{matrix} a_{11} & a_{12} & . . . & a_{1 n} \\ a_{21} & a_{22} & . . . & a_{2 n} \\ . . . & . . . & . . . \\ a_{m 1} & a_{m 2} & . . . & a_{m n} \end{matrix}), a_{i j} = {\begin{cases} 1 : (x_{i}, y_{j}) \in R \\ 0 : (x_{i}, y_{j}) \notin R \end{cases}

위에서 화살표 도표로 나타냈던 R을 부울행렬로 나타내면 아래와 같습니다.

M_{R} = (\begin{matrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})

📄방향 그래프Permalink

두 점을 서로 연결하는 선으로 이루어진 도형을 그래프라고 하는데 그래프는 나중에 더 자세하게 다루겠습니다.

위에서 부울행렬로 표현했던 R을 방향그래프로 나타내면 아래와 같습니다.

📚관계의 성질Permalink

📄반사적(reflexive)Permalink

집합 A에서의 관계 R이 반사적이 되려면 A의 모든 원소가 자기 자신과 관계를 가져야합니다.

모 든 a \in A 에 대 해 (a, a) \in R

관계가 반사적일 경우 부울행렬의 대각원소가 모두 1인 것을 확인할 수 있습니다.

📄대칭적(symmetric)Permalink

집합 A에서의 관계 R이 대칭적이 되려면 R에 포함된 모든 원소가 대칭되는 관계를 가져야 합니다.

모 든 a, b \in A 에 대 해 (a, b) \in R 일 때 (b, a) \in R

관계가 대칭적일 경우 부울행렬이 대칭행렬이 됩니다.

📄추이적(transitive)Permalink

집합 A에서의 관계 R이 추이적이 되려면 R에 포함된 모든 원소들에 대해 $(a, b) \in R$ 이고, $(b, c) \in R$ 이면 $(a, c) \in R$ 이어야 합니다.

모 든 a, b, c \in A 에 대 해 (a, b) \in R 이 고 (b, c) \in R 일 때, (a, c) \in R

📚관계의 종류Permalink

📄역관계Permalink

집합 X에서 집합 Y로의 관계 R이 있을 때, 관계를 구성하는 각 순서쌍의 원소의 순서를 바꾸면 Y에서 X로의 관계가 되고, 이것을 역관계라고 합니다. $R^{- 1}$ 로 표기합니다.

R^{- 1} = {(y, x) | (x, y) \in R}

📄합성관계Permalink

집합 A에서 집합 B로의 관계 R이 있고, 집합 B에서 집합 C로의 관계 S가 있을 때, R을 적용하고 S를 적용하여 A에서 C로의 관계를 만들 수 있는데 이것을 합성관계라고 합니다.

S \cdot R = {(a, c) \in A \times C | a \in A, b \in B, c \in C, (a, b) \in R, (b, c) \in S}

❗️R을 적용하고 S를 적용하는 합성관계 기호가 $S \cdot R$ 로 표기되는 것을 주의합니다.

📄동치관계Permalink

집합 A에서의 관계 R이 반사적, 대칭적, 추이적이면 R은 동치관계라고 합니다.

집합 X에서의 관계 R이 있을 때, 임의의 원소 a, b, c에 대해 $(a, a) \in R_{(반 사 적)}$ 을 만족하고, $(a, b) \in R$ 이면 $(b, a) \in R_{(대 칭 적)}$ 을 만족하고, $(a, b) \in R$ 이고 $(b, c) \in R$ 일 때, $(a, c) \in R_{(추 이 적)}$ 를 만족하면 R을 동치관계라고 합니다.

나머지 함수
나머지 함수는 하나의 식의 나머지를 구하는 함수입니다. 간단하게 예를 들면, 5 mod 3 = 2이 됩니다.
모듈로 합동
두 정수 m, n에 대해 양의 정수 d로 나머지 연산을 했을 때, 같은 값이 나오는 경우가 있습니다. 이 경우 m과 n은 d에 관한 모듈로 합동이라고 합니다. 모듈로 합동은 기호로 m ≡ n (mod d)이라고 표기합니다. m ≡ n (mod d)를 만족하는 (m, n)의 순서쌍들의 집합을 관계 R이라 했을 때, 다음을 만족합니다.
- (반사적) 임의의 a에 대해 a ≡ a (mod d)
- (대칭적) a ≡ b (mod d)이면, b ≡ a (mod d)
- (추이적) a ≡ b (mod d)이고, b ≡ c (mod d)이면, a ≡ c (mod d)

모듈로 합동은 반사적, 대칭적, 추이적 성질을 만족하므로 동치관계입니다. 또한 d에 임의의 자연수를 대입하더라도 항상 반사적, 대칭적, 추이적이므로 모듈로 합동은 항상 동치관계입니다.

예를 들어, 6 ≡ 16 (mod 10)은 6 mod 10 = 6, 16 mod 10 = 6이므로 모듈로 합동입니다.

📄동치류Permalink

집합 A에서의 관계 R이 동치관계일 때, A의 각 원소 a에 대하여 a의 동치류는 a와 R의 관계를 가지는 A의 원소들의 집합이며, [a]로 표기합니다.

[a] = {x | x \in A, (a, x) \in R}

Share on

Twitter Facebook LinkedIn

Juwon Cha