논리와 증명

논리 연습

Soft 로직은 직관적으로 생각되기 때문에 Hard 로직을 잘 생각해야 함

• 명제식
  가정 참 & 결론 참 = 명제 참
  가정 참 & 결론 거짓 = 명제 거짓
  가정 거짓 = 명제 무조건 참

p -> q 가 거짓이라고 하자
다음 명제식의 참 거짓은?

~p -> q : 참
pVq : 참 (논리합)
q -> p : 참

• 역: 결론, 가정

• 이: ~가정,~결론

• 대우: ~결론,~가정

• 진리표
  

증명

수학적 귀납법

P(1)이 참이고, P(n)->p(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.

버블 소트의 증명

배열 A[1],A[2],A[3],...,A[N]을 소팅하는 알고리즘의 정확성을 증멸하려고 한다면,
증명이 가능한 명제
"A[1]<A[2]<A[3]<...<A[N]"를 활용해 증명함

• 증명 연습문제
  
  

근데 화질 480p 실화인가요...