[이산수학] 집합(Set) 용어정리

1. 집합 용어정리

set(집합)
순서상관 x, 중복여부x, 다른 set을 포함 가능한 원소들의 집함합. {}로 원소들을 표시한다.
ex) {1, 2, 3, 4, 5, {1, 2}}와 {3, 5, 2, 4, {1, 2}, 1}는 같은 집합이다.


set builder notation(조건제시법)
조건에 따라 원소들을 표시한 집합 정의 방법
ex) D = {x | x is prime and x> 2}: x가 2보다 큰 소수들의 집합


Universal set(전체집합, U)
모든 대상을 (자기 자신까지도) 원소로 포함하는 집합


empty set or null set(공집합, Ø)
원소가 하나도 없는 집합.

특징:

모든 집합은 공집합을 부분집합으로 가진다.
A U Ø = A
A ∩ Ø = Ø



subset(부분집합, ⊆)
A ⊆ B, A가 B의 부분집합이라는 의미는, A의 모든 원소가 B에도 존재한다는 뜻이다.

{1, 2}는 {1, 2, 3}의 부분집합
{1,2,3}은 {1, 2, 3}의 부분집합

proper subset(진부분집합, ⊂): 부분집합에서 자기 자신을 제외한 집합을 말한다.

{1, 2}는 {1, 2, 3}의 진부분집합
{1,2,3}은 {1, 2, 3}의 진부분집합이 아니다

set cardinality(집합의 크기) : 부분집합의 개수를 말한다. 원소가 n개 있는 집합이라면 원소의 개수는 2^n개다.


power set(멱집합): 모든 부분집합을 원소로 가지는 집합
ex) T = {0, 1, 2}일때, P(T) = {Ø, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}}다.
즉, power set의 원소의 개수는 2^n개다.

참고로 P(Ø) = {Ø}이다. (모든 집합은 Ø을 자신의 부분집합으로 가지고 있으니깐)


tuple(순서쌍): 순서가 존재하는 집합이다. ()로 표기한다.대표적인 예로 좌표계가 있다.
ex) (1,2), (2,1)은 서로 다른 순서쌍이자, 좌표계다.


cartesion product: 원소를 이용해 만들어진 순서쌍을 의미한다.

A = {팔레트, 똘똘, 을숙}, B = {1, 2, 3}일 경우
cartesion product = (팔레트, 1), (팔레트, 2), (팔레트, 3), (똘똘, 1), (똘똘, 2), (똘똘, 3), (을숙, 1), (을숙, 2), (을숙, 3)

 

2. Set Operation(집합 연산자)

Union(합집합)
A∪B: A와 B의 요소 모두 포함하는 집합 - ∨(or)와 개념이 같다

Intersection(교집합)
A∩B: A와 B의 공통요소만 포함하는 집합 - ∧(and)와 개념이 같다

Disjoint(차집합)
A-B: A의 원소는 포함하지만 B의 원소는 포함하지 않는 집합

참고로 위의 관계가 성립한다.

Symmetric Difference
A⊕B = (A∪B) - (A∩B)

Complement set(여집합)
A^C : 전체집합에서 A의 원소를 제외한 집합