[이산수학] 관계의 정의와 성질

<< 이산수학 4주차 >>

다른 집합과의 관계
1. 이항 관계
: A에서 B로의 이항관계
   R ⊆ AxB
R = {(a,b) | a∈A, b∈B}
(a,b) ∈ R  iff aRb

- A와 B 순서에 주의
- 순서쌍 집합, 그림, 테이블 등으로 표현

★★함수와 관계의 차이점★★
 // 하지만 국가와 도시 간의 "수도"에서는 관계보다 함수가 더 적절하게 쓰인다.
    국가-수도 관계는 하나씩 매핑되기 때문에 함수로 매핑하자.
 // 대학의 사립, 국립 유형에서도 1대1로 매핑되기 때문에 함수로 표현하는 게 더 적절하다.


2. 삼항 관계
: A, B, C로의 관계
R ⊆ AxBxC
R = {(a,b,c) | a∈A, b∈B, c∈C}

3. 다항 관계
: A1, ... , An로의 관계
 "n-tuple"이라고 부름.

RDB(Relational Data Base)
>> n-tuple들의 모임이다.
>> DBMS를 사용해 Selection, Join, Projection 명령으로 데이터를 얻을 수 있다.
 - selection : 선택 // 원하는 행 출력
 - projection : 투사 // 원하는 열 출력
 - join : 결합 // 두 테이블을 결합

-----------------------------(잠깐 관계에 대한 사담)-----------------------------
SQL
: 데이터베이스 질의 언어
 Flights ⊆ Airline x Flight_number x Gate x Destination x Departure_time 
 
데이터마이닝
: 데이터 간의 연관 법칙을 찾는 분야
i // 아이템 집합, 즉 판매할 상품들의 집합
T ={t1, ... , tn} // 트랜잭션 집합, 트랜잭션은 한 번에 구매한 상품 집합

ex. 트랜잭션 집합에서 아이템 집합의 I의 빈도수
 ★σ(I) = { ti∈T | I⊆ti }★
  >> 트랜잭션 집합에서 아이템 집합 I의 지지도 : support(I) = σ(I)/|T|
       지지도가 임계값 이상이면, 판매가 빈번하게 이뤄짐

해당 아이템을 산 사람이 다른 특정 아이템도 살 것인가?
 >> I,J를 모두 포함하는 트랜잭션의 빈번도 : support ( I->J ) = σ(I∪J) / σ(I)
 
//SQL과 데이터 마이닝은 (상품과 상품과의) 관계를 주로 나타내기 때문에 배웠다.
------------------------------------------------------------------------------------

동일 집합과의 관계
1. A에 관한 관계 
  // A에서 A로 가는 관계
  // 순서쌍 집합뿐만 아니라 방향 그래프로 표현할 수 있다.
R⊆AxA
R={ (a,a) | a∈A, a∈A }

(ex. 가계도 모델링)
People = { 아담, 가인, 아벨 }
아버지 관계
- father ⊆ People x People = { (a,b) | a is the father of b}
- father = { (아담, 가인), (아담, 아벨) }
집합의 원소들은 정적으로, 관계에 속하면 방향을 나타내서

(ex. 상태 전이 모델링)
S = {s0, s1, s2}
상태들 간의 전이 관계
T⊆ SxS { (si, sj) | sj is a successor of si }
T = { (s0, s1), (s0, s2), (s1, s0), (s1, s2), (s2, s2) } 


2. 역관계
R ⊆ AxB 일 때, R의 역관계는 BxA이다.
R의 역의 역은 R이 된다.

3. 합집합, 교집합, 차집합

4. 관계의 합성
R ⊆ AxB, S ⊆ BxC 일 때,
이들을 결합하면 SºR ⊆ AxC이다.
SºR = {(a,c) | ∃b, a∈A ∧ c∈C ∧ (a,b)∈R ∧ (b,c)∈S}

5. 관계의 곱
관계 R을 n번 결합한 것을 Rⁿ으로 표시
Rⁿ = Rº ... ºR

정의 
- 종료조건 : R¹ = R
- 반복조건 : Rⁿ = R^(n-1)ºR

예제. A = {1,2,3,4}
R⊆AxA = {(1,1), (2,1), (3,2), (4,3)}
R² = {(1,1), (2,1), (3,1), (4,2)}
R³ = {(1,1), (2,1), (3,1), (4,1)}


 관계의 성질
집합 A에 관한 관계 R⊆AxA에 대해서
1. 반사적(reflexive) 
  : 모든 A집합의 원소들에 대해서 자기에서 자기에게로 가는 집합이 존재할 때 "반사적"이라고 한다.
    ∀a∈A, (a,a)∈R
2. 대칭적(symmetric)
  : 모든 원소에 대해서 A에서 B로 가는 관계가 있다면, B에서 A로 가는 관계가 존재해야 함.
    ∀a,b∈A, (a,b)∈R -> (b,a)∈R
    이때, 화살표(->)는 T->T는 참/ T->F는 참/ F->F는 참/ F->T는 거짓이 된다.
3. 전이적(transitive)
  : A에서 B로가는 관계가 있고, B에서 C로 가는 관계가 존재하면 "전이적"이라고 한다.
    ∀a,b,c∈A, ((a,b)∈R ∧ (b,c)∈R ) -> (a,c)∈R
4. 반대칭적
  : A에서 B로 가는 관계가 있고, B에서 A로 가는 관계가 존재하면 "A=B" 이어야함.
     ∀a,b∈A, ((a,b)∈R ∧ (b,a)∈R ) -> (a=b)

(예제. 반대칭)
A = {1,2,3}
R ⊆ AxA = {(1,1) (1,2) (2,1) (2,3)}
반 대칭적이냐? (1,1)∧(1,2)는 1=2이어야 하는데 아니므로 거짓이다.
     결과적으로 어떠한 상황일 때 Anti-symmetric하냐? (1,1)∧(1,2)와 같은 경우가 존재하면 안됨.

동치관계
: 반사적, 전이적, 대칭적 관계를 모두 만족할 때 동치적이라고 한다.
- reflexive : A=A
- symmetric : (A=B) -> (B=A)
- transitive : (A=B ∧ B=C) -> (A=C)

동치류(Equivalence Class)
: 같은 원소끼리 그룹핑
- 동치 클래스 >> 하나의 원소를 대표 원소라고 한다. [a]
          a를 동치 클래스를 대표 멤버라고 부름
- 상 집합 >> 동치 관계로 집합을 분할한다.
     A/R = {[a], [b], ... }

(예제. 동치관계)
R⊂AxA = { (0,0), (0,4), (4,0), (4,4), (1,1), (1,3), (3,1), (3,3), (2,2) 
A/R = {{0,4}, {1,3}, {2}}
순서쌍으로 되어 있는 것을 그래프로 나타내 보면, 같은 집합에 있지만 각각의 다른 클래스로 분류 가능.

동치 예제

(예제. 동치 관계와 집합 분할)
5 mod 3 = 2
8 mod 3 = 2
7 mod 3 = 1
가 존재할 때, 동치클래스는 모듈로 3 연산에 의해 자연수 분할
 - [0] = {0,3,6, ... }
 - [1] = {1,4,7, ... }
 - [2] = {2,5,8, ... }
  >> 자연수 집합의 분할 : N/(mod3) = { [0], [1], [2] }


집합의 분할
: 세 조건을 모두 만족할 때, A1, ... An는 A의 분할이다.
 - 모든 i에 대해서, Ai⊆A     // 각각은 전체 안에 포함되어 있음.
 - A1 ∪ ... ∪ An = A         // 전체를 합하면 A가 된다.
 - 모든 i, j에 대해서, (i≠j) => (Ai ∩ Ai = ∮      // 모두가 서로 겹치는 게 없다.


부분 순서 관계
- reflexive : 반사적
- transitive : 전이적
- anti-symmetric : 반대칭적
 >> divide라는 성질을 보면 anti-symmetric하다. 왜냐하면 1에서 9를 나눌 수 있지만, 9에서 1을 나눌 수 없는 것을 보면 알 수 있다. 
 >> 주로 화살표가 to(아래쪽)에서 from(위쪽)으로 가도록 한다.

Poset(Partially Ordered Set)
: 집합 A와 부분 순서 관계인 R이 주어졌을 때, (A,R)로 표시
 의미는 집합 내의 원소를 부분적으로 정렬할 수 있다.
>> 하세 다이아그램(Hasse Diagram)으로 사용됨. >> 반사적 관계를 지움 >> 전이적 관계를 지움

★만약 하세 다이어그램을 보고 부분순서집합(A,R)을 구하자고 하면, 
   A = {a,b,c,d,e,f,g} // R은 {(a,a,) ... } 반사적, 전이적인 것들을 다시 복원시켜 R을 찾아낸다.

하세 다이아그램 표기법
(x,y) ∈ R  iff xㄷy //ㄷ의 의미 : 모든 x가 y에 포함된다.

부분 순서 집합에서 객체의 명칭
- Greatest : 최고  // 단 하나 >> 모든 원소들의 최고 이어야 함.
- Least : 최하 // 단 하나  >> 모든 원소들의 최하이어야함.
- Maximal : 최대
- Minimal : 최소

- Upper bound : 상한
// 관심있는 부분 집합(S)도 포함한다. 본인도 c->c로 가는 부분집합이 생략되어 있으므로
- Lower bound : 하한
// 관심있는 부분 집합(S) 하한, 한쪽 집합에만 포함되어서는 안됨. 

- GLB : 하한(Lower bound) 중에서 가장 큰것(Greatest)
- LUB : 상한(Upper bound) 중에서 가장 작은것(Least)

래티스 // 격자구조
: 모든 원소 쌍이 LUB와 GLB를 갖는 부분 순서 관계
 (시험>> 레티스 인것과 아닌 것은?)
어디선가 두개를 잡으면 올라가면서, 혹은 내려가면서 "공통"으로 만나는 "단 하나의 첫 번째 것"이 존재한다.


전체 순서 관계(Total Order Relation)
>> 부분순서관계에서는 (x,y)가 R에 속하다면 비교 가능, (x,y)가 R에 속하지 않다면 비교 불가능
 하지만 전체 순서 관계에서는 모든 원소가 "비교 가능"하다. 따라서 LUB와 GLB가 모두 존재함
 (ex. ≤ 관계)

전체 순서 관계

위상 정렬 알고리즘
: "부분순서 관계"를 입력받아서 "전체 순서 관계"로 변환함
(언제 사용됨? 여러명이 프로젝트를 진행하다가 >> 혼자 수행할 때)

Procedure topological sort
 k:=1
 while S≠∮
 ak := S의 최소  //집합에서 미니멀한 것을 초이스함
 S := S-{ak}   따라서 S가 공집합이 되면 반복문을 빠져나옴
 k := k+1
 return a1, a2, ... , an // 결과적으로 얻어지는 것은 시퀀스(=전체 순서, 체인)

혼자 남은 것부터 먼저 없앰 ({1,2,4,5,12,20}, | )의 위상정렬 >>  {1,5,2,4,20,12}



전이 클로우져(폐쇄) 
: 관계 R이 어떤 성질(전이적)을 만족하지 않을 때, 그 성질을 만족하도록 R을 최소한 확장해서 얻은 것을 클로우져라고 한다.
R의 클로우져 >> R* >> 전이적 관점에서 R이 전이적 성질을 만족하지 않을 때, 이를 확장한 것.
- R은 전이적 성질을 갖게됨.
- R⊆R*
- R*는 R의 최소 부분집합을 갖는다.

(예제)
A = {1,2,3,4}
R = {(1,2), (2,3), (3,4)}
>> R* = R ∪ {(1,3), (2,4)} ∪ {(1,4)}

어떻게 하면 전이 클로우저를 빠르게 구할 수 있을까?
"행렬"을 사용하자.

관계를 행렬로 표현
((행렬))
M = 0 0
      1 0
      1 1
((순서쌍))
R = {(2,1), (3,1), (3,2)}

관계를 행렬로 표현했다면
- 대각선이 1 >> 반사적
- 대각선을 기준으로 동일값 >> 대칭적
- 대각선을 기준으로 1일때 0 >> 반대칭적

관계의 합성
R⊆AxB and S⊆BxC
SºR ⊆ AxC
>> 관계의 합성은 ⨀(부울곱//각각을 논리곱으로 연산하고, 논리합으로 합침)와 동일한 기능을 한다.

전이 클로우져, 전이 폐쇄
R -> MR
R* = MR ∨ MR[2] ∨ MR[3] ∨... ∨MR[n]

전이 클로우저를 구하는 일반 알고리즘
Mr[2], Mr[3], ... n개의 원소가 있다면 Mr[n]까지 쭉 구할 텐데 
(바깥쪽 for문 n번) x (A와 Mr의 부울곱을 하게 되면 n³번) = 총 n⁴번의 계산이 필요

전이 클로우저 알고리즘

>> 평범한 알고리즘은 R -> R*의 전이클로우저에서 n⁴의 반복이 필요하다. 

워샬 알고리즘
R = W0 // 처음에 주어진 행렬, 전이적이지 않음
꼭짓점이라는 개념을 사용하여 W1>> 1개 확장, W2>>2개 확장(=W1), W3>>3개 확장
W4에서 전이 클로우저를 구할 수 있음. 
반복문의 개수가 n*n*n이므로 n³ 만큼의 반복으로 알고리즘을 줄이는 과정에 기여했다고 말함.

워샬 알고리즘