[이산수학] 집합론

집합에 대한 개념과 그에 따른 연산을 통하여 수학적 개념을 구체화할 수 있으며

이를 통한 문제 해결에 대한 접근 방식을 확인 할 수 있다

집합

#1 집합

집합은 원소라고 불리는 서로 다른 객체들의 모임

수학적 성징를 가지는 객체들의 모임으로 정확히 정의되어야 하며, 어떤 객체가 그 집합에 속하는지 아닌지를 분명히 구분할 수 있어야함

집합은 대상이 명확한 객체들의 모임 → 중복된 원소가 없어야함

#2 집합을 표현하는 방법

• 원소 나열법 : 집합의 원소들을 { } 사이에 하나씩 나열하는 방법 S = { 1,2,3,4,5 }
• 조건 제시법 : 집합의 원소들이 가지고 있는 특정한 성질을 기술하여 나타내는 방법 S = { x | p(x) } → x는 원소를 태표하는 변수, p(x)는 원소들이 가지고 있는 성질
• 카디날리티(Cardinality) 집합 S 내에 있는 서로 다른 원소들의 개수

→ 집합의 원소 개수가 유한할 경우 유한 집합, 집합의 원소 개수가 무한하면 무한 집합

→ 집합 S1에서 S2로의 일대일 대응 함수가 존재 = S1과 S2가 같은 카디날리티를 가짐

무한 집합의 경우에는 모두 같은 카디날리티를 가지지 않을 수 있음 → 정수들의 집합과 모든 실수들의 집합

• 가산적 집합 or 가산적으로 무한한 집합 정수의 집합과 일대일의 대응 관계에 있는 집합
• 전체 집합 : 집합론에서 관심을 두는 모든 원소를 가지는 집합
• 공집합 : 어떠한 원소도 가지지 않는 집합
• 부분 집합 : 집합 A의 모든 원소가 집합 B의 원소에 속하면 ‘집합 A는 집합 B에 포함된다’ - 집합 A는 집합 B의 부분 집합
• 진부분 집합 : 집합 A가 집합 B의 부분 집합이며 A와 B가 같지 않을 때 진부분 집합이라고 함
• → 진부분 집합의 개수 : S의 개수가 n ⇒ 부분집합의 개수 2^n개 ⇒ 진부분집합의 개수 2^n-1개
• 여집합 : 전체 집합U와 부분 집합 A에서 집합 U에 속하나 A에 속하지 않은 원소들의 집합

집합의 연산

#1 벤다이어그램

주어진 집합들 사이의 관계와 집합의 연산에 대하여 이해하기 쉽도록 이용

전체 집합은 사각형 / 주어진 집합은 원으로 표시하여 사용

#2 합집합

집합 A 또는 B에 속하는 모든 원소의 집합

 

#3 교집합과 서로소

두 집합 A, B에 대하여 이들의 교집합은 집합 A에도 속하고 집합 B에도 속하는 모든 원소의 집합

서로소의 경우 해당 교집합이 공집합 → 집합 A와 집합 B가 공통된 원소를 하나도 가지지 않은 경우

#4 차집합

두 집합 A, B에 대하여 이들의 차집합은 집합 A에 속하고 집합 B에 속하지 않은 모든 원소들의 집합

#5 대칭 차집합

집합 A, B에 대하여 이들의 대칭 차집합은 A,B의 합집합의 원소중에서 A,B의 교집합에 속하지 않은 모든 원소들의 집합

#6 곱집합

순서쌍은 순서로 구분되는 원소들의 쌍으로 나타냄

순서쌍 (a,b)는 쌍의 원소들 간의 순서에 의해 구분

임의의 두 집합 A, B의 곱집합 : 집합 A에 속하는 모든 원소 x와 집합 B에 속하는 모든 원소 y에 대한 모든 (x,y)순서쌍의 집합

집합류와 멱집합

#1 집합류와 멱집합

집합류 : 집합의 집합

멱집합 : 임의의 집합 S에 대하여, S의 모든 부분 집합을 원소로 가지는 집합

#2 멱집합의 주의점

첫째, 멱집합을 구한 다음에는 멱집합의 원소 개수를 확인

둘째, 멱집합의 원소는 모두 집합이므로 공집합을 제외한 원소는 { }안에 작성

셋째, 원래 집합 A의 원소 중 집합인 원소 또한 원소이므로 멱집합에서는 추가적인 집합 표기 필요

→ a와 {a}는 다른 원소

집합의 분할

#1 분할의 3가지 조건

공집합이 아닌 임의의 집합 S의 분할 과정

#2 블록

분할의 원소인 Ai를 분할함

→ 분할은 집합을 구성하는 원소가 서로소이고 각 원소들의 합집합이 원래의 전체 집합