toc {:toc}

5.1 관계와 이항 관계

관계 : 집합에서의 원소들 간의 순서를 고려한 것, 데카르트 곱의 부분집합
이항 관계(R) : 두 집합 A, B에 대하여, A로부터 B로의 이항 관계 R은 두 집합의 곱집합 A x B의 부분집합이다.
- 관계에 대한 표기
- : a와 b가 관계가 있는 경우
- : a와 b가 관계가 없는 경우
정의역 : A, B 사이에 B가 A와 관계로 나타내어질 때, A에 속한 전체 원소
공변역 : A, B 사이에 B가 A와 관계로 나타내어질 때, B에 속한 전체 원소
치역 : A, B 사이에 B가 A와 관계로 나타내어질 때, 관계가 있는 B의 원소
관계에서는 교환법칙이 성립하지 않는다.
카티시안 곱 / 곱집합 : A와 B가 집합일 때 (a, b)로 구성된 모든 순서쌍의 집합 ()
A x B x C와 같은 경우 순서쌍을 구할 때 트리를 활용하면 보다 체계적으로 구할 수 있다.
역관계 : 집합 A에서 집합 B로의 관계 R에 대한 역관계 는 집합 B에서 집합 A로의 관계를 나타낸다.
- 역관계 순서쌍 내의 순서 (b, a) → (a, b)로 순서를 바꾸면 순서쌍은 관계 R에 속하게 된다.
- 관계가 있어야 역관계가 존재한다.

5.2 관계의 표현

화살표 도표

a가 집합 A의 원소이고 b가 집합 B의 원소라고 하면, 일 경우 집합 A에 있는 원소 a에서 집합 B에 있는 원소 b로 화살표를 그려서 관계를 표현한다.

[Fig1]

좌표 도표

집합 A의 원소를 x축 위의 점으로 표시하고 집합 B의 원소를 y축 위의 점으로 생각하여, 와 가 관계가 있으면 a를 가리키는 x 좌표축과 b를 가리키는 y 좌표축이 만나는 곳에 점으로 표시한다.

[Fig2]

방향 그래프

관계 R이 두 집합 A와 B 사이의 관계가 아닌 하나의 집합 A에 대한 관계일 때, 집합 A의 각 원소를 그래프의 정점으로 표시하고 일 경우 a에서 b로의 화살표가 있는 연결선으로 표현하는 것

[Fig3]

관계 행렬

부울 행렬을 이용하는 방식
정의역을 행, 공변역을 열로 취한다.

5.3 합성 관계

합성 관계 : 세 집합 A, B, C에서 을 집합 A에서 집합 B로의 관계라 하고, 를 집합 B에서 집합 C로의 관계라 하면, 집합 A에서 집합 C로의 합성관계 또는 으로 표현한다.

항등 관계 : 를 항등 관계라 한다.
항등관계는 다음의 성질을 갖는다.
- 반사 관계
- 대칭 관계
- 반대칭 관계
- 추이 관계계

5.4 관계의 성질

반사 관계

반사 관계 : 집합 A에 있는 모든 원소 x에 대하여 이면, 즉 인 경우
- 관계 R에 대한 방향 그래프를 그랬을 때 그래프의 모든 정점에서 자기 자신을 가리키는 화살표가 있어야 반사 관계가 성립된다.
- 즉, 하나라도 집합 A에 대해 자기 자신과의 관계가 없으면 반사 관계가 아니다.
비반사 관계 : 집합 A의 모든 원소에 대하여 인 경우
- R의 원소 중 자기 자신과 관계가 있는 원소가 하나도 존재하지 않는 경우를 말한다.

대칭 관계

대칭 관계 : 집합 A에 있는 원소 x, y에 대해 일 때 이면 관계 R을 대칭 관계라 한다.
방향그래프에서 반드시 양방향으로 화살표가 있어야 한다. 반사 관계 그림에서 c는 대칭 관계가 아니다.

{: width = 250, height = 300}[Fig4]

반대칭 관계

반대칭 관계 : 집합 A에 있는 모든 원소 x, y에 대하여 이고 일 때 x = y인 관계를 만족하는 관계 R
R이 반대칭 관계일 때, 이고, 이면 이 되어야 한다.
즉, 반대칭 관계는 대각원소를 제외하고는 대칭되면 안 된다.
이는 곧, 의 경우와 같이 자기 자신에 대한 반사 관계를 가지면서 다른 원소들과 대칭 관계가 없을 경우, 대칭 관계도 되고 반대칭 관계도 될 수 있다.

[Fig5]

추이 관계

집합 A에 있는 원소 x, y, z에 대하여 관계 R이 이고 인 관계를 만족할 때 관계 R을 말한다.

(b, a), (a, c)의 관계를 갖지만 (b, c)의 관계를 갖지 않기 때문에 추이 관계가 아니다.
(1, 4), (4, 3)의 관계를 갖고 (1, 3)의 관계를 갖기 때문에 추이 관계이다.

추이 클로우저(transitive closure)

만약 이면 이다.
이고 이면 이다.
1, 2 번을 제외하고는 어떤 것도 에 속하지 않는다.

추이 클로우저는 관계 R에 추이 관계를 추가한 것이라 생각하면 편하다.
반사 및 추이 클로우저는 추이 클로우저 에 반사 관계를 추가한 것이라 생각하면 편하다.

5.5 동치 관계와 분할

동치 관계 : 아래 3 가지 관계를 모두 만족하는 경우
- 집합 A에서 관계 는 다음과 같은 성질을 가질 수 있다.
1. 반사 관계 : 모든 에 대해 이다.
2. 대칭 관계 : 모든 에 대해 이면 이다.
3. 추이 관계 : 모든 에 대해 이고 이면 이다.
동치류/동치클래스 : 집합 A에 대한 동치 관계를 R이라고 할 때, A의 각 원소 x에 대하여 [x]를 R에 대한 x의 동치류, 또는 동치 클래스라고 한다.
이때 집합 A의 동치류의 모임을 A의 몫집합이라 하고, 로 나타낸다.
분할 : 다음조건을 만족시키는 A의 부분 집합의 모임 이라 한다.

는 공집합이 아니다.
는 의 전체 합집합이다. (Collectively Exhaustive)
끼리는 서로소관계이다. (Mutually Exclusive)

mod 합동 은 m으로 x, y를 나눴을 때 나머지가 같은 경우를 한다.
- 달력의 요일로 봤을 때 3, 10은 같은 요일이고, 7로 나눴을 때 나머지가 같기 때문에 mod합동이다.
- mod 합동은 동치관계를 성립한다.
양의 정수 m에 대해 m = 3일 때 mod 합동인 관계의 경우 동치류를 만들어보자
- 집합은 서로소이고 합집합하면 음수가 아닌 정수의 집합이 되므로 분할이 된다.

5.6 부분 순서 관계

일에 대한 순서를 정한다 했을 때, A 작업과 B 작업이 있다고 할 경우 A작업이 먼저 수행되고 바로 다음에 B 작업이 수행된다고 했을 때 이 작업에 대한 순서쌍을 (A, B)로 표시할 수 있다.
부분 순서 관계 : 아래 3 가지 관계를 모두 만족하는 경우
- 집합 A에서 관계 는 다음과 같은 성질을 가질 수 있다.
1. 반사 관계 : 모든 에 대해 이다.
2. 반대칭 관계 : 모든 에 대해 이고 이면 x=y이다.
3. 추이 관계 : 모든 에 대해 이고 이면 이다.
R이 A에 대한 부분 순서 관계이면 순서쌍 (A, R)을 부분 순서 집합이라고 한다.
R이 A에 대한 부분 순서 관계이면, A의 두 원소 x, y에 대하여 을 x가 y를 선행한다고 읽는다.
부분 순서 집합을 그림으로 나타낼 때는 하세 도표를 이용한다.
- 방향 그래프의 일종
집합 A상에서의 관계 R이 다음 조건을 만족할 경우 선형 순서라 한다.
1. R이 부분 순서를 만족한다.
2. 만약 라면 aRb, bRa 또는 a=b 중 하나가 성립한다.
집합 A의 모든 두 원소가 비교 가능하면 A을 선형 순서 집합이라 한다.
선형 순서 집합인 경우 관계를 선형 순서 관계라 한다.

🖥️ Techtellus

Explorer

[이산구조] L05.관계

5.1 관계와 이항 관계

5.2 관계의 표현

5.3 합성 관계

5.4 관계의 성질

5.5 동치 관계와 분할

5.6 부분 순서 관계

참고문헌

연결문서

Graph View

Table of Contents

Backlinks