이산수학

1. 다음이 올바른 주장인지를 밝혀라.
(1) A⇒B 1. ~C가 참이면 C는 거짓
~B⇒C 2. ~B는 거짓이므로 B는 참 (⇒는 가정 참, 결론이 거짓일때만 거짓)
~C 3. A는 참도되고 거짓도 된다
------ 4. 따라서 이것은 잘못된 것이다.
A
(2) P⇒(Q⇒R) 1. Q가 참이면
Q 2. R은 참, P는 참도되고, 거짓도 된다
----------- 3. 따라서 P⇒R은 P는 참, 거짓이고 R은 참이므로 이문제는 올바른 것이다.
P⇒R
2. 유클리드 호제법에 의하여 85와 201의 최대공약수를 구하라.
201=85*2+31
85=31*2+23
31=23*1+8
23=8*2+7
8=7*1+1
7=1*7+0 나머지가 0이 나올때까지, 그러므로 최대공약수는 1
3. A={a, b, c, d}에서의 다음의 세 관계에 대하여 반사적인지, 아니면 비반사적인지 밝혀라.
R1={(a,a), (a,b), (b,b), (b,c), (c,b), (c,c), (c,d), (d,d)}
R2={(a,b), (a,c), (a,d), (b,c), (b,d), (c,d)}
R3={(a,a), (b,c), (c,b), (d,d)}
R4={(a,b)}
----------------------------------------------
R1은 (a,a), (b,b), (c,c), (d,d)가 있으므로 반사적 ○
쌍으로 들어가 있는 것을 찾아야 되므로 (b,c), (c,d)밖에 없으므로 대칭적 ×
(b,c)와 (c,b)가 동시에 관계에 속해있어 반대칭적 × (R2는 대칭적 ○)
(a,b), (b,b), (b,c)에서 (a,c)가 없으므로 추이적 ×
비반사적 ×
R3는 반사적 ×
대칭적 ○
추이적 ×
반대칭적 × -> 쌍으로 들어가 있는 것이 있는데 (b,c)는 같지 않기 때문에
비반사적 ×
R4는 반사적 ×
대칭적 ×
추이적 ○
반대칭적 ○
비반사적 ○
4. 분할 {{1,2},{3,4}}의 동치관계 R와 동치류 [1], [2], [3], [4]를 구하라.
블록 {1,2}에 대하여 순서쌍을 만들면 (1,1), (1,2), (2,1), (2,2)
블록 {3,4}에 대하여 순서쌍을 만들면 (3,3), (3,4), (4,3), (4,4)
따라서, R={(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4)}
동치류는 [1]=[2]={1,2}
[3]=[4]={3,4}
예제) A={1,2,3,4,5}
나머지가 3인 관계 R= {(1,1), (1,4)
(2,2), (2,5)
(3,3)
(4,1), (4,4)
(5,2), (5,5)}
동치류 [1]={1,4}=[4]
[2]={2,5}=[5]
[3]={3}
A의 분할 P={{1,4}, {2,5}, {3}}
※ 반사적, 대칭적, 추이적이면 R는 동치관계이다.
5. (x+y)^20의 전개식에서 x^12*y^8의 계수를 구하라.
20!
C(20,8) = ------- = 125970
12!*8!
(x+y)^10 -> x^3*y^7 = 10C7
(x+3)^10 -> x^3*3^7 = 10C7 = 10C3 * 3^7