[SW Expert Academy][Computational Thinking] 논리와 증명

링크

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPCwCKAAPw5UW6&subjectId=AV1lGr4qAAYCFAb_

문제 1

p	q	~p∧q	q	~(~p∧q)∨q
T	T	F	T	T
T	F	F	F	T
F	T	T	T	T
F	F	F	F	T

p	q	~p∨q	p∧~q	(~p∨q)∨(p∧~q)
T	T	T	F	T
T	F	F	T	T
F	T	T	F	T
F	F	T	F	T

문제 2

p	q	~p∨q	p∧~q	(~p∨q)∧(p∧~q)
T	T	T	F	F
T	F	F	T	F
F	T	T	F	F
F	F	T	F	F

p	q	p∧q	p∧~q	(p∧q)∧(p∧~q)
T	T	T	F	F
T	F	F	T	F
F	T	F	F	F
F	F	F	F	F

문제 3

p	q	p∨q	p∧(p∨q)
T	T	T	T
T	F	T	T
F	T	T	F
F	F	F	F

• 결론 : 동등

p	q	~p∨~q	~(p∨q)
T	T	F	F
T	F	T	F
F	T	T	F
F	F	T	T

• 결론 : 동등하지 않음

문제 4

1. (p∧~q)∨(p∧q) -> p∧(~q∨q) -> p∧T -> p
2. (p∨~q)∧(~p∨~q) -> (p∧~p)∨~q -> F∨~q -> ~q

문제 5

1. ∀x ∈ R , x2 ≥ x
   -> x2-x≥0 -> x(x-1)≥0 이므로 1>x>0 의 실수에 대해서는 성립하지 않는다.
   그렇기 때문에 거짓이다.
2. ∀x ∈ Z , x2 ≥ x
   -> x2-x≥0 -> x(x-1)≥0 이므로 x≥1과 0≥x인 범위에 대해 성립한다. 1과 0 사이에는 정수가 존재하지 않기 때문에 참이다.
3. ∃x ∈ R , x2 < x
   -> x2-x<0 -> x(x-1)<0 이므로 0<x<1인 범위 내에서 성립한다. 해당 범위에 어떤 실수가 하나 이상 존재하므로 참이다.
4. ∃x ∈ Z , x2 < x
   -> x2-x<0 -> x(x-1)<0 이므로 0<x<1인 범위 내에서 성립한다. 해당 범위에 어떤 정수가 하나도 존재할 수 없으므로 거짓이다.

문제 6

자연수 k에 대해 n이 짝수이면 2k이므로 3n+5=6k+5=2(3k+2)+1이므로 홀수이다.

문제 7

자연수 k에 대해 n이 홀수이면 n=2k+1로 표현할 수 있으므로, n2+n = 4k2+6k+2 = 2(2k2+3k+1) 이므로 짝수이다.

문제 8

서로 다른 자연수 m과 n에 대해서 m이 짝수이고 n이 홀수이면 m=2a, n=2b+1로 나타낼 수 있으므로 2m+3n = 4a+6b+3 = 2(2a+3b+1)+1 로 나타낼 수 있으므로 홀수이다.

문제 9

자연수 n에 대해, n2+5가 홀수이면 n은 짝수이므로 대우명제로서 n이 홀수이면 n2+5가 짝수라는 명제가 성립하므로 자연수 k에 대해서 n=2k+1로 표현하면, n2+5 = 4k2+4k+6 = 2(2k2+2k+3) 이므로 짝수이다.

문제 10

n2이 짝수이면, n은 짝수인 명제에 대해 대우명제인 n이 홀수이면, n2이 홀수인 명제가 성립하므로, 자연수 k에 대해서 n=2k+1이므로 n2 = 2(2k2+2k)+1 이므로 홀수이다.

문제 11

자연수 n에 대해서 어떤 자연수 k에 대해 홀수와 짝수를 2k, 2k+1로 표현할 수 있으므로, n2+5n+3 = 4k2+10k+3 = 2(2k2+5k+1)+1이므로 짝수일 때 홀수이고 n2+5n+3 = 4k2+14k+9 = 2(2k2+7k+4)+1 이므로 홀수일 때도 홀수이다. 그러므로 항상 홀수이다.

문제 12

n2이 3의 배수이면 n인 3의 배수인 명제의 대우명제인 n이 3의 배수가 아니면 n2이 3의 배수가 아니라는 명제가 성립하므로 어떤 자연수 k에 대해서 3의 배수가 아닌 경우는 n=3k+1, n=3k+2인 경우로 나눌 수 있다. n=3k+1일 때, n2 = 3(3k2+2k)+1이므로 3의 배수가 아니며 n=3k+2일 때, n2 = 3(3k2+4k+1)+1이므로 3의 배수가 아니다.

문제 13

n이 홀수이면 자연수 k에 대해서 짝수인 4k+2 = 2(2k+1)을 제외한 4k+1, 4k+3인 경우로 나눌 수 있다. n2 = 16k2+8k+1 = 8(k2+k)+1 이고 n2 = 16k2+24k+9 = 8(2k2+3k+1)+1 이므로 8로 나눈 나머지는 1이다.

문제 14

자연수 k에 대해서 모든 자연수는 3k, 3k+1, 3k+2 이기 때문에, (3k)2 = 9k2 = 3(3k2), (3k+1)2 = 9k2+6k+1 = 3(3k2+2k)+1, (3k+2)2 = 9k2+12k+4 = 3(3k2+4k+1)+1 이므로 나머지가 2가 아니다.

문제 15

유리수와 무리수의 합이 유리수라고 가정한다면 유리수 a, 무리수 b, 유리수 c에 대해서 a+b=c 이므로 b=c-a이다. 유리수 간의 뺄셈은 유리수여야만 하므로 성립할 수 없다. 그러므로 유리수와 무리수의 합은 무리수이다.

문제 16

$\sqrt{2}$가 유리수면 $\sqrt{2}$=$\frac{b}{a}$ 이면서 a와 b는 기약분수의 특성상 서로다른 최대공약수를 1로 가지는 '서로수'이다. 제곱하면 2=$\frac{b^2}{a^2}$이므로 2a2=b2이다. b2이 짝수이기 때문에 b도 짝수이다. 자연수 k에 대해서 2a2=4k2 -> a2=2k2이기 때문에 a2이 짝수이기 때문에 a도 짝수이다. a와 b 모두 짝수이기 때문에 최대공약수를 1이상 가지므로 서로수가 아니기 때문에 모순이다.

문제 17

log25를 유리수라고 가정하면 서로수 a와 b에 대해 log25=$\frac{b}{a}$이므로 5=2$\frac{b}{a}$ -> 5b=2a이므로 홀수 = 짝수 이므로 모순이다.

문제 18

n=1일 때, 1=1로 성립한다. n=k일 경우, 1+2+3+···+k = $\frac{k(k+1)}{2}$이므로 양변에 k+1을 더하면 1+2+3+···+k+(k+1) = $\frac{k^2+3k+2}{2}$ = $\frac{(k+1)(k+2)}{2}$이므로 n=k+1일 때도 성립한다.

문제 19

n=1일 때, 1=1로 성립한다. n=k일 경우, 12+22+32+···+k2 = $\frac{k(k+1)(k+2)}{6}$이므로 양변에 (k+1)2을 더하면 12+22+32+···+k2+(k+1)2 = $\frac{(k+1)(k+2)(k+3)}{6}$으로 정리된다. 그러므로 n=k+1일 때도 성립한다.

문제 20

n=1일 때, 1=1로 성립한다. n=k일 경우, $\displaystyle\sum_{i=0}^{k}{r^i}$=$\frac{r^{k+1}-1}{r-1}$인데 양변에 rk+1을 더하면 $\displaystyle\sum_{i=0}^{k}{r^{i+1}}$=$\frac{r^{k+1}-1}{r-1}$+rk+1=$\frac{r^{k+2}-1}{r-1}$ 이므로 n=k+1일 때 성립한다.

문제 21

n=2일 때, 6이므로 6으로 나누어 떨어진다. n=k일 때, k3-k이므로 k(k-1)(k+1)이다. 세 수가 연속되므로 하나 이상의 수가 각각 2의 배수이고 3의 배수일 수 있다. 그렇기 때문에 세 수의 곱은 6의 배수이므로 6으로 나누어 떨어진다.

문제 22

n=2일 때, $\sqrt{2}$<1+$\frac{1}{\sqrt{2}}$이므로 성립한다. n=k일 때, $\sqrt{k}$<$\frac{1}{\sqrt{1}}$+$\frac{1}{\sqrt{2}}$+···+$\frac{1}{\sqrt{k}}$ 이므로 양변에 $\sqrt{k+1}$-$\sqrt{k}$을 더하면 $\sqrt{k+1}$<$\frac{1}{\sqrt{1}}$+$\frac{1}{\sqrt{2}}$+···+$\frac{1}{\sqrt{k}}$+$\frac{1}{\sqrt{k+1}+\sqrt{k}}$이다. n=k+1일 때, $\sqrt{k+1}$<$\frac{1}{\sqrt{1}}$+$\frac{1}{\sqrt{2}}$+···+$\frac{1}{\sqrt{k}}$+$\frac{1}{\sqrt{k+1}}$이기 때문에 형태가 다르지만 후자가의 마지막 더해진 항이 더 크기 때문에 부등호가 성립하여 전체적으로 성립한다.

문제 23

n*n개의 체스판에서 초기에 n개 이상의 칸이 감염되어야 있어야 함으로 하나를 제외한 n-1칸이 감염되어 있을 때, 전체가 감염될 수 없음을 증명하면 된다. 그러므로 n-1개일 때는 (n-1)2<n2이 되어 전체를 감염시킬 수 없으므로 n개일 때만 감염시킬 수 있다.