2.5 Operations on sets | 집합의 연산

Unary / Binary Operations #

Unary Operation #

이는 단항 연산자로, 말 그대로 연산에 대해 필요로 하는 항이 하나라는 의미입니다.

• Power Set of Sets

  • 집합 A의 모든 subsets 집합
    • $\mathcal{P}(A)=\{X|X\subseteq A\}$라고 나타낸다.
    • 이를 해석해보면 $\mathcal{P}(A)$는 집합 A의 모든 subset을 원소로 하는 집합이다.
    • $\mathcal{P}(A)$의 cardinality를 구하는 식을 나타내면 $|\mathcal{P}(A)|$로 쓸 수 있고

      • $\mathcal{P}(A)=2^{|A|}$이다.

        • 위 식이 성립하는 이유는 경우의 수로 나타낼 수 있다.
        • 어떤 집합의 power set을 구하는 경우의 집합을 예로 들어보면 집합 $A=\{1,2\}$이라고 할 때, $|\mathcal{P}(A)|$는 $A=\{\{\empty\}, \{1\},\{2\},\{1,2\}\}$가 됩니다.

        $A=\{1,2\}$에 대해 각 원소는 power set에 포함 될 수 있고 안될 수 있기 때문에 원소 1에 대해 2가지의 경우가 발생합니다. 2에 대해서도 2가지의 경우가 발생합니다.

        집합에서 포함 되거나 되지 않거나만 따지기 때문에 $2^{|A|}$가 성립합니다.

• Complement of sets

  어떤 집합 A에 대해 A에 포함되지 않은 원소들을 모은 집합을 $A^c$ | A의 complement라고 한다.

  이를 수학 기호로 나타내면 $A=\{x|x \notin A\}$

Binary Operation #

이는 이항 연산자라는 의미로 연산에 대해 필요로 하는 항이 이항이라는 의미이다.

• Intersection of Sets and Union of Sets

  • Intersection of Sets
    • 집합 A, B에 모두 포함되는 원소들을 모은 집합을 A와 B의 intersection(교집합)이라고 할 수 있다.
    • 기호로는 $A \cap B = \{x|(x\in A) \wedge (x\in B)\}$로 표현 할 수 있다.
  • Union of Sets
    • 집합 A 또는 B에 포함되는 원소들을 모은 집합을 A, B의 union(합집합)이라고 할 수 있다.
    • 기호로는 $A\cup B=\{x|(x\in A) \vee (x \in B) \}$로 표현 할 수 있다.
    • $|A \cup B|$를 구하는 방법
      • $|A\cup B| = |A|+|B|-|A \cap B|$
    • Special cases
      • 집합 A가 B의 부분집합일 경우 두 집합의 관계는 아래와 같다.
        • $A \subseteq B \longleftrightarrow A \cup B = B, A\cap B = A$
  • General Intersections

    • $\bigcap_{i=1}^{n}A_{i}=A_1\cap A_2 \cap \dots \cap A_n$

    • $\bigcup_{i=1}^{n}A_i=A_1\cup A_2\cup\dots\cup A_n$

• The Algebraic Properties

  • Commutative Law
    • $A\cup B = B \cup A$
    • $A \cap B = B \cap A$
  • Associative Law
    • $A\cup (B \cup C) = (A\cup B) \cup C$
    • $A\cap (B\cap C) = (A\cap B)\cap C$
  • Distribute Law
    • $A\cup(B\cap C) = (A\cup B) \cap (A\cup C)$
  • Identities
    • $A \cup \emptyset = A$
    • $A\cup \emptyset=\empty$
    • $A\cup U = U$
    • $A\cap U = A$
    • $A\cup A^c=U$
    • $A\cap A^c=\empty$
    • $(A^c)^c=A$
  • De Morgan’s Law
    • $(A\cap B)^c=A^c\cup B^c$
    • $(A\cup B)^c=A^c\cap B^c$