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

2023-10-22-DiscreteStructure-L05

5.1 관계와 이항 관계

5.2 관계의 표현

5.3 합성 관계

5.4 관계의 성질

5.5 동치 관계와 분할

5.6 부분 순서 관계

참고문헌

연결문서

Graph View

Table of Contents