[이산수학] 집합의 표현 및 연산

집합의 표현

집합이란?

집합은 원소라 불리는 서로 다른 객체들의 모임으로, 어떤 객체가 그 집합에 속하는지 아닌지를 분명하게 구분할 수 있도록 정확하게 정의되어야 한다.

• 일반적으로 집합을 표시할 때는 영어 대문자(A-Z)으로 표시하고, 집합을 구성하는 원소는 영어 소문자(a-z)로 표시한다. 
• 집합에는 중복되는 원소가 없다.
• 집합 S에 하나의 원소 a가 속해 있다면 a∈S, 속해 있지 않다면 a∉S로 표기한다.

집합의 표현

집합을 표현하는 방법은 두가지가 있다.

1. 원소 나열법 : 집합의 원소들을 {} 사이에 하나씩 나열하는 방법이다. 
   • ex) S = {1, 2, 3, 4, 5}
   • 의미가 명확한 경우(ex. 연속되는 숫자)에는 모든 원소를 나열하는 대신에 …을 이용할 수 있다.
   • ex) S = {1, 2, … , 5}, S = {a, b, …, z}
2. 조건 제시법 : 집합의 원소들이 가지고 있는 특정한 성질을 기술하여 나타내는 방법이다.
   • S = {x | p(x)}, x : 원소를 대표하는 변수, p(x) : 원소들이 가지고 있는 성질
   • ex) 1부터 5까지의 자연수의 집합을 조건 제시법으로 표현해라 : S = {x | x는 자연수이고 1≤x≤5} 

💡자주 사용되는 전체 집합의 표기와 기호 ( 국제적으로 공인되어 사용되는 기호이다.)
Z : 정수의 집합
N : 자연수의 집합
R : 실수의 집합
Q : 유리수의 집합
P : 소수의 집합
C : 복소수의 집합
Sn = 1부터 n까지의 자연수 집합

카디날리티

집합 S 내에 있는 서로 다른 원소들의 개수를 S의 카디날리티(Cardinality) 또는 원소 수라고 하며 |S|로 표기한다.

• 유한 집합 : 집합 S의 카디날리티가 유한인 경우
• 무한 집합 : 집합 S의 카디날리티가 무한인 경우

부분집합과 진부분집합

• 부분 집합 : 집합 S의 원소로 만들 수 있는 모든 경우의 수의 집합
  • 두 집합 A, B에서 집합 A의 모든 원소가 집합 B의 원소에 속한다.
  • 집합 A는 집합 B에 포함된다.
  • A ⊆ B (부분집합이 아닌 경우에는 A ⊈ B)
• 진부분 집합 : 집합 S에 대한 부분집합 중 자기자신(집합 S)를 제외한 부분집합
  • A ⊆ B 이고, A≠B인 경우의 부분집합
  • A ⊂ B (진부분 집합이 아닌 경우에는 A⊄B)

💡집합 S의 원소 개수가 n개일 때,
- 부분 집합의 총 개수 : 2^n
- 진부분 집합의 총 개수 : 2^n-1

공집합, 여집합, 멱집합

• 전체 집합(U) : 집합론에서 관심을 두는 모든 원소의 집합
• 공집합(∅) : 어떠한 원소도 가지지 않는 집합
• 여집합 : 전체 집합 U에 속하나 집합 A에 속하지 않는 원소들의 집합

여집합

• 집합류 : 부분집합의 모임, 집합의 집합
• 멱집합(P(S), 2^s) : 집합 S의 모든 부분 집합을 원소로 가지는 집합
  • P(S) = {A | A ⊆ S}
  • | P(S) | = 2^|s|
  • 멱집합의 원소는 모두 집합이며 공집합을 제외한 모든 원소는 집합을 표시하는 중괄호({})안에 쓰여진다.

💡멱집합 P(A)의 원소들은 A 밑에 첨자(index)를 붙여 표기한다. 이러한 집합류에서 그들의 합집합과 교집합 연산은 다음과 같이 표기한다.

집합의 연산

합집합(Union) : A∪B

• 집합 A 또는 집합 B에 속하는 모든 원소의 집합
• A∪B = { x | x ∈ A ∨ x ∈ B}

A∪B

교집합(Intersection) : A∩B

• 집합 A에도 속하고 집합 B에도 속하는 모든 원소의 집합
• A∩B = { x | x ∈ A ∧ x ∈ B }
• 만약 A∩B이 공집합인 경우, 두 집합 A, B를 서로소라고 한다.

A∩B

차집합(Difference) : A-B

• 집합 A에 속하고 집합 B에는 속하지 않는 모든 원소의 집합
• A-B = { x | x ∈ A ∧ x ∉ B}

A-B

대칭 차집합(Symmetric dirrerence) : A ⊕ B

• A∪B의 원소 중에서 A∩B에 속하지 않는 모든 원수들의 집합
• A ⊕ B = { x | x ∈ A∪B ∧ x ∉ A∩B}
• = { x| x ∈ A -B ∨ x ∈ B-A}
• = { x | ( x ∈ A ∧ x ∉ B ) ∨ ( x ∉  A ∧ x ∈ B)}
• = { x | x ∈(( A∪B )-( A∩B )))}

A ⊕ B

곱집합(Cartesian product) : A x B

💡순서쌍
 순서로 구분되는 원소들의 쌍으로서 (a, b)와 같이 나타낸다. 순서쌍은 쌍의 원소들 간의 순서에 의해 구분된다.

(a,b) 에 대하여 a≠b이면 (a,b) ≠(b,a)
(a,b)=(c,d)이면, a=c, b=d

• 곱집합은 x ∈ A 이고 y ∈ B인 모든 순서쌍(x, y)의 집합을 말한다.
• A x B = {(x,y) | x ∈ A, y ∈ B }

집합 연산의 카디날리티

집합 A, B, C가 유한 집합일 때 다음 식들이 성립한다.

• | A∪B | = |A| + |B| - | A∩B |
• | A∩B | = |A| + |B| - | A∪B |
• | A∪B∪C | = |A| + |B| + |C| - | A∩B |  - | B∩C | - |A∩C| + | A∩B∩C |
• |A-B| = | A∩B^c | = |A| - | A∩B |
• |A x B| = |A| · |B|

집합의 대수 법칙

집합 U를 전체 집합이라고 할 때 집합의 연산에 대한 법칙.

쌍대

명제 안에 있는 교집합과 합집합을 전체 집합에 대한 여집합으로 바꾸어서 만든 새로운 명제를 원래의 명제의 쌍대라고 한다.

집합의 분할

공집합이 아닌 임의의 집합 S의 분할(Partition)을 π로 표기한다.

π = {A1, A2, A3, … Ai, … Ak}

• i = 1, …, k에 대하여 Ai는 공집합이 아닌 집합 S의 부분 집합이다.
• S = A1 ∪ A2 ∪ A3 …∪ Ak
• Ai들 사이에서는 서로소이다. 즉, i ≠ j이면, Ai ∩ Aj = ∅이다.
• 분할의 원소인 Ai를 분할의 블럭이라도 한다.

집합 S의 분할