이산수학 - 3. 집합

1. 집합의 개념

2. 집합의 종류

3. 집합의 연산

4. 집합의 대수법칙

5. 집합의 분할

 

 

1. 집합의 개념

집합(set): 기준에 의해 분류되어 공통된 성질을 가지며 중복되지 않는 원소의 모임

- 원소나열법: A = {1,2,3,4,5}

- 조건제시법: A = {x| 0<x<6, x∈N}

(N: 자연수 Z: 정수 Q: 유리수 I: 무리수 R: 실수 C: 복소수)

 

집합과 원소의 포함관계

a∈A - a가 집합 A의 원소이다.  a∉A - a가 집합 A이 원소가 아니다.

 

기수(cardinality): |A| = 집합 A가 포함하는 원소의 수

유한집합: 집합 A에 포함되는 원소의 개수가 유한한 집합

무한집합: 집합 A에 포함되는 원소의 개수가 무한한 집합

상등: 두 집합 A,B에 속하는 원소가 동일할 때, "두 집합 A,B가 상등이다" 라고 함. A=B

 

 

2. 집합의 종류

전체집합(Universial 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

(2) 모든 집합 A에 대해 ∅ ⊆ A (공집합은 집합이므로 집합기호를 사용해 비교한다.)

(3) 모든 집합 A에 대해 A ⊆ U

(4) 집합 A,B,C에 대해 A ⊆ B, B ⊆ C 이면 A ⊆ C 이다.

(5) 집합 A,B에 대해 A = B ⇔ (A⊆B∧B⊆A)

 

 

 

3. 집합의 연산

합집합(Union): A∪B

교집합(Intersection): A∩B

서로소(Disjoint): A∩B = ∅

차집합(Difference): A-B

대칭차집합(Symmetric Difference): A⨁B = A∪B - A∩B

여집합(Complement): A' = U-A

곱집합(Cartesian Product, 카르테시안 곱): 집합 A,B에 대하여 a∈A, b∈B일때, 순서쌍(a,b)의 집합 A×B, |A|×|B|=|A|×|B|

• A={1,2} B={a,b,c} A×B={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}, |A| = 2, |B| = 3, |A×B| = 2*3 = 6

멱집합(Power set): n개의 원소를 갖는 집합 A에 대하여 집합A의 모든 부분집합을 원소로 갖는 집합 P(A) = {B|B⊆A} |P(A)| = 2^n

• 공집합은 모든 집합의 부분집합이고 집합 자기 자신도 부분집합이 된다.
• A = {1,2,3}, P(A) = {∅, (1), (2), (3), (1,2), (1,3), (2,3), (1,2,3)}, |P(A)| = 2^3 = 8
• A = {∅, {∅}} , P(A) = {∅, {∅}. {{∅}}, {∅,{∅}}} |P(A)| = 4

 

경북대 20년도 기출: 집합 X = {1,2,3} 에서 P(x) 가 X의 멱집합일때 P(X)를 원소나열법으로 표현하고 집합 A의 크기가 4일때, log2|P(P(A))| 를 구하여라

 

P(x) = {∅, (1), (2), (3), (1,2), (1,3), (2,3), (1,2,3)}

P(A) = 2^4 = 16, P(16) = 2^16, log2|2^16| = 16

 

 

 

4. 집합의 대수법칙

 

 출처: 충북대 강의노트

 

 

 

5. 집합의 분할

분할(Partition): 공집합이 아닌 임의의 집합A를 서로소면서 공집합이 아닌 부분집합으로 나누는 것.

분할의 성질  

• Ai ≠ ∅ (분할된 집합은 공집합이 없다)
• Ai ⊆ A (분할된 집합은 본래 집합의 부분집합이다.)
• A = A1 ∪ A1 ∪ A2 .... ∪ Ai (모든 부분집합의 합집합은 본래 집합과 동치)
• i ≠ j 이면, Ai ∩ Aj (서로다른 부분집합의 교집합은 없다.)

A = {a,b,c} 의 모든 분할

{{a},{b},{c}}

{{a,b},{c}}

{{a,c},{b}}

{{b,c},{a}}

{{a,b,c}}

 

 

 

 

+) 편입 기출

(19) A = {0,1,2,3} B = {4,5,6,7} 일때 다음에 답하라

1) A의 멱집합: {∅, (0), (1), (2), (3), (0,1), (0,2), (0,3), (1,2), (1,3), (2,3), (0,1,2), (0,1,3), (0,2,3), (1,2,3), (0,1,2,3)}

2) AxB: {(0,4), (0,5), (0,6), (0,7), (1,4), (1,5), (1,6), (1,7), (2,4), (2,5), (2,6), (2,7), (3,4), (3,5), (3,6), (3,7)}

3) A∩B: ∅