[이산수학] 집합의 연산

벤 다이어그램 (Venn Diagram)

벤 다이어그램 (Venn Diagram) 주어진 집합들 사이의 관계와 집합의 연산에 대하여 이해하기 쉽게 전체 집합 $U$를 사각형으로 표현하고 안에 원으로 표현한 방식

 

합집합

합집합 (Union): 임의의 두 집합 $A$, $B$에 대하여 집합 $A$ 또는 집합 $B$에 속하는 모든 원소들의 집합

$$ A \cup B = \{x \space | \space x \in A \space or \space x \in B\} $$

 

교집합

교집합 (Intersection): 임의의 두 집합 $A$, $B$에 대하여 집합 $A$에도 속하고 집합 $B$에도 속하는 모든 원소들의 집합

$$ A \cap B = \{x \space | \space x \in A \space and \space x \in B\} $$

 

여집합

여집합 (Complement): 임의의 집합 $A$에 대하여 $U$ 안에 있는 모든 원소 중 $A$에 속하지 않은 원소들의 집합

$$ A^c = \{ x \in U \space | \space x \notin A \} $$

 

차집합

차집합 (Difference): 임의의 두 집합 $A, B$에 대하여 집합 $A$에는 속하지만 집합 $B$에는 속하지 않는 모든 원소들의 집합

$$ A - B = \{x \space | \space x \in A \space and \space x \notin B \} $$

 

대칭차집합

대칭차집합 (Symmetric difference): 임의의 두 집합 $A, B$에 대하여 합집합의 원소 중에서 교집합에 속하지 않는 모든 원소들의 집합

$$ A \oplus B = \{x \space | \space x \in A \cup B \space and \space x \notin A \cap B\} $$

 

곱집합

곱집합 (Cartesian Product): $a_1 \in A_1$이면서 $a_2 \in A_2$인 모든 순서쌍 ($a_1, a_2$)의 집합

$$ A_1 \times A_2 = \{(a_1, a_2) \space | \space a_1 \in A_1 \space and \space a_2 \in A_2\} $$

 

집합의 대수 법칙

법칙 이름	항등 관계
교환 법칙 (Commutative laws)	$A \cup B = B \cup A$ $A \cap B = B \cap A$
결합 법칙 (Associative laws)	$(A \cup B) \cup C = A \cup (B \cup C)$ $(A \cap B) \cap C = A \cap (B \cap C)$ $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
분배 법칙 (Distributive laws)	$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
항등 법칙 (Identity laws)	$A \cup \varnothing = A, A \cap \varnothing = \varnothing$ $A \cup U = U, A \cap U = A$
보 법칙 (Complement laws)	$A \cup A^c = U$ $A \cap A^c = \varnothing$
이중 보 법칙 (Double complement laws)	$(A^c)^c = A$
멱등 법칙 (Idempotent laws)	$A \cup A = A$ $A \cap A = A$
드 모르간 법칙 (De Morgan’s laws)	$(A \cup B)^c = A^c \cap B^c$ $(A \cap B)^c = A^c \cup B^c$
흡수 법칙 (Absorption laws)	$A \cup (A \cap B) = A$ $A \cap (A \cup B) = A$
전체 집합과 공집합의 보 법칙 (Complements of $U$ and $\varnothing$)	$U^c = \varnothing$ $\varnothing^c = U$
집합에서의 뺄셈 (Set Difference Law)	$A - B = A \cap B^c$