논리와 증명

1. 논리와 증명

문제1: 다음을 명제식 형태로 쓰고 참인지 거짓인지 판단하시오

① 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다.

p이면 q이다 라는 명제식에서
p 가 거짓이면 전체는 참

ex) 이번 시험에 100점 받으면 치킨 사줄게

100점 받아서 치킨 사줌 -> 약속 지킴
100점 받았는데 치킨 안사줌 -> 약속 안지킴
100점 못받았는데 치킨 사줌 -> 약속 지킴
100점 못받았는데 치킨 안사줌 -> 약속 지킴

② 만약 19893827938274839이 Prime Number라면, 2는 짝수이다.

p의 참거짓 여부에 상관없이, q가 참이니까 전체가 참
= p가 거짓이면 전체가 참이므로 참
= p가 참이어도 q가 참이니까 전체가 참이므로 참

ex) 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다

• 역 (q -> p)
  • 미국에서 2080년 월드컵이 열린다면, 0은 홀수이다.
• 이 (~p -> ~q)
  • 만약 0이 홀수가 아니라면(짝수라면), 미국에서 2080년 월드컵이 열리지 않는다.
• 대우 (~q -> ~p)
  • 미국에서 2080년 월드컵이 열리지 않는다면, 0은 홀수가 아니다(짝수이다).

• 수학적 귀납법의 기본형
  • P(1)이 참이고, P(n) -> P(n+1) 이 참이면, P(n) 은 모든 자연수 n에 대해서 참이다.
  • 여기서 중요한 것은 P(n) 의 참/거짓 여부와 상관 없이 P(n+1) 만 참이면 다 참이다.
  • 따라서 P(n)이 참인지 걱정하지 말고, sum(x-1) 이 진짜로 제대로 된 값을 리턴하는지 확인하지 말고, 참을 리턴한다고 가정하고 그 때 sum(x)가 제대로 된 값을 리턴함을 보이면 된다.