9 관계Relations 3

이제부터 M_R 은 M 우측하단에 R을 뜻합니다. m_ij인 경우 m 우측하단에 ij를 의미합니다. 이 경우 엘리먼트 i행 j열을 뜻합니다.

관계 표현하기Representing Relations

 이번 섹션에서는, 그리고 이 9챕터 나머지 부분에서도, 우리가 학습할 모든 관계들은 이진 관계binary relations일 것입니다. 이러한 이유때문에, 관계라는 용어는 항상 이진 관계를 지칭합니다. 유한 집합들간의 관계를 표현하는데 많은 방법이 있습니다. 9.1절에서 살펴본 것처럼, 관계의 순서쌍을 나열하는 것입니다. 관계를 표현하는 또 다른 방법은, 테이블을 이용하여 표현할 수 있습니다. 이 섹션에서는, 관계를 표현하기위해 사용되는 두 개의 대안적인 수단을 사용할 수 있습니다. 한 방법은 0-1 행렬입니다. 다른 한 방법은 그림으로 표현하는 방향 그래프directed graph를 사용할 수 있습니다. 나중 섹션에서 이야기될 것입니다.

 일반적으로, 컴퓨터 프로그램에서 관계를 표현하는데 행렬은 적절하게 사용될 수 있습니다. 반면에, 사람들이 관계를 표현하는데는 방향 그래프directed graph가 유용하게 사용합니다. 방향 그래프는 관계들의 속성을 이해하는데 유용합니다.

행렬을 이용해 관계들을 표현하기Representing Relations Using Matrices

 유한 집합들간의 관계는 0-1 매트릭스를 이용하여 표현될 수 있습니다. 관계 R을 A={a1, a2, ..., am}에서 B = {b1, b2, ..., bn} 로의 관계라고 가정합시다. (여기서, A와 B의 엘리먼트들은 (일반적으로 오름차순)순서대로 나열되었지만, 임의의 수입니다. 더욱 더, A=B일 때는 같은 순서를 가집니다.) 관계 R은 M_R = [m_ij] 로 표현될 수 있습니다.  여기서 m_ij = 1 if (a_i,b_j) ∈ R, 0 if (a_i,b_j) ∉ R

 다르게 표현하자면, R을 표현하는 0-1 행렬은 a_i가 b_j와 연관될 때 (i, j)에 값 1을 가집니다. 그리고 이 자리의 값이 0이라면 a_i가 b_j와 연관되지 않은 것입니다. (이 표현은 A와 B의 엘리먼트 나열 순서에 따라마다 다릅니다. 그렇기에 앞서 나열의 순서를 강조했습니다. 집합은 비정렬된 쌍이므로 행렬은 모습이 달라질 수 있기 때문입니다.) 아래의 예제를 살펴봅시다.

예제 1

 A = {1,2,3}, B= {1,2} 라고 합시다. R은 A에서 B로의 관계라고 합시다. R은 순서쌍 (a,b)로 이루어져있고, a ∈ R, b ∈ R, a > b 를 만족합니다. 관계 R을 행렬로 표현하면 무엇입니까? 여기서 a_1 = 1, a_2 = 2, a_3 = 3 이고 b_1 = 1, b_2 = 2 입니다. (반드시 미리 명시되어야합니다.)

*** R= {(2,1), (3,1), (3,2)} 입니다. 그러므로 행렬은 다음과 같습니다.

           0  0 

M_R =  1  0

     1  1

M_R의 1들은 관계 R에 포함된 정렬된 쌍(순서쌍) (2,1), (3,1), (3,2)를 보여줍니다. 그리고 0은 R에 포함되지 않은 순서쌍들을 보여줍니다.

예제 2

A = {a_1, a_2, a_3}, B = {b_1,b_2,b_3,b_4,b_5}라 하자. 관계 R에는 어떤 순서쌍이 포함되어있습니까? 행렬로 표현된 관계는 아래에 제시되어 있습니다.

*** 관계 R은 m_ij=1 인 (a_i, b_j)를 포함합니다. 따라서, R={(a_1,b_2), (a_2,b_1), (a_2,b_3), (a_2,b_4), (a_3,b_1), (a_3,b_3), (a_3,b_5)} 입니다.

한 집합 자신으로의 관계 행렬은, 정방 행렬square matrix입니다. 이는 관계의 특정 속성을 판단하는데 사용될 수 있습니다. 

집합 A 자신으로의 관계 R은 다음과 같은 조건에서 반사적일 수 있습니다. 만약 a ∈ A 일 때 모든 (a,a) ∈ R를 만족하면 관계 R은 반사적입니다. ∀a((a,a)∈ R) 즉, R은 (a_i,a_i) ∈ R이면 반사적입니다. 여기서 i = 1, 2, ... , n. 따라서, R은 m_ii = 1 이면 반사적입니다. 여기서 i = 1, 2, ... , n 입니다. 다른 표현으로는, 행렬 M_R의 대각 엘리먼트들이 1일 때 관계 R은 반사적입니다. 아래에 그림이 있습니다. 대각 이외의 엘리먼트들은 0 또는 1의 값을 가질 수 있습니다. ( **  (9.1 절) 조합조건에 대한 문제에서 이야기 된 바 있습니다.)

관계 R이 대칭적symmetric임은 다음 명제의 필요충분조건입니다. (a,b) ∈ R이면 (b,a) ∈ R이다. ∀a∀b((a,b)∈R→(b,a)∈R) 결과적으로, 집합 A={a_1,a_2, ..., a_n} 자신으로의 관계 R이 대칭적symmetric임은 명제 (a_i,a_j) ∈ R이면 (a_j,a_i) ∈ R의 필요충분조건입니다. M_R을 도입하여 용어를 정리하면, 관계 R은 대칭적symmetric임은 m_ij=1일 때 m_ji=1 명제의 필요충분조건입니다. 이는 또한 m_ij=0 일 때 m_ji=0 임도 의미합니다. 결과적으로, R이 대칭적임은 m_ij = m_ji 의 필요충분조건입니다. 여기서 i와 j는 모든 정수입니다. i=1,2, ... , n 그리고 j = 1,2, ..., n입니다. 

행렬의 전치의 정의를 기억해보면, R은 대칭적임은 다음의 명제와 필요충분조건입니다. M_R = M_R^t

관계 R이 반대칭적antisymmetric임은 명제 (a,b)∈R 그리고 (b,a)∈R이면 a=b의 필요충분조건입니다.  ∀a∀b((a,b)∈R ∧ (b,a)∈R→(a=b)) 결과적으로, 반대칭 관계의 행렬의 다음과 같은 속성을 가집니다. 만약 m_ij=1 이고 i≠j 이면, m_ji = 1입니다. 다른표현으로는, i≠j이면 m_ij=0이거나 m_ji=0입니다. ∀a∀b((a=b)→(a,b)∉R ∨ (b,a)∉R) 

아래는 대칭적symmetric과 반대칭적antisymmetric를 0-1행렬로 표현한 것입니다.

예제 3

집합 자신으로의 관계 R은 다음의 행렬과 같이 표현된다고 하자. 

1  1  0

M_R =   1  1  1

            0  1  1  

관계 R은 반사적reflexive입니까? 대칭적symmetric입니까? 반대칭적antisymmetric입니까?

*** M_R의 대각 엘리먼트들이 모두 1과 같으므로, 관계 R은 반사적입니다. 더욱더, M_R이 대칭적이므로 관계 R은 대칭적입니다. 그리고 관계 R이 반대칭적인것도 쉽게 알 수 있습니다.

불린연산자 join과 meet (2.6에서 논의 된)은 두 관계의 합union과 교intersection을 표현하는 행렬을 찾는데 사용될 수 있습니다. R_1과 R_2를 집합 A 자신으로의 관계라고 합시다. 각각 M_R_1, M_R_2의 행렬로 표현됩니다. 이 두 관계들의 합union을 표현한 행렬은 M_R_1 또는 M_R_2이 1을 가진 위치에 1의 값을 가집니다. 두 관계들의 교intersection을 표현한 행렬은 M_R_1, M_R_2이 공통적으로 1을 가진 위치에 1을 가집니다. 따라서, 관계들의 합과 교를 표현하는 집합들은 다음과 같습니다. 

M_(R_1 ∪ R_2) = M_R_1 ∨ M_R_2

M_(R_1 ∩ R_2) = M_R_1 ∧ M_R_2

예제 4

집합 A 자신으로의 관계 R_1과 R_2을 행렬로 표현하면 다음과 같습니다.

   1  0  1                    1  0  1

M_R_1 =   1  0  0       M_R_2 =  0  1  1

              0  1  0                     1  0  0

관계 R_1∪R_2과 R_1∩R_2 는 무엇입니까?

*** 이 관계들의 행렬은 다음과 같습니다.

이제 관계들의 합성에 대한 행렬 판단하겠습니다. 이 행렬은 관계들을 표현한 행렬들의 불린 곱으로 알아 낼 수 있습니다. 예로, A에서 B로의 관계 R이 있고 B에서 C로의 관계 S가 있다고 합시다. A, B, C는 각각 m, n, p 개의 엘리먼트들을 가지고있습니다. S∘R, R, S에 대한 0-1 행렬들을 각가 M_S∘R = [t_ij], M_R = [r_ij], M_S = [s_ij]라 합시다. (이 행렬들의 크기는 m x p, m x n, n x p 입니다.) 순서쌍 (a_i, c_j)는 S∘R의 원소임은 R의 원소에 (a_i,b_k)와 S의 원소에 (b_k, c_j)인 b_k가 존재함에 대해 필요충분조건입니다.