1) 집합

집합이란?

 

집합이란 원소들의 모임이다. x가 집합 S의 원소임을 나타내면  "x∈S"로 표기한다.

ex) 정수 0,1,2를 포함하는 집합 : S={0,1,2}

 

집합 표현시에 의미가 명확한 경우에는 생략부호를 사용 할 수 있다.집합 {a,b,c....,z}는 알파벳 소문자들의 집합이고, 집합 {2,4,6,8.....}은 정수중에 짝수의 집합을 의미한다. 필요에 따라서는 짝수들의 집합을 아래와 같이 표현할 수 있다.

 

S={i:i>0, i is even}

 

이를 읽을때는 "S는 0보다 크고 짝수인 모든 i들의 집합"라 한다.

 

 

많이 사용되는 집합연산

 

합집합: A∪B={x:x∈A or x∈B}

교집합: A∩B={x:x∈A and x∈B}

차집합: A-B={x:x∈A and x∈B}

 

드모르간 법칙

 

부분집합: 어떤 집합 S1의 모든 원소들이 집합 S의 원소이면 S1은 S의 부분집합

S1⊆S

 

진부분집합: S1이 S의 부분집합이면서  S가 S1에 존재하지 않는 원소를 포함하는 경우 S1을 S의 진부분집합이라 한다.

S1⊂S

 

멱집합: 한 집합 S의 모든 부분 집합달의 집합을 S의 멱집합이라한다. 

ex)집합 s={a,b,c }일때, S의 멱집합은 {∮,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 이다.

 

$$2^S$$

 

카티션곱 : 한 집합의 원소들이 다른 여러 집합 원소들의 순서열인 집합.

ex)S_1={2,4}, S_2={2,3,5,6}일때, 카티션 곱은 {(2,2),(2,3),(2,5),(2,6),(4,2),(4,3),(4,5),(4,6)}이다.

 

S_1 * S_2 ={(x,y :x∈S_1,y∈S_2)} 

 

분할: S_1, S_2, S_3, S_4...S_n은 집합 S의 부분집합이라 했을때,

1. 부분집합 S_1, S_2, S_3, S_4... S_n은 서로 서로소

2. S_1 ∪ S_2 ∪ S_3 ∪ S_4.... ∪ S_n=S

3. S_i들은 모두 공집합이 아니다.

위 조건들을 모두 만족했을떄, S_1, S_2, S_3, S_4...S_n을 S의 분할이라고 한다.