앞만 보는 사람

정리에 앞서, 저는 현재 지거국 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 (추론의 규칙)

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