앞만 보는 사람

정리에 앞서, 저는 현재 지거국 3학년으로 재학 중인 공대생입니다. 여기에 나와있는 내용들은 제가 직접 공부하고 요약해서 쓰기 때문에 정확하지 않은 정보가 있거나, 원하는 정보를 얻지 못하실 수 있습니다. 최대한 객관적이고 다양하게 준비해서 올리도록 노력하겠습니다. 자료의 출처나 내용에 대한 질문은 댓글이나 hcbeom9635@gmail.com으로 보내주시면 감사하겠습니다.

저는 공부할 때 Discrete Mathematics - Richard Johnsonbaugh 7th 제본판을 사용했습니다.

이산수학 1장. Sets and Logic

집합(Set)이란?

Set(집합)은 서로 다른 물체들의 모음 입니다. 그리고 집합 안에 있는 것을 Elements(원소)라고 불립니다.

예를 들어 집합 A에 원소 x가 있다면 아래와 같이 간단하게 표현합니다.

x라는 원소를 조금 더 구체화 시켜서 예를 들어봅시다.

A안에 {1,3,5,7}라는 원소가 있어서 1은 A에 속한다고 볼 수 있습니다. 

또한 B안에는 k가 0~5까지의 상수이므로 {1,3,5,7,9,11}라는 원소가 있어서 3또한 A에 속합니다.

이렇게 간단하고 유한한 집합을 Finite sets이라고 불립니다.

반대로 무한한 집합을 Infinite sets이라고 합니다. 무한한 집합은 무엇이 있을까요? 대표적인 예만 들어보자면

정수의 집합은 무한한 집합입니다.

이렇듯 사용자에 따라 여러 가지 종류의 집합을 만들 수 있습니다. X, Y라는 집합이 있을 때, X의 모든 원소가 Y에 포함된다면 X는 Y의 부분집합(subset)이며 기호로는 아래처럼 나타낼 수 있습니다.

또한 X가 Y의 부분집합일 때 X≠Y이면 X는 Y의 진부분집합(proper subset)라고 하며 기호로는 다음과 같습니다.

여기서 중요한 점은, 대부분 교육과정에서는 부분집합과 진부분집합의 표기를 혼용해서 사용하는 것입니다. 사실 중요한 부분은 아니므로 그냥 넘어가도 좋습니다. 만약 교수님께서 구분해서 사용하신다면 그렇게 쓰고, 아니면 아닌 대로 쓰면 됩니다..하하

예를 들어 아래와 같은 집합 A,B가 있으면 A는 B의 부분집합으로 볼 수 있습니다.

생소한 집합인 멱집합(Power Set)와 기수(Cardinality)라는 것을 알아보겠습니다.

멱집합은 집합 X의 모든 부분 집합의 집합입니다.

직관적으로 알 수 있도록 식으로 보면 아래와 같습니다.

기수(Cardinality)는 집합 안의 원소의 수를 뜻합니다. 기호로는 절댓값처럼(A의 기수 = |A|) 쓰면 됩니다.

집합 A에는 a,b의 두 가지 원소만 있으므로

여기서 멱집합과 기수간의 관계를 알아보겠습니다. 

A = {a, b} 이고 P(A) = {∅, {a}, {b}, {a,b}}이므로 |P(A)| = 4 

즉, 집합 A의 원소가 n개일 때 멱집합A의 기수는

집합 안에는 또 다른 집합이 있는 경우도 있습니다. 그런 경우를 벤다이어그램으로 나타내면 아래와 같고, 이러한 모음을 Pairwise Disjoint라고 합니다.

Partition이라는 것은 X가 nonempty subsets S의 모음일 때, X안의 모든 원소들이 S의 한 멤버 안에만 속해 있다면 S는 X의 partition이라고 합니다. 즉, S가 X의 partition이면 S는 pairwise disjoint하다고 볼 수 있습니다.

글로만 보면 확 와닿지 않는데, 예시를 보면 쉽게 이해할 수 있습니다.

마지막으로 Cartesian Product(데카르트 곱)에 대해서 알아보겠습니다. 데카르트 곱은 기호로 X x Y이며 정의는

x ∈ X and y ∈ Y 인 모든 순서쌍 (x,y)들의 집합이다. 데카르트 곱의 예시를 보고 이해해보겠습니다.

지금까지 집합에 대한 내용을 알아봤습니다. 사실 집합은 중학생 때부터 배운 것들이라서 이해하는데 큰 어려움이 없습니다. 그러나 생소한 용어와 영어로 나오니까 몰랐던 부분은 체크하는 게 좋습니다. 다음장에서는 명제를 알아보겠습니다.