충북대학교 이충세 교수가 2015년 1학기에 강의한 이산수학 과목 중 관계(1)을 듣고 정리한 것이다. 그래프를 배울 때 2, 3도 듣고 정리할 예정이다.
사람 사이에는 여러 관계가 있다. 선생-학생, 부모-자식 등이 그 예다. 이와 마찬가지로 집합에도 관계가 있다. 예를 들어, 학생 정보(이름, 학번)과 과목 정보(과목명, 과목 코드)를 카티션 곱을 하면 학생 정보와 과목 정보가 합쳐진 수강 정보가 나오는데, 이는 '어떤 학생이 특정 과목을 수강한다'는 관계를 만들어 낸다.
$A*B$로 표현할 수 있다.
여기서 A를 정의역(Domain), B를 공역(Co-domain)이라고 한다. 또한 A에서 B로 가는 관계 중 A와 실제로 관계를 맺고 있는 것을 치역(Range)라고 한다. 그렇기 때문에 치역은 B의 부분집합이다.
이진관계(Binary Relation)
집합 A, B가 있을 때, 이 둘의 관계. 즉, A * B의 부분집합.
a ∈ A이고, b ∈ B일 때, (a, b) ∈ A * B라면 이진관계인 것이다.
n개의 관계(n-ary Relation)
집합 A1, A2, ... An이 있을 때, A1 * A2 * ... * An의 부분집합.
역관계(Inverse Relation) -> $R^{-1}$
집합 A에서 B로 가는 관계 R이 있을 때, R에 대한 역관계.
예를 들어, A = {1, 2}, B = {a, b}일 때.
R = {(1, a), (1, b), (2, a), (2, b)}
$R^{-1}$ = {(a, 1), (a, 2), (b, 1), (b, 2)}
관계의 표현은 다양한 방법으로 할수 있다.
관계의 성질
반사 관계(Reflexive Relation)
모든 a ∈ A에 대해 (a, a) ∈ R인 관계. 예를 들어, A = {1, 2}이고 R1 = {(1, 1), (1, 2), (2, 1), (2, 2)}라면 R1은 반사 관계에 있는 것이다. 이 중 하나라도 빠지면 반사 관계가 아니다.
관계 행렬으로 표현 했을 때 $M_{ii}$가 모두 1이라면 반사 관계고, 0이라면 비반사 관계에 있다. 0과 1이 섞여 있으면 반사 관계도 아니고, 비반사 관계도 아닌 것이다.
대칭 관계(Symmetric Relation)
어떤 a, b ∈ A에 대해 (a, b) ∈ R이라면 (b, a) ∈ R인 관계. 예를 들어, R1 = {(1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3, 3)}이라면 대칭이며, R2 = {(1, 1), (2, 3), (1, 2), (3, 2)}라면 (1, 2)의 대칭되는 것이 없으므로 대칭이 아니다.
추이(이행) 관계(Transitive Relation)
어떤 a, b, c ∈ A에 대해 (a, b) ∈ R이고 (b, c) ∈ R이라면 (a, c) ∈ R인 관계. 즉, a, b가 관계가 있고, b, c가 관계가 있다면 a, c도 관계가 있을 대 추이 관계에 있다고 한다. 예를 들어, R1 = {(a, d), (d, a), (a, a), (a, b)}인 경우 (d, a)와 (a, b)가 있기 때문에 (d, b)가 있어야 하는데 없으므로 추이 관계가 아니다.
합성 관계(Composition Relation)
A에서 B로 가는 관계 R이 있고, B에서 C로 가는 관계 S가 있을 때 A에서 C로 가는 관계를 합성 관계라고 한다.