[12] 이산수학(관계)

관계(Relation)

A와 B를 집합이라고 하자. A에서 B로의 이항관계(binary relation from A to B)는 두 집합의 곱집합 A x B의 부분집합이다.

 

# 관계와 함수

• 집합 A에서 집합 B로의 함수 f는 A의 각 원소가 B의 원소 하나에 연결된다.
• A에서 B로의 관계 R은 두 집합 원소 사이의 일대다 관계로 표현할 수 있다.

# 역관계 

집합 A에 B로의 관계 R이 있을 때, B에서 A로의 관계를 R에 대한 역관계라고 한다.

 

# 관계 행렬(Relation Matrix)

부울 행렬을 이용하는 방법으로서, 관계 행렬은 집합 A에서 집합 B으로 가는 관계 R에 대한 n x m 행렬로 정의할 수 있다.

 

# 반사관계

집합 A에 대한 관계 R이 A에 속한 a들에 대해 R에 속한 (a,a)가 되면 반사적(reflexive)이라고 한다.

 

# 비반사 관계

반사관계의 반대

 

반사관계와 비반사 관계 둘 다 해당하지 않을 수 있다.

 

# 대칭 관계 

집합 a에 대한 관계 R이 A에 속한 모든 a,b에 대해 R에 (a,b)가 속한다면 대칭적(symmetric)이라고 한다.

 

# 반대칭 관계

집합 𝐴에 대한 관계 𝑅이 모든 𝑎, 𝑏 ∈ A에 대해 𝑎, 𝑏 ∈ R이고 𝑏, 𝑎 ∈ R일 때, 𝑎 = 𝑏이면 반대칭적(antisymmetric)이라
한다. 반대로 말하자면, 𝑎 ≠ 𝑏일 경우 (𝑎, 𝑏) ∈ 𝑅이면 (𝑏, 𝑎) ∉ 𝑅 여야 한다.

 

대칭관계가 아니더라도 반대칭 관계가 아닐수도 있다. 또한 둘 다 만족할 수도 있다. 대칭과 반대칭은 서로 반대말이 아니다.

 

# 추이 관계

집합 𝐴에 대한 관계 𝑅이 모든 𝑎, 𝑏, 𝑐 ∈ 𝐴에 대해 𝑎, 𝑏 ∈ 𝑅이고 𝑏, 𝑐 ∈ 𝑅일 때 𝑎, 𝑐 ∈ 𝑅이면 추이적(transitive)이라 한다.

 

# 추이 관계

𝑅을 집합 𝐴에서 집합 𝐵로의 관계라고 하고 𝑆를 집합 𝐵에서 집합 𝐶로의 관계라 하자. 𝑅과 𝑆의 합성(composite)은 순서쌍
(𝑎, 𝑐)로 구성되는 관계로, 𝑎 ∈ 𝐴, 𝑐 ∈ 𝐶이고, 𝑎, 𝑏 ∈ 𝑅과 𝑏, 𝑐 ∈ 𝑆인 원소 𝑏 ∈ 𝐵가 존재한다.
이때 𝑅과 𝑆의 합성을 𝑆 ∘ 𝑅로 표기한다.