[이산 수학] 관계의 개념

관계의 개념

• 인공지능은 데이터베이스에 저장된 지식을 활용하여 새로운 지식을 생성하거나 문제를 해결한다.
• 데이터베이스는 자료를 효율적으로 처리할 수 있도록 관련 있는 자료를 중복 없이 통합한 집합으로, 구조화된 자료 형태이다.
• 이처럼 구조화된 자료에 의미 있는 관계를 부여하면 새로운 정보를 만들 수 있고, 같은 자료 사이의 관계라고 하더라도 부여된 관계에 따라 전혀 다른 정보가 될 수 있다.
• 그러므로 데이터베이스에 저장된 자료 자체뿐 아니라 그 자료 사이의 관계는 인공지능이 지식을 생성하고 판단하는데 큰 영향을 미친다.

 

• 다음과 같은 자료 집합이 존재하고, 각 집합에 포함된 자료는 오류와 중복이 없어 정보를 제공하는 데 충분하다고 가정하자.

자료 집합 간 관계의 예

• 위 그림처럼 자료 집합을 개별적인 정보만으로 구성한다면 학생, 전공, 과목, 교수 각각에 관한 정보만 검색이 가능하다.
• 그러나 위에서 살펴본 관계를 의미 있게 설정한다면 학번을 이용하여 전공 또는 수강과목을 알수 있고, 과목코드를 이용해 과목 담당 교수를 알 수도 있다.

자료 집합 간 관계의 예

• 이처럼 개별적인 자료 집합 사이에 관계를 설정하여 새로운 정보를 생성할 수 있으므로 자료 간의 관계 정의는 매우 중요하다.

 

관계(Relation : $R : A → B, \; {}_{a}R_{b}$) / 이항 관계(Binary Relation)

집합 $A, B$ 가 있을 때, 집합 $A$ 에서 집합 $B$ 로 가는 관계로, $R$ 은 $A × B$ 의 부분 집합

$a ∈ A, \; b ∈ B \text{일 때}, \; (a, b) ∈ R \text{이면}$	$_{a}R_{b}$
$(a,b) \not ∈R \text{이면}$	$_{a} \require{cancel}\cancel{R}_{b}$

• 두 집합 간의 관계를 이항 관계(Binary Relation)라고 한다.
• 두 집합 간의 가능한 모든 이항 관계는 두 집합의 곱집합으로 구할 수 있다.
  • 예) $A = \{ a, b, c \}$ 에서 집합 $B = \{ 1, 2 \}$ 로 가는 가능한 모든 이항 관계는 $A \times B$ 로 구할 수 있다.
    • 만약 집합 $B$ 에서 집합 $A$ 로 가능 가능한 이항 관계를 구하려면 $B \times A$ 를 구해야 한다.

 

예

$$A \times B = \{ (a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2) \}$$

• $A \times B$ 는 집합 `A` 와 집합 `B` 의 원소로 만들 수 있는 모든 순서쌍의 모임으로, 집합 `A` 에서 집합 `B` 로 가는 가능한 모든 관계를 의미한다.
• 그러므로 집합 `A` 에서 집합 `B` 로의 관계 `R` 은 $A \times B$ 의 모든 원소를 포함할 수도 있고 그렇지 않을 수도 있는 $A \times B$ 의 부분 집합이다.
• 집합 `A` 에서 집합 `B` 로의 관계 `R` 이 다음과 같다고 하자.

$$R = \{(a, 2), (b, 1), (c, 2) \}$$

• $A \times B$ 에 포함되는 원소 중 `(a, 2), (b, 1), (c, 2)` 는 관계 `R` 에 포함되지만, 그 외의 원소 `(a, 1), (b, 2), (c, 1)` 은 관계 `R` 에 포함되지 않는다.
• 즉, 집합 `A` 에서 집합 `B` 로 가는 관계 `R` 이라고 해서 집합 `A` 와 집합 `B` 의 원소로 만들 수 있는 모든 순서쌍을 포함하지는 않는다.
• $A \times B$ 에 포함되는 원소 중 `(a, 2), (b, 1), (c, 2)` 처럼 관계 `R` 에 포함되는 경우에는 $_{a}R_{2}, \; _{b}R_{1}, \; _{c}R_{2}$ 로 표기하고, `(a, 1), (b, 2), (c, 1)` 처럼 관계 `R` 에 포함되지 않는 경우에는$_{a} \require{cancel}\cancel{R}_{1}, \; _{b} \require{cancel}\cancel{R}_{2}, \; _{c} \require{cancel}\cancel{R}_{1}$ 로 표기한다.

 

• 관계에 포함되는 원소는 일반적으로 순서쌍 형태이다.
  • 순서쌍은 구성하는 원소의 순서가 바뀌면 전혀 다른 순서쌍이 되므로 구성 원소의 순서가 중요하다.
• 다음 두 순서쌍은 모두 `a, b` 로 구성되지만, 순서가 다르므로 서로 다른 순서쌍으로 판단한다.

$$(a, b) ≠ (b, a)$$

• 그러므로 순서쌍을 원소로 갖는 관계를 정의할 때 집합 간의 방향성이 매우 중요하다.
  • 방향성이란 순서쌍에서 앞에 오는 원소를 포함하는 집합과 뒤에 오는 원소를 포함하는 집합의 순서를 의미한다.
• 일반적으로 이항 관계를 정의할 때,  '집합 `A` 에서 집합 `B` 로 가는 관계 `R`' 이라고 정의하고, `R: A → B` 로 표기한다.
  • 이는 집합 `A` 의 원소가 관계 `R` 에 포함되는 순서쌍의 앞에 오고, 집합 `B` 의 원소가 순서쌍의 뒤에 옴을 의미한다.
  • 이 때, 집합 `A` 를 정의역(Domain), 집합 `B` 를 공역(Codomain)이라고 한다.
  • 특히, 공역의 원소 중 관계 `R` 에 포함되는 순서쌍의 원소로 사용되는 원소들의 집합을 치역(Range)이라고 한다.

 

정의역(Domain : $\text{dom}(R)$, $D_{R}$)

집합 `A` 에서 집합 `B` 로 가는 이항 관계 `R` 에 속한 순서쌍의 첫 번째 원소가 포함된 집합, 즉 집합 `A`
$$\text{dom}(R) = \{ a \; | \; a ∈ A \}$$

 

공역(Codomain : $\text{codom}(R)$)

집합 `A` 에서 집합 `B` 로 가는 이항 관계 `R` 에 속한 순서쌍의 두 번째 원소가 포함된 집합, 즉 집합 `B`
$$\text{codom}(R) = \{ b \; | \; b ∈ B \}$$

 

치역(Range : $\text{ran}(R)$)

집합 `A` 에서 집합 `B` 로 가는 이항 관계 `R` 에 속한 순서쌍의 두 번째 원소를 모아놓은 집합, 즉 공역의 부분 집합 $$\text{ran}(R) = \{ b \; | \; (a, \; b) ∈ R \}$$

 

$n$ 항 관계($n$-ary Relation)

`n` 개의 집합 $A_{1}, A_{2}, \cdots, A_{n}$ 이 있을 때 $A_{1} \times A_{2} \times \cdots \times A_{n}$ 의 부분 집합

 

• 관계가 항상 2개의 집합 사이에만 존재하는 것은 아니다.

자료 집합 간 관계의 예

• 위의 그림에서 3가지 정보 '학생전공 정보', '수강과목 정보', '담당과목 정보'를 이용하여 아래와 같이 관계를 설정하면 학생이 수강하는 과목의 담당교수에 대한 정보를 알 수 있다.

수강과목 담당교수 정보
학번	과목코드	교수번호

• 이처럼 관계의 정의에 사용되는 집합이 3개 이상일 때, $n$ 항 관계라고 한다.

 

예 : $A= \{ a, b, c \}$ 에서 집합 $B = \{ 1, 2 \}$ 그리고 집합 $C = \{ x, y, z \}$ 로 가는 가능한 모든 관계

$$A \times B \times C = \{(a, 1, x), (a, 1, y), (a, 1, z), (a, 2, x), (a, 2, y), (a, 2, z), (b, 1, x), (b, 1, y), (b, 1, z), (b, 2, x), (b, 2, y), (b, 2, z), (c, 1, x), (c, 1, y), (c, 1, z), (c, 2, x), (c, 2, y), (c, 2, z) \}$$

• 총 $18(= 3 \times 2 \times 3)$ 개의 관계로 표현할 수 있다.

 

역관계(Reverse Relation : $R^{-1}$)

집합 `A` 에서 집합 `B` 로의 관계 `R` 이 있을 때, 집합 `B` 에서 집합 `A` 로의 관계
$$R^{-1} = \{ (b, a) ∈ B \times A \; | \; (a, b) ∈ R \}$$

 

자료 집합 간 관계의 예

• 위의 그림에서 '수강과목 정보'는 각 학생이 수강하는 과목의 정보를 알 수 있는 집합 관계로, (학번, 과목코드) 형태의 순서쌍이 만들어진다.
• 그러나 각 과목별로 수강생의 정보를 알고 싶다면 (과목코드, 학번)의 순서쌍으로 구할 수도 있다.
• 이 때, 각 학생이 수강하는 과목에 대한 정보와 각 과목의 수강생에 대한 정보는 모두 아래 그림의 '학생정보 집합', '과목정보 집합'을 이용하지만, 관계의 방향성에 따라 전혀 다른 순서쌍을 만들어 새로운 정보를 제공한다.

자료 집합 간 관계의 예

• 이처럼 같은 집합에 대하여 방향성이 반대인 관계를 역관계라고 한다.
• 역관계 $R^{-1}$ 은 반드시 관계 `R` 이 있을 때에만 존재하며, 관계 `R` 을 구성하는 순서쌍과 순서가 반대인 순서쌍을 원소로 갖는다.
• 그러므로 관계 `R` 의 정의역이 역관계 $R^{-1}$ 의 공역, 관계 `R` 의 공역이 역관계 $R^{-1}$ 의 정의역이다.
• 즉, 관계 `R : A → B` 에 대하여 역관계는 `R^{-1} : B → A` 이다.

 

예 : 집합 $A = \{ a, b, c \}$ 에서 집합 $B = \{ 1, 2 \}$ 로 가는 관계 $R = \{ (a, 2), (b, 1), (c, 2) \}$

• `R` 의 역관계 `R^{-1}` 는 $R^{-1} =\{(2, a), (1, b), (2, c) \}$ 로, 역관계 $R^{-1}$ 의 정의역은 집합 `B` 이고, 공역은 집합 `A` 이며 치역은 $\{a, b, c \}$ 이다.