이산수학: 집합 ①

제1장: 명제 논리와 집합의 기초 (Foundations of Logic & Sets)

1.1 논리학과 집합론

세상의 모든 집합은 논리 연산로도 표현할 수 있다! 근데 굳이 왜 나누었냐 싶긴하지.

맞아요~ 얘네도 미묘한 차이가 있어요~

	논리연산	집합
대상	명제, 조건식, 스위치 상태(T/F)	원소들의 모임, 데이터의 집합, 공간
목적	데이터나 상황이 조건에 맞는지 틀린지 판별	조건을 만족하는 객체(Object)들을 묶어서 관리하고, 전체적인 구조를 시각화
예시	"이 유저의 레벨이 50 이상인가?" → 맞다(True) / 아니다(False)	"레벨이 50 이상인 유저들의 목록" → [유저A, 유저B, 유저C ...]

논리연산은 문지기고 집합은 문지기가 분류한 것들을 넣어놓은 방쯤 되시겠다.

그래서 집합을 논리연산자로 표현할 수 있다!

요로코롬!

​

1.2 원소와 집합의 표기법

​

1.2.1 집합의 기호

집합의 기호를 배워봅시다.

중간머리의 여집합은 대머리

중간머리와 대머리의 교집합은 진짜 대머리

중간머리와 대머리의 합집합은 풍성머리

1∈A	원소 1은 집합 A에 포함된다.
5∉A	원소 5는 집합 A에 포함되지 않는다.
A = {1, 2, 3}	집합 A의 원소는 1, 2, 3이다.

B⊂A, B⊆A	집합 B는 집합 A에 포함된다. 집합 B는 집합 A의 부분집합이다.
B⊂A이고, A≠B	B가 A의 부분집합이지만 A자신은 아니다. B는 A의 진부분집합이다.
A = B	A와 B는 서로 같은 집합이다.
B⊄A	집합 B는 집합 A에 포함되지 않는다. 집합 B는 집합 A의 부분집합이 아니다. (A∩B = ∅와 같은 모양일 수 있음)
A∩B = ∅	A와 B는 공통된 원소가 하나도 없다. A와 B는 서로소이다. (B⊄A와 같은 모양일 수 있음)

기호	읽는 법	뜻 (설명)
A ∩ B	A 교집합 B	집합 A와 B에 공통으로 들어 있는 원소들의 집합
A ∪ B	A 합집합 B	집합 A에 속하거나 B에 속하는 모든 원소들의 집합
A^c	A의 여집합	전체집합U 중 A를 제외한 원소들의 집합
A - B	A 차집합 B	집합 A의 원소 중 B에 속하는 원소를 제외한 집합

기초개념 끝!

1.2.2 집합의 표현방법

집합을 나타내는 방법은 크게 3가지가 있다.

원소나열법	집합에 속하는 모든 원소를 중괄호 { } 안에 나열하는 방법	{1, 3, 5, 7, 9}
조건제시법	원소들이 갖는 공통적인 성질(조건)을 제시하는 방법	{x|x는 10이하의 홀수}
벤 다이어그램	집합과 원소의 관계를 그림으로 나타내어 시각화하는 방법	원과 사각형으로 이루어진 그림

① 원소나열법(元素 羅列法 / tabular form)

'집합 A는 2, 3, 4만을 원소로 가지고 있다.'를

A={2, 3, 4}

로 표시한다.

오픈런마냥 줄세우는 일이다. 정직하기 그지없지.

그래서 중복된 숫자는 못쓴다. (한명의 사람은 중복되지 않는다고 생각해보자)

A={2, 3, 3, 4, 4} → A={2, 3, 4}

​

② 조건제시법(條件提示法 / set-builder form)

사실 실수의 수는 무한하다! 1과 2사이에는 1.1, 1.123141, 1.1231515125512 등 무수히 많은 소수점을 만들 수 있다! 원소나열법으로 쓸 수 있는 한계가 있다는거지.

그래서 범위를 정한게 조건제시법이다.

A={2, 3, 4}

를 조건제시법으로 표시하면

{n | n은 1보다 크고 4이하인 자연수} {n | n은 자연수의 집합, 1＜n ≤ 4}

등으로 표현할 수 있다.

③ 벤 다이어그램

 

1.3 원소의 개수에 따른 집합의 분류

유한집합	원소의 개수를 셀 수 있는 집합	A = {2, 4, 6\} 원소의 개수 n(A) = 3
공집합 (∅)	원소가 하나도 없는 집합 (유한집합에 포함)	B = {x | x는 1보다 작은 자연수} n(B) = 0
무한집합	원소의 개수가 끝이 없어 셀 수 없는 집합	C = {x | x는 자연수} = {1, 2, 3, ...}

1.4 집합 연산 법칙

① 교환법칙: A∪B = B∪A, A∩B = B∩A

② 결합법칙: (A∪B)∪C = A∪(B∪C)

③ 분배법칙: A∩(B∪C) = (A∩B)∪(A∩C)

⑤ 드모르간의 법칙

$(A∪B)^c=\combi{A}^c∩\combi{B}^c$(A∪B)c=Ac∩Bc​

$(A∩B)^c=\combi{A}^c∪\combi{B}^c$(A∩B)c=Ac∪Bc​

​