1. soft logig vs hard logic
soft logic은 상식적, 직관적, 느낌적인것 - 빠르다 but 부정확
hard logic이 프로그래밍에서 사용되는 것. - 알고리즘 이해를 위해 필요
2. 명제
p→q 명제식에서 p 명제가 '거짓'이라면 q명제의 참or 거짓 여부와 관계없이 명제식은 '참'이다.
p→q 명제식이 거짓이라면, p명제는 참, q명제는 거짓.
예제1) p, q는 명제, p→q는 거짓이라면 다음 명제식의 참or 거짓여부는? (참/참/참)
1. ~p →q
2 p v q
3. q →p
해설) p는 참, q는 거짓. ~p는 거짓.
예제2) 명제식의 진리표 작성 1: p,q에 대한 명제식 2:p,q,r에 대한 명제식
해설) 명제식을 구성하는 명제들의 T/F의 경우의 수를 생각해보고 논리곱에 대한 진리표를 작성한다.
3. 수학적 귀납법
P(1)이 참이고, P(n)→P(n+1)가 참이면, P(n)는 모든 자연수 n에 대해 참이다.
1)알고리즘의 정확성을 증명하기 위해서는 증명 가능한 '명제로 표현'할 수 있는가
2)P(1)이 참임을 증명, P(n)→P(n+1) 참임을 증명. P(n)은 블랙박스로 둘 것. P(n) 자체가 참인지는 상관없다.
예제3) P(x)→Q(x)임을 증명하려는데 Q(X)가 참: 명제식은 참
P(x)→Q(x)임을 증명하려는데 P(X)가 거짓: 명제식은 참