일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 2023채용박람회
- 이런 사람에게 "절대" 돈과 시간 쓰지 마세요. (이헌주 교수 3부)
- 최단경로문제
- 티스토리챌린지
- 오블완
- kgol
- 데이터베이스시스템
- playground배열
- 숫타니파아타
- 집착형
- 등록금0원
- 무소의뿔
- 오일러투어
- 배윤슬
- 다자녀장학금
- 이분그래프
- 합의정리
- 나르시스트
- 직선의방정식
- 맥북에서 wxMaxima 설치
- 그래프2
- 제거된값 첨부하기
- 아이엔이야기
- wxMaxima install for mac os
- 윤파고
- 쌍대성원리
- 정보처리기사공부방법
- wxmaxima
- 청년도배사 이야기
- 허스켈그래프
- Today
- Total
사적공간
부분집합 문제 본문
답: (1): 8, (2):8 (3):4
답이 중요한게 아니고
문제는 직관적으로 볼 때, 부분집합의 개수가 (1)+(2)= 전체 부분집합의 수 으로 읽힌다는 점이다.
이 문제의 핵심은 a,b가 속하는 부분집합 외에 나머지 부분집합이 무엇인지 생각해봐야 한다는 점이다.
= 24, ab가 속하지 않는 부분집합 8 + ?...
?가 무엇일까? =16
전체 부분집합의 개수 = 2의 5승(원소의 개수) = 32
8+8=! 32 나머지 16개가 빈다.
경우의 수를 따져서
ab가 없고 + ab가 있고 + a가 있고 + b가 있고
2의 2승개의 가능성을 모두 더해야 함.
(1)+(2)+a가 속하고 b가 없는 부분집합+b가 속하고 a가 없는 부분집합
a가 속하고 b가 없는 부분집합 =
b가 없는 부분집합(a가 있는 부분집합+ a가 없는 부분집합-a가 없는 부분집합)
b가 없는 부분집합=acde만 있는 부분집합= 2의 4승
2의 4승 / 2 (a가 있고 없고는 반반이니까) = 2의 3승 =8
b가 속하고 a가 없는 부분집합도 기호만 바꿔서 계산하면 마찬가지로 = 2의 3승
다시 정리하면
(1)8+(2)8+8+8 = 32 개
(3)은 (2)의 논리에 (1)의 논리를 적용해서 푼다.
그런데 (2)는 (1)을 풀어서 얻었다. (책 풀이법에 따라;; )
순서가 (1) -> (2) -> (3) : (2) + (1) 로 푼 것이다.
1) a,b는 속하는 집합의 개수 안에서 c는 속하지 않는 부분집합의 개수를 구하는 방법
a,b가 속하는 부분집합의 개수는 a,b가 속하지 않는 부분집합의 개수를 먼저 구한다.
그럼 2의 3승 해서 8개, 여기에 a,b를 추가하면 반대로 8개가 됨.
여기에서 c가 속하지 않는 부분집합의 개수를 구하면(ab가 속하면서 c가 있고 없는 두 세계)
8을 2로 나누어 4가 됨.
ab
abc
abd
abe
abcd
abce
abde
abcde
전체집합은 c가 있는 세계와 없는 세계로 나뉨,
모든 경우에 절반으로 생각해볼 수 있을 것 같다.
그렇다면...
-원소가 1개가 있고 없고의 경우가 절반으로 나뉜다면 = /2
-원소가 2개가 있고 없고의 세계는 = /2^2 로 나누면 될 것 같다. (위에서 정리한 식과 마찬가지로)
이 경우는 위에서도 언급했지만
ex) 원소가 ab의 유무를 기준으로 세계를 보면
ab로 나누는 세계는 b만 없거나, a만 없거나, ab 둘다 없는 경우, ab 둘다 있는 경우
로 나누어 볼 수 있을 것 같다.
2) 위 문장에 역을 취해서 구하는 방법
1) a,b는 속하는 집합의 개수 안에서 c는 속하지 않는 부분집합의 개수를 구하는 방법
-> c가 속하지 않는 부분집합 안에서 a,b가 속해 있는 부분집합의 개수
2의 4승 = 16개 = c가 속하지 않는 부분집합
16개를 4로 나누면 될 것 같다. (같은 형광펜으로 칠한 것에서 얻은 통찰)
4개
이걸 가지고 응용문제를 풀어보면
(1). 30을 4로 나누면 7,
2^7 =128
(2). 2^ 7-2=5 = 32
헤깔리는 부분은
4 = 32개 (4는 속하고, 8은 없는 =! 8이 없는 )
8 = 32개( 8은 속하고, 4가 없는 -! 4가 없는 )
4 8 =32개
x =32개
전체 - 4,8이 속하지 않는 부분집합의개수(32) = 96
8이 없는 세계는 2의 6승임.
(3) 32/2 = 16
(2)에서 12가 있는 세계와 12가 없는 세계
'KNOU_CS > 이산수학' 카테고리의 다른 글
그래프1 차수에 관해 생각해보기 (0) | 2022.08.10 |
---|---|
그래프1 이분그래프 (0) | 2022.08.09 |
부울대수 (0) | 2022.08.09 |
이산수학 학습주안점 (0) | 2022.08.02 |
소수 prime_number 식별_c (0) | 2022.07.29 |