[확률] 6.1 집합

데이터 사이언스 스쿨

집합과 원소

구별 가능한 객체의 모임을 집합(set) 이라고 하고 집합에 포함된 구별 가능한 객체를 그 집합의 원소(element) 라고 한다. 원소 $x$와 그 원소를 포함하는 집합 $A$의 관계는 다음처럼 표시한다.

만약 원소 $x$가 집합 $A$에 포함되지 않는다면 다음처럼 표시한다.

파이썬에서는 set과 frozenset 자료형으로 집합을 나타낸다. set은 내용을 변경할 수 있는 뮤터블(mutable)자료형이고 frozenset은 내용을 변경할 수 없는 임뮤터블(immutable)자료형이다. (리스트 자료형과 튜플 자료형의 관계와 같다.) 뮤터블 자료형은 딕셔너리(dictionary) 자료형의 키(key)나 혹은 set 자료형의 원소가 될 수 없다. 임뮤터블 자료형만 딕셔너리 자료형의 키나 set 자료형의 원소가 될 수 있다.

A = set([1, 2, 3, 3, 2])  # 중복된 자료는 없어진다.
A

{1, 2, 3}

B = frozenset(['H', 'T'])
B

frozenset({'H', 'T'})

set 자료형은 { } 기호를 사용하여 만들 수도 있다.

C = {"\u2660", "\u2661", "\u2662", "\u2663"}
C

{'♠', '♡', '♢', '♣'}

type(C)

집합의 크기

집합의 크기(cardinality) 는 집합이 가지는 원소의 갯수를 말한다. $\vert A \vert$ 기호나 $\text{card}$ 기호를 사용하여 나타낸다. 만약 $A = \{ 1, 2, 3 \}$이면,

파이썬에서는 len 명령을 사용하여 집합의 원소의 갯수를 구한다.

len(A), len(B), len(C)

(3, 2, 4)

이러한 무한집합은 파이썬의 set 또는 frozenset 자료형으로 표현할 수 없다.

합집합과 교집합

두 집합의 합집합(union) 은 각 집합의 원소를 모두 포함하는 집합을 말하고 $\cup$ 기호를 사용하여 표시한다. 두 집합의 교집합(intersection) 은 두 사건 모두에 속하는 원소로만 이루어진 집합을 말하고 $\cap$ 기호를 사용하여 표시한다.

파이썬에서는 union, intersection 메서드나 |, & 연산자로 합집합과 교집합을 구할 수 있다.

A1 = set([1, 2, 3, 4])
A2 = set([2, 4, 6])
A3 = set([1, 2, 3])
A4 = set([2, 3, 4, 5, 6])

A1.union(A2)

{1, 2, 3, 4, 6}

A2 | A1

{1, 2, 3, 4, 6}

A3.intersection(A4)

{2, 3}

A4 & A3

{2, 3}

전체집합, 부분집합, 여집합

어떤 집합의 원소 중 일부만을 포함하는 집합을 부분집합(subset) 이라고 하고 원래의 집합을 전체집합이라고 한다. 집합 $A$가 집합 $\Omega$의 의 부분집합이면 다음처럼 표시한다.

모든 집합은 자기 자신의 부분집합이다.

원소의 크기가 더 작은 부분집합을 진부분집합(proper subset) 이라고 한다. 파이썬에서는 두 집합이 부분집합인지를 알아보는 issubset 메서드가 있다. 객체가 인수의 부분집합이면 True를 반환한다. 등호를 포함하는 부등식 연산자로도 같은 결과를 구할 수 있다. 더 작은 쪽이 부분집합이다. 등호가 없는 부등식 연산자는 진부분집합 관계를 구한다.

A3.issubset(A1)

True

A3 <= A1

True

A3.issubset(A2)

False

A3 <= A2

False

A3 <= A3  # 모든 집합은 자기 자신의 부분집합이다.

True

A3 < A3  # 모든 집합은 자기 자신의 진부분집합이 아니다.

False

차집합과 여집합

어떤 집합 $A$에 속하면서 다른 집합 $B$에는 속하지 않는 원소로 이루어진 $A$의 부분집합을 $A$에서 $B$를 뺀 차집합(difference) 이라고 한다.

전체집합 $\Omega$ 중에서 부분집합 $A$에 속하지 않은 원소로만 이루어진 부분집합을 여집합(complement)이라고 한다.

파이썬에서는 difference 메서드 혹은 - 연산자로 차집합을 구한다.

A1.difference(A2)

{1, 3}

A1 - A2

{1, 3}

공집합

아무런 원소도 포함하지 않는 집합을 공집합(null set) 이라고 하며 $\emptyset$ 기호로 나타낸다. 공집합은 모든 집합의 부분집합이 된다. 또한 임의의 집합과 공집합의 교집합은 공집합이, 임의의 집합과 공집합의 합집합은 그 집합 자신이 된다. 여집합과 원래의 집합의 교집합은 공집합이다.

empty_set = set([])
empty_set

set()

empty_set < A1

True

empty_set.intersection(A1)

set()

empty_set.union(A1)

{1, 2, 3, 4}

부분집합의 수

집합 $A = \{ 1, 2 \}$는 다음과 같은 4개의 부분집합을 가진다.
$A_1 = \emptyset, A_2 = \{ 1 \}, A_3 = \{ 2 \}, A_4 = \{ 1, 2 \}$

부분집합을 만들때 우리가 결정할 수 있는 것은 각각의 원소가 우리가 만들고자 하는 부분집합에 포함되느냐 포함되지 않느냐이다. $N$개의 원소 모두에 대해 이러한 의사결정을 하면 부분집합의 갯수는 우리가 할 수 있는 의사결정의 가짓수인 $2^N$개가 된다.

[정리] 원소의 갯수가 $N$개인 집합은 $2^N$개의 부분집합을 가진다.

연습 문제 6.1.1

(1) 이 집합의 부분집합의 갯수는?

✏️
$2^4=16$ 개

(2) 이 집합의 모든 부분집합을 frozenset 자료형 객체로 만들고 이 부분집합들을 원소로 가지는 하나의 set 객체를 만든다. 이 집합은 일종의 "부분집합의 집합"이 된다.

✏️
파이썬에서 부분집합 구하기
itertools를 사용해서 모든 부분집합을 원소로 갖는 집합을 구한다.

from itertools import chain, combinations
def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
omega = {'HH', 'HT', 'TH', 'TT'}
all_subsets = set(frozenset(subset) for subset in powerset(omega))
print(len(all_subsets))
print(all_subsets)

16 
{frozenset({'TH'}), frozenset({'HH', 'HT'}), frozenset({'HT'}), frozenset({'HH', 'TH'}), frozenset({'HH', 'HT', 'TH', 'TT'}), frozenset({'HT', 'TH'}), frozenset({'HH', 'HT', 'TT'}), frozenset({'HH', 'TH', 'TT'}), frozenset({'HH', 'TT'}), frozenset({'TH', 'TT'}), frozenset({'HT', 'TT'}), frozenset(), frozenset({'HH'}), frozenset({'HT', 'TH', 'TT'}), frozenset({'TT'}), frozenset({'HH', 'HT', 'TH'})} 

합집합과 교집합의 분배 법칙

교집합과 합집합도 괄호를 풀어내는 분배법칙이 성립한다.

연습 문제 6.1.2

다음 세 집합 $A$, $B$, $C$에 대해 위에서 말한 두가지 분배법칙이 성립하는지 파이썬 코드로 증명하라.

✏️

A = set([1,3,5])
B = set([1,2,3])
C = set([2,4,6])
print(A | ( B & C) == ((A | B) & (A | C)))
print(A & ( B | C) == ((A & B) | (A & C)))

  
True True