할 수 있다는 신념, 하면 된다는 생각

정리에 앞서, 저는 현재 지거국 3학년으로 재학 중인 공대생입니다. 여기에 나와있는 내용들은 제가 직접 공부하고 요약해서 쓰기 때문에 정확하지 않은 정보가 있거나, 원하는 정보를 얻지 못하실 수 있습니다. 최대한 객관적이고 다양하게 준비해서 올리도록 노력하겠습니다. 자료의 출처나 내용에 대한 질문은 댓글이나 hcbeom9635@gmail.com으로 보내주시면 감사하겠습니다.

저는 공부할 때 Discrete Mathematics - Richard Johnsonbaugh 7th 제본판을 사용했습니다.

이산수학 1장. Sets and Logic

명제란?

명제(Proposition)이란 참인지 거짓인지 결정할 수 있는 문장을 뜻합니다. 우리는 일상 속에서 수많은 대화를 주고받습니다. 그 말 중에서는 명제인 것도 있고 아닌 것도 있습니다. 예를 들어서 확인해보겠습니다.

ex)

1) 7을 나눌 수 있는 양의 정수는 오직 2와 5이다. -> 거짓으로 판단되므로 명제가 맞다.

2) 모든 양의 정수 n에 대해, n 보다 큰 소수(prime number)가 있다. -> 참으로 판단되므로 명제가 맞다.

3) x + 10 = 14 -> x의 값에 따라 참 또는 거짓이 될 수 있으므로 명제가 아니다. 즉, 참인지 거짓인지 판명 불가.

• p 와 q 가 명제 일 때,
• conjunction (AND) : p ∧ q
  disjunction (Inclusive-OR) : p v q
  disjunction (Exclusive-OR) : p v q
  negation (NOT) : ~ p , ¬ p

Truth Table

명제는 다양한 연산자를 갖고 있는데, 이 연산자에는 '연산우선순위'가 존재합니다. 어려울 것 없습니다. 괄호가 없을 때 연산자 우선순위는 (not) -> (and) -> (or)의 순으로 연산하면 됩니다.

Conditional Proposition(조건 명제)

조건 명제에 대해 알아보겠습니다. 흔히 얘기하는 "p 이면 q 이다"라는 것이 조건 명제입니다. p는 가정이며, q 는 결론에 해당합니다. 이것을 수식으로 써서 표현하면 p -> q 가 됩니다. 그리고 또 한 가지, 영어로 표현하면 "if p, then q" 또는 "p only if q"인 경우도 모두 p->q와 같은 의미로 받아들이면 됩니다. 

어떤 명제의 진리값이 같다면 명제 P와 Q는 logically equivalent하다고 하고, 수식으로는 방정식의 '='처럼 세 줄로 나타냅니다.

• Biconditional Propositions

바이컨디셔널 프로포지션은 한국말로 '필요충분조건' 입니다. 어렵게 왜 영어로 썼냐구요? 대학가면 다 그렇답니다...

여튼 필요충분조건은 문제에서 " p if and only if q"라고 많이 씁니다. 논리식과 여기표는 다음과 같습니다.

• 역(Converse) & 대우(Contrapositive)

역과 대우는 아주 중요한 개념입니다. 주어진 명제가 참인지 거짓인지 판별할 때 역이나 대우를 이용하며 증명하는 경우도 있으니까요..! 역과 대우의 여기표는 다음과 같습니다.

• Arguments

Deductive reasoning(연역적 추론) : 연속적인 명제들로부터 결론을 도출하는 과정

여기서 Argument는 가정들이 모두 참일 경우에 결론이 참이라는 것을 말합니다. 만약 가정에서 거짓이 존재한다면 결론은 거짓입니다. 수식으로 살펴보겠습니다.

• Rules of Inference (추론의 규칙)

이산수학을 배웠다면 여기 부분에서 가장 골머리가 아플 것이다. 그러나 차근차근 공부하다보면 알게된다. 여기 부분은 나중에 더 자세하게 써야겠다... 일단 외워!