신흥철 교수의 이산 수학 5, 6 강: 집합, 집합의 연산

 3장 집합 

1. 집합의 개념

• 집합(Set) 영문 대문자 (A, B, C, ...)
  • 명확한 기준에 의해(1) 분류되어 공통된 성질(2)을 가지며, 중복되지 않는(3) 원소(element, member)의 모임
• 표기 방법
  • 원소나열법: 집합에 포함되는 원소를 일일이 나열
    - A = {1, 2, 3, 4, 5, 6, 7} = {1, 2, 3,... , 7}
  • 조건 제시법: 원소의 공통 성질을 조건식으로 제시
    - A = {x|0<x<=7, x∈N}
    * N(자연수) ⊂ Z(정수) ⊂ Q(유리수), I(무리수), R(실수=QUI) ⊂ C(복소수 - 실수와 허수의 합집합)
• 집합과 원소의 포함관계
  • a가 집합 A의 원소이다 : a ∈ A
  • a가 집합 A의 원소가 아니다. : a ∉ A
• 기수(Cardinality) |A|
  • 집합 A가 포함하는 원소의 수
  • (예제)
    A={x|-4≤x≤4, x∈Z}  |A|=9
    B={y|-3≤y≤3, y∈Q}  |B|=∞
    C={z|z 3=2, z∈Z}      |C|=0
• 유한집합(Finite Set) / 무한집합(Infinite Set)
  • 유한집합: 포함되는 원소의 수가 유한한 집합
  • 무한집합: 포함되는 원소의 수가 무한한 집합
• 상등(Equal) A=B
  • 두 집합 A, B에 속하는 원소가 동일할 때 "두 집합 A와 B가 서로 같다(상등이다)." 
  • A=B ⇔ (a∈A∧a∈B) "a의 모든 원소는 b의 모든 원소이다."
  • (예제) 
    다음 중 상등인 집합끼리 짝지으시오.
    A={a|-3 < a <= 3, a ∈ Z} B = {1, 2, 4, 8,...} C = {c|c=2**k, k>= 0, k ∈ Z} D = {d|d ∈R}
    E = {-2. -1. 0, 1, 2, 3} F = {e|e는 유리수거나 무리수}
    
    A, C의 조건제시법을 원소나열법으로 표기하면, A={-2, -1, 0, 1, 2, 3} C={1, 2, 4, 8, …} ∴ A=E, B=C, D=F

---

2. 집합의 종류

• 전체집합(Universal Set) U
  • 논의 대상이 되는 원소 전체를 포함하는 집합
• 공집합 (Empty Set) Ø 또는 { }
  • 하나의 원소도 포함하지 않는 집합, |Ø|=0
• 부분집합(Subset) A⊆B
  
  • 집합 A의 모든 원소가 집합 B에 포함됨 |A|≤|B|
• 진부분집합(Proper Subset) A⊂B
  • 집합 A의 모든 원소가 집합 B에 포함되지만 집합 A와 집합 B가 상등이 아님. |A|<|B|
• 집합간 포함관계 정리 (1)
  • 모든 집합 A에 대해 A ⊆ A
    • 집합 A에 속하는 모든 원소 a에 대해 a ∈ A (a ∈ A -> a ∈ A)
  • 모든 집합 A에 대해 Ø⊆A
    • (함축명제 a∈Ø→a∈A이 참임을 이용)
      공집합에는 원소가 없으므로 a∈Ø는 거짓
      조건이 거짓이므로 a∈Ø→a∈A는 항상 참
      ∴ Ø⊆A는 참
      (※ 부분집합: a∈A→a∈B가 참이면 A⊆B)
  • 집합 간 포함관계 정리 (2)
    • 모든 집합 A에 대해 A ⊆ U
      • 집합 U는 전체집합이므로 논의 대상의 모든 원소를 포함, 즉, 모든 합 A에 대해
        a ∈ A -> a ∈ U ∴ A⊆U
    • 집합 A, B, C에 대해 A ⊆ B고 B ⊆ C면, A ⊆ C
      
      • 논리의 동치 법칙 중 가설적 삼단 논리와 같다.
        • A ⊆ B : x ∈ A -> x ∈ B
        • B ⊆ C : x ∈ B -> x ∈ C
        • <=> x ∈ A -> x ∈ C (A ⊆ C)
    • 집합 간 포함관계 정리 (3)
      • 집합 A, B에 대해 A = B <=> (A ⊆ B) ^ (B ⊆ A))
      • (a ∈ A ^ a ∈ B) <=>  (a ∈ A -> a ∈ B) ^ (a ∈ B -> a ∈ A) 
      • (a ∈ A ^ a ∈ B) <=> ((a ∈ A) <=> (a ∈ B))
      • (a ∈ A ^ a ∈ B) <=> ((a ∈ A) ^ (a ∈ B))
    • (예제) 집합 A와 B, 집합 B와 C, 집합 B와 E, 집합 C와 E, 집합 C와 D 간의 포함관계는?
      A={a}, B={a, b, w, x, y}, C={x, y}, D={w, x}, E={a, b, w, x, y, z}
      
      A⊂B, C⊂B, B⊂E, C⊂E (A⊂E), C⊄D 또는 C⊅D 또는 C⊈D 또는 C⊉D
    • (예제) 집합 A={{a, b}, c, {d}}일 때
      
      {a, b}∈A, c∈A, {{d}}⊂A, {{a, b}, c, {d}}=A
  •  

---

3. 집합의 연산

• 합집합(Union) A∪B
  • 집합 A, B에 대하여, A와 B에 모두 속하거나 두 집합 중 한 집합에 속하는 원소들로 구성된 집합
  • A∪B={x|x∈A∨x∈B}
  • (예제) 다음 집합 A, B, C의 합집합(A∪B∪C)은?
    A={a, b, c, d}, B={d, e, f, g, h}, C={c, d, e}
    
    A∪B∪C={a, b, c, d, e, f, g, h}
• 교집합(Intersection) A∩B
  • 집합 A, B에 대하여, A와 B에 모두 속하는 원소들로 구성된 집합
  • A∩B={x|x∈A∧x∈B}
  • (예제) 다음 집합 A, B, C의 교집합(A∩B∩C)은?
    A={a, b, c, d}, B={d, e, f, g, h}, C={c, d, e}
    
    A∩B∩C={d}
• 서로소(Disjoint)
  • 집합 A, B에 대하여, A와 B 모두에 공통으로 속하는 원소가 하나도 없는 경우
  • A∩B=Ø
• 합집합과 교집합의 기수(1)
  • |A∪B| = |A| + |B| - |A∩B|
  • |A∩B| = |A| + |B| - |A∪B|
  • |A∩B| = 0(서로소)인 경우, |A∪B| = |A| + |B|
• 합집합과 교집합의 기수(2)
  • |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C|
  • (예제) 집합 A={a, b, c, d, e, f, g}, B={e, f, g, h, i, j, k, l}, C={k, l, m, n}일 때 다음을 구하시오.
    |A∪B|, |A∩C|, |A∪B∪C|
    
    |A∪B| = |A|+|B|-|A∩B|=7+8-3 = 12
    |A∩C| = 0
    |A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C| = 7+8+4-3-2-0+0 =14
• 차집합(Difference) A-B
  • 집합 A, B에 대하여, A에는 속하지만 B에는 속하지 않는 원소들로 구성된 집합
  • A-B={x|x∈A∧x ∉B} (A의 원소 중에서 B에 속하는 요소들을 뺀 부분)
• 대칭차집합(Symmetric Difference) A⊕B (논리 단원에서도 나온 배타적 논리합의 기호와 같다)
  • 집합 A, B에 대하여, A-B에 속하거나 B-A에 속하는 원소들로 구성된 집합
    A⊕B={x|x∈A∧x ∉B} ∨{x|x ∉A∧x∈B} (A에만 속하거나 B에만 속하는 원소들)
            ={x|(x∈A-B) ∨(x∈B-A)}
  • (예제) A⊕B는?
    A={a,b,c,d,e,f,g,h,i,j}, B={g,h,i,j,k,l,m,n}
    
    A⊕B={a, b, c, d, e, f, k, l, m, n}
• 여집합 또는 보집합(Complement) Ā 또는 A'
  • 전체집합 U에는 속하지만 집합 A에는 속하지 않는 원소들로 구성된 집합
  • Ā=A'={x|x∈U∧x ∉A} =U-A
  • (예제) 여집합은?
    X={x|-33≤x<72, x∈R} Y={y|y∈R}
    
    X'={x<-33 ∨ x≥72, x∈R} Y'={y|y∈C-R}
• 곱집합(Cartesian Product) A×B
  • 집합 A, B에 대하여, a∈A, b∈B일 때 순서쌍 (a, b)의 집합
  • A×B={(a, b)|a∈A∧b∈B} |A×B|=|A|·|B|
  • (예제) A={1, 2}, B={a, b, c}에 대하여 A×B와 B×A 및 각각의 기수를 구하시오.
    
    A×B={(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)}
    B×A={(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)} (둘의 순서가 뒤바껴있는 상태)
    |A×B|=|A|·|B|=2×3= 6 =3×2=|B|·|A|=|B×A| (둘의 크기가 같다)
    
    (*행렬을 곱하는 것과 같다.) 
• 멱집합(Power Set) P(A)
  • n개의 원소를 갖는 집합 A에 대하여, A의 모든 부분집합을 원소로 갖는 집합
  • P(A)={B|B⊆A} |P(A)|=2**n
  • (예제) A={1, 2, 3}, B={Ø, {Ø}}에 대하여 멱집합과 기수를 구하시오.
    
    P(A)={Ø,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
    P(B)={Ø, {Ø}, {{Ø}}, {Ø,{Ø}}}
    |P(A)|=2**3=8, |P(B)|=2**2=