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

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

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

이산수학 1장. Sets and Logic

연산자(Quantifier)

이산수학 1장에서는 두 가지의 연산자를 배웁니다.

Universal Quantifier ∀

Existential Quantifier ∃

입니다.

• Universal Quantifier  ∀xP(x)

"for every" , "for all" 즉, 모든 x에 대해 만족하는 명제를 나타낼 때 쓰입니다. Universal Quantifier 명제가 참인지 거짓인지 판별하기 위해서는 반례(CounterExample)를 들어서 판별할 수 있습니다. 모든 x에 대해 만족하는 명제가 거짓이라면, 그 명제를 만족하지 않는 x를 찾으면 됩니다. 수식으로 설명해보겠습니다.

Ex)

• Existential Quantifier  ∃

"there exist" 즉, 명제에 해당하는 x의 값이 하나라도 '존재'하는지의 여부를 확인할 때 쓰입니다. 예시를 통해 확인해보겠습니다.

Ex)

그렇다면 이 두 가지를 동시에 쓸 수는 없을까요? 당연히 쓸 수 있습니다. 그런 경우를 Nested Quantifier라고 합니다.

• Nested Quantifier

Ex)

모든 x에 대해 식을 만족하는 모든 y가 있다면 명제는 참입니다. Nested Quantifier에 드모르간 법칙을 사용하면 아래와 같이 됩니다.

드모르간 법칙을 사용할 때 주의할 점은, ∀이 not을 취하면 ∃이 되고, ∃이 not을 취하면 ∀가 되는 것이 핵심입니다. 또한 명제에도 Not을 포함해줘야 합니다.

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

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

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

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

이산수학 1장. Sets and Logic

집합(Set)이란?

Set(집합)은 서로 다른 물체들의 모음 입니다. 그리고 집합 안에 있는 것을 Elements(원소)라고 불립니다.

예를 들어 집합 A에 원소 x가 있다면 아래와 같이 간단하게 표현합니다.

x라는 원소를 조금 더 구체화 시켜서 예를 들어봅시다.

A안에 {1,3,5,7}라는 원소가 있어서 1은 A에 속한다고 볼 수 있습니다. 

또한 B안에는 k가 0~5까지의 상수이므로 {1,3,5,7,9,11}라는 원소가 있어서 3또한 A에 속합니다.

이렇게 간단하고 유한한 집합을 Finite sets이라고 불립니다.

반대로 무한한 집합을 Infinite sets이라고 합니다. 무한한 집합은 무엇이 있을까요? 대표적인 예만 들어보자면

정수의 집합은 무한한 집합입니다.

이렇듯 사용자에 따라 여러 가지 종류의 집합을 만들 수 있습니다. X, Y라는 집합이 있을 때, X의 모든 원소가 Y에 포함된다면 X는 Y의 부분집합(subset)이며 기호로는 아래처럼 나타낼 수 있습니다.

또한 X가 Y의 부분집합일 때 X≠Y이면 X는 Y의 진부분집합(proper subset)라고 하며 기호로는 다음과 같습니다.

여기서 중요한 점은, 대부분 교육과정에서는 부분집합과 진부분집합의 표기를 혼용해서 사용하는 것입니다. 사실 중요한 부분은 아니므로 그냥 넘어가도 좋습니다. 만약 교수님께서 구분해서 사용하신다면 그렇게 쓰고, 아니면 아닌 대로 쓰면 됩니다..하하

예를 들어 아래와 같은 집합 A,B가 있으면 A는 B의 부분집합으로 볼 수 있습니다.

생소한 집합인 멱집합(Power Set)와 기수(Cardinality)라는 것을 알아보겠습니다.

멱집합은 집합 X의 모든 부분 집합의 집합입니다.

직관적으로 알 수 있도록 식으로 보면 아래와 같습니다.

기수(Cardinality)는 집합 안의 원소의 수를 뜻합니다. 기호로는 절댓값처럼(A의 기수 = |A|) 쓰면 됩니다.

집합 A에는 a,b의 두 가지 원소만 있으므로

여기서 멱집합과 기수간의 관계를 알아보겠습니다. 

A = {a, b} 이고 P(A) = {∅, {a}, {b}, {a,b}}이므로 |P(A)| = 4 

즉, 집합 A의 원소가 n개일 때 멱집합A의 기수는

집합 안에는 또 다른 집합이 있는 경우도 있습니다. 그런 경우를 벤다이어그램으로 나타내면 아래와 같고, 이러한 모음을 Pairwise Disjoint라고 합니다.

Partition이라는 것은 X가 nonempty subsets S의 모음일 때, X안의 모든 원소들이 S의 한 멤버 안에만 속해 있다면 S는 X의 partition이라고 합니다. 즉, S가 X의 partition이면 S는 pairwise disjoint하다고 볼 수 있습니다.

글로만 보면 확 와닿지 않는데, 예시를 보면 쉽게 이해할 수 있습니다.

마지막으로 Cartesian Product(데카르트 곱)에 대해서 알아보겠습니다. 데카르트 곱은 기호로 X x Y이며 정의는

x ∈ X and y ∈ Y 인 모든 순서쌍 (x,y)들의 집합이다. 데카르트 곱의 예시를 보고 이해해보겠습니다.

지금까지 집합에 대한 내용을 알아봤습니다. 사실 집합은 중학생 때부터 배운 것들이라서 이해하는데 큰 어려움이 없습니다. 그러나 생소한 용어와 영어로 나오니까 몰랐던 부분은 체크하는 게 좋습니다. 다음장에서는 명제를 알아보겠습니다.