- 정리(theorem)란 참으로 확인된 명제를 말함. 하나의 명제를 참으로 확정하는 과정을 증명(proof)이라고 함.
수학적 귀납법
직접증명법
- 명제의 함축 p→q가 참이 됨을 증명하는 방법.
간접증명법
- 대우증명법 : 증명하고자 하는 명제의 대우명제를 이용하는 방법
- 모순증명법 : 주어진 명제를 부정한 뒤 그 식을 전개할 때 결론이 모순임을 보여 명제가 참임을 증명하는 방법
- 반려에 의한 증명법 : 주어진 명제에 모순이 되는 간단한 예를 하나 보임으로써 명제를 증명하는 방법
재귀법
- 재귀법 : 하나의 문제를 그보다 작은 갑스을 가지는 동일한 문제로 계속 단순화시켜 해결하는 방법
- 재귀 알고리즘 : 재귀법을 이용한 프로그램 알고리즘
- 예제 : 하노이 탑
Algorithm hanoi(from, to, by, n, c)
Begin
c=0
if n=1 then
begin
move(1, from, to)
c=c+1
endif
else
begin
hanoi(from, by, to, n=1, c)
move(n, from, to)
c=c+1
hanoi(by, to, from, n-1, c)
endelse
End
프로그램 검증
- 프로그램 명령문은 크게 순서문, 조건문 반복문으로 나뉜다.