Soft Logic & Hard Logic

Soft Logic

직관: 논리적인 느낌을 주는 것

특징: 빠르지만 정확하지는 않다. 착각을 일으킨다. 일상에서 유용한다. 어떤 의미인지 모두 알고있다고 가정하고 접근한다.

Hard logic

논라: 프로그래밍 언어 표현들이 논리학에서 나온 것. 알고리즘을 이해하기 위해 hard logic이 필요하다.

결론

Soft logic으로 알고리즘을 이해하는 것은 어렵다. 직관은 한계가 있으므로 증명을 통해 접근한다.

 

명제

기본 개념: 가정이 거짓이면 명제는 늘 참이다 / 결과가 참이면 전체 명제는 늘 참이다.

기호: ' ~ ' 은 NOT /  ' ∨ ' 는 OR /  ' ∧ ' 는 AND 의 뜻을 가진다.

*Or 의 관계인 경우 = inclusive, 택 일의 관계인 경우 = exclusive or

역/이/대우 : p → q 기준

역: q → p

이: ~p → ~q

대우: ~q → ~p

진리표를 활용한 문제를 풀이한다

ex) ~(~p∧q)∨q

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

명제의 변형/간소화

(p∧~q) ∨ (p∧q)을 명제식을 변형해 풀이하라.

공통으로 p∧ 가 들어간다
= (p∧ ) ( ~q∨q) 로 묶일 수 있다
= p ∧ U (전체집합)
= p

(p ∨ ~q)∧(~p ∨ ~q)을 명제식을 변형해 풀이하라.

공통으로 ∨ ~q 가 들어간다
= ( )∨( ~q) 로 묶일 수 있다
= (p∧~p)∨(~q)
= (False)∨(~q)
= ~q

명제 풀이

Q1) n이 홀수이면 n^2을 8로 나눈 나머지는 1임을 증명하라.

풀이1

n = 2k - 1 (k는 자연수)
n^2 = 4(k^2-k) + 1 = 4k(k-1) +1
k(k-1)은 짝수이므로 4k(k-1)은 8로 나누어떨어진다.

풀이2

n이 홀수일 때
n = 4k - 3, 4k - 1 (k는 자연수)
둘의 제곱은 모두 8로 나누었을 때 1이 된다

Q2) 어떤 자연수를 제곱하여도 그 결과를 3으로 나눈 나머지는 2가 아님을 증명하여라.

어떤 자연수 n은 자연수 k에 대해
n= 3k-2, 3k-1, 3k 로 표현할 수 있고
n2을 계산하면 3으로 나눈 나머지는 각각 1, 1, 0이다

Q3) 유리수와 무리수의 합은 무리수임을 증명하라.

<귀류법을 이용하여 증명>
유리수와 무리수의 합이 유리수라고 가정하자.
유리수 a 와 무리수 b가 더해지면 유리수 c가 나온다.
a + b = c 이에 c - a = b 이 성립한다.
유리수의 성질에 의해 c-a는 유리수여야 하지만 b는 무리수이므로 가정에 모순된다.
따라서 유리수와 무리수의 합은 무리수이다.

Q4) √2가 무리수임을 증명하라.

<귀류법을 이용하여 증명>

√2가 유리수라고 가정하면 기약분수로 표현이 가능하다.
√2 = b / a (a와 b는 서로소이며 (1이외의 공약수가 없음) a는 0이 아니다)
양변을 제곱하면 2 = b^2 /a^2 이다.
양변에 a^2을 곱해주면 2a^2 = b^2이다.
b^2은 짝수이므로 b도 짝수가 되어야한다.
b = 2c (c는 자연수)이다.
a^2 = 2c^2
a^2은 짝수이므로 a도 짝수가된다.
a 와 b가 모두 짝수라면 a와 b는 서로소가 아니게 되므로 가정에 모순된다.
따라서 √2는 유리수가 아니다.

Q5) log2(5) 는 무리수임을 증명하라.

<귀류법을 이용하여 증명>

log2(5)를 유리수라고 하면 log2(5)=b/a가 성립한다.
(a와 b는 서로소이며 a는 0이 아니다)
5 = 2^(b/a)로 나타낼 수 있다.
5^a =2^b로 나타낼 수 있다.
홀수 = 짝수가 되므로 모순이 발생한다.
따라서 log2(5)는 무리수이다.

수학적 귀납법

정의: P(1)이 참이고 P(n) → P(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.

관련 내용: 당구공 paradox, Infinitely many prime numbers

응용: 버블소트의 증명 → high-level에서는 소팅이 된다는 것을 직관적인 수준에서 설명하는 경우가 많은데 상세한 증명을 위해선 증명 가능한 명제가 필요하다. 배열 A[1],A[2]…A[n]을 소팅하는 알고리즘의 정확성을 증명하려면 A[1]<A[2]<...<A[n] 이 됨을 설명해야한다. 버블소트를 귀납법을 통해 증명해보자.

나의 풀이

<버블소팅 수학적 귀납법 풀이>
n의 크기를 가지는 임의의 배열에 대해 버블 소팅을 수행한 P(n)의 원소들은
A[0]<=A[1]<=...<=A[n-1]이 성립함을 증명한다.

1. P(2)가 성립하는지 확인한다.
   원소가 한 개인 경우 정렬의 의미가 없으므로
   한 개의 원소를 가지는 배열 A에 임의의 수 k를 맨 앞에 넣고 버블 정렬을 수행한다.
   P(0) <= P(1)이 성립하므로 P(2)는 참이다.

2. P(n) A[0]<=A[1]<=...<=A[n-1]이 성립한다고 가정할 때 P(n+1)이 성립하는지 확인한다.
   P(n)의 배열 A에 임의의 수 k를 넣고 버블 소팅을 수행한다.
   P(n+1)의 원소들은 A[0]<A[1]<...<A[n]이 성립함으로 P(n+1)은 참이다.

3. 1과 2에 의해 모든 자연수 n에 대해 P(n)은 참이다.

문제 풀이

귀납법을 사용해 n-1개가 감염됐을 때 최대 감염수와 n개가 감염됐을 때 최대 감염수를 나타낸다.

서로 다른 두 감염이 일렬로 배치되었을 때 다음 감염은 일어나지 않으므로 대각 배치를 해야함을 알린다.

이를 통해 공식을 얻을 수 있다.

F(n) = n + 2(n - 1) + 2(n - 2) + ... + 2(1) = n^2