[이산수학] 집합론 : 표시법, (진)부분집합, 서로소, 분할, 멱집합, 연산(합,교,차,여,곱), 대수법칙

본 게시글은 대학 전공수업을 들으며 노션에 정리한 내용을 블로그로 옮긴 것으로, 노션 웹을 통해 최적화된 형태로 읽으시길 권장드립니다.(➡️ 노션 링크)

4강 - 집합론

학습 목표

• 집합과 원소를 구별할 수 있고 원소나열법과 조건제시법으로 집합을 표현할 수 있다.
• 집합의 분할과 멱집합을 구할 수 있다.
• 합집합, 교집합, 차집합, 여집합, 대칭차집합과 같은 집합의 기본연산을 수행할 수 있다.
• 집합의 다양한 대수법칙의 원리를 이해하고 필요에 따라 활용할 수 있다.

기본 용어

논리학과 집합론

• 𝒑(𝒙) ∨ 𝒈(𝒙) = 𝑨 ∪ 𝑩

• 𝒑(𝒙) ∧ 𝒈(𝒙) = 𝑨 ∩ 𝑩

집합과 원소

💡 A set is a collection of objects, which are called elements

: 집합이란 원소들의 모음이다.

무정의 용어

• 집합(set)과 원소(element)는 정의 없이 사용하는 용어
• 집합의 구성원이 원소, 집합은 그 원소를 포함.(중복x)
• ****직관적으로 이해할 수 있으나 다른 용어로 정의하기 힘든 대상을 표현하기 위해 사용됨

집합론의 창시자 Georg Cantor : “우리의 직관이나 사고로부터 한정적이고 분리된 객체들의 전체 M에서의 수집”

집합의 표시법

𝒂 ∈ 𝑺, 𝒃 ∉ 𝑺

‘S가 하나의 집합, a를 S의 원소라고 하고 / b를 S의 원소가 아니라고 한다’

원소나열법

S = {1, 2, 3}

조건나열법

****S = { 𝒙｜𝟎 < 𝒙 < 𝟒 인 자연수}

부분집합(subset)

A의 모든 원소가 B의 원소이면 ‘A는 B의 부분집합’이라고 하고,

𝑨 ⊆ 𝑩 또는 𝐀 ⊂ 𝑩로 표기한다.

즉, 𝑨 ⊆ 𝑩 ⇔ ∀𝒙 ( 𝒙 ∈ 𝑨 → 𝒙 ∈ 𝑩 ) : 모든 x에 대해서, x가 A에 속해있다면, x는 B에도 속한다.

진부분집합(proper subset)

“𝑨는 𝑩의 진부분집합이다”

⇔ 𝑨 ⊆ 𝑩, 𝑩 ⊆/ 𝑨 : A는 B의 부분집합이지만, B는 A의 부분집합이 아니다.
⇔ 𝑨 ⊆ 𝑩, 𝑨 ≠ 𝑩 : A는 B의 부분집합이며, A와 B는 같지않다.

본문의 설명과 달리, A가 더 큰 집합임에 유의.

상동(equal)

: 𝑨 = 𝑩 ⇔ 𝑨 ⊆ 𝑩 𝒂𝒏𝒅 𝑩 ⊆ 𝑨

A와 B가 같다 = A가 B의 부분집합이면서 B가 A의 부분집합이다.

서로소(disjoint)

교집합이 없다.(공집합)

즉, 집합 A와 B는 서로소(disjoint) ⟺ 𝑨 ∩ 𝑩 = ∅(공집합)

n개의 집합 𝑨𝟏, 𝑨𝟐, ⋯, 𝑨𝒏은 쌍으로 서로소(pairwise disjoint)

⇔ 𝑨𝒊 ∩ 𝑨𝒋 = ∅ ( 𝒊 ≠ 𝒋, 𝟏 ≤ 𝒊, 𝒋 ≤ 𝒏 )

분할(partition)

집합 A를 ∅이 아닌 부분집합들로 나눌 때,

A의 모든 원소들이 각각 나누어진 부분집합들 중 하나에만 포함될 경우

이 부분집합들 전체의 집합을 A의 분할이라고 함.

즉, 부분집합들은 공집합이 아님 + 쌍으로 서로소 + 모든 부분집합의 합집합 전체집합

https://supermemi.tistory.com/entry/집합-총-정리

 

멱집합

집합 A의 모든 부분집합들의 집합을 A의 멱집합이라고 하고,

P(A)로 표기한다.

• 예제 : 집합 S = {a, b, c}일 때, S의 멱집합 P(S)을 구하시오.

https://www.mathsisfun.com/sets/power-set.html

 

 

 

 

• 멱집합의 원소수 |P(S)| = 2^n이므로, 2^3 = 8
• ( The number of members of a set is often written as |S| )
• P(S) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

집합 연산

• 연산 : 입력으로 수를 받아들이고 출력으로 수를 내어줌
• 집합연산 : 입력으로 집합을 받아들이고 출력으로 집합을 내어줌

https://www.realdigital.org/doc/e127ebfa82dbc904b5c0dac5d1adce8e

합집합(union)

𝑨 ∪ 𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∨ 𝒙 ∈ 𝑩}

교집합(intersection)

𝑨 ∩ 𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∧ 𝒙 ∈ 𝑩}

차집합(difference)

𝑨 − 𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∧ 𝒙 ∉ 𝑩}

여집합(complement, 보집합)

𝑨𝒄 = 𝑼 − 𝑨 = {𝒙 ∈ 𝑼｜𝒙 ∉ 𝑨}

대칭차집합

𝑨⨁𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∪ 𝑩 ∧ 𝒙 ∉ 𝑨 ∩ 𝑩}

https://ko.wikipedia.org/wiki/ 대칭차집합

곱집합(Cartesian product)

https://ko.wikipedia.org/wiki

𝑼를 전체집합, 𝑨 ⊂ 𝑼, 𝑩 ⊂ 𝑼라 할 때,

𝑨의 원소 𝒂와 𝑩의 원소 𝒃로 만들어지는 순서쌍 (𝒂, 𝒃)들의 집합을

𝑨와 𝑩의 곱집합

𝑨 × 𝑩 ={ (𝒂, 𝒃) | 𝒂 ∈ 𝑨, 𝒃 ∈ 𝑩 }

집합의 대수법칙

크기에 관한 성질

합집합의 크기

|𝑨 ∪ 𝑩| = |𝑨| + |𝑩| − |𝑨 ∩ 𝑩|

합집합의 크기 = 각각 집합의 갯수 - 교집합 갯수

|𝑨 ∪ 𝑩 ∪ 𝑪|

= |𝑨| + |𝑩| + |𝑪| − |𝑨 ∩ 𝑩| − |𝑨 ∩ 𝑪| − |𝑩 ∩ 𝑪| + |𝑨 ∩ 𝑩 ∩ 𝑪|

포함관계 및 항등식

교집합, 합집합, 포함관계의 이행성

모든 집합 A, B, C에 대해서 다음을 만족한다.

• 교집합 : 교집합은 하나의 집합의 부분집합이다.(𝑨 ∩ 𝑩) ⊆ 𝑩
• (𝑨 ∩ 𝑩) ⊆ 𝑨
• 합집합 : 합집합은 부분집합을 가진다.𝑩 ⊆ (𝑨 ∪ 𝑩)
• 𝑨 ⊆ (𝑨 ∪ 𝑩)
• 이행성(Transitivity)만약 𝑨 ⊆ 𝑩이고 𝑩 ⊆ 𝑪이면, 𝑨 ⊆ 𝑪이다.
• 만약 X → Y이고 Y → Z이면 X → Z이다

원소논증

집합 𝑿, 𝒀에 대해 𝑿 ⊆ 𝒀를 증명하고자 할 때

∀𝒙 ∈ 𝑿 → 𝒙 ∈ 𝒀 임을 보인다.

=> 모든 X의 원소는 Y의 원소임을 보이면, X는 Y의 부분집합이다.

집합의 항등식

*논리적으로 한번씩 생각해보고, 논리적 동치 법칙 과 비교해볼 것!

U : 전체집합, A,B,C ⊂ U 라 할 때,

• 교환법칙
  • 𝑨 ∪ 𝑩 = 𝑩 ∪ 𝑨 (b) 𝑨 ∩ 𝑩 = 𝑩 ∩ 𝑨
• 결합법칙
  • 𝑨 ∩ 𝑩 ∩ 𝑪 = 𝑨 ∩ (𝑩 ∩ 𝑪)
  • 𝑨 ∪ 𝑩 ∪ 𝑪 = 𝑨 ∪ 𝑩 ∪ 𝑪
• 분배법칙
  • 𝑨 ∩ (𝑩 ∪ 𝑪) = (𝑨 ∩ 𝑩) ∪ (𝑨 ∩ 𝑪)
  • 𝑨 ∪ (𝑩 ∩ 𝑪) = (𝑨 ∪ 𝑩) ∩ (𝑨 ∪ 𝑪)
• 항등법칙
  • 𝑨 ∩ 𝑼 = 𝑨
  • 𝑨 ∪ ∅ = 𝑨
• 보수법칙
  • 𝑨 ∪ 𝑨𝒄 = 𝑼 (b) 𝑨 ∩ 𝑨𝒄 = ∅
• 이중보수법칙
  • (𝑨𝒄)𝒄 = 𝑨
• 멱등법칙
  • 𝑨 ∪ 𝑨 = 𝑨 (b) 𝑨 ∩ 𝑨 = 𝑨
• 전체한계법칙
  • 𝑨 ∪ 𝑼 = 𝑼 (b) 𝑨 ∩ ∅ = ∅
• 드모르간의 법칙
  • (𝑨 ∩ 𝑩)𝒄= 𝑨𝒄 ∪ 𝑩𝒄
  • (𝑨 ∪ 𝑩)𝒄= 𝑨𝒄 ∩ 𝑩𝒄
• 흡수법칙
  • 𝑨 ∩ (𝑨 ∪ 𝑩) = 𝑨
  • 𝑨 ∪ (𝑨 ∩ 𝑩) = 𝑨
• 𝑼와 ∅의 여집합
  • ∅𝒄 = 𝑼
  • 𝑼𝒄 = ∅
• 차집합법칙
  • 𝑨 − 𝑩 = 𝑨 ∩ 𝑩𝒄