이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다 ehanbit.net

Chapter 03. 집 합

학습목표 집합 표현의 여러 가지 방법 익히기 집합 연산자들을 통해 새로운 집합 정의 집합의 종류를 이해하고 표현하기 집합의 대수법칙을 이용한 복잡한 집합 연산 단순화 퍼지이론을 통한 퍼지집합 연산의 이해

Section 01. 기본 개념 [정의1] 집합(set) 공통된 특성을 갖는 대상의 모임 원소(element) 원소 a가 집합 A에 속할 경우 ‘a는 집합 A의 원소다’ 라고 표현 a∈A 로 표시 원소 a가 집합 A의 원소가 아닐 경우 a A 로 표시

기본 개념(계속) 원소나열법 조건제시법 집합에 속하는 모든 원소를 쉼표를 이용하여 { }안에 나열하는 방식 집합에 속하는 원소들의 공통적인 특징을 조건식으로 제시하는 방식

기본 개념(계속) [예제02] 집합 A가 원소 2, 4, 6, 8, 10을 갖도록 집합 A를 원소나열법 과 조건제시법으로 나타내어라. [풀이] 원소나열법: 집합 A={2, 4, 6, 8, 10} 조건제시법: 집합 A={a| 2≤a≤10, a는 짝수}

기본 개념(계속) [정의2] 전체집합(universal set) 일정한 모임 전체의 원소를 포함하는 집합 U로 표시 공집합(empty set) 하나의 원소도 포함하고 있지 않은 집합 { } 또는 로 표시

기본 개념(계속) [예제05] 집합 A={a| a+1<0, a는 양의 정수}는 어떤 집합인지 설명 하 여라. [풀이]

기본 개념(계속) [정의3] 상등 두 집합 A 와 B 가 동일한 원소를 가짐 서로 같다(equal) A=B로 표시 a∈A면 a∈B고, a∈B면 a∈A일 때 A=B다. A=B ⇔ (a∈A ↔ a∈B)

기본 개념(계속) [정의4] 부분집합(subset) A와 B가 집합이고 A의 모든 원소가 B에 포함될 때 A를 B의 부분집합이라고 정의 A⊆B로 표시 A⊆B ⇔ (a∈A → a∈B), ∀a 진부분집합(proper subset) A가 B의 부분집합이지만 A와 B가 같지 않은 경우 A⊂B로 표시

기본 개념(계속) [정리01] 집합 A, B, C 에 대해 다음이 성립한다. (1) ⊆A (2) A⊆A (3) A⊆B고 B⊆C면 A⊆C다 (4) A=B ⇔A⊆B, B⊆A다

기본 개념(계속) 유한집합(finite set) 무한집합(infinite set) 원소 개수가 유한 개인 집합 유한하지 않는 집합이라고 한다. 대표적인 무한집합 (1) R={x| x는 실수} (2) Q={x| x는 유리수} (3) Z={x| x는 정수} (4) N={x| x는 자연수} (5) R+={x∈R| x>0} (6) I={x∈R| 0≤x≤1}

기본 개념(계속) [정의5] [예제09] 기수(cardinality) 유한집합 A가 갖는 원소의 개수 |A|로 표시 집합 A={a| a<10, a는 양의 정수}일 때 A의 기수가 얼마인지 구하여라. [풀이] A={1, 2, 3, 4, 5, 6, 7, 8, 9}므로 |A|=9다.

기본 개념(계속) [예제10] 다음 각 집합의 기수를 구하여라. (1) A={a| a는 영어 대문자의 ASCII 코드값} (2) B={b| b는 IPv4 주소 C class의 호스트번호 모임} (3) C={1월, 2월, 3월,…, 12월} [풀이] (1)집합 영어대문자의 ASCII 코드값의 집합 A={65, 66, 67,…}이다. 그런데 영어 대문자는 총 26글자므로 이에 대응되는 ASCII 코드값들도 26개의 값이 된다. 따라서, |A|=26이다.

기본 개념(계속) (2)집합 B에서 C class의 IP 주소는 총 3바이트의 네트워크 번호와 1바이트의 호스트 번호를 사용한다. 따라서 호스트 번호는 1바이트로 표현할 수 있는 값인 0~255번이 되어 |B|=256이 된다. 그러나 실제 IP 주소에서 0번과 255번은 네트워크 주소와 브로드캐스팅(broadcasting) 주소로 사용되며, 몇몇 호스트 번호는 특정 용도로 사용되어 일반 IP 주소로 사용할 수 없다. (3) 집합 C는 1년 12달의 모임으로 |C|=12다.

Section 02. 집합의 연산 벤 다이어그램(Venn diagram)

집합의 연산(계속) [정의6] 여집합 (complement) 전체집합 U 의 부분집합 A에 대하여 x∈U고 x A인 원 ={x| x∈U ∧ x A}

집합의 연산(계속) [예제13] 집합 A={1, 3, 5}일 때 다음을 구하여라. (1) 전체집합 U={1, 2, 3, 4, 5, 6, 7, 8}일 때 A의 여집합 (2) 전체집합 U={1, 3, 5, 7, 9}일 때 A의 여집합 [풀이] (1) 전체집합 U={1, 2, 3, 4, 5, 6, 7, 8}일 때 A의 여집합 는 다음과 같다. ={2, 4, 6, 7, 8} (2) 전체집합 U={1, 3, 5, 7, 9}일 때 A의 여집합 는 다음과 같다. ={7, 9}

집합의 연산(계속) [정의7] 합집합(union) 두 집합 A와 B에 모두 속하거나 둘 중 어느 한곳에 속 하는 원소들의 모임 A∪B={x| x∈A∨x∈B}

집합의 연산(계속) [정의8] 교집합(intersection) 두 집합 A와 B에 모두 속하는 원소들의 모임 A∩B={x| x∈A∧x∈B}

집합의 연산(계속) [예제18] 집합 A={1, 4, 9}, B={1, 2, 3, 4, 5}, C={1, 2, 3}일 때 [풀이]

집합의 연산(계속) [정의9] 차집합(difference) 집합 A와 B에 대해서 A에는 속하지만 B에는 속하지 않 는 원소들의 모임 A-B={x|x∈A∧x B}

집합의 연산(계속) [예제22] 전체집합 U 가 양의 정수 전체의 집합이고, A={1, 2, 3, 4, 5}, B={2, 4, 6}일 때 다음을 구하여라. (1) A∪B (2) A∩B (3) A-B (4) B-A (5) [풀이] (1) A∪B = {1, 2, 3, 4, 5, 6} (2) A∩B = { 2, 4} (3) A-B = {1, 3, 5} (4) B-A = {6} (5) = U-A = {6, 7, 8, 9, …} = {x| x>5, x는 양의 정수}

집합의 연산(계속) [정의10] 서로소(disjoint) 두 집합 A와 B에 대하여 A∩B=인 경우

집합의 연산(계속) [정리02] [정리03] 집합 A, B 가 유한집합이면 |A∪B|=|A|+|B|-|A∩B| 가 성립한다.

집합의 연산(계속) [예제25] 집합 A와 B는 서로소고 |A∪B|=|A|일 때 집합 B를 구하여 라. [풀이] 기수가 0인 집합, 즉 포함하고 있는 원소가 없으므로 B=이다.

집합의 연산(계속) [정리04] 전체집합 U와 부분집합 A에 대하여 다음과 같은 성질이 성립 한다. (1) ⇔

집합의 연산(계속) 집합의 대수법칙

집합의 연산(계속) [예제 30] 두 집합 A, B 에 대해 A-B=A∩ 임을 보이시오. B

집합의 연산(계속) [예제 31] 다음이 성립함을 보이시오. (1) (U ∩ A)∪(B ∩A)=A (2) (∪A) ∩(B∪A)=A

[예제 33] 다음은 어떤 여행사에서 여행자 100명에게 휴가 때 가고싶은 해외 휴양지를 설문 조사한 결과이다. 집합의 연산(계속) [예제 33] 다음은 어떤 여행사에서 여행자 100명에게 휴가 때 가고싶은 해외 휴양지를 설문 조사한 결과이다. 미국 : 32명, 유럽 : 20명, 동남아 : 45명 미국과 유럽 선택 : 15명 미국과 동남아 : 7명 유럽과 동남아 10명 선택하지 않은 사람 : 30명 휴양지 세 곳을 모두 여행하고 싶다고 선택한 사람은 몇 명인가? 휴양지를 한 곳만 선택한 사람은 몇 명인가 ?

집합의 연산(계속) 집합의 컴퓨터 표현 n 개의 원소를 갖는 전체집합 U의 원소에 u1, u2, u3,…,un과 같이 임의의 순서를 지정하여 표현 U 의 부분집합 A 는 n 개의 비트열(bit string)로 나타내며, U 의 i 번째 원소가 A 의 원소일 경우 비트열의 i 번째 값을 1로, 원소가 아닐 경우 0으로 설정

집합의 연산(계속) [예제35] 전체집합 U={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}에 대하여 하는 비트열을 구하여라. [풀이] U 의 홀수 정수를 원소로 하는 집합은 {1, 3, 5, 7, 9, 11}이 다. 따라서, 이를 비트열로 나타내면 다음과 같다. 101010101010 또한 U 의 짝수 정수를 원소로 하는 집합은 {2, 4, 6, 8, 10, 12}다. 이를 비트열로 나타내면 다음과 같다. 010101010101

집합의 연산(계속) 컴퓨터 비트열 표현에서의 집합 연산 합집합 bit-OR(bitwise-OR) 연산 교집합 bit-AND(bitwise-AND) 연산 여집합 비트의 부정(bitwise-NOT)

집합의 연산(계속) [예제37] 전체집합 U={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}의 부분집 합 A={1, 2, 3, 4, 5}, B={2, 4, 5, 6, 7}를 비트열로 나타내 고, 합집합과 교집합을 구하여라. [풀이] 집합 A 의 비트열: 111110000000 집합 B 의 비트열: 010111100000 두 비트열의 합집합은 다음과 같다. (111110000000)∪(010111100000) =(111110000000)∨(010111100000) =1111 1110 0000 따라서 A∪B ={1, 2, 3, 4, 5, 6, 7}이다.

집합의 연산(계속) 또한 두 비트열의 교집합은 다음과 같다. (111110000000)∩(010111100000) =(111110000000)∧(010111100000) =010110000000 따라서 A∩B ={2, 4, 5}다.

Section03. 곱집합과 멱집합 [정의11] 곱집합 (Cartesian product) 집합 A, B에 대하여 a∈A고 b∈B일 때 순서쌍 (a, b) 의 집합 AⅹB={(a, b)|a∈A∧b∈B} 곱집합 AⅹB의 기수 |AⅹB|=|A|∙|B|

곱집합과 멱집합(계속) [예제43] 임의의 집합 A에 대하여 Aⅹ은 무엇인지 구하여라. [풀이] Aⅹ={(a, b)| a∈A∧b∈}이다. 그런데 에는 어떤 원소 도 포함될 수 없으므로 b∈는 거짓이 되고, a∈A∧b∈ 역시 거짓이 된다. 즉, a∈A∧b∈를 만족하는 순서쌍의 집합은 없다. 그러므로 Aⅹ=이다.

곱집합과 멱집합(계속) [정리05] 집합 A, B, C 에 대하여 다음과 같은 성질이 성립한다. (1)Aⅹ(B ∩C)=(AⅹB )∩(AⅹC ) (2)Aⅹ(B ∪C)=(AⅹB )∪(AⅹC ) [증명] (1)

곱집합과 멱집합(계속) (2)

곱집합과 멱집합(계속) [정의12] 집합류(class) 임의의 집합 X에 대한 부분집합들의 모임 멱집합(power set) 집합 X에 대하여 X의 모든 부분집합을 원소로 갖는 집 합 P(X) = {Y|Y⊆X} 집합 X의 기수가 n이라고 하면 P(X)의 기수는 2n이다

곱집합과 멱집합(계속) [예제46] 다음 각 집합의 멱집합을 구하고 기수를 구하여라. (1) A={1, 2, 3} (2) B={, {}}

[예제47]집합 A={1,2,3}, B={3,4,5},C={2,3,4}일 때 다음을 구하시오. 곱집합과 멱집합(계속) [예제47]집합 A={1,2,3}, B={3,4,5},C={2,3,4}일 때 다음을 구하시오. A x B | A x B x C| P(A∩B∩C) P(A∩B)

Section04. 집합의 분할 [정의13] 분할(partition) 공집합이 아닌 임의의 집합 S를 서로소면서 공집합이 아닌 S의 부분집합으로 나눈 것 S의 분할은 다음과 같은 성질을 만족하는 집합류 (1) i =1, 2, …, k 에 대하여 Si 는 공집합이 아닌 집합 S의 부분집합이다. (2) S = (3) 이면 여기서 집합 Si 를 분할의 블록(block)이라고 한다.

집합의 분할(계속) [예제49] 자연수의 집합을 짝수와 홀수로 분할하여라. [풀이] 자연수 전체의 집합을 N이라고 하고, 홀수의 집합을 X1, 짝 수의 집합을 X2라고 하면 X1={x|n∈N, x=2n-1} X2={x|n∈N, x=2n}

Section05. 퍼지집합 퍼지집합(fuzzy set) 퍼지집합에서는 소속함수(membership function)가 각 원소를 집합 [0,1]로 대응 퍼지집합의 연산 합집합 : 원소의 실수 값이 큰 쪽을 선택 교집합 : 원소의 실수 값이 작은 쪽을 선택 여집합 : 1에서 해당 실수 값을 뺀 값으로 표현 퍼지집합의 응용 제어·정보 시스템등과 관련된 다양한 분야(지능로봇, 인공내장제 어 등)

퍼지집합(계속) [예제50] [풀이]A∪B ={(철수, 1), (영희, 1), (미영, 0.9), (정숙, 0.8)} 전체집합 U={철수, 영희, 미영, 정숙, 하진}에 대하여 퍼지집합 A를 키 큰 사람의 모임, 퍼지집합 B를 잘 생긴 사람의 모임으로 A={(철수, 1), (정숙, 0.8), (영희, 0.7)}, B={(영희, 1), (미영, 0.9), (정숙, 0.6)}과 같이 정의 했을 때 집합 A와 B의 합집합과 교집합과 A의 여집합을 구하여라. [풀이]A∪B ={(철수, 1), (영희, 1), (미영, 0.9), (정숙, 0.8)} A∩B ={(영희, 0.7), (정숙, 0.6)} A = {(철수,0), (정숙, 0.2), (영희, 0.3)}

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

[예제50]에서 퍼지집합 A의 지지집합을 구하여라. 퍼지집합(계속) [예제52] [예제50]에서 퍼지집합 A의 지지집합을 구하여라. [풀이] 퍼지집합 A의 지지집합은 다음과 같다. {철수, 정숙, 영희}

퍼지집합(계속) [예제53]다음은 나이를 나타내는 전체집합 U 위에 4개의 퍼지집합 infant, young, adult, old를 정의한 표이다. (1) 퍼지집합 young의 지지집합을 구하시오. (2) 퍼지집합 young-0.8-수준집합을 구하시오. (3) 퍼지집합 young과 old의 교집합을 구하시오 (4) 퍼지집합 old의 여집합을 구하시오.

Thank you ehanbit.net