0. 프로그래밍과 논리/수학

프로그래밍과 논리/수학

• 명제 : 참이나 거짓을 알 수 있는 식이나 문장
• 진릿값 : 참이나 거짓을 표현

연산(결합)

• 부정(NOT) : 명제의 진릿값이 반대
  ~p 로 표기
• 논리곱(AND) : 명제가 모두 참일 때만 참이 되는 명제
  p^q 로 표기 => p,q 모두 참일 때만 참
• 논리합(OR) : 명제가 모두 거짓일 때만 거짓이 되는 명제
  p V q 로 표기 => p,q 모두 거짓일 때만 거짓
• 베타적 논리합(XOR) : 둘 중 하나만 참일 때 참이 되는 명제

합성

우선순위 : ~ > V,^ > →, ↔

• 항진명제 : 진릿값이 항상 참인 명제
  ex) (~p^q)Vq
• 모순명제 : 진릿값이 항상 거짓인 명제
  ex) (~pVq)^(p^~q)
• 사건명제 : 항진명제도 모순명제도 아닌 명제
• 조건명제 : 조건과 결론으로 제시되는 명제
  p → q (p : 조건, q : 결론)
• 쌍방조건명제 : 두 명제가 모두 조건과 결론이 되는 명제
  p ↔ q

역, 이, 대우

• 조건명제 p → q 의 역, 이 대우를 알아봅시다.
  • 역 : q → p
  • 이 : ~p → ~q
  • 대우 : ~q → ~p

[진리표]

p     q	p → q	q → p	~p → ~q	~q → ~p
T    T T    F F    T F    T	T F T T	T T F T	T T F T	T F T T

진리표를 통해 명제의 쌍을 확인할 수 있습니다.

• 명제와 대우는 쌍이 됩니다.
• 명제의 역과 이는 쌍이 됩니다.

=> 대우가 참이라면 해당 명제도 참이 됩니다.

 

 

증명 (항진명제)

• Trivial Proof

=> 모든 x에 대해 F(x) → G(x) 에서 항상 G가 참인 경우

ex) n이 홀수이면 4n^3 +6n^2+12는 짝수이다.

 

• Vacuous Proof

=> 모든 x에 대해 F(x) → G(x) 에서 F(x)가 항상 거짓인 경우

ex) 4n^3 + 6n^2 + 11이 짝수이면 n이 홀수이다.

 

 

 

제가 공부하고 이해한 내용을 정리한 것이라 틀린 부분이 있을수도 있습니다.
 오늘 배운 두 가지 증명이 도움과 명제의 쌍(명제의 대우의 참,거짓 확인)을 활용한다면 주어진 명제의 참 거짓을 확인할 때 유용할 것이라 생각됩니다.