[이산 수학] 집합의 연산

집합의 연산

• 집합과 집합의 연산을 통해 새로운 집합을 구할 수 있다.

 

합집합과 교집합

합집합(Union : $A ∪ B$ )

집합 `A` 와 `B` 에 모두 속하거나 둘 중 한 집합에만 속하는 원소들로 이루어진 집합
$$A ∪ B = \{ x \; | \; x ∈ A \lor x ∈ B \}$$

• 합집합은 두 집합에 포함된 원소들을 모두 합쳐서 새로운 집합을 만드는 연산으로, 두 집합에 공통으로 존재하는 원소는 한 번만 작성한다.
• 예) $A = \{1, 2, 3, 4, 5 \}, \; B = \{4, 5, 6, 7 \}$ 일 때, $A ∪ B = \{ 1, 2, 3, 4, 5, 6, 7 \}$

 

교집합(Intersection: $A ∩ B$ )

집합 `A` 와 `B` 에 모두에 속하는 원소들로 이루어진 집합
$$A ∩ B = \{ x \; | \; x ∈ A \land x ∈ B \}$$

• 교집합은 두 집합에 공통으로 포함되는 원소들만으로 새로운 집합을 만드는 연산이다.
• 예) $A = \{1, 2, 3, 4, 5 \}, \; B = \{4, 5, 6, 7 \}$ 일 때, $A ∩ B = \{ 4, 5 \}$

 

서로소(Disjoint)

집합 `A` 와 `B` 에 공통으로 포함되는 원소가 하나도 없는 경우
$$A ∩ B = \varnothing$$

• 예) $A = \{1, 2, 3, 4, 5 \}, \; B = \{ 6, 7 \}$ 일 때, $A ∩ B = \varnothing$
• '두 집합 `A` 와 `B` 의 교집합은 공집합이다.' 라는 말과 '두 집합 `A` 와 `B` 는 서로소이다.' 라는 말은 같은 의미이다.

 

합집합과 교집합의 기수

집합 $A, B, C$ 의 기수에 대하여 다음이 성립한다.

① $|A ∪ B| = |A| + |B| - |A ∩ B|$
② $|A ∩ B| = |A| + |B| - |A ∪ B|$
③ $A ∩ B = \varnothing$ 인 경우, $|A ∪ B| = |A| + |B|$
④ $|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|$
⑤ $|A ∩ B ∩ C| = |A| + |B| + |C| - |A ∪ B| - |A ∪ C| - |B ∪ C| + |A ∪ B ∪ C|$

 

증명

• 다음의 벤 다이어그램을 이용하여 합집합과 교집합의 기수 규칙을 증명할 수 있다.

(i) $|A| = ① + ②$
(ii) $|B| = ① + ③$
(iii) $|A ∪ B| = ① + ② + ③$
(iv) $|A ∩ B| = ①$

 

차집합과 대칭 차집합

차집합(Difference : $A - B$ )

집합 `A` 에는 포함되지만, 집합 `B` 에는 포함되지 않는 원소들의 집합
$$A - B = \{ x \; | \; x ∈ A \land x \not ∈ B \}$$

• 사칙 연산의 뺄셈처럼 집합에서 어느 한 집합에만 속하는 원소를 구하는 연산을 차집합이라고 한다.
• 차집합은 교집합, 합집합과는 달리 교환 법칙이 성립하지 않는다.
  • $A -B$ 와 $B - A$ 는 전혀 다른 원소로 구성된 집합이다.
• 예) $A = \{1, 2, 3, 4, 5 \}, \; B = \{ 6, 7 \}$ 일 때,
  • $A - B = \{ 1, 2, 3 \}$
  • $B - A = \{ 6, 7 \}$
  • $A - B$ 와 $B - A$ 는 전혀 다른 원소로 구성되어 있음을 확인할 수 있으며, 교환 법칙이 성립하지 않음을 확인할 수 있다.

 

대칭 차집합(Symmetric Difference : $A \oplus B$ )

집합 `A` 에만 포함되거나 집합 `B` 에만 포함되는 원소들의 집합
$$A \oplus B = \{ x \; | \; x ∈ (A - B) \lor x ∈ (B - A) \}$$

• 대칭 차집합에 대한 조건 제시법 내용을 다음과 같이 정리하면, 집합 $A, B$ 의 합집합에서 교집합을 제외하면 대칭 차집합임을 알 수 있다.

$A \oplus B$
$= \{ x | x ∈ (A - B) \lor x ∈ (B - A) \}$
$= \{ x | (x ∈ A \land x \not∈ B) \lor (x \not ∈ A \land x ∈ B) \}$    (∵ 차집합의 정의)
$= \{ x | (x ∈ A \lor x \not∈ A) \land (x ∈ A \lor x ∈ B) \} \land (x \not ∈ A \lor x \not ∈ B) \land (x \not ∈ B \lor x ∈ B)$    (∵ 분배 법칙)
$=\{ U \land (x ∈ A \lor x ∈ B) \land (x \not ∈ A \lor x \not ∈ B) \land U \}$    (∵ 전체 집합의 정의)
$= \{ x | (x ∈ A \lor x ∈ B) \land \neg [x ∈ A \land x ∈ B) \}$    (∵ 드 므로간의 법칙)
$= \{ x | x ∈ (A ∪ B) \land \neg [x ∈ (A ∩ B)] \}$    (∵ 합집합과 교집합의 정의)
$= \{ x | x ∈ (A ∪ B) \land x \not ∈ (A ∩ B) \}$    (∵ 부정 법칙)
$= \{ x | x ∈ [(A ∪ B) - (A ∩ B)] \}$    (∵ 차집합의 정의)

 

그 외 집합의 연산

여집합(Complement Set: $\overline{A}$ 또는 $A'$ ) / 보집합

전체 집합 `U` 에는 포함되지만, 집합 `A` 에는 포함되지 않는 원소들로 구성된 집합
$$\overline{A} = A' = \{ x \; | \; x ∈ U \land x \not ∈ A \} = U - A \\ |\overline{A}| = |U| - |A|$$

• 전체 집합의 범위에 포함되는 원소 중, 특정 집합에 포함되지 않는 나머지 원소도 집합으로 구성할 수 있는데, 이를 여집합이라고 한다.

 

곱집합(Product Set : $A × B$ )

집합 `A, B` 에 대하여 $a ∈ A, \; b ∈ B$ 일 때, 순서쌍 $(a, b)$ 의 집합
$$A × B = \{(a, b) \; | \; a ∈ A \land b ∈ B \} \\ |A × B| = |A| × |B|$$

• 순서쌍은 원소의 나열에 따라 달라진다.
  • 순서쌍 $(a, b)$ 와 순서쌍 $(b, a)$ 는 전혀 다른 원소로 취급한다.
• 곱집합은 차집합과 마찬가지로 교환 법칙이 성립하지 않는다.
  • 집합 $A, B$ 에 대하여 $a ∈ A, \; b ∈ B$ 일 때 곱집합 $A × B$ 로 만들어지는 순서쌍은 집합 `A` 의 원소인 `a` 가 순서쌍의 앞에 오고, 집합 `B` 의 원소인 `b` 가 순서쌍의 뒤에 와서 `(a, b)` 로 만들어진다.
  • 그러나 곱집합 $B × A$ 에 의해 만들어지는 순서쌍은 $(b, a)$ 로, $(a, b)$ 와는 전혀 다른 순서쌍이다.
• 하지만 기수의 경우, 집합 `A` 의 기수와 집합 `B` 의 기수의 곱으로 구하기 떄문에 $|A × B|$ 와 $|B × A|$ 가 항상 같다.
• 예) $A = \{ 1, 2 \}, \quad B = \{ a, b, c \}$
  • $A × B$ 는 집합 `A` 의 원소가 앞에 오고, 집합 `B` 의 원소가 뒤에 오는 순서쌍으로 구성되며, 각 집합의 원소가 서로 순서쌍으로 만들어져야 한다.
    • $A × B = \{(1, a), (1, b), (1, c), (2, a), (2, b), (2, c) \}$
  • $B × A$ 는 집합 `B` 의 원소가 앞에 오고, 집합 `A` 의 원소가 뒤에 오는 순서쌍으로 구성된다.
    • $B × A = \{ (a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2) \}$
  • 두 곱집합의 기수는 집합 `A, B` 의 기수를 이용해 구할 수 있다.
    • $|A × B| = |B × A| = |A| × |B| = 2 × 3 = 6$

 

멱집합(Power Set : $P(A)$ )

원소가 `n` 개인 집합 `A` 에 대하여, 가능한 모든 부분 집합을 원소로 갖는 집합
$$P(A) = \{ B \; | \; B ⊆ A \} \\ |P(A)| = 2^{m}$$

• 모든 집합은 부분 집합을 가질 수 있다.
  • 공집합($\varnothing$)과 집합 자기 자신은 해당 집합의 부분 집합이 된다.
  • 그 외에도 다양한 형태의 부분 집합을 만들 수 있는데, 공집합($\varnothing$)과 집합 자신을 포함하여 하나의 집합에서 만들 수 있는 모든 부분 집합을 원소로 갖는 집합을 멱집합이라고 한다.
• 예) $A = \{ 1, 2, 3\}$
  • 공집합 $\varnothing$ 과 집합 $A$ 자체인 $\{ 1, 2, 3\}$ 은 집합 $A$ 의 부분 집합이다.
  • 그 외에도 집합 $A$ 의 원소인 $1, 2, 3$ 으로 만들 수 있는 집합들이 집합 $A$ 의 멱집합의 원소가 된다.
  • 그러므로 집합 $A$ 의 멱집합 $P(A)$ 는 다음과 같다.
    • $P(A) = \{ \varnothing, \{1 \}, \{2 \}, \{3 \}, \{1, 2 \}, \{1, 3 \}, \{2, 3 \}, \{1, 2, 3 \} \}$
  • 또한 집합 $A$ 의 멱집합 $P(A)$ 의 기수는 집합 $A$ 의 기수($|A| = 3$)를 이용해 구할 수 있으므로, 다음과 같다.
    • $|P(A)| = 2^{3} = 8$