[이산 수학] 집합의 대수 법칙

집합의 대수 법칙

• 수에 대한 사칙 연산에도 일정한 규칙이 있듯이, 집합 연산에도 일정한 규칙이 있다.
• 이를 집합의 대수 법칙이라고 하는데, 대수 법칙을 이용하면 복잡한 집합 연산을 간단히 할 수 있다.

 

집합의 대수 법칙

집합 연산		법칙
$A ∪ \varnothing = A$	$A ∩ U = A$	항등 법칙(Identity Law)
$A ∪ U = U$	$A ∩ \varnothing = \varnothing$	지배 법칙(Domination Law)
$A ∪ A = A$	$A ∩ A = A$	멱등 법칙(Idempotent Law)
$A ∪ B = B ∪ A$	$A ∩ B = B ∩ A$	교환 법칙(Commutative Law)
$A ∪ (B ∪ C) = (A ∪ B) ∪ C$ $A ∩ (B ∩ C) = (A ∩ B) ∩ C$		결합 법칙(Associative Law)
$A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)$ $A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)$ $A × (B ∩ C) = (A × B) ∩ (A × C)$ $A × (B ∪ C) = (A × B) ∪ (A × C)$ $A × (B - C) = (A × B) - (A × C)$		분배 법칙(Distributive Law)
$\overline{ \overline{A} } = A$		이중 보 법칙(Double Complement Law)
$A ∪ \overline{A} = U$ $\overline{\varnothing} = U$	$A ∩ \overline{A} = \varnothing$ $\overline{U} = \varnothing$	보 법칙(Complement Law)
$\overline{A ∪ B} = \overline{A} ∩ \overline{B}$	$\overline{A ∩ B} = \overline{A} ∪ \overline{B}$	드 므로간의 법칙(De Morgan's Law)
$A ∪ (A ∩ B) = A$	$A ∩ (A ∪ B) = A$	흡수 법칙(Absorption Law)

• 집합의 대수 법칙에서도 괄호 안의 집합 연산과 괄호 밖의 집합 연산이 같은 경우는 결합 법칙을 적용하고, 서로 다른 경우는 분배 법칙을 적용한다.
  • 결합 법칙을 적용해야 하는 경우 : $A ∪ (B ∪ C)$
  • 분배 법칙을 적용해야 하는 경우 : $A ∪ (B ∩ C)$

 

$A × (B ∩ C) = (A × B) ∩ (A × C)$ 증명하기

$(x, y) ∈ A × (B ∩ C)$
$\Leftrightarrow x ∈ A \land y ∈ (B ∩ C)$    (∵ 곱집합의 정의)
$\Leftrightarrow x ∈ A \land (y ∈ B \land y ∈ C)$    (∵ 교집합의 정의)
$\Leftrightarrow (x ∈ A \land y ∈ B) \land (x ∈ A \land y ∈ C)$    (∵ 논리 연산의 분배 법칙*)
$\Leftrightarrow [(x, y) ∈ A × B] \land [(x, y) ∈ A × C]$    (∵ 곱집합의 정의)
$\Leftrightarrow (x, y) ∈ (A × B) ∩ (A × C)$    (∵ 교집합의 정의)

*괄호 안과 밖의 논리 연산자가 and($\land$) 연산자로 같으나, 집합에 포함되는 원소의 기호가 $x, y$ 로 다르기 때문에 분배 법칙으로 연산해야 한다.

 

기호 $\Rightarrow$ 와 $\Leftrightarrow$ 의 의미

• $A \Rightarrow B$ : `A` 가 참이면, `B` 는 항상 참이다.
• $A \Leftrightarrow B$ : $(A \Rightarrow B) \land (B \Rightarrow A)$ 는 항상 참이다.