집합, 관계

계산이론 내용에 들어가기 앞서 수학적인 내용을 정리하는 부분입니다.

 

집합 (Set)

집합은 원소들의 모음입니다.

표기는 다음과 같이 작성합니다.

 

x ∉ S : x는 집합 S의 원소가 아님.

x ∈ S : x는 집합 S의 원소.

 

집합 중에서 원소의 개수가 유한한 집합을 유한(Finite) 집합이라고 하고, 원소의 개수가 무한한 집합을 무한(Infinite) 집합 이라고 합니다.

 

집합의 정의는 크게 2가지로, 원소 나열법(Enumeration), 조건 제시법(Comprehension) 이 있습니다.

원소 나열법은 집합의 원소를 쭉 작성하는 방법이고, 조건 제시법은 어떤 조건 x를 작성해두는 것으로 해당 집합에는 조건 x에 맞는 원소만 있습니다.

 

ex) {i | i  > 0, i % 2 == 1} 해당 조건으로 집합 S를 정의하면, S의 모든 원소는 0보다 큰 홀수로 구성됩니다.

 

집합의 연산은 합집합, 곱집합, 차집합, 여집합이 있습니다.

 

- 합집합(Union)은 집합 2개의 원소를 합치는 것입니다. {x | x ∈ S1 or x ∈ S2}

- 교집합(Intersection)은 집합 2개의 공통 원소를 합치는 것입니다. {x | x ∈ S1 and x ∈ S2}

- 차집합(Difference)는 집합 S1에서 집합 S2의 원소를 제외한 집합을 구합니다. {x | x ∈ S1 and x ∉ S2}

- 여집합(Complement)는 전체 집합 U에서 집합 S의 원소를 제외한 집합을 구합니다. {x | x ∈ U and x ∉ S}

 

공집합(Empty Set, Ø )은 다음과 같은 특징을 가집니다.

 

S ∪ Ø = S - Ø = S

S ∩ Ø = Ø

Ø^c (Complement) = U

(S^c)^c (Complement) = S

 

DeMorgan's Law

 

(S1 ∪ S2)' = S1' ∩ S2'

(S1 ∩ S2)' = S1' ∪ S2'

 

부분집합(Subsets) 이란 S1의 모든 원소가 S2의 원소인 경우입니다. (S1 ⊆ S2)

 

진부분집합(Proper subset) 이란 S1이 S2에 부분집합이면서, S2가 S1에 속하지 않은 원소를 포함하고 있는 경우입니다. (S1 ⊂ S2)

 

서로소(Disjoint)는 S1과 S2가 서로소인 경우를 의미합니다. (S1 ∩ S2 = Ø)

 

분할(Partition)은 S1, S2, S3, ... , Sn 이 집합 S의 부분 집합이고, Si 가 서로소이면서, Si의 합집합은 S이고 Si의 어느 것도 공집합이 아닐 때, Si는 S의 분할이라고 부릅니다.

(S1 ∩ S2 ∩ S3 ∩ ... ∩ Sn = Ø, S1 ∪ S2 ∪ S3 ∪ ... ∪ Sn = S, Si ≠ Ø)

 

집합 연산자는 동등, 크기, 멱집합, 곱이 있습니다.

 

- 동등(Equivalence)는 S1의 모든 원소가 S2의 원소이고, S2의 모든 원소 또한 S1의 원소 일때, S1 = S2로 표기합니다.

- 크기(Size)는 S의 원소의 수를 표기합니다. |Ø| = 0

- 멱집합(Powerset)은 집합 S의 모든 부분집합들을 원소로 가지는 집합을 말합니다. 2^S

ex) S = {a, b, c}, 2^S = { Ø , {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} |2^S| = 8

- 곱(Cartesian Product)은 S1의 원소와 S2의 원소의 순서쌍 집합을 만들어냅니다. 단, 이때 집합 곱의 교환법칙은 성립하지 않습니다. (S = S1 X S2 = {(x, y) | x ∈ S1, y ∈ S2}

ex) S1 = {2, 4}, S2 = {a, b}일때, S1 X S2 = { (2,a), (2,b), (4,a), (4,b) }

 

관계(Relations)와 함수(Function)

집합 A로부터 집합 B로 부터의 관계 R (R ⊆ A X B, (a, b) ∈ R)

ex) A = {1, 2}, B = {3, 4}, R = { (1,3), (1,4), (2,3), (2,4) } 이 때, 이 관계 R에서 1과 3은 연관되어있음.

 

R의 정의역(Domain)과 치역(Image)는 다음처럼 정의됩니다.

Dom(R) = {a | a ∈ A and (a,x) ∈ R for some x ∈ B}

Im(R) = {b | b ∈ B and (y, b) ∈ R for some y ∈ A}

 

ex) A = {a,b}, B = {1, 2, 3}, R = { (a,1), (a,2) } 일때, Dom(R) = {a}, Im(R) = {1, 2}

 

X에 대한 동등 관계 R의 특성은 다음 3가지가 있습니다.

 

- 반사적(Reflexive)은 모든 a ∈ X에 대해서, (a, a) ∈ R

- 대칭적(Symmetric)은 (a,b) ∈ R이라면, (b, a) ∈ R

- 추이적(Transitive)는 R에서 (a,b)이고, (b,c)라면, (a,c) ∈ R

 

A로부터 B의 관계인 함수 f는 A로부터 B인 R로서, 다음 조건이 성립합니다.

 

Dom(f) = A and (x,y) ∈ f and (x, z) ∈ f 라면, 항상 y = z ( 함수는 정의역의 한 원소에 대한 치역의 값이 유일하다. )

 

함수의 동등은 두 관계 f : A → B 와 g : A → B 가 함수라면, 모든 x ∈ A에 대해서, f = g and f(x) = g(x) 을 말합니다.

 

전체함수(total functions)는 f ⊆ A X B and Dom(f) = A 인 경우입니다.

= f가 모든 정의역에 대해서 연관된 값이 있음.

부분함수(partial functions)는 f ⊆ A X B and Dom(f) ⊆ A 인 경우입니다. 

= 정의역의 일부분에 대해서 연관된 값이 있음.