자료구조를 위한 수학적 기초

Relation(관계)

• 관계는 두 집합의 데카르트 곱의 부분집합. 집합 $ A $와 $ B $에 대해 관계 $ R $은 다음과 같이 정의됨:

\[R \subseteq A \times B\]

여기서 $ A \times B = \{ (a, b) \mid a \in A, b \in B \} $

관계의 성질

1. Reflexive: $ R $이 reflexive이려면 $ \forall a \in A, (a, a) \in R $
   • 예시:
     관계 $R$이 $\leq$(작거나 같다)일때, 모든 수 $a$에 대해 $a\leq a$가 참 - reflexive
2. Symmetric: $ R $이 Symmetric이려면 $ \forall a, b \in A, (a, b) \in R \implies (b, a) \in R $
   • 예시:
     관계 $ R $이 “a는 b의 친구”일 때, $ a = b $이면 $ b = a $가 항상 참이므로 symmetric.
3. Antisymmetric: $ R $이 antisymmetric이려면 $ \forall a, b \in A, (a, b) \in R \land (b, a) \in R \implies a = b $
   • 예시:
     관계 $ R $이 $\leq$(작거나 같다)일 때, $ (a, b) \in R $이고 $ (b, a) \in R $이면 $ a = b $가 되어야 하므로 antisymmetric.
4. Transitive: $ R $이 transitive이려면 $ \forall a, b, c \in A, (a, b) \in R \land (b, c) \in R \implies (a, c) \in R $
   • 예시:
     관계 $ R $이 “a는 b의 조상”일 때, $ a $가 $ b $의 조상이고 $ b $가 $ c $의 조상이라면 $ a $는 $ c $의 조상이므로 transitive.

관계의 종류

1. Equivalence Relation (동치 관계):
   • Reflexive, Symmetric, Transitive 성질을 모두 만족하는 관계.

   • 관계 $ R $이 “같다”일 때, $ a = a $ (Reflexive), $ a = b \implies b = a $ (Symmetric), $ a = b \land b = c \implies a = c $ (Transitive).

   • 예시
     • mod equivalene: $ a \equiv b \pmod{n} $는 $ n $으로 나눈 나머지가 같을 때 성립.
       • Reflexive: $ a \equiv a \pmod{n} $
       • Symmetric: $ a \equiv b \pmod{n} \implies b \equiv a \pmod{n} $
       • Transitive: $ a \equiv b \pmod{n} \land b \equiv c \pmod{n} \implies a \equiv c \pmod{n} $
2. Partial Order (부분 순서):
   • Antisymmetric, Transitive 성질을 만족하는 관계.
   • 예시:

     • “작거나 같다” 관계 $ R $이 “작거나 같다”일 때, $ a \leq b \land b \leq a \implies a = b $ (Antisymmetric), $ a \leq b \land b \leq c \implies a \leq c $ (Transitive).

     • “키가 더 크고 몸무게가 더 많다”

       • Antisymmetric: $ a $의 키와 몸무게가 $ b $의 키와 몸무게와 같다면, $ a $와 $ b $는 동일한 사람이어야 함.
       • Transitive: $ a $가 $ b $보다 키가 크고 몸무게가 많으며, $ b $가 $ c $보다 키가 크고 몸무게가 많다면, $ a $는 $ c $보다 키가 크고 몸무게가 많음.
3. Total Order:
   • Partial Order의 모든 성질을 만족하며, 추가로 모든 $ a, b \in A $에 대해 $ a \leq b $ 또는 $ b \leq a $가 성립하는 관계.
   • 예시:
     관계 $ R $이 “작거나 같다”일 때, $ a \leq b $ 또는 $ b \leq a $가 항상 성립하므로 Total Order.
     • “키가 더 크고 몸무게가 더 많다” 는 어떤 관계에 대해서는 성립하지 않을 수 있기 때문에 total order가 아님(키만 더 크거나, 몸무게만 더 많은 경우 존재)

Recursive Relation (재귀적 관계)

• 재귀적 관계는 자기 자신을 활용하여 정의되는 함수.
• 예시:
  • 피보나치 수열 관계: \(T(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ T(n-1) + T(n-2) & \text{if } n > 1 \end{cases}\)
  • 자연수의 팩토리얼 관계: \(T(n) = \begin{cases} 1 & \text{if } n = 0 \\ n \cdot T(n-1) & \text{if } n > 0 \end{cases}\)
• Closed Form
  • Closed Form는 재귀적 관계를 명시적으로 표현한 형태로, 반복적인 계산 없이 결과를 구할 수 있음.
  • 예시:
    • $T(n) = T(n-1) + n; \ T(1)=1$
  • Closed Form: $ T(n) = \frac{n(n+1)}{2} $

Tower of Hanoi 문제

• 정의:
  • Tower of Hanoi는 $ n $개의 원판을 한 기둥에서 다른 기둥으로 옮기는 문제로, 다음 규칙을 따름:
    1. 한 번에 하나의 원판만 옮길 수 있음.
    2. 더 큰 원판이 더 작은 원판 위에 놓일 수 없음.
    3. 원판은 항상 세 개의 기둥 중 하나에 있어야 함.
• 재귀적 관계:

  • 하노이 타워 문제는, $ n - 1 $개의 원판을 경유하는 기둥에 옮기고, 가장 큰 원판을 목적 기둥에 옮긴 다음 다시 $ n - 1 $개의 원판을 목적 기둥에 옮기는 문제로 표현할 수 있음(Recursive)

  • $ T(n) $은 $ n $개의 원판을 옮기는 데 필요한 최소 이동 횟수: \(T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1\)

• Closed Form:
  • $ T(n) = 2^n - 1 $

Mathmatical Proof

Deduction

• Deduction은 일반적인 원리나 법칙에서 특정한 결론을 도출하는 논리적 추론 방법.
• $P \Rightarrow Q$, $Q \Rightarrow R$, then $P\Rightarrow Q$
• 예시:
  • $ P $가 “모든 사람은 죽는다”이고, $ Q $가 “소크라테스는 사람이다”일 때, $ P \land Q $가 참이면 $ R $이 “소크라테스는 죽는다”가 참임을 보일 수 있음.

Contradiction

• Contradiction은 어떤 명제가 참임을 보이기 위해 그 명제가 거짓이라고 가정한 후, 논리적 모순을 도출하는 방법.
• 예시:
  • $ \sqrt{2} $가 무리수임을 증명:
    1. $ \sqrt{2} $가 유리수라고 가정. 즉, $ \sqrt{2} = \frac{p}{q} $이며, $ p $와 $ q $는 서로소 정수.
    2. 양변을 제곱하면 $ 2 = \frac{p^2}{q^2} $, 즉 $ p^2 = 2q^2 $.
    3. $ p^2 $는 2의 배수이므로 $ p $도 2의 배수. 따라서 $ p = 2k $로 표현 가능.
    4. $ p^2 = 4k^2 $를 $ 2q^2 $에 대입하면 $ 2q^2 = 4k^2 $, 즉 $ q^2 = 2k^2 $.
    5. $ q^2 $도 2의 배수이므로 $ q $도 2의 배수.
    6. $ p $와 $ q $가 모두 2의 배수이므로 서로소가 아니라는 모순 발생.
    7. 따라서 $ \sqrt{2} $는 무리수임이 증명됨.

Mathematical Induction

• Mathematical Induction(수학적 귀납법) 은 특정한 사례들로부터 일반적인 결론을 도출하는 논리적 추론 방법.
• 수학적 귀납법은 다음 두 단계를 통해 증명함:
  1. 기초 단계(Base Case): 명제가 특정 단계에서 참임을 보임.
  2. 귀납 단계(Inductive Step): $ n = k $에서 명제가 참이라고 가정하고, $ n = k + 1 $에서도 참임을 보임.
• 예시:
  • $ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} $ 증명:
    1. 기초 단계: $ n = 1 $일 때, $ 1 = \frac{1(1+1)}{2} $이므로 참.
    2. 귀납 단계: $ n = k $에서 $ 1 + 2 + \cdots + k = \frac{k(k+1)}{2} $라고 가정.
       $ n = k + 1 $일 때: \(1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)\) \(= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}\) 따라서 $ n = k + 1 $에서도 참임을 보였으므로, 수학적 귀납법에 의해 명제가 성립.

---

해당 포스트는 서울대학교 컴퓨터공학부 강유 교수님의 자료구조 25-1학기 강의를 정리한 내용입니다.