[이산수학] 관계 -1

관계란?

관계란 객체들 간의 연관성을 표현하는 도구이며 집합에서의 원소들 간의 순서를 고려한 것이다. 원소들 간에 비교 연산자를 사용하며 곱집합의 임의의 부분 집합이라고 할 수 있다. 

 

관계의 집합에 대한 연산, 즉 교집합, 합집합, 여집합, 차집합 등도 관계가 된다.

 

2개의 집합 사이의 관계를 이항(binary) 관계라고 하며 보통 관계를 말할 때는 이항 관계를 의미한다.

💡이항 관계
두 집합 A, B에 대하여 A로부터 B로의 이항 관계 R은 두 집합의 곱집합 AxB의 부분 집합이다.

관계에 대한 표기를 기호로 나타내면 아래와 같다.

정의역

관계 R의 원소인 순서쌍에서 첫 번째 원소의 집합을 말하며 Dom(R)이라고 표시한다.

Dom(R) = { a | (a, b) ∈ R } ⊆ A

치역

관계 R의 원소인 순서싸엥서 두 번째 원소의 집합을 말하며 Ran(R)로 표시한다.

Ran(R) = { b | (a, b) ∈ R } ⊆ B

역관계

집합 A에서 집합 B로의 관계 R에 대한 역관계(Inverse relations) R^-1는 집합 B에서 집합 A로의 관계를 나타낸다. 

aRb의 관계가 있어야만 bR^-1a가 존재하는 것이다.

관계의 표현

집합 사이의 관계를 표현하는 방법은 서술식, 나열식 두가지로 나눌 수 있다.

• 서술식 방법 : 집합 사이의 관계를 문장으로 서술하는 방식
• 나열식 방법 : 서술식에 따라 관계를 순서쌍들의 집합으로 표현하는 방법

화살표 도표

집합 A의 원소 a와 집합 B의 원소 b가 (a, b) ∈ R일 경우 원소 a와 원소 b의 관계를 화살표를 그려 표현하는 방법을 말한다.

좌표 도표

집합 A의 원소를 x축 위에 점으로 표시하고 집합 B의 원소를 y축 위의 점으로 생각하여 순서쌍에 맞춰 점으로 표기하는 방식을 말한다. 

방향 그래프

관계 R이 두 집합 사이의 관계가 아니고 하나의 집합 A에 대한 관계일 때, 집합 A의 각 원소를 그래프의 정점(vertex)로 표시하고 (a, b) ∈ R일 경우 a에서 b로의 화살표가 있는 연결선(edge)로 표현하는 방식을 말한다. 

관계 행렬

Boolean 행렬을 이용하는 방법으로 행렬 안에 있는 모든 원소들이 0 또는 1로 표시되는 행렬을 사용한다. 관계 행렬의 행에는 집합 A의 원소, 열에는 집합 B의 원소를 표시하는데 행렬의 각 요소의 값은 a ∈ A와 b ∈ B의 관계가 있으면 1, 없으면 0으로 표현한다.

합성 관계

합성 관계는 주어진 두 관계로부터 새로운 관계를 이끌어내는 것이다. 세 집합 A, B, C에서 집합 A에서의 집합 B로의 관계를 R1이라 하고 집합 B에서 집합 C로의 관계를 R2라고 할 때, 집합 A에서 집합 C로의 관계를 합성 관계라고 하며 R1•R2 또는 R1R2라고 표기한다.

단 한가지 주의할 점은 R1의 치역이 R2의 정의역이 될 경우에만 합성 명제를 만들 수 있다.

A와 B의 관계를 R, B와 C의 관계를 S라고 한다.

 

항등 관계

집합 A에 대한 항등 관계는 다음과 같다.

집합 A에 두 원소 a,b가 아래와 같은 식이 성립하면 a와 b는 같은 값을 가진다.

또한, 집합 A에서 집합 B에 대한 합성 관계 R에 대해서 아래와 같은 식이 성립하는데 항등 관계를 이용한 합성 관계는 원래의 관계와 같아진다.