Chapter 3. 집합론

개요 집합과 관련된 기본적인 정의로부터 분할에 이르는 다양한 논제들을 고찰 집합의 기본 정의와 표현 방법들을 소개하고, 유한 집합, 무한 집합, 부분 집합, 진부분 집합, 카디날리티 등의 개념을 살펴봄 집합의 연산에 있어서 합집합, 교집합, 차집합, 대칭 차집합, 여집합, 카티시안 곱이라고도 불리는 곱집합 등의 연산과 벤 다이어그램을 통한 집합의 연산을 학습 집합류와 멱집합을 살펴보며 동치류로 만들어지는 집합의 분할 등을 다룸

CONTENTS 3.1 집합의 표현 3.2 집합의 연산 3.3 집합류와 멱집합 3.4 집합의 분할

3. 집합론 집합(Set) 집합은 원소(element)라고 불리는 서로 다른 객체들의 모임으로 현대 수학에서 가장 기초가 되는 개념 집합의 개념은 수학이나 컴퓨터 분야뿐만 아니라 과학이나 공학 분야 등에서 폭넓게 사용 집합의 개념은 19세기 말 독일의 수학자 칸토어(Georg Cantor)가 처음으로 제안 수학적 객체들에 대하여 집합을 정의할 수 있으므로 집합은 수학의 기본 개념 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 a ∉S는 a가 집합 S의 원소가 아님을 나타냄 집합을 표시할 때는 알파벳 대문자 A, B, C, …, Z 등으로 표시함 집합을 구성하는 원소(element 또는 member)는 소문자 a, b, c, …, z 등으로 표시 집합에 속한 원소들로 구성되어 있는데, 집합을 S라하고 하나의 원소를 a라 하면, a ∈S는 a가 집합 S의 원소임을 나타냄 a ∉S는 a가 집합 S의 원소가 아님을 나타냄 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 집합을 표현하는 방법 원소 나열법 집합의 원소들을 { } 사이에 하나씩 나열하는 방법 예를 들어, 1부터 5까지의 자연수의 집합을 원소 나열법으로 나타내면 다음과 같다. S ＝ {1, 2, 3, 4, 5} 여기서 의미가 명확한 경우 모든 원소를 나열하는 대신에 …을 이용 {a, b, …, z}는 소문자 알파벳의 집합을 의미 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 2) 조건 제시법 집합의 원소들이 가지고 있는 특정한 성질을 기술하여 나타내는 방법 조건 제시법의 표현은 S ={x | p(x)}임 x는 원소를 대표하는 변수이고, p(x)는 원소들이 가지고 있는 성질임 예를 들어, 1부터 5까지의 자연수의 집합을 조건 제시법으로 나타내면 다음과 같다. S ＝ {x | x는 자연수이고1≤x≤5} Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 카디날리티(Cardinality) 집합 S 내에 있는 서로 다른 원소들의 개수 |S| 로 표기 예를 들어, 집합 A={1, 3, 5, 7, 9}, 집합 B={1}, 집합 N={1, 2, 3, …}에서, |A| = 5, |B| = 1, |C| = ∞ Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 집합 S1에서 집합 S2로의 일대일 대응인 함수가 존재할 때 S1과 S2는 같은 카디날리티를 가짐 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 ‘가산적 집합(countable set)’또는‘가산적으로 무한한 집합(countably infinite set) 정수의 집합과 일대일의 대응 관계에 있는 집합 유리수들의 집합 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.1 집합의 표현 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 벤 다이어그램(Venn Diagram) 주어진 집합들 사이의 관계와 집합의 연산에 대하여 이해하기 쉽도록 이용 기본적인 집합의 관계 (a) A⊆B (b) 집합 A와 집합 B에 공통된 원소가 있을 때 (c) 집합 A와 집합 B에 공통된 원소가 없을 때 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 합집합(Union) : A∪B 집합 A 또는 집합 B에 속하는 모든 원소의 집합, A ⋃B로 표기함 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 교집합(Intersection) : A∩B 서로 소(Disjoint): A∩B = ∅ 두 집합 A, B에 대하여 이들의 교집합은 집합 A에도 속하고 집합 B에도 속하는 모든 원소의 집합을 말하며, A ∩B로 표기함 A∩B = {𝒳|𝒳 ∈ A ∧𝒳∈B} 서로 소(Disjoint): A∩B = ∅ Mutually exclusive Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 차집합(Difference) : A-B 두 집합 A, B에 대하여 이들의 차집합은 집합 A에 속하고 집합 B에는 속하지 않는 모든 원소들의 집합 A - B = {𝒳|𝒳∈ A ⋀𝒳∉B} Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 대칭 차집합(Symmetric Difference) : A⨁B 집합 A, B에 대하여 이들의 대칭 차집합은 A ∪ B의 원소 중에서 A ∩ B에 속하지 않는 모든 원소들의 집합임 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 곱집합(Cartesian Product) : A×B 순서쌍 (a, b)는 쌍의 원소들 간의 순서에 의해 구분이 되므로 a≠b이면 (a, b)≠(b, a)표현함 두 순서쌍이 (a, b)＝(c, d)이면, a＝c이고 b＝d임 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 집합 연산의 카디날리티 집합의 연산에 의해 새로 만들어진 집합들에 대한 카디날리티를 다음과 같이 표현함 |A∪B|=|A|+|B|-|A∩B| |A∩B|=|A|+|B|-|A∪B| |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C | |A-B|=|A∩B|=|A|-|A∩B| |A×B|=|A|∙|B | Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 집합의 대수 법칙 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 A와 B의 벤 다이어그램 같으므로 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 쌍대의 원리를 이용하여 드 모르간의 법칙 중 첫 번째 식을 사용하면 쌍대로 바꾸면 Discrete Mathematics Chapter 3. 집합론

3.2 집합의 연산 Discrete Mathematics Chapter 3. 집합론

3.3 집합류와 멱집합 집합류(Class) 집합 A에 대하여 A의 원소의 개수가 n개일 때 A의 부분 집합의 집합류 : 부분집합들로 이루어진 집합, 원소가 집합인 집합 Discrete Mathematics Chapter 3. 집합론

3.3 집합류와 멱집합 Discrete Mathematics Chapter 3. 집합론

3.3 집합류와 멱집합 집합 A에 대하여 P(A)의 원소들을 나타내기 위하여 흔히 A1, A2 , ⋯, An과 같이 A 밑에 첨자(index)를 붙여서 표기 첨자가 붙은 집합에서 그들의 합집합과 교집합의 연산은 다음과 같이 표기 Discrete Mathematics Chapter 3. 집합론

3.3 집합류와 멱집합 Discrete Mathematics Chapter 3. 집합론

3.4 집합의 분할 Discrete Mathematics Chapter 3. 집합론

3.4 집합의 분할 블록(Block) 분할의 원소인 Ai 분할에 대한 예로 대한민국의 여러 개의 도를 들 수 있음 각 도들은 공유하는 면적이 없고, 각 도를 합한 것은 대한민국 전체가 되므로 대한민국의 분할이라고 함 분할은 집합을 구성하는 원소가 서로 소이고 각 원소들의 합집합이 원래의 전체 집합이 되어야 함 Discrete Mathematics Chapter 3. 집합론

3.4 집합의 분할 Discrete Mathematics Chapter 3. 집합론

3.4 집합의 분할 Discrete Mathematics Chapter 3. 집합론

퍼지집합(fuzzy set) ㆍ 퍼지집합 A 에서는 소속함수(membership function) 가 각 원소를 : 집합 [0,1]로 대응 : ㆍ소속정도(degree of membership) : (x), x ∈A ㆍ퍼지집합의 연산(Standard Operation이라 정의함) 합집합 : 원소의 소속정도 값이 큰 쪽을 선택 교집합 : 원소의 소속정도 값이 작은 쪽을 선택 여집합 : 1에서 해당 소속정도 값을 뺀 값으로 표현

퍼지집합(fuzzy set) 에 가 포함되는 정도 에 가 포함되는 정도 예) 키가 크거나 몸무게가 무거운 사람의 집합, 키도 크고 몸무게도 무거운 사람의 집합, 키가 크지 않은 사람의 집합

퍼지집합(fuzzy set)

퍼지집합(fuzzy set) ㆍ지지(support)집합 ㆍ -수준( ) 집합 전체집합 U 내의 원소들 중에서 퍼지집합 A 에 조금이라도 포함되어 있는 원소들로 이루어진 집합 ㆍ -수준( ) 집합 일정한 소속함수 값 이상 포함된 원소들로만 구성된 집합