알고리즘 기초 다지기 : 이산수학 부분 순서 관계

이산수학의 핵심 개념 중 하나인 순서 관계는 컴퓨터 과학, 특히 데이터 구조와 알고리즘 설계에 깊숙이 관여하고 있습니다. 이번 글에서는 이산수학의 꽃이라고도 할 수 있는 부분 순서 관계를 시작으로 전순서 집합, 그리고 이를 시각적으로 표현하는 하세 도표까지, 초급자도 쉽게 이해할 수 있도록 자세히 설명해 드리겠습니다.

그전에 집합, 관계에 대해 알아야 합니다. 잘 모르신다면 아래 포스팅에서 확인하시기 바랍니다.

이산수학, 집합 연산 정복

이산수학 동치 관계와 분할

1. 부분 순서 관계 (Partially Ordered Relation)

순서 관계가 잘 와닿지 않는다면 부등호를 대입하면서 보시면 이해가 좀 더 될겁니다.

정의: 집합 A에 대한 관계 R이 다음 세 가지 조건을 만족할 때, R을 A에 대한 부분 순서 관계라고 합니다.

• 반사 관계 (Reflexive Relation): A의 모든 원소 a에 대해 (a, a) ∈ R 이 성립합니다. 즉, 모든 원소는 자기 자신과 관계를 맺습니다.
• 반대칭 관계 (Antisymmetric Relation): (a, b) ∈ R 이고 (b, a) ∈ R 이면 a = b 입니다. 즉, a가 b보다 "앞서고" b가 a보다 "앞선다면" a와 b는 같은 원소여야 합니다.
• 추이 관계 (Transitive Relation): (a, b) ∈ R 이고 (b, c) ∈ R 이면 (a, c) ∈ R 입니다. 즉, a가 b보다 "앞서고" b가 c보다 "앞선다면" a는 c보다 "앞섭니다".

이 세 가지 조건을 모두 만족하는 관계를 부분 순서 관계라고 부르며, 이러한 관계가 정의된 집합을 부분 순서 집합 (Partially Ordered Set, Poset) 이라고 합니다.

예시:

• 집합 A = {1, 2, 3} 에 대해, R = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3)} 은 부분 순서 관계입니다. (각 조건을 만족하는지 확인해 보세요!)
• 우리가 흔히 사용하는 부등식 "≤" 도 부분 순서 관계입니다.

 

2. 비교 가능 (Comparable)과 전순서 집합 (Totally Ordered Set)

부분 순서 집합 (A, ≼) 에서 A의 원소 a, b가 a ≼ b 또는 b ≼ a를 만족할 때, a와 b는 비교 가능 (Comparable) 하다고 합니다. 즉, 두 원소 사이에 순서 관계가 정의되어 있다는 의미입니다.

만약 집합 A의 모든 원소 쌍이 비교 가능하다면, A를 전순서 집합 (Totally Ordered Set) 이라고 합니다. 전순서 집합에서는 어떤 두 원소를 가져와도 누가 먼저인지, 혹은 같은지 판단할 수 있습니다.

정의: 전순서 집합에서의 부분 순서 관계를 전순서 관계 (Totally Ordered Relation) 라고 합니다.

예시:

• 실수 집합 R 에 대한 "≤" 관계는 전순서 관계입니다. 왜냐하면 어떤 두 실수를 가져와도 크기를 비교할 수 있기 때문입니다.
• 자연수 집합 N 에 대한 약수 관계 (a가 b의 약수이다)는 부분 순서 관계이지만 전순서 관계는 아닙니다. 예를 들어, 2와 3은 서로 약수 관계가 아니므로 비교 불가능합니다.

 

 

 

 

 

3. 곱 부분 순서 관계 (Product Partial Ordered Relation)와 사전식 순서 (Lexicographic Order)

두 개의 부분 순서 집합이 있을 때, 이들을 결합하여 새로운 부분 순서 집합을 만들 수 있습니다. 이를 곱 부분 순서 관계 (Product Partial Ordered Relation) 라고 합니다.

(A, ≼)와 (B, ≼)가 부분 순서 집합이면 (A × B, ≼)도 부분 순서 집합입니다. 여기서 A × B는 A와 B의 데카르트 곱 (Cartesian Product)을 의미합니다. 즉, A × B = {(a, b) | a ∈ A, b ∈ B} 입니다.

곱 부분 순서 관계를 정의하는 방법 중 가장 흔한 것이 사전식 순서 (Lexicographic Order) 입니다. 사전식 순서는 마치 사전에서 단어를 정렬하는 방식과 유사합니다.

정의: (A, ≼)와 (B, ≼)를 부분 순서 집합이라고 할 때, A × B 위의 사전식 순서 ≼_lex 는 다음과 같이 정의됩니다.

(a₁, b₁) ≼_lex (a₂, b₂) if and only if a₁ ≺ a₂ or (a₁ = a₂ and b₁ ≼ b₂)

즉, 첫 번째 원소(a₁, a₂)를 비교하여 순서를 결정하고, 만약 첫 번째 원소가 같다면 두 번째 원소(b₁, b₂)를 비교하여 순서를 결정합니다.

예시:

• A = {1, 2}, B = {a, b} 라고 할 때, A × B = {(1, a), (1, b), (2, a), (2, b)} 입니다. 사전식 순서에 따라 정렬하면 (1, a) ≺ (1, b) ≺ (2, a) ≺ (2, b) 가 됩니다.

4. 하세 도표 (Hasse Diagram): 시각적인 표현

부분 순서 집합을 시각적으로 표현하는 강력한 도구가 바로 하세 도표 (Hasse Diagram) 입니다. 하세 도표는 부분 순서 관계를 간결하고 직관적으로 나타내줍니다.

하세 도표 그리는 방법:

1. 집합의 각 원소를 점으로 표현합니다.
2. x ≼ y 이고 x와 y 사이에 다른 원소 z가 존재하지 않아 x ≼ z ≼ y 를 만족하는 z가 없을 때만 x에서 y로 선을 긋습니다. (이때 x는 y보다 아래에 위치합니다.)
3. 화살표는 생략합니다. (모든 선은 아래에서 위로 향한다고 가정합니다.)
4. 반사 관계는 생략합니다. (모든 원소는 자기 자신과 관계를 맺는다고 가정합니다.)
5. 추이 관계는 생략합니다. (x ≼ y 이고 y ≼ z 이면 x ≼ z 이므로 직접 연결하지 않습니다.)

예시:

• 집합 A = {1, 2, 3, 6} 에 대해, 약수 관계 (a가 b의 약수이다)를 하세 도표로 나타내면 다음과 같습니다.

      6
     / \
    2   3
   /   /
  1

하세 도표를 통해 1은 2, 3, 6의 약수이고, 2와 3은 6의 약수임을 쉽게 확인할 수 있습니다. 또한, 2와 3은 서로 약수 관계가 아니므로 연결되어 있지 않습니다.

 

5. 이산수학, 왜 중요할까요?

이산수학은 컴퓨터 과학의 근간을 이루는 학문입니다. 특히, 순서 관계는 데이터베이스, 알고리즘, 프로그래밍 언어 등 다양한 분야에서 활용됩니다.

• 데이터베이스: 데이터베이스에서 레코드를 정렬하거나 검색할 때 순서 관계가 사용됩니다.
• 알고리즘: 정렬 알고리즘, 탐색 알고리즘 등 다양한 알고리즘이 순서 관계를 기반으로 작동합니다.
• 프로그래밍 언어: 프로그래밍 언어에서 객체의 상속 관계를 정의할 때 순서 관계가 사용됩니다.

이처럼 이산수학은 컴퓨터 과학을 이해하고 활용하는 데 필수적인 지식을 제공합니다. 특히, 이산수학의 순서 관계 개념은 복잡한 문제를 체계적으로 분석하고 해결하는 데 도움을 줍니다. 이산수학을 제대로 공부하면 컴퓨터 과학 분야에서 더욱 깊이 있는 이해와 문제 해결 능력을 갖출 수 있습니다. 이산수학은 단순한 이론이 아니라 실질적인 문제 해결에 적용되는 강력한 도구입니다. 이산수학을 통해 여러분의 코딩 실력을 한 단계 업그레이드해 보세요!

결론

이번 글에서는 이산수학의 핵심 개념인 부분 순서 관계, 전순서 집합, 그리고 하세 도표에 대해 자세히 알아보았습니다. 이산수학은 처음 접하는 사람에게는 다소 어렵게 느껴질 수 있지만, 꾸준히 공부하고 다양한 예제를 통해 익숙해지면 컴퓨터 과학 분야에서 큰 도움이 될 것입니다.

이제 여러분의 차례입니다! 주변에서 흔히 볼 수 있는 집합과 관계를 찾아 부분 순서 관계인지 확인해보고, 하세 도표를 직접 그려보면서 오늘 배운 내용을 복습해 보세요. 댓글로 여러분의 경험과 질문을 공유해 주시면 함께 고민하고 답변해 드리겠습니다. 여러분의 적극적인 참여를 기다립니다!

참조 목록

1. Wikipedia - Partial Order: https://en.wikipedia.org/wiki/Partially_ordered_set
2. Khan Academy - Relations: https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs (그래프 이론과 연결하여 이해할 수 있습니다.)
3. Discrete Mathematics and Its Applications, Kenneth H. Rosen: 이산수학 교과서 (Rosen)

주의: 위 참조 목록은 부분 순서 관계에 대한 더 자세한 정보와 관련된 수학적 엄밀성을 제공합니다. 이 글에서 제공된 내용은 이해를 돕기 위한 단순화된 설명입니다.