[ 이산 수학 ] 14. 관계

Binary Relations

 

 : 집합 A와 B를 가지고 만들 수 있는 관계들을 모은 것 = R

 

Binary 라는 뜻은 A와 B 안에 있는 원소가 있을 수도, 없을 수도 있다는 의미로 해석하면 된다. 

 

A = {0,1,2}

B = {a,b}

 

일 때, A*B = {(0, a), (0, b), (1, a), (1, b) (2,a) , (2, b)}이지만

R은 모두 다 가지고 있을 필요가 없다. 

R= {(0, a), (0, b), (1,a) , (2, b)} 이런 식이다.

 

따라서 해당 관계는 아래와 같이 표현할 수 있다.

 

아마 R의 최대값(?)은 A*B와 같을 때 일 것이다.

 

아래 원소를 가질 수 있는 R은? 이런 것도 풀 수 있어야 한다.

 

---

 

n개의 원소가 있는 set A에서 나올 수 있는 R의 개수는?

 

=>1)  각 원소가 있고, 없고 로 생각하면 됨. 

     2)  A*A로 생각해야한다.

 

● 각 원소당 있다 없다를 정할 수 있으므로 한 세트당 2^a를 할 수 있다.

● A*A = n^2개 원소를 매칭할 수 있음

 

= 2^(n^2) 

 

---

관계의 종류

 

• Reflexive
• Symmetric
• Antisymmetric
• Transitive

 

 

1) Reflexive

 

Reflexive 면 (1,1) (2,2) (3,3)이런 걸 가지고 있어야 함.

 

참고할 점은 A= {1,2,3} 이고 R에 {(1,1), (2,2),(3,1)} 만 있다면 안 됨 (3,3)도 있어야 함.

모든 A원소에 대해서 (a,a)가 성립해야 한다 이말

 

가능한 R들

:

 

 

2) Symmetric

 

A에 있는 a,b에 대해서 

(a,b)가 있으면 (b,a)도 있어야 한다.

(1,1)도 (1,1)에 대한 대칭이므로 가능

 

 

가능한 R들

 

 

3) Antisymmetric

 

A에 있는 a,b에 대해서 

(a,b)가 있으면 (b,a) 가 되는 것이 있으면

 

그건 a=b이어야 한다. 그게 아니면 반대칭 X

 

이전 관계일 때 (a=b)이어야 한다는 조건만 하나 더 붙었다.

 

대칭인 건 (a,b)인 것만 된다!

 

 

 

4) Transitive

 

집합 A {a,b,c,...}에 대한 관계에서

 

1) R 중에서 (a,b) 를 잡는다.

2) b로 시작하는 것들 중에 하나를 (b,c) 로 잡는다

3) c로 시작해서 a가 오는 (c,a)를 찾는다.

 

 

(b,c)를 잡고, c로 시작해서 a가 있는 놈을 찾는다.

 

가능한 관계 R들

 

---

 

●  n개의 원소가 있는 집합에서 나올 수 있는 reflexive 관계 R의 개수는?

 

--> 우선 n개의 원소가 있는만큼 n개의 reflexive (a,a) 쌍이 나올 수 있다.

따라서 n개 중에 하나는 꼭 있어야 하고, 나머지 ( n-1 ) 개의 원소들을 자기 알아서 있든 없든 하면 됨

 

따라서 2^( n(n-1) ) 이다.

 

 

R끼리의 연산도 해볼 줄 알기

 

---

Composition of Relation

그냥 합성함수 같은 거라 생각하면 될 것 같다.

R1 -> R2 -> 에서 나오는 값을 보는 것인데 

기호로는 R2 ⊙ R1 순서로 나온다. 참고해두자.

 

---

Power of R

 

 

집합 R을 여러 번 합성 함수처럼 했을 때 어떤 값이 되는지 한 번 구해보자

 

 

R ={(1, 1), (2, 1), (3, 2), (4, 3)} 일 때, 합성을 할 때마다 어떻게 변하는지 보자

 

 

왼쪽은 R이고,

                                     R ⊙ R을 했을 때는 이런 양상이고 그 결과는  오른쪽 사진과 같다.

R^2 = R ⊙ R = {(1,1) (2,1) (3,1) (4,2) }

R^3 = {(1,1) (2,1) (3,1) (4,1) }

...

R^n = {(1,1) (2,1) (3,1) (4,1) }

 

 

n=3 일 때부터는 얼마를 더 합하든 값이 같다.

 

 

 

그렇다면 Transitive R 의 Power 는??

 

 

 

R은  R^n이 R의 부분집합일 때  Transitive 하다.

 

증명)

(a,b)와 (b,c)가 R에 속하면, composition 정의에 따라서 (a,c)가 R^2에 속한다.

R^2 이 R에 속한다는 것은, (a,c)가 R에도 속한다는 것.

 

 

[ wrtn 대답 ] 

 

전이성이란, (a, b)와 (b, c)가 R에 속하면 (a, c)도 R에 속하는 성질을 말한다.

이런 전제 하에, 이 이론은 [ 전이성을 가진 관계 R에 대해, R의 n번째 거듭제곱은 항상 R의 부분집합이다. ]

기호로 Rⁿ ⊆ R (n = 1,2,3,…) 으로 표현된다.

 

1) Rⁿ이 R의 부분집합임을 가정하고 전이성을 증명

: ( a, b)와 (b, c)가 R에 속한다면, 합성의 정의에 따라 (a, c)는 R²에 속한다.

R²이 R의 부분집합이므로, (a, c)도 R에 속하게 된다.

 

+) - 합성을 하면 할수록 원소의 개수가 줄어든다.  

- (a, b)가 Rᵏ⁺¹에 속한다면, 적어도 하나의 원소 x가 존재하여 (a, x)가 R에 속하고,

  (x, b)가 Rᵏ에 속한다는 것을 알 수 있다. (a,b)를 이어주는 매개체가 있었을 것.

   a -> x -> b

 

2) 그렇다면 Rn 이 R의 부분집합인 것도 증명해야한다.

 

수학적 귀납법. 

 

 

- 기초 단계: n=1일 때 성립함을 보입니다. 즉, R¹ ⊆ R이 성립함을 확인합니다. 이는 당연하게 성립합니다. 왜냐하면 R¹은 R 그 자체이기 때문입니다.

 

- 귀납 단계: 이 단계는 두 부분으로 나뉘어집니다.

• 귀납 가정(inductive hypothesis): n=k일 때 Rᵏ ⊆ R이 성립함을 가정.
• 귀납 단계 증명: 이제 n=k+1일 때 Rᵏ⁺¹ ⊆ R이 성립함을 증명해야함.

 

Rᵏ⁺¹ = R^k ⊙ R이다.

Rᵏ⁺¹ 에 (a,b)가 있다는 건,  R에 (a,x)가 있고, R^k에 (x,b)가 있다는 것을 의미한다.

 

 

이렇게 되어야 한다는 뜻!!

 

따라서, (x, b)는 R에 속합니다. 그리고 우리가 알고 있는 것은 R이 전이성을 가지고 있으므로, (a, x)와 (x, b)가 모두 R에 속하면, (a, b)도 R에 속하게 됩니다.

 

 

---

n-ary Relations and Their Applications

[n진 관계]

n개의 원소들에서 조건에 맞는 R만 가져오는 것

 

 

 

Selection

 

--> n개의 원소 중에서, C라는 컨디션을 만족하는 R들만 골라내는 것.

 

 

 

 

 

DB 버전

---

 

Projection

 

여러 개의 필드(값들이 다 들어가있음)에서 

필요한 필드만 추출하는 느낌이라고 생각하면 됨

 

 

---

Join

집합 R들의 필드를 이어 붙여서 합치는 개념.

 

 

 

 

 

 

(출처)

https://jie0025.tistory.com/514