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

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

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

2 Chapter 03. 집 합

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

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

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

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

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

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

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

10 기본 개념(계속) [정의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로 표시

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

12 기본 개념(계속) 유한집합(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}

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

14 기본 개념(계속) [예제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이다.

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

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

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

18 집합의 연산(계속) [예제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}

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

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

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

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

23 집합의 연산(계속) [예제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는 양의 정수}

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

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

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

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

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

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

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

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

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

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

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

35 집합의 연산(계속) [예제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 의 비트열: 집합 B 의 비트열: 두 비트열의 합집합은 다음과 같다. ( )∪( ) =( )∨( ) = 따라서 A∪B ={1, 2, 3, 4, 5, 6, 7}이다.

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

37 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|

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

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

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

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

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

43 [예제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)

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

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

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

47 퍼지집합(계속) [예제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)}

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

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

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

51 Thank you ehanbit.net