관리 메뉴

사적공간

부분집합 문제 본문

KNOU_CS/이산수학

부분집합 문제

2sac 2022. 7. 29. 17:28

출처: 수학의정석(하) p89

답: (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개 

 

이걸 가지고 응용문제를 풀어보면 

 

출처: 수학의정석(하) p89

 

(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