기초 논리
논리에는 Hard Logic과 Soft Logic이 있다.
Hard Logic은 우리가 아는 일반적인 논리 사고를 뜻하고,
Soft Logic은 일상적으로 생활을 하면서 습득한 로직 즉, 직관을 뜻한다.
Soft Logic의 문제점
Soft Logic은 프로그래밍 논리 문제를 풀 때 치명적이다.
Soft Logic은 논리적인 느낌을 주는 것일 뿐, 정확하지 않고, 맞는 거 같다는 강한 착각을 일으키기 때문이다.
Soft Logic을 설명하는 두 문장이 있다.
- 졸업하려면 토익 750점 이상 혹은 오픽 IM2 이상이 필요하다
- 복권에 당첨되면 자동차 혹은 천만원을 줍니다.
두 문장은 같은 문장 구조, 같은 표현을 사용하지만 하나는 Inclusive OR, 다른 하나는 Exclusive OR을 의미한다.
첫 번째 문장의 경우, 토익 750점 이상과 오픽 IM2 이상 둘 다 보유하고 있어도 문제가 되지 않게 받아들여진다.
하지만 두 번째 문장의 경우, 차동차와 천만원 두 가지 중 하나만 준다고 받아들여지게 된다.
이처럼 Soft Logic은 어떤 의미인지 모든 사람이 통상적으로 알고 있다고 가정을 하고 있기 때문에 일상 생활에서 유용하게 사용되지만, 논리적으로 부정확한 표현을 사용하고 있다.
문제는 프로그래밍 논리 문제에서도 Soft Logic으로 알고리즘을 이해하려고 할 때 발생한다.
따라서 프로그래밍 논리 문제에 대해서는 증명을 통해 접근을 해야한다.
명제 문제1
다음 명제식 형태로 쓰고 참인지 거짓인지 판단하시오
"만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다."
이 문제의 경우, 미국에서 2080년 월드컵이 열리는 것은 알 수 없다.
따라서 거짓이라고 생각할 수 있지만, 해당 문장은 참이다.
이를 파악하는 것은 생각보다 간단하다.
"만약" 이라는 가정이 거짓이라면, 뒤에 어떤 내용이 오더라도 해당 명제는 항상 참이다.
직관적으로 알기 쉬운 예제를 통해 알아보겠다.
"만약 졸업을 한다면, 100만원을 줄게"
여기서 발생할 수 있는 모든 경우의 수를 적어보겠다.
- 졸업하고 100만원 받은 경우
- 졸업을 해서 100만원을 받았으니 이는 참이다 (True/True)
- 졸업하고 100만원을 못 받은 경우
- 졸업했으나 100만원을 못 받았으니 이는 거짓이다 (True/False)
- 졸업 못하고 100만원을 못 받은 경우
- 졸업을 못하고 100만원 못 받은 것은 참이다 (False/False)
- 졸업 못하고 100만원을 받은 경우
- 졸업을 못하면 100만원을 안 준다는 말은 없었다. 따라서 졸업 못하더라도 100만원을 받은 경우는 통상적으로 맞지는 않더라도 논리적으로 틀린 문제는 아니기에 참에 해당한다. (False/True)
이를 보면 알 수 있듯이, 가정이 거짓이라면 뒤에 어떤 말이 오더라도 이는 참에 해당한다.
또한, 거짓인 경우는 가정이 참일 때 결과가 거짓인 경우 뿐이다.
명제 문제2
다음 명제식 형태로 쓰고 참인지 거짓인지 판단하시오
“만약 198987879683이 Prime Number라면, 2는 짝수이다.”
위에서 말했던 것과 같이, 거짓에 해당하는 경우는 가정이 참일 때, 결과가 거짓인 경우 뿐이다.
따라서 가정이 참인지 거짓인지는 모르더라도, 결과가 참이기 때문에 이 명제는 참이다.
증명
증명이란, 어떠한 사항에 대해서 정확한 명제식으로 표현할 수 있는 것
재밌는 증명 문제도 있었다.
Infinitely Many Prime Numbers
Prime Number의 개수가 유한한 k개라고 가정
모든 Prime Number를 다 곱하고 1을 더한 수를 n이라고 하자
n은 어떤 prime으로 나누어도 나머지가 1이다
그런데 n은 어떤 Prime보다도 크므로 합성수이다
합성수이지만 어떤 Prime으로도 나누어지지 않으므로 모순 발생